数据库内核月报

数据库内核月报 － 2021 / 07

MySQL · 源码分析 · 条件优化与执行分析

Author: 坚翊

1.概述

optimize_cond函数为sql_optimizer.cc中的一个对condition的优化函数，有四个主要步骤：
1) 提取公共子条件(extract_common_cond)
2) 等值传播(build_equal_items)
3) 常数传播(propagate_cond_constants)
4) 零散条件去除(remove_eq_conds)

2.提取公共子条件

提取公共子条件的是对于(cond1) or (cond2)这种模式的条件，从条件中提取公共部分的条件，这样做的目的在于：1）让mysql 做谓词下推 2）可以减少执行公共子条件的次数

2.1 理论依据

公式

or_condtion_optimization

前提条件

(I) where条件是析取式。即条件形式类似 (A and B) or ( C and D)
(II) 存在公共子条件。即条件形式 A or (A and B) 或者 (A and B) or (A and C)，其中A本身也可以是AND/OR 嵌套的条件
(III) 公共子条件的形式是完全一致的。暂且不考虑类似 AA 这种等价但是形式不一致的情况。还有字符串类型的参数，严格要求大小写保持一致
(IV) 公共子条件具有幂等性。由于破坏幂等性的前提是条件的参数中包含一些类似 RAND(), NOW()等函数，因此这里要求公共子条件中参数只能为Item_field 或者Item_basic_constant 类型。
参考链接: https://yuque.antfin.com/docs/share/66253e89-db95-4958-86fe-a38e49ec9526#

2.2执行分析

DDL语句:

CREATE TABLE t1(i INT); 
CREATE TABLE t2(i INT);
CREATE TABLE t3(i INT);
CREATE TABLE t4(i INT)
INSERT INTO t1 VALUES (127);
INSERT INTO t2 VALUES (128);
INSERT INTO t3 VALUES (128);
INSERT INTO t4 VALUES (128);

SQL为SELECT * FROM t1,t2,t3,t4 WHERE (t1.i=t4.i AND t2.i=t4.i AND t3.i=128) or (t1.i=t4.i AND t2.i=t4.i AND t4.i=128);

输入的item结构为

$c0 (Item_cond_or *) 0x7fffb2a0dc00
|--$c1 (Item_cond_and *) 0x7fffb2a0cb60
|  |--$c2 (Item_func_eq *) 0x7fffb2845fd8
|  |  |--$c3 (Item_field *) 0x7fffb2845cc8 field = test.t1.i
|  |  `--$c4 (Item_field *) 0x7fffb2845e50 field = test.t4.i
|  |--$c5 (Item_func_eq *) 0x7fffb2846510
|  |  |--$c6 (Item_field *) 0x7fffb2846200 field = test.t2.i
|  |  `--$c7 (Item_field *) 0x7fffb2846388 field = test.t4.i
|  `--$c8 (Item_func_eq *) 0x7fffb28468c0
|     |--$c9 (Item_field *) 0x7fffb2846738 field = test.t3.i
|     `--$c10 (Item_int *) 0x7fffb2a0ce40 value = 128
`--$c11 (Item_cond_and *) 0x7fffb2a0d708
   |--$c12 (Item_func_eq *) 0x7fffb2846e08
   |  |--$c13 (Item_field *) 0x7fffb2846af8 field = test.t1.i
   |  `--$c14 (Item_field *) 0x7fffb2846c80 field = test.t4.i
   |--$c15 (Item_func_eq *) 0x7fffb2847340
   |  |--$c16 (Item_field *) 0x7fffb2847030 field = test.t2.i
   |  `--$c17 (Item_field *) 0x7fffb28471b8 field = test.t4.i
   `--$c18 (Item_func_eq *) 0x7fffb28476f0
      |--$c19 (Item_field *) 0x7fffb2847568 field = test.t4.i
      `--$c20 (Item_int *) 0x7fffb2a0d9e8 value = 128


整个提取公共子条件的函数为extract_common_cond，输入的为谓词条件
1) 首先检查是否含有(cond1) or (cond2)的模式，关键在于是否是(Item_cond_or *)类型，如果是则调用get_common_cond函数
2)get_common_cond函数主要是对比or连接的所有条件，并析取所有的公共条件，对于本例子，首先取出第一部分的条件(t1.i=t4.i AND t2.i=t4.i AND t3.i=128) 用以初始化公共子条件的列表。然后取出第二部分的条件(t1.i=t4.i AND t2.i=t4.i AND t4.i=128)用以与第一部分的条件进行逐个对比。
3)两个条件都有3个子条件，所以需要比较9次，决定两个子条件是否相等的功能函数名为check_valid_common_cond，此函数会对比子条件的所有参数，由于条件中可能有嵌套条件，所以该函数为了避免过大开销，则规定嵌套的深度不能超过2层。比较函数check_valid_common_cond亦是递归的，为了处理嵌套条件的情况。
4)经过比较后会得到一个公共的子条件，显然只有t1.i=t4.i和t2.i=t4.i属于公共子条件，所以得到的公共子条件列表只包含两个条件 ，这样便返回到extract_common_cond函数
5)根据4)中得到的公共子条件列表可以重建一个新的(Item_cond_and *)类型，如下所示

$r0 (Item_cond_and *) 0x7fffb2848778
|--$r1 (Item_func_eq *) 0x7fffb2845fd8
|  |--$r2 (Item_field *) 0x7fffb2845cc8 field = test.t1.i
|  `--$r3 (Item_field *) 0x7fffb2845e50 field = test.t4.i
`--$r4 (Item_func_eq *) 0x7fffb2846510
   |--$r5 (Item_field *) 0x7fffb2846200 field = test.t2.i
   `--$r6 (Item_field *) 0x7fffb2846388 field = test.t4.i

