MySQL排序内部原理探秘

概述［目录］一、我们要解决什么问题 二、排序，排序，排序 三、索引优化排序 四、排序模式 五、外部排序 六、trace结果解释 七、MySQL其他相关排序参数 八、MySQL排序优化总结 九、参考文献一、我们要解决什么问题MySQL排序其实是一个老生常谈的问题了，但是我们这次想由浅入深详细说说MySQL排序模式，怎么影响MySQL选择不同的排序模式和怎么优化排序。同时也希望通过这篇文章解决大家的以下疑问：MySQL在哪些地方会使用排序，怎么判断MySQL使用了排序；MySQL有几种排序模式，我们可以通过什么方法让MySQL选择不同的排序模式；MySQL排序跟read_rnd_buffer_size有啥关系，在哪些情况下增加read_rnd_buffer_size能优化排序；怎么判断MySQL使用到了磁盘来排序，怎么避免或者优化磁盘排序；排序时变长字段（varchar）数据在内存是怎么存储的，5.7有哪些改进；在情况下，排序模式有哪些改进；sort_merge_pass到底是什么鬼，该状态值过大说明了什么问题，可以通过什么方法解决；最后MySQL使用到了排序的话，依次可以通过什么办法分析和优化让排序更快？二、排序，排序，排序我们通过explain查看MySQL执行计划时，经常会看到在Extra列中显示Using filesort。其实这种情况就说明MySQL使用了排序。Using filesort经常出现在order by、group by、distinct、join等情况下。三、索引优化排序看到排序，我们的DBA首先想到的肯定是，是否可以利用索引来优化。InnoDB默认采用的是B tree索引，B tree索引本身就是有序的，如果有一个查询如下：select * from film where actor_name='苍老师' order by prod_time;那么只需要加一个(actor_name,prod_time)的索引就能够利用B tree的特性来避免额外排序。如下图所示：通过B-tree查找到actor_name=’苍老师’演员为苍老师的数据以后，只需要按序往右查找就可以了，不需要额外排序 *** 作。对应的哪些可以利用索引优化排序的列举如下：SELECT * FROM t1ORDER BY key_part1,key_part2,... ;SELECT * FROM t1WHERE key_part1 = constantORDER BY key_part2;SELECT * FROM t1ORDER BY key_part1 DESC, key_part2 DESC;SELECT * FROM t1WHERE key_part1 = 1ORDER BY key_part1 DESC, key_part2 DESC;SELECT * FROM t1WHERE key_part1 > constantORDER BY key_part1 ASC;SELECT * FROM t1WHERE key_part1 < constantORDER BY key_part1 DESC;SELECT * FROM t1WHERE key_part1 = constant1 AND key_part2 > constant2ORDER BY key_part2;从以上例子里面我们也可以看到，如果要让MySQL使用索引优化排序应该怎么建组合索引。四、排序模式4.1 实际trace结果但是还是有非常多的SQL没法使用索引进行排序，例如select * from film where Producer like '东京热%' and prod_time>'2015-12-01' order by actor_age;我们想查询“东京热”出品的，从去年12月1号以来，并且按照演员的年龄排序的电影信息。 （好吧，假设我这里有一个每一位男DBA都想维护的数据库:）这种情况下，使用索引已经无法避免排序了，那MySQL排序到底会怎么做列。笼统的来说，它会按照：依据Producer like '东京热%' and prod_time>’2015-12-01’过滤数据，查找需要的数据；对查找到的数据按照order by actor_age进行排序,并 按照select*将必要的数据按照actor_age依序返回给客户端。空口无凭，我们可以利用MySQL的optimize trace来查看是否如上所述。如果通过optimize trace看到更详细的MySQL优化器trace信息，可以查看阿里印风的博客初识5.6的optimizer trace。trace结果如下：依据Producer like ‘东京热%’ and prod_time>’2015-12-01’过滤数据，查找需要的数据"attaching_conditions_to_tables": {"original_condition": "((`film`.`Producer` like '东京热%') and (`film`.`prod_time` > '2015-12-01'))","attached_conditions_computation": [],"attached_conditions_summary": [{"table": "`film`","attached": "((`film`.`Producer` like '东京热%') and (`film`.`prod_time` > '2015-12-01'))"}]}对查找到的数据按照order by actor_age进行排序,并按照select*将必要的数据按照actor_age依序返回给客户端"join_execution": {"select#": 1,"steps": [{"filesort_information": [{"direction": "asc","table": "`film`","field": "actor_age"}],"filesort_priority_queue_optimization": {"usable": false,"cause": "not applicable (no LIMIT)"},"filesort_execution": [],"filesort_summary": {"rows": 1,"examined_rows": 5,"number_of_tmp_files": 0,"sort_buffer_size": 261872,"sort_mode": "<sort_key, packed_additional_fields>"}}]}这里，我们可以明显看到，MySQL在执行这个select的时候执行了针对film表.actor_age字段的asc排序 *** 作。"filesort_information": [{"direction": "asc","table": "`film`","field": "actor_age"}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(快速排序算法)在内存中排好序，并写到临时文件中；重复上述步骤，直到所有的行数据都正常读取了完成；用到了临时文件的，需要利用磁盘外部排序，将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个字符内存空间（

<p >
<span >［目录］

<p >
一、我们要解决什么问题 
二、排序，排序，排序 
三、索引优化排序 
四、排序模式 
五、外部排序 
六、trace结果解释 
七、MysqL其他相关排序参数 
八、MysqL排序优化总结 
九、参考文献

<h2 >
一、我们要解决什么问题
<p >
MysqL排序其实是一个老生常谈的问题了，但是我们这次想由浅入深详细说说MysqL排序模式，怎么影响MysqL选择不同的排序模式和怎么优化排序。

<p >
同时也希望通过这篇文章解决大家的以下疑问：

<ol >

MysqL在哪些地方会使用排序，怎么判断MysqL使用了排序；MysqL有几种排序模式，我们可以通过什么方法让MysqL选择不同的排序模式；MysqL排序跟有啥关系，在哪些情况下增加能优化排序；怎么判断MysqL使用到了磁盘来排序，怎么避免或者优化磁盘排序；排序时变长字段（varchar）数据在内存是怎么存储的，5.7有哪些改进；在情况下，排序模式有哪些改进；到底是什么鬼，该状态值过大说明了什么问题，可以通过什么方法解决；最后MysqL使用到了排序的话，依次可以通过什么办法分析和优化让排序更快？

)的索引就能够利用B tree的特性来避免额外排序。

 *  t1    key_part1,key_part2,... ;
