expensive query

I have to search a data base for a variable number terms, checking
certain fields against the terms, provided all the terms are matched,
while each may match any field, I want that row returned. My problem is,
that this query always takes too long -- and I need it done quickly.
To illustrate, a fictitious similar query would look like this,
two terms (a & b), and four fields (one, two, three, four):

SELECT one, two, three, four
FROM sometable
WHERE (one ~* 'a' OR two ~* 'a' OR three ~* 'a' OR four ~* 'a')
AND (one ~* 'b' OR two ~* 'b' OR three ~* 'b' OR four ~* 'b');

to complicate things, when I perform this, it's actually a join between
three tables, one having 800+ rows. I intend to waste space and save time
by combining all this info into one table. But this still won't be very
fast, is there any way to make this fast? One thing I'm considering is
putting all of this data into one field so that only one text search per
term per record is made, so that instead of doing ~6400 text searches, I
only need ~1600, in the above example. Does this sound like it would help
any? Are there any other suggestions?