CS20-数据库系统

UCB CS186: Introduction to Database System

课程简介

所属大学：UC Berkeley
先修要求：CS61A, CS61B, CS61C
编程语言：Java
课程难度：🌟🌟🌟🌟🌟
预计学时：150 小时

如何编写 SQL 查询？SQL 命令是如何被一步步拆解、优化、转变为一个个磁盘查询指令的？如何实现高并发的数据库？如何实现数据库的故障恢复？什么又是非关系型数据库？这门课会带你深入理解关系型数据库的内部细节，并在掌握理论知识之后，动手用 Java 实现一个支持 SQL 并发查询、B+ 树 Index 和故障恢复的关系型数据库。

从实用角度来说，这门课还会在编程作业中锻炼你编写 SQL 查询以及 NoSQL 查询的能力，对于构建一些全栈的工程项目很有帮助。

课程资源

课程网站：https://cs186berkeley.net/
课程视频：https://www.bilibili.com/video/BV13a411c7Qo
课程教材：无
课程作业：6 个 Project

资源汇总

@PKUFlyingPig 在学习这门课中用到的所有资源和作业实现都汇总在 PKUFlyingPig/CS186 – GitHub 中。

CMU 15-445: Database Systems

课程简介

所属大学：CMU
先修要求：C++，数据结构与算法，CMU 15-213 (A.K.A. CS:APP，这也是 CMU 内部对每年 Enroll 同学的先修要求)
编程语言：C++
课程难度：🌟🌟🌟🌟
预计学时：100 小时

作为 CMU 数据库的入门课，这门课由数据库领域的大牛 Andy Pavlo 讲授（“这个世界上我只在乎两件事，一是我的老婆，二就是数据库”）。

这是一门质量极高，资源极齐全的 Database 入门课，这门课的 Faculty 和背后的 CMU Database Group 将课程对应的基础设施 (Autograder, Discord) 和课程资料 (Lectures, Notes, Homework) 完全开源，让每一个愿意学习数据库的同学都可以享受到几乎等同于 CMU 本校学生的课程体验。

这门课的亮点在于 CMU Database Group 专门为此课开发了一个教学用的关系型数据库 bustub，并要求你对这个数据库的组成部分进行修改，实现上述部件的功能。

具体来说，在 15-445 中你需要在四个 Project 的推进中，实现一个面向磁盘的传统关系型数据库 Bustub 中的部分关键组件。

包括 Buffer Pool Manager (内存管理), B Plus Tree (存储引擎), Query Executors & Query Optimizer (算子们 & 优化器), Concurrency Control (并发控制)，分别对应 Project #1 到 Project #4。

值得一提的是，同学们在实现的过程中可以通过 shell.cpp 编译出 bustub-shell 来实时地观测自己实现部件的正确与否，正反馈非常足。

此外 bustub 作为一个 C++ 编写的中小型项目涵盖了程序构建、代码规范、单元测试等众多要求，可以作为一个优秀的开源项目学习。

课程资源

课程网站：Fall 2019, Fall 2020, Fall 2021, Fall 2022, Spring 2023
课程视频：课程网站免费观看, Fall 2022 的 Youtube 全开源 Lectures
课程教材：Database System Concepts
课程作业：5 个 Project 和 5 个 Homework

在 Fall 2019 中，Project #2 是做哈希索引，Project #4 是做日志与恢复。

在 Fall 2020 中，Project #2 是做 B 树，Project #4 是做并发控制。

在 Fall 2021 中，Project #1 是做缓存池管理，Project #2 是做哈希索引，Project #4 是做并发控制。

在 Fall 2022 中，与 Fall 2021 相比只有哈希索引换成了 B+ 树索引，其余都一样。

在 Spring 2023 中，大体内容和 Fall 2022 一样（缓存池，B+ 树索引，算子，并发控制），只不过 Project #0 换成了 Copy-On-Write Trie，同时增加了很好玩的注册大小写函数的 Task，可以直接在编译出的 bustub-shell 中看到自己写的函数的实际效果，非常有成就感。

值得注意的是，现在 bustub 在 2020 年以前的 version 都已经停止维护。

