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.