MySQL Internals Optimizer

优化器（The Optimizer）

 这篇描述MySQL查询优化器的工作原理。MySQL查询优化器主要为执行的查询决断最有效的路线（routine，走向）。

 

一。源代码和概念

 这部分讨论优化器关键概念，术语，及在MySQL源代码怎么对应的。

 

1.定义

 狭义定义：优化器，就是DBMS为查询时决断要往哪种执行路径的一系列路线。

 MySQL是经常调整查询的路线，所以你得把这篇描述的逻辑和在源代码里的做比较。为了使比较容易些，这里会包含相关文件和路径的注解，例如源代码/sql/sql_select.cc，optimize_cond()函数。

 当一个查询被转成另一种查询时，其结果是一样的，就会发生语句转化。如下这个查询

SELECT ... WHERE 5 = a
就会被转化成为

SELECT ... WHERE a = 5
 最明显的语句转化是少的，有些语句转化，是为了更快的执行。

 

2.优化器源代码

 如下伪代码显示了/sql/sql_select.cc中handle_select()函数的逻辑结构。（源代码/sql/sql_select.cc处理SQL查询）

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()        /* ... to here */
     JOIN::exec()
 缩进行显示了哪个函数调用哪个函数，如handle_select()函数调用mysql_select()函数，mysql_select()函数会调用JOIN::prepare()、JOIN::optimize()、JOIN::exec()，以及类推。mysql_select()函数的第一部分是调用JOIN::prepare()，此函数用来上下文分析、元数据建立和一些语句转化。查询优化器函数JOIN::optimize()和其所有优化处理中的子路线。当执行完JOIN::optimize()函数后，JOIN::exec()接管并完成JOIN::optimize()函数优化决断后的执行工作。

 虽然有JOIN字出现，其实查询优化器的工作会处理所有的查询类型，不单单JOIN联接查询。

 

二。首要优化

 这部分讨论服务器执行的最重要优化。

 

1.优化常数关系

常数等值传递

 如下的表达式会发生语句转化：

WHERE column1 = column2 AND column2 = 'x'
 这种表达式，众所周知，如果A=B && B=C => A=C（可等值传递），上句表达式转化后变成：

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

 

 当且仅当，操作符为如下的任何一个，在column1 <操作符> column2条件中就会发生语句转化：

=, <, >, <=, >=, <>, <=>, LIKE
注意：等值传递的转化，不适合于BETWEEN。可能也不适合于LIKE，这是后话。

 

 常数等值传递同样发生在循环中，前一步传递的输出作为后一步传递的输入。

源代码见/sql/sql_select.cc，change_cond_ref_to_const()函数。或/sql/sql_select.cc，propagate_cond_constants()函数。

 

剔除死代码

 总是TRUE的条件会发生语句转化，如：

WHERE 0=0 AND column1='y'
这种情况下，第一个条件会被剔除，最后为：

column1='y'
 源代码见/sql/sql_select.cc，remove_eq_conds()。

 

 总是FLASE的条件也会发生语句转化，如：

