探究MySQL优化器对索引和JOIN顺序的选择
本文通过一个案例来看看MySQL优化器如何选择索引和JOIN顺序。表结构和数据准备参考本文最后部分"测试环境"。这里主要介绍MySQL优化器的主要执行流程,而不是介绍一个优化器的各个组件(这是另一个话题)。
我们知道,MySQL优化器只有两个自由度:顺序选择;单表访问方式;这里将详细剖析下面的SQL,看看MySQL优化器如何做出每一步的选择。
explain select* from employeeasA,departmentasB where A.LastName='zhou' andB.DepartmentID=A.DepartmentID andB.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优化器主要工作包括以下几部分:QueryRewrite(包括OuterJoin转换等)、consttabledetection、rangeanalysis、JOINoptimization(顺序和访问方式选择)、planrefinement。这个案例从rangeanalysis开始。
2.2rangeanalysis
这部分包括所有Range和indexmerge成本评估(参考1参考2)。这里,等值表达式也是一个range,所以这里会评估其成本,计算出foundrecords(表示对应的等值表达式,大概会选择出多少条记录)。
本案例中,rangeanalysis会针对A表的条件A.LastName='zhou'和B表的B.DepartmentName='TBX'分别做分析。其中:
表AA.LastName='zhou'foundrecords:51
表BB.DepartmentName='TBX'foundrecords:1
这两个条件都不是range,但是这里计算的值仍然会存储,在后面的ref访问方式评估的时候使用。这里的值是根据records_in_range接口返回,而对于InnoDB每次调用这个函数都会进行一次索引页的采样,这是一个很消耗性能的操作,对于很多其他的关系数据库是使用"直方图"的统计数据来避免这次操作(相信MariaDB后续版本也将实现直方图统计信息)。
2.3顺序和访问方式的选择:穷举
MySQL通过枚举所有的left-deep树(也可以说所有的left-deep树就是整个MySQL优化器的搜索空间),来找到最优的执行顺序和访问方式。
2.3.1排序
优化器先根据foundrecords对所有表进行一个排序,记录少的放前面。所以,这里顺序是B、A。
2.3.2greedysearch
当表的数量较少(少于search_depth,默认是63)的时候,这里直接蜕化为一个穷举搜索,优化器将穷举所有的left-deep树找到最优的执行计划。另外,优化器为了减少因为搜索空间庞大带来巨大的穷举消耗,所以使用了一个"偷懒"的参数prune_level(默认打开),具体如何"偷懒",可以参考JOIN顺序选择的复杂度。不过至少需要有三个表以上的关联才会有"偷懒",所以本案例不适用。
2.3.3穷举
JOIN的第一个表可以是:A或者B;如果第一个表选择了A,第二个表可以选择B;如果第一个表选择了B,第二个表可以选择A;
因为前面的排序,B表的foundrecords更少,所以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_DA.LastName='zhou'
在rangeanalysis阶段给出了A.LastName='zhou'对应的记录约为:51。
所以,计算IO成本为:51;ref做IO成本计算时会做一次修正,将其修正为worst_seek(参考)
修正后IO成本为:15,总成本为:25.2
(***)IND_DIDB.DepartmentID=A.DepartmentID
这是一个需要知道前面表的结果,才能计算的成本。所以rangeanalysis是无法分析的
这里,我们看到前面表为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_DA.LastName='zhou'
(***)IND_DIDB.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.测试环境
MySQL:5.1.48-debug-loginnodbplugin1.0.9 CREATETABLE`department`( `DepartmentID`int(11)DEFAULTNULL, `DepartmentName`varchar(20)DEFAULTNULL, KEY`IND_D`(`DepartmentID`), KEY`IND_DN`(`DepartmentName`) )ENGINE=InnoDBDEFAULTCHARSET=gbk; CREATETABLE`employee`( `LastName`varchar(20)DEFAULTNULL, `DepartmentID`int(11)DEFAULTNULL, KEY`IND_L_D`(`LastName`), KEY`IND_DID`(`DepartmentID`) )ENGINE=InnoDBDEFAULTCHARSET=gbk; foriin`seq11000`;domysql-vvv-uroottest-e'insertintodepartmentvalues(600000*rand(),repeat(char(65+rand()*58),rand()*20))';done foriin`seq11000`;domysql-vvv-uroottest-e'insertintoemployeevalues(repeat(char(65+rand()*58),rand()*20),600000*rand())';done foriin`seq150`;domysql-vvv-uroottest-e'insertintoemployeevalues("zhou",27760)';done foriin`seq1200`;domysql-vvv-uroottest-e'insertintoemployeevalues(repeat(char(65+rand()*58),rand()*20),27760)';done foriin`seq11`;domysql-vvv-uroottest-e'insertintodepartmentvalues(27760,"TBX")';done showindexfromemployee; +----------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+ |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|| +----------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+ showindexfromdepartment; +------------+------------+----------+--------------+----------------+-----------+-------------+----------+--------+------+------------+---------+ |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.构造一个Badcase
因为关联条件中MySQL使用索引统计信息做成本预估,所以数据分布不均匀的时候,就容易做出错误的判断。简单的我们构造下面的案例:
表和索引结构不变,按照下面的方式构造数据:
foriin`seq110000`;domysql-uroottest-e'insertintodepartmentvalues(600000*rand(),repeat(char(65+rand()*58),rand()*20))';done foriin`seq110000`;domysql-uroottest-e'insertintoemployeevalues(repeat(char(65+rand()*58),rand()*20),600000*rand())';done foriin`seq11`;domysql-uroottest-e'insertintoemployeevalues("zhou",27760)';done foriin`seq110`;domysql-uroottest-e'insertintodepartmentvalues(27760,"TBX")';done foriin`seq11000`;domysql-uroottest-e'insertintodepartmentvalues(27760,repeat(char(65+rand()*58),rand()*20))'; done explain select* from employeeasA,departmentasB where A.LastName='zhou' andB.DepartmentID=A.DepartmentID andB.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|Usingwhere| |1|SIMPLE|B|ref|IND_D,IND_DN|IND_D|5|test.A.DepartmentID|1|Usingwhere| +----+-------------+-------+------+-----------------+---------+---------+---------------------+------+-------------+
可以看到这里,MySQL执行计划对表department使用了索引IND_D,那么A表命中一条记录为(zhou,27760);根据B.DepartmentID=27760将返回1010条记录,然后根据条件DepartmentName='TBX'进行过滤。
这里可以看到如果B表选择索引IND_DN,效果要更好,因为DepartmentName='TBX'仅仅返回10条记录,再根据条件A.DepartmentID=B.DepartmentID过滤之。