I've a place of my application where lots of complex queries are now being carried out, coming back 10s of records per page from a table of 1000s. Here are a few samples.

SELECT `tasks`.* FROM `tasks` WHERE (`tasks`.company_id = 21) AND (employee_id IS NULL) AND (status != 'Complete') AND (status != 'Cancelled') ORDER BY scheduled desc LIMIT 0, 30;

SELECT `tasks`.* FROM `tasks` WHERE (`tasks`.company_id = 21) AND (employee_id = 0) AND (status != 'Complete') AND (status != 'Cancelled') AND (scheduled IS NOT NULL) AND (scheduled > '2011-03-28' AND scheduled < '2011-09-28');

SELECT `tasks`.* FROM `tasks` WHERE (`tasks`.employee_id = 27) AND (status != 'Complete') AND (status != 'Cancelled') ORDER BY scheduled desc LIMIT 0, 30

employee_id and status will always be present company_id is almost always present, and scheduled is only the default ordering, that the user can alter.

I attempted these indexes:

# ignored for some reason - did not seem to build successfully in the db
add_index :tasks, [:company_id, :employee_id, :status, :scheduled]

# db favorite, but often results in FILESORT
add_index :tasks, [:employee_id, :status, :scheduled]

What's the easiest method to cope with my problem and lower the amount of FILESORTS I am making these queries?

Please tell me basically can offer anymore more information.