order by是怎么排序的，该如何优化？_联合索引 order by排序问题

在我们的业务系统中难免用到排序，那order by这个语法你肯定用过，今天我们就来聊聊order by是怎么工作的，遇到排序慢了又该怎么优化。

order by相关的官方文档：https://dev.mysql.com/doc/refman/5.7/en/order-by-optimization.html

sort buffer

MySQL会为每个线程分配一块内存用于排序，这块内存就被称为“sort buffer”，这块内存的大小通过参数sort_buffer_size来控制，超过这个值就需要使用磁盘临时文件辅助排序。
​

使用如下语句可以看到排序是否使用了临时文件：

/* 打开optimizer_trace，只对本线程有效 */
SET optimizer_trace='enabled=on'; 

/* 执行语句 */
select city, name,age from t where city='北京' order by name limit 1000; 

/* 查看 OPTIMIZER_TRACE 输出 */
SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G
1
2
3
4
5
6
7
8

通过查看OPTIMIZER_TRACE的number_of_tmp_files中看到是否使用了临时文件，外部排序一般使用归并排序算法，假设number_of_tmp_files=12，就是MySQL将需要排序的数据分成12份，每一份单独排序后存在这些临时文件中，然后把这个12个有序文件再合并成一个有序的大文件。
sort_buffer_size越小，需要分成的份数越多。
通过Explain命令可以看到是否进行了排序，如下图中的Extra字段的“Using filesort”就表示进行了排序。

排序方式

由于我们要查询的字段可能不只有排序的字段，因此根据表中这一行记录的大小，排序类型又分为“全字段排序”和“rowid排序”，这个阈值通过max_length_for_sort_data参数来控制，默认为1024字节。
​

假设现在有张表t，主键id，字段分别为name varchar(16)、city varchar(16) index、age int(11)，我们需要执行以下查询：

select name,city,age from t where city='北京' order by name desc limit 1000;
1

全字段排序

当**max_length_for_sort_data**大于需要使用到的长度时，就使用全字段排序
由于name、city、age的三个字段定义的大小为16 + 16 + 4=36，小于max_length_for_sort_data，因此会使用全字段排序，排序过程如下：

1. 初始化sort buffer，确定放入name、city、age三个字段
2. 从索引city中找到第一个满足city='杭州’的主键ID
3. 找到主键ID索引取出整行数据，取name、city、age三个字段的值，存入sort buffer中
4. 从索引city中取下一条记录
5. 重复3、4直到city的值不满足查询条件为止
6. 对sort buffer中的数据按照字段name做快速排序
7. 按照排序结果取前1000行返回给客户端
   

优点

只需要扫描一次原表数据

缺点

当查询要返回的字段很多的话，性能会很差

rowid排序

“全字段排序”只对原表的数据读了一遍，剩下的操作都在sort buffer和临时文件中执行的，但这个算法的不足就是，如果查询要返回的字段很多的话，sort buffer里面要存放的字段太多，这样内存里能够同时放下的行数就相对变少了，可能要分成很多个磁盘临时文件，排序的性能会很差。
​

当**max_length_for_sort_data**小于需要使用到的长度时，MySQL就认为单行太大，就使用rowid排序算法，这种排序算法放入sort buffer的字段只要排序的字段和主键。具体流程如下：

1. 初始化sort buffer，确定放入两个字段，name和id
2. 从索引city找到第一个满足条件的主键id
3. 到主键id索引取出整行，取name、id这 两个字段，存入sort buffer中
4. 从索引city取出下一个记录的主键id
5. 重复步骤3、4直到不满足条件为止
6. 对sort buffer中的数据按照字段name进行排序
7. 遍历排序结果，取前1000行，并按照id的值回到原表中取出city、name和age三个字段返回给客户端
   

优点

解决了查询字段过多sort buffer内存不够的情况

缺点

多了排序后回表查询剩余字段的操作
​

总结

如果MySQL认为内存足够大， 就优先选择全字段排序，把需要的字段全都放到sort buffer中，这样排序后就可以直接从内存里返回查询结果了，不用再回到原表去取数据，多利用内存，尽量减少磁盘访问。

优化分析

并不是所有的order by 都会进行排序

MySQL之所以需要生成临时表，并且在sort buffer和临时文件中做排序操作，主要原因是原来的数据都是无序的，也就是说如果我们需要排序的字段就是已经排好序的，就不用再排序了！

让需要排序的字段提前排好序

我们都知道联合索引的排序规则，首先按照第一列进行排序，再按照第二列进行排序，依次类推，在上边的场景中我们就可以创建(city,name)的联合索引，这样我们进行city的等值查询时，就能保证同一个city的name是有序的，比如查询city=‘北京’，那city='北京’的索引树上，直到不满足条件为止，name字段都是有序的。
​

这样上边的查询就不会进行排序了，通过explain命令也可以看到，Extra少了“Using filesort”

加上(city,name)的联合索引后查询过程变成了：

1. 从索引(city,name)找到第一个满足city='北京’条件的主键id,
2. 到主键索引树上取出整行，取出name、city、age三个字段的值，作为结果集的一部分直接返回
3. 从索引(city,name)取下一个记录主键id
4. 重复步骤2、3直到city不满足条件，或者查到第10000条记录为止

那还有没有优化空间，上边的第二步其实是为了取出age字段，那么我们是不是可以把age字段也放到联合索引中，避免回表查询呢？答案显然是**可以，**也就是我们在InnoDB表结构及索引中讲到里的“覆盖索引”，因此创建(city,name,age)联合索引，再次查看Explain命令，


可以看到Extra字段里多了"Using index"，表示的就是覆盖索引，性能上会提高很多

tip：using where: 服务器Server层收到存储引擎返回的数据之后，会再根据where 条件进行过滤 using filesort: 排序用到了临时文件 using temporary: 用到了临时表

临时表

InnoDB会使用临时表的场景可查看官方文档：https://dev.mysql.com/doc/refman/8.0/en/internal-temporary-tables.html
使用Explain命令看到Extra字段显示“Using temporary”表示的就是需要临时表。

rowid

每个引擎用来唯一标识数据行的信息。

• 对于有主键的InnoDB表来说，这个rowid就是主键ID
• 对于没有主键的InnoDB表来说，这个rowid就是由系统生成的
• MEMORY引擎不是索引组织表，在这个例子里面，可以认为它就是一个数组，这个rowid其实就是数组的下标
  

内存临时表

用rowid排序，因为内存临时表使用MEMORY引擎，回表查询很快.

磁盘临时表

tmp_table_size限制了内存临时表的大小，默认值是16M，如果临时表大小超过了tmp_table_size，那么内存临时表就会转成磁盘临时表。
磁盘临时表默认使用的是InnoDB引擎，由参数internal_tmp_disk_storage_engine控制。
​

超过了sort_buffer_size也不会使用临时文件

MySQL5.6版本引入了一个新的算法，当查询SQL有limit限制时，会使用“优先排序算法”而不会使用“归并排序”。
假设我们要从表t中取字段c最小的三行记录，如果使用归并排序，需要把所有满足条件的数据进行排序，再从其中取三条，这样就浪费了非常多的计算量。
​

优先队列算法，就可以精确的只得到三个最小值，执行流程如下：

1. 对于这10000个准备排序的记录（R,rowid），先取前三行，构造成一个堆；
2. 取下一行(R’,rowid’)，跟当前堆里最大的值比较，如果R’小于R，就把(R,rowid)从堆中去掉，换成(R’,rowid’)
3. 重复第2步，知道第10000个比较完成。