接下来将学习使用我们现在学习的 DBMS 组件来执行查询。
我们今天要讨论的算法都是基于 Disk 的,即查询的中间结果也需要存储到磁盘中。我们需要使用 Buffer Pool 去实现这些算法,要最大化磁盘连续 I/O。
![image-20230412175554237](https://fastly.jsdelivr.net/gh/Angelia-Wang/blogImage/img/image-20230412175554237.png)
Query Plan:算子组织成树形结构,数据从叶子节点流向根节点,根节点的输出就是查询的结果,我们将会在下节课讨论数据移动的粒度。
![image-20230412175858472](https://fastly.jsdelivr.net/gh/Angelia-Wang/blogImage/img/image-20230412175858472.png)
1 Sorting
关系模型是 unsorted 的,即 tuple 不会预先排序。在 ORDER BY
, DISTINCT
, GROUP BY
, JOIN
算子中,都有可能需要进行排序。
如果需要排序的数据在内存中可以放下,那么 DBMS 可以使用标准的排序算法 (e.g., 快速排序)。如果放不下,则需要使用external sorting,能够根据需要溢出到磁盘,并且倾向于顺序而不是随机 I/O。
如果查询包含 ORDER BY
和 LIMIT
语句,这就表明 DBMS 只需要扫描一次数据就可以找到前 N 个元素。这就是所谓的 Top-N Heap Sort。堆排序的理想场景是 top-N 元素能存到内存中,这样 DBMS 只需维护一个内存中的堆排序优先队列即可。
2 External Merge Sort
外部归并排序是一个分治排序算法,将数据分割成一些独立的 runs ,单独地对它们进行排序,接着将它们组合成一个更长的 runs 。可以将 runs 存到磁盘中,并在需要的时候读回来。(这里的一个 run 是指一系列 key/value pairs)
算法有两个阶段:
- Sorting: 将能放进内存中的小块数据进行排序,并将排序好的数据写回磁盘
- Merge: 将两个 (可能是多个,两个的叫做 two-way) 排好序的子文件合并成一个大文件
2.1 Two-way Merge Sort
最基本的版本是二路归并排序。“2” 表示每次将 2 个 runs 合并成一个大 run。
该算法在 Sorting 阶段读取每个页面,对其进行排序,并将排序后的版本写回磁盘。然后,在 Merge 阶段,它使用 3 个缓冲页。它从磁盘中读取两个排序的页面,并将它们合并到第三个缓冲区页面中。每当第三页填满时,它就会被写回磁盘并替换为空页。每组排序的页面称为一个 run。然后,算法递归地将 runs 合并在一起。
标签:Sorting,run,partition,Algorithms,哈希,磁盘,Lecture,排序 From: https://www.cnblogs.com/angelia-wang/p/17311613.html