PostgreSQL Join 执行策略（Nested Loop、Hash Join、Merge Join）与 NOT EXISTS 优化

以集成数据压缩 SQL 优化为例，用大白话讲清楚 Nested Loop、Hash Join、Merge Join 三种执行策略。

一、背景：一条慢 SQL 引发的思考

在对上游下发数据做压缩时，有这样一条 UPDATE SQL：

-- ❌ 原始写法UPDATEmagellan_nk_order_inboundSETversion_number=CONCAT(version_number,'_zip')WHEREversion_number='20260521172049432'ANDorde_idIN(SELECTa.orde_idFROMmagellan_nk_order_inbound aLEFTJOINmagellan_nk_order_inbound bONb.version_number='20260522000707011'ANDa.orde_id=b.orde_idWHEREa.version_number='20260521172049432'ANDb.orde_idISNULL);

这张表有几千万行数据，跑起来非常慢。问题根源就在于 PostgreSQL 对IN (子查询)选择了Nested Loop执行策略。

二、先搞清楚 N 和 M 是什么

后面讲复杂度时会用到 N 和 M，先把它们定义清楚：

三、三种 Join 执行策略

3.1 Nested Loop（嵌套循环）

原理

就是两层 for 循环，外表每扫一行，都去完整扫描一遍内表：

for 外表每一行 a: ← 循环 N 次 for 内表每一行 b: ← 循环 M 次 if a.id == b.id: 匹配！

时间复杂度

O(N × M)

举例：N = 500万，M = 500万

500万 × 500万 = 25,000,000,000,000 次（25万亿次比较）💀

即使内表有索引，内层变成二分查找，也是O(N × logM)：

500万 × log(500万) ≈ 500万 × 23 ≈ 1.15亿次

比无索引好得多，但数据量越大越吃力。

适用场景

• 外表结果集非常小（几十行、几百行）
• 内表在 Join Key 上有索引

一句话总结

数据量小时很快，数据量大时是灾难。

3.2 Hash Join（哈希连接）

原理

分两个阶段，可以理解为"先建字典，再查字典"：

第一阶段 —— Build（建字典）：
把小表的 Join Key 全部装进一个 HashMap（哈希表）：

HashMap = { id_001: true, id_002: true, id_003: true, ... }

这一步扫描内表一次，共M 次操作。

第二阶段 —— Probe（查字典）：
遍历外表每一行，拿 Join Key 去 HashMap 里查，HashMap 查询是 O(1)：

for 外表每一行 a: if a.id 在 HashMap 里？ ← O(1) 查询 匹配！

这一步扫描外表一次，共N 次操作。

时间复杂度

O(N + M)

举例：N = 500万，M = 500万

500万 + 500万 = 1000万次操作 ✅

与 Nested Loop 的25万亿次相比，快了约 250万倍。

适用场景

• 两张表数据量都较大
• Join Key 上没有合适索引
• 内存足够装下小表的 HashMap

一句话总结

大表 Join 的首选策略，用内存换时间。

3.3 Merge Join（归并连接）

原理

和归并排序思路一样，要求两张表都按 Join Key事先排好序，然后像拉链一样合并：

表A（已排序）: 1, 3, 5, 7, 9 表B（已排序）: 2, 3, 6, 7, 8 双指针同时移动，遇到相同值就匹配： A=1, B=2 → A前进 A=3, B=3 → 匹配！双方前进 A=5, B=6 → A前进 ...

时间复杂度

O(N + M) （不含排序开销） 如果需要临时排序：O(N·logN + M·logM)

适用场景

• 两张表在 Join Key 上都有排序索引（B-Tree 索引本身就是有序的）
• 大范围扫描场景

一句话总结

有序数据的最优解，依赖索引排序。

四、三种策略横向对比

五、为什么 NOT EXISTS 更容易触发 Hash Anti Join

5.1 什么是 Anti Join（反连接）

普通 Join 是找"匹配的行"，Anti Join 是找"没有匹配的行"，对应 SQL 里的：

