CMU15445-lecture10

第十课：排序和聚合算法

1 排序

DBMS 需要对数据进行排序，因为表中的元组在关系模型下没有特定的顺序。排序（可能）用于 ORDER BY、GROUP BY、JOIN 和 DISTINCT 运算符。如果需要排序的数据适合内存，那么 DBMS 可以使用标准排序算法（例如，快速排序）。如果数据不适合，那么 DBMS 需要使用外部排序，该排序可以根据需要溢出到磁盘，并且优先选择顺序 I/O 而不是随机 I/O。

如果查询包含带有 LIMIT 的 ORDER BY，则 DBMS 只需扫描数据一次即可找到前 N 个元素。这称为 Top-N 堆排序。堆排序的理想情况是前 N 个元素适合内存，这样 DBMS 在扫描数据时只需维护内存中的排序优先级队列。对于内存中容纳不了的庞大数据进行排序的标准算法是外部合并排序。它是一种分而治之的排序算法，将数据集拆分为单独的运行，然后单独对它们进行排序。它可以根据需要将运行溢出到磁盘，然后一次读回一个。该算法由两个阶段组成：

1. 排序：首先，该算法对适合主内存的小块数据进行排序，然后将排序后的页面写回磁盘。
2. 合并：然后，该算法将排序后的子文件组合成一个更大的文件。

双向归并排序

该算法最基本的版本是双向合并排序。该算法在排序阶段读取每个页面，对其进行排序，然后将排序后的版本写回磁盘。然后，在合并阶段，它使用三个缓冲页。它从磁盘读取两个已排序的页面，并将它们合并到第三个缓冲页中。它从磁盘读取两个已排序的页面，并将它们合并到第三个缓冲页面中。每当第三个页面填满时，它就会被写回磁盘并替换为空白页。每组排序好的页面称为一个运行。然后，算法会以递归方式将这些运行合并在一起。

如果 N 是数据页的总数，则该算法将总共遍历数据 1 +⌈logN⌉ 次（第一步排序为 1，然后递归合并为 ⌈logN⌉ 次）。总 I/O 成本为 2N ×（传递次数），因为每次传递对每个页面执行一次 I/O 读取和一次 I/O 写入。

通用（K路）归并排序

该算法的通用版本允许 DBMS 使用三个以上的缓冲页。设 B 为可用的缓冲页总数。然后，在排序阶段，算法可以一次读取 B 页，并将 ⌈N/B⌉ 个已排序的运行写回到磁盘。合并阶段还可以在每次传递中组合最多 B - 1 次运行，再次使用一个缓冲页面来存储组合数据并根据需要写回磁盘。在广义版本中，该算法执行 ⌈1 + log_B-1 ⌈N/B⌉⌉ 次传递（一次用于排序阶段，log_B-1 ⌈N/B⌉次用于合并阶段）。然后，总 I/O 成本为 2N ×（传递次数），因为它必须在每次传递中对每个页面进行读取和写入。

双缓冲优化

外部合并排序的一个优化是在系统处理当前运行的同时，在后台预取下一次运行并将其存储在第二个缓冲区中。通过持续利用磁盘，这可以减少每一步 I/O 请求的等待时间。此优化需要使用多个线程，因为预取应该在当前运行的计算过程中进行。

使用B+树

对于 DBMS 来说，使用现有的 B+ 树索引来辅助排序有时比使用外部合并排序算法更有优势。具体来说，如果索引是聚集索引，则 DBMS 只需遍历 B+ 树即可。由于索引是聚集的，因此数据将以正确的顺序存储，因此 I/O 访问将是连续的。这意味着它总是比外部合并排序更好，因为不需要计算。另一方面，如果索引是非聚集的，则遍历树几乎总是更糟糕，因为每个记录可以存储在任何页面中，因此几乎所有记录访问都需要读取磁盘。

2 聚合

查询计划中的聚合运算符将一个或多个元组的值折叠为单个标量值。有两种方法可以实现聚合：(1) 排序和 (2) 哈希。

排序

DBMS 首先根据 GROUP BY 键对元组进行排序。如果缓冲池中所有内容都适合，则可以使用内存排序算法（例如快速排序），如果数据大小超出内存，则使用外部合并排序算法。然后，DBMS 对排序后的数据执行顺序扫描以计算聚合。运算符的输出将按键排序。

执行排序聚合时，对查询操作进行排序以最大限度提高效率非常重要。例如，如果查询需要过滤，则最好先执行过滤，然后对过滤后的数据进行排序，以减少需要排序的数据量。

哈希

对于计算聚合而言，散列比排序更节省计算成本。DBMS 在扫描表时会填充临时哈希表。对于每条记录，检查哈希表中是否已经存在条目，并执行适当的修改。如果哈希表的大小太大而无法放入内存中，则 DBMS 必须将其溢出到磁盘。实现此操作分为两个阶段：

• 分区：使用哈希函数 h1 根据目标哈希键将元组拆分为磁盘上的分区。这会将所有匹配的元组放入同一个分区。DBMS 通过输出缓冲区将分区溢出到磁盘。
• 再哈希：对于磁盘上的每个分区，将其页面读入内存，并基于第二个哈希函数 h2（其中 h1 ！= h2）构建内存哈希表。然后遍历该哈希表的每个存储桶，将匹配的元组汇集在一起以计算聚合。这假设每个分区都适合内存。

在 ReHash 阶段，DBMS 可以存储形式 (GroupByKey→RunningValue) 的对来计算聚合。RunningValue 的内容取决于聚合函数。要将新元组插入哈希表：

• 如果找到匹配的 GroupByKey，则适当更新 RunningValue。
• 否则插入一个新的 (GroupByKey→RunningValue) 对。