Join 算法：嵌套循环、排序归并与 Hybrid Hash 的代价和实现
内容提要
文章通过模拟器与源码对比连接算法：Grace哈希代价3(M+N)仅在内存刚够分区时成立，内存充足时Hybrid可降至M+N；哈希并非总快于排序归并，后者遇大量重复键会退化；radix分区收益取决于哈希表与末级缓存差距，实际系统中很少兑现。文章还剖析了PostgreSQL 17与MySQL 8.4在溢出和倾斜处理上的差异。
延伸解读
代价公式的适用条件
文章指出，常见的“Grace hash join 代价为 3(M+N)”仅在内存刚好够分区时成立。当内存充足时，Hybrid hash join 可将代价降至 M+N。此外，哈希连接并非总快于排序归并，后者在遇到大量重复键时会退化为嵌套循环。radix 分区的收益取决于哈希表与末级缓存的差距，实际系统中很少兑现。这些结论提醒读者，算法选择需结合具体内存条件和数据分布。
工业实现的差异与局限
PostgreSQL 17 和 MySQL 8.4 在哈希连接溢出处理上策略不同：PostgreSQL 通过运行时加倍批次数来应对内存不足，但遇到构建侧重键时会放弃加倍并可能超出内存；MySQL 则采用分段装载和重读探测块的方式，不递归分区。两者都假设构建侧键分布均匀，对重键缺乏有效解决方案。这反映了理论算法在工程落地时的权衡与妥协。
内存中分区的实际收益
文章通过实验表明，当哈希表远大于末级缓存时，radix 分区能带来明显性能提升；若哈希表能放入缓存，分区收益很小。但多趟分区在真实硬件上可能因 TLB 和预取机制而表现不佳，单趟分区反而更快。完整系统集成后，分区收益往往被其他开销抵消，因此是否分区需根据数据规模和硬件特性谨慎评估。
Q&A
Grace hash join 的代价真的是 3(M+N) 吗？
不一定。3(M+N) 只在内存刚好够分区时成立。如果内存更充足，hybrid hash join 可以把代价降到 M+N。
sort-merge join 和 hash join 哪个更快？
没有绝对答案。Shapiro 证明 hybrid 在其模型下优于 sort-merge，但 Graefe 等人指出两者性能差别是百分比级别，不是倍数。sort-merge 在遇到大量重复键时会退化成嵌套循环。
PostgreSQL 17 如何处理哈希连接的内存溢出？
PostgreSQL 17 采用 hybrid hash join，当内存不足时通过加倍批次数（nbatch）来溢出到磁盘。如果加倍后所有元组都被写出或都没有写出，则停止加倍，可能超出内存。
MySQL 8.4 的哈希连接在内存不足时怎么做？
MySQL 8.4 在内存不足时会将构建侧数据哈希到最多 128 个 chunk 文件，然后对每个 chunk 对进行连接。如果 chunk 仍然太大，会分段加载构建 chunk 并反复重读探测 chunk，不进行递归分区。
内存中的哈希连接需要做 radix 分区吗？
取决于哈希表相对末级缓存的大小。当哈希表远大于末级缓存时，分区能带来明显收益；如果哈希表能放进缓存，收益很小。实际系统中很少兑现，如 Umbra 的测试中 TPC-H 的 59 个连接只有 1 个受益。
构建侧有大量重复键时，哈希连接会有什么问题？
递归分区无法解决构建侧重键问题，因为相同键的哈希值相同，总会落到同一分区。PostgreSQL 会停止加倍并可能超出内存，MySQL 会反复重读探测 chunk。建议交换构建侧，让重复键落在探测侧。
