探究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也有三个选择：全表扫描、索引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过滤之。