4 min read

CMU 15-445/645 fall2024 p3

15445 C++DataBaseQuery ExecutionOptimizer

在服务器内按 bustub 文档完成环境配置后，P3 主要完成了 SQL 执行层与优化器的核心链路：Executor 体系、Join/Sort/Window 等算子、以及规 则优化（NLJ -> HashJoin、SeqScan -> IndexScan、Sort+Limit -> TopN）。和 P0/P1/P2 一样，public 指模板仓库远程，origin 指我自己的远程 仓库，日常开发在本地仓库完成。

Git 命令

git pull public master # 拉取模板更新 git push origin main # 推送本地提交

execution_common.h / execution_common.cpp

execution_common 里补齐了执行器兼容层和排序通用能力：

  • src/include/execution/execution_common.h:45 定义 EXECUTOR_COMPAT_BATCH_SIZE，统一批处理接口的默认粒度。
  • src/include/execution/execution_common.h:54 提供 NextBatch 兼容签名，保证旧路径和新路径都能跑通。
  • src/execution/execution_common.cpp:62 的 TupleComparator::operator() 实现排序比较逻辑。
  • src/execution/execution_common.cpp:125 的 GenerateSortKey 负责从 tuple 生成排序键。

执行器实现（Executor）

P3 的主体是各类执行器的 Init/Next 生命周期：

  • src/execution/seq_scan_executor.cpp:28、src/execution/seq_scan_executor.cpp:30：顺序扫描，处理可见元组输出。
  • src/execution/index_scan_executor.cpp:33、src/execution/index_scan_executor.cpp:61：索引扫描，按索引结果回表取 tuple。
  • src/execution/filter_executor.cpp:32、src/execution/filter_executor.cpp:40：过滤算子，按谓词裁剪子执行器输出。
  • src/execution/limit_executor.cpp:30、src/execution/limit_executor.cpp:38：限制输出条数并提前终止。
  • src/execution/aggregation_executor.cpp:35、src/execution/aggregation_executor.cpp:55：聚合算子，构建分组聚合并输出结果。
  • src/execution/insert_executor.cpp:34、src/execution/insert_executor.cpp:39：插入执行并返回影响行数。
  • src/execution/delete_executor.cpp:34、src/execution/delete_executor.cpp:39：删除执行并返回影响行数。
  • src/execution/update_executor.cpp:34、src/execution/update_executor.cpp:39：更新执行并维护索引一致性。
  • src/execution/nested_loop_join_executor.cpp:81、src/execution/nested_loop_join_executor.cpp:100：实现 NLJ，确保右侧在每个左侧 tuple 上正确重置。
  • src/execution/hash_join_executor.cpp:84、src/execution/hash_join_executor.cpp:111：实现 Hash Join 的 build/probe 主流程。
  • src/execution/nested_index_join_executor.cpp:66、src/execution/nested_index_join_executor.cpp:103：实现基于索引的连接路径。
  • src/execution/window_function_executor.cpp:177、src/execution/window_function_executor.cpp:330：实现窗口函数预处理与逐行输出。

External Merge Sort

外部排序是 P3 里最关键的磁盘算子之一：

  • src/execution/external_merge_sort_executor.cpp:97、src/execution/external_merge_sort_executor.cpp:106：构造与析构，管理中间结果资 源。
  • src/execution/external_merge_sort_executor.cpp:132、src/execution/external_merge_sort_executor.cpp:188、src/execution/ external_merge_sort_executor.cpp:205、src/execution/external_merge_sort_executor.cpp:232：分块排序与多路归并核心步骤。
  • src/execution/external_merge_sort_executor.cpp:276、src/execution/external_merge_sort_executor.cpp:312、src/execution/ external_merge_sort_executor.cpp:331：执行与结果输出路径。

Plan / Page 支撑结构

  • src/include/execution/plans/aggregation_plan.h:37、src/include/execution/plans/aggregation_plan.h:67、src/include/execution/ plans/aggregation_plan.h:73、src/include/execution/plans/aggregation_plan.h:76、src/include/execution/plans/ aggregation_plan.h:78：聚合计划节点的关键信息组织。
  • src/include/storage/page/intermediate_result_page.h:20、src/include/storage/page/intermediate_result_page.h:30、src/include/ storage/page/intermediate_result_page.h:36、src/include/storage/page/intermediate_result_page.h:40、src/include/storage/page/ intermediate_result_page.h:46：中间结果页布局与读写接口。

Optimizer 规则

优化器部分主要是规则链改写：

  • src/optimizer/optimizer.cpp:20、src/optimizer/optimizer.cpp:43：优化入口与统计/基数估计主流程。
  • src/optimizer/optimizer_custom_rules.cpp:22、src/optimizer/optimizer_custom_rules.cpp:24、src/optimizer/ optimizer_custom_rules.cpp:25、src/optimizer/optimizer_custom_rules.cpp:26、src/optimizer/optimizer_custom_rules.cpp:27、src/ optimizer/optimizer_custom_rules.cpp:29、src/optimizer/optimizer_custom_rules.cpp:30：自定义规则串联执行。
  • src/optimizer/nlj_as_hash_join.cpp:115：把可等值连接的 NLJ 改写成 Hash Join。
  • src/optimizer/seqscan_as_indexscan.cpp:77：把可用索引的 SeqScan 改写成 IndexScan。
  • src/optimizer/sort_limit_as_topn.cpp:52：把 Sort + Limit 改写为 TopN。
  • src/optimizer/column_pruning.cpp:23：列裁剪规则骨架。

Executor Factory / 运行时检查

  • src/execution/executor_factory.cpp:56：统一计划节点到执行器实例的构造入口。
  • src/execution/executor_factory.cpp:116、src/execution/executor_factory.cpp:121：检查执行器注入（含 NLJ 初始化次数检查）。
  • src/execution/executor_factory.cpp:171、src/execution/executor_factory.cpp:178：Sort 与 TopN 的执行器分发。

生成提交包

  1. 自动打包（按 CMakeLists.txt:326 的 P3_FILES，通过 CMakeLists.txt:374 的 submit-p3 目标生成）

cmake —build build —target submit-p3

  1. 生成并写入签名文件

python3 gradescope_sign.py

  1. 检查提交包内容

unzip -l project3-submission.zip