lectrue10 排序和聚合算法

Ne0inhk

24 Mar 2026 — 11 min read

查询计划：到目前为止，我们主要讨论的是访问方法（即如何通过索引或扫描找到数据）。现在，我们需要讨论如何真正执行这些查询。

数据库系统会将SQL语句编译成查询计划，查询计划是一个由算子组成的树状结构。我们将在后续的查询执行课程中详细讲解这部分内容。

对于面向磁盘的数据库系统，我们将利用缓冲池来实现那些在处理过程中需要溢出到磁盘的算法，我们的核心目标是尽可能减少算法的I/O次数。

排序：由于在关系模型中，表中的元组没有特定的顺序，因此 DBMS 需要对数据进行排序。排序（潜在地）被用于 ORDER BY、GROUP BY、JOIN 和 DISTINCT 算子。如果待排序的数据能全部装入内存，DBMS 可以使用标准排序算法（如快速排序）。如果数据量太大无法装入内存，则需要使用外部排序（如归并排序），该算法能够根据需要将数据溢出到磁盘，并且相比随机 I/O，它更倾向于使用顺序 I/O。

如果查询包含带有LIMIT的ORDER BY，DBMS 只需扫描一次数据即可找到前 N 个元素。这被称为 Top-N 堆排序。堆排序的理想场景是前 N 个元素可以装入内存，这样 DBMS 在扫描数据时，只需在内存中维护一个排序好的优先级队列即可。

对于大到无法装入内存的数据，标准排序算法是外部归并排序。这是一种分治算法，它将数据集分割成独立的初始轮次并分别进行排序。它可以根据需要将这些轮次溢出到磁盘，然后一次读回一个进行处理。该算法包含两个阶段：

1.排序：首先，算法对能装入主存的小块数据进行排序，然后将排序后的页面写回磁盘。

2.归并：然后，算法将排序后的子文件合并成一个更大的单一文件。

注：什么是溢出？溢出是指当RAM不足以容纳当前处理的数据时，系统被迫将数据暂时写入硬盘的行为。

排序轮次可以是早物化的（即具体数值直接存储在页面中），也可以是晚物化的（即轮次中仅存储记录 ID/RID，稍后再读取具体数值）。

二路归并排序：归并排序最基础的版本是二路归并排序。

排序阶段：算法读取每个页面，对其内部数据进行排序，然后将排序后的版本写回磁盘。
归并阶段：算法使用三个缓冲页：
- 从磁盘读入两个排序好的页面（作为输入）。
- 将它们合并到第三个缓冲页（作为输出）中。
- 每当第三个页面填满时，就将其写回磁盘并重置为空白页。
Run（轮次/归并段）：每一组排序好的页面被称为一个 Run。算法随后递归地将这些 Run 合并在一起。

开销分析：如果N是总页面数，该算法的性能指标如下。

遍历次数：总共需要进行(1+

)次遍历。其中一次用于初始排序，

用于递归归并。

总I/O开销：2N * 遍历次数，这是因为在每一次遍历中，每个页面都要执行一次I/O读取和一次I/O写入。

注：更准确的说，这是因为在每一次遍历中，每个元组都要执行一次读取和写入。

通用K路归并排序：通用版本的算法允许 DBMS 利用三个以上的缓冲页。假设 B 是可用的缓冲页总数。那么：

排序阶段：算法可以一次读取 B 个页面，并向磁盘写回 N/B 个排序好的 Run。这里的Run就是最小有序单位，即递归深入的终点。
归并阶段：每次遍历可以合并多达 K 个 Run，同样使用一个缓冲页存放合并后的数据，并根据需要写回磁盘。

在通用版本中，算法执行

$1 + \lceil \log_{B-1} \lceil N/B \rceil \rceil$

次遍历，总I/O开销依然是2N * 遍历次数。

注：K=B-1，因为在归并阶段，必须要有K个页面来存放来自K个不同Run的当前数据，同时留出一个页面来存放归并后的结果。

二路归并时需要有两个指针，然后比较这两个指针上的最小值（假如是从小到大排序）并填入归并后的页面。而K路归并则需要K个指针。

如何得出，排序阶段之后我们有N/B个Run，每次合并K个Run，再加上到达初始阶段的那个1，就是那个遍历次数的公式。

