第八讲 Sort Aggregate 算法

我们现在将讨论如何使用迄今为止讨论过的 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完,我们将哈希表写入结果集中

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/525919.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

VueRouter的介绍:什么是路由呢?VueRouter的作用及使用,VueRouter的使用分为5个步骤和特定的2步

1.什么是路由呢? 路由就是路径和组件之间的映射关系,当我们路径变化的时候,就要切换对应的组件。 在前端中解决路径与组件之间的映射关系,官方提供了VueRouter这个插件 2.VueRouter的作用及使用 作用:修改地址栏路…

基于单片机手机屏蔽器系统仿真设计

**单片机设计介绍,基于单片机手机屏蔽器系统仿真设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机手机屏蔽器系统的仿真设计主要涉及到手机信号屏蔽的原理、单片机控制逻辑设计、仿真软件的选择与使用以…

太厉害了,不愧是字节出来的。

🍅 视频学习:文末有免费的配套视频可观看 🍅 点击文末小卡片 ,免费获取软件测试全套资料,资料在手,涨薪更快 前段时间公司缺人,也面了许多测试,一开始瞄准的就是中级水准&#xff0c…

DolphinScheduler 答案整理,最新面试题

DolphinScheduler的架构设计是怎样的? DolphinScheduler的架构设计主要分为四个层次:前端界面层、API服务层、调度层和执行层。 1、前端界面层: 提供任务的定义、流程的设计、监控等功能,用户通过前端界面操作整个系统。 2、AP…

【AN】简单的实现点击播放影片剪辑再点击暂停的功能

动画故事背景 一个影片剪辑,里面做了一个动画。我希望影片剪辑一开始是暂停的,按钮点击后开始播放,再次点击就暂停! 下图那个花瓣就是影片剪辑,里面有个掉落的路径引导动画! 1.首先给花瓣影片剪辑一个实例…

恭贺格雷勒管业入围2024进口管道十大品牌

恭贺格雷勒管业入围2024进口管道十大品牌 2024进口管道十大品牌网络评选再次成功举办。格雷勒管道凭借优异的产品质量,再次成功入围。 格雷勒隶属于格勒菲德进出口贸易(上海)有限公司。德国【格雷勒】在总部德国杜塞尔多夫设置了专业实验室&a…

Master节点快照回退遇到的容器不存在的问题

这次遇到的问题说起来有点扯,k8s集群出了点问题,kuboard无法访问,查看容器状态后,初始问题简单的以为是kuboard出问题了,理论上来说重新安装kuboard即可, 由此问题引发的系统bug,导致master节点…

【算法】第二篇 大衍数列

导航 1. 简介2. 数列特征3. 代码演示1. 简介 大衍数列,来源于《乾坤谱》中对易传“大衍之数五十”的推论。主要用于解释中国传统文化中的太极衍生原理。数列中的每一项,都代表太极衍生过程中,曾经经历过的两仪数量总和。是中华传统文化中隐藏着的世界数学史上第一道数列题。…

本地运行大模型,需要什么样的配置?

本地运行大模型有多爽?只有用过了才知道。 那是一种顺畅、自由的感觉。 比如使用那些主流大模型,最常见的就是网络问题,如 IP 受限,或者服务器压力过大导致的延迟等等。 使用本地大模型,真的是像和人自然交谈那么顺…

LeetCode第十五题:三数之和【15/1000 python】

👤作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。 会一些的技术:数据分析、算法、SQL、大数据相关、python 作者专栏每日更新: LeetCode解锁1000题: 打怪升级之旅 LeetCode解锁1000题: 打怪升级之旅htt…

RabbitMQ 消息重复消费问题

RabbitMQ 消息重复消费问题 解决消息重复消费问题 解决消息重复消费问题 需要在消费端考虑消息的幂等性: 幂等性:对一个接口的多次调用和一次调用得到的结果都是一样的 使用数据库的唯一越苏保证幂等性。

应用程序无法正常启动怎么办,应用程序无法正常启动解决方法

电脑使用过程中会碰到各种问题,比如说,有些时候打开应用可能会失败,与此同时还会出现某些提示。最近有用户就遇到了打开软件就提示“应用程序无法正常启动0xc000007b”,这个问题是很常见的,一般是某部分组件损坏导致的…

LeetCode刷题之105. 从前序与中序遍历序列构造二叉树

文章目录 1.题目描述2. 分析2.1 前序遍历2.1.1 什么是前序遍历?2.1.2 前序遍历有什么特点? 2.2 中序遍历2.2.1 什么是中序遍历2.2.2 中序遍历有什么特点? 2.3 后序遍历2.3.1 什么是后序遍历?2.3.2 特点 2.4 总结 3. 解法 1.题目描…

【算法基础】选择排序与冒泡排序的思想与实现

文章目录 1. 选择排序1.1 思想1.2 实现 2. 冒泡排序2.1 思想2.2 实现 1. 选择排序 1.1 思想 选择排序的思想很简单,如上图所示。在每一次遍历子数组的过程中,选择最小的和子数组的第一位交换。子数组的选择从一开始的整个数组,到后面范围逐渐…

Vue2(十四):路由的使用及注意点、嵌套路由、路由的query和params参数、props配置

一、路由的简介 vue-rooter:是vue的一个插件库,专门用来实现SPA应用 1.对SPA应用的理解 1、单页 Web 应用(single page web application,SPA)。 2、整个应用只有一个完整的页面 index.html。 3、点击页面中的导航链…

CVE-2023-2928 DedeCMS 文件包含漏洞getshell 漏洞分析

DedeCMS(也称为织梦CMS)是一款基于PHPMySQL的开源内容管理系统。 在 DedeCMS 5.7.106 及之前的版本中发现一个漏洞。它已被宣布为关键。受此漏洞影响的是未知功能的文件uploads/dede/article_allowurl_edit.php。对参数 allurls 的操作会导致代码注入。…

近期整理的前端面试问题大集合【附带答案版】

目录 1、vue的双向绑定原理是什么?里面的关键点在哪里? 2、实现水平垂直居中的方式? 3、常用伪元素有哪一些? 4、移动端如何适配不同屏幕尺寸? 5、本地存储有哪一些?他们三者有什么区别? …

智慧乡村建设探索:数字乡村引领农村发展新方向

目录 一、智慧乡村建设的内涵与意义 二、数字乡村的发展现状 三、数字乡村引领农村发展的新方向 (一)推动农业现代化,提升农业生产效率 (二)培育农村新业态,促进农村产业升级 (三&#xf…

陶瓷、高频、普通PCB板材有什么不同?

在电子制造中,印刷电路板(PCB)板材的选择很重要,将直接决定电路板的性能、成本和适用领域,按照市场上应用最广泛的PCB板材,可分为陶瓷、高频及普通,它们三个有什么不同? 1、材质陶瓷…