本文主要是介绍【CMU 15-445】Lecture 10: Sorting Aggregations Algorithms 学习笔记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Sorting & Aggregations Algorithms
- Sorting
- Top-N Heap Sort
- External Merge Sort
- 2-WAY External Merge Sort
- K-WAY External Merge Sort
- Double Buffering Optimization
- Aggregations
- Sorting
- Hashing
本节课主要介绍的是数据库系统中的排序算法以及聚合算法
Sorting
排序算法分为两种:如果内存能够容纳一个关系的所有tuple
,那么可以用任意的标准排序算法在内存中进行排序,如插入排序、快速排序等等;如果内存无法容纳一个关系的所有tuple
,则只能使用外排序。
Top-N Heap Sort
如果一个查询包含ORDER BY加上LIMIT关键字的组合,则可以使用Top-N堆排序的做法,如下图所示,推排序的细节就不多讲了。
External Merge Sort
一种外排序算法是外部归并排序,主要分为以下两个步骤:
- Divide:将文件中的记录分为若干个归并段,使得每个归并段都能被加载到内存中进行单独排序
- Conquer:将若干个有序的归并段merge成最终结果
2-WAY External Merge Sort
一个简单的merge做法是二路归并,如下图例子所示,每次merge合并两个归并段,以此类推直到所有归并段合成一个段为止。在二路归并做法中,只需要内存提供三个缓存页(两个用于加载待merge的归并段,一个用于存放merge结果)。我们可以简单的估计该做法的IO复杂度,假设存放tuple
的page
数量为 N N N,则我们最多需要做 ⌈ l o g 2 N ⌉ \lceil log_2N \rceil ⌈log2N⌉次归并,且每次归并需要对每个page
进行读写,共计 2 N 2N 2N次IO操作,故总复杂度为 2 N ∗ ( 1 + ⌈ l o g 2 N ⌉ ) 2N*(1+\lceil log_2N \rceil) 2N∗(1+⌈log2N⌉)(需要加上第一次做内部排序的IO)
K-WAY External Merge Sort
更进阶的做法是将二路归并扩展至K路归并,因为二路归并中没有充分利用内存缓冲区(只是用了三页缓冲页)。假设内存缓冲页数量为 B B B,可以在排序阶段就充分利用缓冲页进行优化,一次性加载 B B B个page
进行排序,相当于把 B B B个page
合成一个归并段了,这样子在开始归并之前就只有 ⌈ N B ⌉ \lceil \frac{N}{B} \rceil ⌈BN⌉个归并段;在归并阶段,最多可以利用 B − 1 B-1 B−1个缓存页进行多路归并(需要预留一个缓存页存放归并结果)。于是,最多只需执行 ⌈ l o g B − 1 ⌈ N B ⌉ ⌉ \lceil log_{B-1}\lceil \frac{N}{B} \rceil \rceil ⌈logB−1⌈BN⌉⌉次归并,每次归并的IO次数仍为 2 N 2N 2N,故总复杂度为 2 N ∗ ( 1 + ⌈ l o g B − 1 ⌈ N B ⌉ ⌉ ) 2N*(1+\lceil log_{B-1}\lceil \frac{N}{B} \rceil \rceil) 2N∗(1+⌈logB−1⌈BN⌉⌉)(需要加上第一次做内部排序的IO)
Double Buffering Optimization
可以使用两个buffer,当其中一个buffer在做排序处理时,将下一步需要处理的数据预加载到另一个buffer中,充分利用CPU与IO资源。
Aggregations
聚合操作一般有两种实现方式:排序以及哈希。
Sorting
在聚合的排序实现方式中,算法首先按照GROUP BY的key
对tuple
进行排序,使用第一节所讲的内排序或外排序。然后按序遍历元组进行聚合(因为此时相同key的元组处于相邻位置)
Hashing
在很多情况下,聚合操作并不要求元组是有序的,可以使用效率更高的哈希实现方法进行替代。哈希实现方式分为两个步骤:
- Partition:首先使用哈希函数
h1
将所有tuple
按照GROUP BY的key
进行分区(若内存中有 B B B个缓存页,则分为 B − 1 B-1 B−1个分区) - ReHash:对于每一个分区,使用哈希函数
h2
在内存中建立哈希表,并维护聚合所需信息(如最小值、总和等)
一个简单的例子如下图所示,如果想要求每一个分组的平均值,则在ReHash阶段,需要维护COUNT和SUM以便最后算出平均值。
这篇关于【CMU 15-445】Lecture 10: Sorting Aggregations Algorithms 学习笔记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!