“排序归并连接也可尝试最后归并趟融合，但两侧各有多个run时，需要同时保留两侧输入缓冲、重复键组与输出。两次排序各自有四帧并不意味着融合连接仍只用四帧。DB 4选择先把两输入各物化成一个run…”
形式陈述
输入为两张有限bag，按完整连接键相等输出全部出现对。先用外存排序得到键有序的R、S；随后维持两侧游标。若当前R键较小，推进R；若S键较小，推进S；相等为k时收集一侧同键组G_R(k)，让S中每份同键出现与组内全部R出现配对。S的k组耗尽后才释放G_R并继续。
跳过较小键安全，因为另一侧剩余键不小于当前较大键，已不可能再匹配。相等键阶段输出G_R(k)×G_S(k)的全部出现对；不同k的组互斥。因此该过程与共同bag规格一致。
本页的内存版归并给R游标1帧、S游标1帧、R重复组F−3帧、输出1帧，要求F≥4且每个R同键组能装下。两个非空输入已物化为有序文件时，归并至多读P+Q页，另付输出；一侧先耗尽时可以不读另一侧剩余尾页，只有实际读尽两侧时等号成立。先排序的总账至多为SortIO(R)+SortIO(S)+P+Q；排序最终趟若与连接融合，可以省临时写读，但须重新证明同时活跃run缓冲与重复组的预算。
直觉
两个有序游标很快找出“下一次能相遇的键”。真正困难的是相遇后有几份人要互相握手：左边2份、右边3份，就有6次配对，不是2次。
保存一侧组是为了让同组右记录重复使用它；它像一个局部内表。组装不下时，必须把这份重播责任变成明确的存储与读取。
例子与边界
DB-4有R3页、S4页，F=4。先独占四帧分别排序：R一次读3写3，S一次读4写4。采用原位内存排序，写已有帧时不另申请第五帧；两输入各形成一个run，合14次I/O。排序阶段结束释放这些帧，再启动归并。
R有序键为1,1,2,2,3,4；S为1,1,2,2,2,3,4,5。R每个同键组至多2条，每条64B，恰好一帧。两游标、一组、一输出合4帧。键1产生2×2=4份，键2产生2×3=6份，键3和4各1份，键5没有R，合12份。归并读7页，所以输入/临时成本14+7=21；按128B输出槽另写12页，总33。
如果遇等号就把两个游标都前进一步，键2只会输出两份，并漏掉另外四份。给任一游标加一个“重复值计数”也不自动解决输出不同payload的问题：B、D要分别与u、u、t配对。
超大重复组
若某个R键组有a页、S同键组有b页，R组装不下时可把两组物化为临时文件，然后在组内运行分块嵌套循环。本页保守实现先继续扫描并写完两组，再释放主游标的页引用，保留下一组起点；需要重新载入的边界页另计。组内读成本为a+ceil(a/(F−2))b，另外加临时组的写入和形成过程所读的页。
因此“排序后连接只读P+Q”需要重复组可驻留等条件。若所有行同键，输出本身达到|R||S|；组的重读也可能增加到乘积级。不能一边忽略输出，一边声称任意重复输入仍有无条件线性归并I/O。
推论与应用
已有适合键序的访问路径可以省排序，但必须确认可见行顺序及回表代价。非聚簇B+树按键给出RID，不代表堆页也按同一顺序连续读取。输入已经有序和“有一个索引”是两份不同证据。
连接输出天然按连接键分组，有时可直接供下游按同键聚合。这样下游只维护当前组状态，不必再排序；但如果它按另一列分组，原顺序通常不能复用。这也是优化器要保留有用物理顺序的原因。
空输入直接结束；升降序、字符串collation和复合键比较器必须在两侧一致。NULL安全相等、普通SQL等号与外连接补行有各自规则，本页只证明无NULL内等连接。
参考资料
- CMU 15-445/645 Fall 2025，Join Algorithms，§4：排序归并与重复键最坏情形。
- CMU 15-445/645 Fall 2025，Sorting & Aggregation Algorithms，§2：run形成与归并帧分配。四帧阶段调度和保守重复组fallback为本文自定。