扩展：Hash Join 是如何连接两张表的

在查询优化器为什么会选错执行计划中，我们比较了两种取得上海用户订单的方式：先找用户，再借助订单索引逐个查找；或者先为用户建立哈希表，再扫描订单。后一种方式就是哈希连接（Hash Join）。

这里有一个值得继续讨论的问题：如果有 100 个用户与 100 万条订单，扫描全部订单以后，不是还要把每条订单与所有用户比较吗？为什么 Hash Join 不必进行 1 亿次配对检查？

回答这个问题，需要把一次连接拆开来看：怎样组织待查找的记录，怎样定位候选，以及怎样确认候选真的满足连接条件。本文先用几条用户与订单记录走完这个过程，再通过 PostgreSQL 18.3 的本地实验观察执行计划和内存不足时的分批处理。文中的小型哈希函数是教学模型，实际计划与实验数据会单独标明。

1. 扫描整张表，为什么不等于逐对比较

对于下面的查询，连接条件要求订单的 user_id 与用户的 id 相等：

SELECT o.id AS order_id, u.id AS user_id, u.name
FROM orders AS o
JOIN users AS u ON o.user_id = u.id
WHERE u.city = 'Shanghai';

假设筛选后有 100 个上海用户，订单表有 100 万行，每个用户恰好有 100 条订单。最终需要返回的是 1 万条匹配记录。

最直接的连接算法，是让每个用户检查全部订单。下面是伪代码：

for u in 上海用户:
    for o in 全部订单:
        if o.user_id == u.id:
            输出 o.id, u.id, u.name

这种朴素嵌套循环需要检查 100 × 1,000,000 = 100,000,000 个候选组合。即使订单已经在内存中、不必反复从磁盘读取，也仍然需要完成这些比较。这里的记录比较次数、页面访问次数与物理磁盘读取次数，是不同的工作量。

不过，连接需要找出所有匹配组合，并不要求执行器先生成所有可能的组合。 有效的数据结构可以直接缩小查找范围：

Nested Loop 表示为外层每条记录运行一次内层访问，内层可以是完整扫描，也可以是使用当前外层值进行的索引查找。Hash Join 则把一侧记录组织成哈希表，让另一侧按键查找。PostgreSQL 连接策略

因此，Hash Join 的问题变成了：扫描到一条订单时，怎样快速找到可能匹配的用户，而不遍历所有用户？

2. 一条订单怎样找到匹配用户

先把数据缩小。用户表里有四条记录：

订单表有六条记录：

查询仍然要求返回上海用户的订单。用户 400 不满足城市条件，因此订单 1004 和 1005 不应出现在结果中。

2.1 先构建可查找的用户集合

Hash Join 把用于建立哈希表的一侧称为构建侧（build side），把随后按键查找的一侧称为探测侧（probe side）。本例先筛选用户，把三个上海用户放入哈希表，再由订单探测这个表。

用于匹配的字段称为连接键（join key）。本例两侧的连接键分别是 u.id 和 o.user_id。哈希函数把连接键转换成一个数字，即哈希值（hash value），数据库再根据这个数字确定记录应放入哪个桶（bucket）。一个桶保存一组候选记录，可以把它理解为哈希表中的一个查找位置。

连接键 → 哈希值 → 桶的位置 → 桶内的候选记录

哈希表除了组织连接键，还要保留后续匹配与输出需要的信息。例如，本例需要返回 u.name，构建侧就需要使用户名称在匹配后仍然可用。它是本次查询执行过程中建立的结构，与提前创建在表上的持久化索引有不同的生命周期。

构建侧来自执行计划中的一个输入分支，不一定是完整的基表。本例来自城市过滤后的用户；其他查询中，它也可能来自另一个连接或聚合的结果。哪一侧用于构建由计划决定，不能仅根据 SQL 的书写顺序判断。

2.2 根据订单的连接键定位候选

构建完成后，执行器开始逐条处理订单。以订单 1001 为例，它的 user_id = 100，执行器对 100 使用兼容的哈希函数，确定要检查的桶，再从桶中寻找用户 100。

“兼容”意味着：按照连接条件判断为相等的两个值，必须得到相同的哈希值，才能被放到相应的查找位置。不同数据类型之间的等值连接，也需要满足这项要求。PostgreSQL 哈希函数与相等关系

对于本文的非空整数等值连接，单批处理过程可以用下面的伪代码表达。假设有 B 个桶，用取余说明桶号的计算：

