這篇文章主要介紹了探究MySQL優化器對索引和JOIN順序的選擇,包括在優化器做出錯誤判斷時的選擇情況,需要的朋友可以參考下

本文通過一個案例來看看MySQL優化器如何選擇索引和JOIN順序。表結構和數據準備參考本文最后部分"測試環境"。這里主要介紹MySQL優化器的主要執行流程，而不是介紹一個優化器的各個組件(這是另一個話題)。

我們知道，MySQL優化器只有兩個自由度：順序選擇;單表訪問方式;這里將詳細剖析下面的SQL，看看MySQL優化器如何做出每一步的選擇。

1. explain 
2. select * 
3. from 
4. employee as A,department as B 
5. where 
6. A.LastName = 'zhou' 
7. and B.DepartmentID = A.DepartmentID 
8. and B.DepartmentName = 'TBX'; 

1. 可能的選擇

這里看到JOIN的順序可以是A|B或者B|A，單表訪問方式也有多種，對于A表可以選擇：全表掃描和索引`IND_L_D`(A.LastName = 'zhou')或者`IND_DID`(B.DepartmentID = A.DepartmentID)。對于B也有三個選擇：全表掃描、索引IND_D、IND_DN。

2. MySQL優化器如何做 2.1 概述

MySQL優化器主要工作包括以下幾部分：Query Rewrite(包括Outer Join轉換等)、const table detection、range analysis、JOIN optimization(順序和訪問方式選擇)、plan refinement。這個案例從range analysis開始。

2.2 range analysis

這部分包括所有Range和index merge成本評估(參考1 參考2)。這里，等值表達式也是一個range，所以這里會評估其成本，計算出found records(表示對應的等值表達式，大概會選擇出多少條記錄)。

本案例中，range analysis會針對A表的條件A.LastName = 'zhou'和B表的B.DepartmentName = 'TBX'分別做分析。其中：

表A A.LastName = 'zhou' found records: 51

表B B.DepartmentName = 'TBX' found records: 1

這兩個條件都不是range，但是這里計算的值仍然會存儲，在后面的ref訪問方式評估的時候使用。這里的值是根據records_in_range接口返回，而對于InnoDB每次調用這個函數都會進行一次索引頁的采樣，這是一個很消耗性能的操作，對于很多其他的關系數據庫是使用"直方圖"的統計數據來避免這次操作(相信MariaDB后續版本也將實現直方圖統計信息)。

2.3 順序和訪問方式的選擇：窮舉

MySQL通過枚舉所有的left-deep樹(也可以說所有的left-deep樹就是整個MySQL優化器的搜索空間)，來找到最優的執行順序和訪問方式。

2.3.1 排序

優化器先根據found records對所有表進行一個排序，記錄少的放前面。所以，這里順序是B、A。

2.3.2 greedy search

當表的數量較少(少于search_depth，默認是63)的時候，這里直接蛻化為一個窮舉搜索，優化器將窮舉所有的left-deep樹找到最優的執行計劃。另外，優化器為了減少因為搜索空間龐大帶來巨大的窮舉消耗，所以使用了一個"偷懶"的參數prune_level(默認打開)，具體如何"偷懶"，可以參考JOIN順序選擇的復雜度。不過至少需要有三個表以上的關聯才會有"偷懶"，所以本案例不適用。

2.3.3 窮舉

JOIN的第一個表可以是：A或者B;如果第一個表選擇了A，第二個表可以選擇B;如果第一個表選擇了B，第二個表可以選擇A;

因為前面的排序，B表的found records更少，所以JOIN順序窮舉時的第一個表先選擇B(這個是有講究的)。

(*) 選擇第一個JOIN的表為B

(**) 確定B表的訪問方式

因為B表為第一個表，所以無法使用索引IND_D(B.DepartmentID = A.DepartmentID)，而只能使用IND_DN(B.DepartmentName = 'TBX')

使用IND_DN索引的成本計算：1.2;其中IO成本為1。

