【深度長文】MySQL排序内部原理探秘（3）

5.2.2 sort_merge_passes

MySQL手冊中對Sort_merge_passes的描述隻有一句話

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.
      

這段話并沒有把sort_merge_passes到底是什麼，該值比較大時說明了什麼，通過什麼方式可以緩解這個問題。

我們把上面MySQL的外部排序算法搞清楚了，這個問題就清楚了。

其實sort_merge_passes對應的就是MySQL做歸并排序的次數，也就是說，如果sort_merge_passes值比較大，說明sort_buffer和要排序的資料差距越大，我們可以通過增大sort_buffer_size或者讓填入sort_buffer_size的鍵值對更小來緩解sort_merge_passes歸并排序的次數。

對應的，我們可以在源碼中看到證據。

上述MySQL外部排序的算法中第5到第7步，是通過sql/filesort.cc檔案中merge_many_buff()函數來實作，第5步單次歸并使用merge_buffers()實作，源碼摘錄如下：

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 */
...
}      

截取部分merge_buffers()的代碼如下，

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();
...
}      

可以看到：每個merge_buffers()都會增加sort_merge_passes，也就是說每一次對MERGEBUFF (7) 個block歸并排序都會讓sort_merge_passes加一，sort_merge_passes越多表示排序的資料太多，需要多次merge pass。解決的方案無非就是縮減要排序資料的大小或者增加sort_buffer_size。

打個小廣告，在我們的qmonitor中就有sort_merge_pass的性能名額和參數值過大的報警設定。

六、trace 結果解釋

說明白了三種排序模式和外部排序的方法，我們回過頭來看一下trace的結果。

6.1 是否存在磁盤外部排序

"number_of_tmp_files": 0,      

number_of_tmp_files表示有多少個分片，如果number_of_tmp_files不等于0，表示一個sort_buffer_size大小的記憶體無法儲存所有的鍵值對，也就是說，MySQL在排序中使用到了磁盤來排序。

6.2 是否存在優先隊列優化排序

由于我們的這個SQL裡面沒有對資料進行分頁限制，是以filesort_priority_queue_optimization并沒有啟用

"filesort_priority_queue_optimization": {
              "usable": false,
              "cause": "not applicable (no LIMIT)"
            },      

而正常情況下，使用了Limit會啟用優先隊列的優化。優先隊列類似于FIFO先進先出隊列。

算法稍微有點改變，以回表排序模式為例。

• sort_buffer_size足夠大

如果LIMIT 限制傳回N條資料，并且N條資料比sort_buffer_size小，那麼MySQL會把sort buffer作為priority queue，在第二步插入priority queue時會按序插入隊列；在第三步，隊列滿了以後，并不會寫入外部磁盤檔案，而是直接淘汰最尾端的一條資料，直到所有的資料都正常讀取完成。

算法如下：

1. 根據索引或者全表掃描，按照過濾條件獲得需要查詢的資料
2. 将要排序的列值和row ID組成鍵值對，按序存入中priority queue中
3. 如果priority queue滿了，直接淘汰最尾端記錄。
4. 重複上述步驟，直到所有的行資料都正常讀取了完成
5. 最後一輪循環，僅将row ID寫入到結果檔案中
6. 根據結果檔案中的row ID按序讀取使用者需要傳回的資料。為了進一步優化性能，MySQL會讀一批row ID，并将讀到的資料按排序字段要求插入緩存區中(記憶體大小read_rnd_buffer_size)。

• sort_buffer_size不夠大

N條資料比sort_buffer_size大的情況下，MySQL無法直接利用sort buffer作為priority queue，正常的檔案外部排序還是一樣的，隻是在最後傳回結果時，隻根據N個row ID将資料傳回出來。具體的算法我們就不列舉了。

這裡MySQL到底是否選擇priority queue是在sql/filesort.cc的check_if_pq_applicable()函數中确定的，具體的代碼細節這裡就不展開了。

另外，我們也沒有讨論limit m,n的情況，如果是Limit m,n， 上面對應的“N個row ID”就是“M+N個row ID”了，MySQL的limit m,n 其實是取m+n行資料，最後把M條資料丢掉。

從上面我們也可以看到sort_buffer_size足夠大對limit資料比較小的情況，優化效果是很明顯的。

七、MySQL其他相關排序參數

7.1 max_sort_length

這裡需要差別max_sort_length 和max_length_for_sort_data。

max_length_for_sort_data是為了讓MySQL選擇”< sort_key, rowid >”還是”< sort_key, additional_fields >”的模式。

而max_sort_length是鍵值對的大小無法确定時（比如使用者要查詢的資料包含了 SUBSTRING_INDEX(col1, ‘.’,2)）MySQL會對每個鍵值對配置設定max_sort_length個位元組的記憶體，這樣導緻記憶體空間浪費，磁盤外部排序次數過多。

7.2 innodb_disable_sort_file_cache

innodb_disable_sort_file_cache設定為ON的話，表示在排序中生成的臨時檔案不會用到檔案系統的緩存，類似于O_DIRECT打開檔案。

7.3 innodb_sort_buffer_size

這個參數其實跟我們這裡讨論的SQL排序沒有什麼關系。innodb_sort_buffer_size設定的是在建立InnoDB 索引時，使用到的sort buffer的大小。

以前寫死為1M，現在開放出來，允許使用者自定義設定這個參數了。

八、MySQL排序優化總結

最後整理一下優化MySQL排序的手段

1. 排序和查詢的字段盡量少。隻查詢你用到的字段，不要使用select * ；使用limit查詢必要的行資料；
2. 要排序或者查詢的字段，盡量不要用不确定字元函數，避免MySQL直接配置設定max_sort_length，導緻sort buffer空間不足；
3. 使用索引來優化或者避免排序；
4. 增加sort_buffer_size大小，避免磁盤排序；
5. 不得不使用original 排序算法時，增加read_rnd_buffer_size；
6. 字段長度定義合适就好（避免過長）；
7. tmpdir建議獨立存放，放在高速儲存設備上。

寫到這裡，大家可以回顧一下文章開頭的那八個問題，如果回答不了這些問題，說明其實你沒有真正的了解透MySQL的排序，或者說我們的這篇文章寫的太亂了~

九、參考文獻

https://dev.mysql.com/doc/refman/5.7/en/order-by-optimization.html

http://coding-geek.com/how-databases-work/