mysql 子查询执行方式介绍

本贴最后更新于 548 天前,其中的信息可能已经物是人非

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 子查询解嵌套以及相关的变换,敬请期待。

出处

  • MySQL

    MySQL 是一个关系型数据库管理系统,由瑞典 MySQL AB 公司开发,目前属于 Oracle 公司。MySQL 是最流行的关系型数据库管理系统之一。

    692 引用 • 535 回帖 • 2 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...