Negation for searches

What is an efficient way to search for records that does not contain a
specific keyword.

e.g.

Find people where the state is not "MA" and first name contains "John".

This should find:

John Doe in NY
Johnston Ried in CA

But not:

John Swann in MA

I have been using my own search routines for this but they are not very
efficient. I'd like to upgrade it to something like
acts_as_fulltextable, Ferret, or Solr, but not sure which one is
suitable for what I need.

Thanks!

use sphinx with gem as thinking_sphinx

is super fast full text search engine

Best Regards, Dieinzige