我們?nèi)粘９ぷ髦袑?SQL 語句，經(jīng)常會使用 order by 對記錄進行排序。如果 order by 能夠使用索引中記錄已經(jīng)排好序的特性，就不需要再借助內(nèi)存或磁盤空間進行排序，這無疑是效率最高的。然而，還是有各種情況導致 order by 不能夠使用索引，而是要進行額外的排序操作。MySQL 把需要借助內(nèi)存或磁盤空間進行的排序操作統(tǒng)稱為文件排序，而沒有在概念上進一步分為文件排序和內(nèi)存排序。

本文講述的文件排序邏輯基于 MySQL 5.7.35 源碼。

內(nèi)容目錄

1. 整體概覽

為了更好的把握 MySQL 文件排序的全局，我們先拋開細節(jié)，來看看它的實現(xiàn)過程示意圖：

結合上面的示意圖，我們來描述一下大體的實現(xiàn)過程：

• server 層從存儲引擎讀取符合 where 條件的記錄，寫入一個專門存放待排序記錄的內(nèi)存區(qū)域，這個內(nèi)存區(qū)域叫做排序緩沖區(qū)（sort buffer）。
• 排序緩沖區(qū)寫滿之后，會對緩沖區(qū)中的記錄進行排序，排好序的記錄組成一個數(shù)據(jù)塊，數(shù)據(jù)塊包含 Merge_chunk 和數(shù)據(jù)記錄兩部分，Merge_chunk 寫入一個磁盤文件（chunk_file），數(shù)據(jù)記錄寫入另一個磁盤文件（temp_file）。Merge_chunk 中保存著數(shù)據(jù)記錄在磁盤文件（temp_file）中的起始位置、記錄數(shù)量等信息。
• Merge_chunk 和數(shù)據(jù)記錄寫入磁盤文件之后，排序緩沖區(qū)中的數(shù)據(jù)被清空，然后就可以寫入其它待排序記錄了，再次寫滿之后，緩沖區(qū)中的記錄同樣會進行排序，組成一個數(shù)據(jù)塊，并把 Merge_chunk 和數(shù)據(jù)記錄分別寫入磁盤文件 chunk_file 和 temp_file。
• 讀完符合 where 條件的所有記錄之后，可能會生成多個數(shù)據(jù)塊，對數(shù)據(jù)塊進行 7 路歸并排序，把 7 個小數(shù)據(jù)塊合并成大數(shù)據(jù)塊，直到合并得到的大數(shù)據(jù)塊數(shù)量小于等于 15 個（如果歸并排序之前，數(shù)據(jù)塊數(shù)量本身就小于等于 15 個，此步驟跳過）。
• 最后，通過多路歸并排序把小于等于 15 個數(shù)據(jù)塊合并為最終的排序結果，寫入磁盤文件（out_file）。

以上就是 MySQL 文件排序?qū)崿F(xiàn)過程的整體概覽，有了這個基礎，我們就能夠進一步展開其中的細節(jié)了。

2. 排序緩沖區(qū)（sort buffer）

排序緩沖區(qū)是內(nèi)存緩沖區(qū)，用于存放待排序記錄。對于服務器來說，內(nèi)存是稀缺資源，既然排序緩沖區(qū)在內(nèi)存中，其大小必然要受到限制，系統(tǒng)變量 sort_buffer_size 就是用于控制排序緩沖區(qū)大小的。

sort_buffer_size 默認值為 256K，最小可以設置為 32K，最大可以設置為 4G。

3. 單個排序字段太長了怎么辦？

order by 子句中，可能會包含一個或多個排序字段，排序字段可以是 int、char、varchar、blob 等各種類型，假設有個字段是這么定義的：a varchar(21845)，utf8 字符集下，字段內(nèi)容最大可以達到 65535 字節(jié)，將近 64K。

排序緩沖區(qū)的默認大小為 256K，如果以這樣一個字段作為排序字段，就算每條記錄只把這一個字段寫入到排序緩沖區(qū)，寫入 4 條記錄緩沖區(qū)就滿了，在記錄數(shù)量很多情況下，就意味著大量的數(shù)據(jù)塊要寫入到磁盤文件，而大量的磁盤 IO 會導致整個排序過程耗時增加，由此可見，排序內(nèi)容長度也必須受到限制。

max_sort_length 就是用于控制單個字段排序內(nèi)容長度的，默認值為 1024 字節(jié)，最小可以設置為 4 字節(jié)，最大可以設置為 8M。

如果單個排序字段內(nèi)容長度大于 max_sort_length，只有前 max_sort_length 字節(jié)的內(nèi)容會參與排序，以 max_sort_length = 1024 字節(jié)為例，對于單個排序字段內(nèi)容長度超過 1024 字節(jié)的多條記錄，如果前 1024 字節(jié)的內(nèi)容相同，1025 字節(jié)及之后的內(nèi)容不相同，會導致 MySQL 認為記錄的排序字段內(nèi)容一樣，從而出現(xiàn)排序結果和預期不一致的情況。

4. 排序模式（sort mode）

