前言

在MySQL8.0之前的版本中，innodb btree索引中的记录都是严格按照的key的顺序来存储的，但有些时候当我们需要倒序扫描时，效率就会很低。为了解决这个问题，从MySQL8.0版本开始支持在索引Key中倒序存储。你可以按照实际的sql负载来决定如何创建索引，例如你的查询中有Order by a desc, b asc，就可以创建索引key(a desc, b asc)，而在8.0之前的版本中则可能需要代价比较大的filesort来进行, 此外逆序扫描Btree也有额外的开销，例如扫描时的page切换，page内扫描，都比正序扫描的开销要大。

本文简单介绍下用法，并分析下对应的代码实现

以下基于当前最新MySQL8.0.13版本

使用

其实对应的语法一直是存在的，只是没有做具体的实现，直到8.0版本才真正实现，使用也很简单，在创建索引时，对索引列加asc/desc关键字，举个简单的例子：

  1. mysql> CREATE TABLE t1 (a INT PRIMARY KEY, b INT, KEY a_idx(a DESC, b ASC));
  2. Query OK, 0 rows affected (0.05 sec)
  4.   mysql> INSERT INTO t1 VALUES(1,1),(2,2),(3,3);
  5.   Query OK, 3 rows affected (0.02 sec)
  6.   Records: 3  Duplicates: 0  Warnings: 0
  8.   mysql> SELECT b FROM t1 FORCE INDEX(a_idx);
  9.   +------+
  10.   | b    |
  11.   +------+
  12.   |    3 |
  13.   |    2 |
  14.   |    1 |
  15.   +------+
  16.   3 rows in set (0.00 sec)
  18.   mysql> SELECT b FROM t1 FORCE INDEX(PRIMARY);
  19.   +------+
  20.   | b    |
  21.   +------+
  22.   |    1 |
  23.   |    2 |
  24.   |    3 |
  25.   +------+
  26.   3 rows in set (0.00 sec)

如上例，可以看到指定不同的索引给出的结果顺序也是不一样的。

  1. mysql> EXPLAIN SELECT * FROM t1 ORDER BY a DESC, b;
  2. +----+-------------+-------+------------+-------+---------------+-------+---------+------+------+----------+-------------+
  3. | id | select_type | table | partitions | type  | possible_keys | key   | key_len | ref  | rows | filtered | Extra       |
  4. +----+-------------+-------+------------+-------+---------------+-------+---------+------+------+----------+-------------+
  5. |  1 | SIMPLE      | t1    | NULL       | index | NULL          | a_idx | 9       | NULL |    3 |   100.00 | Using index |
  6. +----+-------------+-------+------------+-------+---------------+-------+---------+------+------+----------+-------------+
  7. 1 row in set, 1 warning (0.00 sec)

上例中可以看到explain的结果中没有filesort, 而在之前的版本中对于这样的sql是需要进行排序的。

优化器在选择索引时也会考虑到索引列的顺序，目前还有些条件限制：

  • 由于涉及到数据的存储，目前只支持InnoDB
  • Descending index 无法使用change buffer
  • Descneding index不支持fulltext或spatial index, 选择desc关键字会报错
  • GROUP BY不在隐式的保证顺序性，只有明确的指定asc/desc，才去确保顺序

实现

笔者主要工作是在innodb引擎，对server层不甚了解，本文也主要关注innodb的改动。实际上这个特性的改动主要在server层的优化器和执行器，对于innodb来说，尽管数据存储发生了变化，但改动反而很少。

数据词典： 索引上的列属性被持久化到数据词典表(dd::Index)

  1. dd::fill_dd_indexes_from_keyinfo
  2.     dd::fill_dd_index_elements_from_key_parts

key_rec_cmp: 比较的两个key不是大小关系，而是在索引上的前后关系，因此需要考虑键值列上是asc还是desc的 对于range查询，在之前的版本中总是min_Key被传到innodb作为search_tuple来定位btree，但如果是descending index，则需要选择max_key来作为search tuple (ref: SEL_ARG::get_min_flag(), SEL_ARG::get_max_flag(), SEL_ROOT::store_min_key)

InnoDB record compare: 为了支持这个特性,innodb的改动实际上并不大，大部分代码都是没有变化的，这主要是因为InnoDB使用了统一的比较函数来决定key值位置，索引对象传递到底层的比较函数中，以获取是否存在descending column.

相关函数：

  1. cmp_dtuple_rec_with_match_low
  2. cmp_whole_field
  3. cmp_data

判断是否是descending index: dict_index_has_desc(): 这个函数会扫描索引上所有的列，确保没有desc column, 这个函数看起来有点效率问题，我们可以给dict_index_t加个flag来判断，无需每次遍历

参考文档

1.官方文档

2.wl#1074: Add Descending indexes support

3.MySQL 8.0 Labs – Descending Indexes in MySQL

4.MySQL 8.0: Descending Indexes Can Speed Up Your Queries

5.相关代码