6)接下来需要根据这一公共子条件列表对原条件进行变形，首先是对(t1.i=t4.i AND t2.i=t4.i AND t3.i=128)进行变形，具体操作是对比子条件是否相等，显然这部分对条件(t1.i=t4.i AND t2.i=t4.i)需要被删除，所以只剩下(t3.i=128)这一条件。对于(t1.i=t4.i AND t2.i=t4.i AND t4.i=128)亦做类似处理，得到的条件结构为

|--$ai1 (Item_cond_and *) 0x7fffb2a0cb60
|  `--$ai2 (Item_func_eq *) 0x7fffb28468c0
|     |--$ai3 (Item_field *) 0x7fffb2846738 field = test.t3.i
|     `--$ai4 (Item_int *) 0x7fffb2a0ce40 value = 128
`--$ai5 (Item_cond_and *) 0x7fffb2a0d708
   `--$ai6 (Item_func_eq *) 0x7fffb28476f0
      |--$ai7 (Item_field *) 0x7fffb2847568 field = test.t4.i
      `--$ai8 (Item_int *) 0x7fffb2a0d9e8 value = 128

7) 将新的条件和前面得到的重建条件连接在一起则得到了一个全新的条件，其结构如下所示

$w0 (Item_cond_and *) 0x7fffb2848778
|--$w1 (Item_func_eq *) 0x7fffb2845fd8
|  |--$w2 (Item_field *) 0x7fffb2845cc8 field = test.t1.i
|  `--$w3 (Item_field *) 0x7fffb2845e50 field = test.t4.i
|--$w4 (Item_func_eq *) 0x7fffb2846510
|  |--$w5 (Item_field *) 0x7fffb2846200 field = test.t2.i
|  `--$w6 (Item_field *) 0x7fffb2846388 field = test.t4.i
`--$w7 (Item_cond_or *) 0x7fffb2a0dc00
   |--$w8 (Item_cond_and *) 0x7fffb2a0cb60
   |  `--$w9 (Item_func_eq *) 0x7fffb28468c0
   |     |--$w10 (Item_field *) 0x7fffb2846738 field = test.t3.i
   |     `--$w11 (Item_int *) 0x7fffb2a0ce40 value = 128
   `--$w12 (Item_cond_and *) 0x7fffb2a0d708
      `--$w13 (Item_func_eq *) 0x7fffb28476f0
         |--$w14 (Item_field *) 0x7fffb2847568 field = test.t4.i
         `--$w15 (Item_int *) 0x7fffb2a0d9e8 value = 128

8) 最后需要根据7)中得到的新条件进行递归处理，即再调用extract_common_cond对新的条件进行处理，但是为了性能考虑，同样需要对递归深度做一个限制，即不能超过1层。但是新的条件中前两个子条件都是(Item_func_eq *) 类型，只有最后一个子条件可以满足(cond1) or (cond2)的模式。最后一个子条件由于没有公共子条件所以直接返回，得到最终的结果。

3.等值传播

等值传播是对连接限制和条件中相等的部分组成一个等价类，这样可以生成多种连接限制，从而为连接顺序的优化提供更多的空间

3.1理论依据

例如下面这条SQL语句
SELECT * FROM (t1,t2) LEFT JOIN (t3,t4) ON t1.a=t3.a AND t2.a=t4.a WHERE t1.a=t2.a
显然t1.a=t2.a=t3.a=t4.a
该语句可以改写为以下形式
SELECT * FROM (t1,t2) LEFT JOIN (t3,t4) ON t1.a=t3.a AND t3.a=t4.a WHERE t1.a=t2.a
从而连接部分可以改写成
SELECT * FROM (t1 LEFT JOIN (t3,t4) ON t1.a=t3.a AND t3.a=t4.a),t2 WHERE t1.a=t2.a
因为对t2对连接限制被去除，所以将对t2的连接移到外层
原语句亦可改写为
SELECT * FROM (t1,t2) LEFT JOIN (t3,t4) ON t2.a=t4.a AND t3.a=t4.a WHERE t1.a=t2.a
因为对t1对连接限制被去除，因为从而连接部分可以改写成
SELECT * FROM (t2 LEFT JOIN (t3,t4)ON t2.a=t4.a AND t3.a=t4.a), t1 WHERE t1.a=t2.a
等值传播寻找一个连接条件和限制条件的公共子集，从而可以修改连接的限制，从而让连接优化有更多的可能性

3.2执行分析

DDL语句:

CREATE TABLE t1(i INT); 
CREATE TABLE t2(i INT);
CREATE TABLE t3(i INT);
INSERT INTO t1 VALUES (127);
INSERT INTO t2 VALUES (128);
INSERT INTO t3 VALUES (128);

以3.1中的SQLSELECT * FROM (t1,t2) LEFT JOIN (t3,t4) ON t1.i=t3.i AND t2.i=t4.i WHERE t1.i=t2.i为例
等值传播对主函数名为build_equal_items，该函数对where condition和join condition进行分析，建立一个名为cond_equal的COND_EQUAL的类型将所有的相等的item保存起来，作为一个条件等价类，并返回一个等值传递后的where condtion。对于
1）首先解析的是where condition中的条件，调用子函数build_equal_items_for_cond对其进行解析，传入的条件为t1.a=t2.a，因为这个条件没有嵌套也没有多个相等关系，所以只需要解析一层，如果传入的条件含有多层或有多个等价条件则需要递归调用build_equal_items_for_cond 。对谓词条件的等价类建立还需要考虑一种特殊情况:常量item，这一过程将在下个例子进行解释。输入类型为Item_func_eq的条件此时被转换为类型Item_equal的新条件并进入下一步。
2）1）中返回了谓词条件中的等价条件，接下来需要回到build_equal_items建立全局的等价类cond_equal，首先需要判断返回的等价条件是多个等价条件还是单独的等价条件，本例中只是一个相等条件。将其加入cond_equal，然后将cond_equal的层次关系设置好进入下一步，由于这是顶层的build_equal_items函数所以其上层等价类为空。
3）接下来处理join条件，首先遍历获得join的表中含的条件，在这一过程中需要调用table->join_cond_optim()判断是否含有连接条件，然后递归调用build_equal_items函数，在此次调用过程中需要传递1)和2)中得到的等价条件类 {t1.a, t2.a}作为连接条件的等价类的上层。
4) 其中只有一个table_list附加了条件，其结构如下。顶层是一个and条件，然后t1.a=t3.a和t2.a=t4.a分别为其两个子节点，此时继续递归调用build_equal_items和build_equal_items_for_cond进行等值传递并建立连接条件的等价条件类。连接条件的等价条件类的上层等价条件类是(1)中谓词条件给出的等价条件类。

$ig0 (Item_cond_and *) 0x7fff55e62b00
|--$ig1 (Item_func_eq *) 0x7fff55f6f828
|  |--$ig2 (Item_field *) 0x7fff55e113c0 field = opt.t1.i
|  `--$ig3 (Item_field *) 0x7fff55e11538 field = opt.t3.i
`--$ig4 (Item_func_eq *) 0x7fff55f6fd08
   |--$ig5 (Item_field *) 0x7fff55f6fa18 field = opt.t2.i
   `--$ig6 (Item_field *) 0x7fff55f6fb90 field = opt.t4.i

