带你一步一步深入了解 MySQL Order By 文件排序

如果不满足上面两个条件，会使用 排序模式，后面会讲述这种模式。

max_length_for_sort_data 默认值为 1024 字节，最小可设置为 4 字节，最大可设置为 8M。

的优点是简单方便，它也有缺点，additional_fields 所有字段在排序缓冲区或磁盘文件中都是按照字段最大占用字节数来分配空间的，在以下两种场景中会存在空间浪费：

为了解决这种排序模式浪费空间的问题，引入了另一种排序模式 。

4.2

表示排序缓冲区或磁盘文件中，除了要存入排序字段（sort_key），还要存入存储引擎返回给 server 层的所有字段（packed_additional_fields），并且会尽可能使用最少的空间存放待排序记录。

字段内容为 NULL 时，除 1 bit 的 NULL 标记位之外，字段在排序缓冲区不占用额外存储空间；char、varchar 类型字段内容长度小于字段最大长度时，字段在排序缓冲区中只占用实际内容长度大小的空间，不会像 排序模式一样每个字段都占用字段最大长度大小的空间。

上图是写入到排序缓冲区中记录的示意图，以下对各个部分进行说明：

是以 为基础的，如果不满足使用 的条件，也不会使用 。

使用 排序模式，还需要满足以下条件：

前面我们讲述了 、 的优缺点及使用限制，如果这两种排序模式都不能使用怎么办？

别急，该轮到 排序模式出场了，MySQL 刚出道时采用的就是这种排序模式。

4.3

表示排序缓冲区或磁盘文件中，除了要存入排序字段（sort_key），还要存入记录的主键 ID（rowid）。

上图是写入到排序缓冲区中记录的示意图，相比其它两种排序模式来说，非常简单，不做过多说明了。

想必大家应该发现了 和 、 的区别了，使用 时，排序缓冲区或磁盘文件中只包含了记录的主键 ID，而客户端可能需要除主键之外的字段，怎么办？

这就要二次访问存储引擎了，第一次从存储引擎拿到符合 where 条件的所有记录的主键 ID，第二次根据主键 ID 从存储引擎一条一条读取记录，得到客户端需要的所有字段。

使用 读取数据的过程，有点类似根据 ID 批量从 redis 获取详细数据的过程，先从某个 redis key 读取多个 ID，然后根据 ID 读取缓存的详细数据。

这种排序模式的好处是记录数量不太多的情况下，使用排序缓冲区就能够存储所有待排序记录了，能够在一定程度上避免使用磁盘文件排序。

举例说明：假设排序字段为 int 类型，主键也为 int 类型，写入排序缓冲区的一条记录占用的空间为 4 + 4 = 8 字节，排序缓冲区的默认大小为 256K，能够存放 32768 条记录，对于一般业务来说，都不会一次性读取这么多记录，由此可见，一般情况下，使用 排序模式不会用到磁盘文件排序。

但是，凡事都有例外，如果一条 SQL 语句读取过多的记录，哪怕是使用 ，当排序缓冲区满时，也需要把缓冲区中的记录排好序组成一个数据块，写入磁盘文件，这样一来，即要使用磁盘文件，又要二次访问存储引擎，执行效率就有点惨不忍睹了。

细心的小伙伴可能发现了一点情况，到现在为止讲的三种排序模式，都是把符合 where 条件的所有记录写入排序缓冲区或磁盘文件，那还有优化空间吗？

MySQL 为了提升性能，想了各种办法，使用了各种技巧，对于上面提到的这种情况，自然也还可以再优化，我们一起来看看吧。

5. 提升排序效率5.1 优先队列

通过前面的讲述，我们已经知道了，MySQL 会把符合 where 条件的所有记录写入排序缓冲区，当缓冲区满时，缓冲区中的记录排好序后组成一个数据块，写入到磁盘文件（temp_file），而磁盘 IO 相比内存访问效率低下，优先队列就是为了在文件排序过程中避免使用磁盘文件的一种优化方案。也就是说，使用了优先队列就不会使用磁盘文件排序。

