0 索引

• 1 概述
• 2 索引掃描排序和文件排序簡(jiǎn)介
• 3 索引掃描排序執(zhí)行過(guò)程分析
• 4 文件排序
• 5 補(bǔ)充說(shuō)明
• 6 參考資料

1 概述

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

• 1.通過(guò)索引掃描生成有序的結(jié)果
• 2.使用文件排序(filesort)

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

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

我們知道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順序插入)

圖1

現(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ì)介紹這兩種排序方式罚渐。

3 索引掃描排序執(zhí)行過(guò)程分析

介紹索引掃描排序之前却汉，先看看索引的用途
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正序返回窑眯。

場(chǎng)景一 索引只用于WHERE子句

寫(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í)表（時(shí)間復(fù)雜度為O(M*logN)独榴，M是臨時(shí)表的行數(shù)）
• 對(duì)臨時(shí)表進(jìn)行排序（時(shí)間復(fù)雜度O(M*logM)僧叉，M是臨時(shí)表的行數(shù))

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

場(chǎng)景二 索引只用于ORDER BY子句

接下來(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 效率更高。

場(chǎng)景三 索引既用于WHERE又用于ORDER BY

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

4 文件排序(filesort)

關(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)未蝹鬏斉判?/li>

兩次傳輸排序

兩次傳輸排序會(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ù)使用。我們稱(chēng)之為單次傳輸排序澈魄。

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

還是上面那條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)銷(xiāo)。所以列數(shù)據(jù)量太大時(shí)筛谚，單次傳輸排序的效率可能還不如兩次傳輸排序磁玉。

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

• 所有需要的列或ORDER BY的列只要是BLOB或者TEXT類(lèi)型吮铭，則使用兩次傳輸排序时迫。
• 所有需要的列和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ā)生纸肉。

5 補(bǔ)充說(shuō)明

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

圖2

這是因?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方式扇商。
但也不能完全依賴(lài)optimizer的判斷凤瘦，這時(shí)合理建立索引、引導(dǎo)它使用指定索引可能是更好的選擇案铺。

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技術(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