1 概述

MySQL有兩種方式可以實現ORDER BY：

1.通過索引掃描生成有序的結果

2.使用文件排序(filesort)

圍繞著這兩種排序方式，我們試著理解一下ORDER BY的執行過程以及回答一些常見的問題（下文僅討論InnoDB存儲引擎）。

2 索引掃描排序和文件排序(filesort)簡介

我們知道InnoDB存儲引擎以B+樹作為索引的底層實現，B+樹的葉子節點存儲著所有數據頁而內部節點不存放數據信息，并且所有葉子節點形成一個(雙向)鏈表。

舉個例子，假設userinfo表的userid字段上有主鍵索引，且userid目前的范圍在1001~1006之間，則userid的索引B+樹如下(這里只是為了舉例，下圖忽略了InnoDB數據頁默認大小16KB、雙向鏈表，并且假設B+樹度數為3、userid順序插入)：

現在我們想按照userid從小到大的順序取出所有用戶信息，執行以下SQL：

SELECT *

FROM userinfo

ORDER BY userid;

MySQL會直接遍歷上圖userid索引的葉子節點鏈表，不需要進行額外的排序操作。這就是用索引掃描來排序。

但如果userid字段上沒有任何索引，圖1的B+樹結構不存在，MySQL就只能先掃表篩選出符合條件的數據，再將篩選結果根據userid排序。這個排序過程就是filesort。

下文將詳細介紹這兩種排序方式。

3 索引掃描排序執行過程分析

介紹索引掃描排序之前，先看看索引的用途

SQL語句中，WHERE子句和ORDER BY子句都可以使用索引：WHERE子句使用索引避免全表掃描，ORDER BY子句使用索引避免filesort（用“避免”可能有些欠妥，某些場景下全表掃描、filesort未必比走索引慢），以提高查詢效率。

雖然索引能提高查詢效率，但在一條SQL里，對于一張表的查詢 一次只能使用一個索引（注：排除發生index merge的可能性），也就是說當WHERE子句與ORDER BY子句要使用的索引不一致時，MySQL只能使用其中一個索引(B+樹)。

也就是說，一個既有WHERE又有ORDER BY的SQL中，使用索引有三個可能的場景：

只用于WHERE子句 篩選出滿足條件的數據

只用于ORDER BY子句 返回排序后的結果

既用于WHERE又用于ORDER BY，篩選出滿足條件的數據并返回排序后的結果

舉個例子，我們創建一張orderdetail表 記錄每一筆充值記錄的userid(用戶id)、money(充值金額)、createtime(充值時間)，主鍵是自增id：

