lecture 10 -11

接下来来讲讲Query。在数据库当中，发出查询的请求后，query plan会被储存为树的形式。

为什么我们需要规划算法？

1. 因为我们要保证数据库尽可能的I/O少，以达到效率高的目的，所以我们需要对数据进行排序。

2. 我们需要对数据进行聚合，因为disk里面的内容远比memory的空间要大太多，我们的buffer pool里面总共才几个slot，根本存不了多少的数据，所以在键值对数量固定的情况下，我们就可以将多个数据聚合成一个作为value存储在键值对当中。

Sorting

排序算法没什么好讲的，就跟那种基本算法里面给数组排序类似的，有quick sort, merge sort等等。然后这里还有几个merge sort的变种分类，Two-way Merge Sort和General (K-way) Merge Sort，这个也没什么好讲的。

Aggregation

聚合也有两种方法，一种sorting，一种hashing。

一般来说hash远多于sort。哈希在计算上可能比计算聚合的排序更便宜。DBMS在扫描临时哈希表时填充该表。对于每条记录，检查哈希表中是否已经有条目，并执行适当的修改。如果哈希表的大小太大，无法放入内存，则DBMS必须将其溢出到磁盘。

实现这一目标有两个阶段:

1. Partition: 使用哈希函数h1根据目标哈希键将元组划分为磁盘上的分区。这将把所有匹配的元组放在同一个分区中。假设总共有B个缓冲区，我们将有B-1个用于分区的输出缓冲区和1个用于输入数据的缓冲区。如果任何分区已满，DBMS将把它溢出到磁盘
2. ReHash: 对于磁盘上的每个分区，将其页面读取到内存中，并基于第二个哈希函数h2（其中h1<>h2）构建内存中的哈希表。然后遍历这个哈希表的每个bucket，将匹配的元组聚集在一起计算聚合。这假设每个分区都适合内存

Join

朴素实现是用笛卡尔积的方式，然后对笛卡尔积进行过滤。但是笛卡尔积的大小是指数增长的，所以效率很低。具体的代码实现，就是用两个嵌套的for循环去遍历两张表，去比较 ON 后面的条件一致与否，进行join。时间复杂度是O(n^2)的。

优化的办法是采用制作Hash Table的方式，先将一个表hash化，也就是将同样key(这个key就是 ON 后的条件)的放在同一个value数组里面；再对另外一个表进行插入，如果存在相同的key，则将value插入到value数组里面。这样的话，时间复杂度就降低到了O(n)。