I run a community site. One of the slowest features on the site right now is the user search. And has a couple hundred new accounts are being made daily, it only will get worse.

Thing is they have multiple options to look for one another.

They can search by age, by distance, by dating status, by sexual orientation, by whether they have pictures uploaded, whether they're currently online, etc.

I was really hoping to be able to create a multi-column index on the major search fields to optimize lookups, but it doesn't seem possible. The fields are all optional. So if they don't specify something, it's not included (unless I just create a range for the unspecified values). But that's where the problem lies, once you hit a range on a key_partx, key_partx+1 through key_partn are no longer utilized to optimize the query.

Is there anything I can do for this sort of problem?