MySQL排序的內部原理是什么

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排序到底會怎么做列。
籠統的來說，它會按照：

1. 依據“Producer like ‘東京熱%’  and prod_time>’2015-12-01’  ”過濾數據，查找需要的數據；

2. 對查找到的數據按照“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，那么對應的外部排序算法如下：

1. 從要排序的900M數據中讀取100MB數據到內存中，并按照傳統的內部排序算法（快速排序）進行排序；

2. 將排序好的數據寫入磁盤；

3. 重復1，2兩步，直到每個100MB chunk大小排序好的數據都被寫入磁盤；

4. 每次讀取排序好的chunk中前10MB（= 100MB / (9 chunks + 1)）數據，一共9個chunk需要90MB，剩下的10MB作為輸出緩存；

5. 對這些數據進行一個“9路歸并”，并將結果寫入輸出緩存。如果輸出緩存滿了，則直接寫入最終排序結果文件并清空輸出緩存；如果9個10MB的輸入緩存空了，從對應的文件再讀10MB的數據，直到讀完整個文件。最終輸出的排序結果文件就是900MB排好序的數據了。

5.1.2 多路外部排序

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

1. 從要排序的50GB數據中讀取100MB數據到內存中，并按照傳統的內部排序算法（快速排序）進行排序；

2. 將排序好的數據寫入磁盤；

3. 重復1，2兩步，直到每個100MB chunk大小排序好的數據都被寫入磁盤；

4. 每次取25個分片進行歸并排序，這樣就形成了20個（500/25=20）更大的2.5GB有序的文件；

5. 對這20個2.5GB的有序文件進行歸并排序，形成最終排序結果文件。

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

5.2 MySQL外部排序

5.2.1 MySQL外部排序算法

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

1. 根據索引或者全表掃描，按照過濾條件獲得需要查詢的數據；

2. 將要排序的列值和row ID組成鍵值對，存入sort buffer中；

3. 如果sort buffer內存大于這些鍵值對的內存，就不需要創建臨時文件了。否則，每次sort buffer填滿以后，需要直接用qsort(快速排序模式)在內存中排好序，作為一個block寫到臨時文件中。跟正常的外部排序寫到多個文件中不一樣，MySQL只會寫到一個臨時文件中，并通過保存文件偏移量的方式來模擬多個文件歸并排序；

4. 重復上述步驟，直到所有的行數據都正常讀取了完成；

5. 每MERGEBUFF (7) 個block抽取一批數據進行排序，歸并排序到另外一個臨時文件中，直到所有的數據都排序好到新的臨時文件中；

6. 重復以上歸并排序過程，直到剩下不到MERGEBUFF2 (15)個block。
   通俗一點解釋：
   第一次循環中，一個block對應一個sort buffer（大小為sort_buffer_size）排序好的數據；每7個做一個歸并。
   第二次循環中，一個block對應MERGEBUFF (7) 個sort buffer的數據，每7個做一個歸并。
   …
   直到所有的block數量小于MERGEBUFF2 (15)。

7. 最后一輪循環，僅將row ID寫入到結果文件中；

8. 根據結果文件中的row ID按序讀取用戶需要返回的數據。為了進一步優化性能，MySQL會讀一批row ID，并將讀到的數據按排序字段要求插入緩存區中(內存大小read_rnd_buffer_size)。

這里我們需要注意的是：

1. MySQL把外部排序好的分片寫入同一個文件中，通過保存文件偏移量的方式來區別各個分片位置；

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

算法如下：

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打開文件。

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。