• NOT IN (子查询)
• NOT EXISTS (子查询)
• LEFT JOIN ... WHERE b.id IS NULL

这三种写法逻辑等价，但 PostgreSQL 规划器对它们的理解深度不同。

5.2 IN (子查询) 的问题

WHEREidIN(SELECTidFROM...)

PostgreSQL 在处理IN (子查询)时，早期版本会把它理解为：

"对外表每一行，去子查询里查一遍"

这天然就是 Nested Loop 的思维模式。虽然新版 PostgreSQL 会尝试把它转成 Hash Join，但受统计信息准确性影响，一旦估算行数偏差大，就可能选错策略。

5.3 NOT EXISTS 为什么更好

ANDNOTEXISTS(SELECT1FROM表BWHEREb.id=a.idANDb.version=#{newerBatch})

NOT EXISTS的语义对规划器来说更直接：

“把表B的数据建成 Hash 表，外表每一行去 Hash 表里查，没查到的就留下”

这正好就是Hash Anti Join的执行模式，规划器几乎不会选错。

5.4 三种等价写法的规划器友好度

-- 写法1：LEFT JOIN + IS NULL（最不友好）FROMaLEFTJOINbONa.id=b.idWHEREb.idISNULL-- 规划器需要推断"IS NULL 意味着没匹配"，统计信息偏差时容易走 Nested Loop-- 写法2：NOT IN（较不友好）WHEREa.idNOTIN(SELECTb.idFROMb)-- 还有 NULL 值陷阱：如果子查询结果包含 NULL，整个 NOT IN 结果为空！-- 规划器处理 NULL 语义时额外保守-- 写法3：NOT EXISTS（最友好）✅WHERENOTEXISTS(SELECT1FROMbWHEREb.id=a.id)-- 语义最明确，规划器直接映射为 Hash Anti Join-- 无 NULL 陷阱（子查询返回 NULL 行不影响结果）

六、本次优化对比

优化前

-- countOverlap：LEFT JOIN + IS NOT NULLSELECTCOUNT(a.orde_id)FROMmagellan_nk_order_inbound aLEFTJOINmagellan_nk_order_inbound bONb.version_number=#{newerBatch}ANDa.orde_id=b.orde_idWHEREa.version_number=#{olderBatch}ANDb.orde_idISNOTNULL-- ← 语义绕，规划器理解成本高-- updateZipBatchNumber：IN (子查询 + LEFT JOIN + IS NULL)WHEREversion_number=#{olderBatch}ANDorde_idIN(SELECTa.orde_idFROM...LEFTJOIN...WHEREb.idISNULL-- ← 双重绕弯)

优化后

-- countOverlap：改为 INNER JOIN，语义直接SELECTCOUNT(a.orde_id)FROMmagellan_nk_order_inbound aJOINmagellan_nk_order_inbound bONb.version_number=#{newerBatch}ANDa.orde_id=b.orde_idWHEREa.version_number=#{olderBatch}-- 规划器直接选 Hash Join ✅-- updateZipBatchNumber：改为 NOT EXISTSWHEREversion_number=#{olderBatch}ANDNOTEXISTS(SELECT1FROMmagellan_nk_order_inbound bWHEREb.version_number=#{newerBatch}ANDb.orde_id=magellan_nk_order_inbound.orde_id)-- 规划器直接选 Hash Anti Join ✅

七、额外加速：创建合适的索引

即使规划器选了 Hash Join，扫描version_number时如果没有索引还是要全表扫描。

推荐为压缩相关的表创建联合索引：

-- version_number 用于过滤批次，orde_id 用于 JoinCREATEINDEXidx_st_ver_ridONmagellan_nk_order_inbound(version_number,orde_id);

有了这个索引：

• 扫描version_number = #{olderBatch}直接走索引，跳过无关数据
• Hash Join 的 Build 阶段也能走索引快速定位新批次数据

八、总结

核心记忆：大表 Join 看 Hash Join，反连接用 NOT EXISTS，索引让 N 和 M 变小。