排序在数据库里到底怎么用：ORDER BY、Sort-Merge Join 与外部聚合

前七篇我们一直在"实现排序"：

1. 《C语言常见排序算法详解》：比较排序的写法、复杂度、稳定性；
2. 《从会写到会用：C语言排序算法的实战选择与优化》：场景选型、qsort 泛型、快排优化；
3. 《突破 O(n log n)：C语言非比较排序实战》：计数/基数/桶排序；
4. 《数据放不进内存怎么办：C语言外部排序与海量数据排序实战》：分块、多路归并；
5. 《让多核一起干活：C语言并行排序与多线程实战》：pthread、OpenMP；
6. 《不只是数字：C语言字符串排序与后缀数组入门》：字符串比较与后缀数组；
7. 《TimSort：工业级排序的秘密》：run 识别、栈式归并、Galloping。

但排序算法真正的"主战场"其实不在教科书里，而在数据库执行引擎里。一条 SELECT ... ORDER BY、一次 JOIN、一个 GROUP BY，背后都可能是排序在干活。本篇就回答一个问题：

数据库到底在哪些地方用排序？为什么有时用排序、有时用哈希、有时干脆用索引？三者怎么取舍？

理解这一点，你就明白第 4 篇的外部排序为什么是数据库的"基础设施"，也明白第 7 篇 TimSort 的思想为什么在工程里处处可见。

一、数据库里排序出现的四个位置

排序在数据库执行引擎中不是"一个算子"，而是一类算子，至少出现在四个地方：

它们的共同点是：需要一个"按 key 有序"的输入流。排序算子就是生产有序流的工厂。

二、ORDER BY：排序算子的标准形态

ORDER BY 是最直接的排序。执行引擎有两种实现路径：

2.1 内存排序（In-Memory Sort）

数据量小、能装进 work_mem（PostgreSQL）或 sort_buffer_size（MySQL）时，直接内存排序。现代数据库多用**内省排序（Introsort）**或 TimSort 变体：

• 快排平均快，但最坏 O(n²)，用堆排序兜底；
• 真实数据常部分有序，TimSort 在 ORDER BY 已有索引序的结果上接近 O(n)。

这与第 2 篇"快排 + 优化"、第 7 篇 TimSort 完全对应——数据库的排序算子就是这些算法的工程封装。

2.2 外部排序（External Sort）

数据超过内存阈值，退化为第 4 篇的外部排序：分块排序生成 run，再多路归并。PostgreSQL 的 Sort 节点在超出 work_mem 时会 spill to disk，生成临时 run 文件再归并——这正是第 4 篇公式的直接应用：

• 初始 run 数 R = ⌈N / M⌉；
• 归并趟数 S = ⌈log_k R⌉；
• 总 I/O ≈ 2N·S。

数据库还会做top-N 优化：若 ORDER BY ... LIMIT 100，不需要全排序，用大小为 100 的堆维护当前最大/最小的 100 个即可，复杂度从 O(n log n) 降到 O(n log N)。这是第 1 篇堆排序思想在工程里的经典变体。

2.3 索引排序：根本不用排

如果 ORDER BY 的列上已有 B+ 树索引，且查询条件能利用索引，数据库直接按索引顺序扫描，完全跳过排序算子。这是最快的路径——排序的最好优化是不排序。

这也解释了为什么"给 ORDER BY 列建索引"是常见优化手段。

三、Sort-Merge Join：排序是连接的副产品

JOIN 有三种主流算法：

• Nested Loop Join：小表驱动大表，适合小结果集；
• Hash Join：建哈希表，适合等值连接、内存够；
• Sort-Merge Join：两表都按连接键排序，再双指针归并。

Sort-Merge Join 的流程：

1. 对左表按连接键排序；
2. 对右表按连接键排序；
3. 双指针同时扫描，相等则输出，不等则移动较小一方。

它的复杂度是 O(n log n + m log m)（排序阶段）+ O(n + m)（归并阶段）。相比 Hash Join 的 O(n + m)，排序阶段是额外开销——那为什么还要用它？

三个理由：

1. 输入已有序：若两表已在连接键上有索引，排序阶段可省，直接归并，此时比 Hash Join 更省内存；
2. 内存受限：Hash Join 要建哈希表，大表可能放不下；Sort-Merge Join 可外部排序，内存友好；
3. 需要有序输出：若 ORDER BY 的列与连接键一致，Sort-Merge Join 的输出天然有序，省掉一次排序。

