MySQL排序内部原理探秘
<p><strong>【目录】</strong></p> <p>一、我们要解决什么问题</p> <p>二、排序,排序,排序</p> <p>三、索引优化排序</p> <p>四、排序模式</p> <p>五、外部排序</p> <p>六、trace结果解释</p> <p>七、MySQL其他相关排序参数</p> <p>八、MySQL排序优化总结</p> <p>九、参考文献</p> <h2><strong>一、我们要解决什么问题</strong></h2> <p>MySQL排序其实是一个老生常谈的问题了,但是我们这次想由浅入深详细说说MySQL排序模式,怎么影响MySQL选择不同的排序模式和怎么优化排序。</p> <p>同时也希望通过这篇文章解决大家的以下疑问:</p> <ol> <li>MySQL在哪些地方会使用排序,怎么判断MySQL使用了排序;</li> <li>MySQL有几种排序模式,我们可以通过什么方法让MySQL选择不同的排序模式;</li> <li>MySQL排序跟 read_rnd_buffer_size 有啥关系,在哪些情况下增加 read_rnd_buffer_size 能优化排序;</li> <li>怎么判断MySQL使用到了磁盘来排序,怎么避免或者优化磁盘排序;</li> <li>排序时变长字段(varchar)数据在内存是怎么存储的,5.7有哪些改进;</li> <li>在</li> <li>情况下,排序模式有哪些改进;</li> <li>sort_merge_pass 到底是什么鬼,该状态值过大说明了什么问题,可以通过什么方法解决;</li> <li>最后MySQL使用到了排序的话,依次可以通过什么办法分析和优化让排序更快?</li> </ol> <h2><strong>二、排序,排序,排序</strong></h2> <p>我们通过explain查看MySQL执行计划时,经常会看到在Extra列中显示Using filesort。</p> <p>其实这种情况就说明MySQL使用了排序。</p> <p>Using filesort经常出现在order by、group by、distinct、join等情况下。</p> <h2><strong>三、索引优化排序</strong></h2> <p>看到排序,我们的DBA首先想到的肯定是,是否可以利用索引来优化。</p> <p>InnoDB默认采用的是B tree索引,B tree索引本身就是有序的,如果有一个查询如下:</p> <p>select * from film where actor_name='苍老师' order by prod_time;</p> <p>那么只需要加一个( actor_name,prod_time )的索引就能够利用B tree的特性来避免额外排序。</p> <p>如下图所示:</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/5c035f70ceb672dec0256cb1bbe2ad2f.jpg"></p> <p>通过B-tree查找到actor_name=’苍老师’演员为苍老师的数据以后,只需要按序往右查找就可以了,不需要额外排序操作。</p> <p>对应的哪些可以利用索引优化排序的列举如下:</p> <pre> <code class="language-sql">SELECT * FROM t1 ORDER BY key_part1,key_part2,... ; SELECT * FROM t1 WHERE key_part1 = constant ORDER BY key_part2; SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 DESC; SELECT * FROM t1 WHERE key_part1 = 1 ORDER BY key_part1 DESC, key_part2 DESC; SELECT * FROM t1 WHERE key_part1 > constant ORDER BY key_part1 ASC; SELECT * FROM t1 WHERE key_part1 < constant ORDER BY key_part1 DESC; SELECT * FROM t1 WHERE key_part1 = constant1 AND key_part2 > constant2 ORDER BY key_part2;</code></pre> <p>从以上例子里面我们也可以看到,如果要让MySQL使用索引优化排序应该怎么建组合索引。</p> <h2><strong>四、排序模式</strong></h2> <h3>4.1 实际trace结果</h3> <p>但是还是有非常多的SQL没法使用索引进行排序,例如</p> <p>select * from film where Producer like '东京热%' and prod_time>'2015-12-01' order by actor_age;</p> <p>我们想查询“东京热”出品的,从去年12月1号以来,并且按照演员的年龄排序的电影信息。</p> <p>(好吧,假设我这里有一个每一位男DBA都想维护的数据库:)</p> <p>这种情况下,使用索引已经无法避免排序了,那MySQL排序到底会怎么做列。</p> <p>笼统的来说,它会按照:</p> <ol> <li>依据 Producer like '东京热%' and prod_time>’2015-12-01’ 过滤数据,查找需要的数据;</li> <li>对查找到的数据按照 order by actor_age 进行排序,并 按照 select * 将必要的数据按照 actor_age 依序返回给客户端。</li> </ol> <p>空口无凭,我们可以利用MySQL的optimize trace来查看是否如上所述。</p> <p>如果通过optimize trace看到更详细的MySQL优化器trace信息,可以查看阿里印风的博客初识5.6的optimizer trace。</p> <p>trace结果如下:</p> <ul> <li> <p>依据 Producer like ‘东京热%’ and prod_time>’2015-12-01’ 过滤数据,查找需要的数据</p> <pre> <code class="language-sql">"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'))" } ] }</code></pre> </li> <li> <p>对查找到的数据按照 order by actor_age 进行排序,并按照 select * 将必要的数据按照 actor_age 依序返回给客户端</p> </li> </ul> <pre> <code class="language-sql">"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>" } } ] }</code></pre> <p>这里,我们可以明显看到,MySQL在执行这个select的时候执行了针对film表 .actor_age 字段的asc排序操作。</p> <pre> <code class="language-sql">"filesort_information": [ { "direction": "asc", "table": "`film`", "field": "actor_age" }</code></pre> <h3><strong>4.2 排序模式概览</strong></h3> <p>我们这里主要关心MySQL到底是怎么排序的,采用了什么排序算法。</p> <p>请关注这里</p> <p>"sort_mode": "<sort_key, packed_additional_fields>"</p> <p>MySQL的sort_mode有三种。</p> <p>摘录5.7.13中sql/filesort.cc源码如下:</p> <pre> <code class="language-sql">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>");</code></pre> <p>< sort_key, rowid >”和“< sort_key, additional_fields > 看过其他介绍介绍MySQL排序文章的同学应该比较清楚, < sort_key, packed_additional_fields > 相对较新。</p> <ul> <li>< sort_key, rowid > 对应的是MySQL 4.1之前的“原始排序模式”</li> <li>< sort_key, additional_fields > 对应的是MySQL 4.1以后引入的“修改后排序模式”</li> <li>< sort_key, packed_additional_fields > 是MySQL 5.7.3以后引入的进一步优化的”打包数据排序模式”</li> </ul> <p>下面我们来一一介绍这三个模式:</p> <p><strong>4.2.1 回表排序模式</strong></p> <ul> <li>根据索引或者全表扫描,按照过滤条件获得需要查询的排序字段值和row ID;</li> <li>将要排序字段值和row ID组成键值对,存入sort buffer中;</li> <li>如果sort buffer内存大于这些键值对的内存,就不需要创建临时文件了。否则,每次sort buffer填满以后,需要直接用qsort(快速排序算法)在内存中排好序,并写到临时文件中;</li> <li>重复上述步骤,直到所有的行数据都正常读取了完成;</li> <li>用到了临时文件的,需要利用磁盘外部排序,将row id写入到结果文件中;</li> <li>根据结果文件中的row ID按序读取用户需要返回的数据。由于row ID不是顺序的,导致回表时是随机IO,为了进一步优化性能(变成顺序IO),MySQL会读一批row ID,并将读到的数据按排序字段顺序插入缓存区中(内存大小 read_rnd_buffer_size )。</li> </ul> <p style="text-align:center"><img src="https://simg.open-open.com/show/9c4df1648b4ab7d0a2d6cf64d9ce75c4.jpg"></p> <p><strong>4.2.2 不回表排序模式</strong></p> <ul> <li>根据索引或者全表扫描,按照过滤条件获得需要查询的数据;</li> <li>将要排序的列值和 <strong>用户需要返回的字段</strong> 组成键值对,存入sort buffer中;</li> <li>如果sort buffer内存大于这些键值对的内存,就不需要创建临时文件了。否则,每次sort buffer填满以后,需要直接用qsort(快速排序算法)在内存中排好序,并写到临时文件中;</li> <li>重复上述步骤,直到所有的行数据都正常读取了完成;</li> <li>用到了临时文件的,需要利用磁盘外部排序,将排序后的数据写入到结果文件中;</li> <li>直接从结果文件中返回用户需要的字段数据,而不是根据row ID再次回表查询。</li> </ul> <p style="text-align:center"><img src="https://simg.open-open.com/show/d93d3fc8ea2666489b89f6c7dc70f0f9.jpg"></p> <p><strong>4.2.3 打包数据排序模式</strong></p> <p>第三种排序模式的改进仅仅在于将char和varchar字段存到sort buffer中时,更加紧缩。</p> <p>在之前的两种模式中,存储了“yes”3个字符的定义为VARCHAR(255)的列会在内存中申请255个字符内存空间,但是5.7.3改进后,只需要存储2个字节的字段长度和3个字符内存空间(用于保存”yes”这三个字符)就够了,内存空间整整压缩了50多倍,可以让更多的键值对保存在sort buffer中。</p> <p><strong>4.2.4 三种模式比较</strong></p> <p>第二种模式是第一种模式的改进,避免了二次回表,采用的是用空间换时间的方法。</p> <p>但是由于sort buffer就那么大,如果用户要查询的数据非常大的话,很多时间浪费在多次磁盘外部排序,导致更多的IO操作,效率可能还不如第一种方式。</p> <p>所以,MySQL给用户提供了一个 max_length_for_sort_data 的参数。当“排序的键值对大小” > max_length_for_sort_data 时,MySQL认为磁盘外部排序的IO效率不如回表的效率,会选择第一种排序模式;反之,会选择第二种不回表的模式。</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/72d4babe19b1364f287f57966726f3fe.jpg"></p> <p>第三种模式主要是解决变长字符数据存储空间浪费的问题,对于实际数据不多,字段定义较长的改进效果会更加明显。</p> <p>很多文章写到这里可能就差不多了,但是大家忘记关注一个问题了:“如果排序的数据不能完全放在sort buffer内存里面,是怎么通过外部排序完成整个排序过程的呢?”</p> <p>要解决这个问题,我们首先需要简单查看一下外部排序到底是怎么做的。</p> <h2><strong>五、外部排序</strong></h2> <h3><strong>5.1 普通外部排序</strong></h3> <p><strong>5.1.1 两路外部排序</strong></p> <p>我们先来看一下最简单,最普遍的两路外部排序算法。</p> <p>假设内存只有100M,但是排序的数据有900M,那么对应的外部排序算法如下:</p> <ol> <li>从要排序的900M数据中读取100MB数据到内存中,并按照传统的内部排序算法(快速排序)进行排序;</li> <li>将排序好的数据写入磁盘;</li> <li>重复1,2两步,直到每个100MB chunk大小排序好的数据都被写入磁盘;</li> <li>每次读取排序好的chunk中前10MB(= 100MB / (9 chunks + 1))数据,一共9个chunk需要90MB,剩下的10MB作为输出缓存;</li> <li>对这些数据进行一个“9路归并”,并将结果写入输出缓存。如果输出缓存满了,则直接写入最终排序结果文件并清空输出缓存;如果9个10MB的输入缓存空了,从对应的文件再读10MB的数据,直到读完整个文件。最终输出的排序结果文件就是900MB排好序的数据了。</li> </ol> <p style="text-align:center"><img src="https://simg.open-open.com/show/9fa80c2c693a4393257a7a43bddc457c.jpg"></p> <p><strong>5.1.2 多路外部排序</strong></p> <p>上述排序算法是一个两路排序算法(先排序,后归并)。但是这种算法有一个问题,假设要排序的数据是50GB而内存只有100MB,那么每次从500个排序好的分片中取200KB(100MB / 501 约等于200KB)就是很多个随机IO。效率非常慢,对应可以这样来改进:</p> <ol> <li>从要排序的50GB数据中读取100MB数据到内存中,并按照传统的内部排序算法(快速排序)进行排序;</li> <li>将排序好的数据写入磁盘;</li> <li>重复1,2两步,直到每个100MB chunk大小排序好的数据都被写入磁盘;</li> <li>每次取25个分片进行归并排序,这样就形成了20个(500/25=20)更大的2.5GB有序的文件;</li> <li>对这20个2.5GB的有序文件进行归并排序,形成最终排序结果文件。</li> </ol> <p>对应的数据量更大的情况可以进行更多次归并。</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/32356ff65a2749931f5519ce405fc860.jpg"></p> <h3><strong>5.2 MySQL外部排序</strong></h3> <p><strong>5.2.1 MySQL外部排序算法</strong></p> <p>那MySQL使用的外部排序是怎么样的列,我们以回表排序模式为例:</p> <ol> <li> <p>根据索引或者全表扫描,按照过滤条件获得需要查询的数据;</p> </li> <li> <p>将要排序的列值和row ID组成键值对,存入sort buffer中;</p> </li> <li> <p>如果sort buffer内存大于这些键值对的内存,就不需要创建临时文件了。否则,每次sort buffer填满以后,需要直接用qsort(快速排序模式)在内存中排好序,作为一个block写到临时文件中。跟正常的外部排序写到多个文件中不一样,MySQL只会写到一个临时文件中,并通过保存文件偏移量的方式来模拟多个文件归并排序;</p> </li> <li> <p>重复上述步骤,直到所有的行数据都正常读取了完成;</p> </li> <li> <p>每MERGEBUFF (7) 个block抽取一批数据进行排序,归并排序到另外一个临时文件中,直到所有的数据都排序好到新的临时文件中;</p> </li> <li> <p>重复以上归并排序过程,直到剩下不到MERGEBUFF2 (15)个block。</p> <p>通俗一点解释:</p> <p>第一次循环中,一个block对应一个sort buffer(大小为 sort_buffer_size )排序好的数据;每7个做一个归并。</p> <p>第二次循环中,一个block对应MERGEBUFF (7) 个sort buffer的数据,每7个做一个归并。</p> <p>…</p> <p>直到所有的block数量小于MERGEBUFF2 (15)。</p> </li> <li> <p>最后一轮循环,仅将row ID写入到结果文件中;</p> </li> <li> <p>根据结果文件中的row ID按序读取用户需要返回的数据。为了进一步优化性能,MySQL会读一批row ID,并将读到的数据按排序字段要求插入缓存区中(内存大小 read_rnd_buffer_size )。</p> </li> </ol> <p>这里我们需要注意的是:</p> <ol> <li>MySQL把外部排序好的分片写入同一个文件中,通过保存文件偏移量的方式来区别各个分片位置;</li> <li>MySQL每MERGEBUFF (7)个分片做一个归并,最终分片数达到MERGEBUFF2 (15)时,做最后一次归并。这两个值都写死在代码中了……</li> </ol> <p>5.2.2 sort_merge_passes</p> <p>MySQL手册中对 Sort_merge_passes 的描述只有一句话</p> <pre> <code class="language-sql">Sort_merge_passes The number of merge passes that the sort algorithm has had to do. If this value is large, you should consider increasing the value of the sort_buffer_size system variable.</code></pre> <p>这段话并没有把 sort_merge_passes 到底是什么,该值比较大时说明了什么,通过什么方式可以缓解这个问题。</p> <p>我们把上面MySQL的外部排序算法搞清楚了,这个问题就清楚了。</p> <p>其实 sort_merge_passes 对应的就是MySQL做归并排序的次数,也就是说,如果 sort_merge_passes 值比较大,说明 sort_buffer 和要排序的数据差距越大,我们可以通过增大 sort_buffer_size 或者让填入 sort_buffer_size 的键值对更小来缓解 sort_merge_passes 归并排序的次数。</p> <p>对应的,我们可以在源码中看到证据。</p> <p>上述MySQL外部排序的算法中第5到第7步,是通过sql/filesort.cc文件中 merge_many_buff() 函数来实现,第5步单次归并使用 merge_buffers() 实现,源码摘录如下:</p> <pre> <code class="language-sql">int merge_many_buff(Sort_param *param, Sort_buffer sort_buffer, Merge_chunk_array chunk_array, size_t *p_num_chunks, IO_CACHE *t_file) { ... for (i=0 ; i < num_chunks - MERGEBUFF * 3 / 2 ; i+= MERGEBUFF) { if (merge_buffers(param, // param from_file, // from_file to_file, // to_file sort_buffer, // sort_buffer last_chunk++, // last_chunk [out] Merge_chunk_array(&chunk_array[i], MERGEBUFF), 0)) // flag goto cleanup; } if (merge_buffers(param, from_file, to_file, sort_buffer, last_chunk++, Merge_chunk_array(&chunk_array[i], num_chunks - i), 0)) break; /* purecov: inspected */ ... }</code></pre> <p>截取部分 merge_buffers() 的代码如下,</p> <pre> <code class="language-sql">int merge_buffers(Sort_param *param, IO_CACHE *from_file, IO_CACHE *to_file, Sort_buffer sort_buffer, Merge_chunk *last_chunk, Merge_chunk_array chunk_array, int flag) { ... current_thd->inc_status_sort_merge_passes(); ... }</code></pre> <p>可以看到:每个 merge_buffers() 都会增加 sort_merge_passes ,也就是说每一次对MERGEBUFF (7)个block归并排序都会让 sort_merge_passes 加一, sort_merge_passes 越多表示排序的数据太多,需要多次merge pass。解决的方案无非就是缩减要排序数据的大小或者增加 sort_buffer_size 。</p> <p>打个小广告,在我们的qmonitor中就有 sort_merge_pass 的性能指标和参数值过大的报警设置。</p> <h2>六、trace结果解释</h2> <p>说明白了三种排序模式和外部排序的方法,我们回过头来看一下trace的结果。</p> <h3>6.1 是否存在磁盘外部排序</h3> <p>"number_of_tmp_files": 0,</p> <p>number_of_tmp_files 表示有多少个分片,如果 number_of_tmp_files 不等于0,表示一个 sort_buffer_size 大小的内存无法保存所有的键值对,也就是说,MySQL在排序中使用到了磁盘来排序。</p> <h3><strong>6.2 是否存在优先队列优化排序</strong></h3> <p>由于我们的这个SQL里面没有对数据进行分页限制,所以 filesort_priority_queue_optimization 并没有启用</p> <pre> <code class="language-sql">"filesort_priority_queue_optimization": { "usable": false, "cause": "not applicable (no LIMIT)" },</code></pre> <p>而正常情况下,使用了Limit会启用优先队列的优化。优先队列类似于FIFO先进先出队列。</p> <p>算法稍微有点改变,以回表排序模式为例。</p> <p>sort_buffer_size 足够大</p> <p>如果Limit限制返回N条数据,并且N条数据比 sort_buffer_size 小,那么MySQL会把sort buffer作为priority queue,在第二步插入priority queue时会按序插入队列;在第三步,队列满了以后,并不会写入外部磁盘文件,而是直接淘汰最尾端的一条数据,直到所有的数据都正常读取完成。</p> <p>算法如下:</p> <ul> <li>根据索引或者全表扫描,按照过滤条件获得需要查询的数据</li> <li>将要排序的列值和row ID组成键值对,按序存入中priority queue中</li> <li>如果priority queue满了,直接淘汰最尾端记录。</li> <li>重复上述步骤,直到所有的行数据都正常读取了完成</li> <li>最后一轮循环,仅将row ID写入到结果文件中</li> <li>根据结果文件中的row ID按序读取用户需要返回的数据。为了进一步优化性能,MySQL会读一批row ID,并将读到的数据按排序字段要求插入缓存区中(内存大小 read_rnd_buffer_size )。</li> </ul> <p>sort_buffer_size 不够大</p> <p>否则,N条数据比 sort_buffer_size 大的情况下,MySQL无法直接利用sort buffer作为priority queue,正常的文件外部排序还是一样的,只是在最后返回结果时,只根据N个row ID将数据返回出来。具体的算法我们就不列举了。</p> <p>这里MySQL到底是否选择priority queue是在sql/filesort.cc的 check_if_pq_applicable() 函数中确定的,具体的代码细节这里就不展开了。</p> <p>另外,我们也没有讨论Limit m,n的情况,如果是Limit m,n, 上面对应的“N个row ID”就是“M+N个row ID”了,MySQL的Limit m,n 其实是取m+n行数据,最后把M条数据丢掉。</p> <p>从上面我们也可以看到 sort_buffer_size 足够大对Limit数据比较小的情况,优化效果是很明显的。</p> <h2><strong>七、MySQL其他相关排序参数</strong></h2> <h3><strong>7.1 max_sort_length</strong></h3> <p>这里需要区别 max_sort_length 和 max_length_for_sort_data 。</p> <p>max_length_for_sort_data 是为了让MySQL选择 < sort_key, rowid > 还是 < sort_key, additional_fields > 的模式。</p> <p>而 max_sort_length 是键值对的大小无法确定时(比如用户要查询的数据包含了 SUBSTRING_INDEX(col1, ‘.’,2) )MySQL会对每个键值对分配 max_sort_length 个字节的内存,这样导致内存空间浪费,磁盘外部排序次数过多。</p> <h3><strong>7.2 innodb_disable_sort_file_cache</strong></h3> <p>innodb_disable_sort_file_cache 设置为ON的话,表示在排序中生成的临时文件不会用到文件系统的缓存,类似于 O_DIRECT 打开文件。</p> <h3><strong>7.3 innodb_sort_buffer_size</strong></h3> <p>这个参数其实跟我们这里讨论的SQL排序没有什么关系。 innodb_sort_buffer_size 设置的是在创建InnoDB索引时,使用到的sort buffer的大小。</p> <p>以前写死为1M,现在开放出来,允许用户自定义设置这个参数了。</p> <h2><strong>八、MySQL排序优化总结</strong></h2> <p>最后整理一下优化MySQL排序的手段</p> <ol> <li>排序和查询的字段尽量少。只查询你用到的字段,不要使用select *;使用Limit查询必要的行数据;</li> <li>要排序或者查询的字段,尽量不要用不确定字符函数,避免MySQL直接分配 max_sort_length ,导致sort buffer空间不足;</li> <li>使用索引来优化或者避免排序;</li> <li>增加 sort_buffer_size 大小,避免磁盘排序;</li> <li>不得不使用original排序算法时,增加 read_rnd_buffer_size ;</li> <li>字段长度定义合适就好(避免过长);</li> <li>tmpdir建议独立存放,放在高速存储设备上。</li> </ol> <p>九、参考文献</p> <ul> <li><a href="/misc/goto?guid=4959719501452137923" rel="nofollow,noindex">https://dev.mysql.com/doc/refman/5.7/en/order-by-optimization.html</a></li> <li><a href="/misc/goto?guid=4959719501549930067" rel="nofollow,noindex">http://coding-geek.com/how-databases-work/</a></li> </ul> <p> </p> <p> </p> <p>来自:http://www.tuicool.com/articles/vYVZnmA</p> <p> </p>
本文由用户 MagHubert 自行上传分享,仅供网友学习交流。所有权归原作者,若您的权利被侵害,请联系管理员。
转载本站原创文章,请注明出处,并保留原始链接、图片水印。
本站是一个以用户分享为主的开源技术平台,欢迎各类分享!