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

网友投稿 723 2023-12-26

第一章 背景介绍

笛卡尔积在 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 select case when (t2.a in (select t1.a from t1)) then 1 else 0 end, t2.b from t2;

不需要 Null Aware 的情况

针对 Exists 产生的 semi join 或 anti semi join ,无论列属性限制了是否为 NULL, 都不需要 Null Aware, 因为不需要 asScalar 输出,所以无论 Null 和 False 对于 semi join 或 anti semi join 效果等效。

对于 In 的 semi join 本身结果就是二值性的,如例:1.5 所示,所以不需要 Null Aware。不过这里值得一提的是因为 semi join 与 inner join 结果一致,所以直接将其改写为 inner join。具体操作为 unique column 直接构建 inner join,非 unique column 在构建内表时,需要使用 funcs:firstrow 函数去重,因为在做 in 判断时内表在定义上不能有重复值,详情参考

  以下执行计划,均采用下述代码块表及对应的 SQL 变种构造。

CREATE TABLE t2(a int(11) DEFAULT NULL, b int(11) DEFAULT NULL,KEY idx(a)); CREATE TABLE t1(a int(11) DEFAULT NULL, b int(11) DEFAULT NULL, KEY idx (a)); mysql> select version(); +--------------------+ | version() | +--------------------+ | 5.7.25-TiDB-v7.0.0 | +--------------------+ 1 row in set (0.00 sec)  EXISTS 的 Semi joinmysql> 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 Joinmysql> 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 Joinmysql> 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 Joinmysql> 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 joinmysql> 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 Joinmysql> 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 Joinmysql> explain select case when (t2.a not in (select t1.a from t1)) then 1 else 0 end, t2.b from t2; +-------------------------------+----------+-----------+------------------------+------------------------------------------------------------------------+ | id | estRows | task | access object | operator info | +-------------------------------+----------+-----------+------------------------+------------------------------------------------------------------------+ | Projection_7 | 10000.00 | root | | case(Column#10, 1, 0)->Column#11, test.t2.b | | └─HashJoin_8 | 10000.00 | root | | Null-aware anti left outer semi join, equal:[eq(test.t2.a, test.t1.a)] | | ├─IndexReader_14(Build) | 10000.00 | root | | index:IndexFullScan_13 | | │ └─IndexFullScan_13 | 10000.00 | cop[tikv] | table:t1, index:idx(a) | keep order:false, stats:pseudo | | └─TableReader_10(Probe) | 10000.00 | root | | data:TableFullScan_9 | | └─TableFullScan_9 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo | +-------------------------------+----------+-----------+------------------------+------------------------------------------------------------------------+ 6 rows in set (0.00 sec)  In 的 Left Outer Semi Join

  针对 “In 的 Left Outer Semi Join” 情况,目前 TiDB 还无法有效实现对笛卡尔积的消除,建议改写为 exists 方法绕过。

mysql> explain select case when (t2.a in (select t1.a from t1)) then 1 else 0 end, t2.b from t2; +-------------------------------+----------+-----------+------------------------+---------------------------------------------------------------------+ | id | estRows | task | access object | operator info | +-------------------------------+----------+-----------+------------------------+---------------------------------------------------------------------+ | Projection_7 | 10000.00 | root | | case(Column#10, 1, 0)->Column#11, test.t2.b | | └─HashJoin_8 | 10000.00 | root | | CARTESIAN left outer semi join, other cond:eq(test.t2.a, test.t1.a) | | ├─IndexReader_14(Build) | 10000.00 | root | | index:IndexFullScan_13 | | │ └─IndexFullScan_13 | 10000.00 | cop[tikv] | table:t1, index:idx(a) | keep order:false, stats:pseudo | | └─TableReader_10(Probe) | 10000.00 | root | | data:TableFullScan_9 | | └─TableFullScan_9 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo | +-------------------------------+----------+-----------+------------------------+---------------------------------------------------------------------+ 6 rows in set (0.00 sec) mysql> explain select case when (exists(select 1 from t1 where t1.a = t2.a)) then 1 else 0 end, t2.b from t2; +-------------------------------+----------+-----------+------------------------+--------------------------------------------------------+ | id | estRows | task | access object | operator info | +-------------------------------+----------+-----------+------------------------+--------------------------------------------------------+ | Projection_8 | 10000.00 | root | | case(Column#11, 1, 0)->Column#12, test.t2.b | | └─HashJoin_19 | 10000.00 | root | | left outer semi join, equal:[eq(test.t2.a, test.t1.a)] | | ├─IndexReader_31(Build) | 10000.00 | root | | index:IndexFullScan_30 | | │ └─IndexFullScan_30 | 10000.00 | cop[tikv] | table:t1, index:idx(a) | keep order:false, stats:pseudo | | └─TableReader_27(Probe) | 10000.00 | root | | data:TableFullScan_26 | | └─TableFullScan_26 | 10000.00 | cop[tikv] | table:t2 | keep order:false, stats:pseudo | +-------------------------------+----------+-----------+------------------------+--------------------------------------------------------+ 6 rows in set (0.01 sec)

此问题的引入是因为 TiDB 的 Hash Join 实现,在 2 个 column 列作为 join key 时,不区分二者。所以修复方法目前还是使用 cond Condition 构造 Cartesian 再过滤,详情参考

DROP TABLE IF EXISTS ss, tt; create table ss ( a bigint, b bigint ); create table tt ( a bigint, b bigint ); INSERT INTO ss VALUES (1,NULL),(2,NULL),(2,2); INSERT INTO tt VALUES (1,1),(1,NULL),(2,NULL); SELECT tt.a, tt.b, (tt.a, tt.b) in (select a,b from ss) from tt; // 应该是 mysql> SELECT tt.a, tt.b, (tt.a, tt.b) in (select a,b from ss) from tt; +------+------+--------------------------------------+ | a | b | (tt.a, tt.b) in (select a,b from ss) | +------+------+--------------------------------------+ | 1 | 1 | NULL | | 1 | NULL | NULL | | 2 | NULL | NULL | +------+------+--------------------------------------+ 3 rows in set (0.00 sec) // 实际上,直接走 hash join 会出现 0(False),即:结果是二值性的 mysql> SELECT tt.a, tt.b, (tt.a, tt.b) in (select a,b from ss) from tt; +------+------+--------------------------------------+ | a | b | (tt.a, tt.b) in (select a,b from ss) | +------+------+--------------------------------------+ | 1 | 1 | 0 | | 1 | NULL | 0 | | 2 | NULL | 0 | +------+------+--------------------------------------+ 3 rows in set (0.00 sec)

第三章 现状分析

综上,只有在判断 in 相关表达式下的 Anti Semi Join,Anti Left Outer Semi Join,Left Outer Semi Join 才需要 Null Aware。针对前 2 者,TiDB 已经在 v6.3.0 的 implement the null-aware antiSemiJoin and null-aware antiLeftOuterSemiJoin 中提供了支持。而对于后者,由于 hash join 物理算子实现的特殊性,还处于在构造构造逻辑执行计划时,直接采用笛卡尔积的方法处理,不过可以通过 Exists 方法改写。

针对 TiFlash 侧,TiDB 已经在 Support null-aware semi join push down to tiflash 实现了 Null-Aware 下推 TiFlash,同时 TiFlash 也实现了 null-aware semi join,一旦选择在 TiFlash 上执行 TiDB 将作为接受结果集的进程,便不再需要 hash join, merge join, nested-loop join 等物理执行。系统变量 tidb_enable_null_aware_anti_join 也在 v6.3.0 版本开始引入,默认为 OFF,在 v7.0.0 版本之后,默认为 ON,用于控制下推 TiFlash 时是否在等值条件存在的情况下,使用 Null-Aware Anti Semi Join 替换 CARTESIAN Anti semi join。

第四章 问题分析

在 TiDB 早期,因为 Semi Join should be NULL-Aware · Issue #8844 没有支持 Null-Aware 引发了结果集正确性 BUG,所以当时采用的修复策略是:“标记 column 特殊操作,即:在 join 的 OtherConditions 中加入表达式,使 join 操作感知 Null 的存在,以区分由 in 表达式转换而来的列相等条件和正常的列等值条件,从而检查表达式的操作数是否为 Null,判断半连接的结果。”。

但此修复策略 make semi joins null and empty aware by eurekaka · Pull Request #9051 ,总是会优先生成 CARTESIAN anti semi join,构造笛卡尔积后再筛选需要的数据,导致糟糕执行性能 Support Null-aware Anti Join · Issue #37525 · pingcap/tidb因此,这种情况也是本文想要研究的内容, CARTESIAN (anti) semi join, other cond:eq(schema_x.table_x.col_x, schema_y.table_y.col_y) 算子的出现。

create table foo(a int, b int, c int); create table bar (a int not null, b int, c int); mysql> explain select * from foo where a not in (select b from bar); +-----------------------------+----------+-----------+---------------+-----------------------------------------------------------------+ | id | estRows | task | access object | operator info | +-----------------------------+----------+-----------+---------------+-----------------------------------------------------------------+ | HashJoin_8 | 8000.00 | root | | CARTESIAN anti semi join, other cond:eq(test.foo.a, test.bar.b) | | ├─TableReader_12(Build) | 10000.00 | root | | data:TableFullScan_11 | | │ └─TableFullScan_11 | 10000.00 | cop[tikv] | table:bar | keep order:false, stats:pseudo | | └─TableReader_10(Probe) | 10000.00 | root | | data:TableFullScan_9 | | └─TableFullScan_9 | 10000.00 | cop[tikv] | table:foo | keep order:false, stats:pseudo | +-----------------------------+----------+-----------+---------------+-----------------------------------------------------------------+ 5 rows in set (0.00 sec)

下面是一些因 Null-Aware 导致的笛卡尔积造成生产问题的真实案例。

案例-1

该问题因为 case when (a.col) in (select col from schema_x.table_x)中,in 的用法因为不支持 null aware left outer semi join 导致了 cartesian,而转换成 exist 后 cartesian 消失。, 是上面介绍的 2.3 的情况。

案例-2

CARTESIAN 效率比较差,由于 pad 非空,理论上可以走 anti semi join,但目前优化器还不支持 https://github.com/pingcap/tidb/issues/37527, 这种情况应该改写为语义等价的 not exists。是上面介绍的 not in 的 anti semi join 情况,建议改写 not exist, 是上面介绍的 2.1 的情况。

3. 案例-3

从执行计划看,扫表和聚合的数据量都不算大,内存占用可能是 CARTESIAN anti semi join 性能问题引起,v6.3 TiDB 已经支持 Null-aware Anti Join https://github.com/pingcap/tidb/issues/37525,可以进行优化,将 CARTESIAN anti semi join 转换为 anti semi join,但是 TiFlash 目前还不支持 https://github.com/pingcap/tiflash/issues/6674。即:前面介绍的从 v6.3 开始 TiFlash 支持非 CARTESIAN 的下推,非要走 TiFLash 的话只有升级能解决。是上面介绍的 2.1 的情况, 加 TiFLash 的混合使用。

第五章 解决方案

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

可以在高版本测试 SQL 语句的是否支持后,推荐客户升级到高版本

修改 SQL 处理逻辑不要使用 Not in ,改用 Not Exists 方法绕过

针对 In 的 Left Outer Semi Join 的一直 Null Aware 不支持问题

可以使用 Exists 方法改写绕过

第六章 结论

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

第七章 文献参考

Null/Empty Aware Join

Support null-aware semi join

TiDB Source Code

Jans Blog -- Whats Logical Optimizing in TiDB

Jans Blog -- Whats Psysical Optimizing in TiDB

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:TiDB 优化器逻辑优化之 OR 表达式条件消除
下一篇:华锐技术何志东:证券核心交易系统分布式改造将迎来规模化落地阶段
相关文章