<span ><span  >WHERE key_part1 = constant
<span  >BY key_part2;
<span ><span  >BY key_part1 <span  >DESC,key_part2 <span  >DESC;
<span ><span  >WHERE key_part1 = <span  >1
<span  >WHERE key_part1 > constant
<span  >ASC;
<span ><span  >WHERE key_part1 < constant
<span  >WHERE key_part1 = constant1 <span  >AND key_part2 > constant2
<span  >BY key_part2;

<p >
从以上例子里面我们也可以看到，如果要让MysqL使用索引优化排序应该怎么建组合索引。

<h2 >
四、排序模式
<h3 >
4.1 实际trace结果
<p >
但是还是有非常多的sql没法使用索引进行排序，例如

<p >select * from film where Producer like '东京热%' and prod_time>'2015-12-01' order by actor_age;

<p >
我们想查询“东京热”出品的，从去年12月1号以来，并且按照演员的年龄排序的电影信息。 
（好吧，假设我这里有一个每一位男DBA都想维护的数据库:）

<p >
这种情况下，使用索引已经无法避免排序了，那MysqL排序到底会怎么做列。

<p >
笼统的来说，它会按照：

<ol >

依据’2015-12-01’过滤数据，查找需要的数据；对查找到的数据按照进行排序,并 按照将必要的数据按照依序返回给客户端。

依据’2015-12-01’过滤数据，查找需要的数据

 '2015-12-01'))","attached_conditions_computation": [      ],"attached_conditions_summary": [        {          "table": "`film`","attached": "((`film`.`Producer` like '东京热%') and (`film`.`prod_time` > '2015-12-01'))"        }      ]    }

对查找到的数据按照依序返回给客户端

