MySQL 8.0 Labs – Descending Indexes in MySQL

Starting with the 8.0 optimizer labs release the MySQL server now supports descending indexes. As I will detail in this post, this new feature can be used to eliminate the need for sorting results, and lead to performance improvements in a number of queries.

Introduction

Up until this release, all indexes were created in ascending order. While the syntax itself is parsed, the meta data is not preserved. For example in MySQL 5.7:

While it should be noted that the MySQL 5.7 optimizer is able to scan an ascending index backwards (to give descending order), it comes at a higher cost. As shown further down, we can see forward index scans are ~15% better than backward index scans.

The primary limitation of not being able to support descending indexes is that the optimizer must resort to a filesort for a mixed order such as ORDER BY a DESC, b ASC.

Improvements in MySQL 8.0

With the introduction of descending indexes, InnoDB can now store entries in descending order and and the optimizer will take advantage of it when descending order is requested in the query. Repeating the above example, we can see that the index order information is correctly retained when creating a table:

The output of EXPLAIN has also been improved to differentiate between backward and forward index scans. In case of MySQL-5.7, we use backward index scans or filesort for all queries except Query 2 and Query 6 shown below as both these queries require only ascending order.

Query 1: SELECT * FROM t1 ORDER BY a DESC;

Query 2: SELECT * FROM t1 ORDER BY a ASC;

Query 3: SELECT * FROM t1 ORDER BY a DESC, b ASC;

Query 4: SELECT * FROM t1 ORDER BY a ASC, b DESC;

Query 5: SELECT * FROM t1 ORDER BY a DESC, b DESC;

Query 5: SELECT * FROM t1 ORDER BY a ASC, b ASC;

Below are the performance numbers for all of the above 6 queries when table has one index a_desc_b_asc (a DESC, b ASC). In MySQL-5.7 it is a_asc_b_asc(a ASC, b ASC) as there is no support for descending indexes. Data size is 10 Million rows.

desc_index

Understanding the Performance Numbers:

  1. We see improvement in Query 1 as the order requested is DESC for column “a”.
  2. For Query 2 as order requested is ASC we can see that it takes more time in MySQL-8.0 as we do backward index scan (note that MySQL-8.0 in general is performing better as seen in the graphs. MySQL-5.7 forward scan is taking same time as that of MySQL-8.0 backward scan).
  3. Query 3 is similar to Query 1 with the requested order same as index order. However in MySQL-5.7, for any queries which request  mixed order, it resorts to filesort. Hence the difference is huge.
  4. As we see, Query 4 does a backward index scan hence takes more time than Query 3 in MySQL-8.0. However for Query 5 and Query 6 the requested order ( (a DESC, b DESC)/(a ASC, b ASC)) cannot be satisfied by doing forward or backward index scans in MySQL-8.0. So it uses filesort. But MySQL-5.7 can use forward/backward index scans to give the requested order in this case as ASC/DESC index flags are ignored in MySQL-5.7.
  5. If user wants to avoid filesorts for Query 5 and Query 6, he/she can alter the table to add a key (a ASC, b ASC) . Further to this, if the user wants to avoid backward index scans too, he/she can add both ( a ASC, b DESC) and (a DESC, b DESC).

Here is the final comparison of MySQL-5.7.14 and MySQL-8.0-labs after the additional indexes under point #5 are added:

desc_index-2

Note that, in MySQL-5.7 we cannot add additional indexes to improve the performance for the above mentioned queries. Also, with this feature, materialization could be avoided in some cases like when mixed order is requested on the first table in a join.These are some of the use cases where descending indexes have improved the performance. Descending indexes are also used by range scan access method. Although not all range scan access methods use descending keyparts, we will be trying to lift the limitations in the future.

Changes to Behavior

Along with the introduction of descending indexes we have removed support for implicitly ordering results in ascending order of columns mentioned as part of a GROUP BY. Along with the above improvements, we are also seeing performance improved in cases where order was implied but potentially not required.

Conclusion

We are excited to be able to address one of the long standing feature requests frm the MySQL community. Please check out descending indexes and let us know your thoughts!

About Chaithra Gopalareddy

Chaithra Gopalaredy has been working with MySQL database team since 2011. She is currently employed by Oracle, based in India, Bangalore. She is Principal Software Developer for the Optimizer Team of the MySQL database. She has a background in the database industry, working for Alcatel Lucent's DataBlitz main memory database in past.

7 thoughts on “MySQL 8.0 Labs – Descending Indexes in MySQL

  1. HI, Chaithra Gopalareddy.

    “While it should be noted that the MySQL 5.7 optimizer is able to scan an ascending index backwards (to give descending order), it comes at a higher cost. As shown further down, we can see forward index scans are ~15% better than backward index scans.”

    Would you please show me the reason for the performance difference between forward scan and backward scan , I wonder why ?

    1. Hello musazhang,

      Thanks for showing interest in the new feature. The ~15% cost benefit in forward scans can be attributed to the optimizations done in innodb to favor forward scans over backward scans.
      For ex:
      W.r.t a scan within the page – The records in a page form a singly linked list. To get the next record, a forward scan just follows the link where as the backward scan need to start from the beginning(first slot) till the current slot/record to identify the previous record.
      Along with the above, there are some more contributing factors like, during page switch – page latching rules currently defined in innodb favor forward scans over backward scans.

      So it is recommended to use descending indexes to get the performance benefit.

      Thanks,
      Chaithra

Leave a Reply

Your email address will not be published. Required fields are marked *

Please enter * Time limit is exhausted. Please reload CAPTCHA.