MySQL45讲之order工作原理 - flowers

前言

本文介绍 order 的三种排序方式，全字段排序、rowid 排序和索引树排序，以及每种排序方式具体是如何工作的。

当使用 explain 查看执行计划时，如果 extra 中有 Using filesort，表示经过了排序。

Mysql 会在内存中分配一块内存专门用来排序，可以通过 sort_buffer_size 设置大小。如果需要排序的数据量小于 sort_buffer_size，排序在内存中进行，否则，需要采用 外部排序方法，即借助磁盘排序。

可以通过 OPTIMIZER_TRACE 的结果来查看是否使用了临时文件，

SET optimizer_trace="enabled=on"; 


SELECT * FROM `infORMation_schema`.`OPTIMIZER_TRACE`;

全字段排序

在 city 列已建立普通索引情况下，对于语句 select city,name,age from t where city="杭州" order by name limit 1000; 进行全字段排序流程是：

1. 初始化 sort_buffer，确定放入 city，name，age 字段
2. 遍历 city 索引树，找到第一个 city = "杭州" 的节点，拿到 id
3. 根据 id 从主键索引树中拿到需要返回的字段值，放入 sort_buffer
4. 循环执行 2，3 往后遍历，直到 city != "杭州"，然后再执行后面流程
5. 对 sort_buffer 中的数据按 name 排序
6. 取出前 1000 行返回客户端

将要返回的字段全部放到 sort_buffer 进行排序，所以叫全字段排序。

这个算法有个缺点，如果要返回的字段很多，则一行数据的体积很大，这样很可能要用到外部排序，并且一个文件存下的行数有限，需要比较多的临时文件，临时文件一多，排序性能将十分低，所以这时 mysql 会采用 rowid 排序算法。

rowid排序

当返回的字段很多时，Mysql 将采用 rowid 排序算法。那字段很多的标准是如何界定的呢？MySQL 有一个参数 max_length_for_sort_data，当字段类型的总字节数大于 max_length_for_sort_data 时将采用 rowid 算法。比如，select city,name,age from t where city="杭州" order by name limit 1000; 中 city 和 name 字符串长度都是 16，age 占 4 字节，即总共 36 字节。

在 city 列已建立普通索引情况下，对于语句 select city,name,age from t where city="杭州" order by name limit 1000; 进行 rowid 排序流程是：

1. 初始化 sort_buffer，确定放入 name， id 字段
2. 遍历 city 索引树，找到第一个 city = "杭州" 的节点，拿到 id
3. 根据 id 从主键索引树中拿到 name，id 字段值，放入 sort_buffer
4. 循环执行 2，3 往后遍历，直到 city != "杭州"，然后再执行后面流程
5. 对 sort_buffer 中的数据按 name 排序
6. 取出前 1000 行，按照 id 回到原表中取到 city，name，age 值再返回客户端

从上面流程可见，rowid 排序算法在 sort_buffer 中只放入了排序字段和 id，尽可能避免了外部排序低效的问题，但排序之后，还需要回表重新取一遍返回值的数据。

索引树排序

你或许会问，那有没有可以不排序的算法？

有的，就是索引树排序，因为字段值在索引树上已经有序，所以可以直接遍历索引树取到 id，然后到主键索引树拿返回值返回，不需要再排序。

那能不能直接从索引树中就拿到返回的数据，不要再回表呢？

当然也是可以的，这就是索引覆盖的思想，比如 select city,name,age from t where city="杭州" order by name limit 1000; 语句，只要建立联合索引 (city, name, age)，就可以避免回表操作。

提问

假设你的表里面已经有了 city_name(city, name) 这个联合索引，然后你要查杭州和苏州两个城市中所有的市民的姓名，并且按名字排序，显示前 100 条记录。如果 SQL 查询语句是这么写的 ：

CREATE TABLE `t` (
  `id` int(11) NOT NULL,
  `city` varchar(16) NOT NULL,
  `name` varchar(16) NOT NULL,
  `age` int(11) NOT NULL,
  `addr` varchar(128) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `city` (`city`)
) ENGINE=InnoDB;

select * from t where city in ("杭州","苏州") order by name limit 100;

那么，这个语句执行的时候会有排序过程吗，为什么？

回答：会，因为 city_name 索引只能保证 city 相同的情况下，name 有序。而此时查询两个城市，那么显然不能保证按 name 有序。

如果业务端代码由你来开发，需要实现一个在数据库端不需要排序的方案，你会怎么实现呢？

回答：可以建立联合索引 (name, city) 来避免排序。

进一步地，如果有分页需求，要显示第101页，也就是说语句最后要改成 “limit 10000,100”， 你的实现方法又会是什么呢？

回答：

没有比较好的优化方法。首先看业务是否可以砍掉这个排序的需求，让用户只能一页一页翻，这样用户基本也就只会看前几页，就不需要考虑这个大分页情况了。为了意义不大的功能优化，可能会得不偿失。

如果实在需要，就可以先建立联合索引 (name, city)，再通过下面的 SQL 查询。

SELECT * FROM t WHERE id IN ( SELECT id FROM t WHERE city IN ("杭州","苏州") ORDER BY name LIMIT 10000,100 ) AS tmp;

内查询直接索引覆盖，遍历 10100 个节点，拿到末尾的 100 个 id，不需要回表。再在外查询中，根据 id 从表中拿到数据返回客户端。这样，可以避免回表取 10100 次数据，如果符合的数据够 10100 条的话。

参考

• [1] “orderby”是怎么工作的