数据库中的排序
我们需要排序，因为在关系模型中，表中的元组没有特定的顺序排序，但可能在ORDER BY，GROUP BY，JOIN和DISTINCT运算符中使用。
我们可以通过从左到右扫描叶子节点来使用群集B +树加速排序。 但是，如果我们使用非聚集B +树进行排序，这是一个坏主意，因为它会导致大量I / O读取（通过指针追踪随机访问）。
如果我们需要排序的数据适合内存，那么我们可以使用标准排序算法，如quicksort。 如果数据不合适，我们需要使用能够根据需要溢出到磁盘的外部排序。
外部排序
外部排序 分为2个部分。首先在内存里排序部分data然后写入磁盘。 随后把小块的文件合并成一个排完序的大文件。
2路归并
第1个pass：把每B个 PAGES(B 取决于buffer pool 支持的最大page 数量）读到内存。排序，随后把他们写回磁盘。每一个排序的page组称为一个run
之后的pass：递归的合并每一对run，成为下一个run。每一次都会少掉一般的run。
image.png
number of pass的公式 比较直接因为是指数级减少，所以就是log，n 是page总数。
io次数主要每一个pass里都会涉及到一次读一次写。
所以是2n （# of passes)
2路归并的问题在于 只利用了3个buffer page，2个读，一个写。 有更多的就用不到。没有有效的利用整个buffer pool。
k路归并
读完b个page之后，对这整个page做排序。
随后在合并的时候，n/b 个大page要merge
image.png
在合并的时候，我们可以用b-1个来并发。因为还要留一个page去写。
所以有上图公式。
还有一些情况可以不用外部排序，比如说是聚集的b+树索引。我们可以简单去遍历树的叶子节点来做聚合。但是非聚集的索引就不方便。
image.png
image.png
聚合
一般聚合函数又sum,count,min,max等。
实现聚合的主要手段又2种。一种是排序，一种是hash
排序
首先对GROUP BY键上的元组进行排序。 如果内存足够，则放入缓冲池,使用内存排序算法（例如，快速排序）
如果数据大小超过内存，外部合并排序算法。
然后，DBMS对已排序的数据执行顺序扫描以计算聚合。 operator的输出将按key排序。
image.png
hash
散列计算聚合比排序计算聚合更高效。 DBMS在扫描表时填充哈希表。 对于每条记录，检查哈希表中是否已有条目并执行适当的修改。
如果哈希表的大小太大而无法容纳在内存中，那么DBMS必须将其溢出到磁盘：
- 阶段＃1：分区
- 使用散列函数h1将元组拆分为基于目标散列键的磁盘上的分区。 这会将匹配的所有元组放入同一个分区。 DBMS通过输出缓冲区将分区溢出到磁盘。
- 阶段＃2：ReHash
- 对于磁盘上的每个分区，将其页面读入内存并基于第二个散列函数h2（其中h1 != h2）构建内存中的散列表。 然后遍历此哈希表的每个桶，将匹配的元组汇集在一起以计算聚合。 请注意，这假设每个分区都适合内存。
在ReHash阶段，DBMS可以存储表单对（GroupByKey→RunningValue）来计算聚合。 RunningValue的内容取决于聚合函数。 要将新元组插入哈希表：
•如果我们找到匹配的GroupByKey，只需适当更新RunningValue。
•否则插入新的（GroupByKey→RunningValue）对。
image.png
网友评论