Null-Aware 问题对 TiDB 优化器的影响(OOM)

标签：NULL join semi OOM t2 t1 TiDB Aware 10000.00

作者： jansu-dev

第一章背景介绍

笛卡尔积在 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 转换成逻辑算子，构造初始执行计划。

Null-Aware 问题对 TiDB 优化器的影响(OOM)_github

比如：`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-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](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\|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 判断时内表在定义上不能有重复值，[详情参考](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 的情况。

Null-Aware 问题对 TiDB 优化器的影响(OOM)_github_02

案例-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 相关的逻辑算子。

第七章文献参考

Null/Empty Aware Join
Support null-aware semi join
TiDB Source Code
Jan's Blog -- What's Logical Optimizing in TiDB
Jan's Blog -- What's Psysical Optimizing in TiDB

标签：NULL,join,semi,OOM,t2,t1,TiDB,Aware,10000.00
From： https://blog.51cto.com/tidb/8873038

Null-Aware 问题对 TiDB 优化器的影响(OOM)

第一章背景介绍

一、TiDB 编译

二、逻辑优化

三、物理优化

第二章理论概括

一、TiDB 的 Semi Join 实现

二、Semi Join 使用场景细分

三、为什么需要 Null Aware

四、SQL 与算子对应关系

不需要 Null Aware 的情况

EXISTS 的 Semi join

Not Exists 的 Anti Semi Join

Exists 的 Left Outer Semi Join

Not exists 的 Anti Left Outer Semi Join

In 的 Semi join 改写 Inner join

需要 Null Aware 的情况

Not in 的 Anti Semi Join

Not in 的 Anti Left Outer Semi Join

In 的 Left Outer Semi Join

第三章现状分析

第四章问题分析

第五章解决方案

第六章结论

第七章文献参考

相关文章

赞助商

阅读排行

Null-Aware 问题对 TiDB 优化器的影响(OOM)

第一章 背景介绍

一、TiDB 编译

二、逻辑优化

三、物理优化

第二章 理论概括

一、TiDB 的 Semi Join 实现

二、Semi Join 使用场景细分

三、为什么需要 Null Aware

四、SQL 与算子对应关系

不需要 Null Aware 的情况

EXISTS 的 Semi join

Not Exists 的 Anti Semi Join

Exists 的 Left Outer Semi Join

Not exists 的 Anti Left Outer Semi Join

In 的 Semi join 改写 Inner join

需要 Null Aware 的情况

Not in 的 Anti Semi Join

Not in 的 Anti Left Outer Semi Join

In 的 Left Outer Semi Join

第三章 现状分析

第四章 问题分析

第五章 解决方案

第六章 结论

第七章 文献参考

相关文章

赞助商

阅读排行

第一章背景介绍

第二章理论概括

第三章现状分析

第四章问题分析

第五章解决方案

第六章结论

第七章文献参考