聚合

1.简介¶

聚合函数对一组值执行计算，并返回单个值。

聚合首先要对表进行分组，分组的常用方式有排序和哈希。

排序首先对表进行排序，然后对表进行顺序扫描，并计算结果。

这种做法的问题在于排序本身的成本是较大的，如果我们不需要基于排序的表才能得出计算结果，那么进行多路排序和维护一个中间结果都是较大的消耗。

更具体的名字为External Hashing Aggregate，思想是通过哈希函数对问题进行规模拆分，然后在规模更小的子集中对问题进行处理。

在聚合过程中会维护一个中间哈希表。由于哈希表没有顺序性，因此在维护该哈希表的过程中会产生许多随机I/O。步骤设计的目的的是最大化每个page可以做的工作量，以便于减少磁盘交互，尽可能在内存中进行工作。

拥有两个步骤：

Partition：维护多个bucket，通过哈希函数决定tuple被存放到哪个bucket中，每个拥有相同key的tuple都会被存到同一个bucket中。这一步的目的是拆分数据规模。
ReHash：对于每个bucket，读取他们的数据并以此建立哈希表，然后对表中同一个key的tuple进行计算。由于第一部中已经进行了规模拆分，因此哈希表与磁盘的交互就更少。