内容目录
为了更好的把握 MySQL 文件排序的全局，我们先抛开细节，来看看它的实现过程示意图：
结合上面的示意图，我们来描述一下大体的实现过程：
server 层从存储引擎读取符合 where 条件的记录，写入一个专门存放待排序记录的内存区域，这个内存区域叫做排序缓冲区（sort buffer）。
排序缓冲区写满之后，会对缓冲区中的记录进行排序，排好序的记录组成一个数据块，数据块包含 Merge_chunk 和数据记录两部分，Merge_chunk 写入一个磁盘文件（chunk_file），数据记录写入另一个磁盘文件（temp_file）。Merge_chunk 中保存着数据记录在磁盘文件（temp_file）中的起始位置、记录数量等信息。
Merge_chunk 和数据记录写入磁盘文件之后，排序缓冲区中的数据被清空，然后就可以写入其它待排序记录了，再次写满之后，缓冲区中的记录同样会进行排序，组成一个数据块，并把 Merge_chunk 和数据记录分别写入磁盘文件 chunk_file 和 temp_file。
读完符合 where 条件的所有记录之后，可能会天生多个数据块，对数据块进行 7 路归并排序，把 7 个小数据块合并成大数据块，直到合并得到的大数据块数量小于即是 15 个（如果归并排序之前，数据块数量本身就小于即是 15 个，此步骤跳过）。
末了，通过多路归并排序把小于即是 15 个数据块合并为终极的排序结果，写入磁盘文件（out_file）。
以上便是 MySQL 文件排序实现过程的整体概览，有了这个根本，我们就能够进一步展开个中的细节了。
2. 排序缓冲区（sort buffer）排序缓冲区是内存缓冲区，用于存放待排序记录。对付做事器来说，内存是稀缺资源，既然排序缓冲区在内存中，其大小一定要受到限定，系统变量 sort_buffer_size 便是用于掌握排序缓冲区大小的。
sort_buffer_size 默认值为 256K，最小可以设置为 32K，最大可以设置为 4G。
3. 单个排序字段太长了怎么办？order by 子句中，可能会包含一个或多个排序字段，排序字段可以是 int、char、varchar、blob 等各种类型，假设有个字段是这么定义的：a varchar(21845)，utf8 字符集下，字段内容最大可以达到 65535 字节，将近 64K。
排序缓冲区的默认大小为 256K，如果以这样一个字段作为排序字段，就算每条记录只把这一个字段写入到排序缓冲区，写入 4 条记录缓冲区就满了，在记录数量很多情形下，就意味着大量的数据块要写入到磁盘文件，而大量的磁盘 IO 会导致全体排序过程耗时增加，由此可见，排序内容长度也必须受到限定。
max_sort_length 便是用于掌握单个字段排序内容长度的，默认值为 1024 字节，最小可以设置为 4 字节，最大可以设置为 8M。
如果单个排序字段内容长度大于 max_sort_length，只有前 max_sort_length 字节的内容会参与排序，以 max_sort_length = 1024 字节为例，对付单个排序字段内容长度超过 1024 字节的多条记录，如果前 1024 字节的内容相同，1025 字节及之后的内容不相同，会导致 MySQL 认为记录的排序字段内容一样，从而涌现排序结果和预期不一致的情形。
排序模式是官方的叫法，实际上便是排序缓冲区或磁盘文件中会写入哪些内容。排序模式一共有 3 种：
这 3 种排序模式的共同点，都会把排序字段（sort_key）写入排序缓冲区或磁盘文件，排序字段可能是一个，也可能是多个。
4.1 <sort_key, additional_fields><sort_key, additional_fields> 表示排序缓冲区或磁盘文件中，除了要写入排序字段（sort_key），还要写入存储引擎返回给 server 层的所有字段（additional_fields）：
additional_fields 没有描述为
select 子句中的所有字段，而是用了更长的描述存储引擎返回给 server 层的所有字段，是由于两者并不完备一样，本文后面涌现干系的场景时，也都利用后者来描述。上图是写入到排序缓冲区中记录的示意图，以下对各个部分进行解释：
排序字段（sort_key）：排序字段内容，会进行编码以节省存储空间，可能包含一个或多个排序字段。
字段 标记区域：创建表时，没有指定 NOT 的字段，在这个区域会有 1 bit 用于标记记录中该字段内容是否为 。
char 长度：char 字段长度，占用 1 字节或 2 字节。<sort_key, packed_additional_fields> 排序模式中，为了节省空间，只写入 char 字段实际内容到排序缓冲区，以是须要记录字段内容长度。为了逻辑统一，<sort_key, additional_fields> 排序模式中也会写入 char 字段长度和内容到排序缓冲区。
char 内容：char 字段内容，以最大长度存储，
不会去掉内容尾部的空格。varchar 长度：varchar 字段内容长度，占用 1 字节或 2 字节。
varchar 内容：varchar 字段内容，占用空间为字段最大长度。
如果字段实际内容长度小于定义的最大长度，剩余空间留空。除 blob 类型之外的其它字段：指是的除 tinyblob、mediumblob、blob、longblob、tinytext、mediumtext、text、longtext、json、geometry 之外的其它类型字段，只须要把字段内容写入排序缓冲区，不须要写入字段长度。
tinyblob、mediumblob、blob、longblob、tinytext、mediumtext、text、longtext、json、geometry 都是基于 blob 类型实现的，而 select 子句中包含 blob 类型字段时，不能利用 <sort_key, additional_fields>、<sort_key, packed_additional_fields> 排序模式。
重点解释： 如果某个字段内容为 ，该字段在
字段 标记区域对应的 标记位设置为 1，同时，该字段在排序缓冲区中还会占用存储空间，占用空间大小为字段最大长度。<sort_key, additional_fields> 排序模式的好处，只须要从存储引擎读取一次数据，排序缓冲区或排序结果的终极文件（out_file）存放的便是已经排好序的所有记录，读取个中须要的字段返回给客户端就可以了，这因此空间换韶光的办法。
如果排序缓冲区不足存储符合 where 条件的所有待排序记录，就须要把缓冲区中的记录排好序之后写入磁盘文件，虽然磁盘比较内存来说，空间可以大很多，但是磁盘 IO 比较内存访问效率低下。<sort_key, additional_fields> 排序模式虽然实现起来大略方便，但也会导致排序缓冲区只能存放更少的待排序记录、须要更多的磁盘 IO、占用更多的磁盘空间，以是，其利用会有所限定。
利用 <sort_key, additional_fields> 须要知足以下条件：
存储引擎返回给 server 层的字段中不能包含 blob 类型字段，由于 blob 字段一样平常都是用于存储比较长的内容。 排序字段（sort_key）长度之和 +additional_fields 所有字段最大长度之和必须小于即是系统变量max_length_for_sort_data的值。如果不知足上面两个条件，会利用 <sort_key, rowid> 排序模式，后面会讲述这种模式。
max_length_for_sort_data 默认值为 1024 字节，最小可设置为 4 字节，最大可设置为 8M。
<sort_key, additional_fields> 的优点是大略方便，它也有缺点，additional_fields 所有字段在排序缓冲区或磁盘文件中都是按照字段最大占用字节数来分配空间的，在以下两种场景中会存在空间摧残浪费蹂躏：
字段内容为 ，以 utf8 字符集的 varchar 字段为例，假设有字段 a varchar(21845)，当字段 a 的内容为 时，它在排序缓冲区或磁盘文件中占用的空间也是 21845 3 = 65535 字节，对付 int、float 等其它字段也一样，都存在空间摧残浪费蹂躏。char、varchar 类型字段，字段内容实际占用空间小于最大长度，还是以上面的字段 a 为例，如果字段内容为 文件排序是怎么实现的，只须要10（字符数） 3 = 30 字节就能够存放，但实际占用空间依然是 65535 字节。为理解决这种排序模式摧残浪费蹂躏空间的问题，引入了另一种排序模式
4.2 <sort_key, packed_additional_fields><sort_key, packed_additional_fields>。<sort_key, packed_additional_fields> 表示排序缓冲区或磁盘文件中，除了要存入排序字段（sort_key），还要存入存储引擎返回给 server 层的所有字段（packed_additional_fields），并且会尽可能利用最少的空间存放待排序记录。
字段内容为 时，除 1 bit 的 标记位之外，字段在排序缓冲区不占用额外存储空间；char、varchar 类型字段内容长度小于字段最大长度时，字段在排序缓冲区中只占用实际内容长度大小的空间，不会像 <sort_key, additional_fields> 排序模式一样每个字段都占用字段最大长度大小的空间。
上图是写入到排序缓冲区中记录的示意图，以下对各个部分进行解释：
排序字段（sort_key）：排序字段内容，会进行编码以节省存储空间，可能包含一个或多个排序字段。 记录长度：存储排序缓冲区的记录中，除 排序字段（sort_key）之外的长度，也便是记录长度 ~ 除 blob 类型之外的其它字段的长度。字段 标记区域：创建表时，没有指定 NOT 的字段，在这个区域会有 1 bit 用于存储记录中该字段内容是否为 。 char 长度：char 字段长度，占用 1 字节或 2 字节。为了节省空间，只写入 char 字段实际内容到排序缓冲区，以是须要记录字段内容长度。 char 内容：char 字段实际内容，以实际长度存储， 会去掉内容尾部的空格。varchar 长度：varchar 字段内容长度，占用 1 字节或 2 字节。 varchar 内容：varchar 字段实际内容。 除 blob 类型之外的其它字段：指是的除 tinyblob、mediumblob、blob、longblob、tinytext、mediumtext、text、longtext、json、geometry 之外的其它类型，只须要把字段内容写入排序缓冲区，不须要写入字段长度。 重点解释： 如果某个字段内容为 ，该字段在 字段 标记区域对应的 标记位设置为 1，字段不会占用排序缓冲区的额外空间。<sort_key, packed_additional_fields> 因此 <sort_key, additional_fields> 为根本的，如果不知足利用 <sort_key, additional_fields> 的条件，也不会利用 <sort_key, packed_additional_fields>。
利用 <sort_key, packed_additional_fields> 排序模式，还须要知足以下条件：
packed_additional_fields 所有字段最大长度之和必须 小于即是 65535 字节。为什么是 65535 字节？由于只写入字段实际内容到排序缓冲区或磁盘文件，不同记录长度可能会不一样，这就须要把每条记录的长度记下来，MySQL 用 2 个字节来保存记录长度，而 2 字节无符号整数能够表示的最大数字为 65535。写入排序缓冲区或磁盘文件的一条记录长度必须 小于即是系统变量max_length_for_sort_data的值，记录长度 = 排序字段（sort_key）长度之和 + 存储记录长度的 2 字节 + packed_additional_fields 所有字段最大长度之和。可压缩字段最大长度之和必须大于 12 字节，如果可节省的空间太小，也就没必要折腾了。 前面我们讲述了 <sort_key, additional_fields>、<sort_key, packed_additional_fields> 的优缺陷及利用限定，如果这两种排序模式都不能利用怎么办？
别急，该轮到 <sort_key, rowid> 排序模式出场了，MySQL 刚出道时采取的便是这种排序模式。
4.3 <sort_key, rowid><sort_key, rowid> 表示排序缓冲区或磁盘文件中，除了要存入排序字段（sort_key），还要存入记录的主键 ID（rowid）。
上图是写入到排序缓冲区中记录的示意图，比较其它两种排序模式来说，非常大略，不做过多解释了。
想必大家该当创造了 <sort_key, rowid> 和 <sort_key, additional_fields>、<sort_key, packed_additional_fields> 的差异了，利用 <sort_key, rowid> 时，排序缓冲区或磁盘文件中只包含了记录的主键 ID，而客户端可能须要除主键之外的字段，怎么办？
这就要二次访问存储引擎了，第一次从存储引擎拿到符合 where 条件的所有记录的
主键 ID，第二次根据主键 ID 从存储引擎一条一条读取记录，得到客户端须要的所有字段。利用 <sort_key, rowid> 读取数据的过程，有点类似根据 ID 批量从 redis 获取详细数据的过程，先从某个 redis key 读取多个 ID，然后根据 ID 读取缓存的详细数据。
这种排序模式的好处是记录数量不太多的情形下，利用排序缓冲区就能够存储所有待排序记录了，能够在一定程度上避免利用磁盘文件排序。
举例解释：假设排序字段为 int 类型，主键也为 int 类型，写入排序缓冲区的一条记录占用的空间为 4 + 4 = 8 字节，排序缓冲区的默认大小为 256K，能够存放 32768 条记录，对付一样平常业务来说，都不会一次性读取这么多记录，由此可见，一样平常情形下，利用 <sort_key, rowid> 排序模式不会用到磁盘文件排序。
但是，凡事都有例外，如果一条 SQL 语句读取过多的记录，哪怕是利用 <sort_key, rowid>，当排序缓冲区满时，也须要把缓冲区中的记录排好序组成一个
数据块，写入磁盘文件，这样一来，即要利用磁盘文件，又要二次访问存储引擎，实行效率就有点惨不忍睹了。细心的小伙伴可能创造了一点情形，到现在为止讲的三种排序模式，都是把符合 where 条件的
所有记录写入排序缓冲区或磁盘文件，那还有优化空间吗？MySQL 为了提升性能，想了各种办法，利用了各种技巧，对付上面提到的这种情形，自然也还可以再优化，我们一起来看看吧。
5. 提升排序效率5.1 优先行列步队通过前面的讲述，我们已经知道了，MySQL 会把符合 where 条件的所有记录写入排序缓冲区，当缓冲区满时，缓冲区中的记录排好序后组成一个
数据块，写入到磁盘文件（temp_file），而磁盘 IO 比较内存访问效率低下，优先行列步队便是为了在文件排序过程中避免利用磁盘文件的一种优化方案。也便是说，利用了优先行列步队就不会利用磁盘文件排序。优先行列步队在内存中掩护待排序记录的行列步队，行列步队中的元素不会实际存储记录内容，而是存储指向排序缓冲区中记录的地址，由于要担保不该用磁盘文件，利用优先行列步队提升排序效率的
必要条件是：SQL 语句必须包含 limit。在知足必要条件的根本上，会评估利用优先行列步队进行排序是否更快，以决定是否利用。
利用优先行列步队提升排序效率，借鉴的是
大顶堆的思路，排序缓冲区中只须要保留待排序记录中最大或最小的 limit 条记录（取决于正序还是倒序排序），而不须要存放所有待排序记录。基于前面的描述可以知道，利用优先行列步队的上风有两个：不该用磁盘文件排序，避免磁盘 IO。 只须要对一部分待排序记录中进行排序。 如果排序缓冲区
不能存放所有待排序记录，就意味着须要借助磁盘文件排序，利用优先行列步队无疑是更好的选择，这种情形下，只要排序缓冲区中能够存放 limit + 1 条记录，就会利用优先行列步队。limit + 1 中的 是优先行列步队须要利用的额外的一条记录的空间。
如果排序缓冲区
能够存放所有待排序记录，本身就不须要利用磁盘文件进行排序，利用优先行列步队的上风就剩下一个了：只须要对一部分待排序记录中进行排序。官方根据单元测试创造，利用优先行列步队 + 排序缓冲区进行排序须要的韶光是只利用排序缓冲区的3 倍。因此，当 limit 数量小于待排序记录数量的三分之一时，利用优先行列步队 + 排序缓冲区比只利用排序缓冲区排序更快，才会利用优先行列步队来提升排序效率。经由前面一系列的本钱评估之后，如果还是不能利用优先行列步队，MySQL 会进行末了一次考试测验，这便是末了一抖动了：如果利用的排序模式是 <sort_key, additional_fields>，可能会造成须要利用磁盘文件排序，此时会判断利用
<sort_key, rowid> + 优先行列步队的本钱是否比利用<sort_key, additional_fields> + 磁盘文件排序的本钱更低。。如果利用
<sort_key, additional_fields> + 磁盘文件排序本钱更低，那么还是保持原样，依然利用 <sort_key, additional_fields> 排序模式。如果利用
<sort_key, rowid> + 优先行列步队本钱更低，并且排序缓冲区中能够存放 limit + 1 记录的排序字段（sort_key）和主键 ID，利用的排序模式会由 <sort_key, additional_fields> 修正为 <sort_key, rowid>，并且利用优先行列步队来减少实际参与排序的记录数量，提升排序效率。前面提到的
limit并不是 SQL 语句中 limit 后面的数字，而是 SQL 语句中的 offset + limit。想要理解 MySQL 中 limit 是怎么实现的，可以参考这篇文章：MySQL 查询语句的 limit, offset 是怎么实现的？看到这里，可能有的小伙伴会有疑问，排序模式 <sort_key, additional_fields> 是不是和优先行列步队两者不能共存？
<sort_key, additional_fields> 和优先行列步队是可以共存的，只有当利用 <sort_key, additional_fields> 排序模式导致排序缓冲区不能存放所有待排序记录，要借助磁盘文件实现排序时，如果改为利用
5.2 随机 IO 变为顺序 IO<sort_key, rowid> + 优先行列步队实现排序本钱更低，才会把 <sort_key, additional_fields> 修正为 <sort_key, rowid>，并且利用优先行列步队提升排序效率。利用 <sort_key, rowid> 排序模式，从存储引擎读取符合 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 的实现逻辑是这样的：
从终极的排序结果磁盘文件（out_file）读取主键 ID，写入 随机读缓冲区。写满之后，对 随机读缓冲区中的主键 ID 进行排序。排好序之后，再按照主键 ID 逐条从存储引擎读取记录中须要返回给客户真个其它字段。 这个优化方案基于这样一个假设的条件条件：一批主键 ID，排好序之后逻辑上相邻的主键 ID，其对应的记录更有可能在主键索引的同一个叶子节点中，从存储引擎读取一个主键 ID 对应的记录之后，再读取下一个主键 ID 对应的记录，该记录所在的主键索引叶子节点有可能已经被加载到内存中了，就可以直接从内存中读取记录，从而一定程序上减少随机 IO，提升读取数据的效率。
只有当排序缓冲区存放不下所有记录的 <sort_key, rowid>，须要利用磁盘文件来存储时，才有可能利用随机缓冲区来优化文件排序，然而，这还只是入门门槛，要想利用随机缓冲区，须要知足的其它条件达 9 条之多，涉及到源码细节，就不一一展开了，大家只要知道有这么一种优化方案存在就可以了。
利用 <sort_key, additional_fields>、<sort_key, packed_additional_fields> 排序模式时，不须要利用随机缓冲区来优化文件排序，由于这两种排序模式下，须要返回给客户真个所有字段都已经在排序缓冲区或磁盘文件（out_file）中了，不须要通过主键 ID 二次访问存储引擎读取其它字段。
6. 两类排序MySQL order by 的实现过程，可能会进行两类排序：内部排序、外部排序。
前面多次提到，当排序缓冲区满，会把缓冲区中的记录排好序，组成一个
数据块，然后写入磁盘文件，这里的排序便是内部排序。符合 where 条件的所有记录都写入到磁盘文件之后，可能会存在多个已经内部排好序的
6.1 内部排序数据块，这些数据块须要通过多路归并排序，终极形玉成局有序的结果，这里的排序便是外部排序。内部排序是对排序缓冲区中的记录进行排序，是内存排序。
为了提升性能，MySQL 做了各种各样的努力，内部排序的实现又一次表示了这种追求极致性能的努力。内部排序利用了 3 种排序算法：
基数排序如果排序字段内容长度之和 小于即是 20 字节，并且要排序的记录数量大于即是 1 千，小于 10 万，同时能够知足基数排序须要的内存空间，则会利用基数排序。快速排序如果不知足利用基数排序的条件，则会考虑利用 快速排序，要排序的记录数量小于即是 100，就会利用快速排序。归并排序归并排序是兜底的排序算法，如果不知足利用基数排序和快速排序的条件，就会利用 归并排序。为什么利用快速排序的条件是排序记录数量小于即是 100？源码注释是这样说的，归并排序比快速排序更快，但是归并排序申请临时缓冲区须要额外的韶光本钱，以是在排序记录数量很少的时候，归并排序并没有多大上风，归并排序比快速排序快的临界点是
6.2 外部排序排序记录数量在 10 ~ 40 条之间，守旧一点，以是把这个阈值定为 100。外部排序是对磁盘文件中已经局部排好序的记录进行全局归并排序，是磁盘文件排序。
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）。末了一轮归并排序，写入到磁盘文件的是
7. 倒序排序终极结果，磁盘文件（out_file）中存放的是全局排好序的记录，此时记录中只包含存储引擎返回给 server 层的字段，已经不包含排序字段了。MySQL 文件排序的内部实现中，正序和倒序排序都因此正序的办法进行的，排序字段值大的在前面，排序字段值小的在后面，这样逻辑统一，实现方便。
倒序排序时，把排序字段值写入排序缓冲区之前，会对所有排序字段值进行
逐字节取反操作，取反之后，原来字段值大的变成小的，字段值小的变成大的，排序字段值取反之后再进行正序排序，终极得到的记录便是倒序排序的了。举例解释
select num from t order by num desc以 <sort_key, additional_fields> 排序模式为例，假设表中有 5 条记录，num 字段值分别为：95, 90, 49, 97, 6，num 字段值会写入到排序缓冲区两次，一次是作为 sort_key，一次是作为 additional_fields，5 条记录全部写入缓冲区之后，缓冲区的内容示意如下：
图中
蓝色块表示 sort_key，绿色块表示 additional_fields，为了有个比拟，1 号图示 和 2 号图示分别表示正序和倒序排序之前，排序缓冲区中的记录示意图。3 号图示表示倒序排序之后，排序缓冲区中的记录示意图。从 3 号图示可见，倒序排序时，对排序字段值取反之后按照正序排序，终极实现了记录的
倒序排序。上面示例中，对付 num 字段会写入排序缓冲区两次，可能有的小伙伴会有疑问，这里阐明一下：实际上，排序字段作为 sort_key 写入到排序缓冲区之前，都会进行编码，编码之后的排序字段值就和原字段值不一样了，只用于排序，不作为终极结果返回给客户端，在排好序之后，sort_key 会被丢弃。
8. 窥伺更多排序细节通过 explain，我们只能看到 SQL 语句实行时，是否利用了文件排序，看不到排序过程中是只利用了排序缓冲区，还是也利用了磁盘文件，更不知道排序缓冲区被写满了多少次；也看不到是不是利用了优先行列步队，如果没有利用，是什么缘故原由。
好在 MySQL 给我们供应了一个工具（
optimizer trace）可以进一步理解这些细节，实行以下 SQL 可开启 optimizer trace：
-- 开启 optimizer traceset 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\"大众: ,\公众sort_buffer_size\"大众: 262112,\"大众sort_mode\"大众: \"大众<sort_key, rowid>\"大众}number_of_tmp_files：
即是 0 表示只利用了排序缓冲区。 大于 0 表示还利用了磁盘文件，number_of_tmp_files 的值即是几，就表示排序缓冲区被写满了几次，也意味着写入到磁盘文件的数据块有几个。 大家不要被
number_of_tmp_files属性名误导，虽然属性名中有 tmp_files，但这并不是表示排序过程中利用了多个临时文件。实际上不管有多少个数据块，都是写入到一个磁盘文件（temp_file）中。相信经由本文前面的讲述，大家对付 sort_mode 都已经比较熟习了，一共有三种排序模式：<sort_key, rowid>、<sort_key, additional_fields>、<sort_key, packed_additional_fields>。
// 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 1select from information_schema.OPTIMIZER_TRACE; -- SQL 2对付上面例子，如果先实行
9. 总结SQL 1再实行SQL 2，会创造 optimizer trace 结果是空的，必须同时实行 SQL 1 和 SQL 2，才能得到 SQL 1 的 optimizer trace 结果。本文我们以文件排序的整体概览开始，抛开实现细节，从全局角度理解了文件排序的整体逻辑。接着先容了系统变量
sort_buffer_size用于掌握排序缓冲区大小，max_sort_length用于掌握单个排序字段内容长度。
排序模式小节，先容了三种排序模式：<sort_key, additional_fields> 把排序字段（sort_key）和存储引擎返回给 server 层的字段都写入排序缓冲区或磁盘文件，每个字段都以其最大长度占用存储空间，存在在空间摧残浪费蹂躏。 <sort_key, packed_additional_fields> 是 <sort_key, additional_fields> 的改进版，办理了空间摧残浪费蹂躏的问题。char、varchar 字段只占用实际内容须要的空间，内容为 的字段除了在 标记区域占用 1 bit 之外，不会再占用其它空间。 前面两种排序模式，以空间换韶光，虽然不须要两次访问存储引擎，让文件排序逻辑整体上更大略，但是记录数量多起来之后，须要磁盘文件存储排序结果，而磁盘 IO 会导致排序效率低下。<sort_key, rowid> 须要 两次访问存储引擎，但只写入排序字段（sort_key）和主键 ID 到排序缓冲区，一定程度上避免了利用磁盘文件存放排序结果，某些情形下可能会比前两种排序模式更优。
提升排序效率小节，先容了源码中采取的两个优化方案：SQL 语句中包含 limit 的情形下，通过本钱评估有可能会利用优先行列步队来避免磁盘文件排序，提升排序效率。 利用 <sort_key, rowid> 排序模式，并且由于记录数量太多须要利用磁盘文件时，通过把主键 ID 缓存在随机读缓冲区（read rnd bufer），缓冲区满后对主键 ID 排序，再通过主键 ID 去存储引擎读取客户端须要的字段，尽可能把随机 IO 变为顺序 IO，提升排序效率。
两类排序小节，先容了三种内部排序算法，其利用优先级为：基数排序、快速排序、归并排序。外部排序，可能会进行 0 ~ N 轮归并排序天生
中间结果，最后进行一轮归并排序得到终极结果。天生中间结果的归并排序，排序字段（sort_key）也会写入到磁盘文件，后续天生中间结果和终极结果的归并排序都会用到。天生终极结果的归并排序，磁盘文件只写入存储引擎返回给 server 层的字段，不会包含排序字段（sort_key）。
倒序排序小节，先容了倒序排序的实现：先对排序字段（sort_key）逐字节取反，然后对排序字段进行正序排序，终极得到倒序排序的记录。末了，先容了如何通过 optimizer trace 窥伺文件排序的更多细节。
我们一起学习更多 MySQL 知识
