CMU15445 Lecture 10 Sorting + Aggregations

本节主要介绍Operator Execution

Sorting

对于查询的中间结果也有可能放到磁盘中，比如查询中国人的相关信息（10+亿）
对于DBMS的操作，更加偏好具有sequential I/O的算法

外部排序（外部归并排序)每次两个页是2way外部归并排序

• 先把每个页的内部排序，塞到内存中排序
• 之后每次塞两个页到内存，不停的两个页的归并排序

聚簇B+树(clustered B+Tree),与非聚簇B+树
早物化与晚物化

Aggregation

Sorting Aggregation很简单
还可以Hahsing Aggregation，Hashing Aggregatin更好，因为它不需要排序，时间复杂度更低

对于需要用到磁盘的Hashing Aggregation需要用到extrenal Hashing Aggregation，分为两步：

• Partition
  对于第一个hash，只要是hash的key都会放到相同的桶里，就是首先不处理碰撞，当一个页中的重复项过多，可以提前做去重，也就是distinct

对于AVG， 需要记录个数与总和，因为如果添加了新的tuple之前记录就没用了

• ReHash
  第一个应该就是指外部归并排序过程中已经排序好的中间结果