这三点都指向同一个工程智慧：把排序"复用"到多个目的上。排序一次，既服务连接，又服务输出顺序，还服务后续聚合——这是执行引擎的核心优化思路。

四、GROUP BY：排序聚合 vs 哈希聚合

GROUP BY 有两种实现：

4.1 排序聚合（Sort + GroupAggregate）

先按分组键排序，再顺序扫描，相邻相同 key 归为一组。优点：

• 输出天然按分组键有序，若外层还有 ORDER BY 分组键，省一次排序；
• 内存友好，可外部排序，适合大表；
• 支持"分组内有序"的聚合（如 string_agg 按序拼接）。

这与 Sort-Merge Join 同理：排序的副产品是有序，可复用。

4.2 哈希聚合（HashAggregate）

建哈希表，key 是分组键，value 是聚合状态。优点：

• 复杂度 O(n)，无需排序；
• 适合分组数不多、内存够的场景。

缺点：

• 输出无序（若需有序，还得再排序）；
• 分组数极多（高基数）时哈希表膨胀，可能退化甚至落盘。

4.3 怎么选？

数据库优化器根据统计信息选：

• 分组数少、内存够 → 哈希聚合；
• 分组数多、需有序输出、内存紧张 → 排序聚合；
• 有分组键索引 → 直接按索引扫描，天然有序，连排序都省了。

这和第 3 篇的结论一致：利用数据信息（分组数、索引、有序性）选算法，比死守一种算法更快。

五、窗口函数：排序是语义的一部分

窗口函数 OVER (PARTITION BY p ORDER BY o) 的语义本身就要求有序：

• PARTITION BY 要求按分区键分组（类似 GROUP BY）；
• ORDER BY 要求分区内有序（用于 ROW_NUMBER、RANK、累计求和等）。

执行引擎通常：

1. 按 (p, o) 排序；
2. 顺序扫描，分区切换时重置窗口状态。

这里排序不是"优化"，而是语义必需。这也是为什么窗口函数常是性能瓶颈——它强制了一次排序。

六、排序 vs 哈希 vs 索引：一张决策表

把上面的讨论浓缩成表：

一句话总结：排序、哈希、索引是三把锤子，优化器根据数据分布、内存、索引、输出顺序需求选锤子。排序的优势是"输出有序 + 内存友好 + 可外部化"，哈希的优势是"线性时间"，索引的优势是"根本不用排"。

七、工程启示：从数据库回到 C 语言

数据库的这些设计，对写 C 代码有直接启发：

1. 排序算子要可外部化：写排序库时，提供"内存排序"和"外部排序"两个入口，按数据量自动切换——第 4 篇的框架就是雏形。
2. top-N 是独立优化：不要用全排序实现 LIMIT，用大小为 N 的堆，O(n log N)——第 1 篇堆排序的直接应用。
3. 排序结果可复用：若下游还需要有序，排序一次服务多个目的（如连接 + 输出 + 聚合）。
4. 比较函数是抽象边界：数据库的排序算子接受"比较器 + 投影"，与第 2 篇 qsort 的比较函数同构。把比较逻辑外置，排序框架才能复用。
5. 稳定性有语义：SQL 标准不保证 ORDER BY 相等行的顺序，但工程上常需稳定（如分页）。第 2 篇"加原始下标决胜"的技巧在数据库里同样适用。
6. 统计信息驱动决策：优化器靠行数、基数、分布选算法。写通用库时，若无法获知数据特征，提供"可配置策略"比"固定算法"更实用。

八、常见坑与检查清单

1. ORDER BY 没走索引：检查索引列顺序、排序方向、表达式是否可索引。
2. LIMIT 没触发 top-N：确认执行计划里是 Limit + Sort 还是 Top-N Sort。
3. Hash Join 落盘：work_mem 太小导致哈希表溢出，考虑调大或改 Sort-Merge。
4. HashAggregate 高基数爆炸：分组数极多时哈希表膨胀，考虑排序聚合。
5. 窗口函数强制排序：能改成"分组聚合 + 自连接"时，可能避免排序。
6. 排序稳定性：分页查询依赖稳定顺序时，ORDER BY 要加唯一键决胜。
7. 外部排序临时空间：大排序可能写满临时表空间，需监控。
8. 排序与 NULL：SQL 中 NULL 的排序位置（NULLS FIRST/LAST）因数据库而异，跨库迁移要注意。