OceanBase 是100% 自主研发，连续7年稳定支撑双11，创新推出“三地五中心”城市级容灾新标准，是全球唯一在 TPC-C 和 TPC-H 测试上都刷新了世界纪录的国产原生分布式数据库，于 2021 年 6 月份正式 开放源代码。查询优化器是关系数据库系统的核心模块，是数据库内核开发的重点和难点，也是衡量整个数据库系统成熟度的“试金石”。为了帮助大家更好地理解 OceanBase 查询优化器，我们将撰写系列文章，带大家更好地掌握查询改写的精髓，熟悉复杂 SQL 的等价性，写出高效的 SQL。进入【SQL 改写专题】 查看系列内容

1. 引言

本文是 OceanBase 改写系列第一篇：OceanBase 查询改写实践。多数用户在操作数据库的时候最常用的一般是 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 在查询改写方面的实践与经验。

2. 概要介绍

2.1 改写方式

OceanBase 在接收到一条 SQL 后，会首先进行词法/语法解析，将其转换为一个内部的 STMT 结构。查询改写模块的输入是一个 STMT S1 ，经过一系列的改写算法后，将其等价改写为另外一个 STMT S2 。输出的 S2 将用于生成逻辑执行计划和物理执行计划。查询改写本质上是一个模式匹配的过程。它会依次遍历 STMT 结构中每个对象，检查该对象是否匹配改写的模式。如果满足，那么将其等价变化为另外一种形式。以图(2)的恒真条件消除为例，查询改写会依次遍历 S1 中的所有条件表达式，并检查它们是否是恒正条件。这里， 1=1 是一个恒真条件，改写算法会移除该条件。

图 2 查询改写的输入与输出

2.2 算法分类

查询改写模块会包含很多的改写算法。不同的改写算法会匹配不同的模式，并进行相应的等价变换。一次完整的查询改写尝试利用所有的改写算法对输入的 STMT 进行优化。查询改写框架会负责迭代各种改写算法对 STMT 进行优化。整体上，我们希望每次查询改写都可以把 SQL 变得“更好”。但并不是所有的改写算法都会把 SQL 往“好”的方向改造。我们把改写算法分为如下两类：

• 基于规则的改写: 主要特点是触发这类改写总能生成更好的执行计划，这类改写算法总是有效的。例如，消除恒真、恒假条件总是有利于生成更好的执行计划。这类算法的整体流程是：1. 匹配模式；2. 执行改写。OceanBase 内实现诸如：视图合并、子查询提升、内连接消除、外连接消除等改写算法。
• 基于代价的改写: 主要特点是某些场景下改写后能生成更好的执行计划，有些场景下不能。是否可以触发这类改写需要根据实际的数据分布、是否有合适的索引等因素来判断。基于代价的算法在完成改写后需要“询问”物理优化器：“改写后的 STMT 是否能够生成执行代价更小的计划”，如果代价的确降低了，这次改写才会被触发。这类算法的整体流程是：1. 匹配模式；2. 执行改写；3. 代价验证。OceanBase 内实现了诸如：OR Expansion、JA 子查询提升、Win Magic、Group-By Placement 等代价改写算法。

我们用下面这个例子来具体介绍为什么有些改写是基于代价触发。

Q1: 
SELECT * FROM T1 WHERE C1 < 20000 OR C2 < 30 ;
=>
Q2: 
SELECT /*SEL_1*/ * FROM T1 WHERE C1 < 20000 UNION ALL
SELECT /*SEL_2*/ * FROM T1 WHERE C2 < 30 AND LNNVL (C1 < 20000);

在 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 ·的这个例子，考虑以下两种情景：