双缓冲优化：外部归并排序的一种优化手段是预取，在系统处理Run的同时，后台预取下一个 Run 并将其存储在第二个缓冲区中。通过持续利用磁盘，这减少了每一步等待 I/O 请求的时间。这种优化需要使用多线程，因为预取应该在处理当前 Run 的计算逻辑时同步发生。

比较优化：代码优化常用于加速排序中的比较操作。与其将比较器作为函数指针传递给排序算法，不如将其针对特定的键类型进行硬编码。C++中的模板特化就是一个例子，另一种针对字符串比较的优化是后缀截断，长VARCHAR键的二进制前缀可以先进行相等检查，只有当前缀相等，才会回退到较慢的标准字符串比较。

使用B+树：有时利用现有的B+树索引来辅助排序比使用外部归并排序更有优势。

聚簇索引：DBMS 只需遍历 B+ 树。由于是聚簇索引，数据按正确顺序存储，因此 I/O 访问是顺序的。这总是优于外部归并排序，因为不需要额外的计算。
非聚簇索引：遍历树几乎总是更糟糕的，因为每条记录可能存储在任何页面中，几乎所有的记录访问都会导致一次磁盘随机读取。

聚合：在查询计划中，聚合操作符将一个或多个元组的值合并为单个标量值。实现聚合的方法有两种，排序和哈希。

排序：数据库管理系统（DBMS）首先根据 GROUP BY 的键对元组进行排序。如果所有数据都能装入缓冲池，可以使用内存排序算法（如快速排序）；如果数据量超过内存大小，则使用外部归并排序算法。随后，DBMS 对排序后的数据进行顺序扫描以计算聚合结果。该操作符的输出将按键排序。

在执行排序聚合时，调整查询操作的顺序以最大化效率至关重要。例如，如果查询需要过滤，最好先执行过滤，然后再对过滤后的数据进行排序，以减少需要排序的数据量。

哈希：在计算聚合时，哈希的计算开销可能比排序更低。DBMS 在扫描表时会填充一个临时哈希表。对于每条记录，检查哈希表中是否已经存在相应的条目，并进行适当的修改。如果哈希表的大小太大而无法装入内存，DBMS 必须将其溢出到磁盘。完成这一过程分为两个阶段：

分区：使用哈希函数 h1 根据目标哈希键将元组拆分到磁盘上的分区中。这将把所有匹配的元组放入同一个分区。假设总共有 B 个缓冲区，我们将有 B-1 个用于分区的输出缓冲区和 1 个用于输入数据的缓冲区。如果任何分区满了，DBMS 将其溢出到磁盘。

重哈希：对于磁盘上的每个分区，将其页面读入内存，并基于第二个哈希函数h2(h1≠h2)构建内存哈希表，然后遍历该哈希表的每个桶，将匹配的元组汇集在一起以计算聚合。这假设每个分区都能装入内存。重哈希的作用域是单个分区内的数据，它是粒度更细的哈希。

在重哈希阶段，DBMS可以存储形式为(GroupByKey -> RunningValue)（分组键 -> 运行值）的键值对来计算聚合。RunningValue 的内容取决于具体的聚合函数（如 SUM, AVG, COUNT 等）。向哈希表中插入新元组时：

如果找到了匹配的 GroupByKey，则相应地更新 RunningValue。
否则，插入一个新的 (GroupByKey -> RunningValue) 对。

通常情况下，对于聚合操作，哈希总是更高效的，除非数据预先已经排好序（例如紧跟在OEDER BY之后）。

注：聚合本身过程其实并不困难，我们只需要遍历一遍表即可。问题在于，为了聚合过程的效率，我们需要先让表保持一个相对有序的状态。排序是直接使其有序，而哈希则是让键相同的数据尽可能聚在一起。我们通过哈希函数h1，将“键的哈希值相同的元组”分到同一桶中，然后又通过另一个哈希函数h2将“键的哈希值相同的元组”又分到同一桶中。通过这样，我们尽可能避免了哈希冲突。（哈希值相同不一定key就相同，对于不同的哈希函数，相同的键可以得到不同的值，不同的键也可以得到相同的值，这也使为什么要使用两个哈希函数进一步细分）

哈希实现的好处在于：

1.避免了