PostgreSQL 查询系列 — 7. 排序与归并连接
原文：https://habr.com/en/companies/postgrespro/articles/582058/ （作者 Egor Rogov，PostgresPro）
引言
这是"PostgreSQL 中的查询"系列的最后一篇，主题是第三种物理连接算法——归并连接（Merge Join），以及支撑它（同时也支撑很多其它操作，比如 ORDER BY、去重、分组）的排序机制。文章最后还对嵌套循环、哈希连接、归并连接三者做了一个横向对比总结，作为整个系列的收官。
归并连接的基本原理
归并连接要求参与连接的两个数据集都已经按连接键排好序（可以是提前排好序，比如来自索引扫描，也可以是执行时现场排序得到）。有了这个前提，连接过程就变成了经典的"双指针"合并算法：分别在两个有序集合上各维护一个指针，比较两个指针当前指向的键值——相等就输出这对匹配、并推进指针；不相等就把指向较小键值的那个指针向前移动一步。整个过程只需要对两个输入各扫描一遍（近似线性），不需要像哈希连接那样把任何一侧完整地缓冲进内存，因此内存占用非常小。
处理重复键值
如果外层指针当前的键值在内层里对应多条重复行（一对多或多对多的情况），算法需要把内层指针"倒回去"，重新定位到这一组重复键值的起始位置，把所有匹配的组合都输出完，然后再把外层指针推进到下一个不同的键值。这个"倒回去再重新遍历"的操作是归并连接处理重复值时必须要考虑的细节，也是它相对哈希连接在实现上更复杂的一点。
限制条件
归并连接只支持等值连接条件（和哈希连接一样），无法直接处理不等值的连接谓词；此外，全外连接和右外连接如果要用归并连接实现，往往需要额外保证某种输出顺序或者对未匹配行做专门处理，这类语义上的复杂度决定了归并连接在这些场景下要么不被选用，要么需要配合额外的排序步骤。
归并连接的代价估算
启动代价大致是两个子节点（分别对应两侧输入）代价中较小的那一个（因为归并连接可以边读边比较、不需要等一侧完全就绪才开始工作，这跟哈希连接"必须先把内层建完表"形成对比），再加上一个和两侧估算行数总和相关的、用于粗略估算"需要跳过多少不匹配区间"的 CPU 代价（乘以 cpu_operator_cost）。总代价则在此基础上叠加两侧子节点各自的总代价、按两侧行数总和计算的键值比较开销（同样按 cpu_operator_cost 计费），以及按最终连接结果行数计算的输出代价（cpu_tuple_cost）。
并行归并连接
在并行执行计划里，通常是外层（"external"，即驱动扫描那一侧）可以被拆给多个 worker 并行扫描，但每个 worker 内部依然要独立完整地扫描内层（"internal"）关系一遍来完成归并匹配——也就是说内层这一侧并不会被进一步在多个 worker 间拆分共享。和归并连接本身的限制类似，全外连接和右外连接在并行模式下同样不被支持。
排序：归并连接以及众多其它操作的基石
因为归并连接依赖两侧输入有序，如果数据本身不是天然有序的（比如没有走索引扫描），就需要先经过显式的排序节点。排序在 PostgreSQL 里是一个应用极广的基础设施，除了归并连接，ORDER BY、去重（DISTINCT）、部分分组聚合方式都可能依赖它，因此文章专门花了大篇幅讲排序算法本身根据输入规模、输出需求会在几种策略间切换。
快速排序（Quicksort）——数据能完全放进内存时
当待排序的数据总量不超过可用的 work_mem 时，PostgreSQL 直接在内存里用快速排序（经典 O(n log₂n) 复杂度）完成排序，这是最理想、最快的情形。
Top-N 堆排序——只需要前几名时
如果查询带有 LIMIT，且限制的结果集相对输入规模小得多（文章给出的经验判断标准大致是输出量不超过输入的一半，或者输入本身已经超出 work_mem 但最终输出结果能放进内存），PostgreSQL 会采用堆排序变种，只维护一个大小为 N（也就是 LIMIT 的数量）的堆，复杂度是 O(n log₂k)，其中 k 是最终需要的结果条数——比对全量数据做完整排序要划算得多，因为不需要维护和比较超出 N 之外的那部分排序信息。
外部归并排序（External Merge Sort）——数据超出内存时
当数据量超过 work_mem，PostgreSQL 会退化到基于磁盘的外部排序，大致分为几个步骤：
- 生成初始有序段（run）：分批把数据读进内存，每一批都能放进
work_mem，对这一批做内存内快速排序，排好后写出到磁盘上的一个临时文件，形成一个"有序段"；重复这个过程直到把整个输入都转换成若干个有序段； - 多路归并：同时打开多个（文章提到典型场景下大约 6 到 500 个）有序段对应的文件句柄，用类似归并连接双指针的思路做多路归并，把它们合并成更大的有序段；
- 可能需要多轮归并：如果初始生成的有序段数量超过一次多路归并能同时处理的文件数上限，需要分多轮逐步归并，直到只剩一个整体有序的结果；
- 延迟输出：很多时候最后一轮归并并不会立刻把结果物化到磁盘，而是等到上层节点真正来取数据时才现场归并输出，这样可以避免一次没必要的额外落盘。
外部排序在读取磁盘数据时会采用按块读取（每次读 32 页）的策略以减少 I/O 次数；其代价模型里区分了顺序 I/O 和随机 I/O 的比例，估算时大致按 75% 顺序、25% 随机的经验比例去组合 seq_page_cost 和 random_page_cost，反映出多路归并过程中读写模式介于纯顺序和纯随机之间的现实情况。
增量排序（Incremental Sort，PostgreSQL 13+）
这是一个专门针对"部分有序"输入的优化：假设排序需要按多个键（比如 ORDER BY a, b）排序，而输入数据已经天然按前面一部分键（比如 a）有序（典型来源是走了针对 a 列的索引扫描），那么完全没必要把整个数据集当成无序数据重新做一次全量排序——可以把输入按 a 的取值切成一个个"组"（每组内 a 值相同），只需要在每个组内部单独对剩下的键（这里是 b）做排序即可。
这样做的好处有两个：一是每组的数据量通常远小于整体数据量，排序所需内存大幅降低（甚至完全不需要落盘）；二是可以在处理完前面的组之后就开始把结果吐给上层，不必等到整个数据集排序完毕才能输出第一行，明显改善了启动延迟。它的代价估算会考虑预计的分组数量以及每组平均排序开销。
并行排序：Gather Merge
当排序被并行化时，每个 worker 各自对分配到的数据分片完成局部排序，最后由一个 Gather Merge 节点用类似多路归并的方式，把各个 worker 已经排好序的结果流合并成一个全局有序的结果——内部用二叉堆（binary heap）来维护"当前每个 worker 流的最前面一个元素里最小的是谁"。这个合并阶段的代价包括：parallel_setup_cost（启动并行的固定开销）、构建初始堆的开销、按结果行数乘以 parallel_tuple_cost × 1.05（worker 间传输数据，系数略高于普通的并行元组传输代价，可能是为了体现归并场景下额外的协调开销）、以及每次从堆顶弹出并重新调整堆结构所需的 cpu_operator_cost × log₂n（n 为 worker 数量）。
借助排序完成的去重与分组
Unique 节点
Unique 节点利用"输入已经排好序"这一前提，只需要单趟顺序扫描、比较相邻的两行是否相等即可完成去重——重复值在排序后必然彼此相邻，不需要哈希表也能保证正确性，实现非常轻量。
GroupAggregate 节点
类似地，GroupAggregate 依赖输入已按分组键排序，扫描过程中一旦发现分组键发生变化，就意味着上一个分组已经收集完所有成员，可以立即把这个分组的聚合结果吐出去，是一种流式、边读边算的处理方式，不需要像 HashAggregate 那样维护一张完整的哈希表。并行场景下对应 Partial GroupAggregate（各 worker 先在自己的分片上做局部分组聚合）和 Finalize GroupAggregate（协调进程把各 worker 的局部聚合结果再汇总合并）两阶段协作。
MixedAggregate：排序与哈希的混合策略
面对 GROUPING SETS（同一查询里需要按多套不同的分组维度分别聚合）这类复杂场景，如果严格用排序来实现，可能需要对同一份数据反复按不同键排序，代价很高；MixedAggregate 节点会把排序和哈希两种手段结合起来，对其中一部分分组维度用排序驱动、另一部分维度同时用哈希表处理，尽量在内存限制下用分层、多阶段的方式一次扫描完成尽可能多的分组计算，避免不必要的重复扫描。
三种连接算法的横向对比
文章在结尾给出了对嵌套循环、哈希连接、归并连接的整体比较，大致可以归纳为：
| 维度 | 嵌套循环 | 哈希连接 | 归并连接 |
|---|---|---|---|
| 复杂度特征 | 依赖内层访问效率，配合索引可接近线性，否则接近平方级 | 内存够用时接近线性 O(n)，需要分批落盘时退化为接近 O(n log n) | 输入已排序时接近线性 O(n)，需要额外排序时接近 O(n log n) |
| 内存占用 | 很小（除非用了 Materialize/Memoize 缓存） | 较高（要建哈希表） | 较低（双指针扫描，不需要缓冲整个数据集） |
| 出结果的时机 | 可以立刻边扫边输出第一条结果 | 必须先把构建端整个建完哈希表才能开始探测输出 | 只要两侧开始有序供给，就能较早输出结果 |
| 适用连接条件 | 任意条件（等值、不等值都可以） | 仅限等值连接 | 仅限等值连接，且要求可用 B-tree 操作符类（保证有序性） |
策略性结论：
- 嵌套循环在 OLTP 场景、驱动集合小且内层有高选择性索引可用时优势明显，能给出最快的首行响应；
- 哈希连接在 OLAP 类的大数据量等值连接、且内存足够（或分批代价可接受）时通常是最优选择；
- 归并连接是一种"平衡型"选项：如果两侧数据本来就已经有序（比如天然来自索引扫描），归并连接的代价会非常低，往往优于另外两种；但如果两侧都需要现场专门排序才能用归并连接，这份额外的排序开销通常会让它反而比哈希连接更贵——除非查询本身还要求结果保持有序输出（比如后面紧跟着
ORDER BY用的正好是同一个键），这种情况下"顺带"完成排序的归并连接才可能重新具备优势。
小结
本系列的最后一篇把排序和归并连接放在一起讲，是因为归并连接的效率高度依赖于输入是否已经有序，而排序算法本身（快速排序、Top-N 堆排序、外部归并排序、增量排序）决定了"让数据变得有序"这件事要付出多大代价。当输入能完全放进 work_mem 时用内存内快速排序或堆排序（后者用于 LIMIT 场景），超出内存则退化为基于磁盘、多路归并的外部排序；PostgreSQL 13 引入的增量排序则专门利用"部分预排序"的输入，把全量排序拆解成许多代价低得多的分组内排序。排序机制不仅服务于归并连接，也支撑着 Unique 去重、GroupAggregate 分组聚合，乃至处理 GROUPING SETS 的 MixedAggregate 混合策略。结合本篇的横向对比和前两篇分别讲的嵌套循环、哈希连接，整个系列完整覆盖了 PostgreSQL 优化器可选的全部三种物理连接算法，以及它们各自依赖的核心机制（索引访问、哈希表、排序）——理解这几篇内容，基本上就掌握了阅读和诊断 PostgreSQL EXPLAIN 输出所需的核心知识框架。