Last week I optimized some MySQL queries which triggered the 'not-using-index' warning, even when I had all fields which were used for selecting and sorting indexed. I think a JOIN on a nested subselect somehow confused MySQL: when I duplicated some extra restraining WHERE clauses into the subselect, response shot up from 800msec to 12msec per query. Very nice. But the query still shows up as 'not-using-index', which is strange.
Sometimes when you have complex queries it can make sense to create a temp table, create indexes on that, and then query off of that. But queries like that should show up in reporting, not in serving live web pages.
That said, if you're selecting more than 5% or so of the rows in a table, you're probably better off not using an index.
Another random tip. There is a world of difference between putting indexes on 2 fields, and putting a composite index on 2 fields. If you have restrictive conditions on 2 fields, MySQL has to work with the entire list of rows that match at least one of those conditions. (I don't know whether MySQL has the trick of joining indexes together before looking at rows, but even if it does it has to work with a list of rows matching the condition.) By contrast with a composite index MySQL can only look at rows that match both conditions. Much more efficient.
MySQL's query plan is odd at times. What does an explain look like on that query? If any portion of the query, including subselects isn't able to use an index, it will report it. You can try to force indicies with USE INDEX/FORCE INDEX which can sometimes help.
Ah, I was having trouble with another slow query; however, the EXPLAIN showed that the correct indices were used. I managed to speed it up by restricting the size of the inner SELECT with some extra constraints. From 4 seconds downto 0.1 seconds!
