DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
  1. DZone
  2. Data Engineering
  3. Databases
  4. MySQL 8.0: Descending Indexes Can Speed up Your Queries

MySQL 8.0: Descending Indexes Can Speed up Your Queries

MySQL 8.0 will likely be introducing support for index sort order on disk! Read on to find out what this means and how it can help speed up your queries.

Alexander Rubin user avatar by
Alexander Rubin
·
Oct. 22, 16 · Tutorial
Like (4)
Save
Tweet
Share
8.43K Views

Join the DZone community and get the full member experience.

Join For Free

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)


Please note descending indexes only work for InnoDB:
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.

Database MySQL

Published at DZone with permission of Alexander Rubin, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Using AI and Machine Learning To Create Software
  • Java Development Trends 2023
  • Core Machine Learning Metrics
  • Promises, Thenables, and Lazy-Evaluation: What, Why, How

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: