以下面这张表为例，看一下 order by 的工作流程。
city 字段建有索引。
执行：
select city,name,age
from t where city=’杭州’
order by name limit 1000 ;
查找 city 为‘杭州’的记录，根据 name 排序。
排序流程
先看下 city 索引的示意图：
上面查询语句的执行流程：
1、 初始化 sort_buffer，确定放入 name、city、age 这3个字段。
2、 从索引 city 中找到第一个满足 city=’杭州’ 的主键ID（ID_x）。
3、 到主键索引中找到 ID_x，取出整行，取 name、city、age 3个字段的值，存入 sort_buffer。
4、 从索引 city 取下一个记录的主键ID。
5、 重复3、4，直到 city 值不满足条件。
6、 对 sort_buffer 中的数据按照 name 做快速排序。
7、 把排序结果中的前1000行返回给客户端。
这个排序过程叫做全字段排序，因为需要返回的字段都放入了 sort_buffer 参与排序过程。
排序可能是在内存中完成，也可能需要外部排序，这取决于排序所需要的内存和 sort_buffer_size 参数值。
sort_buffer_size 是为排序而开辟的内存，如果排序的数据量小于其值，排序就在内存中完成，否则会利用磁盘临时文件来辅助排序。
上面的查询中只返回3个字段，不会太长，可以一起都放在 sort_buffer 中，但如果排序的单行长度太大，MySQL会怎么做？
假设 name、city、age 3个字段定义的总长度为36，而 max_length_for_sort_data = 16，就是单行的长度超了，MySQL认为单行太大，需要换一个算法。
此时，放入 sort_buffer 的字段就会只有要排序的字段 name，和主键 id，那么排序的结果中就少了 city 和 age，需要回表了。
排序流程变为：
1、 初始化 sort_buffer，确定放入2个字段，name 和 id。
2、 从索引 city 中找到第一个满足 city=’杭州’ 的主键ID（ID_x）。
3、 到主键索引中取出整行，把 name、id 这2个字段放入 sort_buffer。
4、 从索引 city 取下一个记录的主键ID。
5、 重复3、4，直到city值不满足条件。
6、 对 sort_buffer 中的数据按照 name 做快速排序。
7、 取排序结果中的前1000行，并按照 id 的值到原表中取出 name、city、age 3个字段的值返回给客户端。
这种排序成为rowid排序。
如果内存够大，优先选择全字段排序，把需要的字段都放到 sort_buffer中，这样排序后就会直接从内存里返回查询结果了，不用回到原表取数据。
排序优化
建立一个 city、name 的联合索引，使查询 city='杭州' 的结果就是 name 有序的，就不用排序了。
查询过程变为：
1、 从索引（city,name）找到第一个满足 city=’杭州’ 的主键ID。
2、 到主键索引中取出整行，取 name、city、age 3个字段的值，作为结果集的一部分直接返回。
3、 从索引（city,name）取下一个主键ID。
4、 重复2、3，直到查到1000条，或者不满足条件时结束。
其实，这个查询还可以进一步优化，就是利用覆盖索引。
使用联合索引（city,name）后已经不需要排序过程了，但因为没有 age 字段，所以还需要回表获取。
如果建立一个联合索引（city,name,age），不仅不用排序了，也不用回表取数据了，因为索引中已经包含了查询所需要的字段。
查询过程变为：
1、 从索引（city,name,age）找到第一个满足 city=’杭州’ 的记录，取出这3个字段，作为结果集的一部分直接返回。
2、 从索引取下一个记录，返回。
3、 重复2，直到查到1000条，或者条件不满足时结束。
小结
上面介绍了排序的工作流程，包括：
1、 全字段排序
2、 rowid 排序
并进一步思考如何对排序进行优化：
1、 利用索引使查询结果本身就是有序的。
2、 如果条件允许，使用覆盖索引，直接返回结果。
内容整理自丁奇的《MySQL实战45讲》