10.2.2　单表操作

单表相关的物理运算符包括：

●TableScan：扫描某个表格，MergeServer将扫描请求发给请求的各个子表所在的ChunkServer，并将ChunkServer返回的结果按照子表范围拼接起来作为输出。如果请求涉及多个子表，TabletScan可由多台ChunkServer并发执行。

●Filter：针对每行数据，判断是否满足过滤条件。

●Projection：对输入的每一行，根据定义的输出表达式，计算输出结果行。

●GroupBy：把输入数据按照指定列进行聚集，对聚集后的每组数据可以执行计数（count）、求和（sum）、计算最小值（min）、计算最大值（max）、计算平均值（avg）等聚集操作。

●Sort：对输入数据进行整体排序，如果内存不够，需要使用外排序。

●Limit（offset,count）：返回行号在[offset,offset+count）范围内的行。

●Distinct：消除某些列相同的重复行。

GroupBy、Distinct物理操作符可以通过基于排序的算法实现，也可以通过基于哈希的算法实现，分别对应HashGroupBy和MergeGroupBy，以及HashDistinct和MergeDistinct。下面分别讨论排序算法和哈希算法。

1.排序算法

MergeGroupBy、MergeDistinct以及Sort都需要使用排序算法。通用的＜key,value＞排序器可以分为两个阶段：

●数据收集：在数据收集阶段，调用者将＜key,value＞对依次加入到排序器。如果数据总量超过排序器的内存上限，需要首先将内存中的数据排好序，并存储到外部磁盘中。

●迭代输出：迭代第一行数据时，内存中可能有一部分未排序的数据，磁盘中也可能有几路已经排好序的数据。因此，首先将内存中的数据排好序。如果数据总量不超过排序器内存上限，那么将内存中已经排好序的数据按行迭代输出（内排序）；否则，对内存和磁盘中的部分有序数据执行多路归并，一边归并一边将结果迭代输出。

2.哈希算法

HashGroupBy以及HashDistinct都需要使用哈希算法。假设需要对＜key,value＞对按照key分组，那么首先使用key计算哈希值K，并将这个＜key,value＞对写入到第K个桶中。不同的key可能对应相同的哈希桶，因此，还需要对每个哈希桶内的＜key,value＞对排序，这样才能使得key相同的元组能够连续迭代出来。哈希算法的难点在于数据总量超过内存上限的处理，由于篇幅有限，请自行思考。