“Hash join分区发生极端同键倾斜时，可以只对无法装入的分区退回本算法。这样虽然慢，却能在有限内存下保证结束；反复把相同键hash到更深层无法把它们分开。”
形式陈述
输入为有限bag R、S，连接条件是完整键的相等；输出每一份匹配出现对。采用页与帧预算，另明确哈希表示所需空间。基本hash join先把R建成哈希表，每个键保存全部R出现，再顺序读S；对每个s访问对应桶，比较原键，输出桶中每份相等r。hash值相同只是候选，不能替代相等比较。
R的整个哈希表示装不下时，Grace连接分两阶段，要求F≥3。先选分区函数h，把两表分别写入R₀,…,Rₖ₋₁和S₀,…,Sₖ₋₁；用1帧读输入、k≤F−1帧分别缓冲各分区输出。随后逐个i，把Rᵢ建表，再流式探测Sᵢ。连接阶段给build记录及链指针最多F−2帧，另留1帧probe和1帧输出。若桶头与游标另放C字节控制区，必须预先给出C且证明它们装得下；总内存是F×页载荷+C。没有额外控制区时，就从原F帧中扣除这些元数据，不能只数原表字节。DB-4采用C=64B的固定有界控制区。
不变量是同键的两侧出现一定进入同一分区，每份输入恰好进入一处；分区内的build列表不去重，probe逐个枚举全部相等出现。因此分区连接的bag并集与原连接相同，不同分区不会重复输出同一出现对。
若两表非空且严格执行先完整分区、再完整读取各分区的调度，原输入共P+Q页，分区后临时文件共T页，各build表示都能装入，排除最终输出的I/O为P+Q+2T：读取原输入，写T，再读T。仅在T=P+Q时才化为3(P+Q)。分区尾页、表示变化或递归分区都可能破坏这个等式。若先发现空表而短路，或跳过另一侧为空的分区，则按实际读写另计，不能仍称完整公式精确。
直觉
hash不是把答案算出来，而是先承诺“可能配成对的记录绝不会分家”。分区缩小了要同时放在内存里的集合，真正的匹配仍靠原键检查。
把重复键的值表写成key→单条记录会覆盖旧出现，变成另一种查询。bag连接需要key→出现列表，或者保留严格等价的计数及枚举协议。
例子与边界
DB-4的R为(1,A),(2,B),(1,A),(3,C),(2,D),(4,E)，S为(2,u),(1,v),(2,u),(3,w),(1,x),(5,y),(4,z),(2,t)。两输入共7页，每页2条，F=4；64B输入槽已预留链指针，两个桶头与有限游标放在另计的64B控制区。
取h(k)=k mod 2。R奇分区有(1,A),(1,A),(3,C)，偶分区有(2,B),(2,D),(4,E)，各3条占2页。S奇分区有(1,v),(3,w),(1,x),(5,y)，偶分区有(2,u),(2,u),(4,z),(2,t)，各4条占2页。四文件共8页，比原7页多一页，因为R的两个分区各有一个半空尾页。
分区阶段读7写8。连接阶段每个R分区的3条表示占2帧，顺序读对应S；总读8。原输入与临时文件共23次I/O；12份输出再写12页，总35。两份(2,u)分别探测R的B、D两条，所以产生B/u两份、D/u两份；不能因probe值重复而跳过第二次。
热键不会被再次hash拆开
假设某键在R里有100份，而build最多装4份。换任何仍按完整连接键计算的分区函数，这100份都走向同一子分区。无限递归不会终止。一个完备实现应检测分区没有缩小或限制递归层数，然后对该分区采用分块嵌套循环；或者按出现划块，并保证每块都与对应整个S热键组配对。后一种分块不是普通同键分区，不能只连接同编号块，否则漏掉跨块匹配。
即使不同键碰撞导致大桶，也要明确递归成本。对子分区再读一遍并重写，新增其读写页数；最后再付build/probe读取。一次3(P+Q)不再覆盖多层溢写。
推论与应用
选择build侧应比较实际哈希表示大小与最大分区，而不只看全表行数。窄投影可能让较多行的一侧占更少字节；极端偏斜也可能让平均分区很小、最大分区仍超预算。
Bloom过滤器可以在probe前排除确定没有build键的记录，但“可能存在”仍须查表，且不能丢掉重复出现。它主要改善负探测成本，不自动降低必须读取整个probe文件的顺序页数。
hash连接只处理能由相同键定位的等值条件。复合键必须包含所有等值组成，并用兼容的编码、哈希及相等规则；附加非等值条件在候选对上再检查。SQL NULL如何参与键等价须单独规定，本页固定无NULL。
参考资料
- CMU 15-445/645 Fall 2025，Join Algorithms，§5：build/probe、Grace分区和单热键fallback。DB-4尾页账本为本文独立复算。
- Goetz Graefe, “Query Evaluation Techniques for Large Databases”，ACM Computing Surveys 25(2), 1993，§5.3：hash连接、溢写和分区。