第八讲 Sort Aggregate 算法

我们现在将讨论如何使用迄今为止讨论过的 DBMS 组件来执行查询。

1 查询计划【Query Plan】

我们首先来看当一个查询【Query】被解析【Parsed】后会发生什么？

当 SQL 查询被提供给数据库执行引擎，它将通过语法解析器进行检查，然后它会被转换成关系的代数表示，需要注意的是，这个代数表示是得到优化过后的。

大概解释一下这棵树：

• R 和 S 是两张表，也可以说是两个关系
• 首先对 S 表做查询，条件谓词 value > 100
• 然后将 S 表与 R 表做 join ，连接的条件是 S.id = R.id
• 最后对联表生成的关系做映射，只取R.id和S.cdata两列输出的到结果中

我们得到了用树形表示的查询，树的每一个节点都是一个操作符。数据从树的叶子向上流向根，根节点的输出就是查询的结果。
 

那么我们想用算法对这些操作符做什么呢？？

• 就像不能假设表完全可以被内存容纳下来一样，面向磁盘的 DBMS 也不能假设查询结果（设置时中间结果）可以被内存容纳。
• 我们将使用缓冲池来实现需要溢出到磁盘的算法，即内存不足以承载（中间）结果集时。
• 我们还将更喜欢能够最大化顺序 I/O 量的算法。

2 为什么我们需要排序

关系型模型【Relational model/】/SQL 是无序的【unsorted】。
但是查询【Query】可能要求元组以特定方式排序（ORDER BY）。
但即使查询没有指定顺序，我们可能仍然想要排序来做其他事情：

• 轻松支持重复消除（DISTINCT）。
• 将排序元组【sorted tuples】批量加载到 B+Tree 索引中的速度更快。
• 聚合（GROUP BY）。 

3 内存排序

如果内存足以容纳数据，那么我们可以使用标准排序算法，例如快速排序。

大多数数据库系统使用快速排序进行内存排序。
在其他数据平台中，尤其是 Python，默认排序算法是 TimSort。 它是插入排序和二元归并排序的结合。 通常在真实数据上效果很好。

如果内存不足以容纳数据，那么我们需要使用一种能够感知读取和写入磁盘页面成本的技术。

4 排序算法

今天我们主要讲下面几个算法：

• Top-N 堆排序【Top-N Heap Sort】
• 外部归并排序【External Merge Sort】
• 聚合【Aggregations】

4.1 Top-N 堆排序【Top-N Heap Sort】

如果查询【Query】中包含带有 LIMIT 的 ORDER BY，则 DBMS 只需扫描数据一次即可找到前 N 个元素。

堆排序的理想场景：如果 topN 元素适合内存。

• 扫描一次数据，在内存中维护一个排序的优先级队列。

1️⃣ 我们扫描数据

2️⃣ 并将其设置到堆排序的数组中 

3️⃣ 当我们扫描到 9 时，由于我们只取最小的 4 个元素，因此9直接在内存中被跳过

 

4️⃣ 而碰到元素1后，他会改变我们的堆排序数组

4.2 外部归并排序

分而治之算法，将数据分成单独的 runs ，分别对它们进行排序，然后将它们组合成更长的排序了的 runs。
第 1 阶段 – 排序

• 对适合内存的数据块进行排序，然后将排序后的数据块写回到磁盘上的文件中。

第 2 阶段 – 合并

• 将排序后的 runs 合并成更大的 chunks。 

run 是键/值对的列表。
key：用于比较以计算排序顺序的属性【attribute】。
value：有两种选择

• 元组（早期的物化）。
• 记录 ID（后期的物化）。

 4.2.1 2路外部归并排序

我们将从 2 路外部归并排序的简单示例开始。

• 其中，“2”是我们每次合并的 run 的数量

数据被分成 N 页。

DBMS 有有限数量的 B 个缓冲池页来保存输入和输出数据。

栗子：