1. T1 表上在 C1 列和 C2 列上都有索引。Q1 无法利用这两个索引，它只能走主表扫描。Q2 中 SEL_1 可以利用C1 上的索引， SEL_2 可以利用 C2 上的索引。如果这两个过滤条件有强的过滤性，那么索引扫描可以大大减少读取数据的开销。此时，触发 OR Expansion 改写有利于生成更好的执行计划。
2. T1 表上没有任何索引。Q1 和 Q2 都需要进行全表扫描。但是 Q2 被分拆为两个 SELECT 子句，它需要进行两次全表扫描。因此，改写后的执行代价会上升。在这种情况下，不应该触发 OR Expansion。

3. 完备与正确

笔者认为每一类改写算法背后的理念并不复杂。如果一个业务同学了解一些改写规则，是很容易手动改写 SQL 的，将其等价转换成对数据库内核非常友好的形式。但是，在内核中要实现这些改写算法是极具挑战性的。在业务层改写 SQL 很简单。因为我们的任务只是改对一条已知的 SQL。在内核层改写非常困难。因为我们的任务是给定任意一条SQL，如果可以改写要尽可能的改写，同时改写必须是正确的。这其实对改写算法提出了两点要求：

• 正确：改写后的 SQL 语义不能改变。
• 完备：可以改写的 SQL 要能够改写。

正确性非常容易理解，如果一个改写的结果是错误的，这对业务的价值完全是负面的。完备性同样重要。它要求一个改写算法具有较好的通用性，不能只处理一些简单的场景，而不处理复杂的场景。通用性差对业务的价值是有限的。当然，我们很难把一个改写算法做到完全的完备。因为总有一些非常复杂的情形是很难处理的，强行改写可能会引入正确性问题。在实现一个改写算法的过程中，我们会在确保正确的前提下，尽可能的做到完备。在下文中，我们会通过“外连接消除”来说明“在正确的前提下，实现一个完备的改写”所面临的挑战。

外连接操作可分为左外连接，右外连接和全外连接。连接过程中，外连接左右顺序不能变换，这限制了优化器对连接顺序的选择。考虑 L 与 R 的左外链接（ L LEFT JOIN R ON L.ID = R.ID ）。如果 L 中的一行没有与 R 中的任意一行连接成功，那么连接结果会对 R 的列补空输出（见图 3）。可以看到左外连接的结果是内连接的超集，它主要增加了R表补空产生的行。

图 3 内连接和外连接的区别

SELECT L.ID, L.C1, R.C2 FROM L LEFT JOIN R ON L.ID = R.ID WHERE R.C2 = 'XXX';
/*外连接消除*/
SELECT L.ID, L.C1, R.C2 FROM L, R WHERE L.ID = R.ID AND R.C2 = 'XXX';

考虑 L LEFT JOIN R 的结果，假如存在过滤条件 R.C2 = 'XXX' ，那么补空产生的行会被过滤掉，外连接和内连接产生的结果集是完全相同的。此时，我们可以将外连接改写为内连接。这有助于优化器考虑更多的Join顺序和算法。在外连接消除中，我们称 R.C2 = 'XXX' 这样的条件为“空值拒绝条件”。实现外连接消除最大的挑战在于：给定任意一个表达式，我们可以准确地判定出它是否是一个空值拒绝条件。考虑以下情形：

• R.C2 出现 >, <, ==, IS NOT NULL 等判断表达式的一侧。这类表达式一侧参数为 NULL 时，判断结果必然为 unknown/false，所以它们是空值拒绝条件。
• 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 条件是一个空值拒绝条件。

SELECT L.ID, L.C1, R.C2 FROM L LEFT JOIN R ON L.ID = R.ID 
            WHERE R.C2 IS NOT NULL OR R.C3 IS NOT NULL; 