WHERE (0 = AND s1 = OR s1 = 7
小括号和前两个条件总是FLASE，最后为：

WHERE s1 = 7

 

 还有一些情况下，当WHERE语句中代表不可能的条件，查询优化器可能会全部剔除语句，如下：

WHERE (0 = AND s1 = 5)
因为这条件永远不为TRUE，在EXPLAIN分析中会显示Impossible WHERE。简单地说，MySQL会说WHERE条件被优化过。

 

如果一个字段不能为NULL，优化器会剔除所有不相关的IS NULL的条件，这样

WHERE not_null_column IS NULL
这种条件总为FLASE情况；且

WHERE not_null_column IS NOT NULL
这种条件总为TRUE情况，所以这种字段查询的条件也被剔除。这种判断是很微妙的。举个例：在一个OUT JOIN外联接，被定义成NOT NULL字段仍然含有NULL值，优化器就会单独排除IS NULL条件在这种特殊情况中。

 

 优化器不会检查所有的Impossible WHERE的条件，因为这方面可能性太多了。例如：

CREATE TABLE Table1 (column1 CHAR(1));
...
SELECT * FROM Table1 WHERE column1 = 'Popgo';
优化器不会剔除这种查询的条件，即使在CREATE TABLE定义中使之成为不可能的条件。

 

可合并的常数值

 如下表达式会发生语句转化：

WHERE column1 = 1 + 2
最后为：

WHERE column1 = 3
 在之前说的常数等值传递 ，优化器很容易将这种查询语句合并在一起。这操作就简化了结果。

 

常数值和常数表

 MySQL常数值，有时不单单指在查询的SQL语句的字面意思上，也可在常数表（constant tables）的内容里。常数表（constant tables）被定义为：

1。无记录或一条记录的表

2。表的表达式被WHERE条件约束，而且包含的表达式形式column = "constant"，或者表的主键的所有字段，或者任何唯一键的所有字段（唯一键的字段定义为NOT NULL）

 例如，Table0表的定义包含：

... PRIMARY KEY (column1,column2)
 然后，查询表达式：

FROM Table0 ... WHERE column1=5 AND column2=7 ...
会返回常数表（constant tables）。更多简单地，如果Table1表的定义包含：

... unique_not_null_column INT NOT NULL UNIQUE
然后，查询表达式：

FROM Table1 ... WHERE unique_not_null_column=5
也会返回常数表（constant tables）。

 

 这个规则指一个常数表（constant tables）至多有一条记录值。MySQL就会优先评估是否为常数表（constant tables），并找出那个值。这样，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评估这语句时，首先就会发现，按照常数表（constant tables）的第二点定义，查询条件为unique_not_null_column的表Table1是一个常数表（constant tables），它就会取得这个值。

如果取值失败，也就是在表Table1里unique_not_null_column = 没值，EXPLAIN后结果：

Impossible WHERE noticed after reading const tables
相反，如果取值成功，也就是在表Table1里unique_not_null_column = 为一条记录值，MySQL会转化为如下语句：

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

 

 事实上，这是一个很好的例子。优化器因前面提到的常数等值传递进行一些语句转化。另外，为什么要先描述常数等值传递，因为它在MySQL确认什么是常数表（constant tables）前就先进行了。优化器步骤的顺序，有时是有差别。

 虽然很多查询都没常数表（constant tables）参考。应该牢记，以后无论什么时候，常数constant字被提及，它是指任何一个字面上的值或者一个常数表（constant tables）的内容。

 

2.优化JOIN联接

 这部分讨论优化JOIN联接的不同方法。注意：JOIN联接不单单指JOIN类型，而是所有条件查询的类型。有些人更喜欢叫access type。

 

确定JOIN联接类型

 当评估查询条件表达式时，MySQL会确定它是属于哪个JOIN联接类型。

 如下有记录在档的JOIN类型，从最好到最坏的排序下来：

system：常数表（constant tables）的system类型 
const：常数表（constant tables） 
eq_ref：相等关系的唯一或主键索引 
ref：相等关系的索引，此索引的值不能为NULL 
ref_or_null：相等关系的索引，此索引的值可能为NULL 
range：有关联的索引，如BETWEEN，IN，>=，LIKE等 
index：顺序扫描索引 
ALL：顺序扫描整个表数据

源代码见/sql/sql_select.h，enum join_type{}。另外，还有一小部分没记录在档，为了子查询的JOIN联接类型。

 

 优化器利用JOIN联接类型选择一个驱动表达式，如下：

SELECT *
FROM Table1
WHERE indexed_column = AND unindexed_column = 6
如果indexed_column有比较好的JOIN联接类型，它更可能成为驱动表达式。对它来说，你也会遇到各种不同的例外，但对这句描述，是第一个简单的优化法则。

 

 对驱动来说，什么是最有意义的呢？ 如下查询时的两条执行路径：

最坏执行计划：扫描读表的所有行。这也叫Table1的顺序扫描或简单表扫描。查询每行，检查indexed_column和unindexed_column两列的值是否匹配查询的条件。

最好执行计划： 通过索引，检索哪些有indexed_column = 值的记录。这也叫被索引的搜索。查询每行，检查unindexed_column列的值是否匹配查询的条件。

 

 被索引的搜索通常比顺序扫描调用更少的访问，而且如果访问的表是巨大的，索引又是唯一的，这样表的访问是非常少的。这也是为什么有好执行计划的访问表是更好的，并且这也是为什么常常把indexed_column做为驱动。

 

联接和访问的方法

 在单表搜索中，坏的JOIN联接执行选择比坏的执行选择造成更多的性能损害。所以MySQL开发者发了更多的时间确保查询中的表以一种最佳顺序被联接和此最佳访问方法（常常被称访问路径）被选择作为检查表数据。表联接的固定顺序和相应的所有表的表访问方法的组合，叫做查询执行计划（QEP）。查询优化器的目的就是在所有可能的计划中找出一个最佳的QEP。JOIN联接优先后有一些常规的概念。

 每个计划或计划的部分，被定义成COST成本。计划的成本粗略地反映了计算按照计划的查询所需要的资源，其中主要的因素是当计算查询时所以访问的记录总数。一旦我们有办法分配到不同的成本QEPs，我们有办法对它们进行比较。这样，优化器的目的就是在所有可能的计划中找到一个成本最低的QEP。

 

 在MySQL中，实现了最佳QEP搜索是自下而上的方式。优化器首先确认一张表的所有计划，接着两张表的所有计划，以此类推，直到建立一个完整的最佳QEP。查询计划包括在查询中只有部分表和限定（predicates），被称为部分计划（partial plans）。优化器依赖着一点事实：越多表被加到部分计划（partial plans），成本就越高（注：成本高，执行效率就低）。这使得优化器可扩展更多的表只用较低成本的部分计划（partial plans）类比当前最好的完整计划。
 完成搜索一条最佳QEP的关键路线见sql/sql_select.cc，find_best()。它执行了所有可能计划的详尽搜索，从而保证它最终将找到一个最佳的一条。

 

 如下我们描述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;
     }
   }
}

