CMU 15-445/645-笔记-10-排序&聚合

2022-10-23 22:59 作者:dengluzhanghao 0人读过 | 我要投稿

## 课程目标

聚合操作可以基于排序算法来做，然后可以应用到下一节课会讲到的 join 算法之中

## 为什么需要排序

因为要确保所有的数据都放在了正确的环境中。毕竟在关系模型中，所有的 tuple 都是无序的，它们都属于一种集合代数(set algebra)

聚簇索引(clustering index) 可以基于某种索引来提供一种强制排序的顺序。可以在 table 中某个特定的 key 上使用聚簇索引，但如果此时需要另一个 key 来进行排序的话，那么聚簇索引这种预排序就没有太大帮助了

如果 table 、输出结果、key 是有序的，那么去重就很方便了，因为这个时候只需要查一次 table，如果当前的数据和上一个数据一样，说明有重复数据，就可以将那个重复的数据扔掉

对于 GROUPBY 也是一样的，如果所有数据被预排序过，那么只需要查一次 table，然后根据需要计算出 running total，以此来生成聚合结果(aggregations)

B+ Tree 中的 bulk loading 会加载大量的数据，如果沿着叶子节点对所有数据进行预排序，然后自下而上去构建索引，这种方式会更加高效

## 排序算法

快排、堆排序、冒泡排序... 等等都可以用，因为数据是放在内存中的

但是如果数据没有放在内存中，那么快排就是一个很糟糕的选项了

因为快排会进行大量的随机跳转，它会随机跳转到内存中的不同位置上，它所做的事情属于随机 I/O

而对于数据库来说，要跳转的 page 可能不是放在内存中的，在最糟糕的情况下，每当对数据集进行一次修改，就要进行一次 I/O

那数据库需要的是一种怎样的算法呢?

需要的是一种，能将在磁盘上读写数据所消耗的成本考虑进去的算法，这个算法能最大化序列 I/O 所能获取到数据的数量

这里会用到序列 I/O，因为它比随机 I/O 的效率要高，即便是在速度很快的 SSD 上也是如此

因为可以通过一次序列 I/O 就能拿到大量的数据，并且在 SSD 中也没有磁盘寻道(seek)

### 外部归并排序

基本原理是，将要排序的数据集分成更小的数据块(runs)，然后对这些 runs 分别排序

在一个给定的 run 中所有的 key 都是排过序的

而这些个 runs 则是要排序的整个 key 集合中彼此不相交的子集(也即归并排序的思想)

对这些体积很小的 runs 进行排序，然后将它们合并在一起，并形成更大的排好序的 runs

然后一直重复操作，直到要排序的整个 key 集合排好为止

这里有 2 个阶段

1. 排序

这个阶段，将尽可能多的数据块放入内存，并对它们进行排序，然后将排完序的结果 runs 写回磁盘

2. 归并

这个阶段，将这些排好序的 runs 合并成更大的 runs，然后将它们从磁盘写出，不断重复这个过程，直到排序全部完成

### 2-Way 外部归并排序

2-way 指的是，在每一轮中要合并的 run 的数量是 2，即将 2 个 run 合并成一个新的大的 run，这个新的大的 run 再作为下一次的输入

数据集是被分散在 N 个 page 中的，因为排序时需要将数据缓存在内存中，所以这个时候就需要考虑在执行该算法时，可用的内存是多少

而这个可以用的内存的大小，是可以在数据库系统中作配置来得到

> 在 PostgreSQL 中，这个内存被称之为 working memory。简单来讲就是，对于一个特定的查询来说，working memory 就是它在进行中间某些操作时被允许使用的内存量。可以在这个 working memory 基础上构建一个 hash table，做排序或者其他事情

### 2-Way 外部归并排序例子

每次要从表中读 B 个 Page 到内存中，在内存中对它们进行排序，接着将排完序后的结果写出到磁盘

现在把图中的 Page #1 放到内存中

然后对它进行排序，现在它就是一个排好序的 run

然后把这个排好序的 run 写回到磁盘上

然后对其他的 Page 也做类似的处理

放到内存中 -> 排好序 -> 将这个排好序的 run 写回磁盘