最终会返回一个Item_cond_and的类型，只包含单个Item_equal条件，其中包含t1.a t3.a t2.a t4.a 4个item_field然后将其设置为新的join条件，为后续的优化提供更多的空间。其结构如下所示。

$ii0 (Item_cond_and *) 0x7fff55e62b00
`--$ii1 (Item_equal *) 0x7fff55f71b60

fields = List<Item_field> = {
    ij[0] = (Item_field *) 0x7fff55f70620,
    ij[1] = (Item_field *) 0x7fff55f70798,
    ij[2] = (Item_field *) 0x7fff55e11538,
    ij[3] = (Item_field *) 0x7fff55f6fb90
  }


下再举一例:
DDL语句:

CREATE TABLE t1(i TINYINT); 
CREATE TABLE t2(i INT);
CREATE TABLE t3(i INT);
INSERT INTO t1 VALUES (127);
INSERT INTO t2 VALUES (128);
INSERT INTO t3 VALUES (128);

SQL为SELECT * FROM t1,t2,t3 WHERE t1.i=128 AND t1.i=t2.i AND t2.i=t2.i;
需要注意的是，对于谓词条件中的等价条件，只有t1.i=128才是等值条件，build_equal_items_for_cond会调用一个名为check_equality的函数对每个条件进行判断
对于不同种类型的item默认不相等，而对于t2.i=t2.i这种条件也不认为是等值条件，这个冗余条件将在常数传播和零散条件去除中被优化。
输入的条件结构如下所示

$hy0 (Item_cond_and *) 0x7fff55e62938
|--$hy1 (Item_func_eq *) 0x7fff55e0fdb0
|  |--$hy2 (Item_field *) 0x7fff55e0fc38 field = opt.t1.i
|  `--$hy3 (Item_int *) 0x7fff55e62400 value = 128
|--$hy4 (Item_func_eq *) 0x7fff55e102a0
|  |--$hy5 (Item_field *) 0x7fff55e0ffb0 field = opt.t1.i
|  `--$hy6 (Item_field *) 0x7fff55e10128 field = opt.t2.i
`--$hy7 (Item_func_eq *) 0x7fff55e10780
   |--$hy8 (Item_field *) 0x7fff55e10490 field = opt.t2.i
   `--$hy9 (Item_field *) 0x7fff55e10608 field = opt.t2.i

由于此语句没有连接条件，所以关注点在于build_equal_items_for_cond上，如前文所述，只有t1.i=128才会被认为是等值条件然后优化成Item_equal 和记录在条件等价类cond_equal中。接下来等价类{t1.i,128}会被传递到下一层build_equal_items_for_cond中，由于条件t1.i=t2.i中t1.i可以被等值传递，所以t1.i被传递为128，而t2.i=t2.i不变。build_equal_items_for_cond执行完的条件为:

$hz0 (Item_cond_and *) 0x7fff55e62938
|--$hz1 (Item_func_eq *) 0x7fff55e102a0
|  |--$hz2 (Item_int *) 0x7fff55e62400 value = 128
|  `--$hz3 (Item_field *) 0x7fff55e10128 field = opt.t2.i
|--$hz4 (Item_func_eq *) 0x7fff55e10780
|  |--$hz5 (Item_field *) 0x7fff55e10490 field = opt.t2.i
|  `--$hz6 (Item_field *) 0x7fff55e10608 field = opt.t2.i
`--$hz7 (Item_equal *) 0x7fff55e11580

