数据库内核月报

数据库内核月报 - 2021 / 06

MySQL · 源码分析 · Semi-join优化与执行逻辑

Author: 遥凌

Semi-join 语义

在MySQL中,Semi-join是专门针对SPJ IN/Exists子查询进行优化的一种join语义,起到了对外层表的过滤作用,通过将相关/非相关subquery unnesting为semi join来充分利用join reordering的灵活性,以期获取最高的执行效率,正因为如此,其实现非常灵活多变,共有4种不同的实现策略。 本文主要针对semi-join(antijoin处理类似),描述其整体处理流程和具体细节代码,虽然复杂,但MySQL对于semi-join的处理并不像对于group by/distinct的实现逻辑如此杂乱,还是比较有章可循,因此允许我们顺着rewrite -> optimize的代码流程进行分析。

本篇是对MySQL代码实现的分析,涉及比较多的细节,如果只需要大概了解semi-join是什么以及MySQL处理它的4种策略大致是什么,可以参看之前的月报:

https://www.bookstack.cn/read/aliyun-rds-core/ecc50d80e6916bc3.md

代码版本 MySQL 8.0.18

Notation

我们称在外层子查询当中的相关表outer table,ot1, ot2 … 这其中如果是在inner subquery的where condition中依赖的外表相关表,记为non-trivially correlated outer table,ct1, ct2… 外层query block中,不相关的table,记为non-correlated outer table, nt1, nt2…. 内层query block中的表,记为inner table, it1, it2….

代码流程

Rewrite Phase

将真正可以融合的(有table),建立sj-nest这个TABLE_LIST对象,基本思路就是想将inner table放到外层的join list中,内层的(oe1, … oeM) = (ie1, …, ieM) / inner-cond 都放在外层对应的ON/WHERE条件上,这里分为3种情况:

  1. subq_pred->embedding_join_nest->nested_join 存在
... [LEFT] JOIN  ( ... ) ON (subquery AND condition) ...

这种形式,sj-nest这个TABLE_LIST会放到JOIN后面的 ( … ) 当中

  1. subq_pred->embedding_join_nest->outer_join 不为true
... INNER JOIN tblX ON (subquery AND condition) ...

没有nested join(只有一个tblX)且是INNER JOIN,sj-nest直接append到tblX所在这层的join list中

  1. subq_pred->embedding_join_nest->outer_join 为true
... LEFT JOIN tbl ON (subquery AND condition) ...  
				     ( tbl SJ (subq_tables) )
 					 |                         |
					 |<---- wrap_nest --->|

没有nested join,是left join on tbl的形式,为保证正确性,需要把tbl替换为上面这个(wrap-nest)的TABLE_LIST对象,如下

... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_cond) ...

sj-nest是后续优化semi-join的一个重要结构,会用subq SELECT_LEX中的内容对其进行填充,填充内容如下:

Optimize Phase

Execution Phase

在完成基本的优化后,最重要的函数就是setup_semijoin_dups_elimination,它会创建具体的semi-join执行结构,这个函数的注释中包含了非常重要的信息,描述了每种执行策略,各自可以产生怎样的QEP_TAB序列,这里的描述也将以此为基础,对各个策略的执行结构和必要函数/结构/字段做描述,并分析下MySQl是怎么保证semi-join结果正确性的

setup_semijoin_dups_elimination

(ot|nt)*  [ it (it)* ]  (nt)*
+------+  +==========+  +---+
   (1)         (2)        (3)

所有inner table必须邻接排列,且在所有outer tables的后面

​ MaterializeScan

 (ot|nt)*  [ it (it)* ]  (ot|nt)*
 +------+  +==========+  +-----+
    (1)         (2)         (3)

所有inner table必须邻接排列,且在所有outer tables的前面 由于sj_strategy都标记在了第一个inner table上,而物化的inner table不在primary tables中,这里只有sjm table,因此这里无需做处理,具体执行时,在sjm所对应的QEP_TAB开始执行时,会先通过preprare_scan函数完成inner tables的物化+去重,后续无需特殊处理

