CMU15-445-Spring-2023-Project #3 - Query Execution

news/2024/2/23 15:54:08/文章来源:https://blog.csdn.net/qq_43680965/article/details/135636952

前置知识,参考上一篇博客:CMU15-445-Spring-2023-Project #3 - 前置知识(lec10-14
在这里插入图片描述

  • Parser:将SQL query转变为AST
  • Binder:将查询语句与数据库元数据进行绑定,验证查询的正确性和有效性
  • Planner:为查询生成逻辑计划,描述查询操作的顺序和方式
  • Optimizer:对逻辑计划进行优化转换和选择最优的执行计划,以提高查询性能。

为 BusTub 添加新的运算符执行器和查询优化。BusTub 使用迭代查询处理模型(火山模型),其中每个执行器都实现了一个 Next 函数,用于获取下一个元组结果。当 DBMS 调用执行器的 Next 函数时,执行器会返回 (1) 一个元组或 (2) 一个没有更多元组的指示符。通过这种方法,每个执行器都实现了一个循环,不断调用其子执行器的 Next 来检索元组并逐个处理。
在 BusTub 的迭代器模型实现中,每个执行器的 Next 函数除了返回一个元组外,还会返回一个记录标识符(RID)。记录标识符是元组的唯一标识符。
目录的全部实现都在 src/include/catalog/catalog.h 中。注意成员函数 Catalog::GetTable() 和 Catalog::GetIndex()。在执行器的实现中使用这些函数来查询目录中的表和索引。
对于表修改执行程序(InsertExecutor、UpdateExecutor 和 DeleteExecutor),必须修改操作目标表的所有索引。Catalog::GetTableIndexes() 函数在查询为特定表定义的所有索引时非常有用。一旦获得表中每个索引的 IndexInfo 实例,就可以在底层索引结构上调用索引修改操作。
BusTub 优化器是一种基于规则的优化器。大多数优化器规则以自下而上的方式构建优化计划。由于查询计划具有树形结构,因此在对当前计划节点应用优化器规则之前,首先要对其子节点递归应用规则。
在每个计划节点上,应确定源计划结构是否与要优化的计划结构相匹配,然后检查该计划中的属性,看是否能优化为目标优化计划结构。

  /*** Execute a query plan.* @param plan The query plan to execute* @param result_set The set of tuples produced by executing the plan* @param txn The transaction context in which the query executes* @param exec_ctx The executor context in which the query executes* @return `true` if execution of the query plan succeeds, `false` otherwise*/// NOLINTNEXTLINEauto Execute(const AbstractPlanNodeRef &plan, std::vector<Tuple> *result_set, Transaction *txn,ExecutorContext *exec_ctx) -> bool {BUSTUB_ASSERT((txn == exec_ctx->GetTransaction()), "Broken Invariant");// Construct the executor for the abstract plan nodeauto executor = ExecutorFactory::CreateExecutor(exec_ctx, plan);// Initialize the executorauto executor_succeeded = true;try {executor->Init();PollExecutor(executor.get(), plan, result_set);PerformChecks(exec_ctx);} catch (const ExecutionException &ex) {executor_succeeded = false;if (result_set != nullptr) {result_set->clear();}}return executor_succeeded;}

Task #1 - Access Method Executors

Impl:
image.png

  • SeqScan
    • SeqScanPlanNode 可通过 SELECT * FROM 表语句进行plan。
    • SeqScanExecutor 对表进行遍历,每次返回一个表元。
    • note:通过MakeIterator()生成迭代器遍历tuple。
  • Insert
    • 可以使用 INSERT 语句生成 InsertPlanNode。请注意,指定 VARCHAR 值时需要使用单引号。
    • InsertExecutor 向表中插入元组更新任何受影响的索引。该执行器有一个子执行器,可产生要插入表中的值。planner 将确保这些值与表的模式相同。执行器将生成一个整数类型的元组作为输出,表示有多少行被插入表中。如果表中有相关索引,请记住在插入表时更新索引。
    • note:更新索引时,通过KeyFromTuple()生成key。
  • Update
    • UpdatePlanNode 可以用 UPDATE 语句进行生成。它有一个子节点,包含表中要更新的记录。
    • UpdateExecutor 会修改指定表中的现有tuple。执行器将产生一个整数类型的元组作为输出,显示有多少行被更新。切记要更新受更新影响的索引。
    • note:先删除,再更新(expr->evalutate),后插入。
  • Delete
    • DeletePlanNode 可以用 DELETE 语句进行生成。它有一个子节点,包含要从表中删除的记录。删除执行器应产生一个整数输出,表示从表中删除的记录数。它还需要更新任何受影响的索引。
    • 假定 DeleteExecutor 始终处于它所出现的查询计划的根节点。DeleteExecutor 不应修改其结果集。
  • IndexScan
    • IndexScanExecutor 会遍历索引以检索tuple的 RID。然后,算子使用这些 RID 在相应的表中检索其tuple。然后,它会一次一个地emit这些tuple。
    • 在本项目中,plan中索引对象的类型始终是 BPlusTreeIndexForTwoIntegerColumn。可以安全地将其转换并存储在执行器对象中:tree_ = dynamic_cast<BPlusTreeIndexForTwoIntegerColumn *>(index_info_->index_.get())。
    • 然后,可以从索引对象构建一个索引迭代器,扫描所有键和tuple ID,从表堆中查找元组,并按顺序emit所有元组。BusTub 仅支持具有单个唯一整数列的索引。

