PostgreSQL的学习心得和知识总结（一百七十一）|深入理解PostgreSQL数据库之 外连接消除 的使用和实现
目录结构
注：提前言明 本文借鉴了以下博主、书籍或网站的内容，其列表如下：
1、参考书籍：《PostgreSQL数据库内核分析》
2、参考书籍：《数据库事务处理的艺术：事务管理与并发控制》
3、PostgreSQL数据库仓库链接，点击前往
4、日本著名PostgreSQL数据库专家 铃木启修 网站主页，点击前往
5、参考书籍：《PostgreSQL中文手册》
6、参考书籍：《PostgreSQL指南：内幕探索》，点击前往
1、本文内容全部来源于开源社区 GitHub和以上博主的贡献，本文也免费开源（可能会存在问题，评论区等待大佬们的指正）
2、本文目的：开源共享 抛砖引玉 一起学习
3、本文不提供任何资源 不存在任何交易 与任何组织和机构无关
4、大家可以根据需要自行 复制粘贴以及作为其他个人用途，但是不允许转载 不允许商用 （写作不易，还请见谅 💖）
5、本文内容基于PostgreSQL master源码开发而成
深入理解PostgreSQL数据库之 外连接消除 的使用和实现
- 文章快速说明索引
- 功能使用背景说明
- 外连接->内连接
- 严格与不严格
- 外连接->反半连接
- 全外连接的转换
- 功能实现源码解析
- 第一阶段
- 第二阶段
- 左(右)外连接->内连接
- 左(右)外连接->反半连接
- 全外连接->内连接
- 全外连接->左外连接
文章快速说明索引
学习目标：
做数据库内核开发久了就会有一种 少年得志，年少轻狂 的错觉，然鹅细细一品觉得自己其实不算特别优秀 远远没有达到自己想要的。也许光鲜的表面掩盖了空洞的内在，每每想到于此，皆有夜半临渊如履薄冰之感。为了睡上几个踏实觉，即日起 暂缓其他基于PostgreSQL数据库的兼容功能开发，近段时间 将着重于学习分享Postgres的基础知识和实践内幕。
学习内容：（详见目录）
1、外连接消除 的使用和实现
学习时间：
2025年03月09日 13:06:57
学习产出：
1、PostgreSQL数据库基础知识回顾 1个
2、CSDN 技术博客 1篇
3、PostgreSQL数据库内核深入学习
注：下面我们所有的学习环境是Centos8+PostgreSQL master+Oracle19C+MySQL8.0
postgres=# select version();
version
---------------------------------------------------------------------------------
PostgreSQL 18devel on x86_64-pc-linux-gnu, compiled by gcc (GCC) 13.1.0, 64-bit
(1 row)
postgres=#
#-----------------------------------------------------------------------------#
SQL> select * from v$version;
BANNER Oracle Database 19c EE Extreme Perf Release 19.0.0.0.0 - Production
BANNER_FULL Oracle Database 19c EE Extreme Perf Release 19.0.0.0.0 - Production Version 19.17.0.0.0
BANNER_LEGACY Oracle Database 19c EE Extreme Perf Release 19.0.0.0.0 - Production
CON_ID 0
#-----------------------------------------------------------------------------#
mysql> select version();
+-----------+
| version() |
+-----------+
| 8.0.27 |
+-----------+
1 row in set (0.06 sec)
mysql>
功能使用背景说明
背景描述：
《张树杰 查询优化深度探索 3.8外连接消除》在查询优化的过程中，很多时间都是在和外连接、(反)半连接做斗争。例如：
- 对约束条件 进行下推(谓词下推)时，如果连接操作是外连接，那么有些约束条件下推会受到阻碍
- 如连接顺序交换，内连接的表之间的连接顺序交换比较灵活，而外连接不能随意地交换连接表的顺序
因此， 如果能将外连接转换成内连接，查询优化的过程就会大大地简化。
postgres=# \! date
2025年 03月 12日 星期三 20:31:24 PDT
postgres=#
postgres=# select version();
version
---------------------------------------------------------------------------------
PostgreSQL 18devel on x86_64-pc-linux-gnu, compiled by gcc (GCC) 13.1.0, 64-bit
(1 row)
postgres=#
外连接->内连接
两个表的结构和数据，如下：
postgres=# \d
List of relations
Schema | Name | Type | Owner
--------+---------+-------+----------
public | score | table | postgres
public | student | table | postgres
(2 rows)
postgres=# \d+ score
Table "public.score"
Column | Type | Collation | Nullable | Default | Storage | Compression | Stats target | Description
--------+---------+-----------+----------+---------+---------+-------------+--------------+-------------
sno | integer | | | | plain | | |
cno | integer | | | | plain | | |
degree | integer | | | | plain | | |
Access method: heap
postgres=# \d+ student
Table "public.student"
Column | Type | Collation | Nullable | Default | Storage | Compression | Stats target | Description
--------+-----------------------+-----------+----------+---------+----------+-------------+--------------+-------------
sno | integer | | | | plain | | |
sname | character varying(10) | | | | extended | | |
ssex | integer | | | | plain | | |
Access method: heap
postgres=# table student ;
sno | sname | ssex
-----+-------+------
1 | zs | 1
2 | ls | 1
(2 rows)
postgres=# table score ;
sno | cno | degree
-----+-----+--------
1 | 1 | 36
(1 row)
postgres=#
首先看一下内外连接的区别：如果要查询学生的姓名和成绩，可以对 STUDENT 和 SCORE 做连接，从查询结果可以看出，内连接只显示了有成绩的学生，而外连接则对没有成绩的学生补了NULL值，也就是说这个外连接是不能转换成内连接的。
postgres=# SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
1 | zs | 1 | 1 | 1 | 36
2 | ls | 1 | | |
(2 rows)
postgres=# SELECT * FROM STUDENT INNER JOIN SCORE ON STUDENT.sno = SCORE.sno;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
1 | zs | 1 | 1 | 1 | 36
(1 row)
postgres=#
如果我们再增加一个WHERE条件，形成下面这样的语句，内连接的查询结果就和外连接的查询结果相同了。如下：
postgres=# SELECT * FROM STUDENT INNER JOIN SCORE ON STUDENT.sno = SCORE.sno;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
1 | zs | 1 | 1 | 1 | 36
(1 row)
postgres=# SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE cno IS NOT NULL;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
1 | zs | 1 | 1 | 1 | 36
(1 row)
postgres=# SELECT * FROM STUDENT INNER JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE cno IS NOT NULL;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
1 | zs | 1 | 1 | 1 | 36
(1 row)
postgres=#
WHERE cno IS NOT NULL这样的条件可以让外连接和内连接的结果相同，因为这个约束条件是“严格(strict)”的。
严格(strict)的精确定义是对于一个函数、操作符或者表达式，如果输入参数是NULL 值，那么输出也一定是NULL值，就可以说这个函数、操作符或者表达式是严格的；但是，宽泛地说，对于函数、操作符或者表达式，如果输入参数是NULL值，输出结果是NULL值或者 FALSE， 那么就认为这个函数或者操作符是严格的。
如果在约束条件里有这种严格的操作符、函数或者表达式，由于输入是NULL值，输出是NULL值或者 FALSE，那么对于含有 NULL 值的元组就会被过滤掉。
WHERE cno IS NOT NULL这样的约束条件，如果输入的 cno 是NULL值，这个约束条件返回的是FALSE， 也满足了宽泛的“严格”定义，而且cno又处于左连接的Nullable-side，对于补充的NULL值又能起到过滤的作用，因此增加它可以导致内连接和外连接的查询结果相同。
综上，就可以得出外连接能够被消除的条件，如下：
- 上层有严格的约束条件。
- 约束条件中引用了Nuliable-side 的表。
需要注意的是，消除条件里的上层两个字，所谓的上层是指这个约束条件：不是当前的连接条件，而是上层的连接条件或者过滤条件。目前我们可以粗略地认为连接条件是 ON关键字后面的约束条件，而过滤条件是WHERE关键字后面的约束条件。
postgres=# create table course(cno int, cname varchar(10), tno int);
CREATE TABLE
postgres=# insert into course values(1, 'English', 2), (2, 'Math', 5), (3, 'Data', 3), (4, 'Design', 5), (5, 'Phys', 6);
INSERT 0 5
postgres=# SELECT * FROM STUDENT LEFT JOIN (SCORE LEFT JOIN COURSE ON TRUE) ON COURSE.cno IS NOT NULL;
sno | sname | ssex | sno | cno | degree | cno | cname | tno
-----+-------+------+-----+-----+--------+-----+---------+-----
1 | zs | 1 | 1 | 1 | 36 | 1 | English | 2
1 | zs | 1 | 1 | 1 | 36 | 2 | Math | 5
1 | zs | 1 | 1 | 1 | 36 | 3 | Data | 3
1 | zs | 1 | 1 | 1 | 36 | 4 | Design | 5
1 | zs | 1 | 1 | 1 | 36 | 5 | Phys | 6
2 | ls | 1 | 1 | 1 | 36 | 1 | English | 2
2 | ls | 1 | 1 | 1 | 36 | 2 | Math | 5
2 | ls | 1 | 1 | 1 | 36 | 3 | Data | 3
2 | ls | 1 | 1 | 1 | 36 | 4 | Design | 5
2 | ls | 1 | 1 | 1 | 36 | 5 | Phys | 6
(10 rows)
postgres=#
如上，其中约束条件(或者连接条件〉ON COURSE.cno IS NOT NULL处在(SCORE LEFT JOIN COURSE ON TRUE)的上层，它能对(SCORE LEFT JOIN COURSE ON TRUE)这个外连接的消除起作用，但是不能对 STUDENT LEFT JOIN (SCORE LEFT JOIN COURSE ON TRUE)的消除起到作用，它们的层次关系如下图所示：
其执行计划，如下：
postgres=# explain SELECT * FROM STUDENT LEFT JOIN (SCORE LEFT JOIN COURSE ON TRUE) ON COURSE.cno IS NOT NULL;
QUERY PLAN
-------------------------------------------------------------------------
Nested Loop Left Join (cost=0.00..3.27 rows=10 width=37)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
-> Materialize (cost=0.00..2.13 rows=5 width=26)
-> Nested Loop (cost=0.00..2.11 rows=5 width=26)
-> Seq Scan on score (cost=0.00..1.01 rows=1 width=12)
-> Seq Scan on course (cost=0.00..1.05 rows=5 width=14)
Filter: (cno IS NOT NULL)
(7 rows)
postgres=#
从上面的执行计划可以看出(SCORE LEFT JOIN COURSE ON TRUE)的左连接己经被消除了，但是STUDENT LEFT JOIN (SCORE LEFT JOIN COURSE ON TRUE)的左连接仍然存在。
postgres=# SELECT * FROM STUDENT LEFT JOIN (SCORE LEFT JOIN COURSE ON TRUE) ON TRUE WHERE COURSE.cno IS NOT NULL;
sno | sname | ssex | sno | cno | degree | cno | cname | tno
-----+-------+------+-----+-----+--------+-----+---------+-----
1 | zs | 1 | 1 | 1 | 36 | 1 | English | 2
1 | zs | 1 | 1 | 1 | 36 | 2 | Math | 5
1 | zs | 1 | 1 | 1 | 36 | 3 | Data | 3
1 | zs | 1 | 1 | 1 | 36 | 4 | Design | 5
1 | zs | 1 | 1 | 1 | 36 | 5 | Phys | 6
2 | ls | 1 | 1 | 1 | 36 | 1 | English | 2
2 | ls | 1 | 1 | 1 | 36 | 2 | Math | 5
2 | ls | 1 | 1 | 1 | 36 | 3 | Data | 3
2 | ls | 1 | 1 | 1 | 36 | 4 | Design | 5
2 | ls | 1 | 1 | 1 | 36 | 5 | Phys | 6
(10 rows)
如上例子的结构图如下图所示，可以看到约束条件（或者过滤条件）WHERE COURSE.cno IS NOT NULL可以作用于顶层的连接，查看它的查询计划可以看出，语句中的左连接都被消除了。
postgres=# analyze ;
ANALYZE
postgres=# explain SELECT * FROM STUDENT LEFT JOIN (SCORE LEFT JOIN COURSE ON TRUE) ON TRUE WHERE COURSE.cno IS NOT NULL;
QUERY PLAN
--------------------------------------------------------------------------
Nested Loop (cost=0.00..3.23 rows=10 width=37)
-> Seq Scan on course (cost=0.00..1.05 rows=5 width=14)
Filter: (cno IS NOT NULL)
-> Materialize (cost=0.00..2.06 rows=2 width=23)
-> Nested Loop (cost=0.00..2.05 rows=2 width=23)
-> Seq Scan on score (cost=0.00..1.01 rows=1 width=12)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
(7 rows)
postgres=#
如上，不仅仅是所有的外连接做了消除，在后续的优化中(因为这已经是内连接了)其连接顺序也发生了交换！
严格与不严格
可以通过如下方法来判断一个函数、操作符或者表达式是否严格：
-
对于函数而言， 在PG_PROC系统表中的 proisstrict 列属性代表了当前函数是否严格。
-
如果是操作符表达式， 在 PostgreSQL 数据库中操作符实际都转成了对应的函数，因此也可以用 proisstrict 来表示是否严格。
-
对基于IS [NOT] NULL 产生的 NullTest表达式需要单独处理，其中 IS NOT NULL 是严格的， IS NULL 是不严格的。
/* strict with respect to NULLs? */
bool proisstrict BKI_DEFAULT(t);
如果给定一个表达式，那么可以对表达式进行递归遍历， 如果满足上面的3 种情况，那么这个表达式也是严格的。
外连接->反半连接
而 IS NULL 这样不严格的表达式对我们也是有用的，例如，对于左连接而言， Nonnullable-side 没有连接上的元组会在 Nullable-side 补 NULL 值显示出来，而所谓的没有连接上的元组，恰好是Anti Join所需要的，因此就带来了将左连接(LeftJoin)转换成反连接 (AntiJoin) 的可能性， 这种可能性的前提是：
- 当前层次的连接条件必须是严格的。
- 上层的约束条件和当前层的连接条件都引用了Nullable-side表的同一列。
- 上层的约束条件强制Nullable-side 产生的结果必须是NULL。
来看一个这样的示例：
postgres=# SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
1 | zs | 1 | 1 | 1 | 36
2 | ls | 1 | | |
(2 rows)
postgres=# SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE SCORE.sno IS NULL;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
2 | ls | 1 | | |
(1 row)
postgres=# explain SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE SCORE.sno IS NULL;
QUERY PLAN
------------------------------------------------------------------
Nested Loop Anti Join (cost=0.00..2.06 rows=1 width=23)
Join Filter: (student.sno = score.sno)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
-> Materialize (cost=0.00..1.01 rows=1 width=12)
-> Seq Scan on score (cost=0.00..1.01 rows=1 width=12)
(5 rows)
postgres=#
它的当前层有连接条件 STUDENT.sno = SCORE.sno，通过查 PG_PROC 系统表以及 PG_OPERATOR 系统表可以知道＝操作符是严格的，它的上层的约束条件SCORE.sno IS NULL也引用了 SCORE.sno，而且强制结果为 NULL，而且 SCORE表处在左连接的RHS， 因此它符合转成AntiJoin 的条件。
从这个示例中可以看出， LeftJoin 被转换成了 AntiJoin，这是因为：连接条件 STUDENT.sno = SCORE.sno 是严格的，这保证了在Nullable-side 的表中如果本身就含有NULL 值，这些元组会被连接条件筛选掉。另外，约束条件SCORE.sno IS NULL 是上层的不严格的约束条件，这就保证了在外连接操作之后，约束条件SCORE.sno IS NULL 会把Nullable-side 补的 NULL值的元组保留下来了，这样的操作结果和 Anti Join 的结果应该是一致的。也就是说通过连接条件 STUDENT.sno = SCORE.sno 筛选掉了表中本来就有的 NULL 值， 通过 SCORE.sno IS NULL 保留了外连接补的NULL值。
全外连接的转换
这个下面展开
功能实现源码解析
// src/backend/optimizer/plan/planner.c
PlannerInfo *
subquery_planner(PlannerGlobal *glob, Query *parse, PlannerInfo *parent_root,
bool hasRecursion, double tuple_fraction,
SetOperationStmt *setops)
{
...
/*
* If we have any outer joins, try to reduce them to plain inner joins.
* This step is most easily done after we've done expression
* preprocessing.
* 如果我们有任何外连接，请尝试将其简化为普通内连接。
* 完成表达式预处理后，这一步最容易完成。
*/
if (hasOuterJoins)
reduce_outer_joins(root);
...
}
接下来先看一下该函数的内容，如下：
// src/backend/optimizer/prep/prepjointree.c
/*
* reduce_outer_joins
* Attempt to reduce outer joins to plain inner joins.
* 尝试将外连接减为普通的内连接。
*
* The idea here is that given a query like
* SELECT ... FROM a LEFT JOIN b ON (...) WHERE b.y = 42;
* we can reduce the LEFT JOIN to a plain JOIN if the "=" operator in WHERE
* is strict. The strict operator will always return NULL, causing the outer
* WHERE to fail, on any row where the LEFT JOIN filled in NULLs for b's
* columns. Therefore, there's no need for the join to produce null-extended
* rows in the first place --- which makes it a plain join not an outer join.
* (This scenario may not be very likely in a query written out by hand, but
* it's reasonably likely when pushing quals down into complex views.)
* 如果 WHERE 中的“=”运算符是严格的，我们可以将 LEFT JOIN 简化为普通 JOIN。
* 在 LEFT JOIN 为 b 的列填充 NULL 的任何行上，严格运算符将始终返回 NULL，从而导致外部 WHERE 失败。
* 因此，连接首先不需要生成空扩展行 --- 这使得它成为普通连接而不是外部连接。
* （这种情况在手写查询中可能不太可能发生，但在将限定词推入复杂视图时很可能发生。）
*
* More generally, an outer join can be reduced in strength if there is a
* strict qual above it in the qual tree that constrains a Var from the
* nullable side of the join to be non-null. (For FULL joins this applies
* to each side separately.)
* 更一般地，如果在限定树中，外连接的上方存在严格限定条件，该限定条件将连接的可空侧的变量限制为非空，则外连接的强度会降低。
* （对于FULL JOIN，这分别适用于每一侧。）
*
* ----------------------------------------------------------------------------------------------------
*
* Another transformation we apply here is to recognize cases like
* SELECT ... FROM a LEFT JOIN b ON (a.x = b.y) WHERE b.y IS NULL;
* If the join clause is strict for b.y, then only null-extended rows could
* pass the upper WHERE, and we can conclude that what the query is really
* specifying is an anti-semijoin. We change the join type from JOIN_LEFT
* to JOIN_ANTI. The IS NULL clause then becomes redundant, and must be
* removed to prevent bogus selectivity calculations, but we leave it to
* distribute_qual_to_rels to get rid of such clauses.
* 如果连接子句对于 b.y 是严格的，那么只有空扩展行才能通过上层 WHERE，我们可以得出结论：查询真正指定的是反半连接。
* 我们将连接类型从 JOIN_LEFT 更改为 JOIN_ANTI。
* 然后 IS NULL 子句变得多余，必须将其删除以防止虚假的选择性计算，但我们将其留给 distributor_qual_to_rels 来摆脱此类子句。
*
* ----------------------------------------------------------------------------------------------------
*
* Also, we get rid of JOIN_RIGHT cases by flipping them around to become
* JOIN_LEFT. This saves some code here and in some later planner routines;
* the main benefit is to reduce the number of jointypes that can appear in
* SpecialJoinInfo nodes. Note that we can still generate Paths and Plans
* that use JOIN_RIGHT (or JOIN_RIGHT_ANTI) by switching the inputs again.
* 此外，我们通过翻转 JOIN_RIGHT 情况将其变为 JOIN_LEFT 来摆脱它们。
* 这可以节省此处和一些后续规划器例程中的一些代码；主要好处是减少 SpecialJoinInfo 节点中可能出现的连接类型的数量。
* 请注意，我们仍然可以通过再次切换输入来生成使用 JOIN_RIGHT（或 JOIN_RIGHT_ANTI）的路径和计划。
*
* To ease recognition of strict qual clauses, we require this routine to be
* run after expression preprocessing (i.e., qual canonicalization and JOIN
* alias-var expansion).
* 为了便于识别严格的限定子句，我们要求在表达式预处理（即限定规范化和 JOIN 别名变量扩展）之后运行此例程。
*/
void
reduce_outer_joins(PlannerInfo *root)
{
reduce_outer_joins_pass1_state *state1;
reduce_outer_joins_pass2_state state2;
ListCell *lc;
/*
* To avoid doing strictness checks on more quals than necessary, we want
* to stop descending the jointree as soon as there are no outer joins
* below our current point. This consideration forces a two-pass process.
* The first pass gathers information about which base rels appear below
* each side of each join clause, and about whether there are outer
* join(s) below each side of each join clause. The second pass examines
* qual clauses and changes join types as it descends the tree.
*
* 为了避免对过多的限定条件进行严格性检查，我们希望在当前点下方没有外连接时立即停止下传连接树。
* 这种考虑迫使我们进行两次传递过程。
* 第一次传递收集有关每个连接子句下方出现哪些基本关系的信息，以及有关每个连接子句下方是否有外连接的信息。
* 第二次传递检查限定子句并在下降树时更改连接类型。
*/
state1 = reduce_outer_joins_pass1((Node *) root->parse->jointree);
/* planner.c shouldn't have called me if no outer joins */
if (state1 == NULL || !state1->contains_outer)
elog(ERROR, "so where are the outer joins?");
state2.inner_reduced = NULL;
state2.partial_reduced = NIL;
reduce_outer_joins_pass2((Node *) root->parse->jointree,
state1, &state2,
root, NULL, NIL);
/*
* If we successfully reduced the strength of any outer joins, we must
* remove references to those joins as nulling rels. This is handled as
* an additional pass, for simplicity and because we can handle all
* fully-reduced joins in a single pass over the parse tree.
*
* 如果我们成功降低了任何外连接的强度，我们必须删除对这些连接作为无效rels的引用。
* 为了简单起见，这被处理为一个额外的过程，因为我们可以在解析树的一次传递中处理所有完全简化的连接。
*/
if (!bms_is_empty(state2.inner_reduced))
{
root->parse = (Query *)
remove_nulling_relids((Node *) root->parse,
state2.inner_reduced,
NULL);
/* There could be references in the append_rel_list, too */
root->append_rel_list = (List *)
remove_nulling_relids((Node *) root->append_rel_list,
state2.inner_reduced,
NULL);
}
/*
* Partially-reduced full joins have to be done one at a time, since
* they'll each need a different setting of except_relids.
* 部分缩减全连接必须一次完成一个，因为它们每个都需要不同的 except_relids 设置。
*/
foreach(lc, state2.partial_reduced)
{
reduce_outer_joins_partial_state *statep = lfirst(lc);
Relids full_join_relids = bms_make_singleton(statep->full_join_rti);
root->parse = (Query *)
remove_nulling_relids((Node *) root->parse,
full_join_relids,
statep->unreduced_side);
root->append_rel_list = (List *)
remove_nulling_relids((Node *) root->append_rel_list,
full_join_relids,
statep->unreduced_side);
}
}
我对该函数画了一个概要图，以供大家参考(欢迎指正)：
注：关于期间使用的位图集等比较简单，这里不再赘述！
第一阶段
如上reduce_outer_joins函数分成了两个步骤：第一个步骤是先做一个预检，查看一下查询树中是否存在外连接， 外连接的层次结构是什么样的，这个层次结构通过reduce_outer_joins_pass1_state结构体来记录。如下：
// src/backend/optimizer/prep/prepjointree.c
typedef struct reduce_outer_joins_pass1_state
{
Relids relids; /* base relids within this subtree */ // 当前层次及下层引用了哪些表
bool contains_outer; /* does subtree contain outer join(s)? */ // 下层是否有外连接
List *sub_states; /* List of states for subtree components */ // 下层的state树状结构
} reduce_outer_joins_pass1_state;
以上代码比较复杂，接下来我们开始调试！
案例一(SQL1)：
postgres=# SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE cno IS NOT NULL;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
1 | zs | 1 | 1 | 1 | 36
(1 row)
postgres=# explain SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE cno IS NOT NULL;
QUERY PLAN
--------------------------------------------------------------
Nested Loop (cost=0.00..2.06 rows=1 width=23)
Join Filter: (student.sno = score.sno)
-> Seq Scan on score (cost=0.00..1.01 rows=1 width=12)
Filter: (cno IS NOT NULL)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
(5 rows)
postgres=#
函数堆栈，如下：
reduce_outer_joins(PlannerInfo * root)
subquery_planner(PlannerGlobal * glob, Query * parse, PlannerInfo * parent_root, _Bool hasRecursion, double tuple_fraction, SetOperationStmt * setops)
standard_planner(Query * parse, const char * query_string, int cursorOptions, ParamListInfo boundParams)
planner(Query * parse, const char * query_string, int cursorOptions, ParamListInfo boundParams)
...
在reduce_outer_joins_pass1函数处理开始前，root->parse->jointree的结构如下：
预检操作在reduce_outer_joins_pass1函数中完成，它递归上面的jointree：对其中的RangeTblRef、 FromExpr、 JoinExpr进行递归处理。
- 对于RangeTblRef直接记录它的 rtindex 返回给上层。
- 对于FromExpr，默认当前层次是内连接，递归遍历FromExpr->fromlist，对下层的连接进行预检，查看下层是否包含外连接。
- 对于JoinExpr，如果是外连接，先设置 contains_outer 变量为 true，然后递归遍历 JoinExpr->larg 和 JoinExpr->rarg，查看下层是否包含外连接。
在经过reduce_outer_joins_pass1函数处理后，返回的reduce_outer_joins_pass1_state树状图如下图所示：
或者看如下调试内容，如下：
书中提供的另一个例子，我们也分析一下(SQL2)：
postgres=# explain select * from (STUDENT INNER JOIN SCORE on true) LEFT JOIN (COURSE LEFT JOIN TEACHER on course.tno = teacher.tno) on true ;
QUERY PLAN
--------------------------------------------------------------------------------
Nested Loop Left Join (cost=1.04..4.32 rows=10 width=49)
-> Nested Loop (cost=0.00..2.05 rows=2 width=23)
-> Seq Scan on score (cost=0.00..1.01 rows=1 width=12)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
-> Materialize (cost=1.04..2.16 rows=5 width=26)
-> Hash Left Join (cost=1.04..2.13 rows=5 width=26)
Hash Cond: (course.tno = teacher.tno)
-> Seq Scan on course (cost=0.00..1.05 rows=5 width=14)
-> Hash (cost=1.02..1.02 rows=2 width=12)
-> Seq Scan on teacher (cost=0.00..1.02 rows=2 width=12)
(10 rows)
postgres=# explain select * from (STUDENT INNER JOIN SCORE on true) LEFT JOIN (COURSE LEFT JOIN TEACHER on course.tno = teacher.tno) on true where teacher.tno IS NOT NULL;
QUERY PLAN
--------------------------------------------------------------------------------
Nested Loop (cost=1.04..4.24 rows=5 width=49)
-> Nested Loop (cost=1.04..3.16 rows=2 width=38)
-> Seq Scan on score (cost=0.00..1.01 rows=1 width=12)
-> Hash Join (cost=1.04..2.13 rows=2 width=26)
Hash Cond: (course.tno = teacher.tno)
-> Seq Scan on course (cost=0.00..1.05 rows=5 width=14)
-> Hash (cost=1.02..1.02 rows=2 width=12)
-> Seq Scan on teacher (cost=0.00..1.02 rows=2 width=12)
Filter: (tno IS NOT NULL)
-> Materialize (cost=0.00..1.03 rows=2 width=11)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
(11 rows)
postgres=#
如上SQL，过滤的where条件teacher.tno IS NOT NULL将两个外连接都给消除掉了。下面直接看一下其jointree和reduce_outer_joins_pass1_state树状图：(大家在看这种图的时候可以结合相关数据结构，具体含义不在展开。就像下面jointype、rtindex等)
调试的结果一样，如下：
通过上面的这些结构图可以看出，contains_outer的值为 false 的子树可以被剪掉，这样就能简化reduce_outer_joins_pass2函数的处理流程。
第二阶段
左(右)外连接->内连接
接下来进入阶段二， reduce_outer_joins_pass2函数开始对外连接消除：
typedef struct reduce_outer_joins_pass2_state
{
Relids inner_reduced; /* OJ relids reduced to plain inner joins */ // 简化为普通内连接的OJ(outer join) relids
List *partial_reduced; /* List of partially reduced FULL joins */ // 部分裁剪的 FULL JOIN 列表
} reduce_outer_joins_pass2_state;
// src/backend/optimizer/prep/prepjointree.c
/*
* reduce_outer_joins_pass2 - phase 2 processing 第 2 阶段处理
*
* jtnode: current jointree node
* state1: state data collected by phase 1 for this node
* state2: where to accumulate info about successfully-reduced joins
* root: toplevel planner state
* nonnullable_rels: set of base relids forced non-null by upper quals
* forced_null_vars: multibitmapset of Vars forced null by upper quals
*
* jtnode：当前连接树节点
* state1：第 1 阶段为此节点收集的状态数据
* state2：用于存放收集到的有关成功简化连接的信息
* root：顶层规划器状态
* nonnullable_rels：由上级限定词强制为非空的基本 relid 集
* forced_null_vars：由上级限定词强制为空的 Vars 多位图集
*
* Returns info in state2 about outer joins that were successfully simplified.
* Joins that were fully reduced to inner joins are all added to
* state2->inner_reduced. If a full join is reduced to a left join,
* it needs its own entry in state2->partial_reduced, since that will
* require custom processing to remove only the correct nullingrel markers.
*
* 返回 state2 中有关已成功简化的外连接的信息。
* 完全简化为内连接的连接全部添加到 state2->inner_reduced。
*
* 如果将一个full join简化为一个左连接，则它需要在 state2->partial_reduced 中有自己的条目，
* 因为这将需要自定义处理才能仅删除正确的 nullingrel 标记。
*/
static void
reduce_outer_joins_pass2(Node *jtnode,
reduce_outer_joins_pass1_state *state1,
reduce_outer_joins_pass2_state *state2,
PlannerInfo *root,
Relids nonnullable_rels,
List *forced_null_vars);
它有 3 个比较重要的参数，这 3 个参数的说明如下表所示：
注：参数nonnullable_vars其实在后续的版本中已不再作为参数进行传递，有兴趣的可以看一下相关的提交。
// Tom Lane 2年前 (11 5th, 2022 0:58 中午)
Don't pass down nonnullable_vars while reducing outer joins.
We weren't actually using the passed-down list for anything, other
than computing the new value to be passed down further. I (tgl)
probably had the idea that we'd need this data eventually; but
no use-case has emerged in a good long while, so let's just stop
expending useless cycles here.
Richard Guo
张树杰书对应版本为10.0，我们这里学习继续按照书中的逻辑向下。不同之处 我后续会做相关标识：
| 参数名 | 参数类型 | 描述 |
|---|---|---|
| nonnullable_rels | [IN] Relids | 收集严格约束条件所涉及的表的rtindex，收集工作由find_nonnullable_rels函数实现，函数的参数是FromExpr->quals或者JoinExpr->quals |
| forced_null_vars | [IN] List* | 收集不严格约束条件中的Var，收集工作由find_forced_null_vars函数实现，函数的参数是FromExpr->quals或者JoinExpr->quals |
| nonnullable_vars (没有了) | [IN] List* | 收集严格约束条件中的Var，收集工作由find_nonnullable_vars函数实现，函数的参数是FromExpr->quals或者JoinExpr->quals |
在开始调试之前，先行看一下上面这三个信息收集函数：
// src/backend/optimizer/util/clauses.c
/*
* find_nonnullable_rels
* Determine which base rels are forced nonnullable by given clause.
确定哪些基本关系被给定子句强制为非空。
*
* Returns the set of all Relids that are referenced in the clause in such
* a way that the clause cannot possibly return TRUE if any of these Relids
* is an all-NULL row. (It is OK to err on the side of conservatism; hence
* the analysis here is simplistic.)
* 返回子句中引用的所有 Relid 的集合，这样，如果这些 Relid 中的任何一个是全 NULL 行，子句就不可能返回 TRUE。
*（保守一点是可以的；因此这里的分析比较简单。）
*
* The semantics here are subtly different from contain_nonstrict_functions:
* that function is concerned with NULL results from arbitrary expressions,
* but here we assume that the input is a Boolean expression, and wish to
* see if NULL inputs will provably cause a FALSE-or-NULL result. We expect
* the expression to have been AND/OR flattened and converted to implicit-AND
* format.
* 此处的语义与 contain_nonstrict_functions 略有不同：
* 该函数关注任意表达式的 NULL 结果，但此处我们假设输入是布尔表达式，并希望查看 NULL 输入是否可证明会导致 FALSE 或 NULL 结果。
* 我们期望表达式已被 AND/OR 平铺并转换为隐式 AND 格式。
*
* Note: this function is largely duplicative of find_nonnullable_vars().
* The reason not to simplify this function into a thin wrapper around
* find_nonnullable_vars() is that the tested conditions really are different:
* a clause like "t1.v1 IS NOT NULL OR t1.v2 IS NOT NULL" does not prove
* that either v1 or v2 can't be NULL, but it does prove that the t1 row
* as a whole can't be all-NULL. Also, the behavior for PHVs is different.
* 注意：此函数与 find_nonnullable_vars() 大体相同。
* 不将此函数简化为 find_nonnullable_vars() 的薄包装器的原因在于测试条件确实不同：
* 像“t1.v1 IS NOT NULL OR t1.v2 IS NOT NULL”这样的子句不能证明 v1 或 v2 不能为 NULL，但它可以证明 t1 行作为一个整体不能全部为 NULL。
* 此外，PHV 的行为也不同。
*
* top_level is true while scanning top-level AND/OR structure; here, showing
* the result is either FALSE or NULL is good enough. top_level is false when
* we have descended below a NOT or a strict function: now we must be able to
* prove that the subexpression goes to NULL.
* 扫描顶层 AND/OR 结构时 top_level 为真；此时，显示结果为 FALSE 或 NULL 就足够了。
* 当我们下降到 NOT 或严格函数以下时，top_level 为假：现在我们必须能够证明子表达式变为 NULL。
*
* We don't use expression_tree_walker here because we don't want to descend
* through very many kinds of nodes; only the ones we can be sure are strict.
* 我们在这里不使用 expression_tree_walker，因为我们不想通过很多种节点；只有我们可以确定的节点才是严格的。
*/
Relids
find_nonnullable_rels(Node *clause)
{
return find_nonnullable_rels_walker(clause, true);
}
/*
* find_nonnullable_vars
* Determine which Vars are forced nonnullable by given clause.
确定哪些变量根据给定子句被强制为非空。
*
* Returns the set of all level-zero Vars that are referenced in the clause in
* such a way that the clause cannot possibly return TRUE if any of these Vars
* is NULL. (It is OK to err on the side of conservatism; hence the analysis
* here is simplistic.)
* 返回子句中引用的所有零级变量的集合，这样，如果这些变量中的任何一个为 NULL，子句就不可能返回 TRUE。
* （保守一点也没关系；因此这里的分析比较简单。）
*
* The semantics here are subtly different from contain_nonstrict_functions:
* that function is concerned with NULL results from arbitrary expressions,
* but here we assume that the input is a Boolean expression, and wish to
* see if NULL inputs will provably cause a FALSE-or-NULL result. We expect
* the expression to have been AND/OR flattened and converted to implicit-AND
* format.
* 此处的语义与 contain_nonstrict_functions 略有不同：该函数关注任意表达式的 NULL 结果，但此处我们假设输入是布尔表达式，并希望查看 NULL 输入是否可证明会导致 FALSE 或 NULL 结果。
* 我们期望表达式已被 AND/OR 平铺并转换为隐式 AND 格式。
*
* Attnos of the identified Vars are returned in a multibitmapset (a List of
* Bitmapsets). List indexes correspond to relids (varnos), while the per-rel
* Bitmapsets hold varattnos offset by FirstLowInvalidHeapAttributeNumber.
* 已识别 Var 的 Attnos 以多位图集 (Bitmapsets 列表) 的形式返回。
* 列表索引对应于 relids (varnos)，而每个相关位图集保存按 FirstLowInvalidHeapAttributeNumber 偏移的 varattnos。
*
* top_level is true while scanning top-level AND/OR structure; here, showing
* the result is either FALSE or NULL is good enough. top_level is false when
* we have descended below a NOT or a strict function: now we must be able to
* prove that the subexpression goes to NULL.
* 扫描顶层 AND/OR 结构时 top_level 为真；此时，显示结果为 FALSE 或 NULL 就足够了。
* 当我们下降到 NOT 或严格函数以下时，top_level 为假：现在我们必须能够证明子表达式变为 NULL。
*
* We don't use expression_tree_walker here because we don't want to descend
* through very many kinds of nodes; only the ones we can be sure are strict.
* 我们在这里不使用 expression_tree_walker，因为我们不想通过很多种节点；只有我们可以确定的节点才是严格的。
*/
List *
find_nonnullable_vars(Node *clause)
{
return find_nonnullable_vars_walker(clause, true);
}
/*
* find_forced_null_vars
* Determine which Vars must be NULL for the given clause to return TRUE.
* 确定哪些 Vars 必须为 NULL 才能使给定子句返回 TRUE。
*
* This is the complement of find_nonnullable_vars: find the level-zero Vars
* that must be NULL for the clause to return TRUE. (It is OK to err on the
* side of conservatism; hence the analysis here is simplistic. In fact,
* we only detect simple "var IS NULL" tests at the top level.)
* 这是 find_nonnullable_vars 的补充：查找必须为 NULL 才能使子句返回 TRUE 的零级 Var。
* （保守一点是可以的；因此这里的分析比较简单。事实上，我们只在顶层检测简单的“var IS NULL”测试。）
*
* As with find_nonnullable_vars, we return the varattnos of the identified
* Vars in a multibitmapset.
* 与 find_nonnullable_vars 一样，我们在多位图集中返回已识别 Var 的 varattnos。
*/
List *
find_forced_null_vars(Node *node)
这三个比较抽象(而且涉及到层层递归)，后面调试的时候我们再介绍相关内容吧！
下面继续调试SQL1，它的jointree和state1大家可以自行翻到上面去看。此时jtnode是FromExpr，首先使用上面信息收集函数处理当前层的f->quals也即：where过滤条件。如下：
在其walker函数的处理下，依次：
else if (IsA(node, NullTest))
{
/* IS NOT NULL can be considered strict, but only at top level */
NullTest *expr = (NullTest *) node;
if (top_level && expr->nulltesttype == IS_NOT_NULL && !expr->argisrow)
result = find_nonnullable_rels_walker((Node *) expr->arg, false);
}
继续，如下：
于是这里最后向上返回的result，(find_nonnullable_rels)在解析where条件f->quals得到的结果：收集严格约束条件所涉及的表的rtindex 就是score表的index=2 。
然后是find_forced_null_vars函数，经过对node的递归处理，如下：
如上图所示：这里检查的是var IS NULL自然就无法向上返回var进而无法汇总var->varno。
然后就将这两步收集到信息传递到下层，如下：
forboth(l, f->fromlist, s, state1->sub_states)
{
reduce_outer_joins_pass1_state *sub_state = lfirst(s);
if (sub_state->contains_outer)
reduce_outer_joins_pass2(lfirst(l), sub_state,
state2, root,
pass_nonnullable_rels,
pass_forced_null_vars);
}
这一层的jtnode是左外连接的JoinExpr，两个reduce_outer_joins_pass1_state *的变量实质上就是上面state图中的最下面的叶子节点：
如上图中 这里将左连接转换成了内连接，判断依据：
- 上层传入的
nonnullable_rels也就是where条件变量cno对应的表score表的rtindex：2 - 与(左连接)的右侧
Nullable-side或者补空一侧存在交集。
这时的左外连接可以简化成内连接了！
同样道理：若是该SQL是右外连接，那么与它进行比较的将是左侧 Nullable-side。
接下来就是修改相关值，如下：
除了修改(RangeTblEntry和JoinExpr中的)jointype，还有一个很重要的内容：将RTE_JOIN对应rte的rtindex=3给记录到state2->inner_reduced中！
接下来由于成功记录了，标志着我们成功降低了相关外连接的强度：
/*
* If we successfully reduced the strength of any outer joins, we must
* remove references to those joins as nulling rels. This is handled as
* an additional pass, for simplicity and because we can handle all
* fully-reduced joins in a single pass over the parse tree.
* 如果我们成功降低了任何外连接的强度，我们必须删除对这些连接作为无效rels的引用。
*/
if (!bms_is_empty(state2.inner_reduced)) // 这里面是那个 3
{
root->parse = (Query *)
remove_nulling_relids((Node *) root->parse,
state2.inner_reduced,
NULL);
/* There could be references in the append_rel_list, too */
root->append_rel_list = (List *)
remove_nulling_relids((Node *) root->append_rel_list,
state2.inner_reduced,
NULL);
}
接下来 我们直接看一下SQL1在经过reduce_outer_joins前后的root的对比，如下：
这里简单解释一下这几处不同，之后大家就会明白了外连接消除(外连接->内连接)的底层变换：
- 第一个是
QUERY中的rtable字段的第三个RANGETBLENTRY里面的jointype - 第二个是
jointree中的fromlist中的jointype - 第三个是
jointree中的quals里面NULLTEST表达式的var->varnullingrels - 后面三个是
targetList中后三个(score表的)TARGETENTRY中的var->varnullingrels。因为他们三个以后也不能被JOIN赋空了，而student(左连接的左表)的列本来就不能赋空值
我们在上面也提到优化的这个SQL1实质上就等同于下面的：
postgres=# explain SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE cno IS NOT NULL;
QUERY PLAN
--------------------------------------------------------------
Nested Loop (cost=0.00..2.06 rows=1 width=23)
Join Filter: (student.sno = score.sno)
-> Seq Scan on score (cost=0.00..1.01 rows=1 width=12)
Filter: (cno IS NOT NULL)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
(5 rows)
postgres=# explain SELECT * FROM STUDENT inner JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE cno IS NOT NULL;
QUERY PLAN
--------------------------------------------------------------
Nested Loop (cost=0.00..2.06 rows=1 width=23)
Join Filter: (student.sno = score.sno)
-> Seq Scan on score (cost=0.00..1.01 rows=1 width=12)
Filter: (cno IS NOT NULL)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
(5 rows)
postgres=#
注：有兴趣的小伙伴可以自行去比较一下上面这两个SQL在经历外连接消除之后的root！(几乎是一模一样的)
左(右)外连接->反半连接
postgres=# SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE SCORE.sno IS NULL;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
2 | ls | 1 | | |
(1 row)
postgres=# explain SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE SCORE.sno IS NULL;
QUERY PLAN
------------------------------------------------------------------
Nested Loop Anti Join (cost=0.00..2.06 rows=1 width=23)
Join Filter: (student.sno = score.sno)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
-> Materialize (cost=0.00..1.01 rows=1 width=12)
-> Seq Scan on score (cost=0.00..1.01 rows=1 width=12)
(5 rows)
postgres=#
下面来调试一下上面SQL，如下：
上面经过reduce_outer_joins_pass1预检之后的state1如上所示，不再赘述！
首先处理的jtnode = FromExpr，还是使用find_nonnullable_rels函数先行检查当前层的f->quals，该where条件表达式是IS NULL。这不是一个严格的约束条件，于是这里最后返回空。
即：最后的pass_nonnullable_rels也是空！接下来使用find_forced_null_vars函数继续检查f->quals，如下：
于是最后的pass_forced_null_vars内容，如下：
下一层jtnode = JoinExpr，因为nonnullable_rels为空，与right_state->relids自然没有交集。这里的左外连接无法转换为内连接：
因为它是左连接，于是继续处理：
/*
* See if we can reduce JOIN_LEFT to JOIN_ANTI. This is the case if
* the join's own quals are strict for any var that was forced null by
* higher qual levels. NOTE: there are other ways that we could
* detect an anti-join, in particular if we were to check whether Vars
* coming from the RHS must be non-null because of table constraints.
* That seems complicated and expensive though (in particular, one
* would have to be wary of lower outer joins). For the moment this
* seems sufficient.
*
* 看看我们是否可以将 JOIN_LEFT 减少到 JOIN_ANTI。
* 如果连接自身的限定条件对于被更高限定等级强制为空的任何变量都是严格的，情况就是如此。
* 注意：还有其他方法可以检测反连接，特别是如果我们要检查来自 RHS 的变量是否由于表约束而必须为非空。
* 但这似乎很复杂且成本高昂（特别是，人们必须警惕较低的外连接）。
* 目前这似乎足够了。
*/
if (jointype == JOIN_LEFT)
{
List *nonnullable_vars;
Bitmapset *overlap;
/* Find Vars in j->quals that must be non-null in joined rows */
// 在 j->quals 中查找在连接行中必须为非空的变量
nonnullable_vars = find_nonnullable_vars(j->quals);
/*
* It's not sufficient to check whether nonnullable_vars and
* forced_null_vars overlap: we need to know if the overlap
* includes any RHS variables.
*
* 检查 nonnullable_vars 和 forced_null_vars 是否重叠是不够的：
* 我们需要知道重叠是否包含任何 RHS 变量。
*/
overlap = mbms_overlap_sets(nonnullable_vars, forced_null_vars);
if (bms_overlap(overlap, right_state->relids))
jointype = JOIN_ANTI;
}
这里就是在使用find_nonnullable_vars来收集严格约束条件j->quals中的Var。指的就是 join的约束条件：ON STUDENT.sno = SCORE.sno，如下：
// 该表达式在递归遍历之后 底层：
// src/include/catalog/pg_proc.dat
{ oid => '65',
proname => 'int4eq', proleakproof => 't', prorettype => 'bool',
proargtypes => 'int4 int4', prosrc => 'int4eq' },
该表达式也是严格的，于是可以继续向下遍历相关var：
对这个list进行遍历之后，得到的严格约束条件j->quals中的Var，如下(也即nonnullable_vars)：
于是对于这个左外连接来说， nonnullable_vars(里面是STUDENT.sno、SCORE.sno) 和 forced_null_vars(里面是 SCORE.sno)确定发生重叠。且发生重叠的正是overlap: rtindex=2就是右表：
这里小结一下上面的逻辑，左连接转换为反半连接的判断条件如下：
- 当前层有严格的约束条件(看连接条件ON STUDENT.sno = SCORE.sno)
- 当前层的约束条件和上层传递进来的非严格条件(where 过滤条件SCORE.sno IS NULL)有交集
- 交集中的Var， 引用了 Nullable-side 的表
之后就是修改相关变量的值，有兴趣的小伙伴可以自行去调试！
而对于下面SQL，未能成功转换：
postgres=# explain SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE cno IS NULL;
QUERY PLAN
------------------------------------------------------------------
Nested Loop Left Join (cost=0.00..2.06 rows=1 width=23)
Join Filter: (student.sno = score.sno)
Filter: (score.cno IS NULL)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
-> Materialize (cost=0.00..1.01 rows=1 width=12)
-> Seq Scan on score (cost=0.00..1.01 rows=1 width=12)
(6 rows)
postgres=# SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE cno IS NULL;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
2 | ls | 1 | | |
(1 row)
postgres=#
postgres=# \d+ student
Table "public.student"
Column | Type | Collation | Nullable | Default | Storage | Compression | Stats target | Description
--------+-----------------------+-----------+----------+---------+----------+-------------+--------------+-------------
sno | integer | | | | plain | | |
sname | character varying(10) | | | | extended | | |
ssex | integer | | | | plain | | |
Access method: heap
postgres=# \d+ score
Table "public.score"
Column | Type | Collation | Nullable | Default | Storage | Compression | Stats target | Description
--------+---------+-----------+----------+---------+---------+-------------+--------------+-------------
sno | integer | | | | plain | | |
cno | integer | | | | plain | | |
degree | integer | | | | plain | | |
Access method: heap
postgres=#
当然这里不能只看最后SQL的执行结果，简单分析一下：当前层的约束条件和上层传递进来的非严格条件(where 过滤条件cno IS NULL)在var上没有交集：
全外连接->内连接
首先看一下SQL示例，如下：
postgres=# table student ;
sno | sname | ssex
-----+-------+------
1 | zs | 1
2 | ls | 1
(2 rows)
postgres=# table score ;
sno | cno | degree
-----+-----+--------
1 | 1 | 36
3 | 3 | 99
(2 rows)
postgres=# SELECT * FROM STUDENT full JOIN SCORE ON STUDENT.sno = SCORE.sno ;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
1 | zs | 1 | 1 | 1 | 36
2 | ls | 1 | | |
| | | 3 | 3 | 99
(3 rows)
postgres=# explain SELECT * FROM STUDENT full JOIN SCORE ON STUDENT.sno = SCORE.sno ;
QUERY PLAN
------------------------------------------------------------------
Hash Full Join (cost=1.04..2.09 rows=2 width=23)
Hash Cond: (student.sno = score.sno)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
-> Hash (cost=1.02..1.02 rows=2 width=12)
-> Seq Scan on score (cost=0.00..1.02 rows=2 width=12)
(5 rows)
postgres=# explain SELECT * FROM STUDENT full JOIN SCORE ON STUDENT.sno = SCORE.sno where student.sno IS NOT NULL and score.sno IS NOT NULL;
QUERY PLAN
------------------------------------------------------------------
Nested Loop (cost=0.00..2.10 rows=2 width=23)
Join Filter: (student.sno = score.sno)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
Filter: (sno IS NOT NULL)
-> Materialize (cost=0.00..1.03 rows=2 width=12)
-> Seq Scan on score (cost=0.00..1.02 rows=2 width=12)
Filter: (sno IS NOT NULL)
(7 rows)
postgres=# SELECT * FROM STUDENT full JOIN SCORE ON STUDENT.sno = SCORE.sno where student.sno IS NOT NULL and score.sno IS NOT NULL;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
1 | zs | 1 | 1 | 1 | 36
(1 row)
postgres=#
如上的执行计划，在增加了外层约束条件：student.sno IS NOT NULL and score.sno IS NOT NULL之后，该full join转换成了内连接。接下来我们对这个示例进行调试，如下：
函数reduce_outer_joins_pass1预检之后的state1如上所示。阶段二，在jtnode = FromExpr一层：
/* Scan quals to see if we can add any constraints */
// 扫描这个where约束条件
pass_nonnullable_rels = find_nonnullable_rels(f->quals); // 值为1、2 分别代表student、score
pass_nonnullable_rels = bms_add_members(pass_nonnullable_rels,
nonnullable_rels);
pass_forced_null_vars = find_forced_null_vars(f->quals);// 空
pass_forced_null_vars = mbms_add_members(pass_forced_null_vars,
forced_null_vars);
在jtnode = JoinExpr层，该全外连接被成功消除：
分析一下：
- 全连接的两端都可以被认为是Nullable-side
- 上层有严格的约束条件(例如这个where条件)
- 约束条件中引用了 Nuliable-side 的表：这里 nonnullable rels 和 LHS&RHS 都有交集， 转变为内连接
全外连接->左外连接
注1：看这里的标题，我这里只写了->左外连接而没有->右外连接，这是为什么？
注2：张树杰书中的这一段内容是什么意思？
带着这些问题，请先看一下下面的示例：
postgres=# SELECT * FROM STUDENT full JOIN SCORE ON STUDENT.sno = SCORE.sno ;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
1 | zs | 1 | 1 | 1 | 36
2 | ls | 1 | | |
| | | 3 | 3 | 99
(3 rows)
postgres=# SELECT * FROM STUDENT full JOIN SCORE ON STUDENT.sno = SCORE.sno where score.sno IS NOT NULL;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
1 | zs | 1 | 1 | 1 | 36
| | | 3 | 3 | 99
(2 rows)
postgres=# SELECT * FROM STUDENT full JOIN SCORE ON STUDENT.sno = SCORE.sno where student.sno IS NOT NULL;
sno | sname | ssex | sno | cno | degree
-----+-------+------+-----+-----+--------
1 | zs | 1 | 1 | 1 | 36
2 | ls | 1 | | |
(2 rows)
postgres=# explain SELECT * FROM STUDENT full JOIN SCORE ON STUDENT.sno = SCORE.sno where score.sno IS NOT NULL;
QUERY PLAN
--------------------------------------------------------------------
Nested Loop Left Join (cost=0.00..2.10 rows=2 width=23)
Join Filter: (student.sno = score.sno)
-> Seq Scan on score (cost=0.00..1.02 rows=2 width=12)
Filter: (sno IS NOT NULL)
-> Materialize (cost=0.00..1.03 rows=2 width=11)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
(6 rows)
postgres=# explain SELECT * FROM STUDENT full JOIN SCORE ON STUDENT.sno = SCORE.sno where student.sno IS NOT NULL;
QUERY PLAN
------------------------------------------------------------------
Nested Loop Left Join (cost=0.00..2.10 rows=2 width=23)
Join Filter: (student.sno = score.sno)
-> Seq Scan on student (cost=0.00..1.02 rows=2 width=11)
Filter: (sno IS NOT NULL)
-> Materialize (cost=0.00..1.03 rows=2 width=12)
-> Seq Scan on score (cost=0.00..1.02 rows=2 width=12)
(6 rows)
postgres=#
如上，大家会不会有这样的疑惑：① 倒数第二个执行计划为什么是left join，但是确实是正确的 因为先行扫描的是score表，右表是student；② 两个全连接都被处理成了左外连接。本人计划在这一块把上面这些问题都给覆盖到！
下面开始进行调试，如下：
/* Scan quals to see if we can add any constraints */
// 扫描这个where约束条件 score.sno IS NOT NULL
pass_nonnullable_rels = find_nonnullable_rels(f->quals); // 值为 2 分别代表 score
pass_nonnullable_rels = bms_add_members(pass_nonnullable_rels,
nonnullable_rels);
pass_forced_null_vars = find_forced_null_vars(f->quals);// 空
pass_forced_null_vars = mbms_add_members(pass_forced_null_vars,
forced_null_vars);
在下一层，首先因为nonnullable_rels、right_state->relids两者有交集 于是首先被转成右连接，如下：
这里暂停一下，先解释一下上面的逻辑，如下：
typedef struct reduce_outer_joins_partial_state
{
int full_join_rti; /* RT index of a formerly-FULL join */ // 旧 FULL JOIN的 RT 索引
Relids unreduced_side; /* relids in its still-nullable side */ // 其仍然可空的一侧的 表
} reduce_outer_joins_partial_state;
/* Helper for reduce_outer_joins_pass2 */
static void
report_reduced_full_join(reduce_outer_joins_pass2_state *state2,
int rtindex, Relids relids)
{
reduce_outer_joins_partial_state *statep;
statep = palloc(sizeof(reduce_outer_joins_partial_state));
statep->full_join_rti = rtindex;
statep->unreduced_side = relids; // 不修改的一侧(这一侧 仍然可能被JOIN赋空)
state2->partial_reduced = lappend(state2->partial_reduced, statep);
}
概括一下：
- 对于上面全连接 它被转成了右连接(因为score.sno IS NOT NULL，且引用了score表)
- 但是left_state(student表)一侧 仍然可能为空，因此先被记录在
state2->partial_reduced
/*
* Convert JOIN_RIGHT to JOIN_LEFT. Note that in the case where we
* reduced JOIN_FULL to JOIN_RIGHT, this will mean the JoinExpr no
* longer matches the internal ordering of any CoalesceExpr's built to
* represent merged join variables. We don't care about that at
* present, but be wary of it ...
*
* 将 JOIN_RIGHT 转换为 JOIN_LEFT。
* 请注意，在我们将 JOIN_FULL 缩减为 JOIN_RIGHT 的情况下，这意味着 JoinExpr 不再与任何为表示合并连接变量而构建的 CoalesceExpr 的内部顺序相匹配。
* 我们目前并不关心这一点，但要小心……
*/
if (jointype == JOIN_RIGHT)
{
Node *tmparg;
tmparg = j->larg;
j->larg = j->rarg;
j->rarg = tmparg;
jointype = JOIN_LEFT;
right_state = linitial(state1->sub_states);
left_state = lsecond(state1->sub_states);
}
如上就是张树杰书中提到的额外工作：将所有的右外连接都转换为左外连接。(无论是本身就是右连接，还是被转换成的)这里交换了一下左右的顺序，于是这就是为什么全连接最终只能->左连接(而没有->右连接)。
再往下就是回到了上面相同的逻辑，如下：
但是这里无法再转成反半连接了，因为没有强制为空的变量。
最后就是像上面转成内连接要做we must remove references to those joins as nulling rels一样，这里同样需要修改相关数据结构中变量的值一样：
这里再次看一下函数remove_nulling_relids，如下：
/*
* remove_nulling_relids() removes mentions of the specified RT index(es)
* in Var.varnullingrels and PlaceHolderVar.phnullingrels fields within
* the given expression, except in nodes belonging to rels listed in
* except_relids.
*
* remove_nulling_relids() 删除给定表达式中的Var.varnullingrels 和 PlaceHolderVar.phnullingrels 字段中指定 RT 索引的提示，
* 但属于 except_relids 中列出的 rels 的节点除外。
*/
Node *
remove_nulling_relids(Node *node,
const Bitmapset *removable_relids,
const Bitmapset *except_relids)
{
remove_nulling_relids_context context;
context.removable_relids = removable_relids;
context.except_relids = except_relids;
context.sublevels_up = 0;
return query_or_expression_tree_mutator(node,
remove_nulling_relids_mutator,
&context,
0);
}
注：我们在上面提到：但是left_state(student表)一侧 仍然可能为空，因此被记录在state2->partial_reduced，于是except_relids就是在这里用到了，如下：
这里简单解释一下这几处不同，之后大家就会明白了外连接消除(全外连接->左外连接)的底层变换：
- 第一个是
QUERY中的rtable字段的第三个RANGETBLENTRY里面的jointype - 第二个是
jointree中的fromlist中的jointype - 第三和四是
jointree中的fromlist中的larg、rarg做了交换 - 第五个是
jointree中的quals里面NULLTEST表达式的var->varnullingrels - 后面三个是
targetList中后三个(score表的)TARGETENTRY中的var->varnullingrels
而except_relids的存在，student表相关的列在以后的查询中还有可能赋空 因此它的RT index还是在的，如下：
有兴趣的小伙伴可以自行去调试，这里不再向下了！