排序模式是官方的叫法，實際上就是排序緩沖區(qū)或磁盤文件中會寫入哪些內(nèi)容。排序模式一共有 3 種：

這 3 種排序模式的共同點，都會把排序字段（sort_key）寫入排序緩沖區(qū)或磁盤文件，排序字段可能是一個，也可能是多個。

4.1

表示排序緩沖區(qū)或磁盤文件中，除了要寫入排序字段（sort_key），還要寫入存儲引擎返回給 server 層的所有字段（additional_fields）：

additional_fields 沒有描述為 select 子句中的所有字段，而是用了更長的描述存儲引擎返回給 server 層的所有字段，是因為兩者并不完全一樣，本文后面出現(xiàn)相關的場景時，也都使用后者來描述。

上圖是寫入到排序緩沖區(qū)中記錄的示意圖，以下對各個部分進行說明：

• 排序字段（sort_key）：排序字段內(nèi)容，會進行編碼以節(jié)省存儲空間，可能包含一個或多個排序字段。
• 字段 NULL 標記區(qū)域：創(chuàng)建表時，沒有指定 NOT NULL 的字段，在這個區(qū)域會有 1 bit 用于標記記錄中該字段內(nèi)容是否為 NULL。
• char 長度：char 字段長度，占用 1 字節(jié)或 2 字節(jié)。 排序模式中，為了節(jié)省空間，只寫入 char 字段實際內(nèi)容到排序緩沖區(qū)，所以需要記錄字段內(nèi)容長度。為了邏輯統(tǒng)一， 排序模式中也會寫入 char 字段長度和內(nèi)容到排序緩沖區(qū)。
• char 內(nèi)容：char 字段內(nèi)容，以最大長度存儲，不會去掉內(nèi)容尾部的空格。
• varchar 長度：varchar 字段內(nèi)容長度，占用 1 字節(jié)或 2 字節(jié)。
• varchar 內(nèi)容：varchar 字段內(nèi)容，占用空間為字段最大長度。如果字段實際內(nèi)容長度小于定義的最大長度，剩余空間留空。
• 除 blob 類型之外的其它字段：指是的除 tinyblob、mediumblob、blob、longblob、tinytext、mediumtext、text、longtext、json、geometry 之外的其它類型字段，只需要把字段內(nèi)容寫入排序緩沖區(qū)，不需要寫入字段長度。tinyblob、mediumblob、blob、longblob、tinytext、mediumtext、text、longtext、json、geometry 都是基于 blob 類型實現(xiàn)的，而 select 子句中包含 blob 類型字段時，不能使用 、 排序模式。
• 重點說明： 如果某個字段內(nèi)容為 NULL，該字段在字段 NULL 標記區(qū)域?qū)?NULL 標記位設置為 1，同時，該字段在排序緩沖區(qū)中還會占用存儲空間，占用空間大小為字段最大長度。

排序模式的好處，只需要從存儲引擎讀取一次數(shù)據(jù)，排序緩沖區(qū)或排序結果的最終文件（out_file）存放的就是已經(jīng)排好序的所有記錄，讀取其中需要的字段返回給客戶端就可以了，這是以空間換時間的方式。

如果排序緩沖區(qū)不夠存儲符合 where 條件的所有待排序記錄，就需要把緩沖區(qū)中的記錄排好序之后寫入磁盤文件，雖然磁盤相比內(nèi)存來說，空間可以大很多，但是磁盤 IO 相比內(nèi)存訪問效率低下。 排序模式雖然實現(xiàn)起來簡單方便，但也會導致排序緩沖區(qū)只能存放更少的待排序記錄、需要更多的磁盤 IO、占用更多的磁盤空間，所以，其使用會有所限制。

使用 需要滿足以下條件：

• 存儲引擎返回給 server 層的字段中不能包含 blob 類型字段，因為 blob 字段一般都是用于存儲比較長的內(nèi)容。
• 排序字段（sort_key）長度之和 + additional_fields 所有字段最大長度之和必須小于等于系統(tǒng)變量 max_length_for_sort_data 的值。

如果不滿足上面兩個條件，會使用 排序模式，后面會講述這種模式。

max_length_for_sort_data 默認值為 1024 字節(jié)，最小可設置為 4 字節(jié)，最大可設置為 8M。

的優(yōu)點是簡單方便，它也有缺點，additional_fields 所有字段在排序緩沖區(qū)或磁盤文件中都是按照字段最大占用字節(jié)數(shù)來分配空間的，在以下兩種場景中會存在空間浪費：

• 字段內(nèi)容為 NULL，以 utf8 字符集的 varchar 字段為例，假設有字段 a varchar(21845)，當字段 a 的內(nèi)容為 NULL 時，它在排序緩沖區(qū)或磁盤文件中占用的空間也是 21845 * 3 = 65535 字節(jié)，對于 int、float 等其它字段也一樣，都存在空間浪費。
• char、varchar 類型字段，字段內(nèi)容實際占用空間小于最大長度，還是以上面的字段 a 為例，如果字段內(nèi)容為文件排序是怎么實現(xiàn)的，只需要 10（字符數(shù)）* 3 = 30 字節(jié) 就能夠存放，但實際占用空間依然是 65535 字節(jié)。