其中顶层的等价类只包含(Item_equal *) 0x7fff55e11580 这一个等价条件，即t1.i=128

4.常数传播

等值传播中第二个例子输出的item经过常数传播后会消除冗余的t2.i，将它们传播为128， 其函数为propagate_cond_constants。常数传播的目的在于消除冗余的变量。
我们继续使用第三章输出的item，即输入的item的结构为

$ky0 (Item_cond_and *) 0x7fff55bbe2b8
|--$ky1 (Item_func_eq *) 0x7fff55bc0408
|  |--$ky2 (Item_int *) 0x7fff55bbdd80 value = 128
|  `--$ky3 (Item_field *) 0x7fff55bc0290 field = opt.t2.i
|--$ky4 (Item_func_eq *) 0x7fff55bc08e8
|  |--$ky5 (Item_field *) 0x7fff55bc05f8 field = opt.t2.i
|  `--$ky6 (Item_field *) 0x7fff55bc0770 field = opt.t2.i
`--$ky7 (Item_equal *) 0x7fff55cf1540

1) propagate_cond_constants函数执行的逻辑也是递归的，主要是针对谓词条件中的可常数传播的条件。所以对于AND连接的多个条件，propagate_cond_constants将逐条件进行处理
2) 首先处理的是128 = t2.1, 此条件中含有常量，所以可以根据此条件进行常数传播，即调用change_cond_ref_to_const 函数进行传播，将所有的t2.1转换为128
3) change_cond_ref_to_const 输入两个参数field 和 value 分别对应是 t2.1 和 128，然后根据这两个参数对所有对条件进行优化，第一个处理对条件是128 = t2.1 ，由于此条件和传入的参数完全一样，所以不做任何变形直接返回
4) 接下来处理的条件是t2.1 = t2.1 ，这一条件有两个变量，然后可以被替换为t2.1 = 128, 经过变形后其标识为经过常数传播cond->marker = Item::MARKER_CONST_PROPAG;并加入一个类型为 I_List<COND_CMP> 的save_list中
5) 最后处理的条件是类型为Item_equal 的t1.i = 128 ，由于这已经是个等价类型，所以不需要进行任何传播，直接返回上层。
6) 接下来回到2)中遍历所有的条件，此时得到了传播后的条件t2.1 = 128, 但是此条件被标记为被常数传播处理过，所以不能作为常数条件进行传播。最后的等价条件是一个Item_func::MULT_EQUAL_FUNC 不能作为一个传播的条件，所以直接返回， 此时item结构为

$kz0 (Item_cond_and *) 0x7fff55bbe2b8
|--$kz1 (Item_func_eq *) 0x7fff55bc0408
|  |--$kz2 (Item_int *) 0x7fff55bbdd80 value = 128
|  `--$kz3 (Item_field *) 0x7fff55bc0290 field = opt.t2.i
|--$kz4 (Item_func_eq *) 0x7fff55bc08e8
|  |--$kz5 (Item_field *) 0x7fff55bc05f8 field = opt.t2.i
|  `--$kz6 (Item_int *) 0x7fff55cf1790 value = 128
`--$kz7 (Item_equal *) 0x7fff55cf1540