Task #2 - Aggregation & Join Executors

添加一个aggregation executor、几个join executors,并使优化器在规划查询时能够在nested loop join和hash join之间进行选择。
Impl:
image.png

  • Aggregation
    • 为每组输入计算一个聚合函数(count*、count、min、max、sum)。它只有一个子执行器。输出模式由 group-by columns和aggregation columns组成。
    • 实现聚合的常见策略是使用哈希表,并将group-by columns作为key。在这个项目中,可以假设聚合哈希表适合放在内存中。这意味着不需要实施基于分区的多级策略,哈希表也不需要由缓冲池页面支持。
    • 提供了一个 SimpleAggregationHashTable 数据结构,它提供了一个内存中的哈希表(std::unordered_map),但其接口是为计算聚合而设计的。该类还提供了一个 SimpleAggregationHashTable::Iterator 类型,可用于遍历哈希表。需要为该类完成 CombineAggregateValues 函数。
    • note:在init时就完成aggregation hash table初始化。
  • NestedLoopJoin
    • 默认情况下,DBMS 将对所有连接操作使用 NestedLoopJoinPlanNode。
    • 使用类中的nested loop join算法为 NestedLoopJoinExecutor 实现INNER JOIN和LEFT OUTER JOIN(左边的表不受限制)。此算子的输出模式是左表中的所有列,然后是右表中的所有列。对于外层表中的每个元组,都要考虑内层表中的每个元组,如果满足连接谓词,则输出一个元组。
    • 应在 NestedLoopJoinPlanNode 中使用谓词。请参阅 AbstractExpression::EvaluateJoin,它会处理左元组和右元组及其各自的模式。请注意,这将返回一个值,可能是 false、true 或 NULL。有关如何在元组上应用谓词,请参阅 FilterExecutor。
    • note:对于每个left_tuple,先evaluate join,将匹配的emit,然后处理未匹配的,即右列的值为NULL。
  • HashJoin
    • 如果查询包含两个列之间等条件连接的连接(等条件之间用 AND 分隔),则 DBMS 可以使用 HashJoinPlanNode。
    • 使用类中的hash join算法为 HashJoinExecutor 实现INNER JOIN和LEFT OUTER JOIN。此算子的输出模式是左表中的所有列,然后是右表中的所有列。与聚合一样,可以假定连接所使用的哈希表完全适合内存。
    • note:init时即完成hash join,通过模板类自定义unordered_map的哈希函数。
  • Optimizing NestedLoopJoin to HashJoin
    • hash join通常比NestedLoopJoin产生更好的性能。当可以使用散列连接时,应修改优化器,将NestedLoopJoinPlanNode转换为HashJoinPlanNode。具体来说,当连接谓词是两列之间等条件的连接时,可以使用hash join算法。
    • 在本项目中,处理单个等式条件以及通过 AND 连接的两个等式条件将获得满分。
    • image.png
    • note:自下而上构建优化;需要检查等式条件每一边的列属于哪个表。外层表中的列有可能位于等价条件的右侧;最后返回HashJoinPlanNodeRef。

Task #3 - Sort + Limit Executors and Top-N Optimization

