數(shù)據(jù)準備

CREATE TABLE `user_info` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT COMMENT 'ID',
  `name` varchar(20) NOT NULL COMMENT '用戶名',
  `age` tinyint(4) NOT NULL DEFAULT '0' COMMENT '年齡',
  `sex` tinyint(2) NOT NULL DEFAULT '0' COMMENT '狀態(tài) 0：男 1： 女',
  `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '創(chuàng)建時間',
  `udpate_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '更新時間',
  PRIMARY KEY (`id`),
  KEY `idx_name` (`name`) COMMENT 'name索引'
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='用戶信息'

測試執(zhí)行SQL

1）、查詢字段為索引（索引覆蓋查詢），同時排序字段完全包含查詢字段

EXPLAIN 
select name from user_info where name like '測試用戶4%' order by name;

 執(zhí)行流程如下：

2）、查詢字段為部分索引字段部分普通字段，同時排序字段未完全包含查詢字段

EXPLAIN
select name, age, sex from user_info where name like '測試用戶4%' order by name;

注：該sql會有兩種情況,當 

 執(zhí)行流程如下：

mysql排序中有兩個很關鍵的變量：sort_buffer_size 和 max_length_for_sort_data

sort_buffer_size：MySQL為排序準備的一塊緩存區(qū)內(nèi)存

• 如果排序的數(shù)據(jù)量小于sort_buffer_size，則直接在內(nèi)存完成排序
• 如果排序的數(shù)據(jù)量大于sort_buffer_size，則會借助磁盤臨時文件完成排序。

max_length_for_sort_data：控制哪些字段進入排序緩沖區(qū)。

• 如果排序字段（排序字段+select 字段）長度小于max_length_for_sort_data，進行全字段排序（不回表查詢）
• 如果排序字段（排序字段+select 字段）長度大于max_length_for_sort_data，進行rowid字段排序（二次回表查詢）

例如執(zhí)行如下SQL：   

select name, age, sex from user_info where name like '測試用戶4%' order by name;

• 字段 name、age、sex對應類型及長度：varchar(20)、tinyint(4)、tinyint(2)；
• 排序字段為name，sort字段長度約≈20*2=40（varchar類型的為啥是2，目前沒搞清楚）
• select字段(mysql中稱之為addon字段)，在編碼utf8（utffmb3）中，varchar一個字符對應3個字節(jié)，tinyint為1個字節(jié)，所以addon字段長度≈22*3+1+1=68。
• 排序字段+addon字段=40+68=108<max_length_for_sort_data(1024),這時候name、age、sex數(shù)據(jù)都將進入排序緩沖區(qū)，這就是人們常說的全字段排序。
• 但是此時如果將max_length_for_sort_data改為20，那么只會將主鍵ID和排序字段name放入緩沖區(qū)，排序后通過再次反查聚簇索引樹獲取所需要字段值(age、sex)，這種就是常說的rowid排序。

二者的區(qū)別是：一個是空間換時間、一個時間換空間。

注意: 如果單個排序字段超過max_sort_length大小，mysql將會根據(jù)max_sort_length對排序字段內(nèi)容進行截斷，將會導致排序結(jié)果可能不是預期的（max_length_for_sort_data對應的是所有排序字段+select字段）。

MySQL 原則：如果內(nèi)存夠，就多利用內(nèi)存，盡量減少磁盤訪問。對于 InnoDB 表來說，rowid 排序會進行回表造成磁盤讀

接下來從更底層了解MySQL文件排序

1、整體概覽

 執(zhí)行流程說明：

• 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ù)塊合并為最終的排序結(jié)果，寫入磁盤文件（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)排序結(jié)果和預期不一致的情況。

4、排序模式（sort mode）

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

排序模式一共有 3 種：

• <sort_key, additional_fields>
• <sort_key, packed_additional_fields>
• <sort_key, rowid>

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

4.1 <sort_key, additional_fields>

<sort_key, additional_fields> 表示排序緩沖區(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é)。<sort_key, packed_additional_fields> 排序模式中，為了節(jié)省空間，只寫入 char 字段實際內(nèi)容到排序緩沖區(qū)，所以需要記錄字段內(nèi)容長度。為了邏輯統(tǒng)一，<sort_key, additional_fields> 排序模式中也會寫入 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 類型字段時，不能使用 <sort_key, additional_fields>、<sort_key, packed_additional_fields> 排序模式。

重點說明：

 如果某個字段內(nèi)容為 NULL，該字段在字段 NULL 標記區(qū)域?qū)?NULL 標記位設置為 1，同時，該字段在排序緩沖區(qū)中還會占用存儲空間，占用空間大小為字段最大長度。

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

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

使用 <sort_key, additional_fields> 需要滿足以下條件：

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

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

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

<sort_key, additional_fields> 的優(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é)。

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

4.2 <sort_key, packed_additional_fields>

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

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

 上圖是寫入到排序緩沖區(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ū)的額外空間。

<sort_key, packed_additional_fields> 是以 <sort_key, additional_fields> 為基礎的，如果不滿足使用 <sort_key, additional_fields> 的條件，也不會使用 <sort_key, packed_additional_fields>。

使用 <sort_key, packed_additional_fields> 排序模式，還需要滿足以下條件：

• 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é)省的空間太小，也就沒必要折騰了。

這地方有個varchar長字段問題，例如 name varchar(20)和 name varchar（200）.

• 圖示：