# 构建：每条用户记录都保留，桶内允许有多条候选
for u in 上海用户:
    h = hash(u.id)
    buckets[h % B].append((h, u))

# 探测：每条订单只查对应的桶
for o in 全部订单:
    h = hash(o.user_id)
    for (saved_hash, u) in buckets[h % B]:
        if saved_hash == h and u.id == o.user_id:
            输出 o.id, u.id, u.name

这里也有内层循环，但它遍历的是当前桶中的候选。桶内候选较少时，就能避免让每条订单与全部用户逐一比较。

上述过程得到四条结果，下面仅为方便阅读按订单 id 展示；没有 ORDER BY 时，查询不保证返回顺序：

用户 100 可以先后匹配两条订单。每次匹配后，用户记录仍然保留在哈希表中，后续订单还可以继续查找它。

2.3 找到同一个桶，为什么还要检查连接键

哈希表中的桶数量有限，多个哈希值可能进入同一个桶；不同连接键也可能产生相同的哈希值。这两种情况都需要区分。

假设有 8 个桶，并刻意指定下面的哈希值：

这个模型专门用于演示冲突，不代表 PostgreSQL 对这些整数的实际计算结果，也不代表良好的数据分布。用户 400 已被城市条件过滤，不会进入构建侧；最后一行只用于说明它的订单将探测哪个桶。

订单 1001 的连接键是 100，哈希值为 25，于是进入桶 1。桶中的三个用户需要经过以下检查：

• 用户 200 的哈希值是 41，与 25 不同，可以直接排除。
• 用户 300 的哈希值也是 25，但连接键 300 != 100，仍然需要排除。
• 用户 100 的哈希值和实际连接键都匹配，可以输出结果。

哈希值相同只能说明记录值得继续检查，不能作为原始连接键相等的证明。 对于这里的等值连接，哈希值不同可以排除匹配；哈希值相同后，还要计算真正的相等条件。

PostgreSQL 18.3 的普通 Hash Join 桶扫描遵循这一过程：先比较保存的哈希值，再检查连接条件。上面的取余与候选列表是便于理解的模型；具体实现使用自己的桶号计算与记录组织方式。桶扫描实现 ExecScanHashBucket

2.4 冲突与重复键，需要不同的处理

前面的用户 id 是唯一键，一条订单最多匹配一个用户。但一般的连接并不总是如此。

假设另一张用户标签表有 (100, 'new') 和 (100, 'vip') 两条记录。订单 1001 按用户 id 与标签表连接时，两条标签都满足条件，应该输出两条结果。保存构建侧时就需要保留这两条记录，不能像只保存一个值的字典那样，用后一条覆盖前一条。

哈希冲突带来需要排除的候选，重复连接键则可能带来必须输出的真实组合。更换哈希函数或增加桶数可以改善部分冲突问题，却无法消除查询语义要求保留的匹配。

本文讨论的是普通 = 条件下的内连接。空值参与比较时有 SQL 的空值语义，外连接、半连接和反连接也有额外的输出规则。如果连接还包含其他条件，按哈希键找到的记录还需通过这些条件；仅有大小比较而没有可用于哈希匹配的等值条件时，不能直接使用本文的按键查找方式。

3. 快速查找需要付出什么代价

3.1 平均查找很快，需要桶内候选足够少

假设构建侧有 M 条记录、B 个桶，平均每桶记录数为 α = M / B，这个比例通常称为负载因子（load factor）。

在桶内遍历候选的简化模型中，如果记录分布均匀，定位桶并检查候选的平均工作量可以理解为 O(1 + α)。当桶的数量随数据规模适当增长，使 α 保持较小时，就得到常说的平均 O(1) 查找。它表示平均工作量不会随着整张表的规模线性增长，不表示每次恰好只比较一条记录。

例如，100 条记录分散到 128 个桶，全体桶平均只有约 0.78 条记录。很多桶可能为空，另一些桶有一条或几条记录。但如果大量记录集中到少数桶，或者桶的数量相对数据量过少，实际探测仍然可能检查许多候选。

3.2 结果规模也属于连接成本

设构建侧有 M 行、探测侧有 N 行，最终输出 K 行。在哈希分布合理、内存足够、没有大量被额外条件丢弃的候选时，Hash Join 的主要工作可以近似理解为：

构建哈希表     O(M)
扫描并探测     O(N)
输出匹配结果   O(K)
合计           O(M + N + K)

如果两个输入中所有记录的连接键都等于同一个值，结果就可能有 M × N 行。需要逐行返回这些明细时，无论使用哈希还是索引，都需要处理这些真实匹配。额外连接条件也可能使候选匹配数远大于最终输出数，此时不能只用 K 描述候选检查成本。