优先队列在内存中维护待排序记录的队列，队列中的元素不会实际存储记录内容，而是存储指向排序缓冲区中记录的地址，因为要保证不使用磁盘文件，使用优先队列提升排序效率的必要条件是：SQL 语句必须包含 limit。

在满足必要条件的基础上，会评估使用优先队列进行排序是否更快，以决定是否使用。

使用优先队列提升排序效率，借鉴的是大顶堆的思路，排序缓冲区中只需要保留待排序记录中最大或最小的 limit 条记录（取决于正序还是倒序排序），而不需要存放所有待排序记录。基于前面的描述可以知道，使用优先队列的优势有两个：

如果排序缓冲区不能存放所有待排序记录，就意味着需要借助磁盘文件排序，使用优先队列无疑是更好的选择，这种情况下，只要排序缓冲区中能够存放 limit + 1 条记录，就会使用优先队列。

limit + 1 中的 1 是优先队列需要使用的额外的一条记录的空间。

如果排序缓冲区能够存放所有待排序记录，本身就不需要使用磁盘文件进行排序，使用优先队列的优势就剩下一个了：只需要对一部分待排序记录中进行排序。官方根据单元测试发现，使用优先队列 + 排序缓冲区进行排序需要的时间是只使用排序缓冲区的 3 倍。因此，当 limit 数量小于待排序记录数量的三分之一时，使用优先队列 + 排序缓冲区比只使用排序缓冲区排序更快，才会使用优先队列来提升排序效率。

经过前面一系列的成本评估之后，如果还是不能使用优先队列，MySQL 会进行最后一次尝试，这就是最后一哆嗦了：如果使用的排序模式是 ，可能会造成需要使用磁盘文件排序，此时会判断使用 + 优先队列的成本是否比使用 + 磁盘文件排序的成本更低。。

如果使用 + 磁盘文件排序成本更低，那么还是保持原样，依然使用 排序模式。

如果使用 + 优先队列成本更低，并且排序缓冲区中能够存放 limit + 1 记录的排序字段（sort_key）和主键 ID，使用的排序模式会由 修改为 ，并且使用优先队列来减少实际参与排序的记录数量，提升排序效率。

前面提到的 limit 并不是 SQL 语句中 limit 后面的数字，而是 SQL 语句中的 offset + limit。想要了解 MySQL 中 limit 是怎么实现的，可以参考这篇文章：

看到这里，可能有的小伙伴会有疑问，排序模式 是不是和优先队列两者不能共存？

和优先队列是可以共存的，只有当使用 排序模式导致排序缓冲区不能存放所有待排序记录，要借助磁盘文件实现排序时，如果改为使用 + 优先队列实现排序成本更低，才会把 修改为 ，并且使用优先队列提升排序效率。

5.2 随机 IO 变为顺序 IO

使用 排序模式，从存储引擎读取符合 where 条件的所有记录的主键 ID，按照 sort_key 排序好序之后，需要根据主键 ID 从存储引擎读取记录中的需要返回给客户端的其它字段。按照 sort_key 排好序的记录，在主键索引中不一定是顺序存储的，可能是分散在主键索引的不同叶子节点中，这样一来，通过主键 ID 一条一条去存储引擎读取记录，会造成大量随机 IO，导致从存储引擎读取数据效率低下。

为了尽可能减少随机 IO，MySQL 通过一个专门的内存区域，尽量把随机 IO 变成顺序 IO，这个专门的内存区域为 随机读缓冲区（read_rnd_buffer）。

缓冲区大小由系统变量 read_rnd_buffer_size 控制，默认大小为 256K，最小为 1 字节，最大为 2G，如果设置为 1 字节，就相当于禁用了这个缓冲区了。

随机 IO 变为顺序 IO 的实现逻辑是这样的：

这个优化方案基于这样一个假设的前提条件：一批主键 ID，排好序之后逻辑上相邻的主键 ID，其对应的记录更有可能在主键索引的同一个叶子节点中，从存储引擎读取一个主键 ID 对应的记录之后，再读取下一个主键 ID 对应的记录，该记录所在的主键索引叶子节点有可能已经被加载到内存中了，就可以直接从内存中读取记录，从而一定程序上减少随机 IO，提升读取数据的效率。

