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

引言

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

图1 连接示意图
内连接相比较于外连接另外一个优点在于：内连接是可以随意下压基表谓词条件的，但是外连接是有限制的，比如以影院排片为例，影院使用 Q1 查询所有未排片和排片待定价格的电影进行排片和定价，Q1 中不能把 PLAY.price is null 这个谓词条件提前下压到 PLAY 表进行数据过滤；相反，如果影院使用 Q2 查询所有排片待定价格的电影进行定价，则可以提前把 PLAY.price is null 这个谓词条件下压到 PLAY 表进行数据过滤，这样可以减少连接的数据量，提升查询效率。你可以先理解一下上述场景的区别，下文将展开介绍其背后的原理。
-- 影片表 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 中，根据不同的查询场景，设计和实现了一系列的外连接转内连接的策略。下文将主要介绍这些外连接转内连接的策略。

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

在数据库的外连接中，如果在 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 的基表谓词条件，其实还有更多的场景能够将外连接转内连接，比如下面这两个通用场景。

场景1：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”等。

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

  在介绍利用主外键的约束关系进行外连接转内连接之前，先简单介绍一下主外键约束。如果你了解数据库，那你应该知道，主键是用一组非 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 条件中找到对应外键列的空值拒绝条件，从而可以进行外连接转内连接的改写。本文只是抛砖引玉，你可以深入思考，丰富更多的改写场景及限制。

总结

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