為了解決這種排序模式浪費空間的問題，引入了另一種排序模式 。

4.2

表示排序緩沖區(qū)或磁盤文件中，除了要存入排序字段（sort_key），還要存入存儲引擎返回給 server 層的所有字段（packed_additional_fields），并且會盡可能使用最少的空間存放待排序記錄。

字段內(nèi)容為 NULL 時，除 1 bit 的 NULL 標記位之外，字段在排序緩沖區(qū)不占用額外存儲空間；char、varchar 類型字段內(nèi)容長度小于字段最大長度時，字段在排序緩沖區(qū)中只占用實際內(nèi)容長度大小的空間，不會像 排序模式一樣每個字段都占用字段最大長度大小的空間。

上圖是寫入到排序緩沖區(qū)中記錄的示意圖，以下對各個部分進行說明：

• 排序字段（sort_key）：排序字段內(nèi)容，會進行編碼以節(jié)省存儲空間，可能包含一個或多個排序字段。
• 記錄長度：存儲排序緩沖區(qū)的記錄中，除排序字段（sort_key）之外的長度，也就是記錄長度 ~ 除 blob 類型之外的其它字段的長度。
• 字段 NULL 標記區(qū)域：創(chuàng)建表時，沒有指定 NOT NULL 的字段，在這個區(qū)域會有 1 bit 用于存儲記錄中該字段內(nèi)容是否為 NULL。
• char 長度：char 字段長度，占用 1 字節(jié)或 2 字節(jié)。為了節(jié)省空間，只寫入 char 字段實際內(nèi)容到排序緩沖區(qū)，所以需要記錄字段內(nèi)容長度。
• char 內(nèi)容：char 字段實際內(nèi)容，以實際長度存儲，會去掉內(nèi)容尾部的空格。
• varchar 長度：varchar 字段內(nèi)容長度，占用 1 字節(jié)或 2 字節(jié)。
• varchar 內(nèi)容：varchar 字段實際內(nèi)容。
• 除 blob 類型之外的其它字段：指是的除 tinyblob、mediumblob、blob、longblob、tinytext、mediumtext、text、longtext、json、geometry 之外的其它類型，只需要把字段內(nèi)容寫入排序緩沖區(qū)，不需要寫入字段長度。
• 重點說明： 如果某個字段內(nèi)容為 NULL，該字段在字段 NULL 標記區(qū)域?qū)?NULL 標記位設置為 1，字段不會占用排序緩沖區(qū)的額外空間。

是以 為基礎的，如果不滿足使用 的條件，也不會使用 。

使用 排序模式，還需要滿足以下條件：

• packed_additional_fields 所有字段最大長度之和必須小于等于 65535 字節(jié)。為什么是 65535 字節(jié)？因為只寫入字段實際內(nèi)容到排序緩沖區(qū)或磁盤文件，不同記錄長度可能會不一樣，這就需要把每條記錄的長度記下來，MySQL 用 2 個字節(jié)來保存記錄長度，而 2 字節(jié)無符號整數(shù)能夠表示的最大數(shù)字為 65535。
• 寫入排序緩沖區(qū)或磁盤文件的一條記錄長度必須小于等于系統(tǒng)變量 max_length_for_sort_data 的值，記錄長度 = 排序字段（sort_key）長度之和 + 存儲記錄長度的 2 字節(jié) + packed_additional_fields 所有字段最大長度之和。
• 可壓縮字段最大長度之和必須大于 12 字節(jié)，如果可節(jié)省的空間太小，也就沒必要折騰了。

前面我們講述了 、 的優(yōu)缺點及使用限制，如果這兩種排序模式都不能使用怎么辦？

別急，該輪到 排序模式出場了，MySQL 剛出道時采用的就是這種排序模式。

4.3

表示排序緩沖區(qū)或磁盤文件中，除了要存入排序字段（sort_key），還要存入記錄的主鍵 ID（rowid）。

上圖是寫入到排序緩沖區(qū)中記錄的示意圖，相比其它兩種排序模式來說，非常簡單，不做過多說明了。

想必大家應該發(fā)現(xiàn)了 和 、 的區(qū)別了，使用 時，排序緩沖區(qū)或磁盤文件中只包含了記錄的主鍵 ID，而客戶端可能需要除主鍵之外的字段，怎么辦？

這就要二次訪問存儲引擎了，第一次從存儲引擎拿到符合 where 條件的所有記錄的主鍵 ID，第二次根據(jù)主鍵 ID 從存儲引擎一條一條讀取記錄，得到客戶端需要的所有字段。

使用 讀取數(shù)據(jù)的過程，有點類似根據(jù) ID 批量從 redis 獲取詳細數(shù)據(jù)的過程，先從某個 redis key 讀取多個 ID，然后根據(jù) ID 讀取緩存的詳細數(shù)據(jù)。

這種排序模式的好處是記錄數(shù)量不太多的情況下，使用排序緩沖區(qū)就能夠存儲所有待排序記錄了，能夠在一定程度上避免使用磁盤文件排序。

