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

以集成数据压缩 SQL 优化为例用大白话讲清楚 Nested Loop、Hash Join、Merge Join 三种执行策略。一、背景一条慢 SQL 引发的思考在对上游下发数据做压缩时有这样一条 UPDATE SQL-- ❌ 原始写法UPDATEmagellan_nk_order_inboundSETversion_numberCONCAT(version_number,_zip)WHEREversion_number20260521172049432ANDorde_idIN(SELECTa.orde_idFROMmagellan_nk_order_inbound aLEFTJOINmagellan_nk_order_inbound bONb.version_number20260522000707011ANDa.orde_idb.orde_idWHEREa.version_number20260521172049432ANDb.orde_idISNULL);这张表有几千万行数据跑起来非常慢。问题根源就在于 PostgreSQL 对IN (子查询)选择了Nested Loop执行策略。二、先搞清楚 N 和 M 是什么后面讲复杂度时会用到 N 和 M先把它们定义清楚变量含义举例NJoin 左表外表过滤后的行数旧批次数据500 万行MJoin 右表内表过滤后的行数新批次数据500 万行三、三种 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 双指针同时移动遇到相同值就匹配 A1, B2 → A前进 A3, B3 → 匹配双方前进 A5, B6 → A前进 ...时间复杂度O(N M) 不含排序开销 如果需要临时排序O(N·logN M·logM)适用场景两张表在 Join Key 上都有排序索引B-Tree 索引本身就是有序的大范围扫描场景一句话总结有序数据的最优解依赖索引排序。四、三种策略横向对比对比项Nested LoopHash JoinMerge Join复杂度O(N × M)O(N M)O(N M)500万500万25万亿次 1000万次 ✅1000万次 ✅内存需求低中需装小表低是否需要索引内表最好有索引不需要需要排序索引最适合外表极小大表无索引 Join大表有排序索引最不适合两张大表 Join内存不够时无索引时五、为什么 NOT EXISTS 更容易触发 Hash Anti Join5.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.ida.idANDb.version#{newerBatch})NOT EXISTS的语义对规划器来说更直接“把表B的数据建成 Hash 表外表每一行去 Hash 表里查没查到的就留下”这正好就是Hash Anti Join的执行模式规划器几乎不会选错。5.4 三种等价写法的规划器友好度-- 写法1LEFT JOIN IS NULL最不友好FROMaLEFTJOINbONa.idb.idWHEREb.idISNULL-- 规划器需要推断IS NULL 意味着没匹配统计信息偏差时容易走 Nested Loop-- 写法2NOT IN较不友好WHEREa.idNOTIN(SELECTb.idFROMb)-- 还有 NULL 值陷阱如果子查询结果包含 NULL整个 NOT IN 结果为空-- 规划器处理 NULL 语义时额外保守-- 写法3NOT EXISTS最友好✅WHERENOTEXISTS(SELECT1FROMbWHEREb.ida.id)-- 语义最明确规划器直接映射为 Hash Anti Join-- 无 NULL 陷阱子查询返回 NULL 行不影响结果六、本次优化对比优化前-- countOverlapLEFT JOIN IS NOT NULLSELECTCOUNT(a.orde_id)FROMmagellan_nk_order_inbound aLEFTJOINmagellan_nk_order_inbound bONb.version_number#{newerBatch}ANDa.orde_idb.orde_idWHEREa.version_number#{olderBatch}ANDb.orde_idISNOTNULL-- ← 语义绕规划器理解成本高-- updateZipBatchNumberIN (子查询 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_idb.orde_idWHEREa.version_number#{olderBatch}-- 规划器直接选 Hash Join ✅-- updateZipBatchNumber改为 NOT EXISTSWHEREversion_number#{olderBatch}ANDNOTEXISTS(SELECT1FROMmagellan_nk_order_inbound bWHEREb.version_number#{newerBatch}ANDb.orde_idmagellan_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 阶段也能走索引快速定位新批次数据八、总结知识点结论Nested Loop 慢在哪两层循环复杂度 O(N×M)大表灾难Hash Join 为什么快建字典再查字典复杂度 O(NM)NOT EXISTS vs INNOT EXISTS 语义明确规划器直接选 Hash Anti JoinNOT EXISTS vs LEFT JOIN IS NULLNOT EXISTS 更简洁无 NULL 陷阱规划器更友好索引的作用减少参与 Join 的行数从源头降低 N 和 M核心记忆大表 Join 看 Hash Join反连接用 NOT EXISTS索引让 N 和 M 变小。