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

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

內(nèi)容目錄

1. 整體概覽

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

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

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

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

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

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

sort_buffer_size 默認(rèn)值為 256K，最小可以設(shè)置為 32K，最大可以設(shè)置為 4G。

3. 單個(gè)排序字段太長了怎么辦？

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

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

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

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

4. 排序模式（sort mode）

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

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

4.1

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

additional_fields 沒有描述為 select 子句中的所有字段，而是用了更長的描述存儲(chǔ)引擎返回給 server 層的所有字段，是因?yàn)閮烧卟⒉煌耆粯樱疚暮竺娉霈F(xiàn)相關(guān)的場(chǎng)景時(shí)，也都使用后者來描述。

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

• 排序字段（sort_key）：排序字段內(nèi)容，會(huì)進(jìn)行編碼以節(jié)省存儲(chǔ)空間，可能包含一個(gè)或多個(gè)排序字段。
• 字段 NULL 標(biāo)記區(qū)域：創(chuàng)建表時(shí)，沒有指定 NOT NULL 的字段，在這個(gè)區(qū)域會(huì)有 1 bit 用于標(biāo)記記錄中該字段內(nèi)容是否為 NULL。
• char 長度：char 字段長度，占用 1 字節(jié)或 2 字節(jié)。 排序模式中，為了節(jié)省空間，只寫入 char 字段實(shí)際內(nèi)容到排序緩沖區(qū)，所以需要記錄字段內(nèi)容長度。為了邏輯統(tǒng)一， 排序模式中也會(huì)寫入 char 字段長度和內(nèi)容到排序緩沖區(qū)。
• char 內(nèi)容：char 字段內(nèi)容，以最大長度存儲(chǔ)，不會(huì)去掉內(nèi)容尾部的空格。
• varchar 長度：varchar 字段內(nèi)容長度，占用 1 字節(jié)或 2 字節(jié)。
• varchar 內(nèi)容：varchar 字段內(nèi)容，占用空間為字段最大長度。如果字段實(shí)際內(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 類型實(shí)現(xiàn)的，而 select 子句中包含 blob 類型字段時(shí)，不能使用 、 排序模式。
• 重點(diǎn)說明： 如果某個(gè)字段內(nèi)容為 NULL，該字段在字段 NULL 標(biāo)記區(qū)域?qū)?yīng)的 NULL 標(biāo)記位設(shè)置為 1，同時(shí)，該字段在排序緩沖區(qū)中還會(huì)占用存儲(chǔ)空間，占用空間大小為字段最大長度。

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

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

使用 需要滿足以下條件：

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

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

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

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

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

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

4.2

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

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

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

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

是以 為基礎(chǔ)的，如果不滿足使用 的條件，也不會(huì)使用 。

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

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

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

別急，該輪到 排序模式出場(chǎng)了，MySQL 剛出道時(shí)采用的就是這種排序模式。

4.3

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

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

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

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

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

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

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

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

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

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

5. 提升排序效率

5.1 優(yōu)先隊(duì)列

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

優(yōu)先隊(duì)列在內(nèi)存中維護(hù)待排序記錄的隊(duì)列，隊(duì)列中的元素不會(huì)實(shí)際存儲(chǔ)記錄內(nèi)容，而是存儲(chǔ)指向排序緩沖區(qū)中記錄的地址，因?yàn)橐ＷC不使用磁盤文件，使用優(yōu)先隊(duì)列提升排序效率的必要條件是：SQL 語句必須包含 limit。

在滿足必要條件的基礎(chǔ)上，會(huì)評(píng)估使用優(yōu)先隊(duì)列進(jìn)行排序是否更快，以決定是否使用。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. 兩類排序

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

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

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

6.1 內(nèi)部排序

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

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

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

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

6.2 外部排序

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第二輪歸并排序示意圖：

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

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

終極多路歸并排序：

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

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

前面 N 輪歸并排序，寫入到磁盤文件的是中間結(jié)果，磁盤文件（temp_file、temp_file2）中存放的還是局部排好序的記錄，并且記錄中還包含排序字段（sort_key），因?yàn)楹竺娴臍w并排序還需要用到排序字段（sort_key）。

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

7. 倒序排序

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

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

舉例說明

select num from t order by num desc

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

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

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

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

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

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

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

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

optimizer trace 的輸出結(jié)果 json 中有兩個(gè)和文件排序相關(guān)的屬性：filesort_summary、filesort_priority_queue_optimization，下面我把寫本文過程中使用的測(cè)試 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ù)塊有幾個(gè)。

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

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

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

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

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

舉例說明：

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

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

9. 總結(jié)

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

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

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

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

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

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

外部排序，可能會(huì)進(jìn)行 0 ~ N 輪歸并排序生成中間結(jié)果，最后進(jìn)行一輪歸并排序得到最終結(jié)果。

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

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

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