舉例說明：假設排序字段為 int 類型，主鍵也為 int 類型，寫入排序緩沖區(qū)的一條記錄占用的空間為 4 + 4 = 8 字節(jié)，排序緩沖區(qū)的默認大小為 256K，能夠存放 32768 條記錄，對于一般業(yè)務來說，都不會一次性讀取這么多記錄，由此可見，一般情況下，使用 排序模式不會用到磁盤文件排序。

但是，凡事都有例外，如果一條 SQL 語句讀取過多的記錄，哪怕是使用 ，當排序緩沖區(qū)滿時，也需要把緩沖區(qū)中的記錄排好序組成一個數(shù)據(jù)塊，寫入磁盤文件，這樣一來，即要使用磁盤文件，又要二次訪問存儲引擎，執(zhí)行效率就有點慘不忍睹了。

細心的小伙伴可能發(fā)現(xiàn)了一點情況，到現(xiàn)在為止講的三種排序模式，都是把符合 where 條件的所有記錄寫入排序緩沖區(qū)或磁盤文件，那還有優(yōu)化空間嗎？

MySQL 為了提升性能，想了各種辦法，使用了各種技巧，對于上面提到的這種情況，自然也還可以再優(yōu)化，我們一起來看看吧。

5. 提升排序效率

5.1 優(yōu)先隊列

通過前面的講述，我們已經(jīng)知道了，MySQL 會把符合 where 條件的所有記錄寫入排序緩沖區(qū)，當緩沖區(qū)滿時，緩沖區(qū)中的記錄排好序后組成一個數(shù)據(jù)塊，寫入到磁盤文件（temp_file），而磁盤 IO 相比內(nèi)存訪問效率低下，優(yōu)先隊列就是為了在文件排序過程中避免使用磁盤文件的一種優(yōu)化方案。也就是說，使用了優(yōu)先隊列就不會使用磁盤文件排序。

優(yōu)先隊列在內(nèi)存中維護待排序記錄的隊列，隊列中的元素不會實際存儲記錄內(nèi)容，而是存儲指向排序緩沖區(qū)中記錄的地址，因為要保證不使用磁盤文件，使用優(yōu)先隊列提升排序效率的必要條件是：SQL 語句必須包含 limit。

在滿足必要條件的基礎上，會評估使用優(yōu)先隊列進行排序是否更快，以決定是否使用。

使用優(yōu)先隊列提升排序效率，借鑒的是大頂堆的思路，排序緩沖區(qū)中只需要保留待排序記錄中最大或最小的 limit 條記錄（取決于正序還是倒序排序），而不需要存放所有待排序記錄?；谇懊娴拿枋隹梢灾溃褂脙?yōu)先隊列的優(yōu)勢有兩個：

• 不使用磁盤文件排序，避免磁盤 IO。
• 只需要對一部分待排序記錄中進行排序。

如果排序緩沖區(qū)不能存放所有待排序記錄，就意味著需要借助磁盤文件排序，使用優(yōu)先隊列無疑是更好的選擇，這種情況下，只要排序緩沖區(qū)中能夠存放 limit + 1 條記錄，就會使用優(yōu)先隊列。

limit + 1 中的 1 是優(yōu)先隊列需要使用的額外的一條記錄的空間。

如果排序緩沖區(qū)能夠存放所有待排序記錄，本身就不需要使用磁盤文件進行排序，使用優(yōu)先隊列的優(yōu)勢就剩下一個了：只需要對一部分待排序記錄中進行排序。官方根據(jù)單元測試發(fā)現(xiàn)，使用優(yōu)先隊列 + 排序緩沖區(qū)進行排序需要的時間是只使用排序緩沖區(qū)的 3 倍。因此，當 limit 數(shù)量小于待排序記錄數(shù)量的三分之一時，使用優(yōu)先隊列 + 排序緩沖區(qū)比只使用排序緩沖區(qū)排序更快，才會使用優(yōu)先隊列來提升排序效率。

經(jīng)過前面一系列的成本評估之后，如果還是不能使用優(yōu)先隊列，MySQL 會進行最后一次嘗試，這就是最后一哆嗦了：如果使用的排序模式是 ，可能會造成需要使用磁盤文件排序，此時會判斷使用 + 優(yōu)先隊列的成本是否比使用 + 磁盤文件排序的成本更低。。

如果使用 + 磁盤文件排序成本更低，那么還是保持原樣，依然使用 排序模式。

如果使用 + 優(yōu)先隊列成本更低，并且排序緩沖區(qū)中能夠存放 limit + 1 記錄的排序字段（sort_key）和主鍵 ID，使用的排序模式會由 修改為 ，并且使用優(yōu)先隊列來減少實際參與排序的記錄數(shù)量，提升排序效率。

前面提到的 limit 并不是 SQL 語句中 limit 后面的數(shù)字，而是 SQL 語句中的 offset + limit。想要了解 MySQL 中 limit 是怎么實現(xiàn)的，可以參考這篇文章：MySQL 查詢語句的 limit, offset 是怎么實現(xiàn)的？

