PostgreSQL/GreenPlum Merge Inner Join 解密
1、什么是Merge Join
合并连接是一种匹配算法，其中外表的每个记录与内表的每个记录进行匹配，直到存在连接子句匹配的可能性为止。
仅当两个表都已排序并且
join子句的运算符是“=”时
，才使用该算法。
如下图所示：
merge join的字节点需要Sort节点对内外表进行排序，然后进行join。
2、Merge Inner Join状态机
状态机如下图所示：
EXEC_MJ_INITIALIZE_OUTER
该状态是初始状态，首先要从外表进行扫描。获取外表记录。根据外表扫描的记录进行判断：
1) 外表为空，即扫描出来的记录为空，或者第一个 join条件的左表值为NULL并且null排序后放在最后且为inner join，则结束join，返回NULL
2) 左表值为 NULL或者null排序后放在前面，则重新进入EXEC_MJ_INITIALIZE_OUTER状态，扫描左表
3) 非上述两种条件，则进入 EXEC_MJ_INITIALIZE_INNER状态，获取内表记录
EXEC_MJ_INITIALIZE_INNER
该状态下扫描内表。根据扫描的记录进行判断：
1) 内表为空，即扫描出来的记录为空，或者 第一个 join条件的左表值为NULL并且null排序后放在最后且为inner join，则结束join，返回NULL
2) 内表值为 NULL或者null排序后放在前面，则重新进入EXEC_MJ_INITIALIZE_INNER状态，扫描右表
3) 非上述两种条件，则进入 EXEC_MJ_SKIP_TEST状态
EXEC_MJ_SKIP_TEST
该状态需要对左右表值进行 join条件比较，根据比较结果判断：
1) 左 = 右：标记内表排序后当前扫描位置；标记当前扫描的slot，进入EXEC_MJ_JOINTUPLES状态
2) 左 < 右：进入EXEC_MJ_SKIPOUTER_ADVANCE状态，扫描左表下一条记录
3) 左 > 右：进入EXEC_MJ_SKIPINNER_ADVANCE状态，扫描右表下一条记录
EXEC_MJ_SKIPOUTER_ADVANCE
该状态扫描外表下一条记录。根据扫描的记录进行判断：
1) 外表扫描完，即扫描出来的记录为空，或者第一个 join条件的左表值为NULL并且null排序后放在最后且为inner join，则结束join，返回NULL
2) 左表值为 NULL或者null排序后放在前面，则重新进入EXEC_MJ_SKIPOUTER_ADVANCE状态，扫描左表
3) 非上述两种条件，则进入 EXEC_MJ_SKIP_TEST状态，进行比较
EXEC_MJ_SKIPINNER_ADVANCE
该状态扫描内表下一条记录，根据扫描的记录进行判断：
1) 内表扫描完，即扫描出来的记录为空，或者第一个 join条件的左表值为NULL并且null排序后放在最后且为inner join，则结束join，返回NULL
2) 内表值为 NULL或者null排序后放在前面，则重新进入EXEC_MJ_SKIPINNER_ADVANCE状态，扫描内表
3) 非上述两种条件，则进入 EXEC_MJ_SKIP_TEST状态，进行比较 因为左 > 右才会进入该状态，右时一个NULL，那么左表后面的值肯定也比右的前一个值大，所以join结束。
EXEC_MJ_JOINTUPLES
该状态下，将左右表的值进行连接投影，输出结果。下个周期调用 ExecMergeJoin函数时，直接进入EXEC_MJ_NEXTINNER状态。
EXEC_MJ_NEXTINNER
该状态下，扫描内表下一条记录。并根据扫描的记录进行判断：
1) 内表扫描完，即扫描出来的记录为空，或者第一个 join条件的左表值为NULL并且null排序后放在最后且为inner join，则进入EXEC_MJ_NEXTOUTER状态
2) 内表值为 NULL或者null排序后放在前面，则进入EXEC_MJ_NEXTOUTER状态
3) 非上述两种条件，进行比较，根据比较值进行操作：
左 = 右：进入EXEC_MJ_JOINTUPLES状态
左 < 右：进入EXEC_MJ_NEXTOUTER状态
不可能有左 > 右的分支，因为该状态由 ① 分支而来，排序都是由小到大，所以要么相等，要么右边大
EXEC_MJ_NEXTOUTER
该状态下获取外表的下一条记录，并根据值进行判断：
1) 外表扫描完，即扫描出来的记录为空，或者第一个 join条件的左表值为NULL并且null排序后放在最后且为inner join，则结束join，返回NULL
2) 左表值为 NULL或者null排序后放在前面，则重新进入EXEC_MJ_NEXTOUTER状态，获取外表下一条记录
3) 非上述两种条件，则进入 EXEC_MJ_JOINTUPLES状态，否则进入EXEC_MJ_TESTOUTER状态
EXEC_MJ_TESTOUTER
该状态下，获取标记的内表值，并与外表值比较
1) 左 = 右：需要标记内表排序的位置，并将当前slot放到mj_InnerTupleSlot中
2) 左 > 右：重新获取右表当前扫描的位置的记录
（1） 内表扫描完，或者内表记录为 NULL并且第一个join条件并且null排在最后，结束join，返回NULL
（2） 内表记录为 NULL，并且非第一个join条件或null排在前面，进入EXEC_MJ_SKIPINNER_ADVANCE状态，获取内表下一条记录
（3） 非上述 2种情况，进入EXEC_MJ_SKIP_TEST状态 不可能有左 < 右的分支，因为该状态由 ① 而来，排序都是由小到大，要么相等，要么左边大。
