MySQL排序的內(nèi)部原理是什么

MySQL排序的內(nèi)部原理是什么，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

排序，排序，排序

我們通過explain查看MySQL執(zhí)行計劃的時候，經(jīng)常會看到在Extra列中顯示Using filesort。
其實這種情況就說明MySQL就使用了排序。
Using filesort經(jīng)常出現(xiàn)在order by、group by、distinct、join等情況下。

三、索引優(yōu)化排序

看到排序，我們的DBA首先想到的肯定是，是否可以利用索引來優(yōu)化。
INNODB默認(rèn)采用的是B tree索引，B tree索引本身就是有序的，如果有一個查詢?nèi)缦?/p>

select * from film where actor_name='蒼老師' order by prod_time;

那么只需要加一個(actor_name,prod_time)的索引就能夠利用B tree的特性來避免額外排序。
如下圖所示：

通過B-tree查找到actor_name=’蒼老師’演員為蒼老師的數(shù)據(jù)以后，只需要按序往右查找就可以了，不需要額外排序操作

對應(yīng)的哪些可以利用索引優(yōu)化排序的列舉如下：

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使用索引優(yōu)化排序應(yīng)該怎么建組合索引。

四、排序模式

4.1 實際trace結(jié)果

但是還是有非常多的SQL沒法使用索引進(jìn)行排序，例如

select * from film where Producer like '東京熱%'  and prod_time>'2015-12-01' order by actor_age;

我們想查詢’東京熱’出品的，從去年12月1號以來，并且按照演員的年齡排序的電影信息。
（好吧，假設(shè)我這里有一個每一位男DBA都想維護(hù)的數(shù)據(jù)庫:）

這種情況下，使用索引已經(jīng)無法避免排序了，那MySQL排序到底會怎么做列。
籠統(tǒng)的來說，它會按照：

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

2. 對查找到的數(shù)據(jù)按照“order by actor_age”進(jìn)行排序,并 按照“select *”將必要的數(shù)據(jù)按照actor_age依序返回給客戶端。

空口無憑，我們可以利用MySQL的optimize trace來查看是否如上所述。
如果通過optimize trace看到更詳細(xì)的MySQL優(yōu)化器trace信息，可以查看阿里印風(fēng)的博客初識5.6的optimizer trace
trace結(jié)果如下：

• 依據(jù)“Producer like ‘東京熱%’  and prod_time>’2015-12-01’  ”過濾數(shù)據(jù)，查找需要的數(shù)據(jù)

            "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'))"
                }
              ]
            }

• 對查找到的數(shù)據(jù)按照“order by actor_age”進(jìn)行排序,并 按照“select *”將必要的數(shù)據(jù)按照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在執(zhí)行這個select的時候執(zhí)行了針對film表.actor_age字段的asc排序操作。

