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

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

　　目录 [hide]

　　1. 可能的选择

　　2. MySQL优化器如何做

　　2.1 概述

　　2.2 range analysis

　　2.3 顺序和访问方式的选择：穷举

　　2.3.1 排序

　　2.3.2 greedy search

　　2.3.3 穷举

　　3. 测试环境

　　4. 构造一个Bad case

　　我们知道，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

原文转自：http://www.orczhou.com/index.php/2013/04/how-mysql-choose-index-in-a-join/