4.2 排序模式概览
我们这里主要关心MySQL到底是怎么排序的，采用了什么排序算法。
请关注这里
"sort_mode": "<sort_key, packed_additional_fields>"
MySQL的sort_mode有三种。
摘录5.7.13中sql/filesort.cc源码如下：
Opt_trace_object(trace, "filesort_summary")
.add("rows", num_rows).add("examined_rows", param.examined_rows)
.add("number_of_tmp_files", num_chunks)
.add("sort_buffer_size", table_sort.sort_buffer_size())
.add_alnum("sort_mode",
param.using_packed_addons() ?
"<sort_key, packed_additional_fields>" :
param.using_addon_fields() ?
"<sort_key, additional_fields>" : "<sort_key, rowid>");
“< sort_key, rowid >”和“< sort_key, additional_fields >” 看过其他介绍介绍MySQL排序文章的同学应该比较清楚，“< sort_key, packed_additional_fields >” 相对较新。
- < sort_key, rowid >对应的是MySQL 4.1之前的“原始排序模式”
- < sort_key, additional_fields >对应的是MySQL 4.1以后引入的“修改后排序模式”
- < sort_key, packed_additional_fields >是MySQL 5.7.3以后引入的进一步优化的"打包数据排序模式”
下面我们来一一介绍这三个模式。
4.2.1 回表排序模式
- 根据索引或者全表扫描，按照过滤条件获得需要查询的排序字段值和row ID；
- 将要排序字段值和row ID组成键值对，存入sort buffer中；
- 如果sort buffer内存大于这些键值对的内存，就不需要创建临时文件了。否则，每次sort buffer填满以后，需要直接用qsort(quickcsort,快速排序算法)在内存中排好序，并写到临时文件中；
- 重复上述步骤，直到所有的行数据都正常读取了完成；
- 用到了临时文件的，需要利用磁盘外部排序，将row id写入到结果文件中；
- 根据结果文件中的row ID按序读取用户需要返回的数据。由于row ID不是顺序的，导致回表时是随机IO，为了进一步优化性能（变成顺序IO），MySQL会读一批row ID，并将读到的数据按排序字段顺序插入缓存区中(内存大小read_rnd_buffer_size)。
4.2.2 不回表排序模式
- 根据索引或者全表扫描，按照过滤条件获得需要查询的数据；
- 将要排序的列值和 用户需要返回的字段 组成键值对，存入sort buffer中；
- 如果sort buffer内存大于这些键值对的内存，就不需要创建临时文件了。否则，每次sort buffer填满以后，需要直接用qsort(快速排序算法)在内存中排好序，并写到临时文件中；
- 重复上述步骤，直到所有的行数据都正常读取了完成；
- 用到了临时文件的，需要利用磁盘外部排序，将排序后的数据写入到结果文件中；
- 直接从结果文件中返回用户需要的字段数据，而不是根据row ID再次回表查询。
4.2.3打包数据排序模式
第三种排序模式的改进仅仅在于将char和varchar字段存到sort buffer中时，更加紧缩。
在之前的两种模式中，存储了”yes”3个字符的定义为VARCHAR(255)的列会在内存中申请255个字符内存空间，但是5.7.3改进后，只需要存储2个字节的字段长度和3个字符内存空间（用于保存”yes”这三个字符）就够了，内存空间整整压缩了50多倍,可以让更多的键值对保存在sort buffer中。
4.2.4三种模式比较
第二种模式是第一种模式的改进，避免了二次回表，采用的是用空间换时间的方法。
但是由于sort buffer就那么大，如果用户要查询的数据非常大的话，很多时间浪费在多次磁盘外部排序，导致更多的IO操作，效率可能还不如第一种方式。
所以，MySQL给用户提供了一个max_length_for_sort_data的参数。当“排序的键值对大小” > max_length_for_sort_data时，MySQL认为磁盘外部排序的IO效率不如回表的效率，会选择第一种排序模式；反之，会选择第二种不回表的模式。
第三种模式主要是解决变长字符数据存储空间浪费的问题，对于实际数据不多，字段定义较长的改进效果会更加明显。
能看到这里的同学绝逼是真爱，但是还没完，后面的东西可能会更烧脑…
建议大家喝杯咖啡再继续看。
很多文章写到这里可能就差不多了，但是大家忘记关注一个问题了：如果排序的数据不能完全放在sort buffer内存里面，是怎么通过外部排序完成整个排序过程的呢？
要解决这个问题，我们首先需要简单查看一下外部排序到底是怎么做的。
五、外部排序
5.1 普通外部排序
5.1.1 两路外部排序
我们先来看一下最简单，最普遍的两路外部排序算法。
假设内存只有100M，但是排序的数据有900M，那么对应的外部排序算法如下：
- 从要排序的900M数据中读取100MB数据到内存中，并按照传统的内部排序算法（快速排序）进行排序；
- 将排序好的数据写入磁盘；
- 重复1，2两步，直到每个100MB chunk大小排序好的数据都被写入磁盘；
- 每次读取排序好的chunk中前10MB（= 100MB / (9 chunks + 1)）数据，一共9个chunk需要90MB，剩下的10MB作为输出缓存；
- 对这些数据进行一个“9路归并”，并将结果写入输出缓存。如果输出缓存满了，则直接写入最终排序结果文件并清空输出缓存；如果9个10MB的输入缓存空了，从对应的文件再读10MB的数据，直到读完整个文件。最终输出的排序结果文件就是900MB排好序的数据了。
5.1.2 多路外部排序
上述排序算法是一个两路排序算法（先排序，后归并）。但是这种算法有一个问题，假设要排序的数据是50GB而内存只有100MB，那么每次从500个排序好的分片中取200KB（100MB / 501 约等于200KB）就是很多个随机IO。效率非常慢，对应可以这样来改进：
- 从要排序的50GB数据中读取100MB数据到内存中，并按照传统的内部排序算法（快速排序）进行排序；
- 将排序好的数据写入磁盘；
- 重复1，2两步，直到每个100MB chunk大小排序好的数据都被写入磁盘；
- 每次取25个分片进行归并排序，这样就形成了20个（500/25=20）更大的2.5GB有序的文件；
- 对这20个2.5GB的有序文件进行归并排序，形成最终排序结果文件。
对应的数据量更大的情况可以进行更多次归并。
5.2 MySQL外部排序
5.2.1 MySQL外部排序算法
那MySQL使用的外部排序是怎么样的列，我们以回表排序模式为例：
- 根据索引或者全表扫描，按照过滤条件获得需要查询的数据；
- 将要排序的列值和row ID组成键值对，存入sort buffer中；
- 如果sort buffer内存大于这些键值对的内存，就不需要创建临时文件了。否则，每次sort buffer填满以后，需要直接用qsort(快速排序模式)在内存中排好序，作为一个block写到临时文件中。跟正常的外部排序写到多个文件中不一样，MySQL只会写到一个临时文件中，并通过保存文件偏移量的方式来模拟多个文件归并排序；
- 重复上述步骤，直到所有的行数据都正常读取了完成；
- 每MERGEBUFF (7) 个block抽取一批数据进行排序，归并排序到另外一个临时文件中，直到所有的数据都排序好到新的临时文件中；
- 重复以上归并排序过程，直到剩下不到MERGEBUFF2 (15)个block。
通俗一点解释：
第一次循环中，一个block对应一个sort buffer（大小为sort_buffer_size）排序好的数据；每7个做一个归并。
第二次循环中，一个block对应MERGEBUFF (7) 个sort buffer的数据，每7个做一个归并。
…
直到所有的block数量小于MERGEBUFF2 (15)。 - 最后一轮循环，仅将row ID写入到结果文件中；
- 根据结果文件中的row ID按序读取用户需要返回的数据。为了进一步优化性能，MySQL会读一批row ID，并将读到的数据按排序字段要求插入缓存区中(内存大小read_rnd_buffer_size)。
这里我们需要注意的是：
- MySQL把外部排序好的分片写入同一个文件中，通过保存文件偏移量的方式来区别各个分片位置；
- MySQL每MERGEBUFF (7)个分片做一个归并，最终分片数达到MERGEBUFF2 (15)时，做最后一次归并。这两个值都写死在代码中了…
</div>