#stepsfilesort_informationdirectionfIEldactor_agefilesort_priority_queue_optimizationusablecause applicable ( liMIT)filesort_executionfilesort_summaryexamined_rowsnumber_of_tmp_filessort_buffer_sizesort_mode

字段的asc排序 *** 作。

: [              {                : ,: ,0);">"fIEld":               }

"

)    (,num_rows)    ,param_rows)    ,num_chunks)    ,table_sort_buffer_size())    _alnum(,68);">.using_packed_addons() ?               " :               param_addon_fIElds() ?                : )

”和“< sort_key,additional_fields >看过其他介绍介绍MysqL排序文章的同学应该比较清楚，相对较新。

对应的是MysqL 4.1以后引入的“修改后排序模式”

根据索引或者全表扫描，按照过滤条件获得需要查询的排序字段值和row ID；将要排序字段值和row ID组成键值对，存入sort buffer中；如果sort buffer内存大于这些键值对的内存，就不需要创建临时文件了。否则，每次sort buffer填满以后，需要直接用qsort(快速排序算法)在内存中排好序，并写到临时文件中；重复上述步骤，直到所有的行数据都正常读取了完成；用到了临时文件的，需要利用磁盘外部排序，将row ID写入到结果文件中；根据结果文件中的row ID按序读取用户需要返回的数据。由于row ID不是顺序的，导致回表时是随机IO，为了进一步优化性能（变成顺序IO），MysqL会读一批row ID，并将读到的数据按排序字段顺序插入缓存区中(内存大小)。

根据索引或者全表扫描，按照过滤条件获得需要查询的数据；将要排序的列值和组成键值对，存入sort buffer中；如果sort buffer内存大于这些键值对的内存，就不需要创建临时文件了。否则，每次sort buffer填满以后，需要直接用qsort(快速排序算法)在内存中排好序，并写到临时文件中；重复上述步骤，直到所有的行数据都正常读取了完成；用到了临时文件的，需要利用磁盘外部排序，将排序后的数据写入到结果文件中；直接从结果文件中返回用户需要的字段数据，而不是根据row ID再次回表查询。

的参数。当“排序的键值对大小” > 时，MysqL认为磁盘外部排序的IO效率不如回表的效率，会选择第一种排序模式；反之，会选择第二种不回表的模式。

从要排序的900M数据中读取100MB数据到内存中，并按照传统的内部排序算法（快速排序）进行排序；将排序好的数据写入磁盘；重复1，2两步，直到每个100MB chunk大小排序好的数据都被写入磁盘；每次读取排序好的chunk中前10MB（= 100MB / (9 chunks + 1)）数据，一共9个chunk需要90MB，剩下的10MB作为输出缓存；对这些数据进行一个“9路归并”，并将结果写入输出缓存。如果输出缓存满了，则直接写入最终排序结果文件并清空输出缓存；如果9个10MB的输入缓存空了，从对应的文件再读10MB的数据，直到读完整个文件。最终输出的排序结果文件就是900MB排好序的数据了。

从要排序的50GB数据中读取100MB数据到内存中，并按照传统的内部排序算法（快速排序）进行排序；将排序好的数据写入磁盘；重复1，2两步，直到每个100MB chunk大小排序好的数据都被写入磁盘；每次取25个分片进行归并排序，这样就形成了20个（500/25=20）更大的2.5GB有序的文件；对这20个2.5GB的有序文件进行归并排序，形成最终排序结果文件。

根据索引或者全表扫描，按照过滤条件获得需要查询的数据；

将要排序的列值和row ID组成键值对，存入sort buffer中；

如果sort buffer内存大于这些键值对的内存，就不需要创建临时文件了。否则，每次sort buffer填满以后，需要直接用qsort(快速排序模式)在内存中排好序，作为一个block写到临时文件中。跟正常的外部排序写到多个文件中不一样，MysqL只会写到一个临时文件中，并通过保存文件偏移量的方式来模拟多个文件归并排序；

重复上述步骤，直到所有的行数据都正常读取了完成；

每MERGEBUFF (7) 个block抽取一批数据进行排序，归并排序到另外一个临时文件中，直到所有的数据都排序好到新的临时文件中；

重复以上归并排序过程，直到剩下不到MERGEBUFF2 (15)个block。

