【数据库系统】课程笔记 - part 3

wishapig · 2026-07-23 15:10:35 · 算法·理论

写在前面：

成绩 93/100，绩点 4.8。

由于 db 的笔记有点太多了（12 个 md 文档加在一起有 122K），因此将其按顺序均分为 3 个部分，每个部分包含 4 个 Lecture。

注：Lecture 1 为导论课，Lecture 7 为期中考试复习课，因此没有记录笔记。

另注：我已经尽可能写的详细了，但仍不保证知识点覆盖完全。

【数据库系统】课程笔记 - part 1：https://www.luogu.com.cn/article/47sozboa

【数据库系统】课程笔记 - part 2：https://www.luogu.com.cn/article/xcqqbg8c

【数据库系统】课程笔记 - part 3：https://www.luogu.com.cn/article/fk3j2hgg

Lecture 11 - Query Optimization

Introduction

同一个查询语句可能有多重不同的写法，而执行它们所需的代价可能差别很大，因此这一章就聚焦于如何优化查询。

如上图，两个语法树是等价的，但显然右侧的执行速度会更快，因为它先对 instructor 表进行了一次筛选，之后的连接操作就会少很多项。

Transformation of Relational Expressions

定义：两个关系代数的表达式是等价的，当且仅当对任意的例子两个表达式得到的结果都是一样的（结果中各个元组的顺序和各个字段的顺序是无所谓的）

Equivalence Rules