看到這里，可能有的小伙伴會有疑問，排序模式 是不是和優(yōu)先隊列兩者不能共存？

和優(yōu)先隊列是可以共存的，只有當使用 排序模式導致排序緩沖區(qū)不能存放所有待排序記錄，要借助磁盤文件實現(xiàn)排序時，如果改為使用 + 優(yōu)先隊列實現(xiàn)排序成本更低，才會把 修改為 ，并且使用優(yōu)先隊列提升排序效率。

5.2 隨機 IO 變?yōu)轫樞?IO

使用 排序模式，從存儲引擎讀取符合 where 條件的所有記錄的主鍵 ID，按照 sort_key 排序好序之后，需要根據(jù)主鍵 ID 從存儲引擎讀取記錄中的需要返回給客戶端的其它字段。按照 sort_key 排好序的記錄，在主鍵索引中不一定是順序存儲的，可能是分散在主鍵索引的不同葉子節(jié)點中，這樣一來，通過主鍵 ID 一條一條去存儲引擎讀取記錄，會造成大量隨機 IO，導致從存儲引擎讀取數(shù)據(jù)效率低下。

為了盡可能減少隨機 IO，MySQL 通過一個專門的內(nèi)存區(qū)域，盡量把隨機 IO 變成順序 IO，這個專門的內(nèi)存區(qū)域為 隨機讀緩沖區(qū)（read_rnd_buffer）。

緩沖區(qū)大小由系統(tǒng)變量 read_rnd_buffer_size 控制，默認大小為 256K，最小為 1 字節(jié)，最大為 2G，如果設置為 1 字節(jié)，就相當于禁用了這個緩沖區(qū)了。

隨機 IO 變?yōu)轫樞?IO 的實現(xiàn)邏輯是這樣的：

• 從最終的排序結果磁盤文件（out_file）讀取主鍵 ID，寫入隨機讀緩沖區(qū)。
• 寫滿之后，對隨機讀緩沖區(qū)中的主鍵 ID 進行排序。
• 排好序之后，再按照主鍵 ID 逐條從存儲引擎讀取記錄中需要返回給客戶端的其它字段。

這個優(yōu)化方案基于這樣一個假設的前提條件：一批主鍵 ID，排好序之后邏輯上相鄰的主鍵 ID，其對應的記錄更有可能在主鍵索引的同一個葉子節(jié)點中，從存儲引擎讀取一個主鍵 ID 對應的記錄之后，再讀取下一個主鍵 ID 對應的記錄，該記錄所在的主鍵索引葉子節(jié)點有可能已經(jīng)被加載到內(nèi)存中了，就可以直接從內(nèi)存中讀取記錄，從而一定程序上減少隨機 IO，提升讀取數(shù)據(jù)的效率。

只有當排序緩沖區(qū)存放不下所有記錄的 ，需要使用磁盤文件來存儲時，才有可能使用隨機緩沖區(qū)來優(yōu)化文件排序，然而，這還只是入門門檻，要想使用隨機緩沖區(qū)，需要滿足的其它條件達 9 條之多，涉及到源碼細節(jié)，就不一一展開了，大家只要知道有這么一種優(yōu)化方案存在就可以了。

使用 、 排序模式時，不需要使用隨機緩沖區(qū)來優(yōu)化文件排序，因為這兩種排序模式下，需要返回給客戶端的所有字段都已經(jīng)在排序緩沖區(qū)或磁盤文件（out_file）中了，不需要通過主鍵 ID 二次訪問存儲引擎讀取其它字段。

6. 兩類排序

MySQL order by 的實現(xiàn)過程，可能會進行兩類排序：內(nèi)部排序、外部排序。

前面多次提到，當排序緩沖區(qū)滿，會把緩沖區(qū)中的記錄排好序，組成一個數(shù)據(jù)塊，然后寫入磁盤文件，這里的排序就是內(nèi)部排序。

符合 where 條件的所有記錄都寫入到磁盤文件之后，可能會存在多個已經(jīng)內(nèi)部排好序的數(shù)據(jù)塊，這些數(shù)據(jù)塊需要通過多路歸并排序，最終形成全局有序的結果，這里的排序就是外部排序。

6.1 內(nèi)部排序

內(nèi)部排序是對排序緩沖區(qū)中的記錄進行排序，是內(nèi)存排序。

為了提升性能，MySQL 做了各種各樣的努力，內(nèi)部排序的實現(xiàn)又一次體現(xiàn)了這種追求極致性能的努力。內(nèi)部排序使用了 3 種排序算法：

• 基數(shù)排序如果排序字段內(nèi)容長度之和小于等于 20 字節(jié)，并且要排序的記錄數(shù)量大于等于 1 千，小于 10 萬，同時能夠滿足基數(shù)排序需要的內(nèi)存空間，則會使用基數(shù)排序。
• 快速排序如果不滿足使用基數(shù)排序的條件，則會考慮使用快速排序，要排序的記錄數(shù)量 小于等于 100，就會使用快速排序。
• 歸并排序歸并排序是兜底的排序算法，如果不滿足使用基數(shù)排序和快速排序的條件，就會使用歸并排序。