上述操作使得要排序的 pages 完成之后，会对排好序的 run 进行递归合并，然后将这些结果合并成一起，最终生成的 run 的大小是最开始输入的 2 倍大

对于这种情况而言，至少需要 3 个 buffer page，因为需要 2 个 buffer page 来放那些载入到内存中的 run，1 个 run 对应 1 个 buffer page

另 1 个 buffer page 用来保存要写出的输出结果

要对下图中 2 个 run 进行排序，就将它们扔到内存中

然后将排好序的结果放入到 1 个 page 中，一旦这个 page 写满了，就把它写出到磁盘

然后就是递归地去执行上述过程

### Double Buffering 优化

通过 prefetch 来最小化 I/O 成本，是一种很简单的优化方式

基本原理是，当要对 2 个 page 进行合并时，通过使用 shadow page/buffer 来接收要排序的下一个 run/page，这可以减少异步 I/O 的次数，这样在后台就可以获取到接下来需要的 page(也就是说一边在对第一个 page 排序，另一边同时从磁盘写出第二个要排序的 page 到内存，这样第一个 page 排序完成之后就可以接着第二个 page 的排序了)

比如对 Page #1 进行排序

在对 Page #1 进行排序时，后台就开始获取 Page #2

在对 Page #1 的操作结束时，就可以立即去操作 Page #2 了

### 2-Way 算法总结

#### 例子

使用 5 个 buffer page 对 108 个 page 上的数据进行排序

在第一轮中，要做的 I/O 数量如下

在接下来的几轮中，用上一轮算出来的 run 的数量来计算

接着，不断操作，直到结束为止

### 使用 B+ Tree 来排序

目前这种方式适用于大部分数据集，当然前题是这些数据集中的值都是均匀分布的，即数据没有经过排序，而是随机分布

在某些情况下，可以使用 B+ Tree 来提升排序的速度

那么 B+ Tree 在这个里面起到什么作用了呢?

它在数据结构中让 key 变得有序了

虽然当 table 被修改时，B+ Tree 需要做对应的 split/merge 操作，需要付出点代价去维护，但由于 key 在 B+ Tree 中是有序的，那么在做范围查询时，也就没必要去做排序操作了，直接就能查(这里我理解的是，因为构建 B+ Tree 的过程就已经是一个排序的过程，所以在做查询时就可以直接去查)

如果要排序的 key 和 B+ Tree 上索引中的 key 是一样的话，那么就可以复用这个 B+ Tree，就不用像之前展示的 N-Way merge sort 那样去遍历整个数据集了

但这只适用于 Clustered B+ Tree 的情况，并不适用于 Unclustered B+ Tree

### Clustered B+ Tree

Clusterd B+ Tree 的作用是: 各个 tuple page 中 tuple 的物理位置和在 B+ Tree 索引中定义的顺序相匹配

上图可以看到，能够直接通过 B+ Tree index 找到对应的 tuple pages，并且这个就是有序的

在查询优化器(query optimizer)中也有对应的应用。比如要基于某个 key 进行排序时，如果已经存在关于这个 key 的聚簇索引(clustered index)，那么这个查询优化器就会去使用这个聚簇索引来生成正确的排序，而不会再去执行前面提到的外部归并排序

> 但在 PostgreSQL 中，它并不会强制使用上述方式。比如在上图中，要通过在 B+ Tree 中的某个 key 找到某个对应的 tuple page，但在这个 tuple page 里面的 tuple 它并不是排好序的

### Unclustered B+ Tree

Unclustered B+ Tree 的作用是: 各个 tuple page 中 tuple 的物理位置和在 B+ Tree 索引中定义的顺序不匹配

这是几乎就是个 bad idea，为什么?

因为对于每个记录，都得进行一次 I/O 操作

如上图所示，叶子节点的数据(tuple page)与 B+ Tree index 中数据排列的顺序并没有什么关系

此时如果要去查 B+ Tree index 中它的某个叶子节点中偏前面的 key，可能就需要一次磁盘 I/O，因为需要的 page 可能并不在内存中。在内存中找不到那只能从磁盘中找，获取到它之后放入 buffer 池

此时如果要查 B+ Tree index 中这个叶子节点偏后面的 key，发现它在另一个 page 上，那就必须要把刚放入到 buffer 池中的那个 page 移除掉，把这个找到的 page 放入 buffer 池中(又是一次磁盘 I/O)