select name,sex from user_info_varchar20 order by name LIMIT 999995, 5;
select name,sex from user_info_varchar200 order by name LIMIT 999995, 5;

varchar(200)比varchar(20)產(chǎn)生更多數(shù)據(jù)塊，性能也更差。

注：在處理大長度字符串時可以考慮創(chuàng)建前綴索引或者利用CRC(CRC32或CRC64）創(chuàng)建額外索引。

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

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

4.3 <sort_key, rowid>

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

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

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

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

使用 <sort_key, rowid> 讀取數(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è)務來說，都不會一次性讀取這么多記錄，由此可見，一般情況下，使用 <sort_key, rowid> 排序模式不會用到磁盤文件排序。

但是，凡事都有例外，如果一條 SQL 語句讀取過多的記錄，哪怕是使用 <sort_key, rowid>，當排序緩沖區(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)先隊列需要使用的額外的一條記錄的空間（堆排序第一個位置不放數(shù)據(jù)）。

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

大體流程：

sort_buffer_size足夠大：

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

sort_buffer_size不夠大：

• 否則，N條數(shù)據(jù)比sort_buffer_size大的情況下，MySQL無法直接利用sort buffer作為priority queue，正常的文件外部排序還是一樣的，只是在最后返回結(jié)果時，只根據(jù)N個row ID將數(shù)據(jù)返回出來，如果是Limit m,n， 對應的“N個row ID”就是“M+N個row ID”了，MySQL的Limit m,n 其實是取m+n行數(shù)據(jù)，最后把M條數(shù)據(jù)丟掉。

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

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

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

前面提到的  limit 并不是 SQL 語句中 limit 后面的數(shù)字，而是 SQL 語句中的 offset + limit。

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

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

最后補充一個官網(wǎng)的例子：

官網(wǎng)limit優(yōu)化地址：MySQL :: MySQL 8.0 Reference Manual :: 10.2.1.19 LIMIT Query Optimization

準備數(shù)據(jù)：

/* 創(chuàng)建表 */
CREATE TABLE `ratings` (
`id` bigint(20) NOT NULL AUTO_INCREMENT,
`category` tinyint(4) NOT NULL,
`rating` decimal(4,1) NOT NULL,
PRIMARY KEY (`id`)

) ENGINE=InnoDB DEFAULT CHARSET=utf8 ;

/* 插入測試數(shù)據(jù) */
INSERT INTO `ratings`(`id`, `category`, `rating`) VALUES 
(1, 1, 4.5),
(2, 3, 5.0),
(3, 2, 3.7),
(4, 2, 3.5),
(5, 1, 3.2),
(6, 2, 3.5),
(7, 3, 2.7);

執(zhí)行不帶limit的sql： 

SELECT * FROM ratings ORDER BY category;

查詢優(yōu)化跟蹤器：

SET optimizer_trace='enabled=on'; 
SELECT * FROM ratings ORDER BY category;
SELECT * from information_schema.OPTIMIZER_TRACE;

由于沒有l(wèi)imit，所以未使用排序優(yōu)先級隊列（ "cause": "not applicable (no LIMIT)"）。 

 執(zhí)行帶limit的sql： 

SELECT * FROM ratings ORDER BY category LIMIT 5;

注：結(jié)果和官網(wǎng)的稍微有點不一樣，id3和id4的位置不一樣，本地3在前，官網(wǎng)4在前。

查詢優(yōu)化跟蹤器

SET optimizer_trace='enabled=on'; 
SELECT * FROM ratings ORDER BY category LIMIT 5;
SELECT * from information_schema.OPTIMIZER_TRACE;

通過分析可得知，limit SQL使用了排序優(yōu)先級隊列，limit就是找top N，堆排序。

//TODO 未完待續(xù),通過堆排序推演排序優(yōu)先級隊列

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

使用 <sort_key, rowid> 排序模式，從存儲引擎讀取符合 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)邏輯是這樣的：

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

使用 <sort_key, additional_fields>、<sort_key, packed_additional_fields> 排序模式時，不需要使用隨機緩沖區(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ù)塊需要通過多路歸并排序，最終形成全局有序的結(jié)果，這里的排序就是外部排序。

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)過終極歸并排序得到最終的排序結(jié)果。

接下來我們以磁盤文件（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，所以不需要進行得到中間結(jié)果的第三輪歸并排序，直接進行得到最終排序結(jié)果的多路歸并排序。

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

終極多路歸并排序：

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

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

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

最后一輪歸并排序，寫入到磁盤文件的是最終結(jié)果，磁盤文件（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

以 <sort_key, additional_fields> 排序模式為例，假設表中有 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ū)之前，都會進行編碼，編碼之后的排序字段值就和原字段值不一樣了，只用于排序，不作為最終結(jié)果返回給客戶端，在排好序之后，sort_key 會被丟棄。

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

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

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

--開啟optimizertrace
setoptimizer_trace="enabled=on";


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

optimizer trace 的輸出結(jié)果 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":"<sort_key,rowid>"
}

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)比較熟悉了，一共有三種排序模式：<sort_key, rowid>、<sort_key, additional_fields>、<sort_key, packed_additional_fields>。

filesort_priority_queue_optimization
{
"usable":false,
"cause":"notapplicable(noLIMIT)"
}

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

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

舉例說明：

select * from t2 where i1>=99991840 order by str1;--SQL1

select * from information_schema.OPTIMIZER_TRACE;--SQL2

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

9. 總結(jié)

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

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

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

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

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

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

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

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

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

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論