Fall 2019 的最后一个 Logging & Recovery 的 Project 已经 broken 了（在19年的 git head 上也许还可以跑，但尽管如此 Gradescope 应该也没有提供公共的版本，所以并不推荐大家去做，只看看代码和 Handout 就可以了）。

或许在 Fall 2023 的版本 Recovery 相关的功能会被修复，届时也可能有全新的 Recovery Project，让我们试目以待吧🤪

如果大家有精力的话可以都去尝试一下，或者在对书中内容理解不是很透彻的时候，尝试做一做对应的 Project 会加深你的理解（个人建议还是要全部做完，相信一定对你有帮助）。

资源汇总

非官方的 Discord 是一个很好的交流平台，过往的聊天记录几乎记载了其他同学踩过的坑，你也可以提出你的问题，或者帮忙解答别人的问题，相信这是一份很好的参考。

关于 Spring 2023 的通关指南，可以参考 @xzhseh 的这篇CMU 15-445/645 (Spring 2023) Database Systems 通关指北，里面涵盖了全部你需要的通关道具，和通关方式建议，以及最重要的，我自己在做 Project 的过程中遇到的，看到的，和自己亲自踩过的坑。

@ysj1173886760 在学习这门课中用到的所有资源和作业实现都汇总在 ysj1173886760/Learning: db – GitHub 中。

由于 Andy 的要求，仓库中没有 Project 的实现，只有 Homework 的 Solution。特别的，对于 Homework1，@ysj1173886760 还写了一个 Shell 脚本来帮大家执行自动判分。

另外在课程结束后，推荐阅读一篇论文 Architecture Of a Database System，对应的中文版也在上述仓库中。论文里综述了数据库系统的整体架构，让大家可以对数据库有一个更加全面的视野。

后续课程

CMU15-721 主要讲主存数据库有关的内容，每节课都有对应的 paper 要读，推荐给希望进阶数据库的小伙伴。@ysj1173886760 目前也在跟进这门课，完成后会在这里提 PR 以提供进阶的指导。

Caltech CS122: Database System Implementation

课程简介

所属大学：Caltech
先修要求：无
编程语言：Java
课程难度：🌟🌟🌟🌟🌟
预计学时：150 小时

加州理工的这门课，不同于没有提供 SQL 层功能的 CMU15-445 课程。CS122 课程 Lab 的侧重点在于 SQL 层的相关实现，涉及查询优化器的各个模块，比如SQL的解析，Translate，如何实现 Join，统计信息以及代价估计，子查询实现，Agg，Group By 的实现等。除此之外，还有 B+树，WAL 相关实验。本门课程适合在学完 CMU15-445 课程之后，对查询优化相关内容有兴趣的同学。

下面介绍一下这门课的前 3 个 Assignment 也就是实验 Lab 所要实现的功能：

Assignment1

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

Assignment2

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

Assignment3

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

剩余 Assignment 和 Challenges 可以查看课程介绍，推荐使用 IDEA 打开工程，Maven 构建，注意日志相关配置。

课程资源

课程网站：http://courses.cms.caltech.edu/cs122/
课程代码：https://gitlab.caltech.edu/cs122-19wi
课程教材：无
课程作业：7 Assignments + 2 Challenges

Stanford CS346: Database System Implementation

课程简介

所属大学：Stanford
先修要求：无
编程语言：C++
课程难度：🌟🌟🌟🌟🌟
预计学时：150 小时

RedBase 是 cs346 的一个项目，实现了一个简易的数据库系统，项目是高度结构化的。整个项目能够被分为以下几个部分（同时也是 4 个需要完善的 lab）：

The record management component：记录管理组件。
The index component：B+ 索引管理。
The System Management Component：ddl语句、命令行工具、数据加载命令、元数据管理。
The Query Language Component：在这个部分需要实现 RQL Redbase 查询语言。RQL 要实现 select、insert、delete、update 语句。
Extension Component：除了上述数据库系统的基本功能组件，还需要实现一个扩展组件，可以是 Blob 类型、网络模块、连接算法、CBO 优化器、OLAP、事务等。

RedBase 适合在学完 CMU 15-445 后继续学习数据库系统中的其他组件，因为其代码量不多，可以方便的根据需要扩展代码。同时代码完全由 C++ 编写，也可以用于练习 C++ 编程技巧。