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

原创
2023/12/11 00:00
阅读数 8

作者: 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-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 这个结构。
  1. handleExistSubquery, handleInSubquery 顾名思义,就是对应 SQL 写法的直接生成。

  2. buildSemiApplyFromEqualSubq 主要处理 a = any(subq)a != all(subq) 情况,这 2 种情况会被改写成 a in (subq)a not in (subq) 的处理方式,再进行后续逻辑算子的生成。

  3. buildQuantifierPlan 主要被 handleOtherComparableSubq,handleNEAny, handleEQAll 这 3 个函数调用。

    1. handleOtherComparableSubq 处理 “< any, < max” 的使用场景,例如: t.id < any (select s.id from s)将被改写成 to t.id < (select max(s.id) from s)。
    2. 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。
    3. 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 不上的情况。

  1. 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) ]
  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. 案例-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 的情况。
    

  1. 案例-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 的混合使用。

第五章 解决方案

  1. 针对 v6.3.0 之前 Not in 的 Anti Semi Join 及 Not in 的 Anti Left Outer Semi Join 的 Null Aware 不支持问题

    1. 可以在高版本测试 SQL 语句的是否支持后,推荐客户升级到高版本
    2. 修改 SQL 处理逻辑不要使用 Not in ,改用 Not Exists 方法绕过
  2. 针对 In 的 Left Outer Semi Join 的一直 Null Aware 不支持问题

    1. 可以使用 Exists 方法改写绕过

第六章 结论

   综上,基于第二章可知,在使用 exists / not exists / in / not in / != any / = all / < any / < max 的 8 种情况会涉及到 semi join 相关的逻辑算子。

第七章 文献参考

  1. Null/Empty Aware Join
  2. Support null-aware semi join
  3. TiDB Source Code
  4. Jan's Blog -- What's Logical Optimizing in TiDB
  5. Jan's Blog -- What's Psysical Optimizing in TiDB
展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部