CMU15-445数据库系统:排序与聚集

本文已收录于 CMU数据库系统学习笔记 系列,共计 11 篇,本篇是第 7 篇

课程小结

视频:https://www.bilibili.com/video/BV1Jq4y1B7ce/?spm_id_from=333.788

之前的课程中我们研究了存储引擎、缓存池和访问方法(哈希表与树索引)。本节开始研究算子。

研究四个议题:

  • 算子算法。例如 排序、join等具体是怎么执行的。
  • 用什么样的方案执行查询?
  • 数据库在执行的时候在内存中的运行架构?

执行计划

执行计划是树形的:

面向硬盘的数据库系统

需要注意的是本课程中的数据库系统是面向硬盘的,即假设硬盘存储巨量数据,不能指望这些面向硬盘的数据库系统所有的结果都保存在内存中

本节主要讨论两种算子,即排序和聚集。

为什么要排序?

因为数据库系统查询的返回值的顺序是不定的。如果不加 order by 就不要指望他有任何顺序,这是完全无序的。所以需要排序。

不仅仅是 order by 需要排序,像 DISTINCE 、GROUP BY 指令也需要有排序这个需求。

DISTINCE 指令的主要工作是先排序,然后去重。

GROUP BY 是分组聚合指令,需要把相同的类型聚集在一起,更需要用到排序操作。

排序算法

可以使用最常见的内部排序算法,冒泡排序、快速排序、归并排序等。前提是这些数据都能放在内存中。如果数据非常大呢?

外部归并排序

Early Materialization(早物化),意思是说key好比年龄,tuple data好比这个人的其他信息例如姓名、学号、班级等等信息,这些信息不是按年龄排序的key,但是我们也让这些信息跟随着key一同排序。

Late Materialization(晚物化):考虑到有些行数据的tuple data过多,一同排序比较影响效率,就只让key参与排序。

两路归并排序:

两路体现的是每次读取两个页,如果是三度就是每次读取三个页,三个页做merge操作。使用这种算法我们内存中只需要三个页就可以完成。

在MySQL中一个页才16kb,现在服务器的内存远不止这么少。改进优化:

  • 预读取,上一个page读取在内存中做排序的过程中,可以先预读取下一页:
  • 可以做N路归并排序,N代表页数、B代表缓存池。缓存池的大小越大,排序的轮数越少。

提醒:B+Tree 的叶子结点是已经排好序了,如果一个表中的字段他有主键了,并且是索引,那就说明这个字段在 B+Tree 中的叶子结点已经排好序了,直接用就行。——前面的聚簇讲过索引,可回顾——点击去ctrl + f搜索“聚簇”即可找到。

聚集算法

排序聚集:利用排序去做去重

先筛选,把 grade(等级)是B和C的sid和cid字段 筛选出来,然后做投影去除其他无用列,最后排序后删除(Remove Columns)重复的cid。

这样做可以通过排序来实现去重的目的。但是有些 DISTINCE  和 GROUP BY 操作是想涉及排序的,例如 DISTINCE 的目的仅仅是想去重,这时候如果我们非要进行排序就浪费了。下面使用哈希聚集可以解决这个问题。

外部的哈希聚集

先给我们要聚集的字段以它为key做一个哈希表。给他们映射到磁盘上。其核心思想是利用哈希碰撞

把碰撞的key放在同一个桶里。接下来需要 REHASH。因为相同key的因为碰撞放在了同一个桶中,但是还可能有的key就是因为本身hash函数导致的碰撞被放在了同一个桶中。——这不是我们想看到的。

REHASH(再次hash):将桶里的key进行第2次哈希,因为相同的key得到的hash一定也是相同的,所以可以把key本身不同导致的因为hash缺陷而误放在一个桶的key给筛选出来,剩下的在一个桶里的一定就是key相同的key了。

上面的外部哈希聚集是单纯解决去重问题的,那如果是聚集起来是为了计算呢?例如下面的SQL是为了计算平均值:

解决方法就是记录中间结果,二次hash table中再增加一列value列, value 记录下 (个数, 总和),如果是平均值就保存个数和总和;如果是min就保存最低值;如果是sum就保存总和 … …最后再根据计算函数进行计算即可。

这样我们就解决了聚集计算(GROUP BY)的问题。

作者: 高志远

高志远,23岁,男生,毕业于上海杉达学院电子商务系。

发表评论

邮箱地址不会被公开。