案例：MySQL优化器如何选择索引和JOIN顺序

~
本文通过一个案例来看看MySQL优化器如何选择索引和JOIN顺序。表结构和数据准备参考本文最后部分"测试环境"。这里主要介绍MySQL优化器的主要执行流程，而不是介绍一个优化器的各个组件(这是另一个话题)。 我们知道，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。

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. 测试环境
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过滤之。

这个案例中因为数据量很小，性能还相差不大，但如果生产环境中数据是千万或者亿级别的时候性能就会差非常非常非常大。通过简单的Hint可以解决这个问题。


原文地址：案例：MySQL优化器如何选择索引和JOIN顺序, 感谢原作者分享。

---

青浦区19464964367： mysql explain 查询优化器如何选择最优的索引 - ？
蒯勤先舒： MySQL数据库几配置选项帮助我及捕获低效SQL语句

青浦区19464964367： MySQL 索引优化器选择索引的规则是什么? - ？
蒯勤先舒： optimizer_prune_level、optimizer_search_depth、optimizer_switch 另外至于MySQL查询优化器的规则资料,我也没有找到专门的资料,对于你的标题 MySQL手册章节:7.2. Obtaining Query Execution Plan Information7.5. Optimization and Indexes 基本上问题就不大了,当然这2个章节告诉你的是索引及SQL优化技术理论基础,还必须结合

青浦区19464964367： sql语句优化怎么做的,建索引的时候要考虑什么 - ？
蒯勤先舒： 1、表的主键、外键必须有索引; 2、数据量超过300的表应该有索引; 3、经常与其他表进行连接的表,在连接字段上应该建立索引; 4、经常出现在Where子句中的字段,特别是大表的字段,应该建立索引; 5、索引应该建在选择性高的字段...

青浦区19464964367： sql server索引怎么用 - ？
蒯勤先舒： 1、打开 SQL Server Management Studio并连接到数据库引擎数据库.2、在“对象资源管理器”窗格中展开“数据库”节点.再打开“数据库”节点下的“表”节点,再展开dbo.格式的表.3、右击“索引”选项,在弹出的快捷菜单中选择“新建索引”命令.4、在打开的“新建索引”对话框中,设置索引的名称,索引类型为“聚集”, 然后单击“添加”按钮.5、在打开的 “从dbo.表 中选择列” 对话框中选择要添加到索引键的表列. 然后点击“确定”按钮.6、选择索引键后的“新建索引”对话框中,设置索引列的排序为“升序/降序”,设置完成后,单击“新建索引”对话框的“确定”按钮,这样就为表创建了索引.

青浦区19464964367： SQL Server优化如何通过3个阶段来完成? (1) - ？
蒯勤先舒： 1.查询分析 在查询分析阶段,SQL Server优化器查看每一个由正规查询树代表的子句,并判断它是否能被优化.SQL Server优化一般会尽量优化那些限制扫描的子句.例如,搜索和/或合并子句.但是不是所有合法的SQL语法都可以分成可优化...

青浦区19464964367： SQL,索引的例子 - ？
蒯勤先舒： 就用 mysql 数据库举例吧 一、什么是索引? 索引用来快速地寻找那些具有特定值的记录,所有MySQL索引都以B-树的形式保存.如果没有索引,执行查询时MySQL必须从第一个记录开始扫描整个表的所有记录,直至找到符合要求的记录.表里...

青浦区19464964367： 如何优化索引:提高SQL语句查询性能 - ？
蒯勤先舒： 查询优化的统计信息是一些对象,这些对象包含与值在表或索引视图的一列或多列中的分布有关的统计信息.查询优化器使用这些统计信息来估计查询结果中的基数或行数.通过这些基数估计,查询优化器可以创建高质量的查询计划.例如,...

青浦区19464964367： 在SQL数据库中设置索引的原则是什么?(注意是设置不是创建) - ？
蒯勤先舒： 其实索引的好坏还和你的查询语句有关系,就是where后边的列有关.如果两者协调不好的话,同样应用索引也得不到什么好处.下边的文章希望对你有益: 索引的设计 A:尽量避免表扫描检查你的查询语句的where子句,因为这是优化器重要关...

青浦区19464964367： sql 的 like 语句怎么样才能调用索引,语句如下: - ？
蒯勤先舒： 索引一般是由查询优化器进行分析决定是否使用,查询优化器会根据实际情况对查询语句实行不同的计划,同一条语句,根据当前数据量的多少计划也会不同 如果你要强制让优化器选择使用该索引,可以在查询时表名后面加提示with(index(索引名))

青浦区19464964367： 数据库建立索引怎么利用索引查询? - ？
蒯勤先舒： 1.合理使用索引 索引是数据库中重要的数据结构,它的根本目的就是为了提高查询效率.现在大多数的数据库产品都采用IBM最先提出的ISAM索引结构.索引的使用要恰到好处,其使用原则如下:在经常进行连接,但是没有指定为外键的列上建...