系列文章导读

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

查询优化器是关系型数据库系统的核心模块，是数据库内核开发的重点和难点，也是衡量整个数据库系统成熟度的“试金石”。为了帮助大家更好地理解 OceanBase 查询优化器，我们将撰写查询改写系列文章，带大家更好地掌握查询改写的精髓，熟悉复杂 SQL 的等价性，写出高效的 SQL。本文是 OceanBase 改写系列第八篇，将重点和大家介绍一下连接消除的技术，欢迎探讨～进入【SQL 改写专题】 查看系列内容

1.引言

在实际应用场景中，你可能经常根据业务需要，写出从多张表中进行查询的语句。那我们接着本系列第八篇的内容，仍然以电影院的为例来讲解这个问题，假设需求方想要“查询电影院中所有有排片的影片的排片信息”，这时你可能会很自然地写出如下语句：

Q1:
SELECT PLAY.* FROM PLAY LEFT JOIN MOVIE ON PLAY.ID = MOVIE.ID; 

Q1需要查询排片信息PLAY和影片信息MOVIE两张表的数据，然后通过左连接返回最终结果。从业务角度来看，上述需求的表述不够精简，我们可以将其提炼为“查询电影院中所有电影的排片信息”，Q1实际等价于：

Q2:
SELECT PLAY.* FROM PLAY; 

从SQL语义的角度来看，由于左外连接必然会返回左侧表的所有行，而主键PLAY.ID、MOVIE.ID均具有非NULL、唯一的属性，连接后的左侧表的结果仍然唯一，因此右侧表MOVIE是冗余的，据此我们同样可以得到Q2的结果。

这种在满足一定条件时，消除连接中的一张或多张表的改写规则，被称为“连接消除”。从连接方式看，除了上述示例中的外连接消除，内连接、半连接（SEMI JOIN）和反连接（ANTI JOIN）也同样可运用连接消除规则；从消除满足的条件来看，则可分为自连接连接、主键/主外键连接消除和恒FALSE连接消除等。

2.连接消除

外连接消除

在引言中，我们给出了一项简单的左外连接消除示例，该示例满足条件:

1. 返回列表仅包含左侧表；
2. 连接方式为外连接；
3. 连接条件在主键ID上（非NULL且唯一）且为等值连接

显然，条件1和条件2是必要的，而条件3则非必要，例如，我们可以通过使用DISTINCT来保证查询结果的唯一性，从而使得消除右表后与消除前的结果集一致，此时则无需条件3的限制：

TABLE T1(C1)
TABLE T2(C1)
--Q3和Q4等价
Q3:
SELECT DISTINCT T1.* FROM T1 LEFT JOIN T2 ON T1.C1 = T2.C1; 
Q4:
SELECT DISTINCT T1.* FROM T1; 

在Q3中，C1列存在NULL值和重复值，和T2通过等值条件T1.C1=T2.C1进行外连接后，返回的结果集大于T1的原表行数，但是在通过DISTINCT去重后，其结果和直接对T1表的返回结果集加DISTINCT是一样的。

细心的读者可能已经观察到，加DISTINCT的重点在于保证连接结果的唯一性，如果T1.C1和T2.C1均为UNIQUE KEY，那么即使不加DISTINCT，也仍然可以做连接消除。

前面分别讨论了以主键、唯一键、以及普通列加DISTINCT做连接消除的场景，其它类型的键是否也可进行连接消除？答案是肯定的，例如，业务上可能会在含主外键关系的两张表上写出类似Q5的语句，根据主外键的性质，TF.C1要么为NULL，要么唯一，和T3做外连接后，不会产生额外的行数，因此可以把T3表消除，从而转换为Q6，这种消除方式被称为主外键连接消除。

TABLE T3(C1 PRIMARY KEY, C2)
TABLE TF(C1, C2, FOREIGN KEY (C1) REFERENCES T3(C1))
Q5:
SELECT TF.* FROM TF LEFT JOIN T3 ON TF.C1 = T3.C1; 
Q6:
SELECT TF.* FROM   TF; 

这里我们先来思考一个问题：上述示例均为等值连接，非等值连接的情况下，是否可以消除？

通常，在非等值连接的情况下，无论连接条件是否为主键，左表中的每一行都有可能匹配右表中的多行，从而在左表上产生重复行，此时不能做连接消除。但是若连接条件为恒FALSE，则左表中的每一行都无法和右表匹配，此时，右侧的每一行都会因为不匹配而补NULL，在这一场景下，我们可以将右侧表消除，考虑查询Q7：

Q7:
SELECT * FROM T1 LEFT JOIN T2 ON 1 = 0; 
Q8:
SELECT T1.C1, NULL FROM T1; 

根据左外连接的定义，右表中与左表不匹配的行需补NULL，由于Q7的连接条件恒FALSE，左表T1的每一行都无法与T2中的行匹配，使得右侧表全部补为NULL，换言之，我们无需关注右侧表的返回值，只需保留右侧表返回列的列名、类型等SCHEMA信息即可，因此右侧表T2可被消除。这种在恒FALSE连接条件下消除右表的方式，被称为恒FALSE连接消除。

内连接消除

顾名思义，内连接消除是指消除内连接中的一张或多张表的改写规则，该消除通常发生在自连接中，自连接消除是指连接的两侧为同一张表的场景，考虑查询Q9：

