【CMU 15-445】10 排序和聚合算法

Slides
Notes

1. 排序 Sorting

我们需要排序，因为在关系模型中，表中的元组没有特定的顺序排序(可能)用于 ORDER BY、GROUP BY、JOIN和 DISTINCT 操作符。

我们可以通过从左到右扫描叶节点来使用聚集B+树来加速排序。然而，如果我们使用非聚集B+树进行排序，这不是一个好主意，因为它会导致大量I/O读取(通过指针跟踪进行随机访问)。

如果我们需要排序的数据适合在内存中，则DBMS可以使用标准排序算法(例如，快速排序)。如果数据不适合，则DBMS需要使用能够根据需要溢出到磁盘的外部排序，并且更喜欢顺序I/O而不是随机I/O。

2. 外部归并排序

分而治之的排序算法，将数据集分成多个独立的 runs，然后分别对它们进行排序。它可以根据需要将 runs 溢出到磁盘，然后一次读回一个。

阶段1-排序：对可放入主内存的小块数据进行排序，然后写回磁盘。

阶段2-合并：将已排序的子文件合并为更大的单个文件。

2-路归并排序

• 过程#0：将表的每 B 页读入内存。对它们进行排序，并将它们写回磁盘。每一组已排序的页面都称为 run。
• 过程#1，2，3…：递归地将多对 runs 合并为两倍长的 runs。

通用归并排序（K-路）

• 过程#0：使用 B 缓冲区页，生成大小为 B 的 N / B 个排好序的 runs。
• 过程#1、2、3…：递归合并 B−1 个 runs。（因为至少要留 1 个作为整合的页）

双缓冲优化

在后台预取下一次 run，并在系统处理当前 run 时将其存储在第二个缓冲区中。这通过持续利用磁盘，减少了每个步骤的I/O请求等待时间。

3. 聚合

查询计划中的聚合 operators 将一个或多个元组的值折叠为单个标量值。

首先聚合函数有5个，分别为：

• count：统计记录数
• sum：求和，多个记录求和
• avg：平均数
• Max：最大值
• min：最小值

分组是经常跟聚合函数一起使用的，分组关键字为：group by

使用聚合函数删除重复值（关键字DISTINCT）

实现聚合有两种方法：(1)排序；(2)hashing。

Sorting

DBMS首先在 GROUP BY 的 key(s) 上对元组进行排序。如果所有内容都适合缓冲池，则可以使用内存内排序算法（例如快速排序），如果数据大小超过内存，则可以使用外部合并排序算法。

然后，DBMS对排序后的数据执行顺序扫描，以计算聚合。operators 的输出将按 key 进行排序。

Hashing

对于计算聚合，hashing 可能比排序的计算成本更低。DBMS在扫描表时填充临时哈希表。对于每条记录，检查哈希表中是否已有条目并执行适当的修改。

如果哈希表太大，内存无法容纳，则DBMS必须将其溢出到磁盘：

• 阶段1-分区 Partation：使用 hash 函数 h1 根据目标 hash key 将元组分割为磁盘上的分区。这将把所有匹配的元组放到同一个分区中。DBMS通过输出缓冲区将分区溢出到磁盘。
• 阶段2-重新散列 Rehash：对于磁盘上的每个分区，将其页面读入内存，并基于第二个散列函数 h2 (其中h1 != h2)构建内存中的hash 表。然后遍历这个哈希表的每个桶，将匹配的元组集合在一起来计算聚合。请注意，这假设每个分区都可以放入内存。

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

• 如果找到匹配的GroupByKey，则相应地更新RunningValue。
• 否则插入新的(GroupByKey→RunningValue)对。