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

系列文章导读

100% 自主研发，连续9年稳定支撑双11，创新推出“三地五中心”城市级容灾新标准的OceanBase，是全球唯一一款在 TPC-C 和 TPC-H 测试中刷新世界纪录的国产原生分布式数据库，于 2021 年 6 月正式开放源代码。

查询优化器是关系型数据库系统的核心模块，是数据库内核开发的重点和难点，也是衡量整个数据库系统成熟度的“试金石”。为了帮助大家更好地理解 OceanBase 查询优化器，我们将撰写查询改写系列文章，带大家更好地掌握查询改写的精髓，熟悉复杂 SQL 的等价性，写出高效的 SQL。本文是 OceanBase 改写系列第九篇，将重点和大家介绍外连接转内连接的常见场景与错误，欢迎探讨～

引言

众所周知，内连接和外连接是数据库中最常见的两种表连接；其中外连接包括左外连接、右外连接及全外连接。如图1，展示了数据库中不同的表连接的示意图（其中深色部分代表最终的连接之后的结果），从图中我们不难发现，内连接的连接顺序是可以随意交换的，但是外连接是不能的，连接顺序的随意交换可以让数据库的查询优化器生成更多可选择的计划。

图1 连接示意图

-- 影片表
MOVIE(movie_id， movie_name, release_date)
-- 排片表
PLAY(play_id, movie_id, time, price, seats)


-- 查询所有未排片和排片待定价格的电影
Q1: 
SELECT MOVIE.movie_name,
       PLAY.time,
       PLAY.price
FROM   MOVIE
       LEFT JOIN PLAY
              ON MOVIE.movie_id = PLAY.movie_id
       where PLAY.price is null; 


-- 查询所有排片待定价格的电影
Q2: 
SELECT MOVIE.movie_name,
       PLAY.time,
       PLAY.price
FROM   MOVIE
       INNER JOIN PLAY
              ON MOVIE.movie_id = PLAY.movie_id
       where PLAY.price is null; 

综上所述，内连接相较于外连接在数据库查询优化器中有着更大的优化空间（更多的连接顺序选择，更广的基表谓词条件下压）。因此，在 OceanBase 中，根据不同的查询场景，设计和实现了一系列的外连接转内连接的策略。下文将主要介绍这些外连接转内连接的策略。

1. 外连接转内连接的通用场景

在数据库的外连接中，如果在 probe 表（外连接的右表）中找不到满足连接条件的数据，则需要在相应的连接结果中针对 probe 表的投影列进行补 null 输出，如图2，左外连接示意图展示了一个简单外连接的情形。考虑到外连接这个行为，不难看出，如果在连接之后，存在针对 probe 表的基表谓词条件可以过滤掉连接结果中的 null 情形的，那么这个时候外连接的结果就和内连接的结果是一样的，就可以将外连接改写为内连接。

图2 左外连接示意图

针对上述查询中的 probe 表存在可以过滤 null 的基表谓词条件，最先想到的是否存在 column is not null 条件，从而能够快速判断当前的外连接是否可以改写为内连接，图3 描述了基于 column is not null 基表谓词条件进行不同的外连接转内连接的场景：

图3 外连接转内连接示意图

上述场景描述了外连接转内连接的一个基本策略，即能够在 probe 表的相关基表谓词条件中找到能够过滤 null 的，其中 column is not null 是一种最简单直观的过滤 null 的基表谓词条件，其实还有更多的场景能够将外连接转内连接，比如下面这两个通用场景。

场景一：WHERE 条件的外连接转内连接

在介绍基于 WHERE 条件的外连接转内连接之前，我们先引入一个重要的概念——空值拒绝条件，顾名思义就是拒绝一切 null 的谓词条件，也就是上文所描述的在相关基表谓词条件中找到能够过滤 null 的条件。因此，基于 WHERE 条件的外连接转内连接的关键是能否找到 probe 表的空值拒绝条件。

从上文可以知道，column is not null 其实是最简单直观的一种空值拒绝条件；除此之外，还有很多空值拒绝条件，比如， Q3 是用于查询排片价格高于30元的电影，其中的 PLAY.price > 30 本质上就是一个空值拒绝条件，因为当 PLAY.price 的值为null时，从SQL语义上来讲 null > 30 的比较结果是空，也即查询结果中不会有 PLAY.price 为 null 的行，从而能够过滤掉所有因不满足连接条件而对 probe 表的投影列补 null 的行，因此， Q3 等价于 Q4，也就是说如果将用户输入的查询 Q3 改写为 Q4，那么后续优化器的计划生成选择等会有更大的优化空间。

Q3: 
SELECT MOVIE.movie_name,
       PLAY.time,
       PLAY.price
FROM   MOVIE
       LEFT JOIN PLAY
              ON MOVIE.movie_id = PLAY.movie_id
       where play.price > 30; 
       
Q4: 
SELECT MOVIE.movie_name,
       PLAY.time,
       PLAY.price
FROM   MOVIE
       INNER JOIN play
              ON MOVIE.movie_id = PLAY.movie_id
       where PLAY.price > 30; 

当然并不是所有的基表过滤条件都是空值拒绝的，如Q1和Q2在语义上是不等价的。因为 column is null 不是一个空值拒绝条件。所以在做基于 WHERE 条件的外连接转内连接改写时，需要特别注意空值拒绝条件的覆盖场景，避免陷入改写陷阱。

