mysql 子查询执行方式介绍

MySQL · 源码解析 · mysql 子查询执行方式介绍

mysql 共有如下几种子查询

• Item_singlerow_subselect
• Item_exists_subselect
• Item_in_subselect
• Item_allany_subselect

本文在不讨论查询变换的情况下，我们我们将逐一介绍上述子查询原生的执行方式，本文注重归纳总结，理解思想的情况下，看源码简单多了。

标量子查询（Item_singlerow_subselect）

例子如下，可以出现在投影， where condition, join condition, project list 里面。

desc format=tree select * from t2 where a > (select max(a) from t1);
| -> Filter: (t2.a > (select #2))  (cost=0.35 rows=1)
    -> Table scan on t2  (cost=0.35 rows=2)
    -> Select #2 (subquery in condition; run only once)
        -> Aggregate: max(t1.a)
            -> Table scan on t1  (cost=0.35 rows=1)

由 plan 可以以看到 left expr+ 子查询被解释成为了一个 filter predict（t2.a > (select #2)）。在 mysql 内存中的对象为：

$m0 (Item_func_gt *) 0x7ff5abdc82b0
|--$m1 (Item_field *) 0x7ff5ac240c28 field = test.t2.a
`--$m2 (Item_singlerow_subselect *) 0x7ff5abdc80d0

执行方式

先对 select #2 进行求值，本例子是 max(t1.a)算子求值，存储到 Item_singlerow_subselect 一个 cache 里面，run only once 嘛，只需求值一次。 对外层 t2 表进行 scan，拿到每一行，应用 Item_func_gt 算子，判断 t2.a > Item_singlerow_subselect->val_int(),实际调用的是 t2.a > Item_cache_int->value. Item_cache_int 就是步骤 1 的求值。

exists 子查询(Item_exists_subselect)

场景：exists 表达式是一个 bool 求值，允许出现 bool 值的地方都可以出现该子查询

例子：

set @@optimizer_switch='materialization=off,semijoin=off';
desc format=tree select * from t2 where exists (select 1 from t3 where t2.a=t3.a);
| -> Filter: exists(select #2)  (cost=0.45 rows=2)
    -> Table scan on t2  (cost=0.45 rows=2)
    -> Select #2 (subquery in condition; dependent)
        -> Limit: 1 row(s)
            -> Filter: (t2.a = t3.a)  (cost=0.35 rows=1)
                -> Table scan on t3  (cost=0.35 rows=2)

注意：这个 sql 会做 semi-join 转换，需要关闭 semi join 就能出 exist 计划

内存中的数据结构

(gdb) p $ac1->m_where_cond
$45 = (Item_exists_subselect *) 0x7ff5aabc1478

where_cond 直接就是 Item_exists_subselect，没有 left expr。Item_exists_subselect 负责求值

执行过程：

• 外层 scan t2 表的每一行都需要做一下 filter
• filter 算子是 Item_exists_subselect 求值，先执行 select 1 from t3 where t2.a=t3.a 子语句求值，这个 unit 执行结果会存放在 Item_exists_subselect.value 里面。
• value 将作为 Item_exists_subselect->val_bool() 结果返回。

上面介绍的两种子查询优化执行都比较简单，下面我们介绍一下 mysql 是怎么处理 in 子查询的, 这个会比较复杂。in 子查询有些开关，可以做查询变换，这节里面我们不展开讨论，只专注于原生执行方式

IN 子查询(Item_in_subselect)

这基本上是子查询里面最复杂的了

场景：in 子查询本质上也是一个 bool 函数求值，允许 bool 值的地方都允许 IN 子查询，所以可以出现在 where_cond,

join 条件，having 条件，投用列里面。

例子:

desc format=tree select * from t2 where t2.a in  (select sum(a) from t3 group by b);
| -> Filter: <in_optimizer>(t2.a,<exists>(select #2))  (cost=0.45 rows=2)
    -> Table scan on t2  (cost=0.45 rows=2)
    -> Select #2 (subquery in condition; dependent)
        -> Limit: 1 row(s)
            -> Filter: (<cache>(t2.a) = <ref_null_helper>(sum(t3.a)))
                -> Table scan on <temporary>
                    -> Aggregate using temporary table
                        -> Table scan on t3  (cost=0.45 rows=2)
==>
select t2.a AS a, t2.b AS b
from t2
where < in_optimizer >(
t2.a,
< exists >(
/* select#2 */
select 1
from t3
group by t3.b
having (< cache >(t2.a) = < ref_null_helper >(sum(t3.a)))
)
)

内存数据结构

执行时会被替换为 Item_in_optimizer，重要的数据结构就是左右两个孩子

$ai0 (Item_in_optimizer *) 0x7ff5aaaad7e0
|--$ai1 (Item_field *) 0x7ff5ac240de8 field = test.t2.a
`--$ai2 (Item_in_subselect *) 0x7ff5ac23fdb8

(gdb) my e  optimizer->args[0]
$aj0 (Item_field *) 0x7ff5ac240de8 field = test.t2.a
(gdb) my e  optimizer->args[1]
$ak0 (Item_in_subselect *) 0x7ff5ac23fdb8
(gdb) p  optimizer->arg_count
$56 = 2

优化过程

prepare 期间的一些优化

• 先设置 Item_in_subselect 的 strategy = Subquery_strategy::CANDIDATE_FOR_IN2EXISTS_OR_MAT。在 optimize 期间会决定是否使用 exists 方式执行还是 materialize 方式执行。
• 做 IN to Exists 执行的变换，这个变换只是辅助，如果 optimize 期间选择了 exists，这些变换才是有用的
• 子查询添加 having (< cache >(t2.a) = < ref_null_helper >(sum(t3.a))条件，变成相关的了
• 递归到 parent Query_block 里面将 Item_in_subselect 替换为 Item_in_optimizer。

可能有同学会奇怪为啥要添加 < ref_null_helper > 算子或者 in 子查询替换为 Item_in_optimizer。exists 跟 in 子查询语义是不一样的，exists 是 bool 语义，返回（0,1）IN 可以返回 NULL 的，结果可以是(0,1, NULL）。这点在子查询 Unnest 里面要尤为注意，请查阅下列例子

mysql> select null in (0);
+-------------+
| null in (0) |
+-------------+
|        NULL |
+-------------+
1 row in set (0.00 sec)

mysql> select  exists (select 1 from dual where NULL = 1);
+--------------------------------------------+
| exists (select 1 from dual where NULL = 1) |
+--------------------------------------------+
|                                          0 |
+--------------------------------------------+

optimize 优化

• 在 JOIN::decide_subquery_strategy 基于 cost 选择哪种执行更优，exists 还是 materialize
• 选择 exists 的话，设置 strategy=Subquery_strategy::SUBQ_EXISTS, 投影列替换为”1”, 因为返回 bool 值就行. 同时子查询的内部 block 添加 limit 1
• 选择 mat 的话，设置 strategy = Subquery_strategy::SUBQ_MATERIALIZATION; 去掉 where_cond 或 having_cond 中新添加的相关列 < cache >(t2.a) = < ref_null_helper >(sum(t3.a)， 子查询重新变成非相关的，这样才能做物化。

执行过程

从执行计划树可以看到有个 filter 算子，其实就是 Item_in_optimizer::val_int 求值， Item_in_optimizer 算子右 child 就是替换好的 exists 子查询，代入当前的 t2.a 作为，进行 exists 子查询求值，能得到 bool 值，从而知晓过滤与否

in 子查询变种

如果子查询 t3 在相关列 a 列有索引，正好可以使用 ref access，Item_in_subselect 在 optimize 阶段会创建 subselect_indexsubquery_engine，然后子查询求值，只需要在子查询的单表进行索引查找即可。

限定条件：

• 子查询必须是单表，简单的 spj，没有 groupby

• 内表相关列必须是索引列，形如：

  outer_expr IN (SELECT tbl.key FROM tbl WHERE subq_where)
  

  复现 case：

  mysql> alter table t3 add  index idx_a(a);
  mysql> desc  select * from t2 where t2.a in  (select a from t3);
  +----+--------------------+-------+------------+----------------+---------------+-------+---------+------+------+----------+-------------+
  | id | select_type        | table | partitions | type           | possible_keys | key   | key_len | ref  | rows | filtered | Extra       |
  +----+--------------------+-------+------------+----------------+---------------+-------+---------+------+------+----------+-------------+
  |  1 | PRIMARY            | t2    | NULL       | ALL            | NULL          | NULL  | NULL    | NULL |    2 |   100.00 | Using where |
  |  2 | DEPENDENT SUBQUERY | t3    | NULL       | index_subquery | idx_a         | idx_a | 5       | func |    1 |   100.00 | Using index |
  +----+--------------------+-------+------------+----------------+---------------+-------+---------+------+------+----------+-------------+
  

执行期执行栈

#0  RefIterator<false>::Read (this=0x7ff5aabc2ac8) 
#1  0x0000000009876fc6 in LimitOffsetIterator::Read (this=0x7ff5aabc2ba0)
#2  0x0000000009726579 in ExecuteExistsQuery (thd=0x7ff5ad009180, unit=0x7ff5ac2409c8, iterator=0x7ff5aabc2ba0, found=0x7ff60d1b0237) 
#3  0x0000000009726688 in subselect_indexsubquery_engine::exec (this=0x7ff5aabc2a90, thd=0x7ff5ad009180) 
#4  0x000000000971b614 in Item_subselect::exec (this=0x7ff5ac23f828, thd=0x7ff5ad009180) 
#5  0x000000000971ba94 in Item_in_subselect::exec (this=0x7ff5ac23f828, thd=0x7ff5ad009180) 
#6  0x000000000971f85f in Item_in_subselect::val_bool_naked (this=0x7ff5ac23f828) 
#7  0x00000000094c9bf6 in Item_in_optimizer::val_int (this=0x7ff5aab18fd0) 
#8  0x000000000987669e in FilterIterator::Read (this=0x7ff5aab1a898) 

IN 子查询变种 2-物化执行

上文提到过，IN 子查询默认执行方式有两种，上章节介绍了 exists，下面就是物化执行的 plan。子查询一定是非相关的，先添加索引物化成临时表，然后在执行 in 算子，在物化表里面进行索引查找

set @@optimizer_switch='subquery_materialization_cost_based=off';
set @@optimizer_switch='semijoin=off';
 desc format=tree  select * from t2 where t2.a in  (select a from t3);
 -> Filter: <in_optimizer>(t2.a,t2.a in (select #2))  (cost=0.45 rows=2)
    -> Table scan on t2  (cost=0.45 rows=2)
    -> Select #2 (subquery in condition; run only once)
        -> Filter: ((t2.a = `<materialized_subquery>`.a))
            -> Limit: 1 row(s)
                -> Index lookup on <materialized_subquery> using <auto_distinct_key> (a=t2.a)
                    -> Materialize with deduplication
                        -> Index scan on t3 using idx_a  (cost=0.45 rows=2)

Item_allany_subselect

 select * from t2 where t2.a > all(select a from t3);
==>强行改写成Item_maxmin_subselect
select * from t2
where
    < not >(
        (t2.a <= < max >(
                /* select#2 */
                select t3.a
                from t3
            ))
    )

prepare 阶段

Item_allany_subselect 被替换为 Item_maxmin_subselect，Item_allany_subselect 是 Item_in_subselect 的子类，也复用 in_subselect 诸多逻辑，比如设置 strategy = CANDIDATE_FOR_IN2EXISTS_OR_MAT， optimize 里面再通过代价决定是物化还是 exists 执行

外层的 where_cond 相当于被改写为:

t2.a > max(select a from t3);#max被解析为Item_maxmin_subselect算子

这个执行方式是内层扫描所有 t3.a，外部有个 max 算子求最大值，扫 t3 全表不可避免。

内存数据结构

(gdb) my e $dl1->m_where_cond   //$dl1为select#1的指针
$do0 (Item_func_not_all *) 0x7ff5aab18c18
`--$do1 (Item_func_le *) 0x7ff5aab19660
   |--$do2 (Item_field *) 0x7ff5ac240768 field = test.t2.a
   `--$do3 (Item_maxmin_subselect *) 0x7ff5aab19480

执行期求值流程：

• Item_maxmin_subselect 算子进行求值，会读取内层 unit 所有的值，对于每个 tuple 发送到 Query_result_max_min_subquery, 这个对象会有个比较函数，进行最大，最小函数求值，然后暂存到 Item_singlerow_subselect cache 对象上，逻辑比较简单，可以看下下列函数**

->Item_maxmin_subselect::val_int
->SELECT_LEX_UNIT::ExecuteIteratorQuery
for (;;) {
   int error = m_root_iterator->Read();
   -->Query_result_max_min_subquery::send_data
   ---->Query_result_max_min_subquery::cmp_int
   ---->Item_singlerow_subselect::store
}

本文介绍了 mysql 全部的子查询原生的执行方式，下一篇我们将重点介绍 mysql 子查询解嵌套以及相关的变换，敬请期待。

出处