Null-Aware 问题对 TiDB 优化器的影响 (OOM)
作者：TiDB 社区干货传送门
- 2023-12-15 北京
本文字数：16438 字
阅读完需：约 54 分钟
作者： jansu-dev 原文来源：https://tidb.net/blog/29711f07
第一章 背景介绍
笛卡尔积在 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()](https://github.com/pingcap/tidb/blob/eb35c773b512e4e00c42caf7f04ea7397d00c127/executor/compiler.go#L58) 函数是串联 Preprocess(主要用于语法检查，语义检查，schema 检查等) 及 Optimize（构造初始逻辑执行计划，逻辑优化，物理优化） 两阶段的关键函数。在 [OptimizeExecStmt](https://github.com/pingcap/tidb/blob/eb35c773b512e4e00c42caf7f04ea7397d00c127/planner/optimize.go#L440) 会首次基于 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](http://www.dbnest.net/en/tidb/01TiDB-Principle/1-2TiDB%20Optimizer/01Logical%20Optimizing%20in%20TiDB.html), 在 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](http://www.dbnest.net/en/tidb/01TiDB-Principle/1-2TiDB%20Optimizer/02Physical%20Optimizing%20in%20TiDB.html), 下面只列举了 Table reader 做为案例,其他 CBO 数据库优化器大致也是这样实现的,只是具体公式不同.
复制代码
// 物理优化的计算公式 child-cost + rows * row-size * net-factor + num-tasks * seek-factorcost = ------------------------------------------------------------------------- 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](https://github.com/pingcap/tidb/blob/eb35c773b512e4e00c42caf7f04ea7397d00c127/planner/core/logical_plans.go#L70-L77) 中，如下所示。
复制代码
// 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](https://github.com/pingcap/tidb/blob/eb35c773b512e4e00c42caf7f04ea7397d00c127/planner/core/logical_plan_builder.go#L5213) 中（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](https://github.com/pingcap/tidb/blob/eb35c773b512e4e00c42caf7f04ea7397d00c127/planner/core/logical_plan_builder.go#L5264-L5283) 函数，not 表示 not exist 或者 not in，asScalar 表示 [Scalar value means a single value, but not a nil value or vector.](https://github.com/pingcap/tidb/pull/1461/files#r71078078) 即：主要由 not 和 asScalar 控制最终生成什么逻辑算子。
复制代码
所谓的 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
Left Outer Semi Join 的结果需要考虑 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 判断时内表在定义上不能有重复值，[详情参考](https://docs.pingcap.com/zh/tidb/stable/explain-subqueries)。
复制代码
以下执行计划，均采用下述代码块表及对应的 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 再过滤，[详情参考](https://github.com/pingcap/tidb/issues/8844#issuecomment-540308838)。
复制代码
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 ](https://github.com/pingcap/tidb/pull/37512)中提供了支持。而对于后者，由于 hash join 物理算子实现的特殊性，还处于在构造构造逻辑执行计划时，直接采用笛卡尔积的方法处理，不过可以通过 Exists 方法改写。
针对 TiFlash 侧，TiDB 已经在 [Support null-aware semi join push down to tiflash](https://github.com/pingcap/tidb/issues/40745) 实现了 Null-Aware 下推 TiFlash，同时 TiFlash 也实现了[ null-aware semi join](https://github.com/pingcap/tiflash/pull/6594)，一旦选择在 TiFlash 上执行 TiDB 将作为接受结果集的进程，便不再需要 hash join, merge join, nested-loop join 等物理执行。*系统变量* [*tidb\_enable\_null\_aware\_anti\_join*](https://github.com/pingcap/tidb/issues/42271) *也在 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](https://github.com/pingcap/tidb/issues/8844) 没有支持 Null-Aware 引发了结果集正确性 BUG，所以当时采用的修复策略是：“标记 column 特殊操作，即：在 join 的 OtherConditions 中加入表达式，使 join 操作感知 Null 的存在，以区分由 in 表达式转换而来的列相等条件和正常的列等值条件，从而检查表达式的操作数是否为 Null，判断半连接的结果。”。
但此修复策略 [make semi joins null and empty aware by eurekaka · Pull Request #9051](https://github.com/pingcap/tidb/pull/9051) ，总是会优先生成 CARTESIAN anti semi join，构造笛卡尔积后再筛选需要的数据，导致糟糕执行性能 [Support Null-aware Anti Join · Issue #37525 · pingcap/tidb](https://github.com/pingcap/tidb/issues/37525)。**因此，这种情况也是本文想要研究的内容, 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 相关的逻辑算子。
复制代码
第七章 文献参考
划线
评论
复制
发布于: 刚刚阅读数: 4
版权声明: 本文为 InfoQ 作者【TiDB 社区干货传送门】的原创文章。
原文链接:【http://xie.infoq.cn/article/ae0e030e9289c9a0a4d49c4ad】。文章转载请联系作者。
TiDB 社区干货传送门
关注
TiDB 社区官网:https://tidb.net/ 2021-12-15 加入
TiDB 社区干货传送门是由 TiDB 社区中布道师组委会自发组织的 TiDB 社区优质内容对外宣布的栏目，旨在加深 TiDBer 之间的交流和学习。一起构建有爱、互助、共创共建的 TiDB 社区 https://tidb.net/
评论