• 直接和 null 比较相关的一些条件，比如 column is not null ；
• 普通的比较运算表达式，比如‘=’、‘!=’、‘>’、‘<’、‘in’、‘not in’等；
• 匹配相关的表达式，比如 ‘regexp’、‘like’等；

由于文章篇幅有限，本文不再一一列举，读者可以结合实际，发挥想象，思考更多的空值拒绝条件场景。

场景二：主外键的外连接转内连接

除了利用 WHERE 条件进行外连接转内连接，还可以利用主外键的约束关系进行外连接转内连接；在介绍利用主外键的约束关系进行外连接转内连接之前，先简单介绍一下主外键约束。如果你了解数据库，那你应该知道，主键是用一组非 null 的唯一值来区分表中的每一行，而外键用于建立两个表之间的联系，从表（外键所在表）的部分列依赖与主表的部分列，外键列只能引用主表中的列的值或 null 值，从而达到约束两个表中数据的一致性和完整性的目的。

那么外连接如何利用这主外键约束来转换为内连接呢？先看一个例子，如下创建了 MOVIE 和 PLAY 两张表，其中 PLAY.movie_id（非 null 列）外键依赖于 MOVIE.movie_id（主键列）。Q5 和 Q6 的差别是：从表在外连接的位置不同，从表在 Q5 中是外连接的右表（probe 表），而在 Q6 中是外连接的左表 （build 表）；你可以先自行思考一下，Q5 和 Q6 能否都可以将外连接改写为内连接？

-- 影片表
MOVIE(movie_id， movie_name, release_date, PRIMARY KEY(movie_id))
-- 排片表
PLAY(play_id, movie_id not null, time, price, seats,
     foreign key(movie_id) REFERENCES MOVIE(movie_id))


Q5:
SELECT MOVIE.movie_name,
       PLAY.time,
       PLAY.price
FROM   MOVIE
       LEFT JOIN PLAY
              ON MOVIE.movie_id = PLAY.movie_id; 
                          
Q6:
SELECT MOVIE.movie_name,
       PLAY.time,
       PLAY.price
FROM   PLAY
       LEFT JOIN MOVIE
              ON MOVIE.movie_id = PLAY.movie_id;

OK，先公布答案：Q5 不允许，Q6 允许！

首先分析 Q6 为什么可以，由于外连接的等值连接条件都来自于主外键列，同时从表 PLAY.movie_id 是一个非 null 列，说明从表 PLAY.movie_id 的值都来自于主表 MOVIE.movie_id，因此当从表 PLAY 作为外连接的左表、等值连接条件都来自于主外键列时，说明针对从表 PLAY.movie_id 总能在主表找到对应的列，不会出现补 null 的场景，这就是Q6允许改写的原因。相反如果当主表 MOVIE 做为外连接的左表时，并不能保证一定可以在从表找到对应主表行的数据，是存在出现 补 null 的场景的，因此 Q5 是不允许改写的。

一个改写陷阱

现在我们清楚了基于主外键的外连接转内连接改写的原理，其实基于主外键的改写限制是非常苛刻的，一不小心就会掉入改写的陷阱中，比如下面的 Q7 相较于 Q6 多了一个主外键列的非等值连接条件，但 Q7 是不允许改写的。相信聪明的你已经看出其中的原因了，主要是因为新增的 MOVIE.movie_id > 100 谓词条件会破坏连接过程中的主外键约束关系，当满足等值连接条件但是不满足范围谓词条件时，仍然会补 null 输出，因此不能进行外连接转内连接的改写。这就提醒我们在基于主外键的外连接转内连接改写时，要特别注意主外键约束关系是否被打破。

Q7:
SELECT MOVIE.movie_name,
       PLAY.time,
       PLAY.price
FROM   PLAY
       LEFT JOIN MOVIE
              ON MOVIE.movie_id = PLAY.movie_id
                 AND MOVIE.movie_id > 100;
--不可发生改写

小结

此外，因为基于主外键的外连接转内连接条件苛刻，所以，在这里简单总结一下利用主外键约束进行外连接转内连接的一些基本条件：

• 连接条件仅仅只有主外键列的等值连接；
• 等值连接条件中使用到列是和主外键列是一一对应的；
• 连接条件中的外键列有非 null 性质；
• 从表（外键所在表）为外连接的左表。

除了上述基本条件外，其实针对一些特殊场景也会有一些限制，比如，限定了主表的分区（使用partition hint），由于存在补 null 输出的可能，不能改写。当然，也可以将上述基本条件进行推广，比如，针对“连接条件中的外键列有非空性质”这一条件，如果表中没有定义非空列，是不是也可以在 WHERE 条件中找到对应外键列的空值拒绝条件，从而可以进行外连接转内连接的改写。本文只是抛砖引玉，你可以深入思考，丰富更多的改写场景及限制。

总结

本文主要介绍了一些外连接转内连接的策略，外连接转内连接对于数据库查询优化器而言是不可或缺的。内连接允许更多的连接顺序选择、基表谓词条件下压，有助于查询优化器选择到更好的查询执行计划，提升查询效率。因此，外连接转内连接是一项非常重要的优化技术。

专栏作者介绍

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

系列内容构成

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

附录：

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

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

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

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

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

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

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

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