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:
|
1
2
3
4
5
6
7
8
9
10
11
12
|
mysql 5.7> CREATE TABLE t1 (a INT, b INT, INDEX a_desc_b_asc (a DESC, b ASC)); Query OK, 0 rows affected (0.47 sec) mysql 5.7> SHOW CREATE TABLE t1\G *************************** 1. row *************************** Table: t1 Create Table: CREATE TABLE `t1` ( `a` int(11) DEFAULT NULL, `b` int(11) DEFAULT NULL, KEY `a_desc_b_asc` (`a`,`b`) <-- Order is not preserved ) ENGINE=InnoDB DEFAULT CHARSET=latin1 1 row in set (0.00 sec) |
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:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
mysql 8.0> CREATE TABLE t1 (a INT, b INT, INDEX a_desc_b_asc (a DESC, b ASC)); Query OK, 0 rows affected (0.47 sec) mysql 8.0> show create table t1; +-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+ | Table | Create Table | +-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+ | t1 | CREATE TABLE `t1` ( `a` int(11) DEFAULT NULL, `b` int(11) DEFAULT NULL, KEY `a_desc_b_asc` (`a` DESC,`b`) ) ENGINE=InnoDB DEFAULT CHARSET=latin1 | +-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+ 1 row in set (0.00 sec) |
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;
|
1
2
3
4
5
6
7
|
mysql 8.0> explain SELECT * FROM t1 ORDER BY a DESC; +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-------------+ | 1 | SIMPLE | t1 | NULL | index | NULL | a_desc_b_asc | 10 | NULL | 10 | 100.00 | Using index | +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-------------+ 1 row in set, 1 warning (0.00 sec) |
Query 2: SELECT * FROM t1 ORDER BY a ASC;
|
1
2
3
4
5
6
7
|
mysql 8.0> explain SELECT * FROM t1 ORDER BY a ASC; +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+----------------------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+----------------------------------+ | 1 | SIMPLE | t1 | NULL | index | NULL | a_desc_b_asc | 10 | NULL | 10 | 100.00 | Backward index scan; Using index | +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+----------------------------------+ 1 row in set, 1 warning (0.00 sec) |
Query 3: SELECT * FROM t1 ORDER BY a DESC, b ASC;
|
1
2
3
4
5
6
7
|
mysql 8.0> EXPLAIN SELECT * FROM t1 ORDER BY a DESC, b ASC; +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-------------+ | 1 | SIMPLE | t1 | NULL | index | NULL | a_desc_b_asc | 10 | NULL | 10 | 100.00 | Using index | +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-------------+ 1 row in set, 1 warning (0.00 sec) |
Query 4: SELECT * FROM t1 ORDER BY a ASC, b DESC;
|
1
2
3
4
5
6
7
|
mysql 8.0> EXPLAIN SELECT * FROM t1 ORDER BY a ASC, b DESC; +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+----------------------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+----------------------------------+ | 1 | SIMPLE | t1 | NULL | index | NULL | a_desc_b_asc | 10 | NULL | 10 | 100.00 | Backward index scan; Using index | +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+----------------------------------+ 1 row in set, 1 warning (0.00 sec) |
Query 5: SELECT * FROM t1 ORDER BY a DESC, b DESC;
|
1
2
3
4
5
6
7
|
mysql 8.0> EXPLAIN SELECT * FROM t1 ORDER BY a DESC, b DESC; +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------------+ | 1 | SIMPLE | t1 | NULL | index | NULL | a_desc_b_asc | 10 | NULL | 10 | 100.00 | Using index; Using filesort | +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------------+ 1 row in set, 1 warning (0.01 sec) |
Query 5: SELECT * FROM t1 ORDER BY a ASC, b ASC;
|
1
2
3
4
5
6
7
|
mysql 8.0> EXPLAIN SELECT * FROM t1 ORDER BY a ASC, b ASC; +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------------+ | 1 | SIMPLE | t1 | NULL | index | NULL | a_desc_b_asc | 10 | NULL | 10 | 100.00 | Using index; Using filesort | +----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------------+ 1 row in set, 1 warning (0.00 sec) |
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.
Understanding the Performance Numbers:
- We see improvement in Query 1 as the order requested is DESC for column “a”.
- 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).
- 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.
- 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.
- 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:
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!