通俗一点解释： 第一次循环中，一个block对应一个sort buffer（大小为）排序好的数据；每7个做一个归并。 第二次循环中，一个block对应MERGEBUFF (7) 个sort buffer的数据，每7个做一个归并。 … 直到所有的block数量小于MERGEBUFF2 (15)。

最后一轮循环，仅将row ID写入到结果文件中；

根据结果文件中的row ID按序读取用户需要返回的数据。为了进一步优化性能，MysqL会读一批row ID，并将读到的数据按排序字段要求插入缓存区中(内存大小)。

MysqL把外部排序好的分片写入同一个文件中，通过保存文件偏移量的方式来区别各个分片位置；MysqL每MERGEBUFF (7)个分片做一个归并，最终分片数达到MERGEBUFF2 (15)时，做最后一次归并。这两个值都写死在代码中了……

的描述只有一句话

   passes that   algorithm has had  . If this  is large,you should consIDer increasing     sort_buffer_size  .

到底是什么，该值比较大时说明了什么，通过什么方式可以缓解这个问题。

对应的就是MysqL做归并排序的次数，也就是说，如果值比较大，说明和要排序的数据差距越大，我们可以通过增大或者让填入的键值对更小来缓解归并排序的次数。

函数来实现，第5步单次归并使用实现，源码摘录如下：

<span https://m.jb51.cc/tag/Js/" target="_blank" >Js</a>-keyword" https://m.jb51.cc/tag/color/" target="_blank" >color</a>:rgb(0,136);"&gt;for</span> (i=<span https://m.jb51.cc/tag/Js/" target="_blank" >Js</a>-number" https://m.jb51.cc/tag/color/" target="_blank" >color</a>:rgb(0,102);"&gt;0</span> ; i < num_chunks - MERGEBUFF * <span https://m.jb51.cc/tag/Js/" target="_blank" >Js</a>-number" https://m.jb51.cc/tag/color/" target="_blank" >color</a>:rgb(0,102);"&gt;3</span> / <span https://m.jb51.cc/tag/Js/" target="_blank" >Js</a>-number" https://m.jb51.cc/tag/color/" target="_blank" >color</a>:rgb(0,102);"&gt;2</span> ; i+= MERGEBUFF){  <span https://m.jb51.cc/tag/Js/" target="_blank" >Js</a>-keyword" https://m.jb51.cc/tag/color/" target="_blank" >color</a>:rgb(0,136);"&gt;if</span> (merge_buffers(p<a href="https://www.jb51.cc/tag/ara/" target="_blank" >ara</a>m,// p<a href="https://www.jb51.cc/tag/ara/" target="_blank" >ara</a>m                    from_<a href="https://m.jb51.cc/tag/file/" target="_blank" >file</a>,// from_<a href="https://m.jb51.cc/tag/file/" target="_blank" >file</a>                    to_<a href="https://m.jb51.cc/tag/file/" target="_blank" >file</a>,// to_<a href="https://m.jb51.cc/tag/file/" target="_blank" >file</a>                    sort_buffer,// sort_buffer                    last_chunk++,// last_chunk [out]                    Merge_chunk_array(&amp;chunk_array[i],MERGEBUFF),<span https://m.jb51.cc/tag/Js/" target="_blank" >Js</a>-number" https://m.jb51.cc/tag/color/" target="_blank" >color</a>:rgb(0,102);"&gt;0</span>))                     // flag  goto cleanup;}<span https://m.jb51.cc/tag/Js/" target="_blank" >Js</a>-keyword" https://m.jb51.cc/tag/color/" target="_blank" >color</a>:rgb(0,from_<a href="https://m.jb51.cc/tag/file/" target="_blank" >file</a>,to_<a href="https://m.jb51.cc/tag/file/" target="_blank" >file</a>,sort_buffer,last_chunk++,Merge_chunk_array(&amp;chunk_array[i],num_chunks - i),102);"&gt;0</span>))  <span https://m.jb51.cc/tag/Js/" target="_blank" >Js</a>-keyword" https://m.jb51.cc/tag/color/" target="_blank" >color</a>:rgb(0,136);"&gt;break</span>;                                    /* purecov: i<a href="https://m.jb51.cc/tag/nspec/" target="_blank" >nspec</a>ted */
<span  >...
}


