闸北区网站建设网页制,品牌网站建设 app建设,微信搜一搜怎么做推广,游戏公司网页设计我们现在将讨论如何使用迄今为止讨论过的 DBMS 组件来执行查询。 1 查询计划【Query Plan】
我们首先来看当一个查询【Query】被解析【Parsed】后会发生什么#xff1f;
当 SQL 查询被提供给数据库执行引擎#xff0c;它将通过语法解析器进行检查#xff0c;然后它会被转换…我们现在将讨论如何使用迄今为止讨论过的 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】批量加载到 BTree 索引中的速度更快。聚合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) 该算法仅需要三个缓冲池页面来执行排序B3。
两个输入页面一个输出页面
但是即使我们有更多可用 Buffer Pool 空间 (B3)如果工作线程【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 树进行排序
如果需要排序的表在排序属性上已经有 BTree 索引那么我们可以使用它来加速排序。 只需遍历树的叶节点所在的页即可按所需的排序顺序检索元组。 需要考虑下面两种情况
聚簇 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完我们将哈希表写入结果集中
