接下来将学习使用我们现在学习的 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 合并在一起。
标签：Sorting,run,partition,Algorithms,哈希,磁盘,Lecture,排序 From： https://www.cnblogs.com/angelia-wang/p/17311613.html