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

网友投稿 473 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。随后，进入到 逻辑优化 及 物理优化 阶段。

二、逻辑优化

下面一些过去已总结的内容, 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 列进行筛选。

三、为什么需要 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) ]

值 [例如：(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 变种构造。

需要 Null Aware 的情况

Not In 使用场景需要 Null Aware，相对于 semi join 来说需要知道哪些情况是没 join 上的结果，也是因为 anti semi join 的三值性，即：需要考虑 NULL 的情况。

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

此问题的引入是因为 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) 算子的出现。

下面是一些因 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

标签：TiDB pingcap 数据库

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

第一章背景介绍

一、TiDB 编译

二、逻辑优化

三、物理优化

第二章理论概括

一、TiDB 的 Semi Join 实现

二、Semi Join 使用场景细分

三、为什么需要 Null Aware

四、SQL 与算子对应关系

不需要 Null Aware 的情况

需要 Null Aware 的情况

第三章现状分析

第四章问题分析

第五章解决方案

第六章结论

第七章文献参考

黄东旭解析 TiDB 的核心优势

麒麟v10 上部署 TiDB v5.1.2 生产环境优化实践

高成本云服务？TiDB 帮你省钱

推荐文章

HTAP 还可以这么玩？丨TiDB 在 IoT 智慧园区的应用

新特性解析丨TiDB 资源管控的设计思路与场景解析

TiDB赋能保险业-首个全栈自主核心保单系统成功投产

首个云原生、分布式、全栈国产化银行核心业务系统投产上线丨TiDB × 杭州银行

TiDB 在社交场景的解决方案实践

电商数据技术栈，在海量数据增长下如何实现实时与全量兼得？

金融行业数据库的选择

TiDB 在智能制造中的应用实践

TiDB 在全球头部物流企业计费管理系统的应用实践

PingCAP与教育部教育管理信息中心合作，推动普惠教育数字化转型

友情链接

热评文章

TiDB 中标杭州银行核心系统数据库项目

TiDB 首批通过信通院 HTAP 数据库基础能力评

PingCAP 与 Wisconsin-Madiso

PingCAP 成为中国唯一入选 Forrester

TiDB 走进东软集团，共建医疗数字化基石

共享开源技术，共建开放生态丨平凯星辰余梦杰出席 20

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

第一章 背景介绍

一、TiDB 编译

二、逻辑优化

三、物理优化

第二章 理论概括

一、TiDB 的 Semi Join 实现

二、Semi Join 使用场景细分

三、为什么需要 Null Aware

四、SQL 与算子对应关系

不需要 Null Aware 的情况

需要 Null Aware 的情况

第三章 现状分析

第四章 问题分析

第五章 解决方案

第六章 结论

第七章 文献参考

推荐文章

友情链接

热评文章

第一章背景介绍

第二章理论概括

第三章现状分析

第四章问题分析

第五章解决方案

第六章结论

第七章文献参考