第一章 背景介绍

笛卡尔积在 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 | +----------------------------+----------+-----------+---------------+----------------------------------+

二、逻辑优化

下面一些过去已总结的内容, Whats 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 的执行计划作为最终执行计划。Whats 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 这种类型，只有官方定义的 InnerJoin, LeftOuterJoin, RightOuterJoin, FullOuterJoin 和CrossJoin 共 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 selec