带你一步一步深入了解MySQLOrderBy文件排序

　　我们日常工作中写SQL语句，经常会使用orderby对记录进行排序。如果orderby能够使用索引中记录已经排好序的特性，就不需要再借助内存或磁盘空间进行排序，这无疑是效率最高的。然而，还是有各种情况导致orderby不能够使用索引，而是要进行额外的排序操作。MySQL把需要借助内存或磁盘空间进行的排序操作统称为文件排序，而没有在概念上进一步分为文件排序和内存排序。
　　本文讲述的文件排序逻辑基于MySQL5。7。35源码。
　　内容目录整体概览排序缓冲区（sortbuffer）单个排序字段太长怎么办？排序模式
　　4。1sortkey，additionalfields
　　4。2sortkey，packedadditionalfields
　　4。3sortkey，rowid提升排序效率
　　5。1优先队列
　　5。2随机IO变为顺序IO两类排序
　　6。1内部排序
　　6。2外部排序倒序排序窥探更多排序细节总结1。整体概览
　　为了更好的把握MySQL文件排序的全局，我们先抛开细节，来看看它的实现过程示意图：
　　结合上面的示意图，我们来描述一下大体的实现过程：server层从存储引擎读取符合where条件的记录，写入一个专门存放待排序记录的内存区域，这个内存区域叫做排序缓冲区（sortbuffer）。排序缓冲区写满之后，会对缓冲区中的记录进行排序，排好序的记录组成一个数据块，数据块包含Mergechunk和数据记录两部分，Mergechunk写入一个磁盘文件（chunkfile），数据记录写入另一个磁盘文件（tempfile）。Mergechunk中保存着数据记录在磁盘文件（tempfile）中的起始位置、记录数量等信息。Mergechunk和数据记录写入磁盘文件之后，排序缓冲区中的数据被清空，然后就可以写入其它待排序记录了，再次写满之后，缓冲区中的记录同样会进行排序，组成一个数据块，并把Mergechunk和数据记录分别写入磁盘文件chunkfile和tempfile。读完符合where条件的所有记录之后，可能会生成多个数据块，对数据块进行7路归并排序，把7个小数据块合并成大数据块，直到合并得到的大数据块数量小于等于15个（如果归并排序之前，数据块数量本身就小于等于15个，此步骤跳过）。最后，通过多路归并排序把小于等于15个数据块合并为最终的排序结果，写入磁盘文件（outfile）。
　　以上就是MySQL文件排序实现过程的整体概览，有了这个基础，我们就能够进一步展开其中的细节了。2。排序缓冲区（sortbuffer）
　　排序缓冲区是内存缓冲区，用于存放待排序记录。对于服务器来说，内存是稀缺资源，既然排序缓冲区在内存中，其大小必然要受到限制，系统变量sortbuffersize就是用于控制排序缓冲区大小的。
　　sortbuffersize默认值为256K，最小可以设置为32K，最大可以设置为4G。3。单个排序字段太长了怎么办？
　　orderby子句中，可能会包含一个或多个排序字段，排序字段可以是int、char、varchar、blob等各种类型，假设有个字段是这么定义的：avarchar（21845），utf8字符集下，字段内容最大可以达到65535字节，将近64K。
　　排序缓冲区的默认大小为256K，如果以这样一个字段作为排序字段，就算每条记录只把这一个字段写入到排序缓冲区，写入4条记录缓冲区就满了，在记录数量很多情况下，就意味着大量的数据块要写入到磁盘文件，而大量的磁盘IO会导致整个排序过程耗时增加，由此可见，排序内容长度也必须受到限制。
　　maxsortlength就是用于控制单个字段排序内容长度的，默认值为1024字节，最小可以设置为4字节，最大可以设置为8M。
　　如果单个排序字段内容长度大于maxsortlength，只有前maxsortlength字节的内容会参与排序，以maxsortlength1024字节为例，对于单个排序字段内容长度超过1024字节的多条记录，如果前1024字节的内容相同，1025字节及之后的内容不相同，会导致MySQL认为记录的排序字段内容一样，从而出现排序结果和预期不一致的情况。4。排序模式（sortmode）
　　排序模式是官方的叫法，实际上就是排序缓冲区或磁盘文件中会写入哪些内容。排序模式一共有3种：sortkey，additionalfieldssortkey，packedadditionalfieldssortkey，rowid
　　这3种排序模式的共同点，都会把排序字段（sortkey）写入排序缓冲区或磁盘文件，排序字段可能是一个，也可能是多个。4。1sortkey，additionalfields
　　sortkey，additionalfields表示排序缓冲区或磁盘文件中，除了要写入排序字段（sortkey），还要写入存储引擎返回给server层的所有字段（additionalfields）：
　　additionalfields没有描述为select子句中的所有字段，而是用了更长的描述存储引擎返回给server层的所有字段，是因为两者并不完全一样，本文后面出现相关的场景时，也都使用后者来描述。
　　上图是写入到排序缓冲区中记录的示意图，以下对各个部分进行说明：排序字段（sortkey）：排序字段内容，会进行编码以节省存储空间，可能包含一个或多个排序字段。字段NULL标记区域：创建表时，没有指定NOTNULL的字段，在这个区域会有1bit用于标记记录中该字段内容是否为NULL。char长度：char字段长度，占用1字节或2字节。
　　sortkey，packedadditionalfields排序模式中，为了节省空间，只写入char字段实际内容到排序缓冲区，所以需要记录字段内容长度。为了逻辑统一，sortkey，additionalfields排序模式中也会写入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类型字段时，不能使用sortkey，additionalfields、sortkey，packedadditionalfields排序模式。重点说明：如果某个字段内容为NULL，该字段在字段NULL标记区域对应的NULL标记位设置为1，同时，该字段在排序缓冲区中还会占用存储空间，占用空间大小为字段最大长度。
　　sortkey，additionalfields排序模式的好处，只需要从存储引擎读取一次数据，排序缓冲区或排序结果的最终文件（outfile）存放的就是已经排好序的所有记录，读取其中需要的字段返回给客户端就可以了，这是以空间换时间的方式。
　　如果排序缓冲区不够存储符合where条件的所有待排序记录，就需要把缓冲区中的记录排好序之后写入磁盘文件，虽然磁盘相比内存来说，空间可以大很多，但是磁盘IO相比内存访问效率低下。sortkey，additionalfields排序模式虽然实现起来简单方便，但也会导致排序缓冲区只能存放更少的待排序记录、需要更多的磁盘IO、占用更多的磁盘空间，所以，其使用会有所限制。
　　使用sortkey，additionalfields需要满足以下条件：存储引擎返回给server层的字段中不能包含blob类型字段，因为blob字段一般都是用于存储比较长的内容。排序字段（sortkey）长度之和additionalfields所有字段最大长度之和必须小于等于系统变量maxlengthforsortdata的值。
　　如果不满足上面两个条件，会使用sortkey，rowid排序模式，后面会讲述这种模式。
　　maxlengthforsortdata默认值为1024字节，最小可设置为4字节，最大可设置为8M。
　　sortkey，additionalfields的优点是简单方便，它也有缺点，additionalfields所有字段在排序缓冲区或磁盘文件中都是按照字段最大占用字节数来分配空间的，在以下两种场景中会存在空间浪费：字段内容为NULL，以utf8字符集的varchar字段为例，假设有字段avarchar（21845），当字段a的内容为NULL时，它在排序缓冲区或磁盘文件中占用的空间也是21845365535字节，对于int、float等其它字段也一样，都存在空间浪费。char、varchar类型字段，字段内容实际占用空间小于最大长度，还是以上面的字段a为例，如果字段内容为文件排序是怎么实现的，只需要10（字符数）330字节就能够存放，但实际占用空间依然是65535字节。
　　为了解决这种排序模式浪费空间的问题，引入了另一种排序模式sortkey，packedadditionalfields。4。2sortkey，packedadditionalfields
　　sortkey，packedadditionalfields表示排序缓冲区或磁盘文件中，除了要存入排序字段（sortkey），还要存入存储引擎返回给server层的所有字段（packedadditionalfields），并且会尽可能使用最少的空间存放待排序记录。
　　字段内容为NULL时，除1bit的NULL标记位之外，字段在排序缓冲区不占用额外存储空间；char、varchar类型字段内容长度小于字段最大长度时，字段在排序缓冲区中只占用实际内容长度大小的空间，不会像sortkey，additionalfields排序模式一样每个字段都占用字段最大长度大小的空间。
　　上图是写入到排序缓冲区中记录的示意图，以下对各个部分进行说明：排序字段（sortkey）：排序字段内容，会进行编码以节省存储空间，可能包含一个或多个排序字段。记录长度：存储排序缓冲区的记录中，除排序字段（sortkey）之外的长度，也就是记录长度除blob类型之外的其它字段的长度。字段NULL标记区域：创建表时，没有指定NOTNULL的字段，在这个区域会有1bit用于存储记录中该字段内容是否为NULL。char长度：char字段长度，占用1字节或2字节。为了节省空间，只写入char字段实际内容到排序缓冲区，所以需要记录字段内容长度。char内容：char字段实际内容，以实际长度存储，会去掉内容尾部的空格。varchar长度：varchar字段内容长度，占用1字节或2字节。varchar内容：varchar字段实际内容。除blob类型之外的其它字段：指是的除tinyblob、mediumblob、blob、longblob、tinytext、mediumtext、text、longtext、json、geometry之外的其它类型，只需要把字段内容写入排序缓冲区，不需要写入字段长度。重点说明：如果某个字段内容为NULL，该字段在字段NULL标记区域对应的NULL标记位设置为1，字段不会占用排序缓冲区的额外空间。
　　sortkey，packedadditionalfields是以sortkey，additionalfields为基础的，如果不满足使用sortkey，additionalfields的条件，也不会使用sortkey，packedadditionalfields。
　　使用sortkey，packedadditionalfields排序模式，还需要满足以下条件：packedadditionalfields所有字段最大长度之和必须小于等于65535字节。
　　为什么是65535字节？
　　因为只写入字段实际内容到排序缓冲区或磁盘文件，不同记录长度可能会不一样，这就需要把每条记录的长度记下来，MySQL用2个字节来保存记录长度，而2字节无符号整数能够表示的最大数字为65535。写入排序缓冲区或磁盘文件的一条记录长度必须小于等于系统变量maxlengthforsortdata的值，记录长度排序字段（sortkey）长度之和存储记录长度的2字节packedadditionalfields所有字段最大长度之和。可压缩字段最大长度之和必须大于12字节，如果可节省的空间太小，也就没必要折腾了。
　　前面我们讲述了sortkey，additionalfields、sortkey，packedadditionalfields的优缺点及使用限制，如果这两种排序模式都不能使用怎么办？
　　别急，该轮到sortkey，rowid排序模式出场了，MySQL刚出道时采用的就是这种排序模式。4。3sortkey，rowid
　　sortkey，rowid表示排序缓冲区或磁盘文件中，除了要存入排序字段（sortkey），还要存入记录的主键ID（rowid）。
　　上图是写入到排序缓冲区中记录的示意图，相比其它两种排序模式来说，非常简单，不做过多说明了。
　　想必大家应该发现了sortkey，rowid和sortkey，additionalfields、sortkey，packedadditionalfields的区别了，使用sortkey，rowid时，排序缓冲区或磁盘文件中只包含了记录的主键ID，而客户端可能需要除主键之外的字段，怎么办？
　　这就要二次访问存储引擎了，第一次从存储引擎拿到符合where条件的所有记录的主键ID，第二次根据主键ID从存储引擎一条一条读取记录，得到客户端需要的所有字段。
　　使用sortkey，rowid读取数据的过程，有点类似根据ID批量从redis获取详细数据的过程，先从某个rediskey读取多个ID，然后根据ID读取缓存的详细数据。
　　这种排序模式的好处是记录数量不太多的情况下，使用排序缓冲区就能够存储所有待排序记录了，能够在一定程度上避免使用磁盘文件排序。
　　举例说明：假设排序字段为int类型，主键也为int类型，写入排序缓冲区的一条记录占用的空间为448字节，排序缓冲区的默认大小为256K，能够存放32768条记录，对于一般业务来说，都不会一次性读取这么多记录，由此可见，一般情况下，使用sortkey，rowid排序模式不会用到磁盘文件排序。
　　但是，凡事都有例外，如果一条SQL语句读取过多的记录，哪怕是使用sortkey，rowid，当排序缓冲区满时，也需要把缓冲区中的记录排好序组成一个数据块，写入磁盘文件，这样一来，即要使用磁盘文件，又要二次访问存储引擎，执行效率就有点惨不忍睹了。
　　细心的小伙伴可能发现了一点情况，到现在为止讲的三种排序模式，都是把符合where条件的所有记录写入排序缓冲区或磁盘文件，那还有优化空间吗？
　　MySQL为了提升性能，想了各种办法，使用了各种技巧，对于上面提到的这种情况，自然也还可以再优化，我们一起来看看吧。5。提升排序效率5。1优先队列
　　通过前面的讲述，我们已经知道了，MySQL会把符合where条件的所有记录写入排序缓冲区，当缓冲区满时，缓冲区中的记录排好序后组成一个数据块，写入到磁盘文件（tempfile），而磁盘IO相比内存访问效率低下，优先队列就是为了在文件排序过程中避免使用磁盘文件的一种优化方案。也就是说，使用了优先队列就不会使用磁盘文件排序。
　　优先队列在内存中维护待排序记录的队列，队列中的元素不会实际存储记录内容，而是存储指向排序缓冲区中记录的地址，因为要保证不使用磁盘文件，使用优先队列提升排序效率的必要条件是：SQL语句必须包含limit。
　　在满足必要条件的基础上，会评估使用优先队列进行排序是否更快，以决定是否使用。
　　使用优先队列提升排序效率，借鉴的是大顶堆的思路，排序缓冲区中只需要保留待排序记录中最大或最小的limit条记录（取决于正序还是倒序排序），而不需要存放所有待排序记录。基于前面的描述可以知道，使用优先队列的优势有两个：不使用磁盘文件排序，避免磁盘IO。只需要对一部分待排序记录中进行排序。
　　如果排序缓冲区不能存放所有待排序记录，就意味着需要借助磁盘文件排序，使用优先队列无疑是更好的选择，这种情况下，只要排序缓冲区中能够存放limit1条记录，就会使用优先队列。
　　limit1中的1是优先队列需要使用的额外的一条记录的空间。
　　如果排序缓冲区能够存放所有待排序记录，本身就不需要使用磁盘文件进行排序，使用优先队列的优势就剩下一个了：只需要对一部分待排序记录中进行排序。官方根据单元测试发现，使用优先队列排序缓冲区进行排序需要的时间是只使用排序缓冲区的3倍。因此，当limit数量小于待排序记录数量的三分之一时，使用优先队列排序缓冲区比只使用排序缓冲区排序更快，才会使用优先队列来提升排序效率。
　　经过前面一系列的成本评估之后，如果还是不能使用优先队列，MySQL会进行最后一次尝试，这就是最后一哆嗦了：如果使用的排序模式是sortkey，additionalfields，可能会造成需要使用磁盘文件排序，此时会判断使用sortkey，rowid优先队列的成本是否比使用sortkey，additionalfields磁盘文件排序的成本更低
　　如果使用sortkey，additionalfields磁盘文件排序成本更低，那么还是保持原样，依然使用sortkey，additionalfields排序模式。
　　如果使用sortkey，rowid优先队列成本更低，并且排序缓冲区中能够存放limit1记录的排序字段（sortkey）和主键ID，使用的排序模式会由sortkey，additionalfields修改为sortkey，rowid，并且使用优先队列来减少实际参与排序的记录数量，提升排序效率。
　　前面提到的limit并不是SQL语句中limit后面的数字，而是SQL语句中的offsetlimit。想要了解MySQL中limit是怎么实现的，可以参考这篇文章：MySQL查询语句的limit，offset是怎么实现的？
　　看到这里，可能有的小伙伴会有疑问，排序模式sortkey，additionalfields是不是和优先队列两者不能共存？
　　sortkey，additionalfields和优先队列是可以共存的，只有当使用sortkey，additionalfields排序模式导致排序缓冲区不能存放所有待排序记录，要借助磁盘文件实现排序时，如果改为使用sortkey，rowid优先队列实现排序成本更低，才会把sortkey，additionalfields修改为sortkey，rowid，并且使用优先队列提升排序效率。5。2随机IO变为顺序IO
　　使用sortkey，rowid排序模式，从存储引擎读取符合where条件的所有记录的主键ID，按照sortkey排序好序之后，需要根据主键ID从存储引擎读取记录中的需要返回给客户端的其它字段。按照sortkey排好序的记录，在主键索引中不一定是顺序存储的，可能是分散在主键索引的不同叶子节点中，这样一来，通过主键ID一条一条去存储引擎读取记录，会造成大量随机IO，导致从存储引擎读取数据效率低下。
　　为了尽可能减少随机IO，MySQL通过一个专门的内存区域，尽量把随机IO变成顺序IO，这个专门的内存区域为随机读缓冲区（readrndbuffer）。
　　缓冲区大小由系统变量readrndbuffersize控制，默认大小为256K，最小为1字节，最大为2G，如果设置为1字节，就相当于禁用了这个缓冲区了。
　　随机IO变为顺序IO的实现逻辑是这样的：从最终的排序结果磁盘文件（outfile）读取主键ID，写入随机读缓冲区。写满之后，对随机读缓冲区中的主键ID进行排序。排好序之后，再按照主键ID逐条从存储引擎读取记录中需要返回给客户端的其它字段。
　　这个优化方案基于这样一个假设的前提条件：一批主键ID，排好序之后逻辑上相邻的主键ID，其对应的记录更有可能在主键索引的同一个叶子节点中，从存储引擎读取一个主键ID对应的记录之后，再读取下一个主键ID对应的记录，该记录所在的主键索引叶子节点有可能已经被加载到内存中了，就可以直接从内存中读取记录，从而一定程序上减少随机IO，提升读取数据的效率。
　　只有当排序缓冲区存放不下所有记录的sortkey，rowid，需要使用磁盘文件来存储时，才有可能使用随机缓冲区来优化文件排序，然而，这还只是入门门槛，要想使用随机缓冲区，需要满足的其它条件达9条之多，涉及到源码细节，就不一一展开了，大家只要知道有这么一种优化方案存在就可以了。
　　使用sortkey，additionalfields、sortkey，packedadditionalfields排序模式时，不需要使用随机缓冲区来优化文件排序，因为这两种排序模式下，需要返回给客户端的所有字段都已经在排序缓冲区或磁盘文件（outfile）中了，不需要通过主键ID二次访问存储引擎读取其它字段。6。两类排序
　　MySQLorderby的实现过程，可能会进行两类排序：内部排序、外部排序。
　　前面多次提到，当排序缓冲区满，会把缓冲区中的记录排好序，组成一个数据块，然后写入磁盘文件，这里的排序就是内部排序。
　　符合where条件的所有记录都写入到磁盘文件之后，可能会存在多个已经内部排好序的数据块，这些数据块需要通过多路归并排序，最终形成全局有序的结果，这里的排序就是外部排序。6。1内部排序
　　内部排序是对排序缓冲区中的记录进行排序，是内存排序。
　　为了提升性能，MySQL做了各种各样的努力，内部排序的实现又一次体现了这种追求极致性能的努力。内部排序使用了3种排序算法：基数排序
　　如果排序字段内容长度之和小于等于20字节，并且要排序的记录数量大于等于1千，小于10万，同时能够满足基数排序需要的内存空间，则会使用基数排序。快速排序
　　如果不满足使用基数排序的条件，则会考虑使用快速排序，要排序的记录数量小于等于100，就会使用快速排序。归并排序
　　归并排序是兜底的排序算法，如果不满足使用基数排序和快速排序的条件，就会使用归并排序。
　　为什么使用快速排序的条件是排序记录数量小于等于100？
　　源码注释是这样说的，归并排序比快速排序更快，但是归并排序申请临时缓冲区需要额外的时间成本，所以在排序记录数量很少的时候，归并排序并没有多大优势，归并排序比快速排序快的临界点是排序记录数量在1040条之间，保守一点，所以把这个阈值定为100。6。2外部排序
　　外部排序是对磁盘文件中已经局部排好序的记录进行全局归并排序，是磁盘文件排序。
　　MySQL从存储引擎读取符合where的条件记录写入排序缓冲区，缓冲区满时，会对缓冲区中的记录进行内部排序，排好序的数据组成一个数据块，数据块包含两部分：Mergechunk和数据记录。
　　Mergechunk写入到磁盘文件（chunkfile）中，数据记录写入到磁盘文件（tempfile）中。Mergechunk中保存有数据记录在tempfile中的起始位置、Mergechunk对应的数据块在tempfile中的记录数量等信息。
　　从存储引擎读取完符合where条件的所有记录之后，可能会生成多个数据块写入到磁盘文件（tempfile）。通过多路归并排序，把小数据块合并为更大的数据块，最终得到全局排好序的记录，把磁盘文件（tempfile）中多个数据块合并为一个数据块的过程，借助了优先队列和排序缓冲区来实现。
　　注意：外部排序过程中借助优先队列和排序缓冲区，和5。1优先队列中的优先队列排序缓冲区不是一回事，不要混淆了。外部排序过程只是使用了优先队列和排序缓冲区来加快归并排序的过程。
　　外部排序把小数据块合并为大数据块的过程中，会使用7路归并排序，把7个小数据块合并为1个大数据块，数据块数量多时，会进行多轮归并排序，直到数据块的数量小于等于15，多轮归并排序之后得到的小于等于15个数据块，经过终极归并排序得到最终的排序结果。
　　接下来我们以磁盘文件（tempfile）中包含160个数据块为例来说明外部排序的过程。
　　第一轮归并排序示意图：：
　　左下角chunkfile中有160个Mergechunk，tempfile有160个对应于Mergechunk的数据记录块。归并排序过程中会借助排序缓冲区提升执行效率，因为要进行7路归并排序，排序缓冲区被平均分为7份，每份对应于tempfile中的一个数据块，为了描述方便，我们暂且把排序缓冲区的七分之一叫做子排序缓冲区。在归并排序过程中，会分别从tempfile中的7个数据记录块中读取一部分记录到其对应的子排序缓冲区。
　　读取tempfile中数据记录块的数据到子排序缓冲区之后，优先队列中的每个Mergechunk（对应于chunkfile中的Mergechunk）中有一个属性currentkey，指向子排序缓冲区中的第一条记录，图中优先队列的每个Mergechunk有个红色箭头指向子排序缓冲区，就是表示currentkey属性指向子排序缓冲区中的第一条记录。
　　currentkey指向的记录是子排序缓冲区对应的tempfile数据记录块中排序字段值（sortkey）最大的那条记录。
　　归并排序过程中，会循环把7个Mergechunk的currentkey指向的记录中排序字段值最大的记录写入到tempfile2的数据记录块中，直到所有数据记录块中的记录都写入到tempfile2文件。
　　每次都取currentkey指向的记录中最大的记录，有没有发现这是大顶堆的特点？在源码实现中，找到优先队列中Mergechunk的currentkey属性指向的记录中排序字段值最大的记录，就是用大顶堆的思路实现的。
　　从图中右下角的tempfile2和chunkfile可以看到，经过第一轮归并排序之后，160个小数据块合并成了23个更大的数据块，23大于15，所以还需要进行第二轮归并排序。
　　第二轮归并排序示意图：
　　第一轮归并排序，我们已经讲述了详细的合并过程，第二轮归并排序就不展开讲了，由上图右下角的tempfile和chunkfile可见，第二轮归并排序，由小数据块合并得到的23个更大的数据块，再次进行7路归并排序，最终得到4个数据块。4小于15，所以不需要进行得到中间结果的第三轮归并排序，直接进行得到最终排序结果的多路归并排序。
　　不知道大家有没有发现，第一轮归并排序示意图中，是从tempfile读取记录到子排序缓冲区，然后把归并排序结果写入到tempfile2；第二轮归并排序示意图中，是从tempfile2读取记录到子排序缓冲区，然后把归并排序结果写入到tempfile。这说明在外部归并排序过程中，会使用两个中间结果磁盘文件（tempfile、tempfile2），加上chunkfile、outfile，一共会使用4个磁盘文件，大家知道一下就可以了。
　　终极多路归并排序：
　　从上图可见，经过前面两轮归并排序之后，得到4个数据块，排序缓冲区被分为4个子缓冲区，4个子缓冲区中已局部排好序的记录，经过归并排序写入到存放最终排序结果的磁盘文件中（outfile）。
　　最后一轮归并排序和前面的N归并排序有些不同。
　　前面N轮归并排序，写入到磁盘文件的是中间结果，磁盘文件（tempfile、tempfile2）中存放的还是局部排好序的记录，并且记录中还包含排序字段（sortkey），因为后面的归并排序还需要用到排序字段（sortkey）。
　　最后一轮归并排序，写入到磁盘文件的是最终结果，磁盘文件（outfile）中存放的是全局排好序的记录，此时记录中只包含存储引擎返回给server层的字段，已经不包含排序字段了。7。倒序排序
　　MySQL文件排序的内部实现中，正序和倒序排序都是以正序的方式进行的，排序字段值大的在前面，排序字段值小的在后面，这样逻辑统一，实现方便。
　　倒序排序时，把排序字段值写入排序缓冲区之前，会对所有排序字段值进行逐字节取反操作，取反之后，原来字段值大的变成小的，字段值小的变成大的，排序字段值取反之后再进行正序排序，最终得到的记录就是倒序排序的了。
　　举例说明selectnumfromtorderbynumdesc
　　以sortkey，additionalfields排序模式为例，假设表中有5条记录，num字段值分别为：95，90，49，97，6，num字段值会写入到排序缓冲区两次，一次是作为sortkey，一次是作为additionalfields，5条记录全部写入缓冲区之后，缓冲区的内容示意如下：
　　图中蓝色块表示sortkey，绿色块表示additionalfields，为了有个对比，1号图示和2号图示分别表示正序和倒序排序之前，排序缓冲区中的记录示意图。3号图示表示倒序排序之后，排序缓冲区中的记录示意图。
　　从3号图示可见，倒序排序时，对排序字段值取反之后按照正序排序，最终实现了记录的倒序排序。
　　上面示例中，对于num字段会写入排序缓冲区两次，可能有的小伙伴会有疑问，这里解释一下：实际上，排序字段作为sortkey写入到排序缓冲区之前，都会进行编码，编码之后的排序字段值就和原字段值不一样了，只用于排序，不作为最终结果返回给客户端，在排好序之后，sortkey会被丢弃。8。窥探更多排序细节
　　通过explain，我们只能看到SQL语句执行时，是否使用了文件排序，看不到排序过程中是只使用了排序缓冲区，还是也使用了磁盘文件，更不知道排序缓冲区被写满了多少次；也看不到是不是使用了优先队列，如果没有使用，是什么原因。
　　好在MySQL给我们提供了一个工具（optimizertrace）可以进一步了解这些细节，执行以下SQL可开启optimizertrace：开启optimizertracesetoptimizertraceenabledon；设置optimizertrace输出结果最多可占用的内存空间，单位是：字节如果发现optimizertrace的json结果不全，可以把这个值改成更大的数字setoptimizertracemaxmemsize1048576；
　　optimizertrace的输出结果json中有两个和文件排序相关的属性：filesortsummary、filesortpriorityqueueoptimization，下面我把写本文过程中使用的测试SQL的optimizertrace作为例子来说明：filesortsummary｛rows：10227，examinedrows：10227，numberoftmpfiles：41，sortbuffersize：262112，sortmode：sortkey，rowid｝
　　numberoftmpfiles：等于0表示只使用了排序缓冲区。大于0表示还使用了磁盘文件，numberoftmpfiles的值等于几，就表示排序缓冲区被写满了几次，也意味着写入到磁盘文件的数据块有几个。
　　大家不要被numberoftmpfiles属性名误导，虽然属性名中有tmpfiles，但这并不是表示排序过程中使用了多个临时文件。实际上不管有多少个数据块，都是写入到一个磁盘文件（tempfile）中。
　　相信经过本文前面的讲述，大家对于sortmode都已经比较熟悉了，一共有三种排序模式：sortkey，rowid、sortkey，additionalfields、sortkey，packedadditionalfields。filesortpriorityqueueoptimization｛usable：false，cause：notapplicable（noLIMIT）｝
　　通过usablefalse可知，我的测试SQL没有使用优先队列，原因是没有指定limit。
　　有一点需要特别注意，获取optimizertrace结果的语句必须和SQL语句同时执行，不能分开一条一条的执行，否则查出来的optimizertrace结果是空白。
　　举例说明：selectfromt2wherei199991840orderbystr1；SQL1selectfrominformationschema。OPTIMIZERTRACE；SQL2
　　对于上面例子，如果先执行SQL1再执行SQL2，会发现optimizertrace结果是空的，必须同时执行SQL1和SQL2，才能得到SQL1的optimizertrace结果。9。总结
　　本文我们以文件排序的整体概览开始，抛开实现细节，从全局角度了解了文件排序的整体逻辑。接着介绍了系统变量sortbuffersize用于控制排序缓冲区大小，maxsortlength用于控制单个排序字段内容长度。
　　排序模式小节，介绍了三种排序模式：sortkey，additionalfields把排序字段（sortkey）和存储引擎返回给server层的字段都写入排序缓冲区或磁盘文件，每个字段都以其最大长度占用存储空间，存在在空间浪费。sortkey，packedadditionalfields是sortkey，additionalfields的改进版，解决了空间浪费的问题。char、varchar字段只占用实际内容需要的空间，内容为NULL的字段除了在NULL标记区域占用1bit之外，不会再占用其它空间。前面两种排序模式，以空间换时间，虽然不需要两次访问存储引擎，让文件排序逻辑整体上更简单，但是记录数量多起来之后，需要磁盘文件存储排序结果，而磁盘IO会导致排序效率低下。
　　sortkey，rowid需要两次访问存储引擎，但只写入排序字段（sortkey）和主键ID到排序缓冲区，一定程度上避免了使用磁盘文件存放排序结果，某些情况下可能会比前两种排序模式更优。
　　提升排序效率小节，介绍了源码中采用的两个优化方案：SQL语句中包含limit的情况下，通过成本评估有可能会使用优先队列来避免磁盘文件排序，提升排序效率。使用sortkey，rowid排序模式，并且由于记录数量太多需要使用磁盘文件时，通过把主键ID缓存在随机读缓冲区（readrndbufer），缓冲区满后对主键ID排序，再通过主键ID去存储引擎读取客户端需要的字段，尽可能把随机IO变为顺序IO，提升排序效率。
　　两类排序小节，介绍了三种内部排序算法，其使用优先级为：基数排序、快速排序、归并排序。
　　外部排序，可能会进行0N轮归并排序生成中间结果，最后进行一轮归并排序得到最终结果。
　　生成中间结果的归并排序，排序字段（sortkey）也会写入到磁盘文件，后续生成中间结果和最终结果的归并排序都会用到。生成最终结果的归并排序，磁盘文件只写入存储引擎返回给server层的字段，不会包含排序字段（sortkey）。
　　倒序排序小节，介绍了倒序排序的实现：先对排序字段（sortkey）逐字节取反，然后对排序字段进行正序排序，最终得到倒序排序的记录。
　　最后，介绍了如何通过optimizertrace窥探文件排序的更多细节。