1 概述
2 索引掃描排序和文件排序簡(jiǎn)介
3 索引掃描排序執(zhí)行過(guò)程分析
4 文件排序

5 補(bǔ)充說(shuō)明
6 參考資料

MySQL有兩種方式可以實(shí)現(xiàn)ORDER BY：

1.通過(guò)索引掃描生成有序的結(jié)果

2.使用文件排序(filesort)

圍繞著這兩種排序方式，我們?cè)囍斫庖幌?strong>ORDER BY的執(zhí)行過(guò)程以及回答一些常見(jiàn)的問(wèn)題。（下文僅討論InnoDB存儲(chǔ)引擎）

我們知道InnoDB存儲(chǔ)引擎以B+樹(shù)作為索引的底層實(shí)現(xiàn)，B+樹(shù)的葉子節(jié)點(diǎn)存儲(chǔ)著所有數(shù)據(jù)頁(yè)而內(nèi)部節(jié)點(diǎn)不存放數(shù)據(jù)信息，并且所有葉子節(jié)點(diǎn)形成一個(gè)(雙向)鏈表。
舉個(gè)例子，假設(shè)userinfo表的userid字段上有主鍵索引，且userid目前的范圍在1001~1006之間，則userid的索引B+樹(shù)如下：(這里只是為了舉例，下圖忽略了InnoDB數(shù)據(jù)頁(yè)默認(rèn)大小16KB、雙向鏈表，并且假設(shè)B+樹(shù)度數(shù)為3、userid順序插入)

現(xiàn)在我們想按照userid從小到大的順序取出所有用戶信息，執(zhí)行以下SQL

SELECT * 
  FROM userinfo
    ORDER BY userid;

MySQL會(huì)直接遍歷上圖userid索引的葉子節(jié)點(diǎn)鏈表，不需要進(jìn)行額外的排序操作。這就是用索引掃描來(lái)排序。

但如果userid字段上沒(méi)有任何索引，圖1的B+樹(shù)結(jié)構(gòu)不存在，MySQL就只能先掃表篩選出符合條件的數(shù)據(jù)，再將篩選結(jié)果根據(jù)userid排序。這個(gè)排序過(guò)程就是filesort。

下文將詳細(xì)介紹這兩種排序方式。

介紹索引掃描排序之前，先看看索引的用途
SQL語(yǔ)句中，WHERE子句和ORDER BY子句都可以使用索引：WHERE子句使用索引避免全表掃描，ORDER BY子句使用索引避免filesort（用“避免”可能有些欠妥，某些場(chǎng)景下全表掃描、filesort未必比走索引慢），以提高查詢效率。
雖然索引能提高查詢效率，但在一條SQL里，對(duì)于一張表的查詢 一次只能使用一個(gè)索引（注：排除發(fā)生index merge的可能性），也就是說(shuō)當(dāng)WHERE子句與ORDER BY子句要使用的索引不一致時(shí)，MySQL只能使用其中一個(gè)索引(B+樹(shù))。

也就是說(shuō)，一個(gè)既有WHERE又有ORDER BY的SQL中，使用索引有三個(gè)可能的場(chǎng)景:

只用于WHERE子句 篩選出滿足條件的數(shù)據(jù)

只用于ORDER BY子句 返回排序后的結(jié)果

既用于WHERE又用于ORDER BY，篩選出滿足條件的數(shù)據(jù)并返回排序后的結(jié)果

舉個(gè)例子，我們創(chuàng)建一張order_detail表 記錄每一筆充值記錄的userid(用戶id)、money(充值金額)、create_time(充值時(shí)間)，主鍵是自增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

寫(xiě)腳本插入100w行數(shù)據(jù)（InnoDB別用COUNT(*)查總行數(shù)，會(huì)掃全表，這里只是為了演示）:

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 |
+----+--------+-------+---------------------+

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

寫(xiě)出如下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會(huì)使用userid索引用作WHERE子句的條件過(guò)濾，而ORDER BY子句無(wú)法使用該索引，只能使用filesort來(lái)排序。這就是上文的第一個(gè)場(chǎng)景，整個(gè)執(zhí)行流程大致如下：

先通過(guò)userid索引找到所有滿足WHERE條件的主鍵id（注:從b+樹(shù)根節(jié)點(diǎn)往下找葉子節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(logN))