是否使用全表掃描：這里會比較使用索引的IO成本和全表掃描的IO成本，前者為1，后者為2;所以忽略全表掃描

所以，B表的訪問方式ref，使用索引IND_D

(**) 從剩余的表中窮舉選出第二個JOIN的表，這里剩余的表為：A

(**) 將A表加入JOIN，并確定其訪問方式

可以使用的索引為：`IND_L_D`(A.LastName = 'zhou')或者`IND_DID`(B.DepartmentID = A.DepartmentID)

依次計算使用索引IND_L_D、IND_DID的成本：

(***) IND_L_D A.LastName = 'zhou'

在range analysis階段給出了A.LastName = 'zhou'對應的記錄約為：51。

所以，計算IO成本為：51;ref做IO成本計算時會做一次修正，將其修正為worst_seek(參考)

修正后IO成本為：15，總成本為：25.2

(***) IND_DID B.DepartmentID = A.DepartmentID

這是一個需要知道前面表的結果，才能計算的成本。所以range analysis是無法分析的

這里，我們看到前面表為B，found_record是1，所以A.DepartmentID只需要對應一條記錄就可以了

因為具體取值不知道，也沒有直方圖，所以只能簡單依據索引統計信息來計算：

索引IND_DID的列A.DepartmentID的Cardinality為1349，全表記錄數為1349

所以，每一個值對應一條記錄，而前面表B只有一條記錄，所以這里的found_record計算為1*1 = 1

所以IO成本為：1，總成本為1.2

(***) IND_L_D成本為25.2;IND_DID成本為1.2，所以選擇后者為當前表的訪問方式

(**) 確定A使用索引IND_DID，訪問方式為ref

(**) JOIN順序B|A，總成本為：1.2+1.2 = 2.4

(*) 選擇第一個JOIN的表為A

(**) 確定A表的訪問方式

因為A表是第一個表，所以無法使用索引`IND_DID`(B.DepartmentID = A.DepartmentID)

那么只能使用索引`IND_L_D`(A.LastName = 'zhou')

使用IND_L_D索引的成本計算，總成本為25.2;參考前面計算;

(**) 這里訪問A表的成本已經是25.2，比之前的最優成本2.4要大，忽略該順序

所以，這次窮舉搜索到此結束

把上面的過程簡化如下：

(*) 選擇第一個JOIN的表為B

(**) 確定B表的訪問方式

(**) 從剩余的表中窮舉選出第二個JOIN的表，這里剩余的表為：A

(**) 將A表加入JOIN，并確定其訪問方式

(***) IND_L_D A.LastName = 'zhou'

(***) IND_DID B.DepartmentID = A.DepartmentID

(***) IND_L_D成本為25.2;IND_DID成本為1.2，所以選擇后者為當前表的訪問方式

(**) 確定A使用索引IND_DID，訪問方式為ref

(**) JOIN順序B|A，總成本為：1.2+1.2 = 2.4

(*) 選擇第一個JOIN的表為A

(**) 確定A表的訪問方式

(**) 這里訪問A表的成本已經是25.2，比之前的最優成本2.4要大，忽略該順序

至此，MySQL優化器就確定了所有表的最佳JOIN順序和訪問方式。

3. 測試環境

