15445-11-Sorting&AggregationsAlgorithms

Mindmap

一、查询计划

到目前为止，我们讨论了访问方法。现在需要实际执行查询。

数据库系统会将 SQL 编译为一个查询计划（Query Plan），这是一个由操作符组成的树或有向无环图（DAG）。 在后续课程中将更详细地介绍操作符等内容。

对于面向磁盘的数据库系统，我们使用缓冲池（Buffer Pool）来实现需要溢出到磁盘的算法。 我们的目标是最小化 I/O，并优先使用顺序 I/O而非随机 I/O。

---

二、排序

DBMS 需要排序，因为在关系模型下，表中的元组没有特定顺序。 ORDER BY、GROUP BY、JOIN、DISTINCT 等操作符都可能依赖排序。

若数据能装入内存，DBMS 可使用常规的内存排序算法（如快速排序、vergesort）； 若数据过大，则需使用外部排序（External Sorting），以考虑磁盘操作成本。

排序算法处理输入运行（run）时，将键值对按比较函数和排序参数进行排序。 键用于确定排序顺序，值可以是：

• 整个元组（早期物化，Early Materialization），或
• 记录 ID（后期物化，Late Materialization）。

---

（一）Top-N 堆排序

若查询包含 ORDER BY 与 LIMIT（以及可选的 WITH TIES）， DBMS 只需扫描一次数据，并维护一个优先队列（priority queue）以记录前 N 个元素。 若包含 WITH TIES，则在遇到并列元素时动态扩展优先队列。

理想情况下，若前 N 个元素可存入内存，则整个过程可在内存中完成。

---

（二）外部归并排序（External Merge Sort）

外部归并排序是排序无法完全放入内存数据的标准算法。 它是一种分治算法，主要包含两个阶段：

第一阶段：排序

将可装入内存的小块数据排序后写回磁盘。

第二阶段：合并

将已排序的运行逐步合并成更大的已排序运行。

运行可为早期物化或后期物化形式。

---

（三）双向合并排序（Two-way Merge Sort）

算法在排序阶段读取每页数据，排序后写回磁盘。 合并阶段使用三页缓冲：

• 两页用于输入；
• 一页用于输出，当输出页填满时写回磁盘。

每组已排序的页称为一个“运行（run）”，算法递归合并这些运行。

设：

• 数据页总数为 N

则总遍历次数为：

1 + ⌈log₂N⌉

总 I/O 成本为：

2N × （遍历次数）

因为每趟均需对每页执行一次读取和写入。

---

（四）通用 K 路归并排序（General K-way Merge Sort）

若缓冲页总数为 B，则：

• 排序阶段可一次读取并排序 B 页；
• 写出 N/B 个长度为 B 页的有序运行。

合并阶段可在每趟合并最多 B−1 个运行（B−1 页输入 + 1 页输出）。

遍历总数为：

1 + log₍B−1₎ (N / B)

总 I/O 成本同样为：

2N × （遍历次数）

---

（五）双缓冲优化（Double Buffering）

通过后台预取下一运行并存入第二组缓冲区，可减少等待 I/O 的时间。 此法提高磁盘利用率，但有效缓冲区数减半，且需多线程并行执行。

---

（六）比较优化（Comparison Optimizations）

键比较代价较高，可采用以下优化：

• 代码特化（Code Specialization）： 将排序函数针对特定键类型硬编码，例如 C++ 模板特化。

• 后缀截断（Suffix Truncation）： 对字符串键，先比较前缀；若相等再比较全字符串。

• 键规范化（Key Normalization）： 将可变长度键转换为定长编码字符串，保持排序顺序。

---

（七）使用 B+ 树（Using B+Trees）

若存在适当的 B+ 树索引，DBMS 可直接使用索引来完成排序。

• 若索引为聚集索引（Clustered Index）， 则遍历索引即可获得顺序访问，效率优于外部归并排序。

• 若为非聚集索引（Unclustered Index）， 则可能导致大量随机 I/O，通常性能更差。 例外情况：当执行 Top-N 查询且 N 相对较小时。

---

三、聚合（Aggregation）

聚合操作符将多个元组的值合并为一个标量值。 主要有两种实现方式：

1. 排序聚合
2. 哈希聚合

---

（一）排序聚合（Sorting Aggregation）

DBMS 先根据 GROUP BY 键排序，然后顺序扫描计算聚合结果。

若数据量小，可使用内存排序算法（如快速排序）； 若数据量大，则使用外部归并排序。

优化建议： 若查询包含过滤条件，应先过滤后排序，以减少排序数据量。

---

（二）哈希聚合（Hashing Aggregation）

哈希聚合在输出顺序不重要时通常更高效。

若哈希表可放入内存：

• 扫描表时直接构建临时哈希表；
• 若键已存在则更新值，否则插入新条目。

若哈希表过大，需采用外部哈希聚合（External Hashing Aggregate）， 其为一种分治算法，包括两个阶段：

第一阶段：分区（Partition）

使用哈希函数 h₁ 将数据按键划分为磁盘分区。 若总缓冲页为 B，则有：

• B−1 页用于输出分区；
• 1 页用于输入。 满的分区写回磁盘，生成 B−1 个分区。

第二阶段：重新哈希（ReHash）

逐个读入分区，并使用另一个哈希函数 h₂（h₁ ≠ h₂） 在内存中构建哈希表。 将匹配元组放入相同桶中并执行聚合。

若分区仍过大，可递归继续分区直到能放入内存。

在 ReHash 阶段，存储形如：

(GroupByKey → RunningValue)

其中 RunningValue 依赖聚合函数（如 COUNT 与 SUM 用于 AVG 计算）。

插入逻辑：

• 若键已存在 → 更新 RunningValue；
• 否则 → 新建条目。

---

（三）排序与哈希聚合的选择

二者选择取决于查询特性与系统优化：

• 若数据已排序或输出需排序 → 选择排序聚合；
• 其他情况通常哈希聚合更高效。