為什么使用快速排序的條件是排序記錄數(shù)量小于等于 100？源碼注釋是這樣說的，歸并排序比快速排序更快，但是歸并排序申請臨時緩沖區(qū)需要額外的時間成本，所以在排序記錄數(shù)量很少的時候，歸并排序并沒有多大優(yōu)勢，歸并排序比快速排序快的臨界點是排序記錄數(shù)量在 10 ~ 40 條之間，保守一點，所以把這個閾值定為 100。

6.2 外部排序

外部排序是對磁盤文件中已經(jīng)局部排好序的記錄進行全局歸并排序，是磁盤文件排序。

MySQL 從存儲引擎讀取符合 where 的條件記錄寫入排序緩沖區(qū)，緩沖區(qū)滿時，會對緩沖區(qū)中的記錄進行內(nèi)部排序，排好序的數(shù)據(jù)組成一個數(shù)據(jù)塊，數(shù)據(jù)塊包含兩部分：Merge_chunk 和數(shù)據(jù)記錄。

Merge_chunk 寫入到磁盤文件（chunk_file）中，數(shù)據(jù)記錄寫入到磁盤文件（temp_file）中。Merge_chunk 中保存有數(shù)據(jù)記錄在 temp_file 中的起始位置、Merge_chunk 對應的數(shù)據(jù)塊在 temp_file 中的記錄數(shù)量等信息。

從存儲引擎讀取完符合 where 條件的所有記錄之后，可能會生成多個數(shù)據(jù)塊寫入到磁盤文件（temp_file）。通過多路歸并排序，把小數(shù)據(jù)塊合并為更大的數(shù)據(jù)塊，最終得到全局排好序的記錄，把磁盤文件（temp_file）中多個數(shù)據(jù)塊合并為一個數(shù)據(jù)塊的過程，借助了優(yōu)先隊列和排序緩沖區(qū)來實現(xiàn)。

注意：外部排序過程中借助優(yōu)先隊列和排序緩沖區(qū)，和 5.1 優(yōu)先隊列 中的優(yōu)先隊列 + 排序緩沖區(qū)不是一回事，不要混淆了。外部排序過程只是使用了優(yōu)先隊列和排序緩沖區(qū)來加快歸并排序的過程。

外部排序把小數(shù)據(jù)塊合并為大數(shù)據(jù)塊的過程中，會使用 7 路歸并排序，把 7 個小數(shù)據(jù)塊合并為 1 個大數(shù)據(jù)塊，數(shù)據(jù)塊數(shù)量多時，會進行多輪歸并排序，直到數(shù)據(jù)塊的數(shù)量小于等于 15，多輪歸并排序之后得到的小于等于 15 個數(shù)據(jù)塊，經(jīng)過終極歸并排序得到最終的排序結果。

接下來我們以磁盤文件（temp_file）中包含 160 個數(shù)據(jù)塊為例來說明外部排序的過程。

第一輪歸并排序示意圖：：

左下角 chunk_file 中有 160 個 Merge_chunk，temp_file 有 160 個對應于 Merge_chunk 的數(shù)據(jù)記錄塊。歸并排序過程中會借助排序緩沖區(qū)提升執(zhí)行效率，因為要進行 7 路歸并排序，排序緩沖區(qū)被平均分為 7 份，每份對應于 temp_file 中的一個數(shù)據(jù)塊，為了描述方便，我們暫且把排序緩沖區(qū)的七分之一叫做子排序緩沖區(qū)。在歸并排序過程中，會分別從 temp_file 中的 7 個數(shù)據(jù)記錄塊中讀取一部分記錄到其對應的子排序緩沖區(qū)。

讀取 temp_file 中數(shù)據(jù)記錄塊的數(shù)據(jù)到子排序緩沖區(qū)之后，優(yōu)先隊列中的每個 Merge_chunk（對應于 chunk_file 中的 Merge_chunk）中有一個屬性 current_key，指向子排序緩沖區(qū)中的第一條記錄，圖中優(yōu)先隊列的每個 Merge_chunk 有個紅色箭頭指向子排序緩沖區(qū)，就是表示 current_key 屬性指向子排序緩沖區(qū)中的第一條記錄。

current_key 指向的記錄是子排序緩沖區(qū)對應的 temp_file 數(shù)據(jù)記錄塊中排序字段值（sort_key）最大的那條記錄。

歸并排序過程中，會循環(huán)把 7 個 Merge_chunk 的 current_key 指向的記錄中排序字段值最大的記錄寫入到 temp_file2 的數(shù)據(jù)記錄塊中，直到所有數(shù)據(jù)記錄塊中的記錄都寫入到 temp_file2 文件。

每次都取 current_key 指向的記錄中最大的記錄，有沒有發(fā)現(xiàn)這是大頂堆的特點？在源碼實現(xiàn)中，找到優(yōu)先隊列中 Merge_chunk 的 current_key 屬性指向的記錄中排序字段值最大的記錄，就是用大頂堆的思路實現(xiàn)的。