这里优化器利用了一种深度优先搜索算法。它完成了在FROM语句中评估所有的表。如果评估比起目前为止最好的评估，变得更差，它将停止搜索。扫描的顺序依赖于出现FROM语句中的表的顺序。

源代码见：/sql/table.h， struct st_table。

 分析表（ANALYZE TABLE）可能会影响到一些优化器决断的因素。源代码见：/sql/sql_sqlect.cc，make_join_statistics()。

 find_best()和greedy_search()的直截了当（straightforward）使用将不会用于LEFT JOIN或RIGHT JOIN。例如，从MySQL 4.0.14起，在一些情况下，优化器可能转变LEFT JOIN为STRAIHT JOIN，并交换表的顺序。另外见：LEFT JOIN and RIGHT JOIN Optimization。

 

 RANGE联接类型

 有些条件可以使用索引，但是在一个键的范围（range）或宽度内。这些称为范围条件，最常看到的是带>，>=，<，<=，IN，LIKE，BETWEEN的查询表达式。

对优化器来说，如下表达式：

column1 IN (1,2,3)
和这个是一样的：

column1 = OR column1 = OR column1 = 3
MySQL同样对待这种语句，无需对查询条件的IN到OR或OR到IN做转变。

如下语句，优化器也会用到索引（范围查询range search）

column1 LIKE 'x%'
但这种就不行：

column1 LIKE '%x%'
也就是说，如果匹配条件的第一个字符是通配符，那就没范围查询。

同样，如下两个语句也是一样的

column1 BETWEEN 5 AND 7
和

column1 >= AND column1 <= 7

如果查询的条件，检索了太多的索引键，优化器可能转变RANGE联接类型为ALL JOIN联接类型。像这种转变，特别可能在<和>条件和多级第二索引（secondary indexes）中。源代码见：/myisam/mi_range.c，mi_records_in_range()（MyISAM索引）。

 

 INDEX联接类型

 考虑这个查询

SELECT column1 FROM Table1;
如果column1有加索引，那优化器可能选择从加的索引取值，而不是从表（全表扫描）。像这种方式的索引，一般称为覆盖索引（COVERING INDEX）。在EXPLAIN Extra描述中，MySQL会简单用INDEX单词来表示覆盖索引（COVERING INDEX）。

 语句：

SELECT column1, column2 FROM Table1; 只有当索引被定义成如下，优化器会使用JOIN联接类型为INDEX：join type = index CREATE INDEX ... ON Table1 (column1, column2);
 换句话说，被查询的字段（如：column1, column2）都必需被加索引的，被加索引的多个字段是无顺序之分的。因此，更有意义的严格定义一个多列索引（multiple-column index）作为一个覆盖索引（COVERING INDEX）来使用，无论搜索的考虑。

 

 INDEX MERGE联接类型

概述

 使用索引合并（INDEX MERGE），当表的条件可转化成如下：

cond_1 OR cond_2 ... OR cond_N
 转化的条件是：每个cond_i（cond_1，cond_2。。。）条件可用于范围扫描，且没有一对条件（cond_i，cond_j）用相同的索引。如果cond_i和cond_j条件使用相同的索引，那么cond_i或者cond_j条件能结合一个单一范围扫描，也就没合并的必要了。

 

 如下查询就用了索引合并（INDEX MERGE）：

SELECT * FROM t WHERE key1=c1 OR key2

