接下来将学习使用我们现在学习的 DBMS 组件来执行查询。
我们今天要讨论的算法都是基于 Disk 的，即查询的中间结果也需要存储到磁盘中。我们需要使用 Buffer Pool 去实现这些算法，要最大化磁盘连续 I/O。
Query Plan：算子组织成树形结构，数据从叶子节点流向根节点，根节点的输出就是查询的结果，我们将会在下节课讨论数据移动的粒度。
1 Sorting
关系模型是 unsorted 的，即 tuple 不会预先排序。在 ORDER BY, DISTINCT, GROUP BY, JOIN算子中，都有可能需要进行排序。
如果需要排序的数据在内存中可以放下，那么 DBMS 可以使用标准的排序算法 (e.g., 快速排序)。如果放不下，则需要使用external sorting，能够根据需要溢出到磁盘，并且倾向于顺序而不是随机 I/O。
如果查询包含 ORDER BY 和 LIMIT 语句，这就表明 DBMS 只需要扫描一次数据就可以找到前 N 个元素。这就是所谓的 Top-N Heap Sort。堆排序的理想场景是 top-N 元素能存到内存中，这样 DBMS 只需维护一个内存中的堆排序优先队列即可。
2 External Merge Sort
外部归并排序是一个分治排序算法，将数据分割成一些独立的 runs ，单独地对它们进行排序，接着将它们组合成一个更长的 runs 。可以将 runs 存到磁盘中，并在需要的时候读回来。(这里的一个 run 是指一系列 key/value pairs)
算法有两个阶段：
- Sorting: 将能放进内存中的小块数据进行排序，并将排序好的数据写回磁盘
- Merge: 将两个 (可能是多个，两个的叫做 two-way) 排好序的子文件合并成一个大文件
2.1 Two-way Merge Sort
最基本的版本是二路归并排序。“2” 表示每次将 2 个 runs 合并成一个大 run。
该算法在 Sorting 阶段读取每个页面，对其进行排序，并将排序后的版本写回磁盘。然后，在 Merge 阶段，它使用 3 个缓冲页。它从磁盘中读取两个排序的页面，并将它们合并到第三个缓冲区页面中。每当第三页填满时，它就会被写回磁盘并替换为空页。每组排序的页面称为一个 run。然后，算法递归地将 runs 合并在一起。
? 如下图，一开始一共有 8 个页，每个页是一个独立的 run，然后第一次遍历，也就是 pass0，先将每一个 run 都排好序；第二次遍历中，每次读取进两个相邻的长度为 2 的 run，然后进行合并，输出长度为 4 的排好序的 run（被放置在 2 个页中）；第三次遍历中，每次读取相邻两个长度为 4 的 run，然后进行合并，输出长度为 8 的排好序的 run（放置在 4 个页中）；第四次遍历中，将两个长度为 8 的run合并，最终生成长度为 16 的run（放置在 8 个页中），算法结束。
如果 N 是数据页的总数，该算法在数据中一共要进行 \(1+⌈???_2?⌉\) 次 pass (1 表示第一步先将所有页内的都排好序；\(⌈???_2?⌉\) 是合并过程中迭代的次数)。所有的 I/O 花费是 \(2?×\)(# ?? ????)，因为每个 pass 对每个页面都有一个 IO 读 + 写。
一个 pass 可理解为对数据的一次遍历。
2.2 General (K-way) Merge Sort
DBMS可以使用 3 个以上的缓冲页。
B 表示可用的缓冲页数量，Sorting 阶段，缓冲区可以一次性读进来 B 个页，并且将 \(\left \lceil \frac{N}{B} \right \rceil\) 个排好序的 runs 存进磁盘中；Merge 阶段，每次可以将 B - 1 个 runs 结合在一起，使用另一个缓冲页排序，写回磁盘。
算法一共需要遍历数据 \(1+\left \lceil log_{B-1}\frac{N}{B} \right \rceil\) 次 (1 是 Sorting 阶段，\(\left \lceil log_{B-1}\frac{N}{B} \right \rceil\) 是 Merge 阶段)，总 I/O 花费 \(2?×\)(# ?? ????)。
2.3 Double Buffering Optimization
外排序的一种优化方法是：在后台预获取下一个 run，并在系统处理当前 run 时，将其存储在第二个缓冲区中。这样通过连续使用磁盘减少了每一步I/O请求的等待时间。如在处理 page1 中的 run 时，同时把 page2 中的 run 放进内存。
这种优化需要使用多个线程，因为预获取应该在当前运行的计算过程中进行。
3 Using B+ Trees
如果我们要进行排序的属性，正好有一个构建好的B+树索引，那么可以直接使用B+树排序，而不是用外排序。
如果 B+ 树是 聚簇B+树，那么可以直接找到最左的叶子节点，然后遍历叶子节点，这样总比外排序好，因为没有计算消耗，所有的磁盘访问都是连续的，而且时间复杂度更低。
如果 B+ 树是 非聚簇B+树，那么遍历树总是更坏的，因为每个 record 可能在不同的页中，所有几乎每一个 record 访问都需要磁盘读取。
4 Aggregations
聚集算子就是将多个元组的单个属性的值计算成为单个标量值。
实现聚集有两种方法：(1) 排序, (2) 哈希。
4.1 Sorting Aggregation
DBMS首先对GROUP BY 上的 tuple (作为 key) 进行排序。如果所有内容都能放进 buffer pool，可以使用内排序算法（例如，快速排序），如果数据大小超过内存，则可以使用外部归并排序算法。然后 DBMS 对排序后的数据执行顺序扫描以计算聚集。聚集算子的输出将按 key 排序。
当执行排序聚集的时候，合理安排查询算子执行顺序对提高性能是很重要的。例如，如果查询是一个 filter (即选择)，那么先执行 filter 然后再排序，可以减小需要排序的数据量。
? 如下图，首先先进行 filter 操作，将 grade 是 B/C 的 tuple 筛选出来；然后进行投影操作，将无用的列去掉；然后进行排序，对排好序的结果进行聚集。
4.2 Hashing Aggregation
如果我们不需要数据最终是排好序的，如 GROUP BY 和 DISTINCT 算子，输出结果都不需要进行排序，那么 Hashing 是一个更好的选择，因为不需要排序，而且哈希计算更快。
DBMS 在扫描表时构建临时哈希表 (ephemeral hash table)。对于每个记录，检查哈希表中是否已经存在 enrty，并执行适当的修改。如果哈希表的大小太大，无法容纳在内存中，那么 DBMS 必须将其存到磁盘，有两个阶段来完成这个任务：
- Phase #1 – Partition:
使用哈希函数 \(h1\)，将元组划分成磁盘上的 partition，一个 partition 是指由同样 hash value 的 key 组成的一个或多个页。如果我们有 B 个 buffer 可以用，那么我们使用 B - 1 个 buffer 用来做 partition，剩下 1 个buffer 用来输入数据。 - Phase #2 – ReHash:
对于每一个在磁盘上的 partition，将它的页面 (可能是多个) 读进内存，并且用另一个哈希函数 \(ℎ2(ℎ1≠ℎ2)\) 构建一个 in-memory 哈希表。之后遍历哈希表每个 bucket，并将相匹配的 tuples 计算 aggregation。(这里假设了一个 partition 可以被放进内存)
在 ReHash 阶段，DBMS 可能存储形式为 (GroupByKey → RunningValue) 的 pair，以计算 aggregation，这些 pair 的具体形式取决于聚合函数。构建 in-memory 哈希表时，在哈希表中插入一个新 tuple：如果发现了一个匹配的 GroupByKey，就更新对应的 RunningValue；否则新建一个 (GroupByKey→RunningValue) pair。
? 首先是 Partition，因为我们要做DISTINCT，所以将这些元组按照 cid 作为 key 进行 partition，我们将这些 key 分为了B - 1 个 partition，然后将这些 partition 放入磁盘。
然后进行ReHash，因为在上一个阶段，一个 partition 内可能有碰撞，所以读入 partition 进行二次哈希，注意图中显示的，第一次哈希的一个 partition 可能有好几页。最终形成结果。
根据聚集任务不同，RunningValue 可能不一样，如果我们要进行 AVG 聚集，那么 RunningValue 就是 (COUNT, SUM)。在 ReHash 阶段，每次对一个 tuple 进行哈希，都更改哈希表中的对应 key 的 RunningValue 值。
参考链接
参考笔记：
CMU15445-Lec10 Sorting&Aggregation Algorithms
Lecture #10: Sorting & Aggregation Algorithms
- Aggregation Algorithms Lecture Sorting ampaggregation algorithms lecture sorting javascript algorithms sorting algorithms sorting csharp algorithms lecture joins 11 algorithms sorting algorithms sorting cpp algorithms sorting python algorithms sorting java aggregation high-efficiency neighborhood aggregation information