Impl:
image.png
如果表上有索引,Query Processing层将自动选择它进行排序。在其他情况下,需要一个特殊的排序执行器来完成这项工作。
对于所有order by语句,假设每个排序键只会出现一次。

  • Sort
    • 如果查询的 ORDER BY 属性与索引的键不匹配,BusTub 将为查询生成一个 SortPlanNode;
    • 该计划节点的输出scheme与其输入相同。可以从 order_bys 中提取排序键,然后使用带有自定义比较器的 std::sort 对子节点的元组进行排序。您可以假定表中的所有条目都完全适合内存。
    • 如果查询不包含排序方向(即 ASC、DESC),则排序模式为默认模式(即 ASC)。
  • Limit
    • LimitPlanNode 指定查询将生成的tuple数。
    • LimitExecutor 限制其子执行器输出的tuple数量。如果其子执行器产生的tuple数量少于plan node中指定的限制,则该执行器不会产生任何影响,并产生其接收到的所有tuple。
    • 该计划节点的输出scheme与其输入相同。无需支持偏移。
  • Top-N Optimization Rule
    • 支持 top-N 查询。
    • 默认情况下,BusTub 会将此查询规划为 SortPlanNode 和 LimitPlanNode。这样做效率很低,因为使用堆来跟踪最小的 10 个元素远比对整个表进行排序更有效。注意堆的输出顺序是相反的。std::priority_queue<Tuple, std::vector, decltype(cmp)> pq(cmp);
    • 实现 TopNExecutor 并修改优化器,使其用于包含 ORDER BY 和 LIMIT 子句的查询。

更多优化,TODO。

在这里插入图片描述

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

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

相关文章

2024年美赛数学建模思路 - 案例:FPTree-频繁模式树算法

文章目录 算法介绍FP树表示法构建FP树实现代码 建模资料 ## 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 算法介绍 FP-Tree算法全称是FrequentPattern Tree算法&#xff0c;就是频繁模式树算法&#xff0c…

每日一练:LeeCode-144、145、94.二叉树的前中后序遍历【二叉树】

本文是力扣LeeCode-144、145、94.二叉树的前中后序遍历 学习与理解过程&#xff0c;本文仅做学习之用&#xff0c;对本题感兴趣的小伙伴可以出门左拐LeeCode前序遍历、中序遍历、后序遍历。 给你二叉树的根节点 root &#xff0c;返回它节点值的 前序遍历。 给定一个二叉树的根…

scrapy爬虫实战

scrapy爬虫实战 Scrapy 简介主要特性示例代码 安装scrapy&#xff0c;并创建项目运行单个脚本代码示例配置itemsetting 爬虫脚本 代码解析xpath基本语法&#xff1a;路径表达式示例&#xff1a;通配符和多路径&#xff1a;函数&#xff1a;示例&#xff1a; 批量运行附录1&…

从“精益思想“看机器人的开发与应用:一场科技与效率的完美融合

在科技飞速发展的今天&#xff0c;机器人已经深入到我们的生活和工作之中&#xff0c;成为了提高效率、提升质量的重要工具。然而&#xff0c;如何让机器人的开发和利用更有效率、更精细&#xff0c;这是摆在我们面前的一道难题。此时&#xff0c;"精益思想"的出现&a…

OpenCV C++ 图像处理实战 ——《多尺度自适应Gamma矫正的低照图像增强》

OpenCV C++ 图像处理实战 ——《多尺度自适应Gamma矫正的低照图像增强》 一、结果演示二、多尺度自适应Gamma矫正的低照度图像增强2.1HSI颜色空间2.1.1 功能源码2.2 自适应于直方图分布的 Gamma 矫正2.2.1 功能源码2.3 多尺度 Retinex 分解与明度增强2.3.1 功能源码三、源码测试…

统计学-R语言-3

文章目录 前言给直方图增加正态曲线的不恰当之处直方图与条形图的区别核密度图时间序列图洛伦茨曲线计算绘制洛伦茨曲线所需的各百分比数值绘制洛伦茨曲线 练习 前言 本篇文章是介绍对数据的部分图形可视化的图型展现。 给直方图增加正态曲线的不恰当之处 需要注意的是&#…

【生存技能】git操作

先下载git https://git-scm.com/downloads 我这里是win64&#xff0c;下载了相应的直接安装版本 64-bit Git for Windows Setup 打开git bash 设置用户名和邮箱 查看设置的配置信息 获取本地仓库 在git bash或powershell执行git init&#xff0c;初始化当前目录成为git仓库…

力扣labuladong一刷day61天动态规划最小下降路径

力扣labuladong一刷day61天动态规划最优子结构 一、931. 下降路径最小和 题目链接&#xff1a;https://leetcode.cn/problems/minimum-falling-path-sum/description/ 如下图所示&#xff0c;求最小下降路径&#xff0c;定义dp[i][j]表示从最上面那行的任意位置抵达到nums[i]…

Redis分布式锁--java实现