只有当排序缓冲区存放不下所有记录的 ，需要使用磁盘文件来存储时，才有可能使用随机缓冲区来优化文件排序，然而，这还只是入门门槛，要想使用随机缓冲区，需要满足的其它条件达 9 条之多，涉及到源码细节，就不一一展开了，大家只要知道有这么一种优化方案存在就可以了。

使用 、 排序模式时，不需要使用随机缓冲区来优化文件排序，因为这两种排序模式下，需要返回给客户端的所有字段都已经在排序缓冲区或磁盘文件（out_file）中了，不需要通过主键 ID 二次访问存储引擎读取其它字段。

6. 两类排序

MySQL order by 的实现过程，可能会进行两类排序：内部排序、外部排序。

前面多次提到，当排序缓冲区满，会把缓冲区中的记录排好序，组成一个数据块，然后写入磁盘文件，这里的排序就是内部排序。

符合 where 条件的所有记录都写入到磁盘文件之后，可能会存在多个已经内部排好序的数据块，这些数据块需要通过多路归并排序，最终形成全局有序的结果，这里的排序就是外部排序。

6.1 内部排序

内部排序是对排序缓冲区中的记录进行排序，是内存排序。

为了提升性能，MySQL 做了各种各样的努力，内部排序的实现又一次体现了这种追求极致性能的努力。内部排序使用了 3 种排序算法：

为什么使用快速排序的条件是排序记录数量小于等于 100？

源码注释是这样说的，归并排序比快速排序更快，但是归并排序申请临时缓冲区需要额外的时间成本，所以在排序记录数量很少的时候，归并排序并没有多大优势，归并排序比快速排序快的临界点是排序记录数量在 10 ~ 40 条之间，保守一点，所以把这个阈值定为 100。

6.2 外部排序

外部排序是对磁盘文件中已经局部排好序的记录进行全局归并排序，是磁盘文件排序。

MySQL 从存储引擎读取符合 where 的条件记录写入排序缓冲区，缓冲区满时，会对缓冲区中的记录进行内部排序，排好序的数据组成一个数据块，数据块包含两部分：Merge_chunk 和数据记录。

Merge_chunk 写入到磁盘文件（chunk_file）中，数据记录写入到磁盘文件（temp_file）中。Merge_chunk 中保存有数据记录在 temp_file 中的起始位置、Merge_chunk 对应的数据块在 temp_file 中的记录数量等信息。

从存储引擎读取完符合 where 条件的所有记录之后，可能会生成多个数据块写入到磁盘文件（temp_file）。通过多路归并排序，把小数据块合并为更大的数据块，最终得到全局排好序的记录，把磁盘文件（temp_file）中多个数据块合并为一个数据块的过程，借助了优先队列和排序缓冲区来实现。

注意：外部排序过程中借助优先队列和排序缓冲区，和 5.1 优先队列 中的优先队列 + 排序缓冲区不是一回事，不要混淆了。外部排序过程只是使用了优先队列和排序缓冲区来加快归并排序的过程。

外部排序把小数据块合并为大数据块的过程中，会使用 7 路归并排序，把 7 个小数据块合并为 1 个大数据块，数据块数量多时，会进行多轮归并排序，直到数据块的数量小于等于 15，多轮归并排序之后得到的小于等于 15 个数据块，经过终极归并排序得到最终的排序结果。

接下来我们以磁盘文件（temp_file）中包含 160 个数据块为例来说明外部排序的过程。

第一轮归并排序示意图：：

左下角 chunk_file 中有 160 个 Merge_chunk，temp_file 有 160 个对应于 Merge_chunk 的数据记录块。归并排序过程中会借助排序缓冲区提升执行效率，因为要进行 7 路归并排序，排序缓冲区被平均分为 7 份，每份对应于 temp_file 中的一个数据块，为了描述方便，我们暂且把排序缓冲区的七分之一叫做子排序缓冲区。在归并排序过程中，会分别从 temp_file 中的 7 个数据记录块中读取一部分记录到其对应的子排序缓冲区。

