In 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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | CREATE TABLE `events` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(100) DEFAULT NULL, `event_date` datetime DEFAULT NULL, PRIMARY KEY (`id`), KEY `date_name` (`event_date`,`name`) ) ENGINE=InnoDB AUTO_INCREMENT=2490312 DEFAULT CHARSET=latin1 mysql> explain select * from events order by event_date, name limit 10G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: events partitions: NULL type: index possible_keys: NULL key: date_name key_len: 109 ref: NULL rows: 10 filtered: 100.00 Extra: Using index mysql> explain select * from events order by event_date desc, name desc limit 10G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: events partitions: NULL type: index possible_keys: NULL key: date_name key_len: 109 ref: NULL rows: 10 filtered: 100.00 Extra: Using index 1 row in set, 1 warning (0.00 sec) |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | mysql> select * from events order by event_date desc, name desc limit 10; +--------+-------+---------------------+ | id | name | event_date | +--------+-------+---------------------+ | 8 | test1 | 2016-10-09 10:01:06 | | 7 | test1 | 2016-10-09 10:01:06 | | 262125 | new2 | 2016-10-09 10:01:06 | | 262124 | new2 | 2016-10-09 10:01:06 | | 262123 | new2 | 2016-10-09 10:01:06 | | 262122 | new2 | 2016-10-09 10:01:06 | | 131053 | new1 | 2016-10-09 10:01:06 | | 131052 | new1 | 2016-10-09 10:01:06 | | 6 | test1 | 2016-10-09 10:01:05 | | 5 | test1 | 2016-10-09 10:01:05 | +--------+-------+---------------------+ 10 rows in set (0.00 sec) |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | mysql> explain select * from events order by event_date desc, name asc limit 10G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: events partitions: NULL type: index possible_keys: NULL key: date_name key_len: 109 ref: NULL rows: 2017864 filtered: 100.00 Extra: Using index; Using filesort 1 row in set, 1 warning (0.00 sec) mysql> select * from events order by event_date desc, name asc limit 10; +--------+-------+---------------------+ | id | name | event_date | +--------+-------+---------------------+ | 131053 | new1 | 2016-10-09 10:01:06 | | 131052 | new1 | 2016-10-09 10:01:06 | | 262123 | new2 | 2016-10-09 10:01:06 | | 262122 | new2 | 2016-10-09 10:01:06 | | 262124 | new2 | 2016-10-09 10:01:06 | | 262125 | new2 | 2016-10-09 10:01:06 | | 7 | test1 | 2016-10-09 10:01:06 | | 8 | test1 | 2016-10-09 10:01:06 | | 131055 | new1 | 2016-10-09 10:01:05 | | 131054 | new1 | 2016-10-09 10:01:05 | +--------+-------+---------------------+ 10 rows in set (2.41 sec) |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | Welcome to the MySQL monitor. Commands end with ; or g. Your MySQL connection id is 5 Server version: 8.0.0-labs-opt MySQL Community Server (GPL) Copyright (c) 2000, 2016, Oracle and/or its affiliates. All rights reserved. Oracle is a registered trademark of Oracle Corporation and/or its affiliates. Other names may be trademarks of their respective owners. Type 'help;' or 'h' for help. Type 'c' to clear the current input statement. mysql> alter table events add key date_desc_name_asc(event_date desc, name asc); Query OK, 0 rows affected (8.47 sec) Records: 0 Duplicates: 0 Warnings: 0 mysql> show create table eventsG *************************** 1. row *************************** Table: events Create Table: CREATE TABLE `events` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(100) DEFAULT NULL, `event_date` datetime DEFAULT NULL, PRIMARY KEY (`id`), KEY `date_desc_name_asc` (`event_date` DESC,`name`) ) ENGINE=InnoDB AUTO_INCREMENT=2490312 DEFAULT CHARSET=latin1 1 row in set (0.00 sec) |
I’ve created an index, targeted for our specific query order: event_date descending, name ascending. Now it works much faster:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | mysql> explain select * from events order by event_date desc, name asc limit 10G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: events partitions: NULL type: index possible_keys: NULL key: date_desc_name_asc key_len: 109 ref: NULL rows: 10 filtered: 100.00 Extra: Using index 1 row in set, 1 warning (0.00 sec) mysql> select * from events order by event_date desc, name asc limit 10; +--------+-------+---------------------+ | id | name | event_date | +--------+-------+---------------------+ | 131052 | new1 | 2016-10-09 10:01:06 | | 131053 | new1 | 2016-10-09 10:01:06 | | 262122 | new2 | 2016-10-09 10:01:06 | | 262123 | new2 | 2016-10-09 10:01:06 | | 262124 | new2 | 2016-10-09 10:01:06 | | 262125 | new2 | 2016-10-09 10:01:06 | | 7 | test1 | 2016-10-09 10:01:06 | | 8 | test1 | 2016-10-09 10:01:06 | | 131054 | new1 | 2016-10-09 10:01:05 | | 131055 | new1 | 2016-10-09 10:01:05 | +--------+-------+---------------------+ 10 rows in set (0.00 sec) |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | mysql> explain select * from events order by event_date asc, name desc limit 10G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: events partitions: NULL type: index possible_keys: NULL key: date_desc_name_asc key_len: 109 ref: NULL rows: 10 filtered: 100.00 Extra: Using index; Backward index scan 1 row in set, 1 warning (0.00 sec) |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | mysql> select * from events order by event_date desc, name asc limit 10; +--------+-------+---------------------+ | id | name | event_date | +--------+-------+---------------------+ | 131052 | new1 | 2016-10-09 10:01:06 | | 131053 | new1 | 2016-10-09 10:01:06 | | 262122 | new2 | 2016-10-09 10:01:06 | | 262123 | new2 | 2016-10-09 10:01:06 | | 262124 | new2 | 2016-10-09 10:01:06 | | 262125 | new2 | 2016-10-09 10:01:06 | | 7 | test1 | 2016-10-09 10:01:06 | | 8 | test1 | 2016-10-09 10:01:06 | | 131054 | new1 | 2016-10-09 10:01:05 | | 131055 | new1 | 2016-10-09 10:01:05 | +--------+-------+---------------------+ 10 rows in set (0.00 sec) |
Please note descending indexes only work for InnoDB:
1 2 3 4 5 | mysql> create table events_myisam like events; Query OK, 0 rows affected (0.02 sec) mysql> alter table events_myisam engine=MyISAM; ERROR 1178 (42000): The storage engine for the table doesn't support descending indexes |
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:
1 2 3 | mysql> alter table events_virt add profile_id_negative int GENERATED ALWAYS AS ( -profile_id); | Query OK, 0 rows affected (0.02 sec) Records: 0 Duplicates: 0 Warnings: 0 |
Then we can index it together with the date field:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | mysql> alter table events_virt add key event_date_profile_id_negative(event_date, profile_id_negative); Query OK, 0 rows affected (7.21 sec) Records: 0 Duplicates: 0 Warnings: 0 mysql> show create table events_virtG *************************** 1. row *************************** Table: events_virt Create Table: CREATE TABLE `events_virt` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(100) DEFAULT NULL, `event_date` datetime DEFAULT NULL, `profile_id` int(11) DEFAULT NULL, `profile_id_negative` int(11) GENERATED ALWAYS AS (-(`profile_id`)) VIRTUAL, PRIMARY KEY (`id`), KEY `event_date_profile_id_negative` (`event_date`,`profile_id_negative`) ) ENGINE=InnoDB AUTO_INCREMENT=2424793 DEFAULT CHARSET=latin1 1 row in set (0.00 sec) |
Now we can use the the profile_id_negative index for “desc” sort order:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | mysql> explain select * from events_virt order by event_date desc, profile_id_negative desc limit 10G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: events_virt partitions: NULL type: index possible_keys: NULL key: event_date_profile_id_negative key_len: 11 ref: NULL rows: 10 filtered: 100.00 Extra: NULL 1 row in set, 1 warning (0.00 sec) mysql> select * from events_virt order by event_date desc, profile_id_negative desc limit 10; +--------+-------+---------------------+------------+---------------------+ | id | name | event_date | profile_id | profile_id_negative | +--------+-------+---------------------+------------+---------------------+ | 7 | test1 | 2016-10-09 10:01:06 | 24 | -24 | | 8 | test1 | 2016-10-09 10:01:06 | 80 | -80 | | 131052 | new1 | 2016-10-09 10:01:06 | 131063 | -131063 | | 131053 | new1 | 2016-10-09 10:01:06 | 131117 | -131117 | | 262125 | new2 | 2016-10-09 10:01:06 | 262130 | -262130 | | 262123 | new2 | 2016-10-09 10:01:06 | 262169 | -262169 | | 262124 | new2 | 2016-10-09 10:01:06 | 262193 | -262193 | | 262122 | new2 | 2016-10-09 10:01:06 | 262210 | -262210 | | 5 | test1 | 2016-10-09 10:01:05 | 80 | -80 | | 6 | test1 | 2016-10-09 10:01:05 | 101 | -101 | +--------+-------+---------------------+------------+---------------------+ 10 rows in set (0.00 sec) |
That is much faster, but produces the same results as the following query:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | mysql> select * from events_virt order by event_date desc, profile_id asc limit 10; +--------+-------+---------------------+------------+---------------------+ | id | name | event_date | profile_id | profile_id_negative | +--------+-------+---------------------+------------+---------------------+ | 7 | test1 | 2016-10-09 10:01:06 | 24 | -24 | | 8 | test1 | 2016-10-09 10:01:06 | 80 | -80 | | 131052 | new1 | 2016-10-09 10:01:06 | 131063 | -131063 | | 131053 | new1 | 2016-10-09 10:01:06 | 131117 | -131117 | | 262125 | new2 | 2016-10-09 10:01:06 | 262130 | -262130 | | 262123 | new2 | 2016-10-09 10:01:06 | 262169 | -262169 | | 262124 | new2 | 2016-10-09 10:01:06 | 262193 | -262193 | | 262122 | new2 | 2016-10-09 10:01:06 | 262210 | -262210 | | 5 | test1 | 2016-10-09 10:01:05 | 80 | -80 | | 6 | test1 | 2016-10-09 10:01:05 | 101 | -101 | +--------+-------+---------------------+------------+---------------------+ 10 rows in set (2.52 sec) |
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.
Missing support for descending indexes is https://bugs.mysql.com/bug.php?id=13375
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.