跟我一起读postgresql源码(十三)——Executor(查询执行模块之——Join节点(上))

JOIN节点有以下三种：

T_NestLoopState, T_MergeJoinState, T_HashJoinState,

连接类型节点对应于关系代数中的连接操作，PostgreSQL中定义了如下几种连接类型(以T1 JOIN T2 为例)：

1)Inner Join:内连接，将T1的所有元组与T2中所有满足连接条件的元组进行连接操作。

2)Left Outer Join:左连接，在内连接的基础上，对于那些找不到可连接T2元组的T1元组，用一个空值元组与之连接。

3)Right Outer Join:右连接，在内连接的基础上，对于那些找不到可连接T1元组的T2元组，用一个空值元组与之连接。

4)Full Outer Join:全外连接，在内连接的基础上，对于那些找不到可连接T2元组的T1元组，以及那些找不到可连接T1元组的T2元组，都要用一个空值元组与之连接。

5)Semi Join:类似IN操作，当T1的一个元组在T2中能够找到一个满足连接条件的元组时，返回该T1元组，但并不与匹配的T2元组连接。

6)Anti Join:类型NOT IN操作，当T1的一个元组在T2中未找到满足连接条件的元组时，返回该T1元组与空元组的连接。

我们再看看postgres用户手册里是怎么说的：

条件连接：

T1 { [INNER] | { LEFT | RIGHT | FULL } [OUTER] } JOIN T2 ON boolean_expression T1 { [INNER] | { LEFT | RIGHT | FULL } [OUTER] } JOIN T2 USING ( join column list ) T1 NATURAL { [INNER] | { LEFT | RIGHT | FULL } [OUTER] } JOIN T2

这样看起来，只有头四种连接方式(INNER, LEFT JOIN, RIGHT JOIN, FULL JOIN)在SQL语句中显示使用了，后两种其实是作为postgres内部使用的，例如Semi Join，我之前说过对于SubqueryScan节点，有可能把ANY和EXIST子句转换为半连接。半连接就是Semi Join。

而对于你所指定的连接方式，PostgreSQL内部会见机行事，使用不同的连接操作。

这里，postgres实现了三种连接操作，分别是：嵌套循环连接(Nest Loop)、归并连接(Merge Join)和Hash连接(Hash Join)。

其中归并连接算法可以实现上述六种连接，而嵌套循环连接和Hash连接只能实现 Inner Join、Left Outer Join、Semi Join 和 AntiJoin四种连接。

如图6-52所示，连接节点有公共父类Join, Join继承了 Plan的所有属性，并扩展定义了 jointype用以存储连接的类型，joinqual用于存储连接的条件。

typedef struct Join { Plan plan; JoinType jointype; List *joinqual; /* JOIN quals (in addition to plan.qual) */ } Join;

对应的执行状态节点JoinState中定义了jointype存储连接类型，joinqual存储连接条件初始化后的状态链表。

typedef struct JoinState { PlanState ps; JoinType jointype; List *joinqual; /* JOIN quals (in addition to ps.qual) */ } JoinState; 1.NestLoop节点

NestLoop节点实现了嵌套循环连接方法，能够进行Inner Join、Left Outer Join、Semi Join和Anti Join四种连接方式。
举例如下：

postgres=# explain select a.*,b.* from test_dm a join test_dm2 b on a.id > b.id; QUERY PLAN -------------------------------------------------------------------------------- Nested Loop (cost=0.00..150000503303.17 rows=3333339000000 width=137) Join Filter: (a.id > b.id) -> Seq Scan on test_dm2 b (cost=0.00..223457.17 rows=10000017 width=69) -> Materialize (cost=0.00..27346.00 rows=1000000 width=68) -> Seq Scan on test_dm a (cost=0.00..22346.00 rows=1000000 width=68) (5 行) typedef struct NestLoop { Join join; List *nestParams; /* list of NestLoopParam nodes */ } NestLoop;

NestLoop节点在Join节点的基础上扩展了nestParams字段，这个字段nestParams是一些执行器参数的列表，这些参数的用处是将外部子计划的当前行执行值传递到内部子计划中。目前主要的传递形式是Var型，这个数据结构的定义在：

src/include/nodes/primnodes.h Var - expression node representing a variable (ie, a table column)

下面是状态节点NestLoopState的定义。

typedef struct NestLoopState { JoinState js; /* its first field is NodeTag */ bool nl_NeedNewOuter; //true if need new outer tuple on next call bool nl_MatchedOuter; //true if found a join match for current outer tuple TupleTableSlot *nl_NullInnerTupleSlot; //prepared null tuple for left outer joins } NestLoopState;

NestLoop节点的初始化过程(ExecEndNestLoop函数)中初始化NestLoopState节点，构造表达式上下文这些自不必说，还会对节点中连接条件(joinqual字段)进行处理，转化为对应的状态节点JoinState中的joinqual链表。并且对于LEFT JOIN和ANTI JOIN会初始化一个nl_NullInnerTupleSlot。why？

因为对于T1 JOIN T2，当T1的一个元组在T2中未找到满足连接条件的元组时，这两种连接方式会返回该T1元组与空元组的连接，这个空元组就是由nl_NullInnerTupleSlot实现。

最后还将进行如下两个操作：

1)将nl_NeedNewOuter标记为true,表示需要获取左子节点元组。

2)将nl_MatchedOuter标记为false,表示没有找到与当前左子节点元组匹配的右子节点元组。

初始化就是这些。

接下来是NESTLOOP的执行过程(ExecNestLoop函数)。