## 聚合(Aggregations)

聚合操作的实现，可以有 2 种选择

1. sorting

2. hasing

他们之间有不同的 trade-off，并且性能上也有所不同

因为 sorting 所做的是大量的循序访问(sequential access)，而 hashing 所做的则是随机访问，在有的情况下一个可能比另一个性能要好

一般情况下，不管磁盘的速度有多快，hashing 这种方式的效果会更好

所以在 hashing aggregation 的例子中，会做更多的循序 I/O 而不是随机 I/O

hashing 的速度一直很快，因为所有的数据都是在内存中的

那么聚合操作的过程是怎样的呢?

是这样的，先拿到一堆的值，然后将它们合并到一起，最后生成一个标量值(scalar value)

### Sorting Aggregation

如果数据已经预先排好序了，那么在扫描这堆数据时，就不需要回过头去做聚合计算

因为只需要扫描一轮就可以得到想要的结果，下图是一个例子，enrolled 表已经根据 sid 排好序了

对于接下来的 Query Plan Tree 来说，最先要的做的事情就是过滤

首先需要过滤出所有 grade 不是 B 或 C 的 tuple

然后在进行下一个 operator 操作之前，移除掉输出结果中不需要的列

然后用 DISTINCT 聚合操作完成排序

最后进行去重处理

可以看出在这一整条流程中，基本上都是在尽可能尽早的移除掉无用数据

对于 Projection 操作也是如此，SELECT 想要查什么属性的值，就只查那个对应的属性的列就行，后续在进行排序时，就不用去复制这些额外的数据了(Projection 允许扔掉不需要的列)

> Zone maps 的作用是它可以提前知道它对应的 page 中要进行的查找值得不值得，因为这个里面保存着每个属性可能存在的数据范围是多少

### Aternatives to Sorting

实际上在很多例子中，并不需要排好序的输出结果

但如果不使用 GROUP BY 或者 DISTINCT 来进行排序的话，数据库就会使用它自己的排序，并且付出的代价并不低

在这种情况下，hashing 就能起到作用了

hashing 是另一种分治的算法，通过 hashing，可以对数据集进行拆分，并将正在检查的 tuple 或 key 引导到特定 page 中，然后在内存中处理这些 page

hashing 这种方式会移除掉所有的局部性和排序顺序，因为它会拿到 key，并对 key 进行 hash 处理，然后跳到某个随机位置。而好处就是不需要进行排序了

### Hashing Aggregation

基本原理是，在数据库系统中扫描某个 table ，然后将扫描得到的结果填充到一个临时的 hash table 中。后面在进行查找时，会根据聚合操作类型做不同操作。

比如要插入一个 key

1. 如果这个 key 并不在这个 hash table 中，那么这个 key 就会被填充进这个临时的 hash table

2. 如果这个 key 在这个 hash table 中，就需要通过修改这个 key 或者这个 key 对应的值，来生成所需要的聚合操作的结果

对于 DISTINCT 来讲，它就是通过 hashing 的这种方式来判断是否有重复的 key

对于 GROUP BY 来讲，它就会去执行聚合计算，可能要去更新 RUNNING_TOTAL

注意，这个临时的 hash table 只用于当前对应的这个查询，当这个查询结束时，这个 hash table 会被销毁掉

如果数据库中的所有数据的写入写出都在内存中，而这个 hash table 也在内存里面，那么毫无疑问是最好的，因为复杂度(插入、更新)基本都是 O(1)

但是如果数据库中所有的数据都要写出到磁盘上，那就不行了，因为 hash table 带来的随机性会很糟糕(在插入、更新数据时，可能需要跳转到 hash table 中对应的 page 下，这个时候要拿到这个 page 就需要从磁盘写入数据到内存，需要一次 I/O 操作。每跳转一次，就可能需要一次 I/O，有 I/O 操作，就会降低性能)

那么有没有更好的方案?

### External Hashing Aggeragation

答案是有的，基本原理就是尽可能地减少随机 I/O，尽可能地增加循序 I/O，也就是说将大部分操作尽可能都在内存中完成，然后再将结果写出到磁盘