seq搜索引擎优化至少包括那几步?(本文MySQL优化器如何选择索引和JOIN顺序(组图))
优采云 发布时间: 2021-11-12 08:07seq搜索引擎优化至少包括那几步?(本文MySQL优化器如何选择索引和JOIN顺序(组图))
本文通过一个案例来看看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也有3个选项：全表扫描、索引IND_D、IND_DN。
2. MySQL 优化器如何做2.1 概述
MySQL优化器的主要工作包括以下几部分：Query Rewrite（包括Outer Join转换等）、const表检测、范围分析、JOIN优化（顺序和访问方式选择）、计划细化。这个案例从范围分析开始。
2.2 范围分析
这部分包括了所有的Range和index合并成本评估（参考1参考2)。这里等价表达式也是一个范围，所以这里会计算成本，找到记录（代表对应的等价表达式，大致将选择多少条记录）。
在这种情况下，极差分析会分别分析表A中的条件A.LastName='zhou'和表B中的B.DepartmentName='TBX'。
表A A.LastName = 'zhou' found records: 51
表B B.DepartmentName = 'TBX' found records: 1
这两个条件都不是范围，但是这里计算出来的值还是会被存储起来，用于后续的ref访问方法求值。这里的值是根据records_in_range接口返回的，InnoDB每次调用这个函数都会对索引页进行采样。这是一个非常消耗性能的操作。对于许多其他关系数据库，使用“直方图”统计数据。避免这种操作（相信后续版本的 MariaDB 也会实现直方图统计）。
2.3 选择顺序和访问方式：穷举列表
MySQL通过枚举all找到最优的执行顺序和访问方式（也可以说所有的左深树都是整个MySQL优化器的搜索空间）。
2.3.1 排序
优化器首先根据找到的记录对所有表进行排序，并将记录较少的表放在最前面。因此，这里的顺序是B，A。
2.3.2 贪婪搜索
当表数较少时（小于search_depth，默认为63)，这样直接减少为穷举搜索，优化器会穷尽所有左深树寻找最优执行计划。在另外，为了减少巨大的搜索空间带来的巨大的耗尽消耗，优化器使用了一个“懒惰”的参数prune_level（默认开启），具体如何“懒惰”可以参考JOIN命令的复杂度选择。但至少它需要与“懒惰”相关联的表不止三个，所以这种情况不适用。
2.3.3 精疲力竭
JOIN的第一个表可以是：A或B；如果第一张表选择A，第二张表可以选择B；如果第一张表选择B，第二张表可以选择A；
因为前面的排序，B表找到的记录比较少，所以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. 构建一个坏案例
由于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执行计划对表部门使用索引IND_D，那么A表中的一条记录是(zhou,27760);根据B.DepartmentID=27760，会返回1010条记录，然后根据条件 DepartmentName = Filter by'TBX'。
这里可以看到如果B表选择索引IND_DN，效果更好，因为DepartmentName='TBX'只返回10条记录，然后根据条件A.DepartmentID=B.DepartmentID进行过滤。
认为 文章 有用吗？即刻：与朋友一起学习进步！
我猜你会喜欢
