我们现在将讨论如何使用迄今为止讨论过的 DBMS 组件来执行查询。
1 查询计划【Query Plan】
我们首先来看当一个查询【Query】被解析【Parsed】后会发生什么?
当 SQL 查询被提供给数据库执行引擎,它将通过语法解析器进行检查,然后它会被转换成关系的代数表示,需要注意的是,这个代数表示是得到优化过后的。
大概解释一下这棵树:
- R 和 S 是两张表,也可以说是两个关系
- 首先对 S 表做查询,条件谓词 value > 100
- 然后将 S 表与 R 表做 join ,连接的条件是 S.id = R.id
- 最后对联表生成的关系做映射,只取R.id和S.cdata两列输出的到结果中
我们得到了用树形表示的查询,树的每一个节点都是一个操作符。数据从树的叶子向上流向根,根节点的输出就是查询的结果。
那么我们想用算法对这些操作符做什么呢??
- 就像不能假设表完全可以被内存容纳下来一样,面向磁盘的 DBMS 也不能假设查询结果(设置时中间结果)可以被内存容纳。
- 我们将使用缓冲池来实现需要溢出到磁盘的算法,即内存不足以承载(中间)结果集时。
- 我们还将更喜欢能够最大化顺序 I/O 量的算法。
2 为什么我们需要排序
关系型模型【Relational model/】/SQL 是无序的【unsorted】。
但是查询【Query】可能要求元组以特定方式排序(ORDER BY)。
但即使查询没有指定顺序,我们可能仍然想要排序来做其他事情:
- 轻松支持重复消除(DISTINCT)。
- 将排序元组【sorted tuples】批量加载到 B+Tree 索引中的速度更快。
- 聚合(GROUP BY)。
3 内存排序
如果内存足以容纳数据,那么我们可以使用标准排序算法,例如快速排序。
大多数数据库系统使用快速排序进行内存排序。
在其他数据平台中,尤其是 Python,默认排序算法是 TimSort。 它是插入排序和二元归并排序的结合。 通常在真实数据上效果很好。
如果内存不足以容纳数据,那么我们需要使用一种能够感知读取和写入磁盘页面成本的技术。
4 排序算法
今天我们主要讲下面几个算法:
- Top-N 堆排序【Top-N Heap Sort】
- 外部归并排序【External Merge Sort】
- 聚合【Aggregations】
4.1 Top-N 堆排序【Top-N Heap Sort】
如果查询【Query】中包含带有 LIMIT 的 ORDER BY,则 DBMS 只需扫描数据一次即可找到前 N 个元素。
堆排序的理想场景:如果 topN 元素适合内存。
- 扫描一次数据,在内存中维护一个排序的优先级队列。
1️⃣ 我们扫描数据
2️⃣ 并将其设置到堆排序的数组中
3️⃣ 当我们扫描到 9 时,由于我们只取最小的 4 个元素,因此9直接在内存中被跳过
4️⃣ 而碰到元素1后,他会改变我们的堆排序数组
4.2 外部归并排序
分而治之算法,将数据分成单独的 runs ,分别对它们进行排序,然后将它们组合成更长的排序了的 runs。
第 1 阶段 – 排序
- 对适合内存的数据块进行排序,然后将排序后的数据块写回到磁盘上的文件中。
第 2 阶段 – 合并
- 将排序后的 runs 合并成更大的 chunks。
run 是键/值对的列表。
key:用于比较以计算排序顺序的属性【attribute】。
value:有两种选择
- 元组(早期的物化)。
- 记录 ID(后期的物化)。
4.2.1 2路外部归并排序
我们将从 2 路外部归并排序的简单示例开始。
- 其中,“2”是我们每次合并的 run 的数量
数据被分成 N 页。
DBMS 有有限数量的 B 个缓冲池页来保存输入和输出数据。
栗子:
我们有 N 页的数据,而 DBMS 有一个 B 页大小的缓冲池来保存输入和输出数据。
Pass 0
- 将表的所有 B 页【pages】读入内存
- 对页【page】进行排序并将其写回磁盘
Page 2,3,,,
- 递归地将一对 run 合并为两倍长的 run
- 使用三个缓冲区页面(2 个用于输入页面,1 个用于输出页面)
在每次一次传递【Pass】中,我们都要读写每一个页。
总的传递【Pass】数:= 1 + ⌈ log2 N ⌉
总的 IO 花费 = 2N · (# of passes)
该算法仅需要三个缓冲池页面来执行排序(B=3)。
- 两个输入页面,一个输出页面
但是,即使我们有更多可用 Buffer Pool 空间 (B>3),如果工作线程【worker】必须阻塞磁盘 I/O,那么依然无法有效利用它们。
双缓存优化
当系统处理当前 run 时,在后台预取下一次的 run 并将其存储在第二个缓冲区中。通过持续利用磁盘来减少每个步骤中 I/O 请求的等待时间。
通用外部归并排序
Pass 0
- 使用 B 个 缓冲页
- 产生 ⌈N / B⌉ 个 B 大小的有序 run
Pass #1,2,3,…
- 归并 B-1 个 runs (i.e., K-way merge)
总的传递【Pass】数:= 1 + ⌈ logB-1 ⌈N / B⌉ ⌉
总的 IO 花费 = 2N · (# of passes)
栗子:
确定使用大小为 5 页的 Buffer Pool 来排序占用 108 页的数据,需要经过几次传递【Pass】?
Pass #0: ⌈N / B⌉ = ⌈108 / 5⌉ = 22 个 5 页大小的排好序的 run
Pass #1: ⌈N’ / B-1⌉ = ⌈22 / 4⌉ = 6 个 20 页大小的排好序的 run(最后一个 run 只有3页)
Pass #2: ⌈N’’ / B-1⌉ = ⌈6 / 4⌉ = 2 个排好序的 run ,第一个有 80 页大小,第二个只有 28 页
Pass #3: Sorted file of 108 pages
1+⌈ logB-1⌈N / B⌉ ⌉ = 1+⌈log4 22⌉ = 1+⌈2.229...⌉ = 4 passes
比较优化
方法1:代码特化/硬编码:不要提供比较函数作为排序算法的指针,而是创建特定于键类型的硬编码版本的排序。
方法2:后缀截断:首先比较长 VARCHAR 键【key】的二进制前缀,而不是较慢的字符串比较。 如果前缀相等,则回退到较慢的版本。
4.3 使用 B 树进行排序
如果需要排序的表在排序属性上已经有 B+Tree 索引,那么我们可以使用它来加速排序。
只需遍历树的叶节点所在的页,即可按所需的排序顺序检索元组。
需要考虑下面两种情况:
- 聚簇 B+树
- 非聚集B+树
聚簇索引
遍历到最左边的叶节点的页,然后从所有叶节点的页中检索元组。
这种办法总是比外部归并排序更好,因为没有计算成本,并且所有磁盘访问都是顺序的。
非聚簇索引
这几乎总是一个坏主意。因为在非聚簇索引种,我们需要追踪指向包含数据的页面的每个指针。
一般来说,每个数据记录一个 I/O,这是随机 IO 的灾难。
5 聚合
聚合是一种函数【function】,将多个元组中单个属性的值折叠为单个标量值【scalar value】。比如 min / max / sum / count /avg。
当我们要实现这些聚合时,我们需要找到一种方法,让DBMS系统快速找到与我们试图在其上构建聚合的属性具有相同值的元组,这样我们就可以对它们进行分组【grouping】计算我们想要的聚合函数。
两种实现选择:
- 排序
- 哈希,哈希的方案一般是要比排序更好的,尤其是当你的操盘速度很慢时(最小化IO)。
5.1 排序聚合
我们以一个栗子开始,这是我们的表:
我们要在该表上查询特定条件下不重复的 cid
SELECT DISTINCT cid
FROM enrolled
WHERE grade IN ('B','C')
ORDER BY cid
首先,我们遍历表,我们要应用 where 子句中的过滤条件,来找到所有成绩为 B 和 C 的元组
然后我们做一个映射【Projection】,因为我们不需要所有的属性,我们应用映射,只保留 cid
最后,我们对这个单列【column】进行应用排序,现在要生成最终结果,我们只需要扫描排序产生的输出,并跟踪我在光标处看到的最后一个值是什么,然后如果我遇到了和我之前看到的相同的值,那么我知道,它是重复的,我可以把它扔掉。
5.2 排序的替代方案
如果我们不需要数据有序的话,排序可能并不是最好的方案,那么这该怎么办?
- 在 GROUP BY 中形成组(无顺序)
- 删除 DISTINCT 中的重复项(无顺序)
在这种情况下,哈希散列是更好的选择。
- 只需要去重,无需排序。
- 计算成本比排序更便宜。
5.3 哈希聚合
当 DBMS 扫描表时填充临时哈希表。 对于每条记录,检查哈希表中是否已有条目:
- DISTINCT:丢弃重复项
- GROUP BY:执行聚合计算
如果内存足够容纳着一切数据,那么这很容易。
如果 DBMS 必须将数据溢出到磁盘,那么我们需要变得更智能一点。
外部哈希聚合【External Hashing Aggregation】
第 1 阶段 – 分区【Partition】
- 根据哈希键将元组【tuple】划分为桶【bucket】
- 当它们已满时将它们写到磁盘
使用哈希函数 h1 将元组拆分为磁盘上的分区【Partition】。
- 分区是包含具有相同哈希值的一组键的一个或多个页面,它是一种逻辑分组
- 分区通过输出缓冲区“溢出”到磁盘
假设我们有 B 个缓冲区。 我们将使用 B-1 个缓冲区用于输出数据,即用于分区【Partition】,1 个缓冲区用于输入数据。
我们继续复用用排序聚合时的栗子:
我们首先对数据做条件过滤没然后只保留满足条件的元组:
然后通过映射【Projection】删除无用的列
我们对 cid 应用哈希函数
阶段 #2 – ReHash
- 为每个分区构建内存哈希表并计算聚合
对于磁盘上的每个分区:
- 我们要将该分区的所有页面读入内存,逐一扫描它们,并基于第二个哈希函数 h2 构建内存中哈希表。
- 然后遍历该内存哈希表的每个存储桶,以将匹配的元组组合在一起。
我们这里假设每个分区都适合内存大小。
我们继续基于第一阶段产出的分区,进行第二阶段的操作:
1️⃣ 首先我们对每一个分区应用哈希函数 h2,并写入专属于自己分区的哈希表中,需要注意的是,这个哈希表不是简单的原样存储,而是针对聚合函数的特定实现。
2️⃣ 在将一个分区rehash完,我们再将内存哈希表中的每一个桶中的值,写入到最终结果集中
3️⃣ 在一个分区操作完之后,继续执行下一个分区,循环往复,直到所有分区都处理完。
在 ReHash 阶段,存储(GroupKey→RunningVal) 形式的序对【Pair】。
当我们想在哈希表中插入一条新的元组时:
- 如果我们找到匹配的 GroupKey,我们只需要适当的更新RunningVal
- 否则,插入一条 GroupKey→RunningVal
下面我们举个例子来解释一下,我们使用一个新的查询【Query】
SELECT cid, AVG(s.gpa)
FROM student AS s, enrolled AS e
WHERE s.sid = e.sid
GROUP BY cid
1️⃣ 我们先对数据集做分区
2️⃣ 然后应用哈希函数 h2 ,我们聚合函数要的是平均值,因此哈希表的值是关于聚合函数的特定值,它是数量和平均值的一个复合体
3️⃣ 在rehash完,我们将哈希表写入结果集中