回到 100 个用户与 100 万条订单的例子，Hash Join 避免了大量无用配对，但仍然扫描了全部 100 万条订单。索引 Nested Loop 可以只取得那 1 万条匹配订单，因此不能仅凭“哈希查找平均 O(1)”就判断它更快。两种方式的输入访问范围、启动工作和页面访问方式也需要一起比较。

3.3 哈希表放不进内存时，怎样继续连接

构建哈希表需要保存连接和输出所需的数据，还要维护桶数组、记录链接等结构。空间取决于行数、保留的行宽和结构开销，不能只看输入有多少行。

构建侧全部驻留内存时，执行器可以在构建完成后直接探测。如果哈希表超过可用预算，就需要把工作分成多个批次（batch）。在串行分批哈希连接的基本过程中：

1. 根据哈希值将构建侧记录分配到批次，保留当前批次，把后续批次的记录写入临时文件。
2. 扫描探测侧，将属于当前批次的记录用于探测，把属于后续批次的记录保存到对应临时文件。
3. 依次加载后续批次的构建侧数据，再读取该批次的探测侧数据完成连接。

两侧采用相容的分配规则，因此相等的连接键会进入同一批次。无需为每个批次重新扫描整张原始订单表，但增加了临时文件读写；运行中再次分割过大的批次，还可能产生更多工作。PostgreSQL 18.3 的实现也会根据实际哈希表规模调整批次数，严重倾斜时并不能保证继续分批就一定能满足内存预算。分批哈希连接实现

桶用于缩小一次查找的候选范围，批次用于分阶段处理放不下的数据。 一个批次内部仍然有许多桶，两者不能互换理解。

PostgreSQL 的哈希操作内存预算涉及 work_mem × hash_mem_multiplier。它针对具体操作，不是整个查询或整个数据库的总内存上限；多个操作与会话并发时还会共同消耗内存。因此，增加内存预算可能减少分批工作，也需要结合并发与总体资源评估。PostgreSQL 操作内存配置

4. 回到执行计划，观察这些工作

4.1 Hash 与 Hash Join 分别对应什么

附录提供了前面六条订单的完整 SQL。为了观察指定算法，实验在事务内临时限制 Nested Loop 和 Merge Join，并关闭并行与 JIT；这只能用于研究 Hash Join 的执行行为，不能据此说明它是小数据上的最佳方案。

本地 PostgreSQL 18.3 的实际计划如下，只摘录与本文有关的字段：

Hash Join (actual rows=4.00 loops=1)
  Hash Cond: (o.user_id = u.id)
  -> Seq Scan on hj_orders o (actual rows=6.00 loops=1)
  -> Hash (actual rows=3.00 loops=1)
       Buckets: 1024  Batches: 1  Memory Usage: 9kB
       -> Seq Scan on hj_users u (actual rows=3.00 loops=1)
            Filter: (city = 'Shanghai'::text)
            Rows Removed by Filter: 1

Hash 下方的用户扫描读到四个用户，过滤掉一个，把三行交给 Hash 构建哈希表。Hash Join 再使用订单分支的六行进行探测，最终输出四行。PostgreSQL 的 Hash 节点以一次性构建哈希表的方式工作，这里的三行表示构建时处理的输入数量，不应理解成它像普通扫描节点一样逐行向父节点传递结果。

计划中的订单分支虽然显示在用户分支上方，产生连接结果前仍需要准备好构建侧的哈希表。计划树的排版表示父子关系，不能直接当作从上到下的时间顺序。PostgreSQL Hash Join 计划示例

这里的 Buckets: 1024 是实际桶数，与前面教学模型的 8 个桶不同。Batches: 1 表示没有分成多个批次处理；Memory Usage 是哈希表报告的峰值内存，不是整个查询的内存，也不是数据表的大小。

另外，Hash Cond 展示用于哈希匹配的相等条件；Join Filter 若存在，则表示还要在连接处检查的条件。Rows Removed by Join Filter 不能直接当成“哈希冲突次数”。普通 EXPLAIN 输出并不会列出每个桶里有哪些连接键，也没有直接给出上述每一种冲突的数量。

4.2 相同数据，不同内存预算

第二个实验把构建侧扩大到 5 万个用户，每个名称由 64 个字符组成；探测侧有 20 万条订单，每个用户恰好有四条。查询返回订单 id 和用户名称，因此名称需要保留在构建侧的哈希表中。

