MySQL 深潜 - Semijoin 丛林小道全览
MySQL semijoin 也被称为半连接，主要是解决外查询一个或多个表的记录在包含一个或多个表的子查询结果中的存在性问题，比如 IN/EXIST 子查询。如果按照 IN/EXIST 谓词的原语义去执行，对外查询的每行记录都去计算 IN/EXIST 谓词的结果，子查询的内容就需要单独执行，在关联子查询的情况下，子查询需要多次重复执行，整体的执行效率很低。实际上，部分存在性问题(SPJ 子查询)类似于外查询的多个表与子查询的多个表(以下简述为外表和内表)的连接(JOIN)问题，能连接上说明存在。但是与普通 JOIN 不同的点在于，当外表和内表 JOIN 的时候，外表的每行记录都有可能和内表的多行连接上，这就导致了外表行的重复记录，但是按照原语义 IN/EXIST 子查询只是对外表行上进行的过滤，数据只能减少，而不能膨胀。
如何在外表和内表 JOIN 的同时保证这一点呢？MySQL 中实现了四种执行策略来避免重复行：Materialize、DuplicateWeedOut、FirstMatch 和 LooseScan，以下是几种执行方式的简单概括和示意图。
示意图均以该 SQL 举例：
select * from Country
where Country.code IN (select City.Country
from City
where City.Population > 7*1000*1000)
and Country.continent='Europe'
Materialize 是将内表独立进行 JOIN 后的结果物化到临时表并去重，然后将物化表与其他外表做 JOIN 的执行方式。由于物化表已经去重，与外表做 JOIN 并不会引起数据膨胀，所以就变成普通的 JOIN，与外表的 JOIN ORDER 可以任意调整。
DuplicateWeedout 是创建一个临时表，在执行将外表记录的主键写入临时表上带有唯一索引的 rowids 字段，起到对外表因为和内表 JOIN 之后产生的重复行去重的作用。
FirstMatch 是在外表的一行记录和内表 JOIN 得到一行输出后，直接跳过所有内表接下来的数据行，读取外表的下一行执行，从而避免外表产生重复行的方式。
LooseScan 是在内表有索引存在的情况下，通过做内表上的 LooseScan (仅扫描索引记录不相同的行)来达到对内表记录去重的目的，然后和外表进行连接，这样也不会导致外表出现重复行。
Semijoin 的灵活性
为什么要有四种执行策略呢？因为在内外表不同的 JOIN ORDER、索引存在性、不同的 JOIN 条件情况下，只有特定的执行策略才能被应用，四种组合起来才构成了 semijoin JOIN ORDER 的灵活性，MySQL 通过代价来选择 JOIN ORDER 和对应的执行策略。用以下 SQL 举例(后续文章中均采用同一 schema)，ct 表示 correlated table，为外查询中与子查询关联的表；it 表示 inner table，为子查询的内表。
CREATE TABLE t1 (
a INT,
b INT,
KEY(a),
KEY(b)
);
INSERT INTO t1 VALUES (1, 2), (3, 4), (5, 6), (7, 8), (9, 10), (2, 1), (4, 3), (5, 6);
CREATE TABLE ct1 LIKE t1;
INSERT INTO ct1 SELECT * FROM t1;
CREATE TABLE ct2 LIKE t1;
INSERT INTO ct2 SELECT * FROM t1;
CREATE TABLE it1 LIKE t1;
INSERT INTO it1 SELECT * FROM t1;
CREATE TABLE it2 LIKE t1;
INSERT INTO it2 SELECT * FROM t1;
SELECT * FROM ct1, ct2 WHERE ct1.a IN (SELECT it1.a FROM it1, it2 WHERE it2.b = ct2.b);
重点关注 JOIN ORDER 中外表和内表的相对顺序，得到执行策略对 JOIN ORDER 的支持如下：
JOIN ORDER (ct1, ct2), (it1, it2) (it1, it2), (ct1, ct2) ct1, it1, ct2, it2 it1, ct1, it2, ct2 ct1, (it1, it2), ct2 it1, (ct1, ct2), it2 MaterializeScan N1 Y N2 N2 Y N2 MaterializeLookup Y N1 N2 N2 N1 N2 FirstMatch Y N3 N4 N3 N3 N4 DuplicateWeedOut Y Y Y Y Y Y LooseScan N5 N6 N7 N7 Y N7可以看到 DuplicateWeedOut 是最通用的策略，其他的策略只能应用在特定的 JOIN ORDER 下。表格中没有覆盖 it 表之间、ot 表之间交换顺序的情况；以及原 SQL 中还包含其他不和 IN/EXIST 子查询关联的外表时，大部分情况下，该外表可以在 ct 表之间灵活交换顺序，或者处于 semijoin 范围之外任意位置，所以实际场景中每种执行策略支持的 JOIN ORDER 范围会更广。
以下就深入内核，探寻 semijoin 应用的条件和优化器如何根据代价决定 semijoin 执行策略的。
Prepare 阶段
Semijoin 候选子查询的收集
在对外层查询的谓词 resolve/fix_fields() 过程中，递归对子查询 Query_block::prepare，由子查询自身调用 Query_block::resolve_subquery，判断可以转换为 semijoin 的基本条件，如果满足的话，就会将子查询对应的 Item_exists_subselect(Item_in_subselect 的基类)加入外层查询的 Query_block::sj_candidates 数组中，等待递归返回后，外层查询调用 Query_block::flatten_subqueries 处理。这些基本条件包括：
子查询是 IN/EXIST 类型，=ANY 也会是 IN 子查询； 是一个简单查询块(非 UNION/INTERSECT/EXCEPT 等集合操作符组成)； 不带有显式或隐式的聚集函数、不带有 HAVING 和 WINDOW 函数(Semijoin 是将子查询里的表提出来与外层的表先 join 后再做后续运算，而这些操作符都是需要先读取完子查询里的表做运算后才能计算外层的谓词)； 子查询处于 ON/WHERE 语法中，且是 AND 谓词连接的 top level； 谓词 True/False、nullability 是和转换兼容的。简单来说，最主要的条件就是 SPJ 的 IN/EXIST 子查询。
外层查询将子查询的表上拉，消除原子查询
在 bottom-up 的 resolve 过程中，由包含 semijoin 候选的外层查询块将子查询的表上拉，并消除子查询，这一过程在 Query_block::flatten_subqueries 中。
for SELECT#1 WHERE X IN (SELECT #2 WHERE Y IN (SELECT#3)) :
Query_block::prepare() (select#1)
-> fix_fields() on IN condition
-> Query_block::prepare() on subquery (select#2)
-> fix_fields() on IN condition
-> Query_block::prepare() on subquery (select#3)
<- Query_block::prepare()
<- fix_fields()
-> flatten_subqueries: merge #3 in #2
<- flatten_subqueries
<- Query_block::prepare()
<- fix_fields()
-> flatten_subqueries: merge #2 in #1
在外层查询块中，依次遍历所有 semijoin 的候选子查询：
将它们在外层查询块的谓词位置(WHERE 条件或者嵌套 join 的 ON 条件)用恒 True 表达式替换； 创建 semijoin 的 nested Table_ref 结构，加入到嵌套的 join nest 结构或者 outer-most join list 中，以下简称 (sj-nest)； 将子查询所有的表加入到 Table_ref::NESTED_JOIN 中，链接进外层查询的 leaf_tables，给这些表按照外层的 tableno 重新编号； 构建 NESTED_JOIN::sj_outer_exprs 和 NESTED_JOIN::sj_inner_exprs 向量，IN 子查询就是左表达式和子查询投影列一一对应起来，EXIST 子查询就是 WHERE/ON 条件中的关联条件(IN 子查询也会收集这些关联条件来方便执行使用)，被收集的条件原有位置置空或者 True，比如下列谓词：ot1.a = ANY(SELECT it1.a FROM it1, it2)收集到sj_outer_exprs: ot1.a; sj_inner_exprs: it1.a
ot1.a = ANY(SELECT it1.a FROM it1, it2 WHERE it1.b = ot2.b)收集到sj_outer_exprs: ot1.a, ot2.b; sj_inner_exprs: it1.a, it1.b。
之后，在Query_block::apply_local_transforms -> Query_block::simplify_joins中，会对嵌套的 semijoin/anti-join 做简单处理，将嵌套的结构展平，因为外层的结构是 semijoin 时，内层的输出结果是否发生重复也不影响结果，比如A SJ (B SJ (C)) -> A SJ (B JOIN C), A AJ (B SJ (C)) -> A AJ (B JOIN C)。将内层的 semijoin 的表移到外层的 join list 中，并移除原内层 (sj-nest)。记录 (sj-nest) Table_ref::sj_inner_tables 为原子查询所有内表的 used_tables，将所有的 (sj-nest) 加入当前查询块的 Query_block::sj_nests 数组中。
Optimize 阶段(优化器)
MySQL 对 semijoin 的执行支持好几种不同的执行策略，在不同的执行策略下 semijoin 内表和外表的 JOIN ORDER 不同，从而能够提供更为灵活的 JOIN ORDER 选择；不同的执行策略通过不同的方式来达到去重的目的，避免原本的 semijoin 转化为 JOIN 之后的数据膨胀；不同的执行策略可以利用上不同的索引或者表访问方式。这些执行策略包括：FirstMatch、DuplicateWeedout、LooseScan、Materialize，Materialize 根据物化表和外表 JOIN ORDER 的不同又分为 MaterializeScan 和 MaterializeLookup。优化器的目的就是评估这些执行策略的可行性(开关、索引是否支持等)，选择估算代价最低的策略。
执行策略的代价选择
本小节会介绍这些执行策略的公共处理逻辑，具体到每种执行策略的不同和优化细节将会在以下每种执行策略的章节介绍。
主要的过程在 JOIN::make_join_plan 中:
pull_out_semijoin_tables
在 update_ref_and_keys 之后，如果 semijoin 的内表是可以 eq_ref(唯一索引) 外表，且 (sj-nest) 中不存在其他内表依赖它，那么该表就可以从 (sj-nest) 中移出来，放置在外层的 join list 中，因为这样的表和外层表 join 是不会产生数据膨胀的。这样可以简化 (sj-nest) 的内表结构，如果所有的内表都可以被提出来，那么 (sj-nest) 就可以被直接移除，消除了 semijoin。
optimize_semijoin_nests_for_materialization
在外层优化之前，为可能选择 Materialize 执行的 (sj-nest) 优化内表的 JOIN ORDER，计算其 cost 和 fanout，基于这些数据才能在和外层表的优化过程中计算 cost。详细见 Materialize 章节。
Optimize_table_order::best_extension_by_limited_search -> Optimize_table_order::advance_sj_state
每当一个新表(外表 + 子查询的内表)被尝试加入到 JOIN 序列，且选择完它的最优访问方式(best_access_path)后，就会调用 Optimize_table_order::advance_sj_state 考虑此时可用的 semijoin 执行策略，并计算不同策略各自的 cost，选择最低代价的策略作为当前 JOIN 序列的最优策略，存放在当前表的 POSITION 中(不同策略有不同的状态变量)，并且更新最优策略下的代价和 cardinality(prefix_cost 和 prefix_rowcount)。
注意，这里对于部分执行方式，比如 Materilize/FirstMatch 会重新评估一定范围内每个表的访问方式，以算出在当前策略下，选取最优访问方式后的代价。但是这些访问方式的重新考虑并不会持久化到 JOIN::positions 枚举状态中，避免对外层接下来 greedy search 的影响。只是会持久化 prefix_cost/prefix_rowcount 和当前表 POSITION 中记录 semijoin 执行策略选择的变量，如果枚举完整 JOIN 序列仍然是最优 plan，就会持久化到 best_positions 中。所以当整个 greedy search 结束，在Optimize_table_order::fix_semijoin_strategies识别到 POSITION 中关于 semijoin 的策略选择结果，需要对涉及表的访问方式再次做选择，此时持久化访问方式。
具体对每种执行策略在代价上的考虑，在以下各执行策略章节陈述。
Materialize
Materialize 是将 (sj-nest) 的内表 JOIN 结果物化到临时表并去重后，物化表与其他外表做 JOIN 的执行方式。由于物化表已经去重，与外表做 JOIN 并不会引起数据膨胀，所以就变成普通的 JOIN，与外表的 JOIN ORDER 可以任意调整。根据物化表最终是全表扫、还是在临时表上索引的 eq_ref lookup 分为 MaterializeScan 和 MaterializeLookup 两种方式。
优化过程包括：
optimize_semijoin_nests_for_materialization
JOIN::make_join_plan -> optimize_semijoin_nests_for_materialization
|--遍历所有的 (sj-nest)
|--如果 NESTED_JOIN::sj_corr_tables 不为空，意味着子查询存在无法提取的复杂关联条件，这种情况下子查询无法独立物化，跳过
|--semijoin_types_allow_materialization/types_allow_materialization 检查类型能否物化，物化表索引长度是否超过最大值
|--Optimize_table_order::choose_table_order // 对 semijoin 的内表集合选取最优 join order
|--calculate_materialization_costs // 计算物化表的 NDV、物化的代价、全表扫物化表的代价、物化表 lookup 的代价，
// 存放在 NESTED_JOIN::Semijoin_mat_optimize 中，方便后续不同执行策略的代价比较
|--根据优化得到的 best_positions 里每个表的 read_cost 和 evaluate cost 计算物化代价和 fanout 行数
|--fanout 行数简单的与每个表的输出行数乘积取较小值作为物化表的输出 NDV
|--Cost_model_server::tmptable_readwrite_cost 计算物化表操作代价
|--将 best_positions 信息存储在 Semijoin_mat_optimize::positions 数组中作为 (sj-nest) 内表的最优计划
MaterializeScan
SET optimizer_switch='semijoin=on,materialization=on,loosescan=off,firstmatch=off,duplicateweedout=off';
EXPLAIN SELECT /*+ JOIN_SUFFIX(ct1, ct2) */ * FROM ct1, ct2 WHERE ct1.a IN (SELECT it1.a FROM it1, it2 WHERE it2.b = ct2.b);
+----+--------------+-------------+------------+-------+---------------+------+---------+---------------+------+----------+--------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+--------------+-------------+------------+-------+---------------+------+---------+---------------+------+----------+--------------------------------------------+
| 1 | SIMPLE | <subquery2> | NULL | ALL | NULL | NULL | NULL | NULL | NULL | 100.00 | Using where |
| 1 | SIMPLE | ct1 | NULL | ref | a | a | 5 | <subquery2>.a | 1 | 100.00 | NULL |
| 1 | SIMPLE | ct2 | NULL | ref | b | b | 5 | <subquery2>.b | 1 | 100.00 | NULL |
| 2 | MATERIALIZED | it1 | NULL | index | a | a | 5 | NULL | 16 | 100.00 | Using index |
| 2 | MATERIALIZED | it2 | NULL | index | b | b | 5 | NULL | 16 | 100.00 | Using index; Using join buffer (hash join) |
+----+--------------+-------------+------------+-------+---------------+------+---------+---------------+------+----------+--------------------------------------------+
| -> Nested loop inner join (cost=259 rows=334)
-> Nested loop inner join (cost=142 rows=293)
-> Filter: ((`<subquery2>`.a is not null) and (`<subquery2>`.b is not null)) (cost=53.2..39.2 rows=256)
-> Table scan on <subquery2> (cost=53.3..59 rows=256)
-> Materialize with deduplication (cost=53.3..53.3 rows=256)
-> Filter: ((it1.a is not null) and (it2.b is not null)) (cost=27.7 rows=256)
-> Inner hash join (no condition) (cost=27.7 rows=256)
-> Index scan on it2 using b (cost=0.116 rows=16)
-> Hash
-> Index scan on it1 using a (cost=1.85 rows=16)
-> Index lookup on ct1 using a (a=`<subquery2>`.a) (cost=0.286 rows=1.14)
-> Index lookup on ct2 using b (b=`<subquery2>`.b) (cost=73.2 rows=1.14)
|
Optimize_table_order::advance_sj_state
开始考虑 MaterializeScan 执行方式的前提条件(semijoin_order_allows_materialization)为，当前表为 (sj-nest) 内表，且所有其他内表都出现在前序且连续。代码里用 POSITION::sjm_scan_last_inner 来表示内表的最后一个位置，从下标sjm_scan_last_inner - Table_ref::sj_inner_tables + 1 ~ sjm_scan_last_inner为内表 POSITION 的范围。
从这个位置开始，将 POSITION::sjm_scan_need_tables 设置为所有 sj_inner_tables 和 NESTED_JOIN::sj_depends_on(semijoin条件依赖的外表)的集合，表示当这些表都处于 JOIN 前序时，才能做 MaterializeScan 的 JOIN。满足条件的情况下，会基于物化表的 fanout 重新评估 sjm_scan_last_inner 到当前位置所有外表的访问方式(遍历表调用 best_access_path 传入新的 fanout)，来计算如果选择 MaterializeScan 执行策略的代价，这个过程在Optimize_table_order::semijoin_mat_scan_access_paths中。
MaterializeLookup
SET optimizer_switch='semijoin=on,materialization=on,loosescan=off,firstmatch=off,duplicateweedout=off';
EXPLAIN SELECT * FROM ct1, ct2 WHERE ct1.a IN (SELECT it1.a FROM it1, it2 WHERE it2.b = ct2.b);
+----+--------------+-------------+------------+--------+---------------------+---------------------+---------+-----------------------+------+----------+------------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+--------------+-------------+------------+--------+---------------------+---------------------+---------+-----------------------+------+----------+------------------------------------------------------+
| 1 | SIMPLE | ct1 | NULL | ALL | a | NULL | NULL | NULL | 8 | 100.00 | Using where |
| 1 | SIMPLE | ct2 | NULL | range | b | b | 5 | NULL | 8 | 100.00 | Using index condition; Using join buffer (hash join) |
| 1 | SIMPLE | <subquery2> | NULL | eq_ref | <auto_distinct_key> | <auto_distinct_key> | 10 | test.ct1.a,test.ct2.b | 1 | 100.00 | NULL |
| 2 | MATERIALIZED | it1 | NULL | index | a | a | 5 | NULL | 16 | 100.00 | Using index |
| 2 | MATERIALIZED | it2 | NULL | index | b | b | 5 | NULL | 16 | 100.00 | Using index; Using join buffer (hash join) |
+----+--------------+-------------+------------+--------+---------------------+---------------------+---------+-----------------------+------+----------+------------------------------------------------------+
| -> Nested loop inner join (cost=1653 rows=16384)
-> Inner hash join (no condition) (cost=7.7 rows=64)
-> Index range scan on ct2 using b over (NULL < b), with index condition: (ct2.b is not null) (cost=0.131 rows=8)
-> Hash
-> Filter: (ct1.a is not null) (cost=1.05 rows=8)
-> Table scan on ct1 (cost=1.05 rows=8)
-> Single-row index lookup on <subquery2> using <auto_distinct_key> (a=ct1.a, b=ct2.b) (cost=53.3..53.3 rows=1)
-> Materialize with deduplication (cost=53.3..53.3 rows=256)
-> Filter: ((it1.a is not null) and (it2.b is not null)) (cost=27.7 rows=256)
-> Inner hash join (no condition) (cost=27.7 rows=256)
-> Index scan on it2 using b (cost=0.116 rows=16)
-> Hash
-> Index scan on it1 using a (cost=1.85 rows=16)
|
Optimize_table_order::advance_sj_state
考虑 MaterializeLookup 执行策略的条件为，（sj-nest) 的内表在 JOIN 前序紧密相连，且 semijoin 条件依赖的外表也都出现了，那么就可以考虑在物化表上使用 eq_ref 的 JOIN 方式。在semijoin_mat_lookup_access_paths函数中，基于前序最后一个外表的 prefix_rowcount 来计算物化表 lookup 的代价，加上物化表 setup 的代价作为这种执行方式的最终代价。
DuplicateWeedOut
DuplicateWeedout 适用的范围更广，原外层表和内层表之间的 JOIN ORDER 可以更灵活，实现原理就是创建一个临时表起到对外表因为和内表 JOIN 之后产生的数据膨胀去重的作用。当外表和 (sj-nest) 内表 JOIN 之后，会将 semijoin 涉及的外表主键紧密连接到一起，形成字符串写入 weedout-tmp 临时表的 rowids 字段中，在这个字段上存在唯一索引。如果写入成功，说明当前行组合是第一次出现，继续往后 JOIN；否则直接跳过该行。
SET optimizer_switch='semijoin=on,materialization=off,loosescan=off,firstmatch=off,duplicateweedout=on';
# 传统格式的 EXPLAIN 中比较明显的标识是 Start temporary/End temporary。
EXPLAIN SELECT * FROM ct1, ct2 WHERE ct1.a IN (SELECT it1.a FROM it1, it2 WHERE it2.b = ct2.b);
+----+-------------+-------+------------+-------+---------------+------+---------+------------+------+----------+------------------------------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered |
文章来源：
Author：李博
link：/monthly/monthly/2024/06/02/