從圖中右下角的 temp_file2 和 chunk_file 可以看到，經(jīng)過第一輪歸并排序之后，160 個小數(shù)據(jù)塊合并成了 23 個更大的數(shù)據(jù)塊，23 大于 15，所以還需要進行第二輪歸并排序。

第二輪歸并排序示意圖：

第一輪歸并排序，我們已經(jīng)講述了詳細的合并過程，第二輪歸并排序就不展開講了，由上圖右下角的 temp_file 和 chunk_file 可見，第二輪歸并排序，由小數(shù)據(jù)塊合并得到的 23 個更大的數(shù)據(jù)塊，再次進行 7 路歸并排序，最終得到 4 個數(shù)據(jù)塊。4 小于 15，所以不需要進行得到中間結果的第三輪歸并排序，直接進行得到最終排序結果的多路歸并排序。

不知道大家有沒有發(fā)現(xiàn)，第一輪歸并排序示意圖中，是從 temp_file 讀取記錄到子排序緩沖區(qū)，然后把歸并排序結果寫入到 temp_file2；第二輪歸并排序示意圖中，是從 temp_file2 讀取記錄到子排序緩沖區(qū)，然后把歸并排序結果寫入到 temp_file。這說明在外部歸并排序過程中，會使用兩個中間結果磁盤文件（temp_file、temp_file2），加上 chunk_file、out_file，一共會使用 4 個磁盤文件，大家知道一下就可以了。

終極多路歸并排序：

從上圖可見，經(jīng)過前面兩輪歸并排序之后，得到 4 個數(shù)據(jù)塊，排序緩沖區(qū)被分為 4 個子緩沖區(qū)，4 個子緩沖區(qū)中已局部排好序的記錄，經(jīng)過歸并排序?qū)懭氲酱娣抛罱K排序結果的磁盤文件中（out_file)。

最后一輪歸并排序和前面的 N 歸并排序有些不同。

前面 N 輪歸并排序，寫入到磁盤文件的是中間結果，磁盤文件（temp_file、temp_file2）中存放的還是局部排好序的記錄，并且記錄中還包含排序字段（sort_key），因為后面的歸并排序還需要用到排序字段（sort_key）。

最后一輪歸并排序，寫入到磁盤文件的是最終結果，磁盤文件（out_file）中存放的是全局排好序的記錄，此時記錄中只包含存儲引擎返回給 server 層的字段，已經(jīng)不包含排序字段了。

7. 倒序排序

MySQL 文件排序的內(nèi)部實現(xiàn)中，正序和倒序排序都是以正序的方式進行的，排序字段值大的在前面，排序字段值小的在后面，這樣邏輯統(tǒng)一，實現(xiàn)方便。

倒序排序時，把排序字段值寫入排序緩沖區(qū)之前，會對所有排序字段值進行逐字節(jié)取反操作，取反之后，原來字段值大的變成小的，字段值小的變成大的，排序字段值取反之后再進行正序排序，最終得到的記錄就是倒序排序的了。

舉例說明

select num from t order by num desc

以 排序模式為例，假設表中有 5 條記錄，num 字段值分別為：95, 90, 49, 97, 6，num 字段值會寫入到排序緩沖區(qū)兩次，一次是作為 sort_key，一次是作為 additional_fields，5 條記錄全部寫入緩沖區(qū)之后，緩沖區(qū)的內(nèi)容示意如下：

圖中藍色塊表示 sort_key，綠色塊表示 additional_fields，為了有個對比，1 號圖示 和 2 號圖示分別表示正序和倒序排序之前，排序緩沖區(qū)中的記錄示意圖。3 號圖示表示倒序排序之后，排序緩沖區(qū)中的記錄示意圖。

從 3 號圖示可見，倒序排序時，對排序字段值取反之后按照正序排序，最終實現(xiàn)了記錄的倒序排序。

上面示例中，對于 num 字段會寫入排序緩沖區(qū)兩次，可能有的小伙伴會有疑問，這里解釋一下：實際上，排序字段作為 sort_key 寫入到排序緩沖區(qū)之前，都會進行編碼，編碼之后的排序字段值就和原字段值不一樣了，只用于排序，不作為最終結果返回給客戶端，在排好序之后，sort_key 會被丟棄。

8. 窺探更多排序細節(jié)

通過 explain，我們只能看到 SQL 語句執(zhí)行時，是否使用了文件排序，看不到排序過程中是只使用了排序緩沖區(qū)，還是也使用了磁盤文件，更不知道排序緩沖區(qū)被寫滿了多少次；也看不到是不是使用了優(yōu)先隊列，如果沒有使用，是什么原因。

好在 MySQL 給我們提供了一個工具（optimizer trace）可以進一步了解這些細節(jié)，執(zhí)行以下 SQL 可開啟 optimizer trace：

— 開啟 optimizer traceset optimizer_trace = “enabled=on”;– 設置 optimizer_trace 輸出結果最多可占用的內(nèi)存空間，單位是：字節(jié)– 如果發(fā)現(xiàn) optimizer_trace 的 json 結果不全，可以把這個值改成更大的數(shù)字set optimizer_trace_max_mem_size = 1048576;