<p >
截取部分<code >merge_buffers()的代码如下，

<pre >int merge_buffers(Sort_param param,IO_CACHE from_file,IOCACHE *tofile,Merge_chunk *last_chunk,int flag)
{
<span >...
current_thd->inc_status_sort_merge_passes();
<span >
可以看到：每个<code >merge_buffers()都会增加<code >sort_merge_passes，也就是说每一次对MERGEBUFF
(7)个block归并排序都会让<code >sort_merge_passes加一，<code >sort_merge_passes越多表示排序的数据太多，需要多次merge
pass。解决的方案无非就是缩减要排序数据的大小或者增加<code >sort_buffer_size。

<p >
打个小广告，在我们的qmonitor中就有<code >sort_merge_pass的性能指标和参数值过大的报警设置。

<h2 >
六、trace结果解释
<p >
说明白了三种排序模式和外部排序的方法，我们回过头来看一下trace的结果。

<h3 >
6.1 是否存在磁盘外部排序
<p >"number_oftmpfiles": 0,

<p >number_oftmpfiles表示有多少个分片，如果<code >number_oftmpfiles不等于0，表示一个<code >sort_buffer_size大小的内存无法保存所有的键值对，也就是说，MysqL在排序中使用到了磁盘来排序。

<h3 >
6.2 是否存在优先队列优化排序
<p >
由于我们的这个sql里面没有对数据进行分页限制，所以<code >filesort_priority_queue_optimization并没有启用

<pre >"filesort_priority_queue_optimization": {
<span >"usable": <span >false,0);">"cause": <span >"not applicable (no liMIT)"
},
<p >
而正常情况下，使用了limit会启用优先队列的优化。优先队列类似于FIFO先进先出队列。

<p >
算法稍微有点改变，以回表排序模式为例。

<p >
<span ><code >sort_buffer_size足够大

<p >
如果limit限制返回N条数据，并且N条数据比<code >sort_buffer_size小，那么MysqL会把sort buffer作为priority queue，在第二步插入priority queue时会按序插入队列；在第三步，队列满了以后，并不会写入外部磁盘文件，而是直接淘汰最尾端的一条数据，直到所有的数据都正常读取完成。

<p >
算法如下：

<ul >

根据索引或者全表扫描，按照过滤条件获得需要查询的数据将要排序的列值和row ID组成键值对，按序存入中priority queue中如果priority queue满了，直接淘汰最尾端记录。重复上述步骤，直到所有的行数据都正常读取了完成最后一轮循环，仅将row ID写入到结果文件中根据结果文件中的row ID按序读取用户需要返回的数据。为了进一步优化性能，MysqL会读一批row ID，并将读到的数据按排序字段要求插入缓存区中(内存大小不够大

大的情况下，MysqL无法直接利用sort buffer作为priority queue，正常的文件外部排序还是一样的，只是在最后返回结果时，只根据N个row ID将数据返回出来。具体的算法我们就不列举了。

函数中确定的，具体的代码细节这里就不展开了。

足够大对limit数据比较小的情况，优化效果是很明显的。

和。

是为了让MysqL选择的模式。

是键值对的大小无法确定时（比如用户要查询的数据包含了 ）MysqL会对每个键值对分配个字节的内存，这样导致内存空间浪费，磁盘外部排序次数过多。

设置为ON的话，表示在排序中生成的临时文件不会用到文件系统的缓存，类似于打开文件。

设置的是在创建InnoDB索引时，使用到的sort buffer的大小。

排序和查询的字段尽量少。只查询你用到的字段，不要使用select *；使用limit查询必要的行数据；要排序或者查询的字段，尽量不要用不确定字符函数，避免MysqL直接分配，导致sort buffer空间不足；使用索引来优化或者避免排序；增加大小，避免磁盘排序；不得不使用original排序算法时，增加；字段长度定义合适就好（避免过长）；tmpdir建议独立存放，放在高速存储设备上。

总结

以上是内存溢出为你收集整理的MySQL排序内部原理探秘全部内容，希望文章能够帮你解决MySQL排序内部原理探秘所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/sjk/1169422.html