读取 temp_file 中数据记录块的数据到子排序缓冲区之后，优先队列中的每个 Merge_chunk（对应于 chunk_file 中的 Merge_chunk）中有一个属性 current_key，指向子排序缓冲区中的第一条记录，图中优先队列的每个 Merge_chunk 有个红色箭头指向子排序缓冲区，就是表示 current_key 属性指向子排序缓冲区中的第一条记录。

current_key 指向的记录是子排序缓冲区对应的 temp_file 数据记录块中排序字段值（sort_key）最大的那条记录。

归并排序过程中，会循环把 7 个 Merge_chunk 的 current_key 指向的记录中排序字段值最大的记录写入到 temp_file2 的数据记录块中，直到所有数据记录块中的记录都写入到 temp_file2 文件。

每次都取 current_key 指向的记录中最大的记录，有没有发现这是大顶堆的特点？在源码实现中，找到优先队列中 Merge_chunk 的 current_key 属性指向的记录中排序字段值最大的记录，就是用大顶堆的思路实现的。

从图中右下角的 temp_file2 和 chunk_file 可以看到，经过第一轮归并排序之后，160 个小数据块合并成了 23 个更大的数据块，23 大于 15，所以还需要进行第二轮归并排序。

第二轮归并排序示意图：

第一轮归并排序，我们已经讲述了详细的合并过程，第二轮归并排序就不展开讲了，由上图右下角的 temp_file 和 chunk_file 可见，第二轮归并排序，由小数据块合并得到的 23 个更大的数据块，再次进行 7 路归并排序，最终得到 4 个数据块。4 小于 15，所以不需要进行得到中间结果的第三轮归并排序，直接进行得到最终排序结果的多路归并排序。

不知道大家有没有发现，第一轮归并排序示意图中，是从 temp_file 读取记录到子排序缓冲区，然后把归并排序结果写入到 temp_file2；第二轮归并排序示意图中，是从 temp_file2 读取记录到子排序缓冲区，然后把归并排序结果写入到 temp_file。这说明在外部归并排序过程中，会使用两个中间结果磁盘文件（temp_file、temp_file2），加上 chunk_file、out_file，一共会使用 4 个磁盘文件，大家知道一下就可以了。

终极多路归并排序：

从上图可见，经过前面两轮归并排序之后，得到 4 个数据块，排序缓冲区被分为 4 个子缓冲区，4 个子缓冲区中已局部排好序的记录，经过归并排序写入到存放最终排序结果的磁盘文件中（out_file)。

最后一轮归并排序和前面的 N 归并排序有些不同。

前面 N 轮归并排序，写入到磁盘文件的是中间结果，磁盘文件（temp_file、temp_file2）中存放的还是局部排好序的记录，并且记录中还包含排序字段（sort_key），因为后面的归并排序还需要用到排序字段（sort_keky）。

最后一轮归并排序，写入到磁盘文件的是最终结果，磁盘文件（out_file）中存放的是全局排好序的记录，此时记录中只包含存储引擎返回给 server 层的字段，已经不包含排序字段了。

7. 倒序排序

MySQL 文件排序的内部实现中，正序和倒序排序都是以正序的方式进行的，排序字段值大的在前面，排序字段值小的在后面，这样逻辑统一，实现方便。

倒序排序时，把排序字段值写入排序缓冲区之前，会对所有排序字段值进行逐字节取反操作，取反之后，原来字段值大的变成小的，字段值小的变成大的，排序字段值取反之后再进行正序排序，最终得到的记录就是倒序排序的了。

举例说明

select?num?from?t?order?by?num?desc?

以 排序模式为例，假设表中有 5 条记录，num 字段值分别为：95, 90, 49, 97, 6，num 字段值会写入到排序缓冲区两次，一次是作为 sort_key，一次是作为 additional_fields，5 条记录全部写入缓冲区之后，缓冲区的内容示意如下：

图中蓝色块表示 sort_key，绿色块表示 additional_fields，为了有个对比，1 号图示 和 2 号图示分别表示正序和倒序排序之前，排序缓冲区中的记录示意图。3 号图示表示倒序排序之后，排序缓冲区中的记录示意图。

从 3 号图示可见，倒序排序时，对排序字段值取反之后按照正序排序，最终实现了记录的倒序排序。

