PostgreSQL 查询系列 — 6. 哈希
原文：https://habr.com/en/companies/postgrespro/articles/581174/ （作者 Egor Rogov，PostgresPro）
引言
上一篇的嵌套循环胜在通用，但当外层集合很大、内层又缺乏高效索引时会退化得很惨。本篇讨论的哈希连接（Hash Join）针对的正是这种场景——只要连接条件是等值条件，就可以借助哈希表把"逐行查找"的开销降到接近常数级别。除了连接之外，PostgreSQL 里另外两个常见操作——分组聚合（GROUP BY/DISTINCT/UNION）和某些子查询的求值——也复用了同一套哈希思想，本文一并讨论。
哈希连接的基本原理
哈希连接依赖一个基本事实：如果连接条件是等值条件（a.key = b.key），那么可以对其中一个数据集（通常选较小的那个，称为"内层"或"构建端"）按连接键计算哈希值，把行分发到一个固定数量的桶（bucket）里（桶数总是 2 的幂次，方便用位运算做取模），构建出一张哈希表。之后只需要对另一个数据集（"外层"或"探测端"）里的每一行，同样计算一次哈希值，直接定位到对应的桶，再在桶内做少量比较即可判断是否匹配——平均查找复杂度接近 O(1)，和数据总量基本无关，这正是哈希连接相对嵌套循环的核心优势所在。
整个过程分两个阶段：
- 构建阶段（build）：读取内层（构建端）的全部数据，对每一行按连接键计算哈希，分发进哈希表；
- 探测阶段（probe）：读取外层（探测端）的每一行，计算哈希，去哈希表里查找匹配的桶，核实匹配后输出连接结果。
单趟哈希连接：一切都在内存里
如果整张哈希表能完整放进可用内存（受 work_mem × hash_mem_multiplier 限制，hash_mem_multiplier 默认值为 1.0，即默认情况下哈希相关操作和其它 work_mem 消费者用的是同一个额度），那么构建阶段一次性把内层数据全部读入内存建表，探测阶段只需一遍扫过外层数据即可完成整个连接，这称为单趟（single-pass）哈希连接，是最理想的情况。
两趟（多批次）哈希连接：内存不够时的分区策略
当构建端数据量超过可用内存、哈希表放不下时，PostgreSQL 会启用分批（batch）机制：先把内层数据按哈希值的另一维度（不同于桶的划分维度）切分成若干个批次（batch），只有第一批数据会被建成内存中的哈希表参与本轮探测，其余批次的数据先落盘（写入临时文件）暂存。接着，外层数据同样按相同的分批规则被分流——第一批外层数据立即和内存中第一批内层哈希表做探测，其余批次的外层数据也暂存到磁盘。等第一批处理完，再依次把第二批、第三批……内层数据读回内存重新建表，配合对应批次的外层数据完成探测，如此循环直到所有批次处理完毕。
这个过程本质上是要额外付出磁盘写入和再次读取的代价（体现在代价公式里会用到 seq_page_cost），但相比于完全没有索引可用时退化成的嵌套循环，多批次哈希连接的整体复杂度依然优于简单的逐行比对方式。
关键参数
work_mem：单个哈希表（以及排序等其它需要缓冲的操作）能使用的基础内存额度；hash_mem_multiplier：专门给哈希相关操作（哈希连接、哈希聚合）在work_mem基础上乘以的系数，默认为 1.0，如果调大就相当于允许哈希操作比其它work_mem消费者用更多内存而不必影响全局的work_mem；temp_file_limit：单个会话允许使用的临时文件总大小上限，超过会报错，是防止某个失控查询把磁盘写满的保护阀；seq_page_cost、cpu_operator_cost、cpu_tuple_cost：延续前几篇的通用代价参数，分别对应顺序 I/O、每次哈希/比较运算、每行处理的开销，在哈希连接的代价公式里都会用到。
代价估算的构成
启动代价（startup cost）主要来自构建阶段：把内层数据全部取出来的代价，加上为每一行计算哈希函数的 CPU 代价，再加上外层数据源自身的启动代价（外层要开始探测前，构建端必须先完全建好表，所以构建端的代价基本上都算进启动代价里）。总代价（total cost）在此基础上叠加探测阶段的开销：为外层每一行计算哈希、在桶内做实际比较（要考虑哈希冲突带来的额外比较）、以及构造和输出匹配行的代价。如果触发了多批次模式，还要按落盘、回读的页数乘以 seq_page_cost 追加相应的磁盘 I/O 代价。
并行哈希连接
并行哈希连接（Parallel Hash Join，PostgreSQL 11+）
多个并行 worker 不再各自维护独立的哈希表，而是共同构建一张共享哈希表，存放在共享内存里。这样做的好处是：所有 worker 的内存额度是"合并"计算的，单张共享表能装下更大的内层数据集，相比"每个 worker 各自建一份完整哈希表"的朴素并行方案，显著提高了整体命中单趟（不需要落盘分批）模式的概率，也避免了内存的重复浪费。
并行两趟哈希连接
如果共享哈希表依然放不下全部内层数据，同样要走分批策略：每个 worker 在共享内存中维护自己那部分批次的独立哈希表，各自处理被分配到的分区，worker 之间通过动态的工作分配机制协调进度，尽量做到负载均衡，避免个别 worker 因为数据倾斜而拖慢整体进度。
哈希聚合（HashAggregate）
同样的哈希表思想被复用在 GROUP BY、DISTINCT、UNION（去重版本）等需要"按某个键分组/去重"的操作上：HashAggregate 节点会为每一个不同的分组键在哈希表里维护一条记录（分组键本身 + 该分组的聚合状态，如累加和、计数等），逐行扫描输入、计算分组键的哈希、定位到对应桶、更新聚合状态。当分组数量很多、哈希表本身超出内存限制时，同样会触发类似哈希连接的分批落盘机制，把部分分组的中间状态暂存到磁盘，分批次迭代处理。
面向哈希连接/聚合的一些实践建议
- 只保留查询真正需要的列：参与哈希表构建的每一行都会被暂存在内存（或磁盘）里，无用的列会直接放大哈希表占用的空间，进而增加触发多批次的概率；
- 尽量让构建端（内层）是较小的数据集：哈希表的大小直接取决于构建端的数据量，选择较小的一侧作为构建端能让哈希表更容易完全放进内存，这一点优化器通常会自动判断，但了解这个原理有助于理解为什么某些查询改写（比如提前过滤掉不必要的行）能显著改善哈希连接的表现；
- 值分布不均匀（数据倾斜）会带来额外挑战：如果某个键值对应的行数远超其它键值，对应的桶会异常庞大，可能需要动态调整分区策略（重新分批）来应对，这类场景下单纯依赖默认参数往往难以达到理想效果；
- 并行哈希通常优于多个各自独立维护小哈希表的方案：对于数据量较大的场景，倾向于让优化器选用共享哈希表的并行哈希连接，而不是人为限制并行度导致退化成多份独立小表。
小结
哈希连接把等值连接的查找复杂度从"逐行比较"降到接近常数级别的哈希查找，核心在于构建阶段先把（通常较小的）一侧建成哈希表，探测阶段对另一侧逐行计算哈希去匹配。当哈希表能完全放进 work_mem × hash_mem_multiplier 划定的内存额度时，是理想的单趟模式；放不下时会退化为多批次模式，用磁盘临时文件暂存溢出的批次，代价随之上升但仍优于无索引场景下的嵌套循环。PostgreSQL 11 起的并行哈希连接通过让多个 worker 共享同一张哈希表，进一步提高了单趟命中率和整体吞吐。同样的哈希表思路被复用在 HashAggregate 节点上，服务于 GROUP BY/DISTINCT/UNION 等分组去重操作。哈希连接的限制在于只适用于等值连接，且需要预先付出构建哈希表的启动成本，这也是为什么它更适合处理量级较大、缺乏合适索引的等值连接场景。下一篇文章将介绍第三种连接算法——归并连接，以及支撑它的排序机制。