Descending index in MySQL 8.0

MySQL 8.0 has come with a list of new features for DBA’s ,we will discuss the new feature in MySQL 8.0 which supports Descending index.Prior to MySQL 8.0 (i.e MySQL 5.6 and 5.7) creating desc index syntax was supported but desc keyword was ignored, Now in MySQL 8.0 release descending index is extended are supported.

What is index?

  • Indexes play an important role in performance optimization  and they are used frequently to speed up access to particular data and reduce disk I/O operations .
  • To understand index easily you can imagine a book,every book has an index with content referring to a page number.If you want to search something in a book you first refer to the index and get the page number and then get the information in the page,like this the indexes in MySQL will tell you the row with matching data.

InnoDB uses a B+Tree structure internally for  indexes. A B+Tree is particularly efficient when data doesn’t fit in memory and must be read from the disk, as it ensures that a fixed maximum number of reads would be required to access any data requested, based only on the depth of the tree, So before working with indexes, it is important to understand how indexes work behind the scene and what is the data structure that is used to store these indexes.

B+tree Index:

Indexes are stored on disk in the form of a data structure known as B+tree. B+tree is in many ways similar to a binary search tree. B+tree follows on the same structure as of a binary search tree, in that each key in a node has all key values less than the key as its left children, and all key values more than the key as its right children.

But there are some very important differences,

  • B+tree can have more than 1 keys in a node, in fact thousands of keys is seen typically stored in a node and hence, the branching factor of a B+tree is very large and that allows the B+trees to be a lot shallower as compared to their binary search tree counterparts.
  • B+trees have all the key values in their leaf nodes. All the leaf nodes of a B+tree are at the same height, which implies that every index lookup will take same number of B+tree lookups to find a value (equisearch)
  • Within a B+tree all leaf nodes are linked together in a linked-listed, left to right, and since the values at the leaf nodes are sorted, so range lookups are very efficient.

 

B+ tree example

Image courtesy :wikipedia

What is Descending indexes?

  • A descending index is an index in which the InnoDB stores the entries in descending order and and the optimizer will choose this index  when descending order is requested in the query ,which is more efficient for queries with ORDER BY clauses and it need not use a filesort operation.
  • Descending indexes are supported only for the InnoDB storage engine.
  • By default the indexes are stored in the Ascending order in a B+Tree.

How to add a descending index on a table ?

The keyword DESC is used along with the common index creation syntax ( Alter/Create )

Alter table table_name add desc_idx(col1_name desc,col2_name asc);
Create index desc_idx on table_name(col1_name desc,col2_name asc);

The index (col1_name desc,col2_name asc) satisfies two conditions:

  • Order by col1_name desc,col2_name asc : Forward Scan
  • Order by col1_name asc,col2_name desc : Backward Scan

Now let us see the query performance based on handlers count for the query with and without indexes

  • Here i am using employees table for testing purpose
mysql> select @@version;
+-----------+
| @@version |
+-----------+
| 8.0.11    |
+-----------+

mysql> show create table employees\G
*************************** 1. row ***************************
       Table: employees