再根據(jù)這些主鍵id去主鍵索引(聚簇索引))找到這幾行的數(shù)據(jù)，生成一張臨時(shí)表放入排序緩沖區(qū)（時(shí)間復(fù)雜度為O(M*logN)，M是臨時(shí)表緩沖區(qū)里的行數(shù)）

對(duì)臨時(shí)表緩沖區(qū)里的數(shù)據(jù)進(jìn)行排序（時(shí)間復(fù)雜度O(M*logM)，M是臨時(shí)表緩沖區(qū)里的行數(shù))

由于本例中M的值可以大概參考rows列的值8，非常小，所以整個(gè)執(zhí)行過(guò)程只花費(fèi)0.00 sec

接下來(lái)是上文的第二種場(chǎng)景，索引只用于ORDER BY子句，這即是索引掃描排序：
我們可以繼續(xù)使用上文的SQL，通過(guò)FORCE INDEX子句強(qiáng)制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已經(jīng)沒(méi)了，但是掃過(guò)的rows大概有998056行(準(zhǔn)確的值應(yīng)該是1000000行，InnoDB這一列只是估值)。這是因?yàn)樗饕糜?strong>ORDER BY子句時(shí)，會(huì)直接遍歷該索引的葉子節(jié)點(diǎn)鏈表，而不像第一種場(chǎng)景那樣從B+樹(shù)的根節(jié)點(diǎn)出發(fā) 往下查找。執(zhí)行流程如下：

從create_time索引的第一個(gè)葉子節(jié)點(diǎn)出發(fā)，按順序掃描所有葉子節(jié)點(diǎn)

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

整個(gè)時(shí)間復(fù)雜度是O(M*logN)，M是主鍵id的總數(shù)，N是聚簇索引葉子節(jié)點(diǎn)的個(gè)數(shù)(數(shù)據(jù)頁(yè)的個(gè)數(shù))
本例中M的值為1000000，所以整個(gè)執(zhí)行過(guò)程比第一種場(chǎng)景花了更多時(shí)間，同一臺(tái)機(jī)器上耗時(shí)1.34 sec

上述兩個(gè)例子恰好說(shuō)明了另一個(gè)道理：在某些場(chǎng)景下使用filesort比不使用filesort 效率更高。

第三種情況發(fā)生在WHERE子句與ORDER BY子句能使用相同的索引時(shí)（如: WHERE userid > xxx ORDER BY userid），這樣就能省去第二種情況的回表查詢操作了。
因此，如果可能，設(shè)計(jì)索引時(shí)應(yīng)該盡可能地同時(shí)滿足這兩種任務(wù)，這樣是最好的。 ----《高性能MySQL》

關(guān)于filesort上文其實(shí)已經(jīng)介紹過(guò)了一些。
filesort的名字起得很費(fèi)解，讓人誤以為它會(huì)：將一張非常大的表放入磁盤(pán)再進(jìn)行排序。其實(shí)不是這樣的，filesort僅僅是排序而已，是否會(huì)放入磁盤(pán)看情況而定（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》中對(duì)filesort的介紹：

如果需要排序的數(shù)據(jù)量小于“排序緩沖區(qū)”，MySQL使用內(nèi)存進(jìn)行“快速排序”操作。如果內(nèi)存不夠排序，那么MySQL會(huì)先將數(shù)據(jù)分塊，可對(duì)每個(gè)獨(dú)立的塊使用“快速排序”進(jìn)行排序，再將各個(gè)塊的排序結(jié)果放到磁盤(pán)上，然后將各個(gè)排好序的塊進(jìn)行“歸并排序”，最后返回排序結(jié)果。

所以filesort是否會(huì)使用磁盤(pán)取決于它操作的數(shù)據(jù)量大小。

總結(jié)來(lái)說(shuō)就是，filesort按排序方式來(lái)劃分 分為兩種：

1.數(shù)據(jù)量小時(shí)，在內(nèi)存中快排

2.數(shù)據(jù)量大時(shí)，在內(nèi)存中分塊快排，再在磁盤(pán)上將各個(gè)塊做歸并

數(shù)據(jù)量大的情況下涉及到磁盤(pán)io，所以效率會(huì)低一些。

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

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

2.回表讀取一次數(shù)據(jù)(single-pass)：?jiǎn)未蝹鬏斉判?/p> 兩次傳輸排序

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

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

EXPLAIN 
SELECT * 
    FROM order_detail
        WHERE create_time >= "2018-08-11 00:00:00" and create_time < "2018-08-12 00:00:00" 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 |
