CMU 15-445 数据库系统 课程笔记
教师：Andy Pavlo
#Lecture 1: 背景
- DB vs DBMS
- 平面文件数据库 vs 关系型数据库
- DML: 过程式 vs 声明式(SQL)
- 关系代数: Select Projection Union Intersection Difference Product Join Observation
#Lecture 2: SQL
关系型语言
SQL标准 历史
Join
聚合函数
字符串操作: 大小写敏感 单引号 模式匹配
日期和时间
输出重定向
输出控制: ASC DESC ORDER BY LIMIT
嵌套子查询:
SELECT in SELECT
SELECT in FROM
SELECT in WHERE
通常难以优化
输出处理: ALL ANY IN EXISTS
窗口函数: OVER ORDER BY
公用表表达式(CTE): WITH 临时表, WITH RECURSIVE
#Lecture 3: 存储 Part 1
#易失性设备
一般支持高速随机按字节访问
通常叫memory
#非易失性设备
一般支持按块/页存取
通常顺序存取更快
通常叫disk
#持久化内存 / 非易失性内存
用的少 不讲
#NVMe SSDs
仍然属于disk
#面向硬盘的DBMS
Buffer Pool: 把需要用到的数据页从硬盘搬到内存上
能否利用OS的mmap()？不好，难以控制OS什么时候刷盘，可以用的：madvise(), mlock(), msync()
Storage Manager: 管理硬盘上存储的文件，记录文件包含的页，文件剩余的存储空间等
#页
- 硬件页: 4K 可以保证原子写
- OS页：4K
- 数据库页：1-16K
#页堆
堆文件组织是一种组织页的方式。包括一个堆文件，其中包含无序的页集合。
具体有两种组织方式：
- 链表：每个页指向下一个页，需要O(n)遍历，效率低
- 页目录：维护特殊的页记录每个数据页的信息
#页结构
- 页大小
- 校验码
- 版本
- 事务可见性
- 自包含
两种页内数据组织方式：
Slotted-Page
现在大多数DBMS使用的
每个slot存一个元组
头部保存slot索引，元组从后往前增长
Log-Structured
#元组结构
元组是细粒度的数据，字节序列
- 元组头
- 元组数据
- UID
- 逆正规化元组数据
#Lecture 4: 存储 Part 2
#Log-Structured
Slotted-Page的问题：
- 内碎片：删除元组产生一个空洞
- 写放大：需要读写整个块
Log-Structured 的好处：
- 日志保存的是对数据库的操作 (put, delete)
- 读记录的时候，DMBS从新到旧扫描日志文件，重建元组
- 写很快，读可能会慢，已经写过的页是不可变的，减小随机IO
- …
#数据表示
- 整数，浮点数：INTEGER，BIGINT，SMALLINT，TINYINT，FLOAT，REAL 按照IEEE-754标准，与C++类型一致
- 定点数：NUMERIC，DECIMAL，存储方式类似字符串
- 变长数据：VARCHAR，VARBINARY，TEXT，BLOB
- 日期和时间：TIME，DATE，TIMESTAMP
#Lecture 5: 存储模型 & 压缩
#数据库的Workload
- OLTP
- OLAP
- HTAP
#存储模型
- NSM n元存储模型
- …
- DSM 分解存储模型
- …
- PAX 分区字段
- …
#数据库压缩
- 真实世界的数据都是高可压缩的
- 元组的字段之间有很强的关联性
压缩的要求
- 压缩完最好是固定长度
- lazy解压
- 必须是无损压缩
压缩粒度
- 块级别
- 元组级别
- 字段级别
- 列级别
#简易压缩
#列式压缩
- 游程编码
- 位编码
- …
#Lecture 6: 缓冲池
Project 1内容，略
#OS 页缓存
大多数DBMS绕过OS的页缓存（通过直接IO），Postgres除外
#磁盘IO调度
- Sequencial vs. Random I/O
- Critical Path Task vs. Background Task
- Table vs. Index vs. Log vs. Ephemeral Data
- Transaction Information
- User-based SLAs
#Lecture 7: 哈希表
数据结构课几乎都学过，略
SOTA哈希函数：XXHash3
哈希表 = 哈希函数 + 哈希策略
哈希策略：解决哈希冲突的方法
静态哈希策略
- 线性扫描哈希
- Cuckoo哈希
动态哈希策略
- 链式哈希
- 可拓展哈希
- 线性哈希
#Lecture 8: 树索引
数据结构课几乎都学过，略
#Lecture 9: 索引并发控制
锁，OS课几乎都学过，略
#Lecture 10: 排序 & 聚合算法
#查询计划
DBMS 会首先把SQL编译成查询计划，编译的目标是最小化I/O。
#排序
关系模型没有定义数据元组保存的顺序，当执行 ORDER BY, GROUP BY, JOIN, DISTINCT 运算符的时候，可能需要先对数据排序。对于小数据直接在内存中排序，大量数据就需要用到外排序。
外排序的标准算法是使用归并排序。
- 两路归并
- K路归并
优化思路：
- 双倍缓冲优化
- 比较优化
- 用B+树索引
另外，当查询同时包含了 ORDER BY 和 LIMIT 时，就等价于查询数据的 Top-N 元素，可以用另外的算法。
#聚合
聚合运算将一个或多个元组合并成单个标量值。运算符包括 GROUP BY，
#Lecture 11: 连接算法
The goal of a good database design is to minimize the amount of information repetition.
TODO
#Lecture 12 & 13: 查询执行
#查询计划
DBMS 首先把 SQL 命令转换成查询计划 (query plan)，然后再执行，为了方便优化和debug；
查询计划按照数的结构组织，数据从叶子节点计算到跟节点。
#处理模型
处理模型决定如何执行一个查询计划，主要有三种：
- 迭代器模型 (aka, 火山模型, Pipeline模型)
- 物化模型
- 向量/批处理模型
处理顺序可以是自顶向下，也可以是自底向上；
迭代器模型
物化模型
是迭代器模型的一种特例，每个operator在一次调用中处理完所有需要的数据；
为了防止数据太多，DBMS可以传递limit信息给operator
向量模型
和迭代器模型类似，但是每次Next函数返回一批数据，而不是单个tuple；
这样允许使用SIMD等指令优化速度；
#数据访问方法
DBMS读数据有两种最基本的操作：Sequential Scan 和 Index Scan；
针对Sequential Scan的优化方法：
- Prefetch
- Buffer Pool Bypass
- Parallelization
- Late Materialization
- Heap Clustering
- Approximate Queries
- Zone Map
#修改数据
会修改数据的Operator需要额外维护索引信息。
UPDATE/DELETE Operator需要记录RID，否则会有万圣节问题
万圣节问题：Update操作改变了tuple的位置，使得一条数据被scan了两遍；
#表达式求值
每个tuple都执行一遍表达式很慢，成熟的DBMS会根据cost模型决定要不要把表达式JIT编译；
#分布式数据库
现在大部分的DBMS都采用了thread per worker的方式；
#IO并行
多硬盘并行
数据库分区
#Lecture 14: 查询计划 & 查询优化
SQL是一种声明式语言，只说了要计算什么，但并没有说明如何去计算；
DBMS需要先把SQL转换成实际的查询计划以便执行；
IBM System R在1970s实现了第一个查询优化器，在此之前，人们普遍认为DBMS生成的查询计划不会比人写的更好；
两种优化的策略：
- 基于静态规则
- 基于cost
逻辑查询计划 vs 物理查询计划
#逻辑查询优化
#Cost估计
直方图
采样
#Lecture 15: 并发控制理论
两个并发的问题：
- 并发控制：两个事务同时更新一条记录怎么处理；
- 持久性：断电怎么保证状态正确；
#事务
最简单的实现是每次执行事务时，复制所有文件。
事务的特性：
- 原子性A：原子性确保事务中的所有操作都发生，或者不发生。
- 一致性C：如果每个事务是一致的，并且数据库在事务开始时是一致的，那么在事务完成时保证数据库是一致的。如果数据满足所有验证规则（如约束、级联和触发器），则数据是一致的。
- 隔离性I：隔离是指当一个事务执行时，它应该有一种错觉，即它与其他事务是隔离的。隔离可确保事务的并发执行应具有与事务的顺序执行相同的生成数据库状态。
- 持久性D：如果事务提交，则其对数据库的影响应持续存在。
#原子性
实现原子性的两种方案：
- 用日志记录所有操作：通过日志来实现事务回滚，在内存和硬盘都保存一份，常用；
- CoW创建Page的副本：回滚性能较好，运行时性能较差，不常用；
#一致性
- 数据库一致性：数据库准确地表示它正在建模的真实实体，并遵循完整性约束。（例如，一个人的年龄不能是负数）。此外，将来的事务应在数据库中看到过去提交的事务的影响。
- 事务一致性：如果数据库在事务开始前是一致的，那么在事务开始之后也会保持一致。确保事务一致性是应用程序的责任。
#隔离性
事务仿佛在系统中单独运行，看不到并发事务的影响。
并发控制：
- 悲观
- 乐观
#持久性
在崩溃或重新启动后，已提交事务的所有更改都必须是持久的（即持久的）。
#Lecture 16: 两阶段锁
- Shared (S)：读锁
- Exclusive (X)：写锁
两阶段锁是乐观并发控制方法的一种，特点是第一阶段只获取锁，第二阶段只释放锁；
2PL能够保证冲突序列化；但是不能处理cascading aborts（回滚事务A导致事务B读到坏数据）；
2PL会有脏读的问题，依然可能导致死锁；
严格2PL：在2PL的基础上，还要求必须commit之后才能释放锁；
严格2PL能处理cascading aborts，但是会降低并发度；
死锁检测和死锁避免：略
锁粒度：数据库级别，表级别，页级别，tuple级别
意向锁：保证不同粒度的锁之间的互斥（例如表锁和表中的行锁）的锁，具体分为：
- Intention-Shared (IS)：整块区域的读锁；
- Intention-Exclusive (IX)：整块区域的写锁；
- Shared+Intention-Exclusive (SIX)：S+IX，表示事务要读全部行+更新部分行；
#Lecture 17: 时间戳顺序
时间戳顺序 (Timestamp ordering, T/O) 是一种不需要锁的并发控制手段；
每个事务都会分配一个单调递增的唯一的时间戳，
#基本时间戳顺序 (BASIC T/O)
为每个tuple记录上一次读和写的时间戳，
读操作：检查时间戳，如果是过去的；
写操作：
Thomas Write Rule：
#乐观并发控制 (OCC)
乐观并发控制 (OCC) 是另一种并发控制方案，为每个事务保存要操作的数据的副本；
读操作：读数据复制一份
校验操作
写操作：
#幻读问题
因为一个事务可能会插入新数据，新的数据没有上锁；
- 重新执行一遍scan：Commit的时候重新执行一遍WHERE字句；
- 条件加锁：根据条件判断的结果加锁；
- 索引加锁：利用索引键保护数据；
- K-V锁：对单独一条数据的锁
- 间隙锁：对两条数据之间空隙的锁，防止插入新数据；
- 范围锁：对一段数据的锁；
- 层次锁：
#隔离级别
异常现象：
- 脏读
- 不可重复读
- 幻读
- 【NEW】丢失更新
- 【NEW】Write skew
SQL-92标准隔离级别
- 序列化：Index Lock+严格2PL
- 【NEW】快照隔离；
- 可重复读：严格2PL
- 【NEW】游标稳定性：IBM DB2默认级别，避免了丢失更新
- 读已提交：写锁执行严格2PL，读锁在读后立即释放（Short duration）
- 读未提交：写锁执行严格2PL，读不加锁
额外的隔离级别：
#Lecture 18: MVCC
多版本并发控制 (MVCC) 是最广泛使用的数据库并发控制方法。