Create Table: CREATE TABLE `employees` (
  `emp_no` int(11) NOT NULL,
  `birth_date` date NOT NULL,
  `first_name` varchar(14) NOT NULL,
  `last_name` varchar(16) NOT NULL,
  `gender` enum('M','F') NOT NULL,
  `hire_date` date NOT NULL,
  PRIMARY KEY (`emp_no`),
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
1 row in set (0.00 sec)

mysql> select count(*) from employees; 
+----------+ 
| count(*) | 
+----------+ 
|   300025 | 
+----------+
  • Now let us consider an example of the below query with ordering on descending and ascending conditions.

No index were created initially.

mysql> explain select * from employees order by hire_date desc,first_name asc limit 10\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: employees
   partitions: NULL
         type: ALL
possible_keys: NULL
         key: NULL
      key_len: NULL
          ref: NULL
         rows: 299157
     filtered: 100.00
        Extra: Using filesort
1 row in set, 1 warning (0.01 sec)

 

mysql> select * from employees order by hire_date desc,first_name asc limit 10;
+--------+------------+------------+------------+--------+------------+
| emp_no | birth_date | first_name | last_name  | gender | hire_date |
+--------+------------+------------+------------+--------+------------+
| 463807 | 1964-06-12 | Bikash     | Covnot     | M | 2000-01-28 |
| 428377 | 1957-05-09 | Yucai      | Gerlach    | M | 2000-01-23 |
| 499553 | 1954-05-06 | Hideyuki   | Delgrande  | F | 2000-01-22 |
| 222965 | 1959-08-07 | Volkmar    | Perko      | F | 2000-01-13 |
|  47291 | 1960-09-09 | Ulf        | Flexer     | M | 2000-01-12 |
| 422990 | 1953-04-09 | Jaana      | Verspoor   | F | 2000-01-11 |
| 227544 | 1954-11-17 | Shahab     | Demeyer    | M | 2000-01-08 |
| 205048 | 1960-09-12 | Ennio      | Alblas     | F | 2000-01-06 |
| 226633 | 1958-06-10 | Xuejun     | Benzmuller | F | 2000-01-04 |
| 424445 | 1953-04-27 | Jeong      | Boreale    | M | 2000-01-03 |
+--------+------------+------------+------------+--------+------------+
10 rows in set (1.30 sec)

The query took 1.30 secs for limit of 10 records,so from above handler Handler_read_rnd_next count we can see ,the query is doing full table scan which is equal to total number of records in table.

mysql> show status like 'hand_%';
+----------------------------+--------+
| Variable_name              | Value  |
+----------------------------+--------+
| Handler_commit             |1       |
| Handler_read_first         |1       |
| Handler_read_key           |1       |
| Handler_read_rnd_next      |300025 |
  • Let us create index according to the order in the query for the columns hire_date and first_name.
mysql> create index desc_idx on employees(hire_date desc,first_name);
Query OK, 0 rows affected (2.15 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> explain select * from employees order by hire_date desc,first_name asc limit 10\G *************************** 1. row *************************** 
           id: 1
   select_type: SIMPLE
         table: employees
    partitions: NULL
          type: index possible_keys: NULL
           key: desc_idx
       key_len: 61
           ref: NULL
          rows: 10
      filtered: 100.00
         Extra: Using index
 1 row in set, 1 warning (0.00 sec)
  • Now the query executes much faster.
mysql> select * from employees order by hire_date desc,first_name asc limit 10;
+--------+------------+------------+------------+--------+------------+
| emp_no | birth_date | first_name | last_name  | gender | hire_date |
+--------+------------+------------+------------+--------+------------+
| 463807 | 1964-06-12 | Bikash     | Covnot     | M | 2000-01-28 |
| 428377 | 1957-05-09 | Yucai      | Gerlach    | M | 2000-01-23 |
| 499553 | 1954-05-06 | Hideyuki   | Delgrande  | F | 2000-01-22 |
| 222965 | 1959-08-07 | Volkmar    | Perko      | F | 2000-01-13 |
|  47291 | 1960-09-09 | Ulf        | Flexer     | M | 2000-01-12 |
| 422990 | 1953-04-09 | Jaana      | Verspoor   | F | 2000-01-11 |
| 227544 | 1954-11-17 | Shahab     | Demeyer    | M | 2000-01-08 |
| 205048 | 1960-09-12 | Ennio      | Alblas     | F | 2000-01-06 |
| 226633 | 1958-06-10 | Xuejun     | Benzmuller | F | 2000-01-04 |
| 424445 | 1953-04-27 | Jeong      | Boreale    | M | 2000-01-03 |
+--------+------------+------------+------------+--------+------------+

10 rows in set (0.00 sec)

We can see from Handler_read_next count,the query is using the index to read the next row in key order and here Handler_read_first suggests that the number of times the first entry in an index was read.

mysql> show status like 'hand_%';
+----------------------------+-------+
| Variable_name              | Value  |
+----------------------------+-------+
| Handler_commit             |1       |
| Handler_read_first      |1      |
| Handler_read_next       |9      |
  • Lets the run the query by changing order to hire_date asc and first_name desc.
mysql> explain select * from employees order by hire_date asc,first_name desc limit 10\G 
*************************** 1. row ***************************
            id: 1   select_type: SIMPLE
         table: employees
    partitions: NULL
          type: index possible_keys: NULL
           key: desc_idx
       key_len: 61
           ref: NULL
          rows: 10
      filtered: 100.00
         Extra: Backward index scan
 1 row in set, 1 warning (0.00 sec)

mysql>  select * from employees order by hire_date asc,first_name desc limit 10;
+--------+------------+-------------+--------------+--------+------------+
| emp_no | birth_date | first_name  | last_name | gender | hire_date |
+--------+------------+-------------+--------------+--------+------------+
| 111692 | 1954-10-05 | Tonny       | Butterworth  | F | 1985-01-01 |
| 110183 | 1953-06-24 | Shirish     | Ossenbruggen | F | 1985-01-01 |
| 111035 | 1962-02-24 | Przemyslawa | Kaelbling    | M | 1985-01-01 |
| 110725 | 1961-03-14 | Peternela   | Onuegbe      | F | 1985-01-01 |
| 110022 | 1956-09-12 | Margareta   | Markovitch   | M | 1985-01-01 |
| 110303 | 1956-06-08 | Krassimir   | Wegerle      | F | 1985-01-01 |
| 110085 | 1959-10-28 | Ebru        | Alpin        | M | 1985-01-01 |
| 110511 | 1957-07-08 | DeForest    | Hagimont     | M | 1985-01-01 |
| 111400 | 1959-11-09 | Arie        | Staelin      | M | 1985-01-01 |
| 110114 | 1957-03-28 | Isamu       | Legleitner   | F | 1985-01-14 |
+--------+------------+-------------+--------------+--------+------------+

10 rows in set (0.00 sec)
mysql> show status like 'hand_%';
+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| Handler_commit             | 1     |
| Handler_read_last       | 1    |
| Handler_read_prev       | 9    |

As we can see from handler Handler_read_last and Handler_read_prev the index scan is backward way.

Conclusion:

In MySQL 8.0 it is a great new feature to avoid filesorting for the queries with Order by desc and asc clause.

More can be read on this official work log WL#1074

Image Courtesy : Photo by Verne Ho on Unsplash

Advertisements

One thought on “Descending index in MySQL 8.0

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s