前言
本文介绍 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; 进行全字段排序流程是：
- 初始化 sort_buffer，确定放入 city，name，age 字段
- 遍历 city 索引树，找到第一个 city = "杭州" 的节点，拿到 id
- 根据 id 从主键索引树中拿到需要返回的字段值，放入 sort_buffer
- 循环执行 2，3 往后遍历，直到 city != "杭州"，然后再执行后面流程
- 对 sort_buffer 中的数据按 name 排序
- 取出前 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 排序流程是：
- 初始化 sort_buffer，确定放入 name， id 字段
- 遍历 city 索引树，找到第一个 city = "杭州" 的节点，拿到 id
- 根据 id 从主键索引树中拿到 name，id 字段值，放入 sort_buffer
- 循环执行 2，3 往后遍历，直到 city != "杭州"，然后再执行后面流程
- 对 sort_buffer 中的数据按 name 排序
- 取出前 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”是怎么工作的