• Conjunctive selection 可以分解成一系列嵌套的筛选：\sigma_{\theta_1\land\theta_2}(E)=\sigma_{\theta_1}(\sigma_{\theta_2}(E))
• Selection operations 存在交换律：\sigma_{\theta_1}(\sigma_{\theta_2}(E))=\sigma_{\theta_2}(\sigma_{\theta_1}(E))
• 多层投影嵌套时，只有最外一层有用：\prod_{L_1}(\prod_{L_2}(\cdots(\prod_{L_n}(E))\cdots))=\prod_{L_1}(E)
• 选择条件可以下放到连接条件中：\sigma_{\theta}(E_1\times E_2)=E_1\bowtie_{\theta}E_2，\sigma_{\theta_2}(E_1\bowtie_{\theta_1}E_2)=E_1\bowtie_{\theta_1\land\theta_2}E_2
• \theta$ 连接存在交换律（注意得把 $\theta$ 反过来写，等值连接和自然连接无所谓）：$E_1\bowtie_{\theta}E_2=E_2\bowtie_{\theta'}E_1
• 自然连接存在结合律：(E_1\bowtie E_2)\bowtie E_3=E_1\bowtie(E_2\bowtie E_3)，这也表明了，最终结果都一样，那么就会选择 (E_1\bowtie E_2) 和 (E_2\bowtie E_3) 较小的那个先做（有点类似哈夫曼编码）
• 集合的交/并都存在交换律，结合律
• 选择操作和投影操作有时可以下放到连接操作之前，即先选后连和先投后连

上图就用了先选后连，将 \sigma_{\rm dept\_name="music"} 提前到连接操作之前先对 instructor 做。

上图同理，将两个选择操作下放到先对两张表进行选择再做连接。

Enumeration of Equivalent Expressions

普通的方法就是暴力搜索所有可能的优化方法，但显然搜索的时间是无法接受的，因此实际中需要基于一些经验规则进行启发式的优化。

Statistics for Cost Estimation

在具体分析之前，先给出一些参数的定义：

• f_r$：单个 block 包含的元组个数，那么 $b_r=\lceil n_r/f_r\rceil

Selection Size Estimation

• \sigma_{A=v}(r)$：假设所有 $A$ 的取值均匀分布：$n_r/V(A,r)$，如果 $A$ 是 key attribute 则直接估计为 $1
• - $0$，如果 $v<\min(A,r)
  • 如果缺少了 \min,\max 的统计，则取期望 n_r/2

复杂的选择语句

涉及到多个选择条件 \theta_1,\theta_2,\cdots 的合取或者析取，设 s_i 表示满足条件 \theta_i 的元组个数，P_i=s_i/n_r 表示满足条件 \theta_i 的概率，那么：

• Conjunction \sigma_{\theta_1\land\theta_2\land\cdots\land \theta_n}(r)=n_r\times \prod_{i}P_i
• Disjunction \sigma_{\theta_1\lor\theta_2\lor\cdots\lor\theta_n}(r)=n_r\times(1-\prod_{i}(1-P_i))
• Negation \sigma_{\neg\theta}(r)=n_r-\operatorname{size}(\sigma_{\theta}(r))

注意，上述估计需要保证各个条件是独立的，否则分析会更复杂一些。

Estimation of the Size of Joins

来分析一下连接操作得到结果的大小。

• 显然，笛卡尔积 r\times s 的大小为 n_r\times n_s 个元组

• 如果 R\cap S=\emptyset，那么 r\bowtie s=r\times s

• 如果 R\cap S 是 R 的键（值不重复），那么一个 s 中的元组至多和一个 r 中的元组连接，因此大小不会超过 n_s

  • 更特殊地，如果 R\cap S 是 S 中参照 R 的外键，那么 r\bowtie s 的大小就是 n_s

• 如果 R\cap S=\{A\} 不是 R,S 的键，那么有两种估计方式：

  \begin{aligned} n_r\times \dfrac{n_s}{V(A,s)}\\ n_s\times \dfrac{n_r}{V(A,r)} \end{aligned}

  即假设所有取值均匀分布，分别分析每个 r,s 中的元组能和多少个另一个表中元组连接，通常会取两个结果中的较小值

Size Estimation for Other Operations

• 投影操作：\prod_{A}(r) 的大小估计为 V(A,r)
• 聚合操作：_{A}g_F(r) 的大小估计为 V(A,r)
• 外连接 (outer join)：
  • 左外连接 r,s 的大小估计为 r\bowtie s 的大小加上 n_r，右外连接同理
  • full outer join r,s 的大小估计为 r\bowtie s 的大小加上 n_r+n_s
  • 外连接的符号有点奇怪，放一张图：
• 集合操作：r\cup s,r\cap s,r-s 的大小分别估计为 n_r+n_s,\min(n_r,n_s),n_r，这样的估计可能非常不准确，但提供了一个上界

Estimation of Number of Distinct Values

估计 \sigma_{\theta}(r) 中不同值的个数 V(A,\sigma_{\theta}(r))：

• 如果筛选条件 \theta 迫使 A 只能取一种数或某些数，此时 V(A,\sigma_{\theta}(r)) 即为可能的取值种类数
• 如果筛选条件 \theta 的形式为 A\operatorname{op} r，那么估计 V(A,\sigma_{\theta}(r))=V(A,r)\times s，其中 s 称为选择度 (selectivity)，取值在 [0,1] 中（相当于有多少种取值可以筛选通过）
• 其他情况，估计 V(A,\sigma_{\theta}(r)) 为 \min(V(A,r),n_{\sigma_{\theta}(r)})，更准确的估计需要用到概率论，不过这个结果通常够用

估计 r\bowtie s 中不同值的个数 V(A,r\bowtie s)：

• 如果 A\subseteq R，那么估计 V(A,r\bowtie s)=\min(V(A,r),n_{r\bowtie s})

• 如果 A 包含了来自于 R 的部分 A_1 和来自于 S 的部分 A_2，那么估计：

  V(A,r\bowtie s)=\min(V(A_1,r)\times V(A_2-A_1,s),V(A_2,s)\times V(A_1-A_2,r),n_{r\bowtie s})

  更准确的估计需要用到概率论，不过这个结果通常够用

其他几种操作（投影，聚合等）不作介绍。

Choice of Evaluation Plans

选择一个综合最好的执行方案可能比较困难，通常按照经验规则，同时这里主要考虑连接操作的优化。

• 否则，就读出此时 Q 的内容，并更新 R-timestamp(Q)
• 若 TS(T_i) 小于 R-timestamp(Q)，则说明此时 Q 的新值是之前某个 read 操作需要的，因此写操作被拒绝，需要回滚 T_i
• 若 TS(T_i) 小于 W-timestamp(Q)，则说明 T_i 尝试写入写入一个过时的 Q 值，因此写操作被拒绝，需要回滚 T_i
• 否则进行写操作，并更新 W-timestamp(Q)

如果事务需要被回滚，则需要赋予新的时间戳并重新启动这个事务。

这种协议可以保证冲突可串行，且无死锁，但无法保证可恢复性（需要回滚一个已经 commit 的事务）以及无级联性。

Thomas' Write Rule

在上面写操作的第二条中，若 TS(T_i) 小于 W-timestamp(Q)，直接忽略此时的 write 操作即可。

Validation-Based Protocols

也被称为乐观并发控制 (Optimistic Concurrency Control)，即先假设冲突不会发生，让事务先执行，最后再检查冲突；如果冲突了，就回滚重来。在冲突概率很低的时候，这种控制方法效率很高，能提供更高的并发度。

事务执行的三个阶段：

• 读取与执行，此时 T_i 会正常读取数据库中的内容并执行自己的逻辑，但写操作不会直接修改数据库，而是只写到一个属于自己的临时副本中，对应时间戳 {\rm Start}(T_i)
• 验证，即检查此时写回数据库会不会破坏事务的可串行化，对应时间戳 {\rm Validation}(T_i)
• 写，如果上一步中验证通过则正常写回数据库，否则需要回滚这个事务，重新执行，对应时间戳 {\rm Finish}(T_i)

这里验证阶段和写阶段都被认为是原子性的，串行执行的，即同一时间只有一个事务能执行验证/写。最终串行执行顺序就按照验证阶段的时间戳来。

至于验证方法，在对事务 T_j 进行验证时，需要对所有 {\rm Validation}(T_i)<{\rm Validation}(T_j) 的事务 T_i 进行检查：

只要每个 T_i 都满足二者其一即可，否则需要回滚 T_j。

Multiple Granularity

这部分讲的是多粒度锁，即可以为不同大小的数据单元加锁。

这里不同大小的数据单元可以用一个树形结构组织起来，所有叶子节点都代表一个数据项，其他内部节点为一个表示数据集合的逻辑单元。当给一个节点加上锁时，就等价地为其子树中所有叶子节点加上了同种类型的锁。

对比一下更大的数据单元和更小的数据单元：

• 更小的数据单元，细粒度 (Fine granularity)：可以做到更高的并发度，但需要上更多的锁
• 更大的数据单元，粗粒度 (Coarse granularity)：并发度更低，但需要上的锁更少

同时，加锁时为了避免遍历整棵子树，引入了意向锁 (Intention Lock) 的概念：

• 共享型意向锁 (Intention-shared, IS)，表示后代中有 S 锁
• 排他型意向锁 (Intention-exclusive, IX)，表示后代中有 X 锁
• 共享排他型意向锁 (Shared and intention-exclusive, SIX)，表示后代中有 X 锁，且当前节点被加了 S 锁 (SIX=S+IX)

这几种锁之间的兼容关系如下图所示：

那么加锁和解锁的方式如下：

• 加锁自顶向下进行：先对根节点加上任意类型的锁
  • 当且仅当 T_i 已经给 Q 的父节点加上 IS,IX 锁时，才能给 Q 加上 S,IS 锁
  • 当且仅当 T_i 已经给 Q 的父节点加上 IX,SIX 锁时，才能给 Q 加上 X,IX,SIX 锁
• 解锁自底向上：当且仅当 T_i 没有对 Q 的任何儿子加锁时，才能给 Q 解锁

同时事务的加锁和解锁需要遵循二阶段锁协议。这样可以增强并发性，并降低加锁开销。

Multiversion Schemes

这一部分讲的是在修改时记录数据的历史版本，这样在 read 可以直接取指定的历史版本而不用回滚事务。

Multiversion Timestamp Ordering

每个成功的写操作都会创建一个新的版本，因此一个数据 Q 有多个历史版本 Q_1,Q_2,\cdots,Q_m，每个 Q_i 包括三个部分：

• Content：即这个历史版本中 Q 的值
• W-timestamp：创建这个版本的事务的时间戳
• R-timestamp：成功读这个版本的事务的最大的时间戳

在创建一个新的版本 Q_k 时，其 W-timestamp 和 R-timestamp 都被初始化为这个事务的时间戳，在每次读操作之后，也需要更新对应 Q_i 的 R-timestamp。

接下来处理读操作和写操作，假设 T_i 要对 Q 进行读或写，设 Q_k 为 W-timestamp 不大于 TS(T_i) 的最大的那个版本：

• 若为 read(Q)，则直接返回 Q_k 的 Content 即可
• 若为 write(Q)
  • 若 TS(T_i) 小于 R-timestamp，则需要回滚 T_i
  • 若 TS(T_i) 等于 W-timestamp，则直接覆写这个版本
  • 否则，创建一个新的版本

不难发现这个做法中读操作永远可以成功完成，并且可以串行化。

Multiversion Two-Phase Locking

将所有事务分成两类：更新事务和只读事务，并维护一个时间戳 ts-counter

• 只读事务：与前类似，直接找到时间戳 \le TS(T_i) 的最新版本返回即可，不需要申请任何锁，也不会被阻塞
• 更新事务：
  • 读数据：先申请一个 S 锁，并读取这个数据的最新版本
  • 写数据：先申请一个 X 锁，创建一个新的版本，并将这个版本的时间戳暂时设定为无穷大，表示还未提交
  • 提交：事务完成所有读和写之后进入提交阶段，将创造的新版本的时间戳定义为 ts-counter+1，并将 ts-counter 增加 1，然后释放所有锁

Deadlock Handling

一个系统进入了死锁状态，当且仅当每个事务都在等待另一个事务（即每个点都有一条出边，则一定会有环，即死锁）。

Deadlock prevention

死锁预防协议是用来防止这种情况发生的，下面是几种处理死锁的办法：

• 保守两阶段锁协议 (conservative 2PL)：事务在开始执行之前一次性锁定所有它要用到的数据项，而且必须遵守 “要么全锁成功，要么全不锁” 的原则
• 设置一个数据项的偏序关系，使得锁的申请一定是按某种顺序来的，这样就破坏了死锁产生的 “循环等待” 条件
• 设置一个时间阈值，如果超出了这个阈值就认为发生了死锁，直接回滚所有事务
• 当事务的等待可能会导致死锁时，回滚该事务而不是继续等待：
  • 具体通过 抢夺 (preemption) 来实现：当事务 T_j 向已被 T_i 加锁的数据项请求锁时，通过回滚 T_i，将 T_i的锁抢走，然后向 T_j 授予锁
  • 等待 - 死亡 (wait-die)（非抢夺技术）：当事务 T_i 向已被 T_j 加锁的数据项请求锁时，仅当 T_i 的时间戳小于 T_j（T_i 比 T_j 更老）的时候，T_i 可以等待，否则需要回滚 T_i
  • 受伤 - 等待 (wound-wait)（抢夺技术）：当事务 T_i 向已被 T_j 加锁的数据项请求锁时，仅当 T_i 的时间戳大于 T_j（T_i 比 T_j 更新）的时候，T_i 可以等待，否则需要回滚 T_j（T_j 被 T_i “击伤 (wound)”）

Deadlock Detection

将事务之间的等待关系建出一张有向图（等待图, wait-for gragh），则只需检查这张图中是否存在环，即可确定是否存在死锁。

Deadlock Recovery

如果已经发生了死锁，就需要回滚一些事务（称为 “受害者”）来强行打开死锁：

• 选择回滚代价最小的事务
  • 事务已经执行的时间（执行时间越短，回滚成本越低）
  • 事务已经占用的资源数量
  • 事务剩余的执行步骤数
  • 事务的优先级（低优先级事务优先被选）
• 有两种回滚方法：
  • 完全回滚 (total rollback)：直接中止整个事务，然后重新启动它，这样实现简单，但成本较高：事务之前做的所有工作都白费了，需要从头开始执行
  • 部分回滚 (partial rollback)：只回滚事务到 “刚好打破死锁” 的状态，而不是完全中止

同时，也可能一直选择一个事务回滚（发生 “饥饿” 状态），因此需要记录被选为受害者的次数，并在评估回滚代价时候将这个数据考虑在内。

Insert and Delete Operations

这里除了 read 和 write 操作，再加入 insert 和 delete 操作：

• delete 操作：必须先获得要删除的数据的 X 锁，保证其他事务无法读写这条待删除元组，避免删除过程中出现数据不一致
• insert 操作：在插入新的元组之后直接给它分配一个 X 锁，保证后续对这条新数据的修改、提交操作的排他性

phantom phenomenon

当一个事务在执行过程中，多次执行相同的查询（谓词读取 (predicate read)），但由于其他并发事务插入或删除了符合查询条件的新记录，导致后一次查询的结果集与前一次查询的结果集不同，就好像出现了“幽灵”一样，这些新出现的或消失的记录就是“幽灵”。

解决办法有以下两种：

• 谓词锁：即新定义一个虚拟的数据项，表示满足所有这个谓词的数据集合，那么在查询的时候给这个虚拟的数据项添加一个锁即可保证扫描的内容不变，但是这样做会极大的降低并发度，因此实用性很低
• 索引锁：在关系对应的索引上添加锁，这样既能防止幻象问题，又不会锁住整个表，因此并发度远高于表级锁方案
  • 前提：
  • 每个关系（表）必须至少有一个索引
  • 事务对表的所有访问（增删改查），都必须通过其中一个索引来完成
  • 查询操作：必须对所有它访问过的索引桶 (index buckets) 加 S 锁（好像就是索引节点的意思）
  • 插入/删除：操作时必须更新索引，并且需要获取所有受插入、删除或更新操作影响的索引叶子节点的 X 锁

Concurrency in Index Structures

To be done.

Lecture 14 - Recovery System

Failure Classification

失败的情况有很多种，一般可以分成一下三类：

• 事务失败：包括逻辑错误（例如溢出，输入有误等），系统错误（例如出现死锁等）
• 系统崩溃：例如停电，硬件或软件崩溃（注意，non-volatile storage 认为不被系统崩溃影响）
• 磁盘错误：例如读写头损坏，或其他损坏部分或全部硬盘的情况

Recovery Algorithms

假设一个事务 T_i 需要从账户 A 转账 50 元到账户 B，那么需要做两个更新：A 减去 50，B 加上 50。

但中途可能遇到故障：

• 如果 A 减去 50，B 还没加上 50 的时候系统崩溃，则违反了一致性（A,B 总和发生变化）
• 如果事务成功提交，但还没刷入数据库时系统崩溃，则修改会全部丢失，违反了持久性

因此恢复算法需要做的有两个部分：

• 事务正常执行时，记录足够的信息，用以之后可能的恢复操作
• 系统崩溃重启之后，利用之前记录的信息进行恢复，包括回滚 (undo) 和重做 (redo)，维护原子性，一致性和持久性

Storage Structure

之前介绍到两类存储介质：

• volatile storage：断电等系统崩溃时无法保存数据，例如内存，cache 等
• non-volatile storage：断电时能保存数据，例如硬盘，闪存，磁带等，但依然可能损坏，丢失数据

因此这里提出第三种

• stable storage：一种理想化的存储介质，认为永远不会损坏，丢失数据（可以用之前提到的 RAID，远程备份等技术近似实现）

Data Access

事务访问磁盘时有三个部分：

• 磁盘部分
• 内存中的 buffer block 部分
• 内存中每个事务独占的工作区

其中磁盘与 buffer 之间的传输称为 input/output，buffer 和工作区之间的传输称为 read/write，三者之间的关系如图所示：

这里会有两种可能的情况：

• buffer 满了，不得不提前将一部分数据刷入硬盘
• 事务的结构 commit 至 buffer，但还未刷入硬盘

这两个情况期间如果发生断电，则会违反一致性，硬盘中的数据有问题。

Recovery and Atomicity

（好像没什么内容）

Log-Based Recovery

日志 (log) 假定存储于稳定介质 (stable storage) 上，不然如果日志都可能丢失的话所有分析都无法进行。

记录日志的方式：

• 一个事务 T_i 开始的时候，添加一条 <Ti,start> 的记录
• 在事务 T_i 进行 write(x) 之前，添加一条 <Ti,x,old,new> 的记录，来存储新值和老值
• 在事务 T_i 完成的时候，添加一条 <Ti,commit> 的记录

这里会有两种不同的修改方法：

• 延迟修改：在事务执行，日志记录中延后对数据库的修改
• 立即修改：在事务执行，日志记录的同时立即对数据库进行修改（目前这种方式更常见）

Deferred Database Modification

正常记录日志，但在 commit 之后才进行所有的写操作。

• 这里写操作不需要存老值（因为数据恢复时不需要进行 undo），一条写操作记入日志时的写法为 <Ti,x,new>
• 在故障发生时，修改的内容写入 buffer 但还未写磁盘，此时断电并丢失 buffer 中要刷入磁盘的内容，因此在恢复之后需要 redo 整个事务并刷入磁盘

上面的三个例子中，假设写完了这些日志内容之后发生了崩溃，则：

• (a) 无需进行 redo，因为没有事务进行了 commit
• (b) 需要 redo 事务 T_0，因为它已经 commit 了
• (c) 需要 redo 事务 T_0,T_1，因为它们已经 commit 了

Immediate Database Modification

与延迟修改的模式不同，立即修改的模式会在事务执行过程中不断地向 buffer 中写入数据，而 buffer 的总量是有限的，因此需要或主动或被动地先将 buffer 中的信息刷入磁盘，而这就可能导致内存和磁盘中的数据不一致，从而加大恢复数据的难度。

• redo：需要的数据消失了，在发生崩溃时，如果一个事务有 start 且有 commit，则需要进行 redo
• undo：不需要的数据混入了，在发生崩溃时，如果一个事务有 start 但无 commit，则需要进行 undo

这两条大概就是事务的原子性，要么都做完要么都没做，不能做一半。

即：提交过的不能丢，没提交的不能留

Checkpoint

不难发现在之前的模型中只要一个事务有 start 则一定会被 redo/undo，这个操作的效率是很低的，因此引入了检查点 (checkpoint) 的技术。

因此在建立一个检查点时，需要进行的操作有：

• 将所有目前位于内存中的日志内容写到稳定存储介质中
• 将修改过的内存 block 写入磁盘
• 添加一条日志 <checkpoint L>，其中 L 为所有目前处于活跃状态（已经开始了但还未 commit/abort）的事务列表
• 建立检查点期间不能进行任何更新操作

那么不难看到，在进行恢复的时候，找到最近的一个 <checkpoint L>，那么之后 L 中的事务以及在这个 checkpoint 之后开始的事务需要进行 redo 或 undo。

如上图，在 T_c 处的活跃事务列表为 T_2，因此需要检查的为 T_2 以及 T_c 之后开始的事务（T_3,T_4）：

Shadow Paging

类似于之前影子数据库的想法，将目前状态复制一份形成一个新的副本，然后在新的副本中修改，在确认修改完成并刷入磁盘之后就将指针指向这个新的副本，并删除原来的版本。那么在恢复的时候直接将指针切换回原来的版本即可。

这种技术比较适合串行执行的场景，在高并发的情况下效率不高。

Recovery With Concurrent Transactions

假设我们使用的协议是严格两阶段锁（Strict 2PL），并且使用日志技术进行恢复。

问恢复结果的简单做法：

• 先识别出哪些事务需要 redo，哪些需要 undo
• 直接将所有需要 undo 的操作忽略，剩下的依次做，即可得到正确的结果（相当于手动保证了原子性）

Buffer Management

缓冲区管理的最重要的两条原则：

• 日志先于数据被写入磁盘（write-ahead log, WAL）
• 在对 T_i 进行 commit 时所有和 T_i 有关的日志已经都写入稳定存储介质中了