SELECT * FROM t WHERE (key1=c1 OR key2 索引合并（INDEX MERGE），是实现成一种范围键（range key）并以cond_i（cond_1，cond_2。。。）条件构造成的容器。在做索引合并（INDEX MERGE）时，MySQL检索每个键扫描（keyscans）的行，然后通过一个消除重复的过程来运行它们。目前类Unique用于消除重复的。

INDEX MERGE优化器

单一SEL_TREE对象不能被构造成在OR语句中有不同成员的键的条件，类似这条件：

key1 < c1 OR key2 < c2

从MySQL5.0开始，这些条件被索引合并（INDEX MERGE）方法，和范围优化器（range optimizer）结构的类SEL_IMERGE处理。SEL_IMERGE代表了若干SEL_TREE对象的析取，这种被表示为：

sel_imerge_cond = (t_1 OR t_1 OR ... OR t_n)
每个t_i（t_1，t_2。。。）代表一个SEL_TREE，没有一对（t_i，t_j）不同的SEL_TREE对象能被合并成单一的SEL_TREE对象。

目前的实现方法在构建SEL_IMERGE时，只有当没有单一的SEL_TREE对象能被构建成被分析过的查询的一部分；如果发现单一SEL_TREE对象能被构造，就会马上丢弃SEL_TREE。这实际是一个限制，并且可能导致最坏行检索策略的使用。如下查询：

SELECT * FROM t WHERE (goodkey1=c1 OR goodkey1=c2) AND badkey=c3
在badkey的扫描会被选择，即使在（goodkey1，goodkey1）上的索引合并（INDEX MERGE）会更快。

索引合并（INDEX MERGE） 优化器会收集索引合并（INDEX MERGE）访问行的所有可能的路线列表。这种SEL_IMERGE结构列表表示如下的条件：

(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_IMERGE且一个条件就是一个SEL_IMERGE对象。

最小成本的SEL_IMERGE对象用来检索行。

索引合并（INDEX MERGE）构造函数的详细信息见：源代码sql/opt_range.cc，imerge_list_and_list()，imerge_list_or_list()，和SEL_IMERGE类的成员函数。

RANGE优化器

为了范围RANGE查询，MySQL优化器构建一个SEL_TREE对象，如下这种形式：

range_cond = (cond_key_1 AND cond_key_2 AND ... AND cond_key_N)
每一个cond_key_i都是一个键的组成部分的条件。MySQL为每个有用的键创建一个cond_key_i条件。然后这种成本最便宜的条件cond_key_i用来做范围RANGE扫描。

单一的cond_key_i条件是用SEL_ARG对象中的一个相联指针网（a pointer-linked network of SEL_ARG objects）来表示。每个SEL_ARG对象参考键的特定部分和表示如下的条件：

sel_arg_cond= (inf_val < key_part_n AND key_part_n < sup_val) (1)
AND next_key_part_sel_arg_cond (2)
OR left_sel_arg_cond (3)
OR right_sel_arg_cond (4)

1。实现间隔，可能没有上下临界，也或包括或没包括临界值。

2。实现SEL_ARG对象以下一个键组件作为条件（is for a SEL_ARG object with condition on next key component）。

3。实现有间隔的SEL_ARG对象，在同样区域作为这个SEL_ARG对象（is for a SEL_ARG object with an interval on the same field as this SEL_ARG object）。在当前对象和左边对象中的间隔，是不相交的。left_sel_arg_cond.sup_val <= inf_val。

4。实现有间隔的SEL_ARG对象，在同样区域作为这个SEL_ARG对象。在当前对象和右边对象中的间隔，是不相交的。left_sel_arg_cond.min_val >= max_val。

 MySQL会转变任意深度的嵌套AND-OR条件为上述相连接的形式。

 

行检索算法

 索引合并（INDEX MERGE）有如下两个步骤：

准备阶段：

activate 'index only';
foreach key_i in (key_scans \ clustered_pk_scan)
{
  while (retrieve next (key, rowid) pair from key_i)
  {
    if (no clustered PK scan ||
        row doesn't match clustered PK scan condition)
      put rowid into Unique;
  }
}
deactivate 'index only';

 

行检索阶段：

for each rowid in Unique
{
  retrieve row and pass it to output;
}
if (clustered_pk_scan)
{
  while (retrieve next row for clustered_pk_scan)
   pass row to output;
}
源代码见：sql/opt_range.cc，QUICK_INDEX_MERGE_SELECT类函数的索引合并（INDEX MERGE）行检索代码。

 

3.换位（Transpositions）

 MySQL支持简单语句表达式的换位（反转关系操作符的操作数的顺序）。换句话说：

WHERE - 5 = column1
此语句可转化成：

WHERE column1 = -5

 

 然而，MySQL不支持有运算存在的换位，如：

WHERE 5 = -column1
而这句不能同等对待：

WHERE column1 = -5

 

 像这形式column = constant表达式的换位是为了更好的索引检索。如果这种形式的语句有加了索引的字段，不论表的大小，MySQL始终使用上索引的。（例外：如果表无记录或只有一行记录，它就是常数表，需特别处理。见常数值和常数表）。

 

 AND关系

 一个AND的查询形式如condition1 AND condition2，如下：

WHERE column1 = 'x' AND column2 = 'y'
 这步骤描述了优化器决断的过程：

1。如果两个条件都没被索引，使用顺序扫描（全表扫描）。
2。除前一点之外，如果其中一个条件有更好的JOIN联接类型，则以JOIN联接类型选择一个驱动。（见确定JOIN联接类型）
3。除前两点之外，如果两个条件都有加索引且平等的JOIN联接类型（注：JON 联接类型效果有好坏之分），则以第一个创建的索引选择一个驱动。

 优化器也会根据索引交叉选择索引合并（INDEX MERGE），见 INDEX MERGE联接类型。 例子如下：

CREATE TABLE Table1 (s1 INT, s2 INT);
CREATE INDEX Index1 ON Table1 (s2);
CREATE INDEX Index2 ON Table1 (s1);
...
SELECT * FROM Table1 WHERE s1 = AND s2 = 5;
 当选择一种策略来解决这个查询，优化器会选择s2 = 5作为驱动，由于s2上的索引首先被创建。视为一个偶然的效果，而不是一种规则，在任何时刻都有可能会改变的。

 

 OR关系

 一个OR的查询形式如condition1 OR condition2，如下：

WHERE column1 = 'x' OR column2 = 'y'
 这种查询优化器的决断是使用顺序全表扫描。

 

 还有一种选择在特定的环境下会使用索引合并（INDEX MERGE），更多信息见INDEX MERGE优化器和Index Merge Optimization。

 上述的特定情况不能用于如果两条件的字段是一样。如下：

WHERE column1 = 'x' OR column1 = 'y'
 这种情况，由于语句是RANG查询，所以会走索引的。这个话题会在IN限定（predicate）的讨论中再次看到。

 

 UNION查询

 所有含有UNION的SELECT查询语句会被各自优化。因此，这个查询：

SELECT * FROM Table1 WHERE column1 = 'x'
UNION ALL
SELECT * FROM TABLE1 WHERE column2 = 'y'
 如果column1和column2都有索引的，每个SELECT都会使用索引扫描，各自的结果集会被合并。注意：此查询可能产生相同的结果集，如果查询使用了顺序扫描OR的例子。

 

 NOT（<>）关系

 一个逻辑条件如下 ：

column1 <> 5
等价于：

column1 < 5 OR column1 > 5
 然而，MySQL不会对这种条件进行转化语句。如果你觉得用RANG查询效果会更好，你必需自己手动做语句转化。

 

 还有一个逻辑条件如下：

WHERE NOT (column1 != 5)
等价于：

WHERE column1 = 5
 对这种情况，MySQL也不会做语句转化的。

 我们期待能针对上述两个情况加入新的优化方法。

 

 ORDER BY语句

 通常，如果优化器发现行记录不管怎么样都是有序的，在ORDER BY语句中它也会跳过SORT过程。但是还是验证几个例外的情况。

 例：

SELECT column1 FROM Table1 ORDER BY 'x';
 优化器会扔掉ORDER BY语句，这也是死代码删除一个例子。

 

 例：

SELECT column1 FROM Table1 ORDER BY column1;
 优化器会使用column1的索引，如果存在的话。

 

 例：

SELECT column1 FROM Table1 ORDER BY column1+1;
 优化器会使用column1的索引，如果存在的话。但是不要被弄混了，索引只用来查找记录值。另外：顺序扫描索引的成本比顺序扫描全表的成本是更便宜的（一般索引的大小会比数据值的大小小的），这也是为什么INDEX JOIN联接类型会比ALL类型更优化。见确定JOIN联接类型。

 

 还有一种结果集的全部排序SORT，例：

SELECT * FROM Table1
WHERE column1 > 'x' AND column2 > 'x'
ORDER BY column2;
 如果column1和column2都有索引的，优化器会走在column1上的索引。在这个查询语句，对column2值的排序不会影响驱动的选择。

源代码见：/sql/sql_select.cc，test_if_order_by_key()和/sql/sql_select.cc，test_if_skip_sort_order()。

 

 ORDER BY Optimization，描述了SORT排序过程的内容机制，在这里不重复解释。但恳请你一定要阅读，因为它描述了缓冲和快速排序机制的操作。

 

 GROUP BY和相关的条件

 这里描述了GROUP BY和相关条件（HAVING，COUNT()，MAX()，MIN()，SUM()，AVG()，DISTINCT()）的主要优化。

GROUP BY会使用索，如果一个索引存在的话。 
GROUP BY会用排序，如果没有索引存在。优化器可能选择使用HASH表排序。  
GROUP BY x ORDER BY x的情况，优化器会因为GROUP BY会以 x 的排序，而认为ORDER BY是不需要的。 
优化器包含了为转移特定HAVING条件的WHERE语句中的代码。然而，此代码在编写时是不生效的。源代码见：/sql/sql_select.cc，JOIN::optimize()，在#ifdef HAVE_REF_TO_FIELDS之后。 
如果表句柄（handler）有个有效的快速行总数（row-count），那么这个查询： 
SELECT COUNT(*) FROM Table1;
不必扫描所有行，就能得到行总数值。这只对MyISAM表是正确的，但不适合InnoDB表。另外这个查询

SELECT COUNT(column1) FROM Table1;
 不会有同样的优化，除非column1被定义为NOT NULL。

MAX()和MIN()新的优化方法。例： 
SELECT MAX(column1)
  FROM Table1
  WHERE column1 < 'a';
如果column1被索引了，就很容易找到最大值通过查询索引中的'a'值并且在这之前返回索引键。

优化对如下形式的查询，进行语句转化：
SELECT DISTINCT column1 FROM Table1;
成：

SELECT column1 FROM Table1 GROUP BY column1;
当且仅当这两个条件都是正确：

* GROUP BY能通过索引来未完成。这暗示了只有一个表在FROM语句中且没有WHERE语句。
* 没有LIMIT语句。

因为DISTINCT语句并不总是被转化成GROUP BY，不要期望含有DISTINCT查询语句总会有被排序的结果集。然而，你能依赖GROUP BY优化规则，除非查询包括ORDER BY NULL。

三。其它优化

这部分，讨论其它更特别的优化方法。

1. ref和eq_ref的NULLs值过滤访问

这部分讨论ref和eq_ref联接类型的NULLs值过滤优化方法。

前期（early）NULLs值过滤

假设我们有个联接顺序如下：

..., tblX, ..., tblY, ...
更深入假设，表tblY通过ref或eq_ref 联合类型被访问：

tblY.key_column = tblX.column
或者，使用多个键部分的ref类型访问：

... AND tblY.key_partN = tblX.column AND ...
tblX.column可以为NULL。ref（或eq_ref）类型访问时，前期会应用NULLs过滤。我们做如下的推断：

(tblY.key_partN = tblX.column) =>  (tblX.column IS NOT NULL)
 原等式的检查只有在读了表tblX和tblY的当前行记录后。IS NOT NULL限定（predicate）的检查，只有在读了表tblX的当前行记录后。如果在表tblX和tblY的联合排序中有任何

 其它表，IS NOT NULL限定（predicate）的检查就允许我们跳过访问这些表。

 

 这个特性的实现代码如下：

ref分析器（包含方法update_ref_and_keys()）通过设置KEY_FIELD::null_rejecting=TRUE检查和标记像上述这种类型的查询等式。 
选择JOIN联接排序以后，add_not_null_conds()会增加适当的IS NOT NULL限定（predicate）到适当表的相关条件中。

 

 对所有等式加了IS NOT NULL限定（predicate）是有可能被ref访问类型使用（而不是那些有实际使用的）。然而，目前没这样做。

 

 后期（Late）NULLs过滤

 假设我们有一个表tblX查询计划，是通过ref访问类型被访问：

tblX.key_part1 = expr1 AND tblX.key_part2 = expr2 AND ...
 在调用索引检索前，我们确定任何expri（expr1，expr2，expr3。。。）值是否为NULL。如果是，我们不会调用检索，而是会马上返回没找到匹配数组。

 这个优化方法重用了由前期（early）NULLs过滤产生的null_rejecting属性。这个检查的源代码见：函数join_read_always_key()。

 

 2.分区相关的优化

 这部分讨论MySQL分区相关的优化。MySQL5.1分区相关概念和实现见：Partitioning。

 

 分区裁剪（pruning）

 分区裁剪（partition pruning）的操作，如下定义：

 “提供一个分区表的查询，比对此分区表的DDL语句和查询中的任何WHERE或ON语句，且找出这查询访问的最小分区集。”

 

 这样得到的分区集会比表所有分区的集合小很多，这个分区集也是之后查询语句要用到的。没被加入这个分区集的其它分区，就不会被访问的，也就是说被裁剪掉的分区。正因为这样，查询的执行速度变得更快。

 Non-Transactional Table Engines.??如MyISAM无事务存储引擎，锁会被加在整个分区表。理论上讲，使用分区裁剪（partition pruning）是有可能提高并发，只把锁加在被使用的分区上。但是目前还没实现这功能。

 分区裁剪（partition pruning）不依赖表的存储引擎，所以这功能是MySQL查询优化器的一部分。接下来章节描述分区裁剪（partition pruning）的细节。

 

分区裁剪概述

 分区裁剪（partition pruning）的实现步骤如下：

1。分析WHERE语句条件并构造区间图interval graph，用来描述分析的结果情况。

2。通过区间图，为每个区间找出被访问的分区集（包括子分区）。

3。构造查询所需要的分区集。

 区间图interval graph是自下而上的方式构造成，并来表示上述步骤的描述。接着讨论，我们会首先定义术语区间图interval graph，接着描述怎样用分区区间来组成一个区间图interval graph，最后描述区间图interval graph的工作流程。

 

分区区间（Partitioning Intervals）

单点区间（Single-Point Intervals）

 从最简单的情况开始，假设一个有N个列的分区表，通过分区类型p_type和分区函数p_func，表示如下：

CREATE TABLE t (columns)
PARTITION BY p_type(p_func(col1, col2,... colN)...);
 再假设查询的WHERE条件形式如下：

WHERE t.col1=const1 AND t.col2=const2 AND ... t.colN=constN
 我们能计算出p_func(const1, const2 ... constN)，并挖掘出哪个分区包含的记录和WHERE条件一样。注意：这个流程会在所有的分区类型和所有的分区函数上操作。

 

 注意：此流程只工作在，如果WHERE条件的形式像上述那样，表的每个列必需被验证是否等与一些任意常数（不需要相同的常数为每列）。例如，如果上述例子的WHERE语句中没有col1=const1，那么我们不会计算p_func分区函数的值，也就不会约束实际被用的分区集。

 

 区间游历（Walking）

 假设一个分区表t被定义成columns列集，分区类型p_type，分区函数p_func使用integer类型字段int_col，如下：

CREATE TABLE t (columns)
PARTITION BY
p_type(p_func(int_col))
...
 假设我们有如下形式的WHERE条件查询：

WHERE const1 <= int_col <= const2
我们能缩小此情况的条件成一系列单点区间（Single-Point Intervals），如下，通过转化此WHERE语句为以下关系：

int_field=const1 OR
int_field=const1 + 1 OR
int_field=const1 + 2 OR
... OR
int_field=const2

在源代码里，这种转化被称作区间游历（Walking）。游历短的区间成本是不贵的，这样我们能缩小分区数来扫描小的分区。然尔，游历长的区间不是那么非常有效的，需要检查大量的分区，这样的话，可能所有分区都会被扫描的。

如下参数决定区间游历（Walking）的值：

#define MAX_RANGE_TO_WALK=10

注意：如下条件关系也会利用上述区间游历（Walking）的逻辑：

const1 >= int_col >= const2

 

 区间映射（mapping）

 假设如下的分区表定义：

CREATE TABLE t (columns)
PARTITION BY RANGE|LIST(unary_ascending_function(column))
假设我们对表t的查询的WHERE语句，是如下形式中的一种：

const1 <= t.column <= const2
t.column <= const2
const1 <= t.column

自分区函数是升序，看如下的关系：

const1 <= t.col <= const2

=> p_func(const1) <=

p_func(t.column) <= p_func(const2)
用A和B表示这关系的最左和最右部分，我们能重写关系为：

A <= p_func(t.column) <= B
注意：在这实例中，区间是关闭的且有两个界值。但是，类似的推论可以类推到其它类型的区间。

如范围分区（RANGE partitioning），每个分区占据一个区间于分区函数值的轴线上，每个区间是不相连的，如下：

p0 p1 p2
table partitions ------x------x--------x-------->

  search interval     ----x==============x----------->
                          A              B
 一个分区需要被访问，当且仅当如果它的区间和搜索区间[A, B]没有空的交叉点。

 

 如列举分区（LIST partitioning），每个分区包括点集于分区函数值的轴线上，各分区会产生不同的交叉点，如下：

                      p0  p1   p2   p1   p1   p0
table partitions    --+---+----+----+----+----+---->

search interval     ----x===================x------>
                        A                   B
 一个分区需要被访问，至少一个交叉点在搜索区间[A, B]里。所用的分区集可确定运行从A到B，并收集它们的点在这个搜索范围内的分区。

 

 子分区区间（subpartitioning intervals）

 在前面部分我们描述几种从基本的WHERE条件推断出在用分区集。一切都表明，这些分区的推断方法都适合于子分区，除范围分区（RANGE partitioning）和列举分区（LIST partitioning）的子分区外。

 自每个分区以同样的方式被分子分区，我们会找出在每个分区内的哪个子分区会被访问。

 

 从WHERE语句到区间（From WHERE Clauses to Intervals）

 之前的章节讲述了，从表示分区和子分区区间的WHERE语句推断出分区集。现在我们看看如何从任意WHERE语句抽出区间。

 

 抽取的流程使用范围分析器（RANGE Analyzer），属于MySQL优化器的一部分，它产生范围RANGE访问的计划。这是因为这个任务是相似的。两种WHERE语句的形式：RANGE访问类型使用索引范围（区间）扫描；分区裁剪（partition pruning）模块使用分区区间，用来决定哪个分区被使用。

 为了分区裁剪（partition pruning），范围分析器（RANGE Analyzer）与WHERE语句被调用，一个由分区和子分区函数使用的表的列清单：

(part_col1, part_col2, ... part_colN,
subpart_col1, subpart_col2, ... subpart_colM)
 范围分析器（RANGE Analyzer）工作的结果被称为SEL_ARG图。这是一个很复杂的结构，我们不打算在这里描述它。目前这个文化讨论的重点是我们能游历所有分区，并收集分区和子分区的区间。

 

 如下例子阐明结构和游历流程。假设表t按如下的分区：

CREATE TABLE t (..., pf INT, sp1 CHAR(5), sp2 INT, ... )
  PARTITION BY LIST (pf)
  SUBPARTITION BY HASH(sp1, sp2) (
    PARTITION p0 VALUES IN (1),
    PARTITION p1 VALUES IN (2),
    PARTITION p2 VALUES IN (3),
    PARTITION p3 VALUES IN (4),
    PARTITION p4 VALUES IN (5),
  );
 现假设对表t的一个很复杂的WHERE语句查询：

pf=1 AND (sp1='foo' AND sp2 IN (40,50))

OR

(pf1=3 OR pf1=4) AND sp1='bar' AND sp2=33

OR

((pf=3 OR pf=4) AND sp1=5)

OR

p=8

 

 SEL_ARG图如下：

(root)
   |               :
   | Partitioning  :         Sub-partitioning
   |               :
   |               :
   |               :
   |   +------+    :     +-----------+   +--------+
   \---| pf=1 |----:-----| sp1='foo' |---| sp2=40 |
       +------+    :     +-----------+   +--------+
          |        :                         |
          |        :                     +--------+
          |        :                     | sp2=50 |
          |        :                     +--------+
          |        :
          |        :
       +------+    :     +-----------+   +--------+
       | pf=3 |----:--+--| sp1='bar' |---| sp2=33 |
       +------+    :  |  +-----------+   +--------+
          |        :  |
       +------+    :  |
       | pf=4 |----:--+
       +------+    :
          |        :
          |        :
       +------+    :     +-----------+
       | pf=8 |----:-----| sp1='baz' |
       +------+    :     +-----------+

 上述图表，竖的边界（|）代表OR，横的（-）代表AND，横的和竖的线也代表AND。

 

 分区裁剪（partition pruning）代码游历从图上方到下方，从左边到右边，并做了如下的推论

1。在最上和最左的区间，从使用分区的空集合开始游历：

2。 
执行pf=1的区间分析，找到分区P0的相应集合，右移到sp1='foo' 
再次右移，到sp2=40 
分析sp1='foo' AND sp2=40区间，在某SP1子分区找到行。推论一：在每个分区组成集合P0，标识子分区SP1“被使用” 
下移到sp2=50 
分析sp1='foo'区间和sp2=50区间，在某SP2子分区找到行。推论二：在每个分区组成集合P0，标识子分区SP2“被使用” 
移回到pf=1，然后下称到pf=3 
3。

执行pf=3的区间分析，找到分区P1的相应集合，右移到sp1='bar' 
再次右移，到sp2=33

分析sp1='bar' AND sp2=33区间，在某SP3子分区找到行。推论三：在每个分区组成集合P1，标识子分区SP3“被使用”
移回到pf=3，然后下移到pf=4

4。

执行pf=4的区间分析，找到分区P2的相应集合，右移到sp2='bar'
执行移动和类似的推论已在pf=3验证正确。这样的效果是比较差的，因为我们将再次分析sp1='bar' AND sp2=33区间，但这个操作不会很大影响到整体性能。
移回到pf=3，然后下称到pf=8

5。

执行pf=8的区间分析，找到分区P3的相应集合，右移到sp1='baz'

现在到了sp1='baz'，发现不能再向右移动，也不能构建子分区区间。我们记录下，并返回pf=8
从之前的过程，我们不能再限制子分区区间了，所以推论：在P3分区集里的每个分区，假设所有的子分区都是有效在用的。

6。尝试从pf=9下移，发现到尾，所以游历图也就完成。

 

 注意：在特定的情况下，范围分析器（RANGE Analyzer）的结果会有几种的SEL_ARG图，这图是由OR或AND操作符组成的。出现这种情况对于WHERE语句，要么是非常复杂的要么不允许一个单一的区间列表构建。对这种情况，分区裁剪（partition pruning）代码采用合适的操作，例：

SELECT * FROM t1 WHERE partition_id=10 OR subpartition_id=20
 在这个实例中，没有单一的区间被构建，但分区裁剪（partition pruning）代码正确地推断了使用的分区集是联合：

所有在分区里的子分区包含了partition_id=10的行，在每个分区里一个子分区包含subpartition_id=20的行。

 

 源代码中分区裁剪（partition pruning）实现

 源代码的简单解说：

sql/opt_range.cc：
这代码包含了从WHERE语句到区间（From WHERE Clauses to Intervals）的实现，方法prune_partitions()。关于分区裁剪（partition pruning）的都有详细的行行代码注释，从PartitionPruningModule代码开始：

sql/partition_info.h：

class partition_info {
  ...
  /*
    Bitmap of used (i.e. not pruned away) partitions. This is where result
    of partition pruning is stored.
  */
  MY_BITMAP used_partitions;

  /*
    "virtual function" pointers to functions that perform interval analysis
    on this partitioned table (used by the code in opt_range.cc)
  */
  get_partitions_in_range_iter get_part_iter_for_interval;
  get_partitions_in_range_iter get_subpart_iter_for_interval;

};
sql/sql_partition.cc：

 这代码包含了实现所有分区区间分析类型的方法。

 

 分区检索

 如果分区表被一系列索引检索（即ref，eq_ref，ref_or_null联接访问方式）访问，MySQL会检查是否需要所有分区做索引检索或者限制访问到一个特定的分区。例：

CREATE TABLE t1 (a INT, b INT);

INSERT INTO t1 VALUES (1,1),(2,2),(3,3);

CREATE TABLE t2 (
    keypart1 INT,
    keypart2 INT,
    KEY(keypart1, keypart2)
)
PARTITION BY HASH(keypart2);

INSERT INTO t2 VALUES (1,1),(2,2),(3,3);

 

 查询条件如下：

SELECT * FROM t1, t2
    WHERE  t2.keypart1=t1.a
    AND    t2.keypart2=t1.b;
利用如下算法执行：

(for each record in t1:)
{
  t2->index_read({current-value-of(t1.a), current-value-of(t1.b)});
  while( t2->index_next_same() )
    pass row combination to query output;
 }
 在index_read()调用中，分区表句柄会挖掘出被确定所有分区列的值，在这个例子中，是单一列b，接着找出一个分区访问。如果这个分区被裁剪过，就没其它的分区可访问。

 以上就是MySQL Internals Optimizer的内容，更多相关文章请关注PHP中文网（www.php.cn）！