MySQL排序内部原理探秘

<p style="color:rgb(51,51,51);font-family:'microsoft yahei',arial;font-size:16px;text-align:justify;">
<span style="font-weight:700;">［目录］

#stepsfilesort_informationdirectionfieldactor_agefilesort_priority_queue_optimizationusablecause applicable ( LIMIT)filesort_executionfilesort_summaryexamined_rowsnumber_of_tmp_filessort_buffer_sizesort_mode

: [
              {
                : ,: ,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. 重复1，2两步，直到每个100MB chunk大小排序好的数据都被写入磁盘；
  3. 每次读取排序好的chunk中前10MB（= 100MB / (9 chunks + 1)）数据，一共9个chunk需要90MB，剩下的10MB作为输出缓存；
  4. 对这些数据进行一个“9路归并”，并将结果写入输出缓存。如果输出缓存满了，则直接写入最终排序结果文件并清空输出缓存；如果9个10MB的输入缓存空了，从对应的文件再读10MB的数据，直到读完整个文件。最终输出的排序结果文件就是900MB排好序的数据了。

  

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

  

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

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

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

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

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

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

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

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

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

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

  的描述只有一句话

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

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

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

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

  <span class="hljs-keyword" style="color:rgb(0,136);"&gt;for</span> (i=<span class="hljs-number" style="color:rgb(0,102);"&gt;0</span> ; i < num_chunks - MERGEBUFF * <span class="hljs-number" style="color:rgb(0,102);"&gt;3</span> / <span class="hljs-number" style="color:rgb(0,102);"&gt;2</span> ; i+= MERGEBUFF)
  {
    <span class="hljs-keyword" style="color:rgb(0,136);"&gt;if</span> (merge_buffers(param,// param
                      from_file,// from_file
                      to_file,// to_file
                      sort_buffer,// sort_buffer
                      last_chunk++,// last_chunk [out]
                      Merge_chunk_array(&amp;chunk_array[i],MERGEBUFF),<span class="hljs-number" style="color:rgb(0,102);"&gt;0</span>))                     // flag
    goto cleanup;
  }
  <span class="hljs-keyword" style="color:rgb(0,from_file,to_file,sort_buffer,last_chunk++,Merge_chunk_array(&amp;chunk_array[i],num_chunks - i),102);"&gt;0</span>))
    <span class="hljs-keyword" style="color:rgb(0,136);"&gt;break</span>;                                    /* purecov: inspected */
  <span class="hljs-keyword" style="color:rgb(0,136);">...
  
  }

  
  <p style="color:rgb(51,arial;font-size:16px;text-align:justify;">
  截取部分<code style="font-family:'Source Code Pro',63);">merge_buffers()的代码如下，

  
  <pre class="prettyprint" style="overflow:auto;font-family:'Source Code Pro',monospace;color:inherit;display:block;">int merge_buffers(Sort_param param,IO_CACHE from_file,IO_CACHE to_file,Merge_chunk last_chunk,int flag)
  {
  <span class="hljs-keyword" style="color:rgb(0,136);">...
  current_thd->inc_status_sort_merge_passes();
  <span class="hljs-keyword" style="color:rgb(0,arial;font-size:16px;text-align:justify;">
  可以看到：每个<code style="font-family:'Source Code Pro',63);">merge_buffers()都会增加<code style="font-family:'Source Code Pro',63);">sort_merge_passes，也就是说每一次对MERGEBUFF
  (7)个block归并排序都会让<code style="font-family:'Source Code Pro',63);">sort_merge_passes加一，<code style="font-family:'Source Code Pro',63);">sort_merge_passes越多表示排序的数据太多，需要多次merge
  pass。解决的方案无非就是缩减要排序数据的大小或者增加<code style="font-family:'Source Code Pro',63);">sort_buffer_size。

  
  <p style="color:rgb(51,arial;font-size:16px;text-align:justify;">
  打个小广告，在我们的qmonitor中就有<code style="font-family:'Source Code Pro',63);">sort_merge_pass的性能指标和参数值过大的报警设置。

  
  <h2 style="font-family:'microsoft yahei',51);font-size:30px;text-align:justify;">
  六、trace结果解释

  
  <p style="color:rgb(51,arial;font-size:16px;text-align:justify;">
  说明白了三种排序模式和外部排序的方法，我们回过头来看一下trace的结果。
  
  <h3 style="font-family:'microsoft yahei',51);font-size:24px;text-align:justify;">
  6.1 是否存在磁盘外部排序