+------+-------------+--------------+-------+--------------------+-------------+---------+------+------+-----------------------------+

我們?cè)囍治鲆幌逻@個(gè)SQL的執(zhí)行過(guò)程：

利用create_time索引，對(duì)滿足WHERE子句create_time >= "2018-08-11 00:00:00" and create_time < "2018-08-12 00:00:00"的rowid進(jìn)行回表（第一次回表），回表之后可以拿到該rowid對(duì)應(yīng)的userid，若userid滿足userid > 140000的條件時(shí)，則將該行的rowid，money(ORDER BY的列)放入排序緩沖區(qū)。

若排序緩沖區(qū)能放下所有rowid, money對(duì)，則直接在排序緩沖區(qū)（內(nèi)存）進(jìn)行快排。

若排序緩沖區(qū)不能放下所有rowid, money對(duì)，則分塊快排，將塊存入臨時(shí)文件（磁盤(pán)），再對(duì)塊進(jìn)行歸并排序。

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

熟悉計(jì)算機(jī)系統(tǒng)的人可以看出，第二次回表會(huì)表比第一次回表的效率低得多，因?yàn)榈谝淮位乇韼缀跏?strong>順序I/O；而由于rowid是根據(jù)money進(jìn)行排序的，第二次回表會(huì)按照rowid亂序去讀取行記錄，這些行記錄在磁盤(pán)中的存儲(chǔ)是分散的，每讀一行 磁盤(pán)都可能會(huì)產(chǎn)生尋址時(shí)延（磁臂移動(dòng)到指定磁道）+旋轉(zhuǎn)時(shí)延（磁盤(pán)旋轉(zhuǎn)到指定扇區(qū)），這即是隨機(jī)I/O。

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

還是上面那條SQL，我們?cè)倏纯磫未蝹鬏斉判虻膱?zhí)行過(guò)程：

利用create_time索引，對(duì)滿足WHERE子句create_time >= "2018-08-11 00:00:00" and create_time < "2018-08-12 00:00:00"的rowid進(jìn)行回表（第一次回表），回表之后可以拿到改rowid對(duì)應(yīng)的userid，若userid滿足userid > 140000的條件時(shí)，則將此次查詢用到該行的所有列（包括ORDER BY列）取出作為一個(gè)數(shù)據(jù)元組(tuple)，放入排序緩沖區(qū)。

若排序緩沖區(qū)能放下所有tuples，則直接在排序緩沖區(qū)（內(nèi)存）進(jìn)行快排。

若排序緩沖區(qū)不能放下所有tuples，則分塊快排，將塊存入臨時(shí)文件（磁盤(pán)），再對(duì)塊進(jìn)行歸并排序。

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

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

當(dāng)然，列數(shù)據(jù)量太大的情況不是特別常見(jiàn)，所以MySQL的filesort會(huì)盡可能使用單次傳輸排序，但是為了防止上述情況發(fā)生，MySQL做了以下限制：

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

所有需要的列和ORDER BY的列總大小超過(guò)max_length_for_sort_data字節(jié)，則使用兩次傳輸排序。

我們開(kāi)發(fā)者也應(yīng)該盡可能讓filesort使用單次傳輸排序，不過(guò)EXPLAIN不會(huì)告訴我們這個(gè)信息，所以我們只能肉眼檢查各列的大小看看是否會(huì)觸發(fā)上面兩個(gè)限制 導(dǎo)致兩次傳輸排序的發(fā)生。

如第3小節(jié)所述，既然filesort的效率未必比索引掃描排序低，為什么很多人會(huì)想避免filesort呢？
谷歌一下using filesort，幾乎都是"如何避免filesort"相關(guān)的內(nèi)容。:

這是因?yàn)橥ǔ?strong>ORDER BY子句會(huì)與LIMIT子句配合，只取出部分行。如果只是為了取出top1的行 卻對(duì)所有行進(jìn)行排序，這顯然不是一種高效的做法。這種場(chǎng)景下 按順序取的索引掃描排序可能會(huì)比filesort擁有更好性能（當(dāng)然也有例外）。

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會(huì)幫我們選擇一種高效的ORDER BY方式。
但也不能完全依賴optimizer的判斷，這時(shí)合理建立索引、引導(dǎo)它使用指定索引可能是更好的選擇。

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技術(shù)內(nèi)幕:InnoDB存儲(chǔ)引擎(第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