Caltech CS122 数据库系统实现：聚焦 SQL 层与查询优化器的数据库进阶课程指南

CS122（Database System Implementation）是加州理工学院（Caltech）开设的数据库系统实现课程，与侧重存储层实现的 CMU 15-445 不同，它的 Lab 重点落在 SQL 层：查询优化器各模块、Join 实现、统计信息与代价估计、子查询、聚合与 Group By，以及 B+ 树与 WAL 实验。读完本篇指南，你将了解 CS122 每个 Assignment 的技术任务、它在数据库学习路径中的定位，以及推荐的工程环境与学习策略，便于判断这门课是否适合作为你学完数据库入门课之后的进阶选择。

课程基本信息与学习定位

CS122 的基本信息如下：

• 所属大学：Caltech（加州理工学院）
• 先修要求：无（课程层面未设硬性先修，但强烈建议在学完存储层课程之后学习）
• 编程语言：Java
• 课程难度：五星难度（本仓库文档中评级为最高档）
• 预计学时：150 小时
• 作业规模：7 个 Assignments + 2 个 Challenges

从课程定位上看，CS122 与仓库中介绍的 CMU 15-445 形成鲜明互补。15-445 要求你在 C++ 教学数据库 Bustub 中实现 Buffer Pool Manager、B+ 树、查询执行器、并发控制等存储层与执行层组件，但其代码中并不提供 SQL 层功能；而 CS122 的 Lab 恰好覆盖 15-445 没有深入的部分——SQL 解析（Parser）、Translate、查询优化器（Optimizer）的各个模块。文档原文给出的学习建议很明确：本门课程适合在学完 CMU 15-445 之后、对查询优化相关内容有兴趣的同学。换句话说，如果你希望完整走通一条"从磁盘上的字节到一条 SQL 的执行计划"的数据库实现之路，15-445 负责"下半程"（存储与执行），CS122 则补齐"上半程"（SQL 层与优化）。

实验主线：围绕 NanoDB 的 SQL 层实现

CS122 的 Lab 围绕一个名为 NanoDB 的教学数据库展开，要求你在其上逐层实现 SQL 层的完整能力链。按照一条 SQL 语句在系统中的处理顺序，课程涉及的模块包括：

1. SQL 解析（Parser）：把 SQL 文本解析为结构化的语法表示；
2. Translate：将解析结果翻译为内部表示/计划节点；
3. Join 实现：用具体的连接算法（nested-loop join）实现 Join 计划节点；
4. 统计信息与代价估计：收集表统计信息、计算计划代价、估计谓词选择性；
5. 子查询实现：处理嵌套查询的语义与执行；
6. Agg / Group By 实现：聚合与分组算子的执行；
7. B+ 树实验：索引结构的实现；
8. WAL（Write-Ahead Logging）实验：日志与恢复相关机制。

下面按文档给出的前 3 个 Assignment 逐一展开。

Assignment 1：数据修改语句与 Buffer Pool

Assignment 1 的任务清单为：

• 为 NanoDB 提供 delete、update 语句的支持；
• 为 Buffer Pool Manager 添加合适的 pin/unpin 代码；
• 提升 insert 语句的性能，同时不使数据库文件大小过分膨胀。

从任务结构看，这一阶段的落脚点是"让 NanoDB 从只读走向可更新"。delete 与 update 意味着系统必须能定位并改写已有元组，并保证修改与缓冲区管理正确协同：Buffer Pool Manager 中页面被 pin 住时不会被换出，unpin 之后才允许淘汰——"添加合适的 pin/unpin 代码"正是要求你在读写路径上正确管理页面的引用计数与脏页标记，这是缓冲池实现的经典易错点。第三个任务则引入工程约束意识：insert 提速（例如批量写、减少随机 I/O）与数据库文件大小膨胀之间存在取舍，需要在两者之间做平衡，而不是单方面追求插入吞吐。

Assignment 2：计划生成器与 Join 执行

Assignment 2 的任务清单为：

• 实现一个简单的计划生成器（Plan Generator），将各种已经 Parser 过的 SQL 语句转化为可执行的执行计划；
• 使用 nested-loop join 算法，实现支持 inner join 和 outer join 的 Join 计划节点；
• 添加一些单元测试，保证 inner join 和 outer join 功能实现正确。

这一 Assignment 是 SQL 层从"静态表示"跨入"动态执行"的关键一步。计划生成器接收 Parser 已经解析过的 SQL 语句，为其构造一棵可执行的计划树——文档特意强调"简单"，说明此阶段先建立"从 AST 到执行计划"的完整链路，而非一开始就做最优计划。执行层则聚焦 nested-loop join：以嵌套循环为最基础的连接算法，同时覆盖 inner join（只保留满足连接条件的元组对）与 outer join（保留不满足条件一侧的元组，另一侧补 NULL）两种语义。要求补充单元测试，则意味着你需要自行构造能区分两类 join 语义的测试数据——例如外表中无匹配行的元组在 inner join 下被丢弃、在 outer join 下以 NULL 补齐——这是验证 join 正确性的最小充分条件。

Assignment 3：统计信息、代价估计与谓词选择性

Assignment 3 的任务清单为：

• 完成收集表的统计信息；
• 完成各种计划节点的计划成本计算；
• 计算可出现在执行计划中的各种谓词的选择性（selectivity）；
• 根据谓词更新计划节点输出的元组统计信息。

如果说 Assignment 2 解决的是"能执行"，Assignment 3 解决的是"执行得怎样才算便宜"，这正是查询优化器的核心：

