CS 自学指南 · Caltech CS122 数据库系统实现:从 SQL 层到查询优化器的完整实践

本篇对应 CS 自学指南 数据库系统模块下的 Caltech CS 122:Database System Implementation 课程条目(中文页 docs/数据库系统/CS122.md,英文页 docs/数据库系统/CS122.en.md)。它聚焦一门以 Java 实现数据库 SQL 层与查询优化器为核心目标的高难度实践课:从 SQL 解析、Translate、Join 计划节点,到统计信息收集、代价估计与谓词选择性计算,再到 B+ 树与 WAL 实验。读完本篇,你可以明确 CS122 在整个数据库自学路线中的位置、七个 Assignment 分别要攻克哪些组件,以及用 IDEA + Maven 开展实验的工程要点。

课程档案与定位

CS122 的基本档案如下(与原文档一致):

项目	内容
所属大学	加州理工学院(Caltech)
先修要求	无(课程官方未设硬性先修)
编程语言	Java
课程难度	五星(指南中数据库模块最高档之一)
预计学时	约 150 小时
课程作业	7 个 Assignments + 2 个 Challenges

CS122 的定位需要放在"实现一个数据库"这条主线上看。指南中同模块的 CMU 15-445 是公认的数据库入门神课,其实验围绕 C++ 教学数据库 bustub 展开,覆盖 Buffer Pool、B+ 树、算子与优化器、并发控制等组件,但不提供 SQL 层功能;而 CS122 的 Lab 恰恰补上了这块拼图——它的侧重点是 SQL 层的相关实现,涉及查询优化器的各个模块:SQL 的解析(Parsing)、Translate、如何实现 Join、统计信息(Statistics)以及代价估计(Cost Estimation)、子查询(Subquery)实现、Aggregation 与 Group By 的实现等。除此之外,课程还有 B+ 树和 Write-Ahead Logging(WAL)相关实验。

因此指南给出的建议很明确:本门课程适合在学完 CMU 15-445 之后,对查询优化相关内容有兴趣的同学。也就是说,15-445 帮你打通存储、缓冲、并发这些"地基",CS122 则带你进入"如何把一条 SQL 翻译成高效的执行计划"这一上层领域。二者的语言与代码库也不同:15-445 是 C++(bustub),CS122 是 Java(NanoDB 教学数据库),正好可以兼顾两种工程生态。

在指南的数据库系统章节导语中,核心主张是"没有什么能比自己写个关系型数据库更能加深对数据库系统的理解了"。CS122 与同模块的 Stanford CS346(RedBase,C++)、UCB CS186(Java 实现支持 SQL 并发查询、B+ 树索引与故障恢复的数据库)属于同一梯队,而 CS122 的独特之处正是 SQL 层与优化器的纵深。学完数据库基础课之后,若还想拓宽视野,指南还收录了 CMU 15-799 这类专题进阶课。

技术主线:SQL 层与查询优化器

CS122 覆盖的模块几乎是一张"从 SQL 字符串到物理执行计划"的完整流水线,按数据流顺序可以拆解为以下几段(以下概念说明属于通用的数据库系统背景知识,帮助理解实验目标):

SQL 解析与 Translate

SQL 层的第一关是把 SQL 文本变成程序可操作的结构。解析阶段(通常借助 ANTLR 等工具生成 parser)把 SELECT ... WHERE ... GROUP BY ... 这类语句变成解析树/AST;Translate 阶段再把解析树转换为一棵逻辑执行计划树——Seq Scan(顺序扫描)、Filter(过滤)、Join、Aggregate 等逻辑算子,并在此阶段完成关系名、列名到表结构元数据的绑定。CS122 的 Assignment 2 要求实现的"计划生成器(Plan Generator)",正是解析树/AST 到可执行计划这一转换环节的落点。

Join 计划节点

