Lec 11 排序与聚合算法

0. 为什么 DBMS 里总是要排序

关系模型本身是无序的，但 DBMS 还是频繁需要排序：

  • ORDER BY
  • DISTINCT
  • GROUP BY
  • 窗口函数
  • 给 B+Tree 做 bulk loading

对于磁盘导向的 DBMS，关键约束是：输入或输出往往放不进内存。因此这讲重点讨论的是能 spill 到磁盘、并尽量利用顺序 I/O 的算法。

下面统一记号：

  • T = tuple 数
  • N = page 数
  • B = buffer page 数
  • G = 聚合后的 group 数

1. 排序模型

排序操作的对象可以看成 (key, value) 对：

  • Key：决定顺序的属性
  • Value：要么是完整 tuple，要么是 record id / offset

Early vs. Late Materialization

策略 实际排序的内容 适合场景
Early materialization (sort key, tuple) tuple 较小，后续算子也需要整行数据
Late materialization (sort key, rid) 列存或宽表，避免频繁复制大 tuple

内存内排序复杂度

如果只看比较型内存排序，常见 CPU 复杂度是：

\[ O(T \log T) \]

课程真正关心的是：数据一旦超出内存，CPU 复杂度不再是唯一重点，磁盘 I/O 通常才是主导项。

2. External Merge Sort

如果数据能装进内存，就用常规内存排序；如果装不下，就需要 外部归并排序（external merge sort）。

核心思想

它是一个典型的分治过程：

  1. 把数据切成内存能放下的若干 run。
  2. 每个 run 在内存中排好序。
  3. 写回磁盘。
  4. 多轮归并，直到只剩一个有序 run。

Pass 0：生成初始 runs

假设有 B 个 buffer page，输入有 N 个 page：

  • 每次读最多 B 个 page
  • 在内存中排序
  • 写出一个有序 run

因此初始 run 的数量大约是 \lceil N / B \rceil。

后续归并

每一轮 merge pass：

  • 用 B-1 个输入 buffer
  • 用 1 个输出 buffer
  • 一次最多归并 B-1 个 run

代价公式

总 pass 数：

\[ 1 + \left\lceil \log_{B-1}\left\lceil \frac{N}{B} \right\rceil \right\rceil \]

总 I/O 成本：

\[ 2N \cdot \left(1 + \left\lceil \log_{B-1}\left\lceil \frac{N}{B} \right\rceil \right\rceil\right) \]

原因很直接：每一轮都要把整个文件读一遍、写一遍。

如果忽略实现细节，比较次数仍然大致是：

\[ O(T \log T) \]

但在 DBMS 场景里，真正更关键的是上面的 I/O 公式。

Double Buffering

Double buffering 的作用是把 CPU 和 I/O 重叠起来：

  • 当前 buffer 在处理时，后台预取下一段 run
  • 吞吐更高
  • 但实际可用于 merge 的 buffer 会减少，因为一部分内存被预取/输出占用

3. 利用 B+Tree 排序

如果表在排序键上已经有 B+Tree，DBMS 可以直接利用索引顺序，而不是重新外部排序。

Clustered B+Tree

  • 按序扫描叶子页即可。
  • 数据页与索引顺序一致。
  • 磁盘访问几乎是顺序的。
  • 一般比重新 external sort 更好。

Unclustered B+Tree

  • 键是有序的，但取 tuple 时需要一路追 record pointer。
  • 很容易退化成接近“一条记录一次 I/O”。
  • 对全量排序通常很差。
  • 例外是 Top-N 查询，因为只需要前面很小一部分结果。

4. Top-N Heap Sort

对于下面这类查询：

1
2
3
SELECT * FROM enrolled
ORDER BY sid ASC
FETCH FIRST 10 ROWS WITH TIES;

DBMS 并不需要把所有数据全排完。

核心思想

  • 整个输入只扫描一遍。
  • 内存里维护一个大小为 N 的 heap / priority queue。
  • 无法进入前 N 的元素直接丢掉。

它特别适合：

  • LIMIT 很小
  • 前 N 条结果能放进内存
  • 不值得为此付出完整排序的代价

如果有 WITH TIES，最终结果条数可能略大于 N。

复杂度：

  • 时间：O(T \log N)
  • 内存：O(N)
  • I/O：输入只需完整扫描一遍，再加输出

5. Collation

字符串排序不是简单地“按字节比大小”。

Collation 定义了：

  • 字符顺序
  • 相等比较方式
  • 大小写敏感性
  • 重音敏感性
  • locale-specific 规则

