摘要：本文整理自蚂蚁金服OB团队高级开发工程师朱涛(山文)在OceanBase TechTalk第四期杭州站的演讲，带读者深入了解OceanBase在查询改写方面的实践与经验。Tips：您可以关注“OceanBase”公众号回复“0512”获取现场PPT和视频回放
引言
多数用户在操作数据库的时候最常用的一般是 SELECT ... FROM ... WHERE 的操作，更复杂一些的语句中，会加入 GROUP-BY，ORDER-BY 和 LIMIT，而类似于窗口函数这样的特性，绝大多数情况下都是不会用到的。
当大家要写一个查询语句的话，肯定是用自己熟悉的语法，写出语义正确的查询。直观、正确的“SQL”，对用户而言可能就是一条 “好 SQL” 了。
事实上，完成同一个查询需求，我们总是可以写出多个不同的 SQL 语句。例如，我曾经遇到过有些应用开发同学会写图(1)左侧的 SQL 来实现“更新 T 表中 type = 10，按 k 排列最小的三行”。
从语义的角度，这条 SQL 其实没有什么问题。但从性能的角度看，这条 SQL 写的并不好。如果不进行任何优化，内核会首先执行子查询，计算出满足条件的 id 集合；然后执行外层主查询，更新相应的行。对内核而言，这其实一条“烂 SQL”。我们可以用图(1)右侧的 SQL 来完成相同的功能。
图(1)：一次查询改写的实例
内核在执行这条改写的查询时，只需要访问 T 表一次，找出满足条件的行并直接更新。业务写出低效 SQL 可能是因为对语法了解的不是很全面；也可能是因为对内核执行的方式了解不多。
如果每个使用数据库的用户都是资深专家，精通 SQL 的编写并对数据库内核处理方式有深刻的理解，那肯定可以写出非常好的SQL。但这并不是这项语言设计的初衷。
SQL的目标是让用户只关心正确地描述自己的需求。如何高效地处理是数据库内核的工作。因此，内核开发实现了“查询改写”模块，它会负责将用户的“好 SQL”等价改写为一条内核的“好 SQL”。本文主要介绍 OceanBase 在查询改写方面的实践与经验。
概要介绍
1. 改写方式
OceanBase 在接收到一条 SQL 后，会首先进行词法/语法解析，将其转换为一个内部的 STMT 结构。查询改写模块的输入是一个 STMT S1 ，经过一系列的改写算法后，将其等价改写为另外一个 STMT S2 。输出的 S2 将用于生成逻辑执行计划和物理执行计划。
查询改写本质上是一个模式匹配的过程。它会依次遍历 STMT 结构中每个对象，检查该对象匹配改写的模式。如果满足，那么将其等价变化为另外一种形式。以图(2)的恒真条件消除为例，查询改写会依次遍历 S1 中的所有条件表达式，并检查它们是否是恒正条件。这里， 1=1 是一个恒真条件，改写算法会移除该条件。
图(2)：查询改写的输入与输出
2. 算法分类
查询改写模块会包含很多的改写算法。不同的改写算法会匹配不同的模式，并进行相应的等价变换。一次完整的查询改写尝试利用所有的改写算法对输入的 STMT 进行优化。
查询改写框架会负责迭代各种改写算法对 STMT 进行优化。整体上，我们希望每次查询改写都可以把 SQL 变得“更好”。但并不是所有的改写算法都会把SQL往"好"的方向进行改写。我们把改写算法分为如下两类:
- 基于规则的改写：主要特点是触发这类改写总能生成更好的执行计划，这类改写算法总是有效的。例如，消除恒真、恒假条件总是有利于生成更好的执行计划。这类算法的整体流程是：1）匹配模式；2）执行改写。OB 内实现诸如：视图合并、子查询提升、内连接消除、外连接消除等改写算法。
- 基于代价的改写：主要特点是某些场景下改写后能生成更好的执行计划，有些场景下不能。是否可以触发这类改写需要根据实际的数据分布、是否有合适的索引等因素来判断。
基于代价的算法在完成改写后需要“询问”物理优化器：“改写后的 STMT 是否能够生成执行代价更小的计划”，如果计划的代价的确降低了，这次改写才会被触发。这类算法的整体流程是：1）匹配模式；2）执行改写；3）代价验证。OB 内实现了诸如：OR Expansion、JA 子查询提升、Win Magic、Group-By Placement 等代价改写算法。
我们用下面这个例子来具体介绍为什么有些改写是基于代价触发。
在 OceanBase 内，Q1 会被 OR Expansion 改写算法改为 Q2。从语义上，这两个查询是等价的。Q1 要查找满足 C1 < 20000 或者 C2 < 30 的记录集合；在 Q2 中， SEL_1 查找满足 C1 < 20000 的记录集合， SEL_2 查找满足 C2 < 30 且不满足 C1 < 20000 的记录集合，两部分取并集即为最终的结果。
值得注意的是， SEL_2 使用 LNNVL(...) 而不是 C1 >= 20000 来查找不满足 C1 < 20000 的记录。考察下面这个例子，给定 r1 (C1, C2) 的取值为 (NULL, 40)，我们预期 SEL_2 可以返回r1。但如果使用 C1 >= 20000 ，r1 同样会被过滤掉。
针对OR Expansion的这个例子，考虑以下两种情景：
- T1 表上在 C1 列和 C2 列上都有索引。Q1 无法利用这两个索引，它只能走主表扫描。Q2 中
SEL_1可以利用C1 上的索引，SEL_2可以利用 C2 上的索引。如果这两个过滤条件有强的过滤性，那么索引扫描可以大大减少读取数据的开销。此时，触发 OR Expansion 改写有利于生成更好的执行计划。 - T1 表上没有任何索引。Q1 和 Q2 都需要进行全表扫描。但是 Q2 被分拆为两个 SELECT 子句，它需要进行两次全表扫描。因此，改写后的执行代价会上升。在这种情况下，不应该触发 OR Expansion。
完备与正确
笔者认为每一类改写算法背后的理念并不复杂。如果一个业务同学了解一些改写规则，是很容易手动改写已有的 SQL，将其等价转换成对数据库内核非常友好的形式。
但是，在内核中要实现这些改写算法是极具挑战性的。在业务层改写 SQL 很简单。因为我们的任务只是改对一条已知的SQL。在内核层改写非常困难。因为我们的任务是给定任意一条SQL，如果可以改写要尽可能的改写，同时改写必须是正确的。这其实对改写算法提出了两点要求：
- 正确：改写后的 SQL 语义不能改变。
- 完备：可以改写的 SQL 要能够改写。
正确性非常容易理解，如果一个改写的结果是错误的，这对业务的价值完全是负面的。完备性同样重要。它要求一个改写算法具有较好的通用性，不能只处理一些简单的场景，而不处理复杂的场景。通用性差对业务的价值是有限的。当然，我们很难把一个改写算法做到完全的完备。
因为总有一些非常复杂的情形是很难处理的，强行改写可能会引入正确性问题。在实现一个改写算法的过程中，我们会在确保正确的前提下，尽可能的做到完备。在下文中，我们会通过“外连接消除”以及“聚合相关子查询提升”来说明“在正确的前提下，实现一个完备的改写”所面临的挑战。
1. 外连接消除
外连接操作可分为左外连接，右外连接和全外连接。连接过程中，外连接左右顺序不能变换，这限制了优化器对连接顺序的选择。考虑 L 与 R 的左外链接（ L LEFT JOIN R ON L.ID = R.ID ）。如果 L 中的一行没有与 R 中的任意一行连接成功，那么连接结果会对 R 的列补空输出（见图(3)）。可以看到左外连接的结果是内连接的超集，它主要增加了R表补空产生的行。
图(3)：内连接和外连接的区别
考虑 L LEFT JOIN R 的结果，假如存在过滤条件 R.C2 = 'XXX' ，那么补空产生的行会被过滤掉，外连接和内连接产生的结果集是完全相同的。此时，我们可以将外连接改写为内连接。这有助于优化器考虑更多的Join顺序和算法。在外连接消除中，我们称 R.C2 = 'XXX' 这样的条件为“空值拒绝条件”。实现外连接消除最大的挑战在于：给定任意一个表达式，我们可以准确地判定出它是否是一个空值拒绝的条件。考虑以下情形：
- R.C2 出现 >, <, ==, IS NOT NULL 等判断表达式的一侧。这类表达式一侧参数为 NULL 时，判断结果必然为 unknown，所以它们是空值拒绝条件。
- F(R.C2) 出现在 >, <, == 等判断表达式的一侧。这类表达式的判定具有更高的难度。因为，我们很难确定当 R.C2 的输入为 NULL 时，F(R.C2) 的输出是什么。例如，F(R.C2) 是 NVL(R.C2, ?) 时，输出结果是 ？。因此，我们很难推断 NVL(R.C2, ?) = 'XXX' 是否构成空值拒绝条件。
显然，实现对第一种情形的改写是比较容易的，难度较大的是对第二种情形的改写。OceanBase 实现了表达式“空值传递”的判定：给定一个嵌套表达式及一个（一组）参数，计算当参数的输入为NULL时，表达式的输出是否为 NULL。因此，OceanBase 可以支持以上两种情形的改写。
以上主要分析了单个列构成的空值拒绝条件。在左外连接的结果中，右表的所有列都会补空。所以，我们还可以进一步判定：多个右表的列构成的过滤表达式是否是空值拒绝条件。例如，下面 SQL 的过滤条件是一个 OR 条件。仅考虑 R.C2 的话， R.C2 IS NOT NULL 对整个SQL而言不是一个空值拒绝条件。但同时考虑 R.C2 和 R.C3 的话，OR 条件是一个空值拒绝条件。
可以看到，外连接消除的想法并不复杂。针对一些简单的场景，(i.e. R.C2 直接出现在判断表达式的一则)，我们是很容易判定这个条件是否是空值拒绝条件；对一些相对复杂的场景，(i.e. R.C2 是嵌套在四则运算(+,-,*,/)中），我们也是比较容易判定的；对一些更加复杂的场景，(i.e. R.C2 嵌套在一些函数表达式中CASE WHEN, NVL 等），判定的难度就大大增加了。对外连接消除而言，抽象空值拒绝性质只是正确实现改写的第一步。为了提升改写的通用性，我们还需要抽象表达式的空值传递性质；同时算法要能够识别多个空值列构成的空值拒绝条件。
2. 聚合相关子查询提升
接下来，我们通过聚合相关子查询提升（下面简称为 JA 子查询提升，Join Aggregation）来说明保证改写正确性所面临的困难。JA 子查询的使用情景通常是：用户使用一个相关的子查询来计算一个统计值，然后利用该统计值来对主查询的结果进行过滤。我们通过下面这个例子来更加直观地说明JA子查询提升的理念。给定一个 PLAY 表记录近期电影的排片信息；一个 TICKETS 表记录这些排片的售票信息，Q3统计了入座率低于一般的场次。
如果不做任何改写的话，执行引擎会迭代 PLAY 中的每一行，将 P.ID 填到子查询中，执行子查询，计算聚合函数 COUNT(*)，最后判断过滤条件是否满足。本质上，这个过程类似于一次 NEST-LOOP Join。子查询的计算次数取决于 PLAY 的行数。在 OceanBase中，JA 子查询改写会把 Q3 转为 Q4：
这种改写的核心理念是：用一个分组查询提前计算了某个排片的入座人数，然后再与PLAY连接，连接后执行过滤条件 P.SEATS > ... 。这个改写中，需要使用 LEFT JOIN 和 CASE WHEN 来处理一个特殊的情形。假如某一次排片放在了深夜、或者放映的是一部烂片，这场排片 p0 没有卖出一张票。考虑 Q4 中的视图 V ，它的结果其实没有包含 p0 的售票量的统计值。
这就导致，p0 在 V 中找不到可以连接的记录。因此，我们用 LEFT JOIN 保留 p0 这一行，并对 V 的列补空。在执行过滤的时候，我们用 CASE WHEN 判定当前行是否是 LEFT JOIN 补空产生的，如果不是，我们在过滤条件中填入分组查询得到的统计值 V.aggr ；如果是，我们在过滤条件中填入0（售票量为0）。
这类 JA 子查询提升的改写是很容易改写错误的。我们可以看一下 Oracle 的改写方式。Oracle 同样是改写成了 LEFT JOIN。过滤条件改造成了一个 OR 条件。OR 的第一个分支处理售票量非 0 的场景，第二个分支处理售票量为 0 的场景。对于 Q3 而言，这个改写是正确的。但是推广到更一般的场景下，这个改写是错误的。
错误的原因在于：它认为满足 V.aggr IS NULL 的行一定是LEFT JOIN对右表补空产生的。这个假设是不一定成立的。因为视图 V 输出的统计结果可能本身就是NULL (e.g. Q5)，这种情况不应该判断 OR 分支的第二个条件。
除此此外，JA 子查询提升还有很多容易被忽视的正确性问题。例如， P.ID = T.ID 也是需要满足一定要求的。当等值条件两侧的类型不一致或者collation不一致的时候也是有可能出现正确性问题的。因为， JA 子查询提升是把 根据 P.ID = T.ID 推导 GROUP BY T.ID ，这种改写成立的背后有一个假设： P.ID = T.ID 的比较类型与 T.ID = T.ID 的比较类型是一致的。
从 JA 子查询的提升可以看到，实现一个正确的改写算法需要仔细考虑每一个改写行为背后是否存在相应的假设。这些假设都需要转换成“模式匹配”过程中的约束。仅当这些假设成立的情况下，我们才可以进行相应的改写。另一方面，为了让我们的改写算法更加趋近于“完备”，我们需要不断改进改写的方式，去弱化这些假设。
总结
本文主要介绍了 OceanBase 的查询改写，简要地介绍了改写的方式，改写算法的种类，以及我们在实现每一个改写算法时主要思考的问题。除此之外，改写算法之间还会存在互相的影响。例如，一次改写后可以触发另外一个改写；一次改写后可能导致另外一个改写无法触发。这些内容被统筹在 OceanBase 的改写框架中。后续，我们将为读者带来更多 OceanBase 在改写框架方面的思考与实践。
