Optimizing Subquery and sorting

Question

Is there a way to set an index that do not use any kind of filesorting for the following query in mysql?

SELECT * FROM bigtable WHERE id IN ([a indexed subquery]) ORDER BY title;

The ID in this case is the primary key. Innodb is used. Doing a EXPLAIN on this kind of query will always say it's using filesort.

Edit 1:

The subquery is not important since it in my case is generated automatically. But for the sake of argument lets make the query like this instead

SELECT * FROM bigtable WHERE id IN (4,6,8,7,10,40,21,54...) ORDER BY title; 

Is there any way to to index this query that do not use a filesort for the "ORDER BY"?

Bonus question: Are there any other databases that can do this?

Answer 1

Doing lots of research and already knowing lots about indexes I figured out that this is not possible with the current type of indexes for my exact example. I actually haven't found any other db that can do this either.

The fact remains that the final list needs to be sorted manually by the db, but the sorting is still very fast so maybe this isn't a big issue. Thanks for all the answers!

If I'm wrong please correct me ;-)

Answer 2

Is it really this bad to have a filesort operation going on here? From what I get from e.g. here it might be called FILEsort, but in essence it's just an ordinary sort; which you explicitly request in your ORDER BY.

I'm assuming the system is using the index on the id field to find the relevant records which are by definition stored in id-order, extract the Title value from the records found and then sorts that result before returning it to the client.

I can't come up with a good way to avoid this, nor why this would be bad. If you really, really, really wanted to, you could try to somehow change the PK to the TITLE + ID field and then let the query scan the entire table to find the right ID's in the right order. But this would be terribly inefficient and would only (potentially) work with single-threading. Once it breaks out over multiple threads you're still going to have to accumulate the result and sort the result to be sure about the output. Given the likelihood that there might be optimisations that 'screw up' the naive 'scanning from begin to end approach' I wouldn't be too surprised if even in the best-case scenario the system would go the safe way and to the sort anyway.

Answer 3

Do you have permissions to create temporary table in the database (or any other database hosted on the same mysql server)?

If yes, then I propose the following solution:

CREATE TEMPORARY TABLE temp_indexed_subquery
SELECT id 
FROM bigtable 
WHERE "where conditions";
SELECT b.* FROM bigtable AS b
JOIN temp_indexed_subquery AS t 
ON t.id = b.id;

If no, then try this:

SELECT b.* 
FROM bigtable 
JOIN (SELECT id FROM bigtable WHERE "where conditions") t ON t.id = b.id;

Its harder to help more without knowing the table structure or the sub-query.

Edit: Ah, I had a similar problem with filesort, and got around it the following way (modifying the first proposed solution):

CREATE TEMPORARY TABLE temp_indexed_subquery
(UNIQUE KEY id(id), KEY title(title)) 
SELECT id, title
FROM bigtable 
WHERE "where conditions";
SELECT b.*, t.title FROM temp_indexed_subquery AS t
JOIN bigtable AS b
ON b.id = t.id
ORDER BY t.title;

Here I'm adding an index on the temporary table's "title" field, and sorting by that. In my case, doing this meant MySQL didn't have to use filesort to give me an ordered result. I hope this helps. (by the way, how many rows does bigtable have, and how many ids are typically in the indexed subquery)

Answer 4

Under some circumstances, MySQL will use an index for sorting. If you have an index on bigtable(title), then the following query should use the index:

select *
from bigtable
order by title;

I would expect your query to also use the index, unless the "indexed subquery" causes the optimizer to us.e a different execution plan. MySQL does a pretty good job documenting its optimization strategies for order by