optimizer trace 的輸出結果 json 中有兩個和文件排序相關的屬性：filesort_summary、filesort_priority_queue_optimization，下面我把寫本文過程中使用的測試 SQL 的 optimizer trace 作為例子來說明：

// filesort_summary{ “rows”: 10227, “examined_rows”: 10227, “number_of_tmp_files”: 41, “sort_buffer_size”: 262112, “sort_mode”: “”}

number_of_tmp_files：

• 等于 0 表示只使用了排序緩沖區(qū)。
• 大于 0 表示還使用了磁盤文件，number_of_tmp_files 的值等于幾，就表示排序緩沖區(qū)被寫滿了幾次，也意味著寫入到磁盤文件的數(shù)據(jù)塊有幾個。

大家不要被 number_of_tmp_files 屬性名誤導，雖然屬性名中有 tmp_files，但這并不是表示排序過程中使用了多個臨時文件。實際上不管有多少個數(shù)據(jù)塊，都是寫入到一個磁盤文件（temp_file）中。

相信經(jīng)過本文前面的講述，大家對于 sort_mode 都已經(jīng)比較熟悉了，一共有三種排序模式：、、。

// filesort_priority_queue_optimization{ “usable”: false, “cause”: “not applicable (no LIMIT)”}

通過 usable = false 可知，我的測試 SQL 沒有使用優(yōu)先隊列，原因是沒有指定 limit。

有一點需要特別注意，獲取 optimizer trace 結果的語句必須和 SQL 語句同時執(zhí)行，不能分開一條一條的執(zhí)行，否則查出來的 optimizer trace 結果是空白。

舉例說明：

select * from t2 where i1 >= 99991840 order by str1; — SQL 1select * from information_schema.OPTIMIZER_TRACE; — SQL 2

對于上面例子，如果先執(zhí)行 SQL 1 再執(zhí)行 SQL 2，會發(fā)現(xiàn) optimizer trace 結果是空的，必須同時執(zhí)行 SQL 1 和 SQL 2，才能得到 SQL 1 的 optimizer trace 結果。

9. 總結

本文我們以文件排序的整體概覽開始，拋開實現(xiàn)細節(jié)，從全局角度了解了文件排序的整體邏輯。接著介紹了系統(tǒng)變量 sort_buffer_size 用于控制排序緩沖區(qū)大小，max_sort_length 用于控制單個排序字段內(nèi)容長度。

排序模式小節(jié)，介紹了三種排序模式：

• 把排序字段（sort_key）和存儲引擎返回給 server 層的字段都寫入排序緩沖區(qū)或磁盤文件，每個字段都以其最大長度占用存儲空間，存在在空間浪費。
• 是 的改進版，解決了空間浪費的問題。char、varchar 字段只占用實際內(nèi)容需要的空間，內(nèi)容為 NULL 的字段除了在 NULL 標記區(qū)域占用 1 bit 之外，不會再占用其它空間。
• 前面兩種排序模式，以空間換時間，雖然不需要兩次訪問存儲引擎，讓文件排序邏輯整體上更簡單，但是記錄數(shù)量多起來之后，需要磁盤文件存儲排序結果，而磁盤 IO 會導致排序效率低下。 需要兩次訪問存儲引擎，但只寫入排序字段（sort_key）和主鍵 ID 到排序緩沖區(qū)，一定程度上避免了使用磁盤文件存放排序結果，某些情況下可能會比前兩種排序模式更優(yōu)。

提升排序效率小節(jié)，介紹了源碼中采用的兩個優(yōu)化方案：

• SQL 語句中包含 limit 的情況下，通過成本評估有可能會使用優(yōu)先隊列來避免磁盤文件排序，提升排序效率。
• 使用 排序模式，并且由于記錄數(shù)量太多需要使用磁盤文件時，通過把主鍵 ID 緩存在隨機讀緩沖區(qū)（read rnd bufer），緩沖區(qū)滿后對主鍵 ID 排序，再通過主鍵 ID 去存儲引擎讀取客戶端需要的字段，盡可能把隨機 IO 變?yōu)轫樞?IO，提升排序效率。

兩類排序小節(jié)，介紹了三種內(nèi)部排序算法，其使用優(yōu)先級為：基數(shù)排序、快速排序、歸并排序。

外部排序，可能會進行 0 ~ N 輪歸并排序生成中間結果，最后進行一輪歸并排序得到最終結果。

生成中間結果的歸并排序，排序字段（sort_key）也會寫入到磁盤文件，后續(xù)生成中間結果和最終結果的歸并排序都會用到。生成最終結果的歸并排序，磁盤文件只寫入存儲引擎返回給 server 層的字段，不會包含排序字段（sort_key）。

倒序排序小節(jié)，介紹了倒序排序的實現(xiàn)：先對排序字段（sort_key）逐字節(jié)取反，然后對排序字段進行正序排序，最終得到倒序排序的記錄。

最后，介紹了如何通過 optimizer trace 窺探文件排序的更多細節(jié)。