• 表统计信息（如行数、页数等）是一切代价计算的输入；
• 代价计算需要为扫描、连接、聚合等各类计划节点分别建立成本模型；
• 谓词选择性估计回答"WHERE 条件过滤后还剩多少元组"，是代价模型中最关键也最易失真的环节；
• 最后一条要求把前两者串起来：谓词作用于某个计划节点后，其输出端口的元组数/页数等统计必须随之更新，下游节点的代价才能基于被过滤后的真实规模计算。

四个任务合起来，恰好构成一个最小可用的基于代价的优化器（CBO）的信息闭环：统计信息 → 选择性估计 → 逐节点代价传播 → 计划成本汇总。

后续 Assignment 与 Challenges

除上述 3 个 Assignment 外，课程共有 7 个 Assignments + 2 个 Challenges。文档指出，课程的实验还包含 B+ 树与 WAL（预写日志） 相关实验——这两块把课程从 SQL 层拉回存储与恢复层面：B+ 树考察索引组织的实现，WAL 考察事务日志与崩溃恢复机制。剩余 Assignment 与 Challenges 的具体内容，文档建议直接查看课程介绍（见下文课程资源），此处不再展开，以避免超出本仓库文档可确认的范围。

工程环境与学习建议

文档对动手实现给出了明确的工具链建议：

• 推荐用 IntelliJ IDEA 打开工程：课程代码为 Java 工程，IDEA 对重构、调试与单元测试组织更友好；
• 使用 Maven 构建：依赖管理与模块构建统一由 Maven 负责；
• 注意日志相关配置：文档特别提醒"注意日志相关配置"——在实现优化器与执行器时，大量调试依赖对计划树与统计信息的日志输出，日志级别与输出配置若不提前理顺，排错成本会显著上升。

此外，结合文档给出的作业体量（7 个 Assignments + 2 个 Challenges）与预计学时（150 小时），建议将 Assignment 2 的计划生成链路、Assignment 3 的统计-代价闭环作为两条主线优先打通：前者决定"能不能跑通一条查询"，后者决定"查询能不能被合理优化"，两条主线交汇之后，后续的子查询、Agg/Group By、B+ 树与 WAL 实验都可以在既有框架上增量推进。

在仓库数据库学习体系中的位置

本仓库的数据库系统板块收录了多门实现型课程，CS122 在其中有清晰而独特的生态位。以仓库文档为参照，可以这样对比：

课程	文档位置	语言	侧重点	作业规模
UCB CS186	docs/数据库系统/CS186.md	Java	理论 + 实现 SQL 并发查询、B+ 树索引、故障恢复的数据库	6 个 Project
CMU 15-445	docs/数据库系统/15445.md	C++	存储层：Buffer Pool、B+ 树、执行器与优化器算子、并发控制	5 个 Project + 5 个 Homework
Caltech CS122	docs/数据库系统/CS122.md	Java	SQL 层：Parser、Translate、Join、统计信息与代价估计、子查询、Agg/Group By，外加 B+ 树与 WAL 实验	7 Assignments + 2 Challenges
Stanford CS346	docs/数据库系统/CS346.md	C++	RedBase：记录管理、B+ 索引、系统管理、查询语言 RQL 与扩展组件	4 Projects + 1 Extension
CMU 15-799	docs/数据库系统/15799.md	C++	数据库前沿专题（Streaming、Graph DB、NVM、Self-Driving DBMS 等）	2 Projects + 1 Group Project

从这张对照可以看出 CS122 的差异化价值：

• 相对 CS186（Java 入门实现课，覆盖索引与恢复）和 15-445（C++ 存储层实现课），CS122 独占"SQL 层 + 查询优化器"这一环，且同为 Java 实现，语言切换成本低；
• 相对 CS346 RedBase，后者虽也含查询语言实现（RQL 的 select/insert/delete/update），但组织方式更偏组件式（记录管理、索引、系统管理、查询语言四块 + 扩展），CS122 则把优化器的统计-代价-选择性闭环作为独立 Assignment 深挖；
• 完成 CS122 与 15-445 之后，若想进一步拓展视野（前沿主题、论文导向），可衔接仓库中的 CMU 15-799。

一条合理的组合路线是：先用 15-445 或 CS186 建立存储层与执行层的实现经验，再用 CS122 补齐 SQL 层与查询优化器，最后视兴趣选择 15-799 接触前沿方向。

课程资源

文档给出的课程资源如下：

• 课程网站：Caltech CS122 官方课程站点（courses.cms.caltech.edu 下的 cs122 页面），后续 Assignment 与 Challenges 的完整安排以该站点课程介绍为准；
• 课程代码：Caltech 课程代码仓库（gitlab.caltech.edu 下的 cs122-19wi），NanoDB 工程与实验代码以此为准；
• 课程教材：无；
• 课程作业：7 个 Assignments + 2 个 Challenges。

需要说明的适用前提：本课程无指定教材，理论部分需要结合数据库系统经典教材中的查询处理与优化章节自学；代码仓库按学年组织（如 19wi），不同年份版本的手写要求可能存在差异，动手前应先核对对应学年的 handout。

小结

Caltech CS122 是一门以 Java 实现 SQL 层为核心的数据库进阶课程：Assignment 1 打通数据修改语句与缓冲池管理，Assignment 2 建立"解析 → 计划 → nested-loop join 执行"的链路，Assignment 3 补齐统计信息、谓词选择性与代价估计的优化器闭环，其余 Assignment 与 B+ 树、WAL 实验进一步覆盖索引与恢复。文档原文给出的建议——先学完 CMU 15-445 再学 CS122、用 IDEA + Maven 管理工程、注意日志配置——依然是上手这门课最省事的路线。对本仓库的读者而言，CS122 与 15-445、CS186、CS346 组合使用，可以覆盖数据库实现课程从存储层到 SQL 层的完整谱系。