1. MySQL: 5.1.48-debug-log innodb plugin 1.0.9 
2.  
3. CREATE TABLE `department` ( 
4. `DepartmentID` int(11) DEFAULT NULL, 
5. `DepartmentName` varchar(20) DEFAULT NULL, 
6. KEY `IND_D` (`DepartmentID`), 
7. KEY `IND_DN` (`DepartmentName`) 
8. ) ENGINE=InnoDB DEFAULT CHARSET=gbk; 
9.  
10. CREATE TABLE `employee` ( 
11. `LastName` varchar(20) DEFAULT NULL, 
12. `DepartmentID` int(11) DEFAULT NULL, 
13. KEY `IND_L_D` (`LastName`), 
14. KEY `IND_DID` (`DepartmentID`) 
15. ) ENGINE=InnoDB DEFAULT CHARSET=gbk; 
16.  
17. for i in `seq 1 1000` ; do mysql -vvv -uroot test -e 'insert into department values (600000*rand(),repeat(char(65+rand()*58),rand()*20))'; done 
18. for i in `seq 1 1000` ; do mysql -vvv -uroot test -e 'insert into employee values (repeat(char(65+rand()*58),rand()*20),600000*rand())'; done 
19.  
20. for i in `seq 1 50` ; do mysql -vvv -uroot test -e 'insert into employee values ("zhou",27760)'; done 
21. for i in `seq 1 200` ; do mysql -vvv -uroot test -e 'insert into employee values (repeat(char(65+rand()*58),rand()*20),27760)'; done 
22. for i in `seq 1 1` ; do mysql -vvv -uroot test -e 'insert into department values (27760,"TBX")'; done 
23.  
24. show index from employee; 
25. +----------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+ 
26. | Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | 
27. +----------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+ 
28. | employee | 1 | IND_L_D | 1 | LastName | A | 1349 | NULL | NULL | YES | BTREE | | 
29. | employee | 1 | IND_DID | 1 | DepartmentID | A | 1349 | NULL | NULL | YES | BTREE | | 
30. +----------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+ 
31.  
32. show index from department; 
33. +------------+------------+----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+ 
34. | Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | 
35. +------------+------------+----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+ 
36. | department | 1 | IND_D | 1 | DepartmentID | A | 1001 | NULL | NULL | YES | BTREE | | 
37. | department | 1 | IND_DN | 1 | DepartmentName | A | 1001 | NULL | NULL | YES | BTREE | | 
38. +------------+------------+----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+ 

4. 構造一個Bad case

因為關聯條件中MySQL使用索引統計信息做成本預估，所以數據分布不均勻的時候，就容易做出錯誤的判斷。簡單的我們構造下面的案例：

表和索引結構不變，按照下面的方式構造數據：

1. for i in `seq 1 10000` ; do mysql -uroot test -e 'insert into department values (600000*rand(),repeat(char(65+rand()*58),rand()*20))'; done 
2. for i in `seq 1 10000` ; do mysql -uroot test -e 'insert into employee values (repeat(char(65+rand()*58),rand()*20),600000*rand())'; done 
3.  
4. for i in `seq 1 1` ; do mysql -uroot test -e 'insert into employee values ("zhou",27760)'; done 
5. for i in `seq 1 10` ; do mysql -uroot test -e 'insert into department values (27760,"TBX")'; done 
6. for i in `seq 1 1000` ; do mysql -uroot test -e 'insert into department values (27760,repeat(char(65+rand()*58),rand()*20))'; 
7. done 
8.  
9. explain 
10. select * 
11. from 
12. employee as A,department as B 
13. where 
14. A.LastName = 'zhou' 
15. and B.DepartmentID = A.DepartmentID 
16. and B.DepartmentName = 'TBX'; 
17. +----+-------------+-------+------+-----------------+---------+---------+---------------------+------+-------------+ 
18. | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | 
19. +----+-------------+-------+------+-----------------+---------+---------+---------------------+------+-------------+ 
20. | 1 | SIMPLE | A | ref | IND_L_D,IND_DID | IND_L_D | 43 | const | 1 | Using where | 
21. | 1 | SIMPLE | B | ref | IND_D,IND_DN | IND_D | 5 | test.A.DepartmentID | 1 | Using where | 
22. +----+-------------+-------+------+-----------------+---------+---------+---------------------+------+-------------+ 

可以看到這里，MySQL執行計劃對表department使用了索引IND_D，那么A表命中一條記錄為(zhou,27760);根據B.DepartmentID=27760將返回1010條記錄，然后根據條件DepartmentName = 'TBX'進行過濾。

這里可以看到如果B表選擇索引IND_DN，效果要更好，因為DepartmentName = 'TBX'僅僅返回10條記錄，再根據條件A.DepartmentID=B.DepartmentID過濾之。