(ot|ct|nt) [ loosescan_tbl (ot|nt|it)* it ]  (ot|nt)*
+--------+   +===========+ +=============+   +------+
   (1)           (2)          (3)              (4)

这里的要求是,所有non-trivially correlated outer tables必须都在inner tables的前面,这是必须的因为loosescan是对内表去重,如果有相关表在外层,它会决定内表的内容,因此必须要在于相关表join完成后再做去重,避免数据错误(如 本可以通过与ct做join过滤掉的tuple,却被保留下来参与了与nt/ot的join ) loosescan要求在第一个inner table上使用Index,对后续range(3)使用了first match策略,从而保证整个inner table范围内,做到了去重,在(3)的范围内,目前MySQL的实现是不允许有ot/nt的,虽然图示如此 相关执行结构: last_sj_tab,也就是整个range的最后一个tab的idx,设置给loose scan driving tab->match_tab driving tab的idx和last_sj_tab的idx,设置给last_sj_tab的firstmatch_return/match_tab loosescan_tbl->loosescan_buf/loosescan_tbl->loosescan_key_len,用来保存looscan keypart的buffer及其长度,用来在上层显式的skip掉重复index entry

 (ot|nt)*  [ it ((it|nt)* it) ]  (nt)*
 +------+  +==================+  +---+
   (1)             (2)          (3)

在inner table的range之内,是可以有nt表的,对于这种情况,MySQL会使用一种”split jump”的执行方式,即: 这里的序号1/2是第i行的意思 通过这种方式,nt1中的每行都还是正常被join到的,只是通过jump的方式保证了inner table不会有重复行 执行结构: firstmatch_return在每个jump range最后一个inner table上,记录跳回的range的起始tab idx match_tab 记录last inner table的位置,不随jump range变化

ot -> [it1 -> nt1 -> it3 ]
=>  1  ->  1   ->  1    ->  1
<- jump
2    ->   1
2    ->   2
<- jump
.....					
<- jump
2  ->  1
2  ->  2  ->   1    ->  1
....
(ot|nt)*  [ it ((it|ot|nt)* (it|ot))]  (nt)*
+------+  +=========================+  +---+
  (1)                 (2)               (3)

DuplicateWeedout的执行和MySQL nested-loop的执行方式有比较强的耦合:
如果在range (2) 范围内没有使用join buffer,则从range (1)中输入进来的每一行row combination,可以通过一个have_confluent_row标记来简化执行,也就是判断如果prefix部分到来的是不是新的一行 row comibination,则由于已经join过了,所以不再进一步处理,只有当每次时新的行时,才做处理!这样保证了range (1) 范围内的outer table,是没有重复列的,而对于range (2)范围内的ot|nt,则需要将其row id加入到tmp table distinct key中来完成去重如果在range (2) 范围内使用了join buffer,上面所描述的方案将无法成立,因为没法保证每到来一个range (1) 中的 row combination,是新的一行数据因此只能将整个range (1) + range (2)的所有 ot+nt的rowid,作为distinct keypart,加入到tmp table中,完成去重 执行结构:create_sj_tmp_table: 根据SJ_TMP_TABLE::TAB数组中描述的需要记录rowid的各个table,创建SJ_TMP_TABLE对象,保存在first inner table->flush_weedout_table上,以及 range的最后一个inner table->check_weed_out_table上 create_duplicate_weedout_tmp_table: 创建实际去重的tmp table + distinct key,这个table保存在SJ_TMP_TABLE::tmp_table字段上。

总结

文中涉及的代码细节很多也比较复杂,需要大家结合实际代码来看。

另外在调试中发现了社区对于semi-join materialization代价信息的填充中的一个明显bug,具体问题是在完成sjm的优化后,需要将sjm table的代价信息存入到外层join序列的POSITION数组中,而MySQL选择了错误的position序列导致访问了不正确的结构,具体参看 https://bugs.mysql.com/bug.php?id=103997