文章目录 Redis分布式锁方案&#xff1a;SETNX EXPIRE基本原理比较好的实现会产生四个问题 几种解决原子性的方案方案&#xff1a;SETNX value值是&#xff08;系统时间过期时间&#xff09;方案&#xff1a;使用Lua脚本(包含SETNX EXPIRE两条指令)方案&#xff1a;SET的扩展…

springcloud Alibaba中gateway和sentinel联合使用

看到这个文章相信你有一定的sentinel和gateway基础了吧。 官网的gateway和sentinel联合使用有些过时了&#xff0c;于是有了这个哈哈&#xff0c;给你看看官网的&#xff1a; 才sentinel1.6&#xff0c;现在都几了啊&#xff0c;所以有些过时。 下面开始讲解&#xff1a; 首先…

【Linux】自定义shell

👑作者主页:@安 度 因 🏠学习社区:安度因 📖专栏链接:Linux 文章目录 获取命令行前置字段命令行输入解析命令行普通指令的执行子进程执行命令指令类型判断 && 内建命令总结 &&a

【Maven】007-Maven 工程的继承和聚合关系

【Maven】007-Maven 工程的继承和聚合关系 文章目录 【Maven】007-Maven 工程的继承和聚合关系一、Maven 工程的继承关系1、继承的概念2、继承的作用3、继承的语法4、父工程统一管理依赖版本父工程声明依赖版本子工程继承以来版本 二、Maven 工程的聚合关系1、聚合的概念2、聚合…

VitePress-01-从零开始的项目创建(npm版)

说明 本文介绍一下 VitePress的项目创建的步骤。 主要用到的命令工具是 npm。 本文的操作步骤是从无到有的创建一个完整的基本的【VitePress】项目。 环境准备 根据官方文档的介绍&#xff0c;截止本文发稿时&#xff0c;需要使用node.js 18 的版本。 可以使用node -v 的命令查…

【MySQL】MySQL表的约束-空属性/默认值/列属性/zerofill/主键/自增长/唯一键/外键

文章目录 表的约束1.空属性 --null && not null2.默认值 -- default3.列描述4.zerofill5.主键6.自增长7.唯一键8.外键 表的约束 表的约束&#xff1a;表中一定要有各种约束&#xff0c;通过约束&#xff0c;让我们未来插入数据库表中的数据是符合预期的。约束的本质是…

【GCC】6 接收端实现:周期构造RTCP反馈包

基于m98代码。GCC涉及的代码,可能位于:webrtc/modules/remote_bitrate_estimator webrtc/modules/congestion_controller webrtc/modules/rtp_rtcp/source/rtcp_packet/transport_feedback.cc webrtc 之 RemoteEstimatorProxy 对 remote_bitrate_estimator 的 RemoteEstimato…

Spark与HBase的集成与数据访问

Apache Spark和Apache HBase分别是大数据处理和分布式NoSQL数据库领域的两个重要工具。在本文中&#xff0c;将深入探讨如何在Spark中集成HBase&#xff0c;并演示如何通过Spark访问和操作HBase中的数据。将提供丰富的示例代码&#xff0c;以便更好地理解这一集成过程。 Spark…

【EI会议征稿通知】第四届图像处理与智能控制国际学术会议(IPIC 2024)

第四届图像处理与智能控制国际学术会议&#xff08;IPIC 2024&#xff09; 2024 4th International Conference on Image Processing and Intelligent Control 2024年第四届图像处理与智能控制国际学术会议&#xff08;IPIC 2024&#xff09;将于2024年5月3日-5日在吉隆坡举…

【Jmeter之get请求传递的值为JSON体实践】

Jmeter之get请求传递的值为JSON体实践 get请求的常见传参方式 1、在URL地址后面拼接&#xff0c;有多个key和value时&#xff0c;用&链接 2、在Parameters里面加上key和value 第一次遇到value的值不是字符串也不是整型&#xff0c;我尝试把json放到value里面&#xff0…

C练习——杨辉三角

题目&#xff1a; 打印近似杨辉三角&#xff0c;行数n自选 百度找的杨辉三角&#xff0c;参考一下&#xff1a; 解析&#xff1a; 把它的全部元素左对齐&#xff0c;就可以看成近似杨辉三角的样子 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 …… 每个数等于它上方两数…

OpenCV C++ 环境搭建和简单示例

OpenCV介绍 OpenCV&#xff1a;开源发行的跨平台计算机视觉和机器学习软件库&#xff0c;用C语言编写&#xff0c;提供了C &#xff0c;Python&#xff0c;Java和MATLAB接口&#xff0c;并支持Windows&#xff0c;Linux&#xff0c;Android和Mac OS。 OpenCV下载 去官网http…