两次查询使用相同 SQL 和数据，固定 hash_mem_multiplier = 2，仅将事务内的 work_mem 从 512kB 改为 8MB。本次观察如下：

较小预算下，执行器分成八批，哈希表报告的峰值内存较小，却增加了临时文件读写。较大预算下，哈希表可以一次容纳构建侧，使用更多内存，并省去了本次观察中的分批临时文件工作。

这也说明，较小预算下的 Memory Usage 不能用来推断全部构建侧数据只需要 770kB；这里有一部分数据已经交给后续批次处理。

实验使用临时表，因此表自身的缓冲访问显示为 local hit/read。上表只比较 temp read/written，它记录排序、哈希等操作产生的临时工作文件访问，两者含义不同。这里的数值是块访问次数，不是行数或去重后的文件大小；连接根节点已包含子节点贡献，不应沿计划树重复相加。EXPLAIN 缓冲信息

具体桶数、批次数和内存用量可能随版本、统计和运行环境变化。这组实验验证的是分批处理与临时文件工作的关系，没有进行耗时基准测试。EXPLAIN ANALYZE 还包含观测开销，默认不向客户端发送原查询结果集，也不能代替应用响应时间。

从一条订单的查找过程回到执行计划，可以看到 Hash Join 减少无用比较的方式：先组织构建侧，再为探测侧的连接键定位少量候选，并用实际连接条件确认结果。它的收益与代价同时来自这个过程——哈希查找缩小了候选范围，构建、输入扫描、真实匹配输出以及必要的分批处理仍然需要完成。

附录：复现实验

下面的 SQL 在同一个连接内顺序执行，使用独立、可销毁的本地测试数据库。表均为临时表，配置使用 SET LOCAL，最后的 ROLLBACK 会撤销本次建表并恢复事务内设置。运行前确认没有同名临时表；示例不会删除或替换已有表。

BEGIN;
SET LOCAL jit = off;
SET LOCAL max_parallel_workers_per_gather = 0;
SET LOCAL enable_nestloop = off;
SET LOCAL enable_mergejoin = off;
SET LOCAL hash_mem_multiplier = 2;

CREATE TEMP TABLE hj_users (
  id integer PRIMARY KEY,
  name text NOT NULL,
  city text NOT NULL
);
CREATE TEMP TABLE hj_orders (
  id integer PRIMARY KEY,
  user_id integer NOT NULL
);
INSERT INTO hj_users VALUES
  (100, 'Guang', 'Shanghai'), (200, 'Greg', 'Shanghai'),
  (300, 'Alice', 'Shanghai'), (400, 'Grace', 'Beijing');
INSERT INTO hj_orders VALUES
  (1001, 100), (1002, 200), (1003, 100),
  (1004, 400), (1005, 400), (1006, 300);
ANALYZE hj_users;
ANALYZE hj_orders;

-- 加排序只为核对展示结果；下面的连接计划不包含这个排序。
SELECT o.id AS order_id, u.id AS user_id, u.name
FROM hj_orders o JOIN hj_users u ON o.user_id = u.id
WHERE u.city = 'Shanghai'
ORDER BY o.id;

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT o.id AS order_id, u.id AS user_id, u.name
FROM hj_orders o JOIN hj_users u ON o.user_id = u.id
WHERE u.city = 'Shanghai';

CREATE TEMP TABLE hj_users_big AS
SELECT i AS id, repeat('u', 64) AS name
FROM generate_series(1, 50000) s(i);
CREATE TEMP TABLE hj_orders_big AS
SELECT i AS id, (i % 50000) + 1 AS user_id
FROM generate_series(1, 200000) s(i);
ANALYZE hj_users_big;
ANALYZE hj_orders_big;

SET LOCAL work_mem = '512kB';
EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT o.id, u.name
FROM hj_orders_big o JOIN hj_users_big u ON o.user_id = u.id;

SET LOCAL work_mem = '8MB';
EXPLAIN (ANALYZE, BUFFERS, TIMING OFF)
SELECT o.id, u.name
FROM hj_orders_big o JOIN hj_users_big u ON o.user_id = u.id;
ROLLBACK;

参考资料

• PostgreSQL 18：Planner/Optimizer
• PostgreSQL 18：Using EXPLAIN
• PostgreSQL 18：EXPLAIN
• PostgreSQL 18：Resource Consumption
• PostgreSQL 18：Operator Classes and Operator Families
• PostgreSQL 18.3：nodeHash.c
• PostgreSQL 18.3：nodeHashjoin.c