我们有 N 页的数据，而 DBMS 有一个 B 页大小的缓冲池来保存输入和输出数据。

Pass 0

• 将表的所有 B 页【pages】读入内存
• 对页【page】进行排序并将其写回磁盘

Page 2,3,,,

• 递归地将一对 run 合并为两倍长的 run
• 使用三个缓冲区页面（2 个用于输入页面，1 个用于输出页面）

在每次一次传递【Pass】中，我们都要读写每一个页。

总的传递【Pass】数：= 1 + ⌈ log2 N ⌉

总的 IO 花费 = 2N · (# of passes)

 

该算法仅需要三个缓冲池页面来执行排序（B=3）。

• 两个输入页面，一个输出页面

但是，即使我们有更多可用 Buffer Pool 空间 (B>3)，如果工作线程【worker】必须阻塞磁盘 I/O，那么依然无法有效利用它们。

双缓存优化

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

通用外部归并排序 

Pass 0

• 使用 B 个 缓冲页
• 产生  ⌈N / B⌉ 个 B 大小的有序 run

Pass #1,2,3,…

• 归并 B-1 个 runs (i.e., K-way merge)

总的传递【Pass】数：= 1 + ⌈ logB-1 ⌈N / B⌉ ⌉

总的 IO 花费 = 2N · (# of passes)

栗子：

确定使用大小为 5 页的 Buffer Pool 来排序占用 108 页的数据，需要经过几次传递【Pass】?

Pass #0: ⌈N / B⌉ = ⌈108 / 5⌉ = 22 个 5 页大小的排好序的 run

Pass #1: ⌈N’ / B-1⌉ = ⌈22 / 4⌉ = 6 个 20 页大小的排好序的 run（最后一个 run 只有3页）

Pass #2: ⌈N’’ / B-1⌉ = ⌈6 / 4⌉ = 2 个排好序的 run ，第一个有 80 页大小，第二个只有 28 页

Pass #3: Sorted file of 108 pages

1+⌈ logB-1⌈N / B⌉ ⌉ = 1+⌈log4 22⌉ = 1+⌈2.229...⌉ = 4 passes

比较优化

方法1：代码特化/硬编码：不要提供比较函数作为排序算法的指针，而是创建特定于键类型的硬编码版本的排序。

方法2：后缀截断：首先比较长 VARCHAR 键【key】的二进制前缀，而不是较慢的字符串比较。 如果前缀相等，则回退到较慢的版本。

4.3 使用 B 树进行排序

如果需要排序的表在排序属性上已经有 B+Tree 索引，那么我们可以使用它来加速排序。
只需遍历树的叶节点所在的页，即可按所需的排序顺序检索元组。
需要考虑下面两种情况：

• 聚簇 B+树
• 非聚集B+树

聚簇索引

遍历到最左边的叶节点的页，然后从所有叶节点的页中检索元组。
这种办法总是比外部归并排序更好，因为没有计算成本，并且所有磁盘访问都是顺序的。

非聚簇索引

这几乎总是一个坏主意。因为在非聚簇索引种，我们需要追踪指向包含数据的页面的每个指针。

一般来说，每个数据记录一个 I/O，这是随机 IO 的灾难。

4.4 聚合 

聚合是一种函数【function】，将多个元组中单个属性的值折叠为单个标量值【scalar value】。比如 min / max / sum / count /avg。

当我们要实现这些聚合时，我们需要找到一种方法，让DBMS系统快速找到与我们试图在其上构建聚合的属性具有相同值的元组，这样我们就可以对它们进行分组【grouping】计算我们想要的聚合函数。

两种实现选择：

• 排序
• 哈希，哈希的方案一般是要比排序更好的，尤其是当你的操盘速度很慢时（最小化IO）。

4.4.1 排序聚合

我们以一个栗子开始，这是我们的表：

我们要在该表上查询特定条件下不重复的 cid

SELECT DISTINCT cid

FROM enrolled

WHERE grade IN ('B','C')

ORDER BY cid

 

首先，我们遍历表，我们要应用 where 子句中的过滤条件，来找到所有成绩为 B 和 C 的元组

然后我们做一个映射【Projection】，因为我们不需要所有的属性，我们应用映射，只保留 cid

 

最后，我们对这个单列【column】进行应用排序，现在要生成最终结果，我们只需要扫描排序产生的输出，并跟踪我在光标处看到的最后一个值是什么，然后如果我遇到了和我之前看到的相同的值，那么我知道，它是重复的，我可以把它扔掉。

4.4.2 排序的替代方案 

如果我们不需要数据有序的话，排序可能并不是最好的方案，那么这该怎么办？

• 在 GROUP BY 中形成组（无顺序）
• 删除 DISTINCT 中的重复项（无顺序）

在这种情况下，哈希散列是更好的选择。

• 只需要去重，无需排序。
• 计算成本比排序更便宜。

4.4.3 哈希聚合

当 DBMS 扫描表时填充临时哈希表。 对于每条记录，检查哈希表中是否已有条目：

• DISTINCT：丢弃重复项
• GROUP BY：执行聚合计算

如果内存足够容纳着一切数据，那么这很容易。
如果 DBMS 必须将数据溢出到磁盘，那么我们需要变得更智能一点。

外部哈希聚合【External Hashing Aggregation】

第 1 阶段 – 分区【Partition】

• 根据哈希键将元组【tuple】划分为桶【bucket】
• 当它们已满时将它们写到磁盘

使用哈希函数 h1 将元组拆分为磁盘上的分区【Partition】。

• 分区是包含具有相同哈希值的一组键的一个或多个页面，它是一种逻辑分组
• 分区通过输出缓冲区“溢出”到磁盘

假设我们有 B 个缓冲区。 我们将使用 B-1 个缓冲区用于输出数据，即用于分区【Partition】，1 个缓冲区用于输入数据。

我们继续复用用排序聚合时的栗子：

我们首先对数据做条件过滤没然后只保留满足条件的元组：

 

然后通过映射【Projection】删除无用的列

 

我们对 cid 应用哈希函数 

阶段 #2 – ReHash

• 为每个分区构建内存哈希表并计算聚合

对于磁盘上的每个分区：

• 我们要将该分区的所有页面读入内存，逐一扫描它们，并基于第二个哈希函数 h2 构建内存中哈希表。
• 然后遍历该内存哈希表的每个存储桶，以将匹配的元组组合在一起。

我们这里假设每个分区都适合内存大小。

我们继续基于第一阶段产出的分区，进行第二阶段的操作：

1️⃣ 首先我们对每一个分区应用哈希函数 h2，并写入专属于自己分区的哈希表中，需要注意的是，这个哈希表不是简单的原样存储，而是针对聚合函数的特定实现。

 2️⃣ 在将一个分区rehash完，我们再将内存哈希表中的每一个桶中的值，写入到最终结果集中

3️⃣ 在一个分区操作完之后，继续执行下一个分区，循环往复，直到所有分区都处理完。

在 ReHash 阶段，存储（GroupKey→RunningVal） 形式的序对【Pair】。

当我们想在哈希表中插入一条新的元组时：

• 如果我们找到匹配的 GroupKey，我们只需要适当的更新RunningVal
• 否则，插入一条 GroupKey→RunningVal

下面我们举个例子来解释一下，我们使用一个新的查询【Query】

SELECT cid, AVG(s.gpa)

FROM student AS s, enrolled AS e

WHERE s.sid = e.sid

GROUP BY cid

1️⃣ 我们先对数据集做分区

 

2️⃣ 然后应用哈希函数 h2 ，我们聚合函数要的是平均值，因此哈希表的值是关于聚合函数的特定值，它是数量和平均值的一个复合体

 3️⃣ 在rehash完，我们将哈希表写入结果集中