Recently, I was asked about an interesting case in ORDER BY … LIMIT optimization. Consider a table
create table tbl ( ... KEY key1(col1, col2), PRIMARY KEY (pk) ) engine=InnoDB;
Consider queries like:
select * from tbl where col1='foo' and col2=123 order by pk limit 1; select * from tbl where col1='bar' and col2=123 order by pk limit 1;
These run nearly instantly. But, if one combines these two queries with
col1='bar' into one query with
col1 IN ('foo','bar'):
select * from tbl where col1 IN ('foo','bar') and col2=123 order by pk limit 1;
then the query is be orders of magnitude slower than both of the queries with
The first thing to note when doing investigation is to note that the table uses InnoDB engine, which has extended_keys feature. This means, the index
KEY key1(col1, col2)
KEY key1(col1, col2, pk)
Once you have that, and also you have
col1='foo' AND col2=123 in the WHERE clause, the optimizer is able to see that index `key1` produces records ordered by the
`pk` column, i.e. in the order required by the ORDER BY clause. This allows to satisfy the
LIMIT 1 part by reading just one row.
Now, if we change
col1 IN('foo','bar'), we will still be able to use index `key1`, but the rows we read will not be ordered by `pk`. They will come in two ordered batches:
'bar', 123, pkX 'bar', 123, pkX+1 'bar', 123, pkX+2 ... 'foo', 123, pkY 'foo', 123, pkY+1 'foo', 123, pkY+2
The query has
ORDER BY pk LIMIT 1, but, since the rowset is not ordered by pk, the optimizer will have to read all of the rows, sort them, and find the row with the least value of `pk`.
Now, wouldn’t it be great if the optimizer was aware that the index scan returns two ordered batches? It would be able to read not more than #LIMIT rows from each batch. I can think of two possible execution strategies:
- Run something similar to index_merge strategy: start an index scan
col1='foo'and an index scan on
col1='bar'. Merge the two ordered streams until we’ve found #limit rows. This approach works well when you’re merging a few streams. If there are a lot of streams, the overhead of starting concurrent index scans will start to show up.
- Use the same index cursor to #LIMIT rows from the first batch, then from the second, and so forth. Merge these ordered streams using filesort’s merge pass or priority queue. This approach reads more rows than the first one, but we don’t have to create another index cursor.
Now, the question is whether this kind of queries is frequent enough to implement this optimization.