❝
作者：宫水三叶。现微软工程师（Java 后端方向），退役 OIer。
更多和 MySQL 面试 & 算法相关内容可点击「这里」关注 ~
更好的阅读体验，请 点击 查看原文
转载需关注公众号联系开白名单 ~
❞
前言
业务中的各种查询通常对应了用户所看到的各项列表，列表一般是根据某个维度进行排序。
换句话说，业务中使用 SELECT 语句的时候除了不可避免的搭配 WHERE 以外，还会配合 ORDER BY 进行使用。
今天来好好聊聊 MySQL 的 ORDER BY 排序。
排序算法
说到排序算法，有插入排序、选择排序、归并排序、堆排序、快速排序、计数排序、桶排序、基数排序、冒泡排序、希尔排序、梳排序 ...
关于各种排序算法的排序流程和具体实现，不是本篇博客的重点，不作详细说明。
这里直接贴各类排序算法的时空复杂度：
通常我们实现的这些排序算法，都是在”纯内存“环境中进行。
MySQL 作为数据库难道是在先将所有要排序的数据加载到内存，再应用排序算法吗？
MySQL 的排序方案
在分析 MySQL 的不同的排序方案之前，先来了解 sort buffer 概念。
MySQL 会为每个线程分配固定大小的 sort buffer 用作排序。
sort buffer 是具有逻辑概念的内存区域，大小由 sort_buffer_size 参数控制，默认为 256 kb。
由于 sort buffer 大小固定，而 data（待排序的数据量）并不固定，所以根据 sort buffer 与 data（待排序数据量）的大小差值，可分为内部排序和外部排序：
如何验证当前执行的排序语句使用的是内部排序还是外部排序？
可以通过 EXPLAIN 命令来查看，如果在分析结果中的 Extra 字段里包含 Using filesort 字眼，说明执行了外部排序操作。
全字段排序
「全字段排序是指，只要与最终结果集有关的字段都会被放进 sort buffer，而不管该字段本身是否参与排序。」
以下面的 SQL 为例子：
SELECT nick_name, age, phone
FROM t_user
WHERE city = "深圳"
ORDER BY nick_name;
假设 city 字段上有索引，全字段排序的过程：
-
从 city 索引树上找到第一条值为深圳的数据，取得 id 之后回表（回到主键索引）取得 nick_name、age、phone 三个字段放入 sort buffer
-
从 city 索引树取下一条值为深圳的数据，重复 1 过程，直到下一条数据不满足值为深圳条件
-
到这一步，所有 city = 深圳 的数据都在 sort buffer 了。对 nick_name 执行快速排序
-
将排序结果返回
可以看到当查询条件本身有索引可用的话，全字段排序的排序过程都在 sort buffer（内存）进行，回表次数为符合条件的数据个数。
当然，如果我们建立的是 city、nick_name、age、phone 的联合索引，还可以实现“索引覆盖”，即在一棵索引树上取得全部所需数据，减少回表（随机读）次数。
不过针对每个查询或排序语句建立联合索引，会导致索引过多，大大降低写入更新数据的速度，以及大大提升数据所需要的存储空间。
生产上对索引的建立修改需要格外谨慎。
rowId 排序
rowId 就是 MySQL 对每行数据的唯一标识符。
当数据表有主键时，rowId 就是表主键；当数据表没有主键或者主键被删除时，MySQL 会自动生成一个长度为 6 字节的 rowId 为作为 rowId。
「rowId 排序是指只将与排序相关的字段和 rowId 放入 sort buffer，其余结果集需要用到的数据在排序完成后，通过 rowId 回表取得。」
全字段排序的流程看着已经十分合理，为什么还需要有个 rowId 排序？
这是我们只需要输出三个字段的情况，假如我们有上百个字段需要返回呢？sort buffer 默认只有 256 kb。能够装下多少行的原始数据行？
所以当待排序的数据行很大的时候，使用全字段排序必然会导致“外部排序”。而且是使用很多临时文件的“外部排序”，效率很低下。
相比全字段排序，rowId 排序的好处是在 sort buffer 大小固定的情况下，sort buffer 能够容纳更多的数据行，能够避免使用或者少使用“外部排序文件”。
缺点是最终返回结果集的时候，需要再次进行回表。
还是之前那个例子：
SELECT nick_name, age, phone
FROM t_user
WHERE city = "深圳"
ORDER BY nick_name;
rowId 排序全过程：
-
从 city 索引树上找到第一条值为深圳的数据，取得 id 之后回表（回到主键索引）取得 nick_name 这个与排序相关的字段和主键 id 一起放入 sort buffer
-
从 city 索引树取下一条值为深圳的数据，重复 1 过程，直到下一条数据不满足值为深圳条件
-
这时候，所有 city = 深圳 的数据都在 sort buffer 了（sort buffer 里面的数据包含两个字段： id 和 nick_name）。对 nick_name 执行快速排序
-
利用排序好的数据，使用主键 id 再次回表取其他字段，将结果返回
注意：在步骤 4 中不会等所有排序好的 id 回表完再返回，而是每个 id 回表一次，取得该行数据之后立即返回，所以不会消耗额外的内存。
优先队列排序
无论是使用全字段排序还是 rowId 排序，都不可避免了对所有符合 WHRER 条件的数据进行了排序。
有读者可能会认为，那不是应该的吗？
设想一下，如果我们还搭配着 LIMIT 使用呢？
例如我们在排序语句后添加 LIMIT 3 ，哪怕查出来的数据有 10W 行，我们也只需要前 3 行有序。
为了得到前 3 行数据，而不得不将 10W 行数据载入内存，大大降低了 sort buffer 的利用率。
这时候你可能想到利用“最小堆”、“最大堆”来进行排序。
没错，这正是 MySQL 针对带有 LIMIT 的 ORDER BY 语句的优化：使用优先队列进行排序。
以下面的 SQL 为例子：
SELECT nick_name, age, phone
FROM t_user
WHERE city = "深圳"
ORDER BY nick_name LIMIT 3;
优先队列进行排序的流程：
-
在所有待排序的数据，取数量为 LIMIT （本例中为 3）的数据，构建一个堆
-
不断的取下一行数据，更新堆节点
-
当所有行的扫描完，得到最终的排序结果
如何选择?
现在我们知道有全字段排序和 rowId 排序，那么 MySQL 是如何在这两种排序方案中做选择呢？
由于 rowId 排序相对于全字段排序，不可避免的多了一次回表操作，回表操作意味着随机读，而随机 IO 是数据库中最昂贵的操作。
所以 MySQL 会在尽可能的情况下选择全字段排序。
那么什么情况下 MySQL 会选择 rowId 排序呢，是否有具体的值可以量度？
答案是有的，通过参数 max_length_for_sort_data 可以控制用于排序的行数据最大长度，默认值为 1024 字节。
当单行数据长度超过该值，MySQL 就会觉得如果还用全字段排序，会导致 sort buffer 容纳下的行数太少，从而转为使用 rowId 排序。
临时表排序
通常对于一个执行较慢的排序语句，在使用 EXPLAIN 进行执行过程分析的时候除了能看到 Using filesort 以外，还能看到 Using temporary，代表在排序过程中使用到了临时表。
内存临时表排序
MySQL 优先使用内存临时表。当 MySQL 使用内存临时表时，临时表存储引擎为 memory 。
如果当前 MySQL 使用的是内存临时表的话，将会直接使用 rowId 排序，因为这时候所谓的“回表”只是在内存表中读数据，操作不涉及硬盘的随机 IO 读。
使用 rowId 可以在 sort buffer 容纳给多的行，避免或减少外部排序文件的使用。
磁盘临时表排序
如果系统中很多需要使用临时表的排序语句执行，而又不加以限制，全都使用临时表的话，内存很快就会被打满。
所以 MySQL 提供了 tmp_table_size 参数限制了内存临时表的大小，默认值是 16M。
如果临时表大小超过了tmp_table_size，那么内存临时表就会转成磁盘临时表。
当使用磁盘临时表的时候，表储存引擎将不再是 memory，而是由 internal_tmp_disk_storage_engine 参数控制，默认为 InnoDB 。
这时候 MySQL 会根据单行大小是否超过 max_length_for_sort_data 决定采用全字段排序还是 rowId 排序。
总结
总结一下，MySQL 总是使用 「“最快”」 的排序方案：
-
当排序数据量不超过 sort buffer 容量时，MySQL 将会在内存使用快速排序算法进行排序（内部排序）；当排序数据量超过 sort buffer 容量时，MySQL 将会借助临时磁盘文件使用归并排序算法进行排序（外部排序）
-
在进行真正排序时，MySQL 又会根据数据单行长度是否超过 max_length_for_sort_data而决定使用 rowId 排序还是全字段排序，优先选择全字段排序，以减少回表次数
-
当需要借助临时表的时候，MySQL 会优先使用内存临时表（此时表引擎为 memory 引擎），回内存临时表取数据并不涉及随机读，也不涉及扫描行，效率较高。所以在配合内存临时表的时候，会使用 rowId 排序方式；当内存临时表大小超过 tmp_table_size 限制时，则需要将内存临时表转换为磁盘临时表，这时候由于回表意味着随机读，所以会搭配全字段排序方式
