2.Mysql 查询优化器

源自：https://dev.mysql.com/doc/internals/en

优化器是一组例程，它们决定DBMS应该采用什么样的执行路径进行查询。在/sql/sql_select.cc 类文件中的方法 handle_select() 调用关系 如图，

handle_select()   mysql_select()       JOIN::prepare()             setup_fields()       JOIN::optimize() /* optimizer is from here ... */           optimize_cond()           opt_sum_query()           make_join_statistics()                 get_quick_record_count()                 choose_plan()                        /* Find the best way to access tables */                         /* as specified by the user. */                        optimize_straight_join()                               best_access_path()                          /* Find a (sub-)optimal plan among all or subset */                          /* of all possible query plans where the user */                          /* controls the exhaustiveness of the search. */                         greedy_search()                                best_extension_by_limited_search()                                        best_access_path()                        /* Perform an exhaustive search for an optimal plan */                        find_best()                 make_join_select()           JOIN::exec()

可以看到handle_select()调用mysql_select()，后者调用JOIN:prepare()，后者调用setup_fields()，依此类推。mysql_select()的第一部分是JOIN:prepare()，它用于上下文分析、元数据设置和一些子查询转换。优化器是JOIN:optimize()及其所有下级例程。优化器完成后，JOIN:exec()接管并执行JOIN:optimize()决定的工作. optimize_cond()和opt_sum_query() 方法执行转换。make_join_statistics() 将它可以找到的有关索引的所有信息组合在一起，这些信息可能对访问查询的表有用。

# 静态常量传播 常数传播发生在循环中，因此一个传播步骤的输出可以输入到下一个步骤。=, <, >, <=, >=, <>, <=> 如下：

WHERE column1 = column2 AND column2 = 'x'

可以优化为：

WHERE column1 =  'x' AND column2 = 'x'

/sql/sql_select.cc, change_cond_ref_to_const() /sql/sql_select.cc, propagate_cond_constants().

# 消除 Dead Code

例如

WHERE 0=0 AND column1='y'  ==》 WHERE column1='y'

如果列定义为 NOT NULL ,以下查询条件将被移除：

WHERE not_null_column IS NULL

常数表达式 转换常量：

WHERE column1 = 1 + 2   ==》WHERE column1 = 3

# 常量表：1.小于等于1行的表；2.一种受WHERE条件限制的表表达式，包含column=constant形式的表达式，用于表主键的所有列，或表的唯一键的所有列（前提是唯一列也被定义为NOT NULL）。例如：

... PRIMARY KEY (column1,column2)       定义表的主键 查询语句：FROM Table0 ... WHERE column1=5 AND column2=7 ... (返回常量表)

定义了唯一键的表：unique_not_null_column INT NOT NULL UNIQUE

FROM Table1 ... WHERE unique_not_null_column=5......

这些规则意味着常量表最多有一个行值。MySQL将预先计算一个常量表，以确定该值是什么。然后MySQL将把这个值“插入”到查询中。下面是个例子：

SELECT Table1.unique_not_null_column, Table2.any_column      FROM Table1, Table2     WHERE Table1.unique_not_null_column = Table2.any_column      AND Table1.unique_not_null_column = 5;

MySQL 在评估这个SQL时，根据常量表的定义2，发现table1是一个常量表。                    情况1. 如果检索失败（表中没有unique_not_null_column=5的行），则常量表没有行，如果对语句运行EXPLAIN，则会看到此消息

Impossible WHERE noticed after reading const tables

情况2：如果检索到unique_not_null_column=5的行，则查询语句转换为：

SELECT 5, Table2.any_column       FROM Table1, Table2      WHERE 5 = Table2.any_column AND 5 = 5;

实际上这是一个很好的组合例子。优化器执行一些转换是因为常量传播，我们前面已经描述过了。顺便说一下，我们首先描述常量传播，因为它发生在MySQL发现常量表是什么之前。优化器步骤的顺序有时会有所不同。 源码位置：/sql/sql_select.cc, make_join_statistics().

# 优化 JOIN   JOIN type 1.system : 常量的系统表 2.const    : 常量表 3.eq_ref  : 在主键索引或唯一键上 做等值比较，一般返回一行数据 4.ref        : 具有相等关系的索引，索引值不能为NULL，(返回 少量数据行) 5.ref_or_null : 具有相等关系的索引，但索引值可能为空 6.range   : 在索引上 范围比较 >= ,<= ,between,in,like。 7.index    : 扫描索引 8.ALL      : 扫描全表 看下面的一个例子：

SELECT *FROM Table1         WHERE indexed_column = 5 AND unindexed_column = 6

