分块嵌套循环连接 | Codeboy's Blog

形式陈述

输入是两张有限bag R、S和可判定连接条件θ。输出为所有满足θ(r,s)的输入出现对，保留两侧出现次数；相同值匹配的输出可以重复。本文在DB-4页模型中先固定相等连接，并假定内表可从头重新扫描。

F≥3个数据帧中，F−2帧保存一块外表记录，1帧顺序读内表，1帧放输出。算法依次读一块R；对S每页中的每条s，遍历当前R块的每条r，满足θ就输出；S到末尾后释放R块，载入下一块，再从S开头开始。已知任一输入为空时直接输出空bag；若需要实际读取才能发现为空，其发现成本另计。

不变量是：已完成外块与整个S的匹配均已输出且只输出一次；当前块只输出了与已访问S出现的配对；后续外块尚未输出。外块不重叠且覆盖R，各内扫描覆盖S，所以任一(r,s)出现对被比较恰好一次。这同时给出完备性与无额外重复性，不能把相同值的两份r合并掉。

若R占P>0页、S占Q>0页，忽略输出且不跨轮缓存S，精确输入I/O为

P+\left\lceil P/(F-2)\right\rceil Q.

全部记录对比较次数为|R||S|。I/O变少不等于比较次数也随块大小下降；输出Z份还需Ω(Z)的枚举工作和按输出宽度计的页写。

直觉

逐记录外循环为了每条r重读S，浪费了同页其余记录已经被读入的机会。分块后，让一次S扫描服务一整块r；保留更多外记录就是减少内表重扫轮数。

它不依赖可哈希的等号，θ可以是小于或一个更复杂的谓词。代价是可能检查大量最终不匹配的记录对。

例子与边界

DB-4的R键顺序为1,2,1,3,2,4，共3页；S键顺序2,1,2,3,1,5,4,2，共4页，F=4。第一块R为前4条，占2帧；扫描S4页，键1贡献2×2=4份，键2的B行贡献3份，键3贡献1份，合8份。第二块为(2,D),(4,E)，再扫描S4页，分别贡献3、1份，合4份。

R页只读3次，S共读8次，所以输入I/O=11；12份输出按DB-4宽度写12页，总23。全程最大2外块+1内页+1输出=4帧。第一块消费完才可覆盖其帧；输出持有借用r时须先复制或等待消费者用完。

改以S作外侧：4页分成两个2页块，各扫R3页，输入成本4+2×3=10，比R外侧11少1。不能只根据3<4认定R外侧更优。没有取整、块数很大时，小外表往往有利；实际优化仍应比较两边的完整公式。

若F=3，只能保留1页R，成本3+3×4=15；F=5则能保留全R，成本3+4=7。内存跨越整块阈值时，成本是台阶式变化。

若S是网络流或昂贵子计划的输出，第二次扫描可能无法完成。必须先物化S并计写读，或为每个R块重新执行S子计划；后者还须保证相同读视图和逻辑输入。F≤2时，这份同时保留外、内、输出的算法配置无效，不可给公式中的分母强行取正。

推论与应用

索引嵌套循环把“对每个r扫描全部S”替换为“用r的键探测S索引”。索引必须返回所有匹配出现；非唯一键只取一条会改变bag。成本至少包括外扫描、每次索引路径和回表页，不能只乘树高。具体覆盖与回表情形接B+树。

Hash join分区发生极端同键倾斜时，可以只对无法装入的分区退回本算法。这样虽然慢，却能在有限内存下保证结束；反复把相同键hash到更深层无法把它们分开。

参考资料

CMU 15-445/645 Fall 2025，Join Algorithms，§3：嵌套循环、缓冲页分配和索引探测。
Goetz Graefe, “Query Evaluation Techniques for Large Databases”，ACM Computing Surveys 25(2), 1993，§5.1，印刷pp.105–106：嵌套循环连接；本文DB-4取整反例和出现对证明为独立推导。