前言写过 SQL 的人多半都遇到过这么个怪事两张同样的表JOIN 条件也一样有时候唰一下就出结果有时候却慢得像在熬一锅老汤。奇怪的是问题往往不在索引也不在数据量而在一件被很多人忽略的事——数据库到底用哪种算法把两张表拼到了一起。表连接JOIN是关系型数据库里最重的活儿之一。一条多表查询的执行计划连接方式选对了可能快上几十倍选错了索引加得再多也白搭。这也是为什么主流数据库几乎都内置了好几种连接算法——没有哪一种是万能的每种都只擅长某一类场景。目前主流关系型数据库在物理执行层面一般会提供三种连接实现嵌套循环连接NestLoop、归并连接MergeJoin、哈希连接HashJoin。这篇就来把这三者的原理、代价模型和选型逻辑一次性讲清楚。这里写目录标题前言一、先说清楚连接算法到底在解决什么问题二、嵌套循环连接NestLoop2.1 基本嵌套循环最直白的双层循环2.2 物化嵌套循环别一遍遍扫内表2.3 索引嵌套循环让索引帮你精准点穴2.4 NestLoop 小结三、归并连接MergeJoin3.1 原理先排好序再归并3.2 物化归并与落盘那个坑3.3 MergeJoin 小结四、哈希连接HashJoin4.1 原理先建表再探测4.2 内存的边界work_mem 与分批4.3 HashJoin 小结五、三种连接算法对比与选型5.1 核心对比5.2 选型决策路径5.3 如何干预连接方式的选择六、总结一、先说清楚连接算法到底在解决什么问题不管你的 SQL 写得多花哨两表连接的本质就一句话给定外表驱动表和内表被驱动表找出所有满足连接条件的元组对。打个比方。假设外表有 n 行、内表有 m 行最朴素的办法就是双层 for 循环——外表每取一行就和内表的每一行都比一遍。这就是 NestLoop 的雏形。听起来简单问题也明显比一遍意味着要做 n×m 次比较数据一多就扛不住。于是数据库又想出了两种更聪明的办法MergeJoin 借助排序HashJoin 借助哈希表。理解了这一点后面的三种算法本质上就是对同一个问题——“怎么少比几次”——给出的三种不同回答。二、嵌套循环连接NestLoopNestLoop 是最基础、也最通用的连接算法。它的内核就是那个双层 for 循环但在工程实现上又长出了三种模样基本嵌套循环、物化嵌套循环、索引嵌套循环。2.1 基本嵌套循环最直白的双层循环基本嵌套循环的逻辑一句话就能说明白外层表每次拿出一条元组和内层表的每一条逐一比较满足条件就拼成结果输出。它的适用场景也很明确内外表数据量都不大或者内表很小、外表很大。从理论上看连接操作主要吃 CPU所以基本 NestLoop 的代价大致可以这么估代价 ≈ 扫描外表的代价 扫描内表的代价不过这只是扫一次的账。外表有 n 行、内表有 m 行时内表实际上会被反复扫 n 次总比较次数是n × m。这恰恰是 NestLoop 的软肋——数据量一上来n×m 就会像滚雪球一样爆炸。下面这段示例把这个过程跑了一遍建两张各 100 万行的表再用where把参与连接的数据压到极小逼优化器选 NestLoop。-- 准备数据两张各 100 万行的表createtablet1(aint);createtablet2(aint);insertintot1values(generate_series(1,1000000));insertintot2values(generate_series(1,1000000));setmax_parallel_workers_per_gather0;-- 关掉并行排除干扰explainanalyzeselect*fromt1joint2ont1.at2.awheret1.a10andt2.a1;执行计划长这样Nested Loop (cost0.00..36350.01 rows1 width8) (actual time0.057..286.687 rows1 loops1) - Seq Scan on t1 (cost0.00..19425.00 rows1 width4) Filter: ((a 10) AND (a 1)) Rows Removed by Filter: 999999 - Seq Scan on t2 (cost0.00..16925.00 rows1 width4) Filter: (a 1) Rows Removed by Filter: 999999这里 t1 做外表循环、t2 做内表被反复扫描。看actual time整体接近 286ms——基本 NestLoop 扛到这个量级已经开始喘了。一个常被忽略的点NestLoop 是三种算法里唯一能处理非等值连接比如t1.a t2.a、t1.a t2.a的。排序和哈希都依赖相等这个概念只有循环比较能搞定大于“小于”。所以非等值连接的查询你基本只能在计划里看到 Nested Loop。想验证的话把连接条件换成不等explainanalyzeselect*fromt1joint2ont1.at2.awheret1.a5andt2.a5;这种条件下无论你怎么调开关优化器也只能老老实实走 NestLoop。2.2 物化嵌套循环别一遍遍扫内表基本 NestLoop 最大的毛病是每来一条外表记录都要把内表从头到尾扫一遍。内表一大这个反复全表扫描就贵得离谱。物化嵌套循环Materialized NestLoop就是来治这个毛病的。它的思路是先把内表一次性扫出来存进内存work_mem或临时文件往后外表每来一条记录直接拿这份物化好的内表去比再也不用回头走缓冲区管理器去反复全表扫。尤其内表能整个塞进 work_mem 时提速非常明显。适用场景就一条内表会被反复访问。把上例的过滤条件放宽一点就能在计划里看到Materialize节点explainanalyzeselect*fromt1joint2ont1.at2.awheret1.a100andt2.a100;Nested Loop (cost0.00..34000.25 rows1 width8) (actual time0.091..289.167 rows99 loops1) Join Filter: (t1.a t2.a) Rows Removed by Join Filter: 9702 - Seq Scan on t1 (cost0.00..16925.00 rows100 width4) Filter: (a 100) - Materialize (cost0.00..16925.50 rows100 width4) (actual time0.000..1.741 rows99 loops99) - Seq Scan on t2 (cost0.00..16925.00 rows100 width4) Filter: (a 100)注意Materialize那行的loops99——内表被访问了 99 次。但因为早就物化进了内存每次耗时只有零点几毫秒比反复全表扫划算太多。2.3 索引嵌套循环让索引帮你精准点穴物化是把内表缓存起来索引嵌套循环Index NestLoop则换了个思路如果内表在连接键上有可用索引就别全表扫了直接用索引把匹配的那几条揪出来。虽然名字里还挂着嵌套循环但内表查找的代价已经从 O(m) 掉到了 O(log m)、甚至接近 O(1)外表也只需要循环一遍。所以索引嵌套循环往往是 NestLoop 家族里跑得最快的一种。适用场景外表不大内表连接键能命中索引。代价模型也随之变了代价 ≈ 扫描外表代价 用索引扫内表代价通常远小于全表扫给 t2 建个索引再看createindexont2(a);explainanalyzeselect*fromt1joint2ont1.at2.awheret1.a100andt2.a10;Nested Loop (cost0.42..16947.10 rows1 width8) (actual time0.049..171.314 rows9 loops1) Join Filter: (t1.a t2.a) - Seq Scan on t1 (cost0.00..16925.00 rows100 width4) Filter: (a 100) - Materialize (cost0.42..8.63 rows9 width4) - Index Only Scan using t2_a_idx on t2 (cost0.42..8.58 rows9 width4) Index Cond: (a 10) Heap Fetches: 9内表这次走的是Index Only Scan每次都靠索引精准定位省掉了全表扫的高昂代价。这也解释了一条经典经验小表驱动大表再让大表的连接键挂上索引往往就是最高效的连接姿势。2.4 NestLoop 小结一句话记住 NestLoop最通用什么连接条件都能啃包括非等值但代价和数据量的乘积牢牢绑在一起。它真正发光的时刻是数据量小或者能用索引把内表查找代价压下来的时候。三、归并连接MergeJoinNestLoop 的痛在 n×m。MergeJoin 给出的解法是要是两边都排好序就不用两两比了可以齐头并进地归并。3.1 原理先排好序再归并归并连接的步骤清晰得像教科书把每个表的数据按连接键排好序分别读入两个表的元组取两边最小的元组来匹配再取次小的匹配依此类推直到做完。因为是排好序的两边各扫一遍就能拼完时间复杂度从 n×m 一下降到O(nm)前提是已经有序。这是 MergeJoin 最迷人的地方。但天下没有白吃的午餐它有两个硬约束只能用于等值连接和自然连接非等值没法靠排序归并要求内外表都有序。好在如果表上有索引索引本身就是有序的就不用再排只有一个有索引就只排另一个两个都有皆大欢喜都不用排。适用场景两个表的数据都基本有序两表能走索引或者至少外表能走索引。代价模型代价 ≈ 扫描外表 扫描内表 外表排序 内表排序也就是说排序的开销得算进总账。数据要是天然无序又没索引排序本身就是一笔不小的花费。下面这个例子用order by强制 t1 有序看看 MergeJoin 的计划analyze;setmax_parallel_workers_per_gather0;explainanalyzeselect*fromt1joint2ont1.at2.awheret1.a100andt2.a10orderbyt1.a;Merge Join (cost33856.66..33857.67 rows1 width12) (actual time276.471..276.478 rows10 loops1) Merge Cond: (t1.a t2.a) - Sort (cost16928.32..16928.57 rows100 width4) Sort Key: t1.a Sort Method: quicksort Memory: 29kB - Seq Scan on t1 ... - Sort (cost16928.33..16928.58 rows100 width4) Sort Key: t2.a Sort Method: quicksort Memory: 25kB - Seq Scan on t2 ...计划里冒出两个Sort节点分别给 t1、t2 排完序再归并。数据量小、装得进内存时用的是quicksort飞快。顺手的好处如果你这条 SQL 本来就要ORDER BY而 MergeJoin 恰好按同样的键排好了那外层就省掉一次额外的排序——一次连接顺便把最终结果也排好了可谓一鱼两吃。3.2 物化归并与落盘那个坑跟 NestLoop 一样MergeJoin 也支持物化归并连接把内表排好序的结果物化下来让内表扫描更省事。不过这里更要盯紧的是排序的内存边界。排序和归并都得吃 work_mem 这块工作内存待排序的数据一旦塞不下数据库就会落盘走外排external merge代价肉眼可见地往上蹿。看这个大数据量的例子explainanalyzeselect*fromt1joint2ont1.at2.a;Merge Join (cost255514.69..278014.69 rows1000000 width8) (actual time380.418..910.112 ...) Merge Cond: (t1.a t2.a) - Sort (cost127757.34..130257.34 rows1000000 width4) Sort Key: t1.a Sort Method: external merge Disk: 13736kB -- 落盘了 - Seq Scan on t1 ... - Materialize (cost127757.34..132757.34 rows1000000 width4) - Sort (cost127757.34..130257.34 rows1000000 width4) Sort Key: t2.a Sort Method: external merge Disk: 13736kB -- 落盘了 - Seq Scan on t2 ...盯住Sort Method: external merge Disk: 13736kB这行——排序数据撑爆了 work_mem只能写临时文件。一旦在计划里看到落盘往往就是 MergeJoin 拖慢的信号这时要么调大 work_mem要么干脆换一种连接方式。3.3 MergeJoin 小结记住 MergeJoin 的关键词等值连接、有序、O(nm)、怕落盘。它最擅长数据天然有序或能走索引的场景配上 ORDER BY 还能顺手把结果排好省一次排序。四、哈希连接HashJoinHashJoin 拿哈希表这个数据结构给出了第三种答案先给内表建一张哈希表再让外表的每条记录去这张表里探测。跟 MergeJoin 一样HashJoin只能用于等值连接和自然连接——道理很简单只有相等才能用哈希来定位。4.1 原理先建表再探测HashJoin 的执行分成两个清清楚楚的阶段构建阶段Build扫一遍内表所有元组对连接键做哈希把它们塞进各自的哈希桶bucket探测阶段Probe逐行扫外表对每条记录的连接键做同样的哈希看它该落进哪个桶再跟桶里的内表记录比一比对得上就拼成结果。浓缩成三步就是给内表建哈希表把数据分发到各个桶里一行行扫外表做哈希确定它属于哪个桶跟那个桶里的内表数据做连接。外表每条记录只需要跟同一个桶里的少数内表记录比而不是跟全部内表比——这正是它比 NestLoop 快的根本原因。适用场景数据分布随机、无序且重复值不是特别多。大表之间的等值连接最常落到它头上。代价模型代价 ≈ 内表建哈希的代价 外表元组数 n × 内表元组数 m × 选择率× 单元组 CPU 耗时这里的选择率selectivity反映了哈希碰撞、桶内实际需要比较的比例是 HashJoin 代价里的关键变量。来看个典型的 HashJoin 计划analyze;setmax_parallel_workers_per_gather0;-- 相比前文 nestloop 的例子这里把数据量放大explainanalyzeselect*fromt1joint2ont1.at2.awheret1.a1000andt2.a100;Hash Join (cost16926.26..33855.03 rows1 width8) (actual time174.828..285.586 rows100 loops1) Hash Cond: (t1.a t2.a) - Seq Scan on t1 (cost0.00..16925.00 rows1002 width4) Filter: (a 1000) - Hash (cost16925.01..16925.01 rows100 width4) Buckets: 1024 Batches: 1 Memory Usage: 12kB - Seq Scan on t2 (cost0.00..16925.01 rows100 width4) Filter: (a 100)重点看Hash节点下面那行Buckets: 1024哈希桶数量、Batches: 1批次数量、Memory Usage: 12kB内存占用。Batches: 1说明整张哈希表一次就装进了内存这是最理想的状态。4.2 内存的边界work_mem 与分批哈希表也得占内存同样受 work_mem 管着。内表太大、一次哈希塞不下时数据库会把哈希表切成多个批次Batch先把数据写临时文件再一批批读回内存处理。Batches一旦大于 1就意味着哈希也落盘了性能跟着打折。所以调优 HashJoin 时有个常见动作——看 Batches 是不是大于 1。如果是且内存还宽裕就适当调大 work_mem争取让它退回Batches: 1-- 假设默认 work_mem 偏小导致 HashJoin 出现 Batches 1setwork_mem64MB;explainanalyzeselect*fromt1joint2ont1.at2.a;-- 调大后Hash 节点里 Batches 往往能从多批退回 1 批临时文件消失不过得特别提醒一句work_mem 是单个操作的内存额度不是全局总量。一条复杂查询可能同时跑好几个排序或哈希ORDER BY、DISTINCT、MergeJoin 用排序HashJoin、哈希聚集、基于哈希的 IN 子查询用哈希每个都会各占一份 work_mem。把它调得过大得防着并发会话一起来时总内存被撑爆。4.3 HashJoin 小结HashJoin 的关键词是等值连接、建表探测、怕落盘Batches1、适合大表无序数据。在大多数大表等值连接的场景里它通常是优化器的默认心头好。五、三种连接算法对比与选型原理讲完了回到最实用的问题到底该用哪种先上一张对比表把核心特征拉平了看。5.1 核心对比维度NestLoopMergeJoinHashJoin支持的连接条件任意含非等值仅等值/自然连接仅等值/自然连接时间复杂度O(n × m)O(n m)需先有序接近 O(n m)依赖哈希分布是否要求有序否是或用索引替代否是否需要额外内存较少物化时用 work_mem排序用 work_mem建哈希表用 work_mem典型落盘点n×m 过大排序数据落盘哈希表分批落盘最适合的场景小数据量小表驱动大表内表有索引数据天然有序/有索引结果还需排序大表等值连接数据无序、重复值不多5.2 选型决策路径实际选型不是拍脑袋可以顺着下面这条路径一步步想先看连接条件是不是等值。非等值、、!只有 NestLoop 一条路没得选。再看数据量。两边都小或一边很小优先 NestLoop——尤其内表连接键有索引时索引嵌套循环常常就是最优解。接着看是否有序。数据天然有序带主键、有索引、按时间追加等又是等值连接MergeJoin 几乎白捡一个有序优势查询本身还要ORDER BY的话MergeJoin 还能一鱼两吃。最后看数据分布。大表、无序、等值、重复值不多——这是 HashJoin 的主场也是大数据量下优化器最常选的方案。总结成一句口诀小数据靠 NestLoop 索引有序数据靠 MergeJoin大数据无序靠 HashJoin。5.3 如何干预连接方式的选择正常情况下优化器会基于代价估算自动挑出它认为最优的连接方式。可一旦统计信息不准、数据分布特殊优化器也会看走眼。这时候有两条路可以人工插手。第一条是连接类开关。每种算法都配了一个开关-- 允许 / 禁止使用某种连接方式setenable_nestloopoff;-- 数据量很小时才更该开setenable_hashjoinoff;-- 数据随机分布时更合适setenable_mergejoinoff;-- 内外表基本有序时更合适有个坑得提前说这些开关不是绝对禁止而是把对应算法的代价估到天上去让它尽量不被选中——真到了别无选择的地步数据库该用还是会用。所以与其全局改开关、拖累所有 SQL不如用 HINT 只对单条 SQL 精确控制把影响圈到最小。我们可以做个对照实验直观感受开关的效果。同一条大表等值连接默认走 HashJoinexplainselect*fromt1joint2ont1.at2.awheret1.a1000andt2.a100;-- 默认Hash Join把 HashJoin 和 MergeJoin 都关掉逼优化器改走 NestLoopsetenable_hashjoinoff;setenable_mergejoinoff;explainselect*fromt1joint2ont1.at2.awheret1.a1000andt2.a100;-- 此时会看到 Nested Loop第二条是 HINT。当优化器因为代价估算偏差多条件、多表连接、相关子查询等选错计划时可以在 SQL 里用 HINT 直接点名连接方式和驱动表比如指定走 HashJoin、或指定让某张小表当驱动表。HINT 的具体语法因数据库而异但用的时候记住一条核心原则只在优化器确实选错时才出手而且尽量只作用于出问题的那一条 SQL。此外三种连接在并行查询下都能再上一层楼。比如并行 HashJoin会先在小表上建好哈希再并行扫描大表做探测并行 NestLoop 则常常配合内表索引扫描来提速。开启并行后原本串行的连接能更好地榨干多核——当然前提是数据量够大不然并行的协调开销反而得不偿失。六、总结回到开头那个为什么有时快、有时慢的疑问——答案十有八九就藏在连接算法里。NestLoop是最通用的兜底选手什么连接都能接但代价跟 n×m 死死绑定真正强在小数据量以及小表驱动大表内表有索引的场景MergeJoin用排序换来 O(nm) 的优雅前提是等值连接加有序数据特别适合天然有序或最终还要排序的查询但要提防排序落盘HashJoin靠哈希表扛下大表等值连接是大表无序数据下的主力最怕哈希表分批落盘。归根结底一句话没有绝对最优的连接算法只有最适合当下数据分布和访问模式的那一种。看懂执行计划里那个Nested Loop/Merge Join/Hash Join节点搞清它为什么被选中、有没有落盘、该不该换一种方式你就抓住了 SQL 调优里最关键的那根杠杆。下次再碰上慢查询不妨先EXPLAIN一下看看连接这一环用的是谁——说不定答案就明明白白摆在那儿。
