MySQL排序內部原理探秘

MagHubert 8年前發布 | 30K 次閱讀 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 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;

從以上例子里面我們也可以看到，如果要讓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個字符內存空間（用于保存”yes”這三個字符）就夠了，內存空間整整壓縮了50多倍,可以讓更多的鍵值對保存在sort buffer中。

4.2.4 三種模式比較

第二種模式是第一種模式的改進，避免了二次回表，采用的是用空間換時間的方法。

但是由于sort buffer就那么大，如果用戶要查詢的數據非常大的話，很多時間浪費在多次磁盤外部排序，導致更多的IO操作，效率可能還不如第一種方式。

所以，MySQL給用戶提供了一個 max_length_for_sort_data 的參數。當“排序的鍵值對大小” > max_length_for_sort_data 時，MySQL認為磁盤外部排序的IO效率不如回表的效率，會選擇第一種排序模式；反之，會選擇第二種不回表的模式。

第三種模式主要是解決變長字符數據存儲空間浪費的問題，對于實際數據不多，字段定義較長的改進效果會更加明顯。

很多文章寫到這里可能就差不多了，但是大家忘記關注一個問題了：“如果排序的數據不能完全放在sort buffer內存里面，是怎么通過外部排序完成整個排序過程的呢？”

要解決這個問題，我們首先需要簡單查看一下外部排序到底是怎么做的。

五、外部排序

5.1 普通外部排序

5.1.1 兩路外部排序

我們先來看一下最簡單，最普遍的兩路外部排序算法。

假設內存只有100M，但是排序的數據有900M，那么對應的外部排序算法如下：

從要排序的900M數據中讀取100MB數據到內存中，并按照傳統的內部排序算法（快速排序）進行排序；
將排序好的數據寫入磁盤；
重復1，2兩步，直到每個100MB chunk大小排序好的數據都被寫入磁盤；
每次讀取排序好的chunk中前10MB（= 100MB / (9 chunks + 1)）數據，一共9個chunk需要90MB，剩下的10MB作為輸出緩存；
對這些數據進行一個“9路歸并”，并將結果寫入輸出緩存。如果輸出緩存滿了，則直接寫入最終排序結果文件并清空輸出緩存；如果9個10MB的輸入緩存空了，從對應的文件再讀10MB的數據，直到讀完整個文件。最終輸出的排序結果文件就是900MB排好序的數據了。

5.1.2 多路外部排序

上述排序算法是一個兩路排序算法（先排序，后歸并）。但是這種算法有一個問題，假設要排序的數據是50GB而內存只有100MB，那么每次從500個排序好的分片中取200KB（100MB / 501 約等于200KB）就是很多個隨機IO。效率非常慢，對應可以這樣來改進：

從要排序的50GB數據中讀取100MB數據到內存中，并按照傳統的內部排序算法（快速排序）進行排序；
將排序好的數據寫入磁盤；
重復1，2兩步，直到每個100MB chunk大小排序好的數據都被寫入磁盤；
每次取25個分片進行歸并排序，這樣就形成了20個（500/25=20）更大的2.5GB有序的文件；
對這20個2.5GB的有序文件進行歸并排序，形成最終排序結果文件。

對應的數據量更大的情況可以進行更多次歸并。

5.2 MySQL外部排序

5.2.1 MySQL外部排序算法

那MySQL使用的外部排序是怎么樣的列，我們以回表排序模式為例：

根據索引或者全表掃描，按照過濾條件獲得需要查詢的數據；
將要排序的列值和row ID組成鍵值對，存入sort buffer中；
如果sort buffer內存大于這些鍵值對的內存，就不需要創建臨時文件了。否則，每次sort buffer填滿以后，需要直接用qsort(快速排序模式)在內存中排好序，作為一個block寫到臨時文件中。跟正常的外部排序寫到多個文件中不一樣，MySQL只會寫到一個臨時文件中，并通過保存文件偏移量的方式來模擬多個文件歸并排序；
重復上述步驟，直到所有的行數據都正常讀取了完成；
每MERGEBUFF (7) 個block抽取一批數據進行排序，歸并排序到另外一個臨時文件中，直到所有的數據都排序好到新的臨時文件中；
重復以上歸并排序過程，直到剩下不到MERGEBUFF2 (15)個block。

通俗一點解釋：

第一次循環中，一個block對應一個sort buffer（大小為 sort_buffer_size ）排序好的數據；每7個做一個歸并。

第二次循環中，一個block對應MERGEBUFF (7) 個sort buffer的數據，每7個做一個歸并。

…

直到所有的block數量小于MERGEBUFF2 (15)。
最后一輪循環，僅將row ID寫入到結果文件中；
根據結果文件中的row ID按序讀取用戶需要返回的數據。為了進一步優化性能，MySQL會讀一批row ID，并將讀到的數據按排序字段要求插入緩存區中(內存大小 read_rnd_buffer_size )。

這里我們需要注意的是：

MySQL把外部排序好的分片寫入同一個文件中，通過保存文件偏移量的方式來區別各個分片位置；
MySQL每MERGEBUFF (7)個分片做一個歸并，最終分片數達到MERGEBUFF2 (15)時，做最后一次歸并。這兩個值都寫死在代碼中了……

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時會按序插入隊列；在第三步，隊列滿了以后，并不會寫入外部磁盤文件，而是直接淘汰最尾端的一條數據，直到所有的數據都正常讀取完成。

算法如下：

根據索引或者全表掃描，按照過濾條件獲得需要查詢的數據
將要排序的列值和row ID組成鍵值對，按序存入中priority queue中
如果priority queue滿了，直接淘汰最尾端記錄。
重復上述步驟，直到所有的行數據都正常讀取了完成
最后一輪循環，僅將row ID寫入到結果文件中
根據結果文件中的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排序的手段

排序和查詢的字段盡量少。只查詢你用到的字段，不要使用select *；使用Limit查詢必要的行數據；
要排序或者查詢的字段，盡量不要用不確定字符函數，避免MySQL直接分配 max_sort_length ，導致sort buffer空間不足；
使用索引來優化或者避免排序；
增加 sort_buffer_size 大小，避免磁盤排序；
不得不使用original排序算法時，增加 read_rnd_buffer_size ；
字段長度定義合適就好（避免過長）；
tmpdir建議獨立存放，放在高速存儲設備上。

九、參考文獻

來自：http://www.tuicool.com/articles/vYVZnmA

本文由用戶 MagHubert 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1475910384210.html

MySQL 排序算法數據庫服務器

MySQL排序內部原理探秘

一、我們要解決什么問題

二、排序，排序，排序

三、索引優化排序

四、排序模式

4.1 實際trace結果

4.2 排序模式概覽

五、外部排序

5.1 普通外部排序

5.2 MySQL外部排序

六、trace結果解釋

6.1 是否存在磁盤外部排序

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

七、MySQL其他相關排序參數

7.1 max_sort_length

7.2 innodb_disable_sort_file_cache

7.3 innodb_sort_buffer_size

八、MySQL排序優化總結

相關經驗

相關資訊

相關文檔

目錄