专栏作者介绍
OceanBase 优化器团队，由 OceanBase 高级技术专家溪峰、技术专家山文等领衔，致力于打造全球领先的分布式查询优化器。
系列内容构成
本次查询改写系列不仅包括子查询优化、聚合函数优化、 窗口函数优化、 复杂表达式优化四大模块，还有更多模块内容，敬请期待，欢迎关注** OceanBase 开源用户群** （钉钉号：33254054），与 OceanBase 查询优化器团队一同交流。
引言
在上一篇中，我们讲解了 OceanBase 查询改写实践概述，简要地介绍了改写的方式、改写算法的种类、我们在实现每一个改写算法时主要思考的问题以及多个改写规则是如何组织在一个改写框架下的。本篇文章是《SQL 查询改写》系列第二篇，主要讲解子查询提升。使用子查询可以让用户简洁明了地写出含义清晰的复杂 SQL 语句。这个功能对用户而言非常友好，但是对数据库而言却并不友好。从数据库角度而言，处理子查询相对比较低效。为了改进子查询的处理，数据库系统通常会尝试改写 SQL，消除子查询。
子查询通常有两类用法：
1. 用于一些存在性的判定谓词中，例如 IN, EXISTS, ANY/ALL 比较等，这类场景中子查询的结果是一个集合；
2. 用于计算一个具体的值，例如，出现在 SELECT 中计算一个投影项，这类场景中子查询的结果是一个具体的值。
OceanBase 对这两类子查询都设计了不同的方式进行改写。本文会首先介绍针对第一类子查询的改写策略，即存在性谓词中出现的子查询。
存在性判定谓词在 SQL 语句中很常见。它主要用来判定在一个集合中是否存在/不存在满足条件的记录。以电影表 MOVIES 和排片表 PLAY 为例，下面这个 SQL Q1 使用了一个典型的存在性判定谓词
EXISTS (SELECT …)
。
– 电影表 MOVIES(movie_id, movie_name, rate); – 排片表 PLAY(movie_id, time, price) – Q1: 找出在 19:00 存在排片的电影。 SELECT movie_name FROM MOVIES WHERE EXISTS (SELECT timeFROM PLAY WHERE PLAY.movie_id = MOVIES.movie_id AND PLAY.time = ‘19:00’);
如果维持子查询的计算形式，以上查询对每一部电影，都需要扫描一下排片表，检查是否存在’19:00’的排片场次。这个过程类似于 NEST-LOOP JOIN 的过程，子查询的执行次数等同于
MOVIES
表中读取到的行数。OceanBase 会将以上子查询改写成连接，从而丰富计划选择的空间。
子查询提升
OceanBase 会将上述 Q1 的查询改写成类似于 Q2 的形式。这个变化是等价的。Q2 中半连接的语义是：对
MOVIES
中的每一行，如果能和
PLAY
中任意一行按照
PLAY.movie_id = MOVIES.movie_id AND PLAY.time = ‘19:00’
连接成功，那么就输出该行；否则，不输出。直观地理解，Q1 和 Q2 的语义是相同的。
– Q2: 提升成 SEMI JOIN SELECT movie_name FROM MOVIES SEMI JOIN PLAY ON PLAY.movie_id = MOVIES.movie_id AND PLAY.time = ‘19:00’;
将子查询改写成 SEMI JOIN 后有如下优势：
-
MOVIES
和
PLAY
可以使用更加丰富的连接算法。例如，使用 merge-join 或者 hash-join。在原始子查询中，
PLAY
表会被反复扫描多遍；假如没有合适的索引的话，扫描代价可能会很高。改写之后，使用 merge-join 或者 hash-join 时，
PLAY
只需要被扫描一遍。
-
SEMI JOIN 在特定的情况下，还可以转换成 INNER JOIN。以上查询可以进一步变换成 Q3 的形式。在Q3 中，查询优化器可以选择以 V 为驱动表，MOVIES 为被驱动表的 NEST LOOP JOIN。当
PLAY.time = ‘19:00’
过滤后的行数很少，
MOIVES
行数较多时，这种执行计划的效果会很好。
– Q3: SEMI JOIN 改写成 INNER JOIN SELECT movie_name FROM MOVIES, (SELECT DISTINCT move_id FROM PLAY WHERE PLAY.time = ‘19:00’) V WHERE V.movie_id = MOVIES.movie_id;
EXISTS/ANY 比较谓词可以改写成 SEMI JOIN。这类谓词主要是判断是否存在一条记录满足过滤条件。类似的，业务中也大量使用 NOT EXISTS/ALL 比较谓词，这类谓词用于判断不存在性。OceanBase 会尝试将这类谓词改写成 ANTI JOIN。例如，Q4 使用了一个 NOT IN 谓词（等于 != ALL），它可以被改写成 Q5 的形式。
– Q4: 找出 19:00 没有排片的电影 SELECT movie_name FROM MOVIES M WHERE movie_id NOT IN (SELECT movie_id FROM PLAY P WHERE P.time = ‘19:00’); – Q5: NOT IN 谓词改写成 ANTI JOIN SELECT movie_name FROM MOVIES M ANTI JOIN PLAY P ON (M.movie_id = P.movie_id OR M.movie_id IS NULLOR P.movie_id IS NULL) AND P.time = ‘19:00’
这里 ANTI JOIN 的语义为：对 M 表中的一行，如果能与 P 表中任意一行连接成功，那么就过滤该行；否则，输出该行。
值的注意的是，Q5 中存在一个特殊的 ANTI JOIN 连接谓词：
M.movie_id = P.movie_id OR M.movie_id IS NULL OR P.movie_id IS NULL
。这主要是为了处理 movie_id 取值为 NULL 的情况。考虑以下情景：给定 M 表中的一行
m1
，其中
m1.movie_id
取值为 NULL，并且子查询的结果集非空。在 Q4 中，NOT IN 的判定结果为 unknown，
m1
会被过滤掉。在 Q5 中，OR 连接谓词的判定结果为 true，ANTI JOIN 可以连接成功，
m1
也会被过滤掉。很多时候，我们可能错误地认为，Q4 可以直接改写成下文 Q7 的形式。但实际这两者语义是有区别的。在 Q7 中，由于
m1.movie_id is NULL
，ANTI JOIN 的连接条件判定结果为 unknown，连接不成功，
m1
不会被过滤掉。因此，Q4 和 Q7 是不等价的。类似地，也可以分析
P.movie_id
取值为 NULL 时的查询行为，这里不再赘述。这种语义特点很值得一提， NOT IN 谓词在处理 NULL 值时的特殊性很容易被忽略。下面我们会对此进一步分析。
NOT EXISTS 与 NOT IN 的语义和性能区别。我们在业务支持的过程中，注意到许多业务没有认识到 NOT EXISTS 和 NOT IN 在处理 NULL 值时的语义区别。有一些场景可以使用 NOT EXISTS ，但实际使用了 NOT IN，导致查询性能较慢或者资源开销较高。Q6 使用了 NOT EXISTS 谓词，它的作用和 Q4 很接近。两者一个比较大的区别在于：Q6 的结果集中会保留 M.movie_id 取值为 NULL 的结果；而 Q4 不会。
对比 Q4 和 Q6 的改写结果 Q5 和 Q7，我们可以进一步分析这两个谓词的性能差异。Q5 中，ANTI JOIN 是没有等值连接谓词的，而 Q7 中有一个等值连接谓词。当没有等值连接谓词的时候，查询优化器只能选择 nest loop join 尝试将 M 和 P 中的每一行进行两两连接。当存在等值连接谓词时，查询优化器可以选择 merge join/hash join 或者通过 nest loop join 将等值连接谓词下推成右表上的过滤谓词。相比较而言，存在等值连接谓词时，查询可以选择更丰富的连接算法，从而获得更好的性能。
– Q6: 找出 19:00 没有排片的电影 SELECT movie_name FROM MOVIES M WHERE NOT EXISTS (SELECT movie_id FROM PLAY P WHERE P.time = ‘19:00’ AND M.movie_id = P.movie_id); – Q7: NOT EXISTS 谓词改写 ANTI JOIN SELECT movie_name FROM MOIVES M ANTI JOIN PLAY P ON P.time = ‘19:00’ AND M.movie_id = P.movie_id;
最后，我们可以再额外讨论一下对 Q5 的优化。OceanBase 在优化和执行方面对 Q5 也设计了其他一些策略来提升查询的性能。这里简单介绍两种机制。
- 如果 MOVIES 和 PLAY 表中，在 movie_id 上存在非空约束，那么改写时，我们会去掉 movie_id is null 的判定，直接得到 Q7 的改写结果。
- 当 Q4 最终的改写结果就是 Q5 时，为了避免生成纯粹的 NEST LOOP JOIN，OceanBase 实现了 null-aware hash join 算法。此时，优化器可以选择 null-aware hash join 对 M 和 P 进行连接，避免对 P 表的重复扫描。
总结
本文主要介绍了将存在性判定谓词中的子查询改写成 SEMI/ANTI JOIN 的策略。
这类子查询主要出现在存在性判定谓词 ( EXISTS/NOT EXISTS, ANY/ALL 比较 )中，其典型的特点是，子查询的结果是一个集合。将这类子查询改写成连接可以让查询优化器选择更加丰富的连接算法，也可以和其他改写策略配合，产生更加丰富的连接次序。整体上，这是一个基于规则的改写策略。除了这类子查询外，业务 SQL 中也大量使用子查询计算一个单值。在下一篇文章中，我们将介绍如何改写这种类型的子查询。下周三，我们不见不散。
最后的最后，如果你有任何问题都可以和我们联系。
联系我们
欢迎广大 OceanBase 爱好者、用户和客户随时与我们联系、反馈，方式如下：