7) 4)中save_list中含有一个COND_CMP类型，其中含有 t2.1 = 128 的条件，所以下一流程是将此条件传播到所有的条件中，从而进一步消除t2.i这一变量, 与2)到5)中的流程类似，change_cond_ref_to_const 函数将所有的条件优化，其中只有第一个条件128 = t2.1 可以被优化为128 = 128， 其他条件都无法优化。所以我们得到了这一传播的最终结果如下所示。

$ld0 (Item_cond_and *) 0x7fff55bbe2b8
|--$ld1 (Item_func_eq *) 0x7fff55bc0408
|  |--$ld2 (Item_int *) 0x7fff55bbdd80 value = 128
|  `--$ld3 (Item_int *) 0x7fff55cf18a8 value = 128
|--$ld4 (Item_func_eq *) 0x7fff55bc08e8
|  |--$ld5 (Item_field *) 0x7fff55bc05f8 field = opt.t2.i
|  `--$ld6 (Item_int *) 0x7fff55cf1790 value = 128
`--$ld7 (Item_equal *) 0x7fff55cf1540

5.零散条件去除

这一函数主要是一些特殊情况的优化，故名思意是零散条件去除，没有统一的优化理论。本文无法覆盖所有的情形，所以只能粗略概括一下这些优化，亦作抛砖引玉之意

(I) ISNULL条件的变化

针对以下情形：对设置为auto_increment的列进行查询SELECT * from table_name where auto_increment_column IS NULL，这个查询将会被转换为SELECT * from table_name where auto_increment_column = LAST_INSERT_ID。这是一个对具体case的优化，覆盖的场景较少故不做过多分析。

(II) 其他谓词条件的优化

主要的调用函数为internal_remove_eq_conds, 此函数亦为递归调用的函数，对谓词条件中的每个条件进行处理，以去除满足以下规则的冗余条件
1) 恒为真或假的条件
2) 二元运算符(or, and)却只有一个参数
3) ISNULL的参数是常数
4) 简单常数计算表达式
5) bool函数计算
对于第四章中输出的item，在此流程中亦可被优化，因为128=128 为常数表达式条件，可以被去除。输入的item结构为

$lk0 (Item_cond_and *) 0x7fff55e62938
|--$lk1 (Item_func_eq *) 0x7fff55e102a0
|  |--$lk2 (Item_int *) 0x7fff55e62400 value = 128
|  `--$lk3 (Item_int *) 0x7fff55bbcac0 value = 128
|--$lk4 (Item_func_eq *) 0x7fff55e10780
|  |--$lk5 (Item_field *) 0x7fff55e10490 field = opt.t2.i
|  `--$lk6 (Item_int *) 0x7fff55bbc9a8 value = 128
`--$lk7 (Item_equal *) 0x7fff55e11580

其中128=128 足够简单故可以被提前计算，计算结果返回为true，故设置结果类型为Item::COND_TRUE，此条件可以被去除，所以变换为

$ll0 (Item_cond_and *) 0x7fff55e62938
|--$ll1 (Item_func_eq *) 0x7fff55e10780
|  |--$ll2 (Item_field *) 0x7fff55e10490 field = opt.t2.i
|  `--$ll3 (Item_int *) 0x7fff55bbc9a8 value = 128
`--$ll4 (Item_equal *) 0x7fff55e11580

这样就完成了整个optimize_cond函数的流程