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 函数).
循环嵌套连接的基本思想如下 (以表 R(左关系) 与表 S(右关系)连接为例):
FOR each tuple s in S DO
FOR each tuple r in R DO
IF r and s join to make a tuple t THEN
output t;
为了迭代实现此方法,NestLoopState 中定义了字段 nl_NeedNewOuter 和 nl_MatchedOuter.当元组处于内层循环时,nl_NeedNewOuter 为 false, 内层循环结束时 nl_NeedNewOuter 设置为 true.为了能够处理 Left Outer Join 和 Anti Join, 需要知道内层循环是否找到了满足连接条件的内层元组,此信息由 nl_MatchedOuter 记录,当内层循环找到符合条件的元组时将其标记为 true.
NestLoop 执行过程主要是由 ExecNestLoop 函数来做.该函数主要是一个如上面提到的一个大循环.
该循环执行如下操作:
<1> 如果 nl_NeedNewOuter 为 true,则从左子节点获取元组,若获取的元组为 NULL 则返回空元组并结束执行过程.如果 nLNeedNewOuter 为 false, 则继续进行步骤 2.
<2> 从右子节点获取元组,若为 NULL 表明内层扫描完成,设置 nl_NeedNewOuter 为 true, 跳过步骤 3 继续循环.
<3> 判断右子节点元组是否与当前左子节点元组符合连接条件,若符合则返回连接结果.
以上过程能够完成 Inner Join 的递归执行过程.但是为了支持其他几种连接则还需要如下两个特殊的处理:
1)当找到符合连接条件的元组后将 nl_MatchedOuter 标记为 true.内层扫描完毕时,通过判断 nl_MatchedOuter 即可知道是否已经找到满足连接条件的元组,在处理 Left Outer Join 和 Anti Join 时需要进行与空元组 (nl_NullInnerTupleSlot) 的连接,然后将 nLMatchedOuter 设置为 false.
2) 当找到满足匹配条件的元组后,对于 Semi JOIN 和 Anti JOIN 方法需要设置 nl_NeedNewOuter 为 true.区别在于 Anti Join 需要不满足连接条件才能返回,所以要跳过返回连接结果继续执行循环.
NestLoop 节点的清理过程 (ExecEndNestLoop 函数) 没有特殊处理,只需递归调用左右子节点的清理过程.
2.MergeJoin 节点
Mergejoin 实现了对排序关系的归并连接算法,归并连接的输人都是已经排好序的.PostgreSQL 中 Mergejoin 算法实现的伪代码如下:
Join {
get initial outer and inner tuples INITIALIZE
do forever {
while (outer != inner) { SKIP_TEST
if (outer < inner)
advance outer SKIPOUTER_ADVANCE
else
advance inner SKIPINNER_ADVANCE
}
mark inner position SKIP_TEST
do forever {
while (outer == inner) {
join tuples JOINTUPLES
advance inner position NEXTINNER
}
advance outer position NEXTOUTER
if (outer == mark) TESTOUTER
restore inner position to mark TESTOUTER
else
break // return to top of outer loop
}
}
}
算法首先初始化左右子节点,然后执行以下操作 (其中对于大小的比较都是指对连接属性值的比较):
1)扫描到第一个匹配的位置,如果左子节点 (outer) 较大,从右子节点 (inner) 中获取元组;如果右子节点较大,从左子节点中获取元组.
2) 标记右子节点当前的位置.
3) 循环执行左子节点 == 右子节点判断,若符合则连接元组,并获取下一条右子节点元组,否则退出循环执行步骤 4.
4) 获取下一条左子节点元组.
5) 如果左子节点 == 标记处的右子节点 (说明该条左子节点与上一条相等),需要将右子节点扫描位置回退到扫描位置,并返冋步骤 3; 否则跳转到步骤 1.
为了说明归并排序的连接算法,我们以 Inner Join 为例给出部分执行过程,两个 current 分别指向输人的当前元组,mark 用于标记扫描的位置.
1) 首先找到左右序列第一个匹配位置,下图中 current(outer)=0 小于 Current(inner),因此 outer 的 current 向后移动.
2) 如图所示,当找到匹配项后,则进行连接,使用 mark 标记当前 inner 的扫描位置,并将 inner 的 current 向后移动.
3) 接着判断 current(outer) = 1 小于 current(inner) =2, 则将 outer 的 current 向后移动,并判断 outer 是否与 mark 相同 (这是为了发现 outer 的 current 与前一个相同的情况).
4) 下图显示 current(outer) =2 不等于 mark(inner) = 1,则继续扫描过程.
5) 判断两个 current 是否相同,发现 Currem(outer)=2 等于 current(inner)=2,则进行连接,同样标记 inner 的当前位置,并将 inner 的 cuirent 向后移动,如下图所示.其中的 current(inner) = 2 仍满足连接条件,因此连接完成后 inner 的 current 继续向后移动.
6) 如下图所示,current(outer)=2 小于 current(inner)=5, 则将 outer 的 current 指针向后移动.
7) 此时判断 current(outer) 和 mark(inner) 相等,则将 inner 的 current 指向 mark 的位置,重新获取 inner 的元组进行匹配,如下图所示.
8) 不断重复这样的匹配模式,直到 inner 或 outer 中的一方被扫描完毕,则表示连接完成.
MergeJoin 节点的定义如下:
typedef struct MergeJoin
{
Join join;
List *mergeclauses; /* mergeclauses as expression trees */
/* these are arrays, but have the same length as the mergeclauses list: */
Oid *mergeFamilies; /* per-clause OIDs of btree opfamilies */
Oid *mergeCollations; /* per-clause OIDs of collations */
int *mergeStrategies; /* per-clause ordering (ASC or DESC) */
bool *mergeNullsFirst; /* per-clause nulls ordering */
} MergeJoin;
该节点在 join 的基础上扩展定义了几个 mergexxx 字段.其中 mergeclauses 存储用于计算左右子节点元组是否匹配的表达式链表,mergeFamilies,mergeCollations,mergeStrategies,mergeNullsFirst 均与表达式链表对应,表明其中每一个操作符的操作符类,执行的策略 (ASC 或 DEC) 以及空值排序策略.
在初始化过程中,会使用 Mergejoin 构造 MergeJoinState 结构:
typedef struct MergeJoinState
{
JoinState js; /* its first field is NodeTag */
int mj_NumClauses;
MergeJoinClause mj_Clauses; /* array of length mj_NumClauses */
int mj_JoinState;
bool mj_ExtraMarks;
bool mj_ConstFalseJoin;
bool mj_FillOuter;
bool mj_FillInner;
bool mj_MatchedOuter;
bool mj_MatchedInner;
TupleTableSlot *mj_OuterTupleSlot;
TupleTableSlot *mj_InnerTupleSlot;
TupleTableSlot *mj_MarkedTupleSlot;
TupleTableSlot *mj_NullOuterTupleSlot;
TupleTableSlot *mj_NullInnerTupleSlot;
ExprContext *mj_OuterEContext;
ExprContext *mj_InnerEContext;
} MergeJoinState;
通过对于连接类型的判断来设置如下几个变量的值:
1)mj_FillOuter: 为 true 表示不能忽略没有匹配项的左子节点元组,需要与空元组进行连接,在 LEFT JOIN,ANTI JOIN 和 FULL JOIN 时为 true.
2)mj_FillInner: 为 true 表示不能忽略没有匹配项的右子节点元组,需要与空元组进行连接,在 RIGHT JOIN,FULL JOIN 时为 true.
3)mj_InnerTupleSlot: 为右子节点元组生成的空元组,在 mj_FillOuter 为真时构造.
4)mj_OuterTupleSlot: 为左子节点元组生成的空元组,在 mj_FillInner 为真时构造.
除此之外,需要将标记当前左 (右) 子节点元组是否找到能够连接的元组的变量 mj_MatchedOuter(mj_MatchedInner)设置为 false, 将存储左 (右) 子节点元组的字段 mj_NullOuterTupleSlot(mj_InnerTupleSlot)设置为 NULL, 并为 mj_MarkedTupleSlot 分配存储空间.
还剩一个 hashjoin,我看了半天看不太懂,下篇再说吧~
来源: https://www.cnblogs.com/flying-tiger/p/8331425.html