可以看到，外连接消除的想法并不复杂。针对一些简单的场景，(i.e. R.C2 直接出现在判断表达式的一则)，我们是很容易判定这个条件是否是空值拒绝条件；对一些相对复杂的场景，(i.e. R.C2 是嵌套在四则运算(+,-,*,/)中），我们也是比较容易判定的；对一些更加复杂的场景，(i.e. R.C2 嵌套在一些函数表达式中CASE WHEN, NVL 等），判定的难度就大大增加了。对外连接消除而言，抽象空值拒绝性质只是正确实现改写的第一步。为了提升改写的通用性，我们还需要抽象表达式的空值传递性质。进一步地，算法要能够识别多个空值列构成的空值拒绝条件。

在上文中，我们介绍了如何尽可能完备的判断一个谓词是否是空值拒绝谓词。另外一个重要的问题是，是否所有的空值拒绝谓词都可以用于将外连接改写为内连接。相对于上个问题，这个问题重要性是更高的。它构成了外连接消除的正确性边界。如果改写规则的正确性边界归纳的不准确，查询改写会改变业务 SQL 的语义，从而导致查询结果出错。

SELECT L.ID, R.ID, T.ID FROM (L LEFT JOIN R ON L.ID = R.ID) 
                              LEFT JOIN T ON (R.ID = T.ID);

考虑以上查询。L LEFT JOIN R 的结果会再次与 T进行外连接，连接谓词是 R.ID = T.ID。这个谓词中包含了 L LEFT JOIN R右表的列。独立的看，这个谓词的确具有空值拒绝的性质；然而，作为外连接的连接谓词，即便这个谓词的判断结果为非真，它也不会过滤外连接左侧的数据。因此，虽然当 R.ID取值为 NULL 时，R.ID = T.ID判定结果为非真，但这个谓词不能用于将外连接改写为内连接。

4. 改写框架

OceanBase 的查询改写模块实现了大量的改写规则。如第二节描述的，改写规则总体上被分为两大类，基于规则的改写和基于代价的改写。

SQL 经过解析之后，会形成内部结构 （STMT），然后交给查询改写进行等价性变化。改写框架负责按照特定的次序去尝试各个改写算法，当遇到代价改写时，还会额外的触发代价验证。框架会不断的迭代改写策略直到当前 STMT 达到收敛状态，无法再触发任何改写。

在改写框架中，各个改写算法的触发次序是比较重要的。有一些改写需要在另外一些改写之前触发。典型的场景例如，视图合并和谓词移动。视图合并会尝试将多个查询块合并成一个；而谓词移动会在多个查询块直接上拉或者下压谓词。改写框架会优先尝试视图合并，然后再触发谓词移动。这是因为，如果视图合并可以成功，那么就不再需要考虑在多个查询块之间移动谓词。OceanBase 的查询改写模块会仔细考虑各个改写算法之间的关系，然后确定它们的触发次序。

在改写框架中，另外一个比较重要的问题是代价验证。触发一次代价改写有可能会生成更好的执行计划，也有可能不会。改写框架中包含了一个代价验证的模块。在代价验证的过程中，框架会对改写之后结果再迭代一遍规则改写集合。这是因为代价改写之后，可能会出现一些新的改写机会。最后，查询优化器会为改写前和改写后的 STMT 生成执行计划，并判定改写后的结果是否能降低整个执行计划的代价。

5. 总结

本文主要介绍了 OceanBase 的查询改写，简要地介绍了改写的方式、改写算法的种类、我们在实现每一个改写算法时主要思考的问题以及多个改写规则是如何组织在一个改写框架下的。查询改写是查询优化器模块的重点和难点，也是 SQL 性能调优工作者和 DBA 都需要掌握的基础知识。OceanBase 实现了大量的改写规则，本文是对整个改写模块概要性的介绍。在本文的基础上，后续我们也会系统性的推出一系列的查询改写文章，介绍OceanBase 实现的不同的改写规则/算法。我们会陆续介绍 OceanBase 在子查询、分组操作、窗口函数、多种连接类型、表达式等不同关系代数和计算表达式上积累的优化经验。我们相信这一系列的文章会给大家提供参考与借鉴，也欢迎大家一起就查询改写系列问题进行交流、探讨。

最后的最后，有任何问题都可以和我们联系。

联系我们

欢迎广大 OceanBase 爱好者、用户和客户随时与我们联系、反馈，方式如下：

社区版官网论坛

社区版项目网站提 Issue