查询计划
到目前为止，我们主要讨论的是访问方法（即如何通过索引或扫描找到数据）。现在，我们需要讨论如何真正执行这些查询。
数据库系统会将 SQL 语句编译成查询计划，查询计划是一个由算子组成的树状结构。我们将在后续的查询执行课程中详细讲解这部分内容。
对于面向磁盘的数据库系统，我们将利用缓冲池来实现那些在处理过程中需要溢出到磁盘的算法，我们的核心目标是尽可能减少算法的 I/O 次数。
排序
由于在关系模型中，表中的元组没有特定的顺序，因此 DBMS 需要对数据进行排序。排序（潜在地）被用于 ORDER BY、GROUP BY、JOIN 和 DISTINCT 算子。如果待排序的数据能全部装入内存，DBMS 可以使用标准排序算法（如快速排序）。如果数据量太大无法装入内存，则需要使用外部排序（如归并排序），该算法能够根据需要将数据溢出到磁盘，并且相比随机 I/O，它更倾向于使用顺序 I/O。
如果查询包含带有 LIMIT 的 ORDER BY，DBMS 只需扫描一次数据即可找到前 N 个元素。这被称为 Top-N 堆排序。堆排序的理想场景是前 N 个元素可以装入内存，这样 DBMS 在扫描数据时，只需在内存中维护一个排序好的优先级队列即可。
对于大到无法装入内存的数据，标准排序算法是外部归并排序。这是一种分治算法，它将数据集分割成独立的初始轮次并分别进行排序。它可以根据需要将这些轮次溢出到磁盘，然后一次读回一个进行处理。该算法包含两个阶段：
- 排序：首先，算法对能装入主存的小块数据进行排序，然后将排序后的页面写回磁盘。
- 归并：然后，算法将排序后的子文件合并成一个更大的单一文件。
注：什么是溢出？溢出是指当 RAM 不足以容纳当前处理的数据时，系统被迫将数据暂时写入硬盘的行为。
排序轮次可以是早物化的（即具体数值直接存储在页面中），也可以是晚物化的（即轮次中仅存储记录 ID/RID，稍后再读取具体数值）。
二路归并排序
归并排序最基础的版本是二路归并排序。
- 排序阶段：算法读取每个页面，对其内部数据进行排序，然后将排序后的版本写回磁盘。
- 归并阶段：算法使用三个缓冲页：
- 从磁盘读入两个排序好的页面（作为输入）。
- 将它们合并到第三个缓冲页（作为输出）中。
- 每当第三个页面填满时，就将其写回磁盘并重置为空白页。
- Run（轮次/归并段）：每一组排序好的页面被称为一个 Run。算法随后递归地将这些 Run 合并在一起。
开销分析
如果 N 是总页面数，该算法的性能指标如下。
- 遍历次数：总共需要进行 $(1 + \log_{2}N)$ 次遍历。其中一次用于初始排序，$\log_{2}N$ 用于递归归并。
- 总 I/O 开销：$2N \times$ 遍历次数，这是因为在每一次遍历中，每个页面都要执行一次 I/O 读取和一次 I/O 写入。
注：更准确的说，这是因为在每一次遍历中，每个元组都要执行一次读取和写入。
通用 K 路归并排序
通用版本的算法允许 DBMS 利用三个以上的缓冲页。假设 B 是可用的缓冲页总数。那么：
- 排序阶段：算法可以一次读取 B 个页面，并向磁盘写回 $N/B$ 个排序好的 Run。这里的 Run 就是最小有序单位，即递归深入的终点。
- 归并阶段：每次遍历可以合并多达 K 个 Run，同样使用一个缓冲页存放合并后的数据，并根据需要写回磁盘。
在通用版本中，算法执行 $(1 + \lceil \log_{B-1} \lceil N/B \rceil \rceil)$ 次遍历，总 I/O 开销依然是 $2N \times$ 遍历次数。
注：K=B-1，因为在归并阶段，必须要有 K 个页面来存放来自 K 个不同 Run 的当前数据，同时留出一个页面来存放归并后的结果。
二路归并时需要有两个指针，然后比较这两个指针上的最小值（假如是从小到大排序）并填入归并后的页面。而 K 路归并则需要 K 个指针。
$(1 + \lceil \log_{B-1} \lceil N/B \rceil \rceil)$ 如何得出：排序阶段之后我们有 N/B 个 Run，每次合并 K 个 Run，再加上到达初始阶段的那个 1，就是那个遍历次数的公式。
优化手段
- 双缓冲优化：外部归并排序的一种优化手段是预取，在系统处理 Run 的同时，后台预取下一个 Run 并将其存储在第二个缓冲区中。通过持续利用磁盘，这减少了每一步等待 I/O 请求的时间。这种优化需要使用多线程，因为预取应该在处理当前 Run 的计算逻辑时同步发生。