Join 是查询优化的核心难点之一。CS122 的实验要求基于 nested-loop join(嵌套循环连接) 算法实现支持 inner join 和 outer join 的 Join 计划节点。嵌套循环连接的执行模型是对外层每一行,扫描内层数据逐行匹配,适合理解连接语义的正确性定义;而 outer join(左/右外连接)还要求在"无匹配"时保留未连接的外侧行——这也是为什么 Assignment 2 明确强调要为 inner 与 outer 连接分别编写单元测试来保证正确性,因为外连接的 NULL 补位语义极易写错。

统计信息与代价估计

一条 SQL 往往存在多种可行的执行计划,优化器要靠代价模型从中挑选。代价模型的输入是元组基数(cardinality)估计,而基数估计的核心工具是谓词选择性(selectivity):例如对 WHERE 子句中每个谓词估算其过滤比例,再用它逐级更新计划各节点输出的元组统计信息。这正是 Assignment 3 的四项任务(统计收集、节点成本计算、谓词选择性、统计信息更新)背后的完整逻辑链:先采集表级统计信息,再为各类计划节点定义成本函数,最后让选择性感应每一层过滤对输出行数的影响。

Aggregation / Group By 与子查询

Aggregation 与 Group By 的实现要处理分组键的归组、聚合函数(SUM、COUNT、AVG 等)的增量计算,以及分组与过滤在计划中的先后顺序;子查询实现则涉及 IN、EXISTS 等语义的改写或嵌套执行。这两块都是 SQL 层区别于"仅有算子库"的课程的关键增量,也是 CS122 相对 15-445 的差异化价值所在。

B+ 树与 WAL

除 SQL 层主线外,课程还包含 B+ 树(存储引擎中最核心的索引结构)与 WAL(Write-Ahead Logging,崩溃恢复的基础机制)相关实验。这两项与 CMU 15-445 的 Project 内容(缓冲池、B+ 树索引、日志恢复/并发)形成对照:如果已在 15-445 中实现过 C++ 版本,在 NanoDB 上以 Java 再做一遍,有助于从两种语言/两套代码结构中巩固对同一组件的理解。

实验(Assignment)详解

原文档对前三个 Assignment 做了逐条介绍,以下完整保留并逐项展开其技术含义;其余 Assignment 与 Challenges 的完整清单需查阅课程官网介绍(指南建议以课程描述为准)。

Assignment 1:DELETE / UPDATE 与缓冲池正确性

• 为 NanoDB 提供 DELETE、UPDATE 语句的支持:即在已有查询/插入能力的基础上补全 DML 闭环。UPDATE 涉及先定位目标行、修改页内记录并处理页分裂/重组的连带影响;DELETE 则要考虑标记删除与页空间回收。
• 为 Buffer Pool Manager 添加合适的 pin/unpin 代码:这是缓冲池使用的"纪律性"修正。页被 pin 后驻留在内存中受保护,unpin 释放引用;pin 计数不正确会导致页被提前换出、指针悬空。这一任务本质上是让 NanoDB 的页生命周期管理变得可推理、可测试。
• 提升 INSERT 语句的性能,同时不使数据库文件大小过分膨胀:性能与文件占用的权衡题——朴素地每次插入都追加新页会让数据文件快速膨胀,合理做法涉及页内空闲空间管理与页分配策略。

Assignment 2:计划生成器与嵌套循环 Join

• 实现一个简单的计划生成器,将各种已经 Parser 过的 SQL 语句转化为可执行的执行计划——这是把"语法正确"推进到"可执行"的关键一步;
• 使用 nested-loop join 算法,实现支持 inner join 与 outer join 的 Join 计划节点;
• 添加单元测试,保证 inner join 与 outer join 的功能实现正确。

注意这里的教学顺序:先有可用的 join 物理算子与测试基线,后续 Assignment 3 的代价估计才有优化对象。

Assignment 3:统计信息、代价与选择性

• 完成收集表的统计信息(如行数、页数、列取值分布等,作为优化器的输入);
• 完成各种计划节点的计划成本计算(为每类节点定义成本函数);
• 计算可出现在执行计划中的各种谓词的选择性(等值、范围等谓词的过滤比例估计);
• 根据谓词更新计划节点输出的元组统计信息(沿计划树向上传播基数估计)。