CREATE TABLE `order_detail` (

`id` int(11) NOT NULL AUTO_INCREMENT,

`userid` int(11) NOT NULL,

`money` float NOT NULL,

`create_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,

PRIMARY KEY (`id`),

KEY `userid` (`userid`),

KEY `create_time` (`create_time`)

) ENGINE=InnoDB DEFAULT CHARSET=utf8

寫腳本插入100w行數據（InnoDB別用COUNT(*)查總行數，會掃全表，這里只是為了演示）：

SELECT COUNT(*) FROM order_detail;

+----------+

| COUNT(*) |

+----------+

| 1000000 |

+----------+

SELECT * FROM order_detail LIMIT 5;

+----+--------+-------+---------------------+

| id | userid | money | create_time |

+----+--------+-------+---------------------+

| 1 | 104832 | 3109 | 2013-01-01 07:40:38 |

| 2 | 138455 | 6123 | 2013-01-01 07:40:42 |

| 3 | 109967 | 7925 | 2013-01-01 07:40:46 |

| 4 | 166686 | 4307 | 2013-01-01 07:40:55 |

| 5 | 119837 | 1912 | 2013-01-01 07:40:58 |

+----+--------+-------+---------------------+

現在我們想取出userid=104832用戶的所有充值記錄，并按照充值時間create_time正序返回。

場景一 索引只用于WHERE子句

寫出如下SQL并EXPLAIN一下：

EXPLAIN

SELECT *

FROM order_detail

WHERE userid = 104832

ORDER BY create_time;

+------+-------------+--------------+------+---------------+--------+---------+-------+------+-----------------------------+

| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |

+------+-------------+--------------+------+---------------+--------+---------+-------+------+-----------------------------+

| 1 | SIMPLE | order_detail | ref | userid | userid | 4 | const | 8 | Using where; Using filesort |

+------+-------------+--------------+------+---------------+--------+---------+-------+------+-----------------------------+

key列的值是userid，可以看出這條SQL會使用userid索引用作WHERE子句的條件過濾，而ORDER BY子句無法使用該索引，只能使用filesort來排序。這就是上文的第一個場景，整個執行流程大致如下：

先通過userid索引找到所有滿足WHERE條件的主鍵id（注：從b+樹根節點往下找葉子節點，時間復雜度為O(logN))

再根據這些主鍵id去主鍵索引(聚簇索引)找到這幾行的數據，生成一張臨時表（時間復雜度為O(M*logN)，M是臨時表的行數）

對臨時表進行排序（時間復雜度O(M*logM)，M是臨時表的行數)

由于本例中M的值可以大概參考 rows列的值8，非常小，所以整個執行過程只花費0.00 sec。

場景二 索引只用于ORDER BY子句

接下來是上文的第二種場景，索引只用于ORDER BY子句，這即是索引掃描排序。

我們可以繼續使用上文的SQL，通過FORCE INDEX子句強制Optimizer使用ORDER BY子句的索引create_time：

EXPLAIN

SELECT *

FROM order_detail

FORCE INDEX (create_time)

WHERE userid = 104832

ORDER BY create_time;

+------+-------------+--------------+-------+---------------+-------------+---------+------+--------+-------------+

| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |

+------+-------------+--------------+-------+---------------+-------------+---------+------+--------+-------------+

| 1 | SIMPLE | order_detail | index | NULL | create_time | 4 | NULL | 998056 | Using where |

+------+-------------+--------------+-------+---------------+-------------+---------+------+--------+-------------+

可以看到Extra字段里的Using filesort已經沒了，但是掃過的rows大概有998056行(準確的值應該是1000000行，InnoDB這一列只是估值)。這是因為索引用于ORDER BY子句時，會直接遍歷該索引的葉子節點鏈表，而不像第一種場景那樣從B+樹的根節點出發 往下查找。執行流程如下：

從create_time索引的第一個葉子節點出發，按順序掃描所有葉子節點

根據每個葉子節點記錄的主鍵id去主鍵索引(聚簇索引)找到真實的行數據，判斷行數據是否滿足WHERE子句的userid條件，若滿足，則取出并返回

整個時間復雜度是O(M*logN)，M是主鍵id的總數，N是聚簇索引葉子節點的個數(數據頁的個數)。本例中M的值為1000000，所以整個執行過程比第一種場景花了更多時間，同一臺機器上耗時1.34 sec。

上述兩個例子恰好說明了另一個道理：在某些場景下使用filesort比不使用filesort 效率更高。

場景三 索引既用于WHERE又用于ORDER BY

第三種情況發生在WHERE子句與ORDER BY子句能使用相同的索引時（如: WHERE userid > xxx ORDER BY userid），這樣就能省去第二種情況的回表查詢操作了。

因此，如果可能，設計索引時應該盡可能地同時滿足這兩種任務，這樣是最好的。----《高性能MySQL》

4 文件排序(filesort)

關于filesort上文其實已經介紹過了一些。

filesort的名字起得很費解，讓人誤以為它會：將一張非常大的表放入磁盤再進行排序。其實不是這樣的，filesort僅僅是排序而已，是否會放入磁盤看情況而定（filesort is not always bad and it does not mean that a file is saved on disk. If the size of the data is small, it is performed in memory.）。以下是《高性能MySQL》中對filesort的介紹：

如果需要排序的數據量小于“排序緩沖區”，MySQL使用內存進行“快速排序”操作。如果內存不夠排序，那么MySQL會先將數據分塊，可對每個獨立的塊使用“快速排序”進行排序，再將各個塊的排序結果放到磁盤上，然后將各個排好序的塊進行“歸并排序”，最后返回排序結果。

所以filesort是否會使用磁盤取決于它操作的數據量大小。

總結來說就是，filesort按排序方式來劃分 分為兩種：

1.數據量小時，在內存中快排

2.數據量大時，在內存中分塊快排，再在磁盤上將各個塊做歸并

數據量大的情況下涉及到磁盤io，所以效率會低一些。

根據回表查詢的次數，filesort又可以分為兩種方式：

1.回表讀取兩次數據(two-pass)：兩次傳輸排序

2.回表讀取一次數據(single-pass)：單次傳輸排序

兩次傳輸排序

兩次傳輸排序會進行兩次回表操作：第一次回表用于在WHERE子句中篩選出滿足條件的rowid以及rowid對應的ORDER BY的列值；第二次回表發生在ORDER BY子句對指定列進行排序之后，通過rowid回表查出SELECT子句需要的字段信息。

舉個例子，我們需要從充值記錄表篩選出2018年8月11日到12日的所有userid>140000用戶的訂單的明細，并按照金額從大到小進行排序（下面只是為filesort舉例，不是一種好的實現）：

EXPLAIN

SELECT *

FROM order_detail

WHERE create_time >= '2018-08-11 0000' and create_time < '2018-08-12 0000' and userid > 140000

order by money desc;

+------+-------------+--------------+-------+--------------------+-------------+---------+------+------+-----------------------------+

| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |

+------+-------------+--------------+-------+--------------------+-------------+---------+------+------+-----------------------------+

| 1 | SIMPLE | order_detail | range | userid,create_time | create_time | 4 | NULL | 1 | Using where; Using filesort |

+------+-------------+--------------+-------+--------------------+-------------+---------+------+------+-----------------------------+

我們試著分析一下這個SQL的執行過程：

利用createtime索引，對滿足WHERE子句createtime >= '2018-08-11 0000' and create_time < '2018-08-12 0000'的rowid進行回表（第一次回表），回表之后可以拿到該rowid對應的userid，若userid滿足userid > 140000的條件時，則將該行的rowid，money(ORDER BY的列)放入排序緩沖區。

若排序緩沖區能放下所有rowid, money對，則直接在排序緩沖區（內存）進行快排。

若排序緩沖區不能放下所有rowid, money對，則分塊快排，將塊存入臨時文件（磁盤），再對塊進行歸并排序。

遍歷排序后的結果，對每一個rowid按照排序后的順序進行回表操作（第二次回表），取出SELECT子句需要的所有字段。

熟悉計算機系統的人可以看出，第二次回表會表比第一次回表的效率低得多，因為第一次回表幾乎是順序I/O；而由于rowid是根據money進行排序的，第二次回表會按照rowid亂序去讀取行記錄，這些行記錄在磁盤中的存儲是分散的，每讀一行 磁盤都可能會產生尋址時延（磁臂移動到指定磁道）+旋轉時延（磁盤旋轉到指定扇區），這即是隨機I/O。

所以為了避免第二次回表的隨機I/O，MySQL在4.1之后做了一些改進：在第一次回表時就取出此次查詢用到的所有列，供后續使用。我們稱之為單次傳輸排序。

單次傳輸排序（MySQL4.1之后引入）

還是上面那條SQL，我們再看看單次傳輸排序的執行過程：

利用createtime索引，對滿足WHERE子句createtime >= '2018-08-11 0000' and create_time < '2018-08-12 0000'的rowid進行回表（第一次回表），回表之后可以拿到改rowid對應的userid，若userid滿足userid > 140000的條件時，則將此次查詢用到該行的所有列（包括ORDER BY列）取出作為一個數據元組(tuple)，放入排序緩沖區。

若排序緩沖區能放下所有tuples，則直接在排序緩沖區（內存）進行快排。

若排序緩沖區不能放下所有tuples，則分塊快排，將塊存入臨時文件（磁盤），再對塊進行歸并排序。

遍歷排序后的每一個tuple，從tuple中取出SELECT子句需要所有字段。

單次傳輸排序的弊端在于會將所有涉及到的列都放入排序緩沖區，排序緩沖區一次能放下的tuples更少了，進行歸并排序的概率增大。列數據量越大，需要的歸并路數更多，增加了額外的I/O開銷。所以列數據量太大時，單次傳輸排序的效率可能還不如兩次傳輸排序。

當然，列數據量太大的情況不是特別常見，所以MySQL的filesort會盡可能使用單次傳輸排序，但是為了防止上述情況發生，MySQL做了以下限制：

所有需要的列或ORDER BY的列只要是BLOB或者TEXT類型，則使用兩次傳輸排序。

所有需要的列和ORDER BY的列總大小超過maxlengthforsortdata字節，則使用兩次傳輸排序。

我們開發者也應該盡可能讓filesort使用單次傳輸排序，不過EXPLAIN不會告訴我們這個信息，所以我們只能肉眼檢查各列的大小看看是否會觸發上面兩個限制 導致兩次傳輸排序的發生。

5 補充說明

如第3小節所述，既然filesort的效率未必比索引掃描排序低，為什么很多人會想避免filesort呢？

谷歌一下using filesort，幾乎都是"如何避免filesort"相關的內容：

這是因為通常ORDER BY子句會與LIMIT子句配合，只取出部分行。如果只是為了取出top1的行 卻對所有行進行排序，這顯然不是一種高效的做法。這種場景下 按順序取的索引掃描排序可能會比filesort擁有更好性能（當然也有例外）。

Whether the optimizer actually does so depends on whether reading the index is more efficient than a table scan if columns not in the index must also be read.

官方文檔告訴我們optimizer會幫我們選擇一種高效的ORDER BY方式。

但也不能完全依賴optimizer的判斷，這時合理建立索引、引導它使用指定索引可能是更好的選擇。

6 參考資料

MySQL 8.0 Reference Manual :: 8.2.1.14 ORDER BY Optimization

《高性能MySQL》

Sergey Petrunia's blog ? How MySQL executes ORDER BY

MySQL filesort algorithms - Valinv

MySQL技術內幕:InnoDB存儲引擎(第2版)

B+ Tree Visualization

B+ Trees(pdf)

MySQL :: MySQL 8.0 Reference Manual :: 8.8.2 EXPLAIN Output Format

What do Clustered and Non clustered index actually mean? - Stack Overflow

原文標題：詳解 MySQL ORDER BY

文章出處：【微信公眾號：數據分析與開發】歡迎添加關注！文章轉載請注明出處。

責任編輯：haq