优化器使用 indexed_column = 5 作为 driver expression，先检索少量数据，然后再 判断 unindexed_column = 6 的条件。 索引搜索通常比顺序扫描涉及更少的访问，如果表很大但索引是唯一的，则访问要少得多。这就是为什么使用“好的”执行计划进行访问更好，也就是为什么选择index_column作为 driver 通常是好的。

查询计划 QEP      每个计划（或计划的一部分）都分配了成本cost。计划的成本大致反映了根据计划计算查询所需的资源，其中主要因素是计算查询时将要访问的行数。如果有方法可以将成本分配给不同的QEP，那么就可以对它们进行比较。因此，优化器的目标是在所有可能的计划中找到一个成本最小的QEP。      在MySQL中，最优QEP的搜索是以自底而上的方式进行的。优化器首先考虑 [一个表]的所有计划，然后再考虑[两个表]的所有计划，依此类推，直到构建一个完整的最优QEP。由查询中的一些表组成的查询计划称为 部分计划 。优化器倾向于：向部分计划中添加的表越多，其成本就越高。 查询计划代码在： sql/sql_select.cc, find_best(). 来自MySQL 官方 文档 find_best() 伪代码如下： remaining_tables = {t1, ..., tn}; /* all tables referenced in a query */ procedure find_best(    partial_plan in,      /* in, partial plan of tables-joined-so-far */    partial_plan_cost,    /* in, cost of partial_plan */    remaining_tables,    /* in, set of tables not referenced in partial_plan */    best_plan_so_far,    /* in/out, best plan found so far */    best_plan_so_far_cost)/* in/out, cost of best_plan_so_far */ {    for each table T from remaining_tables    {      /* Calculate the cost of using table T. Factors that the         optimizer takes into account may include:           Many rows in table (bad)           Many key parts in common with tables so far (very good)           Restriction mentioned in the WHERE clause (good)           Long key (good)           Unique or primary key (good)           Full-text key (bad)           Other factors that may at some time be worth considering:           Many columns in key           Short average/maximum key length           Small table file           Few levels in index           All ORDER BY / GROUP columns come from this table */      cost = complex-series-of-calculations;     /* Add the cost to the cost so far. */      partial_plan_cost+= cost;      if (partial_plan_cost >= best_plan_so_far_cost)        /* partial_plan_cost already too great, stop search */        continue;      partial_plan= expand partial_plan by best_access_method;      remaining_tables= remaining_tables - table T;      if (remaining_tables is not an empty set)      {        find_best(partial_plan, partial_plan_cost,                  remaining_tables,                  best_plan_so_far, best_plan_so_far_cost);      }      else      {        best_plan_so_far_cost= partial_plan_cost;        best_plan_so_far= partial_plan;      }    } } 使用该方法不适用于 left join 和 right join

索引合并优化 在查询的条件中 cond_1 and cond_2 and cond_3 and ....中，(cond_i,cond_j) 不使用相同的索引，MySQL 通过索引合并方法，构造key 对，例如（cond_1,cond_3,cond_8）然后根据条件中的 key 扫描行，扫描出的行数据再通过duplicate elimination procedure(重复消除程序)，过滤重复的数据，最后输出检索的行数据(数据可能取交集或者并集)，通过  Unique class 用于重复数据消除。

sel_imerge_cond = (t_1 OR t_2 OR ... OR t_n) t_1 是SEL_TREE 对象，其中任意一对 (t_i,t_j)都不能再合并成一个SEL_TREE 对象

 (t_11 OR t_12 OR ... OR t_1k)    AND  (t_21 OR t_22 OR ... OR t_2l)     AND  ...                                                 AND  (t_M1 OR t_M2 OR ... OR t_mp)

针对每个条件，构造一个 矩阵，其中 t_ij是SEL_TREE对象，每行(t_11 OR t_12 OR ... OR t_1k) 是SEL_IMERGE  对象，

Order BY 如果 排序的列已经是有序的，则 MySQL 会跳过 order 程序， SELECT column1 FROM Table1 ORDER BY column1+1; 如果 column1 是索引列，则优化器使用索引扫描，如果column1不是索引列则会进行全表扫描，代价很大，应该避免在待排序的列上进行运算。

Group By 1.如果 是索引列，则使用索引 2.如果没有索引，groupby将使用排序,优化器选择使用哈希表。 3.当使用GROUP BY x ORDER BY x时，优化器会去掉 order by，因为group by 默认也是排序的 4.优化器将某些 having 条件转移到where 条件中 5.如果 group by 使用索引列，并且没有使用limit 进行限制条数，则优化器将        SELECT DISTINCT column1 FROM Table1; 转化成       SELECT column1 FROM Table1 GROUP BY column1;