算法的藝術(shù)：MySQL order by對(duì)各種排序算法的巧用
這篇文章我們從比較宏觀的角度來(lái)看MySQL中關(guān)鍵字的原理。本文，我們主要探索order by語(yǔ)句的底層原理。閱讀完本文，您將了解到：
order by語(yǔ)句有哪些排序模式，以及每種排序模式的優(yōu)缺點(diǎn);
order by語(yǔ)句會(huì)用到哪些排序算法，在什么場(chǎng)景下會(huì)選擇哪種排序算法;
如何查看和分析sql的order by優(yōu)化手段(執(zhí)行計(jì)劃 + OPTIMIZER_TRACE日志);
如何優(yōu)化order by語(yǔ)句的執(zhí)行效率?(思想：減小行大小，盡量走索引，能夠走覆蓋索引最佳，可適當(dāng)增加sort buffer內(nèi)存大小)
這里我們從數(shù)據(jù)結(jié)構(gòu)的維度來(lái)看數(shù)據(jù)和索引，也就是都當(dāng)成B+樹(shù)的的，我們需要數(shù)據(jù)的時(shí)候再?gòu)拇鎯?chǔ)引擎的B+樹(shù)中讀取。
以下是我們本文作為演示例子的表，假設(shè)我們有如下表：
索引如下：
對(duì)應(yīng)的idx_d索引結(jié)構(gòu)如下(這里我們做了一些夸張的手法，讓一個(gè)頁(yè)數(shù)據(jù)變小，為了展現(xiàn)在索引樹(shù)中的查找流程)：
1、如何跟蹤執(zhí)行優(yōu)化
為了方便分析sql的執(zhí)行流程，我們可以在當(dāng)前session中開(kāi)啟 optimizer_trace:
- SET optimizer_trace='enabled=on';
然后執(zhí)行sql，執(zhí)行完之后，就可以通過(guò)以下堆棧信息查看執(zhí)行詳情了：
- SELECT * FROM information_schema.OPTIMIZER_TRACE\G;
以下是
- 1select a, b, c, d from t20 force index(idx_abc) where a=3 order by d limit 100,2;
的執(zhí)行結(jié)果，其中符合a=3的有8457條記錄，針對(duì)order by重點(diǎn)關(guān)注以下屬性：
- "filesort_priority_queue_optimization": { // 是否啟用優(yōu)先級(jí)隊(duì)列
- "limit": 102, // 排序后需要取的行數(shù)，這里為 limit 100,2，也就是100+2=102
- "rows_estimate": 24576, // 估計(jì)參與排序的行數(shù)
- "row_size": 123, // 行大小
- "memory_available": 32768, // 可用內(nèi)存大小，即設(shè)置的sort buffer大小
- "chosen": true // 是否啟用優(yōu)先級(jí)隊(duì)列
- },
- ...
- "filesort_summary": {
- "rows": 103, // 排序過(guò)程中會(huì)持有的行數(shù)
- "examined_rows": 8457, // 參與排序的行數(shù)，InnoDB層返回的行數(shù)
- "number_of_tmp_files": 0, // 外部排序時(shí)，使用的臨時(shí)文件數(shù)量
- "sort_buffer_size": 13496, // 內(nèi)存排序使用的內(nèi)存大小
- "sort_mode": "sort_key, additional_fields" // 排序模式
1.1、排序模式
其中 sort_mode有如下幾種形式：
- sort_key, rowid：表明排序緩沖區(qū)元組包含排序鍵值和原始表行的行id，排序后需要使用行id進(jìn)行回表，這種算法也稱(chēng)為original filesort algorithm(回表排序算法);
- sort_key, additional_fields：表明排序緩沖區(qū)元組包含排序鍵值和查詢(xún)所需要的列，排序后直接從緩沖區(qū)元組取數(shù)據(jù)，無(wú)需回表，這種算法也稱(chēng)為modified filesort algorithm(不回表排序);
- sort_key, packed_additional_fields：類(lèi)似上一種形式，但是附加的列(如varchar類(lèi)型)緊密地打包在一起，而不是使用固定長(zhǎng)度的編碼。
如何選擇排序模式
選擇哪種排序模式，與max_length_for_sort_data這個(gè)屬性有關(guān)，這個(gè)屬性默認(rèn)值大小為1024字節(jié)：
- 如果查詢(xún)列和排序列占用的大小超過(guò)這個(gè)值，那么會(huì)轉(zhuǎn)而使用sort_key, rowid模式;
- 如果不超過(guò)，那么所有列都會(huì)放入sort buffer中，使用sort_key, additional_fields或者sort_key, packed_additional_fields模式;
- 如果查詢(xún)的記錄太多，那么會(huì)使用sort_key, packed_additional_fields對(duì)可變列進(jìn)行壓縮。
1.2、排序算法
基于參與排序的數(shù)據(jù)量的不同，可以選擇不同的排序算法：
- 如果排序取的結(jié)果很小，小于內(nèi)存，那么會(huì)使用優(yōu)先級(jí)隊(duì)列進(jìn)行堆排序;
- 例如，以下只取了前面10條記錄，會(huì)通過(guò)優(yōu)先級(jí)隊(duì)列進(jìn)行排序：
- select a, b, c, d from t20 force index(idx_abc) where a=3 order by d limit 10;
- 如果排序limit n, m，n太大了，也就是說(shuō)需要取排序很后面的數(shù)據(jù)，那么會(huì)使用sort buffer進(jìn)行快速排序：
- 如下，表中a=1的數(shù)據(jù)有三條，但是由于需要limit到很后面的記錄，MySQL會(huì)對(duì)比優(yōu)先級(jí)隊(duì)列排序和快速排序的開(kāi)銷(xiāo)，選擇一個(gè)比較合適的排序算法，這里最終放棄了優(yōu)先級(jí)隊(duì)列，轉(zhuǎn)而使用sort buffer進(jìn)行快速排序：
- select a, b, c, d from t20 force index(idx_abc) where a=1 order by d limit 300,2;
- 如果參與排序的數(shù)據(jù)sort buffer裝不下了，那么我們會(huì)一批一批的給sort buffer進(jìn)行內(nèi)存快速排序，結(jié)果放入排序臨時(shí)文件，最終使對(duì)所有排好序的臨時(shí)文件進(jìn)行歸并排序，得到最終的結(jié)果;
- 如下，a=3的記錄超過(guò)了sort buffer，我們要查找的數(shù)據(jù)是排序后1000行起，sort buffer裝不下1000行數(shù)據(jù)了，最終MySQL選擇使用sort buffer進(jìn)行分批快排，把最終結(jié)果進(jìn)行歸并排序：
- select a, b, c, d from t20 force index(idx_abc) where a=3 order by d limit 1000,10;
2、order by走索引避免排序
執(zhí)行如下sql：
- select a, b, c, d from t20 force index(idx_d) where d like 't%' order by d limit 2;
我們看一下執(zhí)行計(jì)劃：
發(fā)現(xiàn)Extra列為：Using index condition，也就是這里只走了索引。
執(zhí)行流程如下圖所示：
通過(guò)idx_d索引進(jìn)行range_scan查找，掃描到4條記錄，然后order by繼續(xù)走索引，已經(jīng)排好序，直接取前面兩條，然后去聚集索引查詢(xún)完整記錄，返回最終需要的字段作為查詢(xún)結(jié)果。這個(gè)過(guò)程只需要借助索引。
如何查看和修改sort buffer大小?
我們看一下當(dāng)前的sort buffer大?。?/p>
可以發(fā)現(xiàn)，這里默認(rèn)配置了sort buffer大小為512k。
我們可以設(shè)置這個(gè)屬性的大?。?/p>
- SET GLOBAL sort_buffer_size = 32*1024;
- 或者
- SET sort_buffer_size = 32*1024;
下面我們統(tǒng)一把sort buffer設(shè)置為32k
- SET sort_buffer_size = 32*1024;
3、排序算法案例
3.1、使用優(yōu)先級(jí)隊(duì)列進(jìn)行堆排序
如果排序取的結(jié)果很小，并且小于sort buffer，那么會(huì)使用優(yōu)先級(jí)隊(duì)列進(jìn)行堆排序;
例如，以下只取了前面10條記錄：
- select a, b, c, d from t20 force index(idx_abc) where a=3 order by d limit 10;
a=3的總記錄數(shù)：8520。查看執(zhí)行計(jì)劃：
發(fā)現(xiàn)這里where條件用到了索引，order by limit用到了排序。我們進(jìn)一步看看執(zhí)行的optimizer_trace日志：
- "filesort_priority_queue_optimization": {
- "limit": 10,
- "rows_estimate": 27033,
- "row_size": 123,
- "memory_available": 32768,
- "chosen": true // 使用優(yōu)先級(jí)隊(duì)列進(jìn)行排序
- },
- "filesort_execution": [
- ],
- "filesort_summary": {
- "rows": 11,
- "examined_rows": 8520,
- "number_of_tmp_files": 0,
- "sort_buffer_size": 1448,
- "sort_mode": "sort_key, additional_fields"
- }
發(fā)現(xiàn)這里是用到了優(yōu)先級(jí)隊(duì)列進(jìn)行排序。排序模式是：sort_key, additional_fields，即先回表查詢(xún)完整記錄，把排序需要查找的所有字段都放入sort buffer進(jìn)行排序。
所以這個(gè)執(zhí)行流程如下圖所示：
- 通過(guò)where條件a=3掃描到8520條記錄;
- 回表查找記錄;
- 把8520條記錄中需要的字段放入sort buffer中;
- 在sort buffer中進(jìn)行堆排序;
- 在排序好的結(jié)果中取limit 10前10條，寫(xiě)入net buffer，準(zhǔn)備發(fā)送給客戶(hù)端。
3.2、內(nèi)部快速排序
如果排序limit n, m，n太大了，也就是說(shuō)需要取排序很后面的數(shù)據(jù)，那么會(huì)使用sort buffer進(jìn)行快速排序。MySQL會(huì)對(duì)比優(yōu)先級(jí)隊(duì)列排序和歸并排序的開(kāi)銷(xiāo)，選擇一個(gè)比較合適的排序算法。
如何衡量究竟是使用優(yōu)先級(jí)隊(duì)列還是內(nèi)存快速排序?
一般來(lái)說(shuō)，快速排序算法效率高于堆排序，但是堆排序?qū)崿F(xiàn)的優(yōu)先級(jí)隊(duì)列，無(wú)需排序完所有的元素，就可以得到order by limit的結(jié)果。
MySQL源碼中聲明了快速排序速度是堆排序的3倍，在實(shí)際排序的時(shí)候，會(huì)根據(jù)待排序數(shù)量大小進(jìn)行切換算法。如果數(shù)據(jù)量太大的時(shí)候，會(huì)轉(zhuǎn)而使用快速排序。
有如下SQL：
- select a, b, c, d from t20 force index(idx_abc) where a=1 order by d limit 300,2;
我們把sort buffer設(shè)置為32k：
- SET sort_buffer_size = 32*1024;
其中a=1的記錄有3條。查看執(zhí)行計(jì)劃：
可以發(fā)現(xiàn)，這里where條件用到了索引，order by limit 用到了排序。我們進(jìn)一步看看執(zhí)行的optimizer_trace日志：
- "filesort_priority_queue_optimization": {
- "limit": 302,
- "rows_estimate": 27033,
- "row_size": 123,
- "memory_available": 32768,
- "strip_additional_fields": {
- "row_size": 57,
- "sort_merge_cost": 33783,
- "priority_queue_cost": 61158,
- "chosen": false // 對(duì)比發(fā)現(xiàn)快速排序開(kāi)銷(xiāo)成本比優(yōu)先級(jí)隊(duì)列更低，這里不適用優(yōu)先級(jí)隊(duì)列
- }
- },
- "filesort_execution": [
- ],
- "filesort_summary": {
- "rows": 3,
- "examined_rows": 3,
- "number_of_tmp_files": 0,
- "sort_buffer_size": 32720,
- "sort_mode": "<sort_key, packed_additional_fields>"
- }
可以發(fā)現(xiàn)這里最終放棄了優(yōu)先級(jí)隊(duì)列，轉(zhuǎn)而使用sort buffer進(jìn)行快速排序。
所以這個(gè)執(zhí)行流程如下圖所示：
- 通過(guò)where條件a=1掃描到3條記錄;
- 回表查找記錄;
- 把3條記錄中需要的字段放入sort buffer中;
- 在sort buffer中進(jìn)行快速排序;
- 在排序好的結(jié)果中取limit 300, 2第300、301條記錄，寫(xiě)入net buffer，準(zhǔn)備發(fā)送給客戶(hù)端。
3.3、外部歸并排序
當(dāng)參與排序的數(shù)據(jù)太多，一次性放不進(jìn)去sort buffer的時(shí)候，那么我們會(huì)一批一批的給sort buffer進(jìn)行內(nèi)存排序，結(jié)果放入排序臨時(shí)文件，最終使對(duì)所有排好序的臨時(shí)文件進(jìn)行歸并排序，得到最終的結(jié)果。
有如下sql：
- select a, b, c, d from t20 force index(idx_abc) where a=3 order by d limit 1000,10;
其中a=3的記錄有8520條。執(zhí)行計(jì)劃如下：
image-20200614171147989
可以發(fā)現(xiàn)，這里where用到了索引，order by limit用到了排序。進(jìn)一步查看執(zhí)行的optimizer_trace日志：
- "filesort_priority_queue_optimization": {
- "limit": 1010,
- "rows_estimate": 27033,
- "row_size": 123,
- "memory_available": 32768,
- "strip_additional_fields": {
- "row_size": 57,
- "chosen": false,
- "cause": "not_enough_space" // sort buffer空間不夠，無(wú)法使用優(yōu)先級(jí)隊(duì)列進(jìn)行排序了
- }
- },
- "filesort_execution": [
- ],
- "filesort_summary": {
- "rows": 8520,
- "examined_rows": 8520,
- "number_of_tmp_files": 24, // 用到了24個(gè)外部文件進(jìn)行排序
- "sort_buffer_size": 32720,
- "sort_mode": "<sort_key, packed_additional_fields>"
- }
我們可以看到，由于limit 1000，要返回排序后1000行以后的記錄，顯然sort buffer已經(jīng)不能支撐這么大的優(yōu)先級(jí)隊(duì)列了，所以轉(zhuǎn)而使用sort buffer內(nèi)存排序，而這里需要在sort buffer中分批執(zhí)行快速排序，得到多個(gè)排序好的外部臨時(shí)文件，最終執(zhí)行歸并排序。(外部臨時(shí)文件的位置由tmpdir參數(shù)指定)
其流程如下圖所示：
4、排序模式案例
4.1、sort_key, additional_fields模式
sort_key, additional_fields，排序緩沖區(qū)元組包含排序鍵值和查詢(xún)所需要的列(先回表取需要的數(shù)據(jù)，存入排序緩沖區(qū)中)，排序后直接從緩沖區(qū)元組取數(shù)據(jù)，無(wú)需再次回表。
上面 2.3.1、2.3.2節(jié)的例子都是這種排序模式，就不繼續(xù)舉例了。
4.2、模式
sort_key, packed_additional_fields：類(lèi)似上一種形式，但是附加的列(如varchar類(lèi)型)緊密地打包在一起，而不是使用固定長(zhǎng)度的編碼。
上面2.3.3節(jié)的例子就是這種排序模式，由于參與排序的總記錄大小太大了，因此需要對(duì)附加列進(jìn)行緊密地打包操作，以節(jié)省內(nèi)存。
4.3、模式
前面我們提到，選擇哪種排序模式，與max_length_for_sort_data[2]這個(gè)屬性有關(guān)，max_length_for_sort_data規(guī)定了排序行的最大大小，這個(gè)屬性默認(rèn)值大小為1024字節(jié)：
也就是說(shuō)如果查詢(xún)列和排序列占用的大小小于這個(gè)值，這個(gè)時(shí)候會(huì)走sort_key, additional_fields或者sort_key, packed_additional_fields算法，否則，那么會(huì)轉(zhuǎn)而使用sort_key, rowid模式。
現(xiàn)在我們特意把這個(gè)值設(shè)置小一點(diǎn)，模擬sort_key, rowid模式：
- SET max_length_for_sort_data = 100;
這個(gè)時(shí)候執(zhí)行sql：
- select a, b, c, d from t20 force index(idx_abc) where a=3 order by d limit 10;
這個(gè)時(shí)候再查看sql執(zhí)行的optimizer_trace日志：
- "filesort_priority_queue_optimization": {
- "limit": 10,
- "rows_estimate": 27033,
- "row_size": 49,
- "memory_available": 32768,
- "chosen": true
- },
- "filesort_execution": [
- ],
- "filesort_summary": {
- "rows": 11,
- "examined_rows": 8520,
- "number_of_tmp_files": 0,
- "sort_buffer_size": 632,
- "sort_mode": "<sort_key, rowid>"
可以發(fā)現(xiàn)這個(gè)時(shí)候切換到了sort_key, rowid模式，在這個(gè)模式下，執(zhí)行流程如下：
- where條件a=3掃描到8520條記錄;
- 回表查找記錄;
- 找到這8520條記錄的id和d字段，放入sort buffer中進(jìn)行堆排序;
- 排序完成后，取前面10條;
- 取這10條的id回表查詢(xún)需要的a，b，c，d字段值;
- 依次返回結(jié)果給到客戶(hù)端。
可以發(fā)現(xiàn)，正因?yàn)樾杏涗浱罅耍詓ort buffer中只存了需要排序的字段和主鍵id，以時(shí)間換取空間，最終排序完成，再次從聚集索引中查找到所有需要的字段返回給客戶(hù)端，很明顯，這里多了一次回表操作的磁盤(pán)讀，整體效率上是稍微低一點(diǎn)的。
5、order by優(yōu)化總結(jié)
根據(jù)以上的介紹，我們可以總結(jié)出以下的order by語(yǔ)句的相關(guān)優(yōu)化手段：
- order by字段盡量使用固定長(zhǎng)度的字段類(lèi)型，因?yàn)榕判蜃侄尾恢С謮嚎s;
- order by字段如果需要用可變長(zhǎng)度，應(yīng)盡量控制長(zhǎng)度，道理同上;
- 查詢(xún)中盡量不用用select *，避免查詢(xún)過(guò)多，導(dǎo)致order by的時(shí)候sort buffer內(nèi)存不夠?qū)е峦獠颗判?，或者行大小超過(guò)了max_length_for_sort_data導(dǎo)致走了sort_key, rowid排序模式，使得產(chǎn)生了更多的磁盤(pán)讀，影響性能;
- 嘗試給排序字段和相關(guān)條件加上聯(lián)合索引，能夠用到覆蓋索引最佳。
References
[1]: 滴滴云. MySQL 全表 COUNT(*) 簡(jiǎn)述. zhihu.com. Retrieved from https://zhuanlan.zhihu.com/p/54378839
[2]: MySQL. 8.2.1.14 ORDER BY Optimization. Retrieved from https://dev.mysql.com/doc/refman/5.7/en/order-by-optimization.html
[3]: MySQL：排序(filesort)詳細(xì)解析. Retrieved from https://www.jianshu.com/p/069428a6594e
[4]: MYSQL實(shí)現(xiàn)ORDER BY LIMIT的方法以及優(yōu)先隊(duì)列(堆排序). Retrieved from http://blog.itpub.net/7728585/viewspace-2130920/
本文轉(zhuǎn)載自微信公眾號(hào)「Java架構(gòu)雜談」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java架構(gòu)雜談公眾號(hào)。
博客地址：https://www.itzhai.com
