探究MySQL优化器对索引和JOIN顺序的选择 |
|
本文标签：MySQL,优化器 本文通过一个案例来看看MySQL优化器如何选择索引和JOIN顺序 。表结构和数据准备参考本文最后部分"测试环境" 。这里主要介绍MySQL优化器的主要执行流程，而不是介绍一个优化器的各个组件(这是另一个话题) 。 我们知道，MySQL优化器只有两个自由度：顺序选择；单表访问方式；这里将详细剖析下面的SQL，看看MySQL优化器如何做出每一步的选择 。 explain select * from employee as A,department as B where A.LastName = zhou and B.DepartmentID = A.DepartmentID 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 。 MySQL优化器主要工作包括以下几部分：Query Rewrite(包括Outer Join转换等)、const table detection、range analysis、JOIN optimization(顺序和访问方式选择)、plan refinement 。这个案例从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 这两个条件都不是range，但是这里计算的值仍然会存储，在后面的ref访问方式评估的时候使用 。这里的值是根据records_in_range接口返回，而对于InnoDB每次调用这个函数都会进行一次索引页的采样，这是一个很消耗性能的操作，对于很多其他的关系数据库是使用"直方图"的统计数据来避免这次操作(相信MariaDB后续版本也将实现直方图统计信息) 。 MySQL通过枚举所有的left-deep树(也可以说所有的left-deep树就是整个MySQL优化器的搜索空间)，来找到最优的执行顺序和访问方式 。 优化器先根据found records对所有表进行一个排序，记录少的放前面 。所以，这里顺序是B、A 。 当表的数量较少(少于search_depth，默认是63)的时候，这里直接蜕化为一个穷举搜索，优化器将穷举所有的left-deep树找到最优的执行计划 。另外，优化器为了减少因为搜索空间庞大带来巨大的穷举消耗，所以使用了一个"偷懒"的参数prune_level(默认打开)，具体如何"偷懒"，可以参考JOIN顺序选择的复杂度 。不过至少需要有三个表以上的关联才会有"偷懒"，所以本案例不适用 。 JOIN的第一个表可以是：A或者B；如果第一个表选择了A，第二个表可以选择B；如果第一个表选择了B，第二个表可以选择A； 因为前面的排序，B表的found records更少，所以JOIN顺序穷举时的第一个表先选择B(这个是有讲究的) 。 (*) 选择第一个JOIN的表为B (**) 从剩余的表中穷举选出第二个JOIN的表，这里剩余的表为：A (*) 选择第一个JOIN的表为A 把上面的过程简化如下： (*) 选择第一个JOIN的表为B (*) 选择第一个JOIN的表为A 至此，MySQL优化器就确定了所有表的最佳JOIN顺序和访问方式 。
MySQL: 5.1.48-debug-log innodb plugin 1.0.9
CREATE TABLE `department` (
`DepartmentID` int(11) DEFAULT NULL,
`DepartmentName` varchar(20) DEFAULT NULL,
KEY `IND_D` (`DepartmentID`),
KEY `IND_DN` (`DepartmentName`)
) ENGINE=InnoDB DEFAULT CHARSET=gbk;
CREATE TABLE `employee` (
`LastName` varchar(20) DEFAULT NULL,
`DepartmentID` int(11) DEFAULT NULL,
KEY `IND_L_D` (`LastName`),
KEY `IND_DID` (`DepartmentID`)
) ENGINE=InnoDB DEFAULT CHARSET=gbk;
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
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
for i in `seq 1 50` ; do mysql -vvv -uroot test -e insert into employee values ("zhou",27760); done
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
for i in `seq 1 1` ; do mysql -vvv -uroot test -e insert into department values (27760,"TBX"); done
show index from employee;
+----------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+----------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+
| employee | 1 | IND_L_D | 1 | LastName | A | 1349 | NULL | NULL | YES | BTREE | |
| employee | 1 | IND_DID | 1 | DepartmentID | A | 1349 | NULL | NULL | YES | BTREE | |
+----------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+
show index from department;
+------------+------------+----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+------------+------------+----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+
| department | 1 | IND_D | 1 | DepartmentID | A | 1001 | NULL | NULL | YES | BTREE | |
| department | 1 | IND_DN | 1 | DepartmentName | A | 1001 | NULL | NULL | YES | BTREE | |
+------------+------------+----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+
4. 构造一个Bad case 因为关联条件中MySQL使用索引统计信息做成本预估，所以数据分布不均匀的时候，就容易做出错误的判断 。简单的我们构造下面的案例： 表和索引结构不变，按照下面的方式构造数据：
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
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
for i in `seq 1 1` ; do mysql -uroot test -e insert into employee values ("zhou",27760); done
for i in `seq 1 10` ; do mysql -uroot test -e insert into department values (27760,"TBX"); done
for i in `seq 1 1000` ; do mysql -uroot test -e insert into department values (27760,repeat(char(65+rand()*58),rand()*20));
done
explain
select *
from
employee as A,department as B
where
A.LastName = zhou
and B.DepartmentID = A.DepartmentID
and B.DepartmentName = TBX;
+----+-------------+-------+------+-----------------+---------+---------+---------------------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+-----------------+---------+---------+---------------------+------+-------------+
| 1 | SIMPLE | A | ref | IND_L_D,IND_DID | IND_L_D | 43 | const | 1 | Using where |
| 1 | SIMPLE | B | ref | IND_D,IND_DN | IND_D | 5 | test.A.DepartmentID | 1 | Using where |
+----+-------------+-------+------+-----------------+---------+---------+---------------------+------+-------------+
可以看到这里，MySQL执行计划对表department使用了索引IND_D，那么A表命中一条记录为(zhou,27760)；根据B.DepartmentID=27760将返回1010条记录，然后根据条件DepartmentName = TBX进行过滤 。 这里可以看到如果B表选择索引IND_DN，效果要更好，因为DepartmentName = TBX仅仅返回10条记录，再根据条件A.DepartmentID=B.DepartmentID过滤之 。 |
