cmu15-445_Sorting&Aggregation

Sorting

我们需要排序，因为在关系模型中，表中的元组没有特定的顺序。排序（可能）按顺序BY、组BY、JOIN和不同的操作符使用。不仅仅是 order by 需要排序，像 DISTINCT 、GROUP BY 指令也需要有排序T这个需求。DISTINCT 指令的主要工作是先排序，然后去重。GROUP BY 是分组聚合指令，需要把相同的类型聚集在一起，更需要用到排序操作。

我们可以通过从左到右扫描叶节点，使用clustered B+树来加速排序。然而，如果我们使用一个unclustered B+树来排序，这是一个坏主意，因为它会导致大量的I/O读取（通过指针跟踪的随机访问）。

如果我们需要排序的数据可以装入内存，那么DBMS可以使用标准的排序算法（例如，快速排序）。如果数据不能全部装入内存，那么DBMS需要使用外部排序，它能够根据需要溢出到磁盘，并且更倾向于使用顺序排序，而不是随机I/O。

External Merge Sort

分治排序算法，将数据集划分为不同的运行，然后分别对它们进行排序。它可以根据需要将运行溢出到磁盘，然后一次读取它们。

下图是一个2路外部归并排序的例子，首先利用B个Page将所有的run在内存中排序. 这时由于run是有序的，每次可以只将run的一端部分数据放入内存留作Merge，内存中留出1个Page用于存放输出. 当内存中的run数据Merge完成后将run剩下的数据继续导入内存，之前生成的输出此时也可以刷到硬盘中，为新的输出留出空间.

上面的例子中，即使增加B的大小也不能提升多大的性能，原因在于前后I/O的开销并没有降低.此时我们若将计算与I/O时间重叠，那么就可以掩盖I/O传输带来的延时. 即当内存中对Page 1排序时同时开始将Page 2数据传输到内存中.算法推广到B-1路Merge算法，依然首先利用内存中的B个Page将N个数据划分成N/B个有序的run，然后利用B-1个Page对 N/B 个有序的run进行 B-1 Merge操作，留一个Page用于存放输出.

注意：若在这批数据上已经建立了B+树索引，由于B+树可以保证叶子节点有序且物理上连续存储，此时可以不用外部排序对数据进行排序. 但使用B+树代替外部排序有一个条件，B+树排序的Key必须要和本次查询的所需要聚合的属性一样，否则B+树对于本次查询而言它就是一个非聚簇索引.

若B+树排序的Key和本次查询的所需要聚合的属性不同，那么所需要聚合的Key此时并非连续存储.

Aggregation

聚合操作有两种实现方式，可以通过排序或者哈希两种方式实现.

例如下图中的例子，由于distinct也是聚合操作的一种，若数据有序则非常容易实现去重（一趟扫描，相同的Key舍去，不同的Key保留），且这时候去重后的键也是有序的.

若不要求去重后或者Group by的结果是有序的，那么使用基于哈希的聚合方法开销更低.

由于哈希函数特性，每次只需要检查哈希结果是否已经存在结果集中，若已经存在不加入结果集. 这是纯内存情况下的基于哈希的聚合方法，此处主要介绍设计面向磁盘的哈希聚合方法.

为了减小处理的中间结果集，与外部归并排序相似，也分为两个阶段：数据划分
和重Hash。在第一阶段中，利用哈希函数h1将数据划分为B-1个partition，此时相同Key的数据一定在同一个partition中。在第二阶段，使用哈希函数h2将partition中的值映射到一个哈希表中，若哈希表已经占满一个Page可以立即写入磁盘。

阶段1示例:

阶段二示例:

对于剩下数据生成的哈希表可以在插入到之前的哈希表中。

我们发现，第一阶段的哈希目的在于将数据划分到B-1个块中且每个块中的Key相同，此时不同数据块中的key一定不相同（相同Key的数据一定在相同的块中）. 此时若第二阶段顺序处理每个partition，当一个数据块处理完时若输出数据已经占满1个块被压入磁盘，因为后面的数据块中不会再出现相同Key的数据，这样也减少了哈希表冲突处理。

也可以在哈希表中添加其他的信息支持更多的查询功能：