Binary Collation

  • 速度最快
  • 直接按字节 / code point 比较
  • 对性能友好
  • 但 ASCII / binary 顺序不等于自然语言顺序

Locale-Aware Comparison

课上提到的 ICU / UCA 风格比较是多层次的：

  • Primary：基础字母差异
  • Secondary：重音差异
  • Tertiary：大小写差异
  • Quaternary：标点或进一步 tie-breaking

因为逐层比较很贵，系统通常会 预计算 sort key。

常见优化

  • Code specialization：给特定 key 类型生成专用比较逻辑，而不是一直走通用 comparator。
  • 前缀比较：长字符串先比一个便宜的二进制前缀，前缀相等时再走慢路径。
  • Key normalization：把变长属性编码成能保持排序关系的固定形式。

6. Aggregation

聚合的本质是把多条记录压缩成更少的结果：

  • DISTINCT
  • GROUP BY
  • SUM / COUNT / MIN / MAX / AVG

系统问题本质上和排序很接近：怎样快速把同一组 key 的 tuple 放到一起？

7. 基于排序的聚合

思路

  1. 先按 group key 排序。
  2. 扫描有序流。
  3. 对当前 group 维护 running state。

常见 running state

聚合函数 运行时状态
COUNT count
SUM sum
MIN 当前最小值
MAX 当前最大值
AVG (count, sum)

什么时候适合

当下面场景出现时，sort-based aggregation 很自然：

  • 输入本来就有序
  • 查询本身也需要有序输出
  • 一次排序可以被多个后续算子复用

如果排序本来就必须做，那么排序之后的聚合只需要线性扫描：

\[ O(T) \]

所以总成本可以近似看成：

\[ \text{sort cost} + O(T) \]

8. Hash Aggregation

如果 不需要最终顺序，哈希通常更合适。

内存内 Hash Aggregate

扫描时对每条记录：

  • 用 group key 哈希
  • 去临时 hash table 里找对应 entry
  • 没有就创建
  • 有的话就更新 running aggregate

只要 hash table 能放进内存，这个方案通常很直接。

期望复杂度：

  • 时间：O(T)
  • 内存：O(G) 个聚合状态

最坏情况下哈希冲突会让时间变差，但期望情况通常是线性的。

9. 外部 Hash 聚合

如果聚合状态放不进内存，就使用两阶段外部算法。

Phase 1：Partition

  • 用哈希函数 h1 按 group key 分桶
  • 写到 B-1 个磁盘分区
  • 1 个输入 buffer，B-1 个输出 buffer

Phase 2：ReHash / Aggregate

对每个分区分别：

  • 读回内存
  • 建一个较小的内存 hash table
  • 在这个分区内部完成聚合

之所以可行，是因为同一个 group key 会被送进同一个分区。

如果不需要递归重分区，并且忽略最终结果输出，一个常用的 I/O 近似是：

\[ 3N \]

因为：

  • partition 阶段读写输入一次：2N
  • rehash / aggregate 阶段再读一次：N

10. 如何选择：排序还是哈希

任务 优先方案 原因
结果本身需要有序 Sort 排序本来就是输出要求的一部分
ORDER BY ... LIMIT N Top-N heap 避免完整排序
GROUP BY / DISTINCT 且不要求顺序 Hash aggregate 很多场景下比排序更便宜
已有排序键上的 clustered index B+Tree scan 顺序已经“物化”出来了

11. 复杂度总结

技术 CPU / tuple 复杂度 I/O / 内存视角
内存内比较排序 O(T \log T) 需要输入能放进内存
External merge sort 比较代价约 O(T \log T) 2N \cdot \left(1 + \left\lceil \log_{B-1}\left\lceil N/B \right\rceil \right\rceil\right) I/Os
Clustered B+Tree 排序 经过一次索引定位后基本线性扫描 近似一次顺序扫描相关页
Unclustered B+Tree 排序 pointer chasing 主导 可能接近“一条 tuple 一次随机取数”
Top-N heap sort O(T \log N) O(N) 内存，一次输入扫描
Sort-based aggregation \text{sort cost} + O(T) 当结果也需要顺序时最自然
内存内 hash aggregation 期望 O(T) O(G) 内存
外部 hash aggregation 每阶段期望线性 若无递归重分区，约 3N I/Os

快速总结

  1. External merge sort 是磁盘场景下的基础排序算法。
  2. B+Tree 可以替代排序，但真正稳定好用的是 clustered access。
  3. Top-N 查询不应该默认做完整排序。
  4. 字符串排序的难点在于 collation，而不只是比较字节。
  5. 聚合的核心是把相同 key 聚在一起，主流方案只有两类：排序和哈希。