根据指定的字段排序来显示结果，是我们写应用时最常见的需求之一了，比如一个交易系统中，按照交易时间倒序显示交易记录。相信你听说过这样的建议：如果有order by的需求，给需要排序的字段加上索引，就可以避免数据库排序操作。
所谓数据库排序操作，是指数据库在执行过程中，先将满足条件的数据全部读出来，放入内存中，再执行快排，这个内存就是sort_buffer。如果临时数据量比sort_buffer大， 就要把数据放入临时文件，然后做外部排序，这个排序过程的消耗是比较大的。
所谓避免数据库排序操作，是指执行过程中不需要快排或外部排序。
为什么加上索引就可以避免排序呢？如果索引存储顺序和order by不一致，还需要排序吗? 如果是联合索引呢？
今天我们就来说一说，建了索引以后，order by是怎么执行的以及怎么优化。
为了便于说明，我创建一个简单的表，这个表里，除了主键索引id外，还有一个联合索引ab。你可以在文稿中看到这个表的定义。
create table `t` (
`id` int(11) NOT NULL,
`a` int(11) NOT NULL,
`b` int(11) NOT NULL,
`c` int(11) NOT NULL,
primary key (`id`),
key `ab` (`a`, `b`)
) engine = InnoDB;
我们来看看不同的业务需求下，SQL语句怎么写，以及在MySQL里是怎么执行的。
单字段排序
一个简单的需求是将这个表的数据，按照a的大小倒序返回。你的SQL语句可以这么写：
select * from t order by a desc;
我们来看看这个联合索引ab的结构。
可以看出，在这个索引上，数据存储顺序是：按照a值递增，对于a值相同的情况，按照b值递增。
因此上面这个语句的执行流程就是：
- 从索引ab上，取最右的一个记录，取出主键值ID_Z；
- 根据ID_Z到主键索引上取整行记录，作为结果集的第一行；
- 在索引ab上取上一个记录的左边相邻的记录；
- 每次取到主键id值，再到主键索引上取到整行记录，添加到结果集的下一行；
- 重复步骤3、4，直到遍历完整个索引。
可以看出，这个流程中并不涉及到排序操作。我们也可以用explain语句来验证这个结论。下图是这个语句的explain的结果，可以看到，Extra字段中没有Using filesort字样，说明这个语句执行过程中，不需要用到排序。
组合字段排序
根据上面的分析，我们再来看看下面这个语句：
select * from t order by a desc, b desc;
这个语句的意思是，按照a值倒序，当a的值相同时按照b值倒序。
你一定发现了，这个语句的执行逻辑和执行结果，跟前面的语句是一模一样的，因此也不需要排序。
倒序不需要排序，正序呢？正序的语句是这么写的：
select * from t order by a, b;
显然，这个语句也是不需要排序的，执行流程上，只需要先取ab索引树最左边的节点，然后向右遍历即可。
到这里我们可以小结一下：
InnoDB索引树以任意一个叶节点为起始点，可以向左或向右遍历；
如果语句需要的order by顺序刚好可以利用索引树的单向遍历，就可以避免排序操作。
Descending Indexes
接下来我们来看一种不满足”单向遍历“的场景。
select * from t order by a, b desc;
这个语句要求查询结果中的记录排序顺序是：按照a值正序，对于相同的a值，按照b值倒序。
由于不满足单向遍历的要求，因此只能选择使用排序操作。
下图是这个语句explain的结果。
extra字段中Using filesort表示使用了排序。
你一定想到了，如果可以让InnoDB在构建索引ab的时候，相同的a里面，b能够从大到小排序，就又可以满足单向遍历的要求了。在MySQL5.7及之前的版本是不支持这么创建索引的，在8.0版本中支持了这个功能，官方名称是Descending Indexes。在8.0版本中，我们可以把索引ab的定义做个修改。
create table `t` (
`id` int(11) NOT NULL,
`a` int(11) NOT NULL,
`b` int(11) NOT NULL,
`c` int(11) NOT NULL,
primary key (`id`),
key `ab` (`a`, `b` desc)
) engine = InnoDB;
我们将索引ab的定义做了修改，在字段b后面加上desc，表示对于相同的a值，字段b按照倒序存储。这个表对应的索引ab的结构图如下。
这样从左到右遍历这个索引的时候，就刚好满足a正序，然后b逆序的要求。
Descending Indexes可以避免这种情况下的排序操作，语句的执行性能自然就提升了。
应用优化
前面说过，Descending Indexes这个功能是在MySQL 8.0才支持的。那如果你的生产环境上使用的还是低于8.0的版本，有没有不需要排序的方法呢？
Of cause.
假设我们现在的需求就是在MySQL 5.7版本下，要求按照”a值正序，然后b值逆序”的顺序，返回所有行a和b的值。
首先，为了避免数据库排序，我们直接执行下面这个语句：
select a,b from t order by a, b;
当然，这个语句返回的结果集是不满足业务要求的，但是我们知道，对于相同的a值，b值是有序递增的，我们要把这个数据特点利用起来。
执行这个语句后，应用端的逻辑改造如下：
构造一个空栈(stack)，栈中的节点可以保存数据行；
读入第一行，入栈；
读入下一行，
a.如果新一行中a值与上一行相同，将新一行入栈；
b.如果新一行中a值与上一行不同，则将栈中的所有数据行依次出栈并输出，直到栈清空；然后新一行入栈。
重复步骤3直到遍历完整个索引，将栈中的所有数据行依次出栈并输出，直到栈清空。
下图是用第一个图中的示例数据，执行上面的流程的效果图。
可以看到，这个过程中数据库端没有使用排序，在应用端也没有使用排序。
这个过程需要在应用端构造一个栈，需要临时内存。当然这个内存并不是凭空多出来的，因为如果不使用这个方法，就只能在MySQL端排序，这个内存就会在MySQL里创建，也就是sort_buffer。
相比之下，使用应用端的内存还是比使用MySQL的内存好些，也算是这个方案的另一个优点。
总结
本文讲述了MySQL在有索引的情况下，处理order by请求的执行过程，也介绍了Descending Indexes的应用背景。
Descending Indexes是MySQL 8.0才支持的特性。在数据库不支持一些特性的时候，也可以考虑通过应用端的协作来实现业务需求。方案优化并不一定只是数据库的优化，综合考虑系统中各个模块的特性，可以增强我们解决问题的灵活性。
