EmergencyEMERGENCY? Get 24/7 Help Now!

MySQL 8.0: Descending Indexes Can Speed Up Your Queries

 | October 20, 2016 |  Posted In: MySQL

PREVIOUS POST
NEXT POST

Descending IndexesIn this blog, we’ll discuss descending indexes in MySQL 8.0.

Summary

The future MySQL 8.0 will (probably) have a great new feature: support for index sort order on disk (i.e., indexes can be physically sorted in descending order). In the MySQL 8.0 Labs release (new optimizer preview), when you create an index you can specify the order “asc” or “desc”, and it will be supported (for B-Tree indexes). That can be especially helpful for queries like “SELECT … ORDER BY event_date DESC, name ASC LIMIT 10″ (ORDER BY clause with ASC and DESC sort).

MySQL 5.6 and 5.7 Index Order

Actually, the support for this syntax (CREATE INDEX … col_name … [ASC | DESC]) was there for a long time, but it was reserved for future extensions: if you created an index and specify “DESC” keyword was ignored in MySQL 5.6 and 5.7 (an index is always created in ascending order).

At the same time, MySQL (all versions) can scan the index backward, so those two queries will use index:

In the second query, MySQL scans the index backward for two fields.

What is also very important here is the “LIMIT 10”. MySQL scans the table in the order of index (and avoids filesort), then it aborts the scan after finding 10 rows. That makes the query almost instant:

But what about a different order: DESC and ASC (which make sense in the example where we want to show the latest events first but also use the secondary order, alphabetical, by event name). The query does a filesort and performs much slower:

MySQL 8.0 (Labs release)

The MySQL Server 8.0.0 Optimizer labs release includes new support for the index sort order (for InnoDB only). Here is how our query from the above performs:

I’ve created an index, targeted for our specific query order: event_date descending, name ascending. Now it works much faster:

The index (event_date desc, name asc) satisfies two conditions:

  • order by event_date desc, name asc: forward index scan
  • order by event_date asc, name desc: backward index scan

Note the “Backward index scan” in the Extra column above.

This is a similar situation to an index on (event_date, name) sorted in ascending order, and can be used to satisfy both event_date asc, name asc and event_date desc, name desc (same order across two fields).

The original query that ran in 2.41 seconds (and performed a filesort operation), now runs almost instantly with the new index:

Please note descending indexes only work for InnoDB:

Workaround for MySQL 5.7

A (rather limited) workaround exist for MySQL 5.7, and involves creating (and indexing) a virtual field. Let’s say that instead of varchar, we need to order by an unsigned integer (i.e., “id”, which is an auto_increment field in another table). Our query will look like this: “select * from events order by event_date desc, profile_id asc limit 10”. In this case, we can “invert” the profile_id by making it negative and store it in a “virtual” (aka “generated”) column:

Then we can index it together with the date field:

Now we can use the the profile_id_negative index for “desc” sort order:

That is much faster, but produces the same results as the following query:

Conclusion

MySQL 8.0 (Labs release) has a preview of this great new index sort order feature, which can significantly increase the performance of frequently slow query patterns: order by field1 desc, field2 asc limit N. 

This feature can be found in other databases (for example, in MongoDB). It might be that this much-needed feature will be at some point backported into MySQL 5.7, so we can use it in that version.

I want to thank the MySQL Server Development team at Oracle for implementing it. If you are interested in other MySQL optimizer features, take a look at Manyi Lu’s presentation at Percona Live Amsterdam, where she talks about other great MySQL 8.0 features: histograms, invisible indexes, common table expressions and extended JSON support.

PREVIOUS POST
NEXT POST
Alexander Rubin

Alexander joined Percona in 2013. Alexander worked with MySQL since 2000 as DBA and Application Developer. Before joining Percona he was doing MySQL consulting as a principal consultant for over 7 years (started with MySQL AB in 2006, then Sun Microsystems and then Oracle). He helped many customers design large, scalable and highly available MySQL systems and optimize MySQL performance. Alexander also helped customers design Big Data stores with Apache Hadoop and related technologies.

3 Comments

    • Great capability but be very careful with designs that are dependent on timeseries high volume inserts using a datetimestamp index descending. I have tested this on many other databases over the last 35 years and everyone had this issue. If the index maintenance process is constantly inserting new index records based on latest timestamp the process is constantly forcing the 3rd index page in the b-tree to reshuffle or page split to accomodate inserting new records before previous records inserted. In summary either very slow insert times and / or locking issues. Maybe mysql 8.0 has found a better way, I look forward to the opportunity to test this myself or hear back from others regarding same.

  • This is an exciting feature in MySQL 8 – but do you have some benchmarks on the overhead that it creates when inserting new entries in the table? Is it the same overhead as a normal index, or is it higher?

    On an application experiencing a high percentage of writes, the overhead cost of this index would be an important issue to think about.

Leave a Reply