这四项任务构成一个自洽的代价驱动优化闭环:统计信息是原料,选择性是估计工具,节点成本是决策依据,元组统计更新则保证每一层算子"看到"的输入规模是修正后的值。

其余 Assignment 与 Challenges

课程共 7 个 Assignments + 2 个 Challenges,前三个覆盖了 DML/缓冲池、计划生成与 Join、统计与代价三大块,后续部分(子查询、Aggregation/Group By、B+ 树、WAL 等方向)请按课程官网的介绍核对具体清单与要求。

学习环境:IDEA + Maven 与日志配置

指南对 CS122 给出的工程化建议是:推荐使用 IDEA(IntelliJ IDEA)打开工程,使用 Maven 构建,并注意日志相关配置。结合这类 Java 课程的通用实践,可以补充几点可操作的理解:

• NanoDB 工程是标准的 Maven 项目,IDEA 可直接导入 pom.xml 完成依赖解析与工程识别,之后用 Maven 完成编译、测试与打包;
• 各 Assignment 都强调单元测试(如 Assignment 2 明确要求为 join 节点补测试),日常开发循环建议以"改代码 → 跑测试"为最小闭环;
• "注意日志相关配置"提示:课程代码中日志输出通常由 log 配置文件(如 log4j/logback 一类)控制,环境导入后若发现控制台输出缺失或格式异常,先检查工程内的日志配置文件,而不是怀疑测试逻辑本身。

需要说明的是,上述构建与日志细节属于通用 Java 工程实践,具体以 NanoDB 课程仓库的实际工程结构为准。

与指南内其他数据库课程的对照

结合本仓库同模块文档,四门"动手实现数据库"的课程可这样取舍(语言、难度、学时均取自各自课程条目):

课程	语言	侧重点	难度	预计学时
CMU 15-445	C++	缓冲池、B+ 树/哈希索引、算子与优化器、并发控制;无 SQL 层	四星	约 100 小时
Caltech CS122	Java	SQL 层与查询优化器:解析/Translate、Join、统计与代价、子查询、Agg/Group By;另有 B+ 树与 WAL 实验	五星	约 150 小时
Stanford CS346	C++	RedBase:记录管理、索引、系统管理、RQL 查询语言 + 扩展	五星	约 150 小时
UCB CS186	Java	SQL 并发查询、B+ 树索引与故障恢复	—	—

一条被指南隐含支持的进阶路线是:CMU 15-445(地基)→ Caltech CS122(SQL 层与优化器)→ CMU 15-799(前沿专题,如 Self-Driving DBMS)。若偏好 C++ 生态,则可用 Stanford CS346 的 RedBase 替代 CS122 承担"继续拼组件"的角色。

课程资源与适用前提

原文档列出的课程资源:

• 课程网站:Caltech CMS 的 CS122 课程页(courses.cms.caltech.edu 的 cs122 栏目);
• 课程代码:Caltech 内部 GitLab 上的 cs122-19wi 仓库;
• 课程教材:无(以课程材料为准);
• 课程作业:7 个 Assignments + 2 个 Challenges。

适用前提与限制方面,有三点需要留意:其一,课程档案标注"先修要求:无",但指南明确指出更适合完成 15-445 后再学,因为 SQL 层建立在缓冲池、存储等下层概念之上;其二,课程以 Java 进行,若你更习惯 C++,可评估先走 15-445/CS346 路线;其三,课程代码托管在 Caltech 的 GitLab 而非公开开源仓库,获取渠道以课程官网说明为准,自学时需确认自己能够访问该仓库,否则实验环节无法开展。

小结

CS122 在 CS 自学指南数据库模块中的角色可以概括为一句话:15-445 教你把数据库的"下半身"(缓冲、索引、并发)跑通,CS122 教你把"上半身"(SQL 解析、计划生成、统计与代价驱动的优化)补全。如果你已完成一门数据库实现基础课,并且对"一条 SQL 究竟是如何被翻译成高效执行计划的"这个问题有实打实的好奇心,那么这门 150 小时的 Java 实践课值得排入你的学习计划。