MySQL 8.0: Descending Indexes Can Speed up Your Queries

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:

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:

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:

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:

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:

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

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:

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)

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:

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:

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:

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:

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.