上面示例中，对于 num 字段会写入排序缓冲区两次，可能有的小伙伴会有疑问mysql排序，这里解释一下：实际上，排序字段作为 sort_key 写入到排序缓冲区之前，都会进行编码，编码之后的排序字段值就和原字段值不一样了，只用于排序，不作为最终结果返回给客户端，在排好序之后，sort_key 会被丢弃。

8. 窥探更多排序细节

通过 explain，我们只能看到 SQL 语句执行时，是否使用了文件排序，看不到排序过程中是只使用了排序缓冲区，还是也使用了磁盘文件，更不知道排序缓冲区被写满了多少次；也看不到是不是使用了优先队列，如果没有使用，是什么原因。

好在 MySQL 给我们提供了一个工具（optimizer trace）可以进一步了解这些细节，执行以下 SQL 可开启 optimizer trace：

--?开启?optimizer?trace
set?optimizer_trace?=?"enabled=on";

--?设置 optimizer_trace 输出结果最多可占用的内存空间，单位是：字节
--?如果发现?optimizer_trace?的?json?结果不全，可以把这个值改成更大的数字
set?optimizer_trace_max_mem_size?=?1048576;

optimizer trace 的输出结果 json 中有两个和文件排序相关的属性：filesort_summary、filesort_priority_queue_optimization，下面我把写本文过程中使用的测试 SQL 的 optimizer trace 作为例子来说明：

//?filesort_summary
{
????"rows":?10227,
????"examined_rows":?10227,
????"number_of_tmp_files":?41,
????"sort_buffer_size":?262112,
????"sort_mode":?""
}

number_of_tmp_files：

大家不要被 number_of_tmp_files 属性名误导，虽然属性名中有 tmp_files，但这并不是表示排序过程中使用了多个临时文件。实际上不管有多少个数据块，都是写入到一个磁盘文件（temp_file）中。

相信经过本文前面的讲述，大家对于 sort_mode 都已经比较熟悉了，一共有三种排序模式：、、。

//?filesort_priority_queue_optimization
{
????"usable":?false,
????"cause":?"not?applicable?(no?LIMIT)"
}

通过 usable = false 可知，我的测试 SQL 没有使用优先队列，原因是没有指定 limit。

有一点需要特别注意，获取 optimizer trace 结果的语句必须和 SQL 语句同时执行，不能分开一条一条的执行，否则查出来的 optimizer trace 结果是空白。

举例说明：

select?*?from?t2?where?i1?>=?99991840?order?by?str1;?--?SQL?1
select?*?from?information_schema.OPTIMIZER_TRACE;?--?SQL?2

对于上面例子，如果先执行 SQL 1 再执行 SQL 2，会发现 optimizer trace 结果是空的，必须同时执行 SQL 1 和 SQL 2，才能得到 SQL 1 的 optimizer trace 结果。

9. 总结

本文我们以文件排序的整体概览开始，抛开实现细节，从全局角度了解了文件排序的整体逻辑。接着介绍了系统变量 sort_buffer_size 用于控制排序缓冲区大小，max_sort_length 用于控制单个排序字段内容长度。

排序模式小节，介绍了三种排序模式：

提升排序效率小节，介绍了源码中采用的两个优化方案：

两类排序小节，介绍了三种内部排序算法，其使用优先级为：基数排序、快速排序、归并排序。

外部排序，可能会进行 0 ~ N 轮归并排序生成中间结果，最后进行一轮归并排序得到最终结果。

生成中间结果的归并排序，排序字段（sort_key）也会写入到磁盘文件，后续生成中间结果和最终结果的归并排序都会用到。生成最终结果的归并排序，磁盘文件只写入存储引擎返回给 server 层的字段，不会包含排序字段（sort_key）。

倒序排序小节，介绍了倒序排序的实现：先对排序字段（sort_key）逐字节取反，然后对排序字段进行正序排序，最终得到倒序排序的记录。

最后，介绍了如何通过 optimizer trace 窥探文件排序的更多细节。

如果本文对你有所帮助，还请帮忙点赞、在看、转发朋友圈，让更多人看到，我们一起进步，谢谢 ^_^

（编辑：财气旺网 - 财气网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!