深入 PostgreSQL Merge Join 执行器

为什么需要 Merge Join

当两张表都已经在连接键上有序时，PostgreSQL 会优先选择 Merge Join（合并连接）：它不需要把任何一张表完整地搬进内存，而是像合并两个有序链表一样，同时向前扫描两个输入流，按排序键对齐元组。

这让它特别适合两类场景：

• 输入本身有 B-tree 索引，天然有序；
• 大数据集的等值连接，且排序代价可以摊薄。

代价是：输入必须有序。如果规划器拿不到有序输入，就会在下面挂一个 Sort 节点——这个排序的开销有时会让 Merge Join 反而不如 Hash Join。

代码位置

核心数据结构：MergeJoinState

执行时，每个 Merge Join 节点持有一个 MergeJoinState，其中最关键的几个字段：

typedef struct MergeJoinState {
    JoinState   js;                 /* 继承自 JoinState */
    int         mj_JoinState;       /* 当前状态机状态 */
    bool        mj_FillOuter;       /* 左/全外连接：填充无匹配的外层元组 */
    bool        mj_FillInner;       /* 右/全外连接：填充无匹配的内层元组 */
    bool        mj_MatchedOuter;
    bool        mj_MatchedInner;
    TupleTableSlot *mj_OuterTupleSlot;
    TupleTableSlot *mj_InnerTupleSlot;
    TupleTableSlot *mj_MarkedTupleSlot;  /* Mark/Restore 的标记位 */
    /* ... merge join 子句、比较函数等 ... */
} MergeJoinState;

• mj_OuterTupleSlot / mj_InnerTupleSlot：当前正在比较的外层、内层元组。
• mj_MarkedTupleSlot：最关键的字段——记住内层流的某个位置，用于处理重复 join key。
• mj_FillOuter / mj_FillInner：外连接时，无匹配的一侧需要用 NULL 填充后输出。

状态机：11 个状态

Merge Join 的执行主体是一个状态机。每次 ExecMergeJoin() 被调用，根据 mj_JoinState 跳到对应分支，处理完一段逻辑后转移到下一个状态。

核心算法

把状态机折叠成伪代码，主体结构是两层循环：

Join {
    取初始的外层元组 outer 和内层元组 inner

    do forever {
        // 第一阶段：对齐——把较小的那一侧向前推进
        while (outer != inner) {
            if (outer < inner)  前进外层
            else                前进内层
        }

        // 对齐成功，标记当前内层位置
        mark = inner

        do forever {
            // 第二阶段：输出所有 outer == inner 的组合
            while (outer == inner) {
                输出 (outer, inner) 的连接结果
                前进内层
            }

            前进外层
            if (outer == mark)   恢复内层到标记位  // 重复 join key
            else                 break            // 进入下一轮对齐
        }
    }
}

Mark/Restore：为什么要标记内层？

考虑这样两组输入（连接键相等的元组要两两组合）：

外层:  ... 5 5 5 ...
内层:  ... 5 5 ...

外层有 3 个 5，内层有 2 个 5，正确结果是 $3 \times 2 = 6$ 条记录。

算法的处理方式是：当第一个外层 5 对齐内层时，标记内层当前位置（mark）。把这个 5 和内层所有 5 配对后，外层前进到下一个 5——此时发现新的外层元组仍然等于 mark，就把内层指针恢复回标记位，再配对一遍。

没有 Mark/Restore，内层流已经被消费完，第二个外层 5 就找不到匹配了。这正是 mj_MarkedTupleSlot 存在的意义。

三种 Join 算法对比

一个经验法则：如果两侧都大、且能拿到有序输入，Merge Join 的常数因子和内存占用往往优于 Hash Join；否则 Hash Join 通常胜出。

小结

Merge Join 的精妙之处在于用状态机把"对齐 → 标记 → 配对 → 恢复"这套流程拆成可恢复的步骤，配合 Mark/Restore 机制优雅地处理重复 join key。理解这 11 个状态的转移，也就理解了 PostgreSQL 执行器处理有序连接的核心思路。

下次用 EXPLAIN 看到一个 Merge Join 节点下面挂着 Sort 时，不妨想想：规划器是相信排序的代价能换来流式、低内存的连接，值得吗？