SQL改写系列十一：外连接转AntiJoin的场景与限制

在《SQL 改写系列九：外连接转内连接的常见场景与错误》中，我们知道当谓词可以过滤掉连接结果中因为连接而补null的行时，可以把外连接转换为内连接，如图1中路径(a)所示。这时聪明的你肯定会问：谓词能筛选出因为连接而补null的行时，我们又能做什么优化呢？答案是：对于左外连接（LeftJoin）或右外连接（RightJoin），OceanBase会把外连接转位AntiJoin，如图1中路径(b)所示。进入【SQL 改写专题】 查看系列内容

在LeftJoin和RIghtJoin场景，驱动表（在这个例子中是t1）需要扫描被驱动表(t2)的所有行，找出所有匹配的行。 但转换成AntiJoin之后，由于AntiJoin的目的是输出没有在被驱动表中找到匹配行的驱动表中的行，因此在AntiJoin场景，只要在被驱动表中找到一行满足连接条件的数据，我们就可以认为驱动表中的行不满足输出条件，就可以停止这轮扫描。综上，我们可以知道LeftJoin/RightJoin转换成AntiJoin之后可以减少扫描被驱动表的行数。

外连接转AntiJoin

对于左外连接和右外连接，当针对基表的过滤谓词可以筛选出因为连接而补null的行时，我们可以把外连接转化为AntiJoin。图2以最简单的过滤谓词 column is null为例描述了不同外连转AntiJoin的场景。

然而在实际查询中，谓词不会一直像 t2.c1 is null 这么简单。在一个 SQL 语句中，is null 谓词的左边可以是复杂表达式{如(t2.c1 + t2.c2) is null}，于是，我们进一步推广支持外连接转AntiJoin的谓词形态，让这个改写在复杂谓词条件下也能发生，并且结合前文提到的谓词推导和谓词移动，使更多的查询能从外连接转AntiJoin中获益。在了解复杂条件的改写之前，我们需要先了解OceanBase中空值传递的概念。

对于复杂表达式 A = b+c+d，它是由表达式 b,c,d构成的。假设当b为null的时候，表达式A也会null，那我们则认为表达式A对于表达式b是空值传递的。 在这个例子中，表达式A对于b, c, d都是空值传递的。常见的空值传递判断条件有：

1. 表达式对自身是空值传递的
2. 基本的算数表达式对其子表达式都是空值传递的
3. 一些系统函数(SQRT，LOG_TEN，LOG_TWO，FLOOR，CEIL，LEAST，GREATEST，LEAST_INNER，GREATEST_INNER，MIN，MAX，SUM等）
4. 非AND/OR/IS/IS NOT的布尔表达式

在了解空值传递这个概念后，我们可以知道：只要is null谓词左边的表达式对于被驱动表中的列是空值传递的（如 (t2.c1+t2.c2) 对于t2.c1是空值传递的)，那在t2.c1是null的时候is null谓词左边的表达式也是null，is null谓词结果为true，如此便可以把被驱动表补null的行筛选出来。

综上所述，我们知道即便是对于 (t2.c1+t2.c2) is null这样的复杂谓词，只要满足对被驱动表中的列空值传递的条件，在特定条件也可以做外连接转AntiJoin的改写。至于这个特定条件是什么，我们接着往下看。

改写限制条件

条件1：对于补null侧的基表，谓词中的列不能存在null值。

-- 影片表
MOVIE(movie_id， movie_name)
movie_id	movie_name
1					'Gone With Wind'
2					'Leon'
-- 排片表
PLAY(play_id, movie_id, time, price)
play_id	movie_id	time					price
1				1					'2022-10-01'	35
2				1					NULL					40

Q1: 
SELECT 	MOVIE.movie_name,
       	PLAY.time
FROM	 	MOVIE
      	LEFT JOIN PLAY
               ON	MOVIE.movie_id = PLAY.movie_id;
WHERE		PLAY.time is null;

-- 外连接结果
R1:
movie_name				price
'Gone With Wind'	40
'Leon'						NULL

-- AntiJoin结果
R2:
movie_name				time
'Leon'						NULL

条件2：对于非补null侧的基表， 谓词中的列不应该对谓词是空值传递的。

-- 影片表
MOVIE(movie_id， movie_name)
movie_id	movie_name
1					'Gone With Wind'
2					NULL
-- 排片表
PLAY(play_id, movie_id, time, price)
play_id	movie_id	time					price
1				1					'2022-10-01'	35
2				2					'2022-10-02'	40

Q2: 
SELECT 	MOVIE.movie_name,
       	PLAY.time
FROM	 	MOVIE
      	LEFT JOIN PLAY
               ON	MOVIE.movie_id = PLAY.movie_id;
WHERE		(PLAY.time AND MOVIE.movie_name) is null;

-- 外连接结果
R3:
movie_name				price
NULL							40

-- AntiJoin结果
R4:
movie_name				time	

总结

看到这里，相信你已经了解了LeftJoin和RightJoin改写为AntiJoin的优点及适用场景，相较于LeftJoin和RightJoin需要扫描被驱动表的所有行，AntiJoin在找到第一行匹配的数据后就会停止扫描被驱动表，可以减少实际扫描数据的数量，因而在执行的时候有更好的性能。我们认为，谓词能筛选出被驱动表补null的行时，就能进行半连接转Anti的改写，但是依旧需要注意数据原本就可能为null的情况。此外，借助空值传递的概念，我们把能做改写的场景从简单谓词场景推广到了复杂谓词场景。

专栏作者介绍

OceanBase 优化器团队，由 OceanBase 高级技术专家溪峰、技术专家山文等领衔，致力于打造全球领先的分布式查询优化器。

系列内容构成

本次查询改写系列不仅包括子查询优化、聚合函数优化、 窗口函数优化、 复杂表达式优化四大模块，另外还有更多模块内容，敬请期待！本文根据连接方式，向大家介绍外连接消除、内连接消除和半连接/反连接消除三类消除场景，并根据连接的条件，引入了主键/主外键消除、自连接消除和恒 FALSE 连接消除。欢迎关注 OceanBase 开源用户群 （钉钉号：33254054），进群与 OceanBase 查询优化器团队一同交流。

附录：

1、OceanBase 改写系列一：OceanBase 查询改写实践概述

2、OceanBase 改写系列二: 子查询提升首篇

3、OceanBase 改写系列三：如何提升子查询性能（包含聚合函数）的最佳实践

4、OceanBase 改写系列四: 聚合分组等价变换大法之分组下压

5、OceanBase 改写系列五：视图合并设计与实践

6、OceanBase 改写系列六：谓词推导

7、OceanBase 改写系列七：谓词移动

8、OceanBase 改写系列八：连接消除

9、OceanBase 改写系列九：外连接转内连接的常见场景与错误

10、OceanBase 改写系列十：半连接转内连接