Speed up search across multiple columns

We have a table:

user_info (user_id,domain_id,first_name,middle_name,last_name,work_place,.,.,.)

Now, we have a user search that search across three columns first_name,last_name and work_place.
If a user enters a query like: "Bill Gates" we have to search following conditions
either

• First name, last name or work place is "Bill Gates" OR

• first name is bill, last name gates

• first name bill, workplace gates

• ..

• ..

• so on

My query is:

SELECT * FROM users WHERE active=1
AND ((first_name = 'Bill Gates' OR last_name = 'Bill Gates' OR work_place = 'Bill Gates') 
OR ((first_name = 'Bill' OR last_name = 'Bill' OR work_place = 'Bill') 
AND (first_name = 'Gates' OR last_name = 'Gates' OR work_place = 'Gates')) );

and I have a composite index on (first_name,last_name,work_place) but the query is extremely slow. Takes about 3 minutes to execute.

Any idea how to speed this one up ? I have tried unions but its still slow

You could try something like this to reduce the ORs. This was validated on SQL Server so you may need to tweak a bit:

SELECT * FROM users 
WHERE active=1
AND first_name  IN ('Bill Gates', 'Bill', 'Gates')
OR last_name    IN ('Bill Gates', 'Bill', 'Gates')
OR workplace    IN ('Bill Gates', 'Bill', 'Gates')

Seems like some data validation is called for overall though.

StackExchange Database Administrators Q#15172, answer score: 3