TABLE T4(C1 UNIQUE KEY, C2)
Q9:
SELECT * FROM T4 tt1,T4 tt2 WHERE tt1.C1 = tt2.C1; 
Q10:
SELECT T4.*,T4.* FROM T4 WHERE T4.C1 IS NOT NULL; 

Q9在同一张表上进行内连接，要求满足在同一列上做等值连接，且该列具有唯一性。根据内连接的性质，在内连接时，不匹配的行会被过滤掉，由于Q9是同一张表以同一列做连接条件进行内连接，因此除NULL值外的每一行都一定匹配，所以实际上只需查询一次表，右侧的结果从左侧补上即可，从而将Q9转换为Q10。

在上一节中，我们讨论了在普通列上加DISTINCT后进行外连接消除的场景，如果把Q9中的连接条件改为TT1.C2 = TT2.C2，然后加上DISTINCT，是否可以进行内连接消除？考察查询Q11:

Q11:
--C2是普通列
SELECT DISTINCT * FROM T4 tt1,T4 tt2 WHERE tt1.C2 = tt2.C2; 

Q11的运算流程如下图所示，由于没有相同行，加DISTINCT后也无法起到去重的作用，最终结果集大于原表行数，因此无法做消除。

当然，如果要求Q11仅返回单侧的结果，或者通过主外键进行内连接，是可以进行消除的，读者可以自行尝试构造下。

半连接/反连接消除

在文章OceanBase 改写系列二: 子查询提升首篇中，我们介绍过半连接（SEMI JOIN）和反连接（ANTI JOIN）的概念，这两种连接方式也可进行连接消除。下面分别给出SEMI /ANTI JOIN消除的示例：

Q12:
SELECT * FROM T1
WHERE  EXISTS(SELECT 1 FROM T2 LEFT JOIN T3 ON T2.C1 = T3.C1); 
Q13:
SELECT * FROM T1 WHERE EXISTS(SELECT 1 FROM T2); 

Q14:
SELECT * FROM T1
WHERE C1 NOT IN (SELECT T2.C1 FROM T2 LEFT JOIN T3 ON T2.C1 = T3.C1); 
Q15:
SELECT * FROM T1 WHERE C1 NOT IN (SELECT T2.C1 FROM T2); 

考虑查询Q12，Q12含一个EXISTS子查询，根据EXISTS子查询的语义，我们只需保证其子查询返回结果不为空即可。注意到Q12的EXISTS子查询中含有一个左外连接，而左外连接必然会返回左表的结果，即EXISTS子查询是否为真，仅取决于T2表的结果集是否为空，因此，其右侧表可全部消除，从而将Q12转换为Q13。ANTI JOIN同理。

Q12和Q14都是利用EXISTS和NOT IN的语义来消除掉子查询中的冗余连接的，我们能否把SEMI JOIN/ANTI JOIN的右侧（即EXISTS/NOT IN语句）消除掉呢？考虑查询Q16:

Q16:
SELECT * FROM T1 WHERE EXISTS(SELECT 1 FROM T1 tt WHERE T1.C1 = tt.C1); 
Q17:
SELECT * FROM T1 WHERE T1.C1 IS NOT NULL; 

Q16中的主查询遍历T1表，然后找到子查询TT表中满足T1.C1 = TT.C1的值，注意到主查询和子查询引用的均为T1表且连接条件为同一列，根据EXISTS子查询的语义，若T1.C1不全为NULL，则经过EXISTS子查询过滤后一定可返回T1.C1不为NULL的行；若T1.C1全为NULL，那么EXISTS子查询一定返回FALSE，此时结果集为空。综上，可将Q16转换为Q17。由于连接条件过滤掉了T1.C1为NULL的值，因此在消除后补上了T1.C1 IS NOT NULL这一条件；若T1.C1具有NOT NULL的限制，则该条件也可去除。

Q16的主查询和子查询中扫描的是同一张表T1，换言之，Q16也可视作自连接消除，这种做法和前一节介绍的内连接消除非常相似。实际上，Q16可通过某些规则转换为内连接，然后采用前一节的内连接消除来消除掉右侧表，我们将在后续文章中介绍这项改写规则，本文不再展开。

3.总结

本文根据连接方式，简要介绍了外连接消除、内连接消除和半连接/反连接消除三类消除场景，并根据连接的条件，引入了主键/主外键消除、自连接消除和恒FALSE连接消除。尽管本文仅介绍了查询语句的消除，但是上述规则也可应用在 DELETE、UPDATE和MERGE INTO 语句中，概括来看，连接消除要着重关注两个要点，一是连接的方式和连接条件，比如是否外连接，是否等值连接等等，例如，恒FALSE连接消除就利用了左外连接时右侧不匹配的行需补NULL的性质；二是表的定义和约束，比如是否含主键、主外键、唯一键等约束。在实际应用中，有些SQL语句并不直接满足本文所介绍的消除规则，但是通过其它改写（如子查询上拉、谓词推导等等），可得到隐含的消除条件，从而扩展连接消除的应用场景。从业务上看，有些被连接的表数据量非常大，导致连接后计算开销也相应增大，如果可通过该改写消除掉这些表，则可大大降低连接的计算开销，从而大幅提升性能。

专栏作者介绍

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

系列内容构成

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

附录：

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

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

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

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

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

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

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