"filesort_information": [
              {
                "direction": "asc",
                "table": "`film`",
                "field": "actor_age"
              }

4.2 排序模式概覽

我們這里主要關(guān)心MySQL到底是怎么排序的，采用了什么排序算法。

請關(guān)注這里

"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排序文章的同學(xué)應(yīng)該比較清楚，“< sort_key, packed_additional_fields >” 相對較新。

• < sort_key, rowid >對應(yīng)的是MySQL 4.1之前的“原始排序模式”

• < sort_key, additional_fields >對應(yīng)的是MySQL 4.1以后引入的“修改后排序模式”

• < sort_key, packed_additional_fields >是MySQL 5.7.3以后引入的進(jìn)一步優(yōu)化的"打包數(shù)據(jù)排序模式”

下面我們來一一介紹這三個模式：

4.2.1  回表排序模式

• 根據(jù)索引或者全表掃描，按照過濾條件獲得需要查詢的排序字段值和row ID；

• 將要排序字段值和row ID組成鍵值對，存入sort buffer中；

• 如果sort buffer內(nèi)存大于這些鍵值對的內(nèi)存，就不需要創(chuàng)建臨時文件了。否則，每次sort buffer填滿以后，需要直接用qsort(快速排序算法)在內(nèi)存中排好序，并寫到臨時文件中；

• 重復(fù)上述步驟，直到所有的行數(shù)據(jù)都正常讀取了完成；

• 用到了臨時文件的，需要利用磁盤外部排序，將row id寫入到結(jié)果文件中；

• 根據(jù)結(jié)果文件中的row ID按序讀取用戶需要返回的數(shù)據(jù)。由于row ID不是順序的，導(dǎo)致回表時是隨機(jī)IO，為了進(jìn)一步優(yōu)化性能（變成順序IO），MySQL會讀一批row ID，并將讀到的數(shù)據(jù)按排序字段順序插入緩存區(qū)中(內(nèi)存大小read_rnd_buffer_size)。

4.2.2 不回表排序模式

• 根據(jù)索引或者全表掃描，按照過濾條件獲得需要查詢的數(shù)據(jù)；

• 將要排序的列值和 用戶需要返回的字段 組成鍵值對，存入sort buffer中；

• 如果sort buffer內(nèi)存大于這些鍵值對的內(nèi)存，就不需要創(chuàng)建臨時文件了。否則，每次sort buffer填滿以后，需要直接用qsort(快速排序算法)在內(nèi)存中排好序，并寫到臨時文件中；

• 重復(fù)上述步驟，直到所有的行數(shù)據(jù)都正常讀取了完成；

• 用到了臨時文件的，需要利用磁盤外部排序，將排序后的數(shù)據(jù)寫入到結(jié)果文件中；

• 直接從結(jié)果文件中返回用戶需要的字段數(shù)據(jù)，而不是根據(jù)row ID再次回表查詢。

4.2.3打包數(shù)據(jù)排序模式

第三種排序模式的改進(jìn)僅僅在于將char和varchar字段存到sort buffer中時，更加緊縮。

在之前的兩種模式中，存儲了”yes”3個字符的定義為VARCHAR(255)的列會在內(nèi)存中申請255個字符內(nèi)存空間，但是5.7.3改進(jìn)后，只需要存儲2個字節(jié)的字段長度和3個字符內(nèi)存空間（用于保存”yes”這三個字符）就夠了，內(nèi)存空間整整壓縮了50多倍,可以讓更多的鍵值對保存在sort buffer中。

4.2.4三種模式比較

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

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

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

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

能看到這里的同學(xué)絕逼是真愛，但是還沒完，后面的東西可能會更燒腦…
      建議大家喝杯咖啡再繼續(xù)看。

很多文章寫到這里可能就差不多了，但是大家忘記關(guān)注一個問題了：“如果排序的數(shù)據(jù)不能完全放在sort buffer內(nèi)存里面，是怎么通過外部排序完成整個排序過程的呢？”
要解決這個問題，我們首先需要簡單查看一下外部排序到底是怎么做的。

五、外部排序

5.1 普通外部排序

5.1.1 兩路外部排序

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

假設(shè)內(nèi)存只有100M，但是排序的數(shù)據(jù)有900M，那么對應(yīng)的外部排序算法如下：

1. 從要排序的900M數(shù)據(jù)中讀取100MB數(shù)據(jù)到內(nèi)存中，并按照傳統(tǒng)的內(nèi)部排序算法（快速排序）進(jìn)行排序；

2. 將排序好的數(shù)據(jù)寫入磁盤；

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

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

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

5.1.2 多路外部排序

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

1. 從要排序的50GB數(shù)據(jù)中讀取100MB數(shù)據(jù)到內(nèi)存中，并按照傳統(tǒng)的內(nèi)部排序算法（快速排序）進(jìn)行排序；

2. 將排序好的數(shù)據(jù)寫入磁盤；

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

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

5. 對這20個2.5GB的有序文件進(jìn)行歸并排序，形成最終排序結(jié)果文件。

對應(yīng)的數(shù)據(jù)量更大的情況可以進(jìn)行更多次歸并。

5.2 MySQL外部排序

5.2.1 MySQL外部排序算法

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

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

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

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

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

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

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

7. 最后一輪循環(huán)，僅將row ID寫入到結(jié)果文件中；

8. 根據(jù)結(jié)果文件中的row ID按序讀取用戶需要返回的數(shù)據(jù)。為了進(jìn)一步優(yōu)化性能，MySQL會讀一批row ID，并將讀到的數(shù)據(jù)按排序字段要求插入緩存區(qū)中(內(nèi)存大小read_rnd_buffer_size)。

這里我們需要注意的是：

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

2. MySQL每MERGEBUFF (7)個分片做一個歸并，最終分片數(shù)達(dá)到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對應(yīng)的就是MySQL做歸并排序的次數(shù)，也就是說，如果sort_merge_passes值比較大，說明sort_buffer和要排序的數(shù)據(jù)差距越大，我們可以通過增大sort_buffer_size或者讓填入sort_buffer_size的鍵值對更小來緩解sort_merge_passes歸并排序的次數(shù)。

對應(yīng)的，我們可以在源碼中看到證據(jù)。
上述MySQL外部排序的算法中第5到第7步，是通過sql/filesort.cc文件中merge_many_buff()函數(shù)來實現(xiàn)，第5步單次歸并使用merge_buffers()實現(xiàn)，源碼摘錄如下：

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越多表示排序的數(shù)據(jù)太多，需要多次merge pass。解決的方案無非就是縮減要排序數(shù)據(jù)的大小或者增加sort_buffer_size。

打個小廣告，在我們的qmonitor中就有sort_merge_pass的性能指標(biāo)和參數(shù)值過大的報警設(shè)置。

六、trace 結(jié)果解釋

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

6.1 是否存在磁盤外部排序

"number_of_tmp_files": 0,

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

6.2 是否存在優(yōu)先隊列優(yōu)化排序

由于我們的這個SQL里面沒有對數(shù)據(jù)進(jìn)行分頁限制，所以filesort_priority_queue_optimization并沒有啟用

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

而正常情況下，使用了Limit會啟用優(yōu)先隊列的優(yōu)化。優(yōu)先隊列類似于FIFO先進(jìn)先出隊列。

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

• sort_buffer_size足夠大

如果Limit 限制返回N條數(shù)據(jù)，并且N條數(shù)據(jù)比sort_buffer_size小，那么MySQL會把sort buffer作為priority queue，在第二步插入priority queue時會按序插入隊列；在第三步，隊列滿了以后，并不會寫入外部磁盤文件，而是直接淘汰最尾端的一條數(shù)據(jù)，直到所有的數(shù)據(jù)都正常讀取完成。

算法如下：

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

2. 將要排序的列值和row ID組成鍵值對，按序存入中priority queue中

3. 如果priority queue滿了，直接淘汰最尾端記錄。

4. 重復(fù)上述步驟，直到所有的行數(shù)據(jù)都正常讀取了完成

5. 最后一輪循環(huán)，僅將row ID寫入到結(jié)果文件中

6. 根據(jù)結(jié)果文件中的row ID按序讀取用戶需要返回的數(shù)據(jù)。為了進(jìn)一步優(yōu)化性能，MySQL會讀一批row ID，并將讀到的數(shù)據(jù)按排序字段要求插入緩存區(qū)中(內(nèi)存大小read_rnd_buffer_size)。

• sort_buffer_size不夠大

否則，N條數(shù)據(jù)比sort_buffer_size大的情況下，MySQL無法直接利用sort buffer作為priority queue，正常的文件外部排序還是一樣的，只是在最后返回結(jié)果時，只根據(jù)N個row ID將數(shù)據(jù)返回出來。具體的算法我們就不列舉了。

這里MySQL到底是否選擇priority queue是在sql/filesort.cc的check_if_pq_applicable()函數(shù)中確定的，具體的代碼細(xì)節(jié)這里就不展開了。

另外，我們也沒有討論limit m,n的情況，如果是Limit m,n， 上面對應(yīng)的“N個row ID”就是“M+N個row ID”了，MySQL的limit m,n 其實是取m+n行數(shù)據(jù)，最后把M條數(shù)據(jù)丟掉。

從上面我們也可以看到sort_buffer_size足夠大對limit數(shù)據(jù)比較小的情況，優(yōu)化效果是很明顯的。

七、MySQL其他相關(guān)排序參數(shù)

7.1 max_sort_length

這里需要區(qū)別max_sort_length 和max_length_for_sort_data。

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

而max_sort_length是鍵值對的大小無法確定時（比如用戶要查詢的數(shù)據(jù)包含了 SUBSTRING_INDEX(col1, ‘.’,2)）MySQL會對每個鍵值對分配max_sort_length個字節(jié)的內(nèi)存，這樣導(dǎo)致內(nèi)存空間浪費(fèi)，磁盤外部排序次數(shù)過多。

7.2 innodb_disable_sort_file_cache

innodb_disable_sort_file_cache設(shè)置為ON的話，表示在排序中生成的臨時文件不會用到文件系統(tǒng)的緩存，類似于O_DIRECT打開文件。

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