CMU15445 Project3记录

CMU15445 Project3记录
W3nYuiP3的源码真是太多了,看的我头晕,理解起来也比较困难,因为我不是科班生,我按照以下两位博主的专栏去整理、学习了一些内容。前两位做的都是2024Fall的project,第三位对p3做了详细的解析,第四位则是p3的开发者。
- https://zhuanlan.zhihu.com/p/690034893
- https://zhuanlan.zhihu.com/p/674080359
- https://zhuanlan.zhihu.com/p/587566135 (p3的解决方案)
- https://zhuanlan.zhihu.com/p/570917775 (在这个项目开始前,推荐阅读p3开发者迟先生的博客)
从project3开始,我们就要逐渐搭建一个数据库的架构了,p1、p2的B+树、缓冲池的内容是数据库的底层内容,而p3要实现的就是SQL查询的算子执行器,以及优化器。
可以参考CMU官网给出的这张流程图:
通过阅读源码 BusTubInstance::ExecuteSqlTxn ,可以看到整体的查询逻辑是:
- Parser采用了 libpg_query 库将 sql 语句 parse 为 AST(语法树)
- Binder根据AST绑定到数据库实体上,这样的数据结构才能被cpp理解。
- Planner会生成一个算子树/查询计划,这个算子树的每个节点都是一个AbstractPlanNode对象,每个plannode包含了一个或者多个abstract expression对象。
- Optimizer根据规则优化查询计划。
- 最后由executor执行引擎去执行这个算子树。
整个执行过程是Iterator Model的(pull-based的火山模型),那么火山模型又是什么?还有其他的执行模型吗(这一问题可以参考第三篇blog,他的Executor篇章介绍了Materialization Model与Vectorization Model)?
火山模型
火山模型(Volcano Model)在软件开发领域主要指数据库查询执行引擎中的一种经典执行模型,而非软件开发流程模型。其核心是通过迭代器接口实现数据的拉取式(Pull-Based)处理,由上层算子主动向下层算子请求数据,而非下层算子主动推送数据。这一模型由 Goetz Graefe 在 1994 年的论文《Volcano: An Extensible and Parallel Query Evaluation System》中提出,至今仍是 PostgreSQL、MySQL 等主流数据库执行引擎的基础设计范式。
1. 迭代器接口设计
火山模型将每个查询操作(如扫描、过滤、连接)抽象为一个统一的迭代器(Iterator),所有算子必须实现三个标准接口:
init():初始化资源(如打开文件、构建哈希表)。next():主动拉取下一条数据,若无数据则返回空值。close():释放资源(如关闭扫描器、清空内存)
2. 数据流动方向
- 自底向上拉取数据:根节点算子(如
Project)调用子节点的next()获取数据,子节点再递归调用其子节点,直到叶子节点(如SeqScan)从存储引擎读取原始数据。 - 控制流与数据流方向相反:控制流自顶向下(调用
next()),数据流自底向上(返回元组)。
Task #1 - Access Method Executors
需要实现从存储系统中读取和写入表的执行器。
Seq Scan (顺序扫描):
迭代遍历表,并每次返回一个批次的元组。 提示: 使用 TableIterator 时,注意前缀递增和后缀递增的区别。不要输出被标记为删除的元组(检查 TupleMeta 的 is_deleted_ 字段)。输出是匹配元组的副本及其原始 RID。
- 可以从顺序扫描讲起,整体的逻辑就是:根据
plan中的table_oid通过exec_ctx找到目标表,初始化表迭代器,随后在Next()中持续扫描表中tuple,跳过已删除记录,并根据下推谓词过滤,把满足条件的tuple和其RID放入输出batch,从而完成顺序扫描算子。 - 整体需要获取的资源都可以从
ExectorContext中找到
Insert (插入)
将元组插入表中并更新任何受影响的索引。它有且只有一个子节点提供值。执行器应当输出一个包含了std::vector<Value> values与schema的数组,指示插入的行数。
简单描述逻辑就是:
InsertExecutor只是一个消费者,他负责调度insert这个过程。那么需要插入的tuple数据从哪里来?数据通过child_executor获取,那么只需要校验:child_executor_->Next即可。
针对获取的child_tuples,我们需要对其都执行一次插入,而真正控制插入的函数是:InsertTuple,他会利用我们p1与p2的内容实现插入,且返回一个optional<RID>用于后续判断。且由于一张表可能会有多个索引,因此我们需要对每个索引都进行一次更新,最后对每一个索引都执行一次InsertEntry即可。
整个插入设计的地方众多,只能按照插入的语义以及对应的内容一步步查找,找到正确的插入函数以及返回格式进行返回。
Update (更新)
修改指定表中现有的元组。输出修改的行数。注意同步更新索引。
提示: 要实现更新,首先删除受影响的元组,然后插入一个新元组。
在Next的实现中,通过查询table_heap内的接口,我们可以发现,官方建议在project3的update实现为先删除后插入的过程,因此按照这个流程,先获取旧tuple与rid,然后从TableHeap中标记为删除,同时删除索引,然后通过update_plan内的target_expressions进行Evaluate,获取新的信息,再重新组合成tuple,插入到表中,生成新的rid,并重新构建索引。
我在写的时候,以为target_expressions与在seq_scan中遇到的谓词下推相似,是以tuple为单位的,但后来才发现在update_executor.h中介绍了,是以列为单位的,因此还要从table_schema中获取对应列,进行逐列比较。
Delete (删除)
从表中逻辑删除记录。输出删除的行数,并更新索引。
如果完成了update,那么delete就比较简单了,就是从update执行器抄下删除逻辑部分即可。
Index Scan (索引扫描) & 优化器规则
需要实现 SeqScanAsIndexScan 优化器规则(谓词下推)。当谓词(Predicate)中包含被索引列的等值测试时,将 SeqScanPlanNode 转换为 IndexScanPlanNode。需要支持单点查找和同一索引的多个点查找(OR 条件)。
- 关于谓词下推的理解:谓词就是 SQL 里的过滤条件,比如 WHERE 子句、JOIN 的 ON 条件 。下推就是把这些条件从查询上层”推”到更底层,在数据读取或处理的早期阶段就执行过滤 。简单说就是先过滤再做关联、聚合等操作,让无关数据不参与后续耗时计算 。
IndexScanExecutor本身要支持两种执行模式- 点查询 Point Lookup
- 顺序扫描 Ordered Scan
- Optimizer 要在合适的时候,把原来的计划改写成
IndexScanPlanNodeWHERE indexed_col = constant这种情况,需要实现OptimizeSeqScanAsIndexScanORDER BY indexed_col ASC这种情况,项目已经实现了
通过EXPLAIN两种情形可以得到,对点查询进行优化后,计划需要变成:
IndexScan { index_oid=0, filter=(#0.0=1) }
而我目前还是SeqScan,因此需要完善Seqscan_as_indexscan.cpp,来实现优化,具体实现可以参考order_by_index_scan.cpp与aggregation_plan.h
在实现了plan模式的转变后,针对这个查询语句,其点查询的执行方式是:
- 从谓词里提取常量
1,存储在pred_keys_内 - 构造索引 key
- 调用
ScanKey(key, &rids, txn) - 得到对应 RID
- 回表
table_heap->GetTuple(rid) - 跳过被删除的 tuple
- 输出结果
同时可以根据pred_keys_的大小,执行两种IndexScan,pred_keys_ 非空时做 point lookup,pred_keys_ 为空时做 ordered scan。
结合p3的提示,对于该优化器的设计,我是这么写的:
OptimizeSeqScanAsIndexScan只接受:- v1 = 1
- 1 = v1
- v1 = 1 OR v1 = 4
- v1 = 1 OR v1 = 1
- 只要出现 AND、不同列、非 =,就直接放弃优化,保留
SeqScan
整个Task1写下来,最难的地方就是在optimizer的书写,其他执行器的书写都是在熟悉这个项目,而optimizer是实打实的让你写优化,如何实现作业要求的优化功能,他的列该如何转换,如何去重,如何比较,都需要一个个优化。天天都在报越界…
现在写完了task1,回来看看为什么task1会报错,因为我看到题目让我使用
tree_ = dynamic_cast<BPlusTreeIndexForTwoIntegerColumn *>(index_info_->index_.get())
所以我大量使用了tree_.ScanKey,但是实际上把他dynamic_cast 成 BPlusTreeIndexForTwoIntegerColumn *,如果碰到create index t1v1 on t1(v1)这样的这种单列整型索引时,会被建成 GenericKey<4>,而BPlusTreeIndexForTwoIntegerColumn *是BPlusTreeIndex<GenericKey<8>, ...>的别名,而不是一个模板,因此这时候获取tree_会得到nullptr,这时候再调用tree_->ScanKey当然会越界。这里我用返回来修改了index_scan_executor的代码,一种是获取create index t1v1 on t1(v1)加上模板函数,构造不同的tree_,同时也可以利用index_info->index_->ScanKey来实现查询。
Task #2 - Aggregation & Join Executors
这一节开始,可以主要参考十一的p3记录,他详细介绍了每一种情况书写起来会碰到的问题。
Aggregation (聚合)
为每一组输入计算聚合函数。输出 Schema 为 Group-by 列 + 聚合列。 在本项目中,你可以假设聚合哈希表完全可以装入内存。我们提供了一个 SimpleAggregationHashTable 数据结构,你需要完成其 CombineAggregateValues 函数。 提示: 聚合是一个 Pipeline Breaker(管道断路器)。需要仔细权衡是在 Init() 还是 Next() 中执行聚合的 Build(构建)阶段。必须处理聚合输入中的 NULL 值。
什么是pipeline breaker?
在数据库执行查询时,最理想的模式是流式处理(Pipelining)。例如它们拿到一条数据,立刻处理后传给下一个节点,不需要把数据存起来。这种操作可以无缝衔接,内存占用极小。
而对于pipeline breaker,课件是这么描述的:A pipeline breaker is an operator that cannot finish until all its children emit all their tuples.
因此在Aggregation这个算子的Init()函数,就要把所有的结果计算出来。而聚合得到的结果暂存在SimpleAggregationHashTable内,且项目假设该数据结构内存足够,不需要再实现内存池/分区的操作。
同时要注意的是,如果整个Aggregation的结果是一个空表,那么他也是需要返回值的,具体可以在运行如下测试时可以了解到。这时就需要考虑到官方的InsertCombine函数可能会造成COUNT(*)的统计错误。
1 | ./bin/bustub-sqllogictest ../test/sql/p3.07-simple-agg.slt --verbose |
针对插入时的NULL值,需要修改AggregateKey的比较。
连接执行器 (Join)
关于连接的含义,以及逻辑可以查阅数据库连接wiki
Nested Loop Join (嵌套循环连接)
针对没有索引的表进行连接,实现内连接或左外连接。
针对这个执行器,需要注意的是Next()是一个batch 接口,他不需要一次就完成所有的计算,因此需要记录上下文,保留左表信息、右表信息、当前left_tuple是否完成匹配。
整体的Next()逻辑就是:
1 | while output size < batch_size: |
同时要注意,在每次emit时,都需要检查容器长度,在写这一部分时,如果是left join,右表无匹配,此时需要返回一个(left_tuple, null_tuple),如果不检查大小就会造成越界。
Nested Index Join (嵌套索引连接)
当连接条件的右侧有索引时,通过探测索引进行高效连接。
这里不再查询整个右表,而是利用索引快速查询。
1 | for each outer tuple from child executor: |
在跑Extra checks: ["ensure:nlj_init_check"]这个check时,会出现报错,报错提示我:
nlj check failed, are you initializing the right executor every time when there is a left tuple?
这说明在做Nested Loop Join时我的断言出错了,我遵照了缓存的写法,但是这里官方检查的是标准 NLJ,即对每一个左表的tuple,都要对右表进行一次init()。
所以逻辑就会变成:
1 | while output size < batch_size: |
Task #3 - Hash Join Executor and Optimization
如果等值连接条件没有索引,Nested Loop Join 的性能会极差。你需要实现:
- Hash Join (哈希连接): 在内存中构建哈希表以执行等值连接。Build 阶段读取右侧子节点的所有元组构建哈希表,Probe 阶段读取左侧元组进行探测。
- Hash Join Optimization (优化器规则): 实现规则将
NestedLoopJoin转换为HashJoin(当检测到等值条件=时)。
根据我阅读几位大佬的文章,以前应该是没有这个内容的,原先是作为leaderboard的优化去写的,这个内容作为task也说明了他是数据库比较重要的性能优化的一环。同时官方希望在面对大表时采用Grace Hash Table来解决容量问题,这个之后再去优化了。
具体的哈希表设计,我直接按照SimpleAggregationHashTable内的设计去修改的,同样的,Task3是对Task2的优化,所以他也是一个pipeline breaker,这里我在Init时就对右表做好hash缓存,之后每一次Next都要做索引记录。
在写完哈希表逻辑之后,最好根据作业描述,修改成Grace Hash Table,具体可以看一下这一篇博客,他也做了一些拓展。
同样的,在这里利用Grace Hash Table唯一的区别就是:当$tuple batch size >= batch size$中 断时,需要考虑的事情增加了:
- 分区是否执行完,是否需要加载新的分区
- 当前分区右表位置
- 一个
key对应了右表多个tuple,当前tuples内的位置也需要保存 - 当前分区左表位置
- 何时需要切换分区,左右表分区的对应关系是什么
当然如果利用Grace Hash Table算法也放不下时,就需要利用到IntermediateResultPage,将hash表暂存入页中进行替换。
对于$NLJ->HashJoin$的优化器,基本就是参照$NLJ->IndexJoin$去写就行,只需要注意需要递归所有子树,同时对返回的key需要支持如下类型,因此需要针对所有节点类型都做判断:
1 | <column expr> = <column expr> AND <column expr> = <column expr> AND ... |
加入了intermediate_result_page后的流程图。
1 | flowchart TD |
Task #4 - External Merge Sort + Limit Executors + Window Functions
Task4实现三个算子,外部归并排序、Limit、窗口函数。
外部归并排序
对于排序,最难做的就是读源码,理解每个文件需要实现的内容是什么。
对于排序规则,需要在execution_common内实现。
- 行的比较:每个Key都去比较 Key是NULL的情况
- ASC、DECS的设置
- NULLS FIRST/LAST
- DEFAULT : ASC
external_merge_sort_executor内主要利用intermediate_result_page去把 tuple 存到磁盘页,最后利用run 和 run iterator两两比较,得到最后的结果。
我是在这里实现intermediate_result_page,然后回去把Task3的 grace hash join完善的,直到做到Task4我才想好intermediate_result_page内真正需要的是什么,他只需要将tuple存到页就行,只是一个工具类罢了。
我的intermediate_result_page只做了最基础的功能,基本是按照table_page去写的,把table_page根据RID读取的形式改成了顺序插入按槽读取,写的自己方便就行:
- 支持顺序追加
Tuple - 支持按槽位读取第
i个Tuple - 支持查询当前页 tuple 数、剩余空间、是否满
- 有
next_page_id_便于切换
说来惭愧…我是第一次见到table_page这种写法,利用页内存管理数据,因此要考虑增长问题,每组tuple的offset和size在slot array内从前向后增长,而tuple则从后向前写入,根据如下的分配,就需要考虑tuple在写入时是否会覆盖到slot array的内存了。
1 | --------------------------------------------------------- |
最后就是结合之前所有内容,实现归并排序。这个归并排序也可以优化,先计算好所有的key再进行排序。整体而言就和leetcode里的有序链表合并一样做就行。当然也可以进一步优化,每一次在保存到intermediate_result_page内时,保留SortKey,这样在归并时避免重复计算。
同时这里讲的是外部归并排序,所以在排序时我是边比较边写入新的run。
整体写下来就和leetcode内的合并两个有序链表一样。
Limit算子
比较简单,直接比大小,如果$limit > batchSize$大时需要保留剩余元组数。
Window Function
WindowFunctionExecutor 要做的是“对每一行都输出一个结果”,但这个结果不是只看当前行,而是看“当前行所在的一组行(partition)”,以及“这组里排在当前行之前/到当前行为止的那些行(order by)”。
目前Window Function只需要两种语义:
没有
ORDER BY:
这行的窗口值 = 它所在 partition 的“整组聚合结果”。
对每个 partition 跑一次整组聚合,然后把结果复制给该 partition 的每一行。有
ORDER BY:
这行的窗口值 = 它所在 partition 中,按ORDER BY排序后,从开头到当前行为止的“前缀聚合结果”。
对每个 partition 按当前顺序从前往后扫,维护一个“运行中的 aggregate state”。每读到一行就Combine一次,并把当前 state 记到这一行。
在这里由于要排序我就简单做了,在Init()时就把所有 tuple 全读出来,判断是否有ORDER BY , 对每个 window 列单独计算一列结果并拼出输出。
Leaderboard
Leaderboard Task 包含三条极其诡异的 sql,要做的就是增加新的优化规则,让这三条 sql 执行地越快越好,避免段错误/超时。分三个部分:
- Query 1: Too Many Joins!
- Query 2: The Mad Data Scientist
- Query 3: All that work, for a little thing?
Query 1: Too Many Joins!
SQL:
1 | SELECT * FROM t4, t5, t6 |
简单来说就是join 条件和普通过滤条件混在一起,无法直接转成 HashJoin ,单表过滤条件没有尽早下推到 SeqScan,扫描和 join 的数据量都太大。
理解这个题目真心有点累,看着简单但是需要自己在OptimizeCustom内实现一个新的优化方案。
从题目可以看到我们需要修改NLJ与hash_join的优化器,我的想法是拆分OptimizeMergeFilterNLJ的职责:
- 把
WHERE里的大条件按AND拆开 - 判断每个子谓词属于左子树、右子树,还是跨左右两边
- 左右单边谓词继续往下推
- 跨左右两边的等值谓词保留在当前
join上 - 递归重复这个过程,直到推到最底层
- 最后把只剩 join key 的
NLJ转换成HashJoin
一开始我就是拆分了谓词,但是没有继续下推,没有到最下层,查了很久bug。
到最后我就写了这一个query,之后有时间再写吧…写起来太麻烦了,但是在不断的修缮中可以学到很多。






