Lec 11-16¶
Lec 11 Sorting & Aggregation¶
我们即将讨论如何使用DBMS components来执行queries.
operators是以树状排列的，data从leaves向root流动. root node的输出结果就是query的结果.
我们不能假定query能直接fit in到memory中，所以需要使用buffer pool 来实现相关的处理算法. 同时，我们希望算法能最大化串行I/O的数量.
Sorting¶
Relational Model/SQL是unordered，但queries本身经常会调用ORDER BY/DISTINCT/GROUP BY指令，因此我们需要将排序纳入考虑. 需要注意的是，DBMS中的排序是 In-Memory Sort.
如果data能恰好被memory容纳，那并不会有什么多余的问题，我们只需要使用标准的排序算法，如VergeSort (针对大部分数据已经排好序了)，QuickSort, TimSort, RadixSort等等算法.
但是如果data不能恰好被memory容纳，我们就得想想别的办法了，需要尽可能考虑reading/writing disk pages的开销.
对于一个给定的run（比如vector<pair<key,value>>这种形式），排序是基于comparison function和sorting parameters的.