作者： vivo 互聯網服務器團隊- Li Xin
本文通過一個線上慢SQL案例，介紹了Join的兩種算法和Order by的工作原理，並通過Explain和Optimizer_trace工具完整推演了慢SQL的執行過程。基於對原理和執行過程的分析，本文給出一種“引導執行引擎選擇效率更高的算法”的方案，從而使查詢性能得到大幅提升。
1、線上慢 SQL 背景
慢 SQL 會影響用户使用體驗，降低數據庫的整體性能，嚴重的甚至會導致服務器掛掉、整個系統癱瘓。筆者通過監控平台發現線上存在這樣一條慢SQL（原始SQL已脱敏，表結構出於簡化的目的做了一定刪減，實際執行耗時以文中提供數據為準），其執行耗時在分鐘級。
select t1.*,t2.x from t_table1 t1 leftjoin t_table2 t2 on t1.a = t2.a orderby t1.c desc;
表結構如下：
CREATETABLE `t_table1` (
`id` bigint(20) unsigned NOTNULL AUTO_INCREMENT COMMENT '主鍵',
`a` varchar(64) NOTNULL,
`b` varchar(64) NOTNULL,
`c` varchar(20) NOTNULL,
PRIMARYKEY (`id`),
KEY `idx_a` (`a`)
) ENGINE=InnoDB AUTO_INCREMENT=0DEFAULT CHARSET=utf8mb4;
CREATETABLE `t_table2` (
`id` bigint(20) unsigned NOTNULL AUTO_INCREMENT COMMENT '主鍵',
`a` varchar(64) NOTNULL,
`x` varchar(64) NOTNULL,
`y` varchar(20) NOTNULL,
PRIMARYKEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=0DEFAULT CHARSET=utf8mb4;
其他信息：
當發現慢SQL時，筆者的第一反應是使用Explain查看SQL的執行計劃，結果如下：
通過Explain初步分析：兩張表均執行了全表掃描，結合兩張表的數據規模分析全表掃描並非耗時達到分鐘級的主要原因。另外執行計劃extra種提示的Using temporary; Using filesort; Using join buffer (Block Nested Loop)又分別代表什麼含義呢？
2、原理探究
2.1 Join 算法原理
2.1.1 驅動表和被驅動表
在Join語句中，執行引擎優先掃描的表被稱為驅動表，另一張表被稱為被驅動表。執行引擎在選擇驅動表時，除了必須要遵守的特定語義外，最重要的考慮便是執行效率。
首先列舉兩種特定語義約束驅動表選取的場景：
場景一：Straight join指定連接順序，強制要求執行引擎優先掃描左側的表。
場景二：Left/Right [outer] join，方向連接的特點是反方向表中如果不存在關聯的數據則填充NULL值，這一特性要求方向查詢時優先掃描相同方向的表。倘若where條件中明確指明反方向表中的部分列非空，則驅動表的選擇就不受此語義的限制，執行引擎會依據效率選取驅動表。
當沒有特定語義的約束時，執行引擎便會依據執行效率選取驅動表，如何判斷哪張表作為驅動表的效率更高呢？下文會結合Join的兩種算法更深入地探討這個問題。
2.1.2 Block Nested-Loop Join
假設一個數據量為m行的驅動表與一個數據量為n行的被驅動表進行join查詢。
最簡單的一種算法：
- 從驅動表掃描一行數據；
- 對被驅動表進行全表掃描，得到的結果依次與驅動表的數據進行join並把滿足條件的數據加入結果集；
- 接着掃描驅動表，每掃描一行數據，均重複執行一次步驟2，直至驅動表的全部數據被掃描完畢。
這種算法的磁盤掃描開銷為m*n，非常低效，MySQL在實際中並未直接使用該算法，而是採用緩存的思想（分配一塊Join buffer）對該算法進行改進，並命名為Block Nested-Loop join(BNL)。
BNL的算法步驟為：
- 從驅動表一次掃描K條數據，並把數據緩存在Join buffer；
- 對被驅動表進行全表掃描，得到的結果依次與驅動表的K條數據進行join並把滿足條件的數據加入結果集；
- 清空join_buffer；
- 接着從驅動表再取出K條數據，重複步驟2、3，直至掃描完驅動表的全部數據。
上述算法中，驅動表分段取數的次數記為l，整個算法的磁盤掃描開銷為m+ln。由於分段的次數與驅動表的數據成正相關，所以公式可以記為m+λmn，λ的取值範圍為(0,1)。
當兩張表的行數（m、n大小）固定的情況下，m對結果的影響更大，m越小整體掃描的代價越小，所以執行引擎優先選擇數據量更小的表作為驅動表(符合“小表驅動大表”的説法)。
2.1.3 Index Nested-Loop Join
BNL算法使用了Join buffer結構，雖然有可能通過減少重複掃描來降低磁盤掃描開銷，然而驅動表分段掃描的次數過多依然可能會導致查詢的低效。索引是MySQL查詢提效的重要結構，當被驅動表的關聯鍵存在索引時，MySQL會使用Index Nested-Loop Join（NLJ）算法。
該算法的步驟為：
- 從驅動表掃描一行數據；
- 使用驅動表的關聯鍵搜索被驅動表的索引樹，通過被驅動表的索引結構找到被驅動表的主鍵，再通過主鍵回表查詢出被驅動表的關聯數據（暫不考慮覆蓋索引的情況）；
- 接着掃描驅動表，每掃描一行數據，均重複執行一次步驟2，直至驅動表的全部數據被掃描完畢。
每次搜索一棵樹的複雜度近似為log2 n，上述過程在被驅動表掃描一行數據的時間複雜度是2log2 n，算法的整體複雜度為m+2mlog2 n，在該算法中，依舊是m對結果的影響更大，m越小整體掃描的代價越小，所以執行引擎總是選擇數據量更小的表作為驅動表(符合“小表驅動大表”的説法)。
2.2 Order by 算法原理
2.2.1 全字段排序
MySQL會為每個線程分配一塊內存（Sort buffer）用於排序，當Sort buffer的空間不足時（通過系統參數sort_buffer_size設置Sort buffer的大小），執行引擎不得不開闢磁盤臨時文件用於排序，此時排序的性能也會大幅降低。
全字段排序是將查詢需要的所有字段進行暫存，並按照排序字段進行排序，並將排序後的結果集直接返回。
2.2.2 Rowid 排序
若要查詢的數據單行佔用空間較大，Sort buffer中可以容納的排序行數將會減少，此時使用磁盤臨時文件進行排序的概率將會增大。為了提高排序性能，執行引擎提供一種只存儲排序字段的算法，稱為Rowid排序算法。
該算法的步驟為：
- 將參與排序的字段和主鍵進行臨時存儲；
- 按照排序字段進行排序，得到有序的主鍵；
- 根據有序的主鍵進行回表，按順序將所有要查詢的數據返回。
Rowid排序在單行查詢數據較大時可以通過節省臨時排序空間從而達到降低排序開銷的目的，然而該算法的代價是會增加磁盤掃描的次數（主鍵回表），所以是否選擇使用該算法需要根據實際情況進行取捨（通過系統參數max_length_for_sort_data設置）。
3、調優過程
3.1 執行過程分析
瞭解了Join和Order by的工作原理，我們推測執行計劃的大致過程為：
- t_table_1與t_table_2進行Join查詢，使用了BNL算法（Using join buffer (Block Nested Loop)）
- 將Join的結果暫存臨時表（Using temporary）
- 對臨時表中的數據進行排序後返回（Using filesort）
為了佐證筆者的推測以及瞭解每一步的開銷情況，Optimizer_trace命令可以提供更多執行過程細節。
{
"considered_execution_plans": [
{
"table": "`t_table1` `t1`",
"best_access_path": {
"considered_access_paths": [
{
"rows_to_scan": 3000,
"access_type": "scan",
"resulting_rows": 3000,
"cost": 615,
"chosen": true,
"use_tmp_table": true
}
] /* considered_access_paths */
} /* best_access_path */,
"rest_of_plan": [
{
"table": "`t_table2` `t2`",
"best_access_path": {
"considered_access_paths": [
{
"rows_to_scan": 69882,
"access_type": "scan",
"using_join_cache": true,
"buffers_needed": 5,
"resulting_rows": 69882,
"cost": 4.19e7,
"chosen": true
}
] /* considered_access_paths */
} /* best_access_path */,
"rows_for_plan": 2.1e8,
"cost_for_plan": 4.19e7,
"sort_cost": 2.1e8,
"new_cost_for_plan": 2.52e8,
"chosen": true
}
] /* rest_of_plan */
}
] /* considered_execution_plans */
}
上圖展示的即為執行引擎預估的執行計劃，從Optimizer_trace的輸出結果中可以佐證上述對於執行過程的推測。另外我們可以得到執行代價的結果為：
- t_table1的掃描行數為3000，代價為615;
- t_table2的掃描行數為69882，由於BNL算法t_table2會被多次全表掃描，整體代價為4.19e7;
- 對Join結果進行排序的開銷為2.1e8。
從執行引擎預估的執行計劃可以看出執行引擎認為排序的開銷最大，另外由於使用BNL算法會導致被驅動表執行多次全表掃描，其執行代價僅次於排序。然而預估的執行計劃並不代表真正的執行結果，下面展示Optimizer_trace命令對於真實執行結果部分參數：
{
"join_execution": {
"select#": 1,
"steps": [
{
"creating_tmp_table": {
"tmp_table_info": {
"table": "intermediate_tmp_table",
"row_length": 655,
"key_length": 0,
"unique_constraint": false,
"location": "memory (heap)",
"row_limit_estimate": 25614
} /* tmp_table_info */
} /* creating_tmp_table */
},
{
"filesort_summary": {
"rows": 3000,
"examined_rows": 3000,
"number_of_tmp_files": 0,
"sort_buffer_size": 60200,
"sort_mode": "<sort_key, rowid>"
} /* filesort_summary */
}
] /* steps */
} /* join_execution */
}
從執行結果參數來看：
- 執行引擎使用臨時表保存Join的結果，且臨時表是一張內存表。
- 參與排序的數據行數為3000行，沒有使用磁盤臨時文件進行排序，排序算法選擇的是Rowid排序。
綜合執行引擎的預估的執行計劃和真實的執行結果參數可以得出，執行引擎預估最大的執行開銷為排序，但實際上排序並未使用到磁盤臨時文件，且Rowid排序的回表操作是在內存中進行的（在內存臨時表中進行回表），3000條數據的內存排序開銷是極快的，所以真實的最大開銷是BNL算法導致的對被驅動表多次進行全表掃描的開銷。
3.2 最終的優化
對於BNL算法，可以通過在被驅動表添加索引使其轉化為NLJ算法來進行優化（此處注意一些索引失效的場景，筆者在實際調優中遇到了字符集不同導致的索引失效場景）。在t_table2表添加索引後，觀察一週內的SQL監控如下，可以看到SQL最大響應時間不超過20ms，執行效率得到了大幅提升。
4、總結
本文完整的介紹了一個SQL調優案例，通過這個案例可以歸納出SQL調優的基本思想。首先，需要了解SQL語句中的關鍵字（Join、Order by...）的基本工作原理，並輔助一些執行過程數據（Explain、Optimizer_trace），通過實驗驗證猜想，最終達成調優的目的。
