用生活中最直观的例子彻底搞懂 Merge Join 是什么、为什么快、什么时候用。一、先从生活场景开始场景一两摞乱序试卷找同学期末考试老师手里有两摞试卷A 摞数学试卷500 份乱序堆放B 摞语文试卷500 份乱序堆放现在要找出同一个同学的两份试卷配成一对。笨办法Nested Loop拿起数学试卷第1份张三→ 翻遍500份语文找张三 → 找到 拿起数学试卷第2份李四→ 翻遍500份语文找李四 → 找到 ... 总共翻了500 × 500 25万次聪明办法先排序再合并Merge Join第一步把两摞试卷都按学号排好序001~500 第二步左手拿A摞右手拿B摞同时从第一份开始翻 左手001号, 右手001号 → 匹配配成一对两手同时往后翻一张 左手002号, 右手003号 → 左边小只翻左手 左手003号, 右手003号 → 匹配两手同时往后翻一张 左手004号, 右手005号 → 左边小只翻左手 ... 总共翻了500 500 1000次结论排完序之后各翻一遍就结束两摞试卷绝不回头。二、Merge Join 核心原理双指针扫描Merge Join 本质是对两个有序序列用双指针做合并规则非常简单指针A → [1, 3, 5, 7, 9] 指针B → [2, 3, 6, 7, 8] 规则 A B → 匹配两指针同时右移 A B → A指针右移 A B → B指针右移 任意一方到头 → 结束逐步演示步骤1A1, B2 → 12A右移 步骤2A3, B2 → 32B右移 步骤3A3, B3 → 匹配✅ 双方右移 步骤4A5, B6 → 56A右移 步骤5A7, B6 → 76B右移 步骤6A7, B7 → 匹配✅ 双方右移 步骤7A9, B8 → 98B右移 步骤8A9, B结束 → 扫描结束 总步骤数8次远小于 5×525次两个序列各走一遍绝不回头这就是 O(NM) 的来源。三、时间复杂度分析3.1 有索引时O(N M)B-Tree 索引本身就是按 Key 排好序的有序结构。索引结构简化示意 key001 → 行指针 key002 → 行指针 key003 → 行指针 ...天然有序PostgreSQL 直接沿着两个索引做双指针扫描无需临时排序直接 O(NM)。3.2 无索引时O(N·logN M·logM)没有索引PostgreSQL 必须先把数据排序第一步对 N 行数据排序 → O(N·logN) 第二步对 M 行数据排序 → O(M·logM) 第三步双指针合并 → O(NM) 总计O(N·logN M·logM)举例N M 500万有索引500万 500万 1000万次操作 无索引500万×23 500万×23 1000万 ≈ 2.4亿次操作没有索引时代价远超 Hash Join规划器通常不会选 Merge Join。四、Merge Join vs Hash Join选哪个这是实际工作中最常见的疑问一张表说清楚对比项Hash JoinMerge Join需要排序❌ 不需要✅ 必须有序靠索引额外内存需要把小表装进 HashMap几乎为零只有两个指针有索引时不一定用索引直接复用索引O(NM)无索引时O(NM)照样快需先排序代价大内存不够时会写临时磁盘变慢不受内存限制规划器偏好通用首选有合适索引时才考虑一句话记忆没有索引 → Hash Join建字典O(NM) 有排序索引 → Merge Join双指针O(NM)且不占内存 内存紧张 → 优先 Merge Join不需要建 HashMap五、用 EXPLAIN 看规划器的选择EXPLAINANALYZESELECTa.orde_idFROMorders aJOINorders bONa.orde_idb.orde_idANDb.version_number20260522000707011WHEREa.version_number20260521172049432;执行计划输出示例-- 没有索引时规划器选 Hash Join Hash Join (cost...) Hash Cond: (a.orde_id b.orde_id) - Seq Scan on orders a (...) ← 全表扫描 - Hash - Seq Scan on orders b (...) ← 建 HashMap -- 有 (version_number, orde_id) 联合索引时规划器可能选 Merge Join Merge Join (cost...) Merge Cond: (a.orde_id b.orde_id) - Index Scan using idx_a on orders a (...) ← 走索引已有序 - Index Scan using idx_b on orders b (...) ← 走索引已有序看到Merge JoinIndex Scan的组合说明规划器充分利用了索引的有序性。六、什么情况下 Merge Join 会失效6.1 Join Key 数据类型不一致-- a.id 是 INTb.id 是 VARCHARONa.idb.id-- 需要隐式类型转换破坏有序性无法 Merge Join6.2 索引列被函数包裹ONLOWER(a.name)LOWER(b.name)-- 走不了索引无法 Merge Join6.3 非等值 JoinONa.priceb.price-- Merge Join 只支持等值连接6.4 数据分布极度不均匀某个 Key 值有几百万重复值低基数双指针在这个值上会反复扫描退化成 O(N×M)。七、总结Merge Join 的本质两个有序序列 双指针 各走一遍O(NM)什么时候 Merge Join 最好用✅ Join Key 上双方都有 B-Tree 索引 ✅ 内存资源紧张不想建 HashMap ✅ 大范围顺序扫描场景什么时候不要指望 Merge Join❌ 没有索引需临时排序代价大 ❌ 非等值 Join ❌ Join Key 被函数处理过 ❌ 数据低基数大量重复值三种策略终极对比Nested LoopHash JoinMerge Join比喻两层 for 循环建字典查字典双指针合并有序列表复杂度O(N × M)O(N M)O(N M)内存低中极低依赖索引内表需要不需要必须适合场景外表极小大表通用大表双方有索引核心记忆Merge Join 先排好序再双指针各走一遍。排序靠索引索引有了就免费索引没有就代价大。
