第一章 背景介绍
笛卡尔积在 TiDB 执行计划中经常出现，该类执行计划又极其消耗数据库资源，容易引发执行速度慢，消耗大量内存，甚至引发 OOM 的情况。本文将着重研究因 TiDB 对 NULL Aware 的不完全支持，导致的笛卡尔积情况，期望对后续数据库问题分析提供参考, 及自己更深入理解 SQL 的编译及优化过程。
具体内容为：
首先，简述 TiDB 优化器的实现方式及一条 SQL 什么情况下会产生 Semi Join / Anti Semi Join / Left Outer Semi Join / Anti Left Outer Semi Join。
其次，将其与 NULL Aware 在 TiDB 中的实现现状结合分析，因 NULL Aware 问题产生笛卡尔积的原因。
最后，基于 TiDB 在不同版本下的不同支持程度，提供改写或升级建议。
一、TiDB 编译
具体 TiDB 实现中，Compile() 函数是串联 Preprocess(主要用于语法检查，语义检查，schema 检查等) 及 Optimize（构造初始逻辑执行计划，逻辑优化，物理优化） 两阶段的关键函数。在 OptimizeExecStmt 会首次基于 AST 构造初始逻辑计划，其实从代码分类上看已经进入了 Optimize 阶段，主要操作是基于 AST 中存在的符号转译成一一对应的逻辑算子，这部分流程是硬编码的，一种函数或 join 连接就代表一类逻辑算子。最后通过自低向上的递归遍历,将所有 AST Node 转换成逻辑算子，构造初始执行计划。
比如：select sum(col_1) from table_x group by col_1 当识别到 sum() 函数的 AST Node 后，在该阶段生成一个 AGG 逻辑算子，对应下图所示的 HashAgg_11。随后，进入到 逻辑优化 及 物理优化 阶段。
mysql> create table jan(id int,name varchar(20));
mysql> explain select sum(id) from jan;
+----------------------------+----------+-----------+---------------+----------------------------------+
| id | estRows | task | access object | operator info |
+----------------------------+----------+-----------+---------------+----------------------------------+
| HashAgg_11 | 1.00 | root | | funcs:sum(Column#5)->Column#4 |
| └─TableReader_12 | 1.00 | root | | data:HashAgg_5 |
| └─HashAgg_5 | 1.00 | cop[tikv] | | funcs:sum(test.jan.id)->Column#5 |
| └─TableFullScan_10 | 10000.00 | cop[tikv] | table:jan | keep order:false, stats:pseudo |
+----------------------------+----------+-----------+---------------+----------------------------------+
二、逻辑优化
下面一些过去已总结的内容, What's Logical Optimizing in TiDB | Jan-Blog-EN, 在 TiDB 中逻辑优化就是以固定的顺序(下述), 从头到尾的依次基于规则改写逻辑执行计划. 如: gcSubstituter 生成列改写优化, ppdSolver 谓词下推, columnPruner 列裁剪, joinReOrderSolver 重排序表链接顺序.
// 逻辑优化必走的流程
var optRuleList = []logicalOptRule{
&gcSubstituter{},
&columnPruner{},
&resultReorder{},
&buildKeySolver{},
&decorrelateSolver{},
&semiJoinRewriter{},
&aggregationEliminator{},
&skewDistinctAggRewriter{},
&projectionEliminator{},
&maxMinEliminator{},
&ppdSolver{},
&outerJoinEliminator{},
&partitionProcessor{},
&collectPredicateColumnsPoint{},
&aggregationPushDownSolver{},
&pushDownTopNOptimizer{},
&syncWaitStatsLoadPoint{},
&joinReOrderSolver{},
&columnPruner{}, // column pruning again at last, note it will mess up the results of buildKeySolver
}
三、物理优化
物理优化主要工作，是基于逻辑算子衍生物理算子并计算不同物理算子选择下的 cost 大小，取最小 cost 的执行计划作为最终执行计划。What's Psysical Optimizing in TiDB | Jan-Blog-EN, 下面只列举了 Table reader 做为案例,其他 CBO 数据库优化器大致也是这样实现的,只是具体公式不同.
// 物理优化的计算公式
child-cost + rows * row-size * net-factor + num-tasks * seek-factor
cost = -------------------------------------------------------------------------
tidb_distsql_scan_concurrency
第二章 理论概括
本章理论概括主要包含，semi join 在 TiDB 中的实现及触发 semi join 使用场景来说明，即 : 什么情况下会遇到 semi join 执行计划。并在第三部分说明为什么 semi join 需要 Null Aware，并在下一章现状分析中分析由于 TiDB 对 Null Aware 的不安全实现为什么会导致 cartesian 的出现。
一、TiDB 的 Semi Join 实现
涉及到 semi join 的一共有 4 种逻辑算子定义，定义在 logical_plans.go 中，如下所示。
// SemiJoin means if row a in table A matches some rows in B, just output a.
SemiJoin
// AntiSemiJoin means if row a in table A does not match any row in B, then output a.
AntiSemiJoin
// LeftOuterSemiJoin means if row a in table A matches some rows in B, output (a, true), otherwise, output (a, false).
LeftOuterSemiJoin
// AntiLeftOuterSemiJoin means if row a in table A matches some rows in B, output (a, false), otherwise, output (a, true).
AntiLeftOuterSemiJoin
在 AST 中并没有 semi join 这种类型，只有官方定义的 Inner Join, Left Outer Join, Right Outer Join, Full Outer Join 和 Cross Join 共 5 种，会产生下述 semi join 的动作在 buildSemiApply 中（Apply 在 TiDB 中比较特殊，代表只会使用 Nested-Loop 的物理算子进行 Join 的逻辑算子，这个 Apply 算子会在后期优化中改写掉）, 共有 4 个函数会调用该函数，分别为 buildQuantifierPlan, buildSemiApplyFromEqualSubq, handleExistSubquery, handleInSubquery 这 4 个函数中，均属于 expressionRewriter 这个结构。
-
handleExistSubquery, handleInSubquery 顾名思义，就是对应 SQL 写法的直接生成。
-
buildSemiApplyFromEqualSubq 主要处理
a = any(subq)及a != all(subq)情况，这 2 种情况会被改写成a in (subq)或a not in (subq)的处理方式，再进行后续逻辑算子的生成。 -
buildQuantifierPlan 主要被 handleOtherComparableSubq，handleNEAny， handleEQAll 这 3 个函数调用。
- handleOtherComparableSubq 处理 “< any, < max” 的使用场景，例如： t.id < any (select s.id from s)将被改写成 to t.id < (select max(s.id) from s)。
- handleNEAny 处理 != any 的使用场景，例如：t.id != any (select s.id from s) 将被改写成 t.id != s.id or count(distinct s.id) > 1 or [any checker]。 如果 s.id 中有两个不同的值，则必须存在一个不等于 t.id 的s.id。
- handleEQAll 处理 = all 的使用场景，例如：t.id = all (select s.id from s) 将被改写成 t.id = (select s.id from s having count(distinct s.id) <= 1 and [all checker])。
因此，涉及 TiDB 中与 semi join 有关的使用方式共有 8 种：exists / not exists / in / not in / != any / = all / < any / < max。
二、Semi Join 使用场景细分
第一章介绍过构造初始逻辑计划时，是函数或表达式与逻辑算子是 1v1 转化的。下面表格中展示逻辑算子与 SQL 写法的对应关系，逻辑来自于 buildSemiJoin 函数，not 表示 not exist 或者 not in，asScalar 表示 Scalar value means a single value, but not a nil value or vector. 即：主要由 not 和 asScalar 控制最终生成什么逻辑算子。
函数值 — asScalar | not |
true |
false |
SQL Expression |
true |
AntiLeftOuterSemiJoin |
AntiSemiJoin |
Not in / not Exists |
false |
LeftOuterSemiJoin |
SemiJoin |
In / Exists |
asScalar 决定是否为 LeftOuterSemiJoin, Not 决定是否为 Anti |
所谓的 asScalar 的作用就是在 semi join 的基础上，因为可能要与其它条件进行 or 运算，所以需要保留左表的全部列并输出一个额外的列(True/False)，来表示是否有匹配。如下述：HashJoin_9 中 probe 表的某一行 a 匹配上了 build 表的任意一行，则输出 a, true，否则输出 a, false，之后这个布尔列会在 Selection_8 与 a>1 进行 or，统一对 a 列进行筛选。
create table t(a int not null);
explain select * from t t1 where t1.a>1 or t1.a in (select a from t);
+---------------------------------+---------+-----------+---------------+------------------------------------------------------+
| id | estRows | task | access object | operator info |
+---------------------------------+---------+-----------+---------------+------------------------------------------------------+
| Projection_7 | 0.80 | root | | test.t.a |
| └─Selection_8 | 0.80 | root | | or(gt(test.t.a, 1), Column#5) |
| └─HashJoin_9 | 1.00 | root | | left outer semi join, equal:[eq(test.t.a, test.t.a)] |
| ├─TableReader_13(Build) | 1.00 | root | | data:TableFullScan_12 |
| │ └─TableFullScan_12 | 1.00 | cop[tikv] | table:t | keep order:false, stats:pseudo |
| └─TableReader_11(Probe) | 1.00 | root | | data:TableFullScan_10 |
| └─TableFullScan_10 | 1.00 | cop[tikv] | table:t1 | keep order:false, stats:pseudo |
+---------------------------------+---------+-----------+---------------+------------------------------------------------------+
7 rows in set (0.00 sec)
三、为什么需要 Null Aware
Left Outer Semi Join 及 Semi Join 与 Inner Join 本质上其实都是 join 的变种，他们的区别在于结果是否考虑 NULL 的情况。Semi Join 与 Inner Join 的结果都是二值性(True False)的，但 Left Outer Semi Join 是三值性(True False Null)的。因此，Left Outer Semi Join 的 semi join 本身具有结果的特殊性，需要单独处理。
好比 inner join 和 semi join 只需考虑 join 上的情况，而 (anti) left outer semi join 要考虑 Null join 不上的情况。
- Semi Join 与 Inner Join 的结果只有 True 和 False
select * from Outer_Table outer, Inner_Table inner where outer.id = inner.id; |
|||
Join 的列值 — Outer.id | Inner.id |
NULL |
() |
值 [例如：(1)] |
NULL |
False [NULL in NULL] |
False [ () in NULL ] |
False [ 1 in NULL ] |
() |
False [NULL in () ] |
False [ () in () ] |
False [ 1 in () ] |
值 [例如：(1)] |
False [NULL in (1) ] |
False [ () in (1) ] |
True [ 1 in (1) ] |
- Left Outer Semi Join 的结果需要考虑 NULL 的情况
select * from Outer_Table outer where outer.id in (select id from Inner_Table); |
|||
Join 的列值 — Outer | Inner |
NULL |
值[例如：1] |
值(例如：1) |
NULL |
NULL [NULL in NULL] |
NULL [ 1 in NULL ] |
False [ 1 in NULL ] |
值 [例如：(1)] |
NULL [NULL in (1) ] |
True [ 1 in (1) ] |
True [ 1 in (1) ] |
值 [例如：(1, NULL)] |
NULL [NULL in (1, NULL) ] |
NULL [ 1 in NULL ] |
四、SQL 与算子对应关系
注意：下述情况只描述关联列可为 Null 的情况，如果为 Not Null 就不需要 Null Aware，也不会出现 Cartesian，可自行测试，不在此展开。
drop table if exists t1,t2;
CREATE TABLE t2(a int(11) Not NULL, b int(11) Not NULL,KEY idx(a));
CREATE TABLE t1(a int(11) Not NULL, b int(11) Not NULL, KEY idx (a));
explain SELECT * FROM t1 WHERE EXISTS ( SELECT * FROM t2 WHERE t1.a = t2.a );
explain SELECT * FROM t1 WHERE not EXISTS ( SELECT * FROM t2 WHERE t1.a = t2.a );
explain select case when (exists(select 1 from t1 where t1.a = t2.a)) then 1 else 0 end, t2.b from t2;
explain select case when (Not exists(select 1 from t1 where t1.a = t2.a)) then 1 else 0 end, t2.b from t2;
explain SELECT * FROM t1 WHERE t1.a in (SELECT a FROM t2);
explain SELECT * FROM t1 WHERE t1.a not in (SELECT a FROM t2);
explain select case when (t2.a not in (select t1.a from t1)) then 1 else 0 end, t2.b from t2;
explain select case when (t2.a in (select t1.a from t1)) then 1 else 0 end, t2.b from t2;
不需要 Null Aware 的情况
针对 Exists 产生的 semi join 或 anti semi join ,无论列属性限制了是否为 NULL, 都不需要 Null Aware， 因为不需要 asScalar 输出，所以无论 Null 和 False 对于 semi join 或 anti semi join 效果等效。
对于 In 的 semi join 本身结果就是二值性的，如例：1.5 所示，所以不需要 Null Aware。不过这里值得一提的是因为 semi join 与 inner join 结果一致，所以直接将其改写为 inner join。具体操作为 unique column 直接构建 inner join，非 unique column 在构建内表时，需要使用 funcs:firstrow 函数去重，因为在做 in 判断时内表在定义上不能有重复值，详情参考。
以下执行计划，均采用下述代码块表及对应的 SQL 变种构造。
CREATE TABLE t2(a int(11) DEFAULT NULL, b int(11) DEFAULT NULL,KEY idx(a));
CREATE TABLE t1(a int(11) DEFAULT NULL, b int(11) DEFAULT NULL, KEY idx (a));
mysql> select version();
+--------------------+
| version() |
+--------------------+
| 5.7.25-TiDB-v7.0.0 |
+--------------------+
1 row in set (0.00 sec)
EXISTS 的 Semi join
mysql> explain SELECT * FROM t1 WHERE EXISTS ( SELECT * FROM t2 WHERE t1.a = t2.a );
+-----------------------------+----------+-----------+------------------------+---------------------------------------------+
| id | estRows | task | access object | operator info |
+-----------------------------+----------+-----------+------------------------+---------------------------------------------+
| HashJoin_21 | 7992.00 | root | | semi join, equal:[eq(test.t1.a, test.t2.a)] |
| ├─IndexReader_35(Build) | 9990.00 | root | | index:IndexFullScan_34 |
| │ └─IndexFullScan_34 | 9990.00 | cop[tikv] | table:t2, index:idx(a) | keep order:false, stats:pseudo |
| └─TableReader_30(Probe) | 9990.00 | root | | data:Selection_29 |
| └─Selection_29 | 9990.00 | cop[tikv] | | not(isnull(test.t1.a)) |
| └─TableFullScan_28 | 10000.00 | cop[tikv] | table:t1 | keep order:false, stats:pseudo |
+-----------------------------+----------+-----------+------------------------+---------------------------------------------+
6 rows in set (0.00 sec)
Not Exists 的 Anti Semi Join
mysql> explain SELECT * FROM t1 WHERE not EXISTS ( SELECT * FROM t2 WHERE t1.a = t2.a );
+-----------------------------+----------+-----------+------------------------+--------------------------------------------------+
| id | estRows | task | access object | operator info |
+-----------------------------+----------+-----------+------------------------+--------------------------------------------------+
| HashJoin_19 | 8000.00 | root | | anti semi join, equal:[eq(test.t1.a, test.t2.a)] |
| ├─IndexReader_31(Build) | 10000.00 | root | | index:IndexFullScan_30 |
| │ └─IndexFullScan_30 | 10000.00 | cop[tikv] | table:t2, index:idx(a) | keep order:false, stats:pseudo |
| └─TableReader_27(Probe) | 10000.00 | root | | data:TableFullScan_26 |
| └─TableFullScan_26 | 10000.00 | cop[tikv] | table:t1 | keep order:false, stats:pseudo |
+-----------------------------+----------+-----------+------------------------+--------------------------------------------------+
Exists 的 Left Outer Semi Join
mysql> explain select case when (exists(select 1 from t1 where t1.a = t2.a)) then 1 else 0 end, t2.b from t2;
+-------------------------------+----------+-----------+------------------------+--------------------------------------------------------+
| id | estRows | task | access object | operator info |
+-------------------------------+----------+-----------+------------------------+--------------------------------------------------------+
| Projection_8 | 10000.00 | root | | case(Column#11, 1, 0)->Column#12, test.t2.b |
| └─HashJoin_19 | 10000.00 | root | | left outer semi join, equal:[eq(test.t2.a, test.t1.a)] |
| ├─IndexReader_31(Build) | 10000.00 | root | | index:IndexFullScan_30 |
| │ └─IndexFullScan_30 | 10000.00 | cop[tikv] | table:t1, index:idx(a) | keep order:false, stats:pseudo |
| └─TableReader_27(Probe) | 10000.00 | root | | data:TableFullScan_26 |
| └─TableFullScan_26 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
+-------------------------------+----------+-----------+------------------------+--------------------------------------------------------+
6 rows in set (0.01 sec)
Not exists 的 Anti Left Outer Semi Join
mysql> explain select case when (Not exists(select 1 from t1 where t1.a = t2.a)) then 1 else 0 end, t2.b from t2;
+-------------------------------+----------+-----------+------------------------+-------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+-------------------------------+----------+-----------+------------------------+-------------------------------------------------------------+
| Projection_8 | 10000.00 | root | | case(Column#11, 1, 0)->Column#12, test.t2.b |
| └─HashJoin_19 | 10000.00 | root | | anti left outer semi join, equal:[eq(test.t2.a, test.t1.a)] |
| ├─IndexReader_31(Build) | 10000.00 | root | | index:IndexFullScan_30 |
| │ └─IndexFullScan_30 | 10000.00 | cop[tikv] | table:t1, index:idx(a) | keep order:false, stats:pseudo |
| └─TableReader_27(Probe) | 10000.00 | root | | data:TableFullScan_26 |
| └─TableFullScan_26 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
+-------------------------------+----------+-----------+------------------------+-------------------------------------------------------------+
6 rows in set (0.01 sec)
In 的 Semi join 改写 Inner join
mysql> explain SELECT * FROM t1 WHERE t1.a in (SELECT a FROM t2);
+--------------------------------+----------+-----------+------------------------+----------------------------------------------------------+
| id | estRows | task | access object | operator info |
+--------------------------------+----------+-----------+------------------------+----------------------------------------------------------+
| HashJoin_25 | 9990.00 | root | | inner join, equal:[eq(test.t1.a, test.t2.a)] |
| ├─StreamAgg_48(Build) | 7992.00 | root | | group by:test.t2.a, funcs:firstrow(test.t2.a)->test.t2.a |
| │ └─IndexReader_49 | 7992.00 | root | | index:StreamAgg_41 |
| │ └─StreamAgg_41 | 7992.00 | cop[tikv] | | group by:test.t2.a, |
| │ └─IndexFullScan_33 | 9990.00 | cop[tikv] | table:t2, index:idx(a) | keep order:true, stats:pseudo |
| └─TableReader_52(Probe) | 9990.00 | root | | data:Selection_51 |
| └─Selection_51 | 9990.00 | cop[tikv] | | not(isnull(test.t1.a)) |
| └─TableFullScan_50 | 10000.00 | cop[tikv] | table:t1 | keep order:false, stats:pseudo |
+--------------------------------+----------+-----------+------------------------+----------------------------------------------------------+
8 rows in set (0.00 sec)
需要 Null Aware 的情况
Not In 使用场景需要 Null Aware，相对于 semi join 来说需要知道哪些情况是没 join 上的结果，也是因为 anti semi join 的三值性，即：需要考虑 NULL 的情况。
Not in 的 Anti Semi Join
mysql> explain SELECT * FROM t1 WHERE t1.a not in (SELECT a FROM t2);
+-----------------------------+----------+-----------+------------------------+-------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+-----------------------------+----------+-----------+------------------------+-------------------------------------------------------------+
| HashJoin_8 | 8000.00 | root | | Null-aware anti semi join, equal:[eq(test.t1.a, test.t2.a)] |
| ├─IndexReader_14(Build) | 10000.00 | root | | index:IndexFullScan_13 |
| │ └─IndexFullScan_13 | 10000.00 | cop[tikv] | table:t2, index:idx(a) | keep order:false, stats:pseudo |
| └─TableReader_10(Probe) | 10000.00 | root | | data:TableFullScan_9 |
| └─TableFullScan_9 | 10000.00 | cop[tikv] | table:t1 | keep order:false, stats:pseudo |
+-----------------------------+----------+-----------+------------------------+-------------------------------------------------------------+
5 rows in set (0.00 sec)
Not in 的 Anti Left Outer Semi Join
mysql> explain select case when (t2.a not in (select t1.a from t1)) then 1 else 0 end, t2.b from t2;
+-------------------------------+----------+-----------+------------------------+------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+-------------------------------+----------+-----------+------------------------+------------------------------------------------------------------------+
| Projection_7 | 10000.00 | root | | case(Column#10, 1, 0)->Column#11, test.t2.b |
| └─HashJoin_8 | 10000.00 | root | | Null-aware anti left outer semi join, equal:[eq(test.t2.a, test.t1.a)] |
| ├─IndexReader_14(Build) | 10000.00 | root | | index:IndexFullScan_13 |
| │ └─IndexFullScan_13 | 10000.00 | cop[tikv] | table:t1, index:idx(a) | keep order:false, stats:pseudo |
| └─TableReader_10(Probe) | 10000.00 | root | | data:TableFullScan_9 |
| └─TableFullScan_9 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
+-------------------------------+----------+-----------+------------------------+------------------------------------------------------------------------+
6 rows in set (0.00 sec)
In 的 Left Outer Semi Join
针对 “In 的 Left Outer Semi Join” 情况，目前 TiDB 还无法有效实现对笛卡尔积的消除，建议改写为 exists 方法绕过。
mysql> explain select case when (t2.a in (select t1.a from t1)) then 1 else 0 end, t2.b from t2;
+-------------------------------+----------+-----------+------------------------+---------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+-------------------------------+----------+-----------+------------------------+---------------------------------------------------------------------+
| Projection_7 | 10000.00 | root | | case(Column#10, 1, 0)->Column#11, test.t2.b |
| └─HashJoin_8 | 10000.00 | root | | CARTESIAN left outer semi join, other cond:eq(test.t2.a, test.t1.a) |
| ├─IndexReader_14(Build) | 10000.00 | root | | index:IndexFullScan_13 |
| │ └─IndexFullScan_13 | 10000.00 | cop[tikv] | table:t1, index:idx(a) | keep order:false, stats:pseudo |
| └─TableReader_10(Probe) | 10000.00 | root | | data:TableFullScan_9 |
| └─TableFullScan_9 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
+-------------------------------+----------+-----------+------------------------+---------------------------------------------------------------------+
6 rows in set (0.00 sec)
mysql> explain select case when (exists(select 1 from t1 where t1.a = t2.a)) then 1 else 0 end, t2.b from t2;
+-------------------------------+----------+-----------+------------------------+--------------------------------------------------------+
| id | estRows | task | access object | operator info |
+-------------------------------+----------+-----------+------------------------+--------------------------------------------------------+
| Projection_8 | 10000.00 | root | | case(Column#11, 1, 0)->Column#12, test.t2.b |
| └─HashJoin_19 | 10000.00 | root | | left outer semi join, equal:[eq(test.t2.a, test.t1.a)] |
| ├─IndexReader_31(Build) | 10000.00 | root | | index:IndexFullScan_30 |
| │ └─IndexFullScan_30 | 10000.00 | cop[tikv] | table:t1, index:idx(a) | keep order:false, stats:pseudo |
| └─TableReader_27(Probe) | 10000.00 | root | | data:TableFullScan_26 |
| └─TableFullScan_26 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
+-------------------------------+----------+-----------+------------------------+--------------------------------------------------------+
6 rows in set (0.01 sec)
此问题的引入是因为 TiDB 的 Hash Join 实现，在 2 个 column 列作为 join key 时，不区分二者。所以修复方法目前还是使用 cond Condition 构造 Cartesian 再过滤，详情参考。
DROP TABLE IF EXISTS ss, tt;
create table ss (
a bigint,
b bigint
);
create table tt (
a bigint,
b bigint
);
INSERT INTO ss VALUES (1,NULL),(2,NULL),(2,2);
INSERT INTO tt VALUES (1,1),(1,NULL),(2,NULL);
SELECT tt.a, tt.b, (tt.a, tt.b) in (select a,b from ss) from tt;
// 应该是
mysql> SELECT tt.a, tt.b, (tt.a, tt.b) in (select a,b from ss) from tt;
+------+------+--------------------------------------+
| a | b | (tt.a, tt.b) in (select a,b from ss) |
+------+------+--------------------------------------+
| 1 | 1 | NULL |
| 1 | NULL | NULL |
| 2 | NULL | NULL |
+------+------+--------------------------------------+
3 rows in set (0.00 sec)
// 实际上，直接走 hash join 会出现 0（False），即：结果是二值性的
mysql> SELECT tt.a, tt.b, (tt.a, tt.b) in (select a,b from ss) from tt;
+------+------+--------------------------------------+
| a | b | (tt.a, tt.b) in (select a,b from ss) |
+------+------+--------------------------------------+
| 1 | 1 | 0 |
| 1 | NULL | 0 |
| 2 | NULL | 0 |
+------+------+--------------------------------------+
3 rows in set (0.00 sec)
第三章 现状分析
综上，只有在判断 in 相关表达式下的 Anti Semi Join，Anti Left Outer Semi Join，Left Outer Semi Join 才需要 Null Aware。针对前 2 者，TiDB 已经在 v6.3.0 的 implement the null-aware antiSemiJoin and null-aware antiLeftOuterSemiJoin 中提供了支持。而对于后者，由于 hash join 物理算子实现的特殊性，还处于在构造构造逻辑执行计划时，直接采用笛卡尔积的方法处理，不过可以通过 Exists 方法改写。
针对 TiFlash 侧，TiDB 已经在 Support null-aware semi join push down to tiflash 实现了 Null-Aware 下推 TiFlash，同时 TiFlash 也实现了 null-aware semi join，一旦选择在 TiFlash 上执行 TiDB 将作为接受结果集的进程，便不再需要 hash join, merge join, nested-loop join 等物理执行。系统变量 tidb_enable_null_aware_anti_join 也在 v6.3.0 版本开始引入，默认为 OFF，在 v7.0.0 版本之后，默认为 ON，用于控制下推 TiFlash 时是否在等值条件存在的情况下，使用 Null-Aware Anti Semi Join 替换 CARTESIAN Anti semi join。
第四章 问题分析
在 TiDB 早期，因为 Semi Join should be NULL-Aware · Issue #8844 没有支持 Null-Aware 引发了结果集正确性 BUG，所以当时采用的修复策略是：“标记 column 特殊操作，即：在 join 的 OtherConditions 中加入表达式，使 join 操作感知 Null 的存在，以区分由 in 表达式转换而来的列相等条件和正常的列等值条件，从而检查表达式的操作数是否为 Null，判断半连接的结果。”。
但此修复策略 make semi joins null and empty aware by eurekaka · Pull Request #9051 ，总是会优先生成 CARTESIAN anti semi join，构造笛卡尔积后再筛选需要的数据，导致糟糕执行性能 Support Null-aware Anti Join · Issue #37525 · pingcap/tidb。因此，这种情况也是本文想要研究的内容, CARTESIAN (anti) semi join, other cond:eq(schema_x.table_x.col_x, schema_y.table_y.col_y) 算子的出现。
create table foo(a int, b int, c int);
create table bar (a int not null, b int, c int);
mysql> explain select * from foo where a not in (select b from bar);
+-----------------------------+----------+-----------+---------------+-----------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+-----------------------------+----------+-----------+---------------+-----------------------------------------------------------------+
| HashJoin_8 | 8000.00 | root | | CARTESIAN anti semi join, other cond:eq(test.foo.a, test.bar.b) |
| ├─TableReader_12(Build) | 10000.00 | root | | data:TableFullScan_11 |
| │ └─TableFullScan_11 | 10000.00 | cop[tikv] | table:bar | keep order:false, stats:pseudo |
| └─TableReader_10(Probe) | 10000.00 | root | | data:TableFullScan_9 |
| └─TableFullScan_9 | 10000.00 | cop[tikv] | table:foo | keep order:false, stats:pseudo |
+-----------------------------+----------+-----------+---------------+-----------------------------------------------------------------+
5 rows in set (0.00 sec)
下面是一些因 Null-Aware 导致的笛卡尔积造成生产问题的真实案例。
- 案例-1
该问题因为 case when (a.col) in (select col from schema_x.table_x)中，in 的用法因为不支持 null aware left outer semi join 导致了 cartesian，而转换成 exist 后 cartesian 消失。, 是上面介绍的 2.3 的情况。
- 案例-2
CARTESIAN 效率比较差，由于 pad 非空，理论上可以走 anti semi join，但目前优化器还不支持 https://github.com/pingcap/tidb/issues/37527, 这种情况应该改写为语义等价的 not exists。是上面介绍的 not in 的 anti semi join 情况,建议改写 not exist, 是上面介绍的 2.1 的情况。
3. 案例-3
从执行计划看，扫表和聚合的数据量都不算大，内存占用可能是 CARTESIAN anti semi join 性能问题引起，v6.3 TiDB 已经支持 Null-aware Anti Join https://github.com/pingcap/tidb/issues/37525，可以进行优化，将 CARTESIAN anti semi join 转换为 anti semi join，但是 TiFlash 目前还不支持 https://github.com/pingcap/tiflash/issues/6674。即:前面介绍的从 v6.3 开始 TiFlash 支持非 CARTESIAN 的下推,非要走 TiFLash 的话只有升级能解决。是上面介绍的 2.1 的情况, 加 TiFLash 的混合使用。
第五章 解决方案
-
针对 v6.3.0 之前 Not in 的 Anti Semi Join 及 Not in 的 Anti Left Outer Semi Join 的 Null Aware 不支持问题
- 可以在高版本测试 SQL 语句的是否支持后，推荐客户升级到高版本
- 修改 SQL 处理逻辑不要使用 Not in ，改用 Not Exists 方法绕过
-
针对 In 的 Left Outer Semi Join 的一直 Null Aware 不支持问题
- 可以使用 Exists 方法改写绕过
第六章 结论
综上，基于第二章可知，在使用 exists / not exists / in / not in / != any / = all / < any / < max 的 8 种情况会涉及到 semi join 相关的逻辑算子。