Descending indexing and loose index scanPeter Zaitsev
Comments to my previous posts, especially this one by Gokhan inspired me to write a bit about descending indexes and about loose index scan, or what Gokhan calls “better range” support. None of these are actially related to Innodb tables in general – these are features MySQL should get for all storage engines at some point.
Descending indexes – This is something MySQL does not have at this point, but it was not where for so long at large extent because it is less problem than many people think. First – if index is ascending it does not mean it can’t be scanned in reverse order and it will well be. This is how MySQL will optimize indexed ORDER BY col DESC queries for example. Reverse scan could be as fast as forward scan – this is however where storage engines and operating systems come in play. For example certain operation systems might not do backward read-ahead which may slow it down a bit. Or some storage engines, such as MyISAM (for packed indexes) may have reverse scan being much slower than forward scan.
So when do you really need Descending indexes ? Most typical case is when you want to order by two colums in different directions: … ORDER BY price ASC, date DESC LIMIT 10 If you have indexed on (price,date) in ascending order you will not be able to optimize this query well – external sort (“filesort”) will be needed. If you would be able to build index on price ASC, date DESC the same query could retrive data in aready sorted order.
This is however something you can workaround by having something like “reverse_date” column and using it for sort. With MySQL 5.0 you even can use triggers to update it as real date updates so it becomes less ugly. In fact this is for example why you would see “reverse_timestamp” field in Wikipedia table structure.
Loose index scan – Number of years ago when I just started using MySQL I thought it would have any optimization which could come to my mind. For example if I would have (A>0 and B>6) clause and index (A,B) I expected it would start looking at all values where A>0 instantly jumping to onces have B>6 by using index. It is possibe. So I was shocked and upset to find out it did not. And this optimization is still not implemented. This is very important item to remember when you designing your new applications or porting ones from other databases. Designing the indexes for MySQL you should only make sure queries use “=” for all keyparts in the last of index. Only last one is allowed to have “range” clauses, such as >, IN etc. All clauses which follow the range in the index will not use index for their operation.
Let me give one more example KEY (A,B,C) A=5 and B>6 and C=7 In this case index will be used to check A=5 and B>6 cause. C=7 will not be using the index (rows with all C values will be retrieved from the index) and if this is not the index covered query you might rather shorten your key to KEY(A,B) to keep index smaller.
The good news are Loose index scan implementation is finally on a way. In fact it was even implemented in MySQL 5.0, but only for very narrow case of aggregate queries.
In general complete loose index scan implementation is one of my most wanted features for MySQL optimizer.
P.S If you post queries in your comments please also explain which indexes do you have on the table. SHOW CREATE TABLE is the best. Otherwise I can get you wrong.