postgres中的merge join

目前数据库中的join操作无非三种 nextloop merge hash

本文分析pg的merge join 不得不说pg真是学习数据库实现的好东西不愧是学院派用来教学的代码写的干净注释清晰全面

pg源码中的伪代码 nodeMergejoin.c

 1 *        Join {
 2  *            get initial outer and inner tuples                INITIALIZE
 3  *            do forever {
 4  *                while (outer != inner) {                    SKIP_TEST
 5  *                    if (outer < inner)
 6  *                        advance outer                        SKIPOUTER_ADVANCE
 7  *                    else
 8  *                        advance inner                        SKIPINNER_ADVANCE
 9  *                }
10  *                mark inner position                            SKIP_TEST
11  *                do forever {
12  *                    while (outer == inner) {
13  *                        join tuples                            JOINTUPLES
14  *                        advance inner position                NEXTINNER
15  *                    }
16  *                    advance outer position                    NEXTOUTER
17  *                    if (outer == mark)                        TESTOUTER
18  *                        restore inner position to mark        TESTOUTER
19  *                    else
20  *                        break    // return to top of outer loop
21  *                }
22  *            }
23  *        }
24  *

merge join中的两列inner outer是需要排序的默认就是顺序了可能pg源码中描述的比较详细了
我应用了这一算法也就说说我的理解

1 有序两列inner outer，每列一个指针，初始化阶段两个指针分别指向每一列第一个值。

2 判断两个指针指向的数值，值小的向下偏移一个单元，然后继续比较，直到全部比较完毕或者两个值相等的时候跳出循环（伪代码第一个while的功能）

3 标记一下inner当前所处的位置和值

4 执行join操作直到两列值不相等

5 移动outer向下一个单元

6 当前outer和inner相等的话就把inner回退到之前标记的位置继续join

如果不等的话回到最开始重新寻找相等的位置进行join

毕竟是外代码给大家一个思路具体实现的时候肯定依据自己需求优化实现 pg用了状态机的方式真心nb！