面临的问题：

我们设计的这个数据库是基于磁盘的，而实际处理数据需要用到内存，因此我们的算法需要去考虑我们此时想得到的数据可能不在内存中而在磁盘中。

External Merge Sort

外部归并排序。

排序算法将我们想要排序的数据集分成更小的数据块，称之为runs，然后其对runs单独排序。之后该算法会对runs进行合并得到更大的runs，直到最后整个数据集变为有序的。

Phase #1：我们会将尽可能多的数据块放入内存，并对它们进行排序，然后将排完序的结果写回磁盘。
Phase #2：我们会将排完序的runs结合。

2-way External Merge Sort

N为page数量。

number of passes = 1 + $\log_2N$

total I/O cost = 2N·(# of passes)

Double Buffering Optimization

当系统在排序当前的run时，预取下一个要用到的run到另一个buffer中，这样可以减少对于IO请求的等待时间。
![2-way external merge sort-0](images/2-way external merge sort-0.png)

General External Merge Sort

Pass #0

Use B buffer pages
Produce $\lceil N/B \rceil$ sorted runs of size B

Pass #1,2,3,…

Merge B-1 runs，因为有一个buffer pool用来保存输出结果

Number of passes: 1+ $\lceil \log_{B-1} \lceil N/B \rceil \rceil$

Total I/O cost: 2N·(# of passes)

![2-way external merge sort](images/2-way external merge sort.png)

Using B+ tree for sorting

如果数据表对于要排序的属性已经拥有一个b+树的索引，那么我们可以直接使用b+树来加速排序，DBMS只需要遍历b+树的叶子节点以此获得按特定顺序排列的tuple。对于b+树索引，有两种情况需要考虑，分别是clustered b+ tree和unclustered b+ tree。对于前者，其叶子节点的tuple按顺序排列在相近的page上，因此io消耗很小，但是对于后者由于不是聚簇索引，读取tuples所需要消耗的io成本过大，因此通常只使用clustered b+ tree。

Aggregations

聚合操作就是我们拿到一堆值，然后将它们合并起来生成一个标量值。

Sorting Aggregation

根据排序更快地去除一些重复值。

Hashing Aggregation

当对数据表进行扫描时，维护一个临时的hash table（只用于本次查询），对于每一个记录，检查该hash table中是否已经有一个相同key的条目，根据不同的聚合操作（distinct，group by），做不同的处理。

External Hashing Aggregate

hash table所需的内存可能不够，此时就要将部分数据写到磁盘上。对于这种情况，我们为了查询的速度，应当进行相应的处理。

Phase #1 - Partition

首先将数据拆分开到一个个的bucket中（基于hash key），当某个page满时将它们写到磁盘上。

假设我们拥有B个buffer，我们将使用B-1个buffer用于分区，1个buffer用于输入数据。

Phase #2 - ReHash

对每个分区中的数据重新做hash操作得到一个新的hash table，最后根据hash table得到最终结果。（为什么这样比sorting更高效呢？）