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(quickcsort,快速排序算法)在記憶體中排好序，并寫到臨時檔案中；
- 重複上述步驟，直到所有的行資料都正常讀取了完成；
- 用到了臨時檔案的，需要利用磁盤外部排序，将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資料到記憶體中，并按照傳統的内部排序算法（快速排序）進行排序；
- 每次取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)時，做最後一次歸并。這兩個值都寫死在代碼中了…