关系型数据库相关笔记

本笔记主要参考了数据库基础和原理系列，如有其他引用会在适当位置注明。

概览

核心组件

• 进程管理器（Process Manager）：管理进程 / 线程池。为了实现纳秒级操作，一些现代数据库使用自己的线程而不是操作系统线程。
• 网络管理器（Network Manager）：管理网路 I/O（尤其是对于分布式数据库）。
• 文件系统管理器（File System Manager）：管理磁盘 I/O，它是数据库的首要瓶颈。
• 内存管理器（Memory Manager）：用于处理大容量内存。为了避免磁盘 I/O 带来的性能损失，需要大量的内存。
• 安全管理器（Security Manager）：用于对用户的验证和授权。
• 客户端管理器（Client Manager）：用于管理客户端连接。

工具

• 备份管理器（Backup Manager）：用于保存和恢复数据。
• 恢复管理器（Recovery Manager）：用于崩溃后重启数据库到一个一致状态。
• 监控管理器（Monitor Manager）：用于记录数据库活动信息和提供监控数据库的工具。
• 管理员管理器（Administration Manager）：用于保存元数据（比如表的名称和结构），提供管理数据库、模式、表空间的工具。

查询管理器

• 查询解析器（Query parser）：用于检查查询是否合法。
• 查询重写器（Query rewriter）：用于预优化查询。
• 查询优化器（Query optimizer）：用于优化查询。
• 查询执行器（Query executor）：用于编译和执行查询

数据管理器

• 事务管理器（Transaction manager）：用于处理事务。
• 缓存管理器（Cache manager）：数据被使用之前置于内存，或者数据写入磁盘之前置于内存。
• 数据访问管理器（Data access manager）：访问磁盘中的数据。

数据查询流程

客户端管理器

客户端管理器是处理客户端通信的。客户端可以是一个（网站）服务器或者一个最终用户或最终应用。当连接到数据库时：

• 管理器首先检查验证信息（用户名和密码），然后检查否有访问数据库的授权。这些权限由 DBA 分配。
• 然后，管理器检查是否有空闲进程（或线程）来处理查询，还会检查数据库是否负载很重。
• 管理器可能会等待一会儿来获取需要的资源。如果等待时间达到超时时间，它会关闭连接并给出一个可读的错误信息。
• 然后，管理器会把查询送给查询管理器来处理。
• 因为查询处理进程不是 “不全则无” 的，一旦它从查询管理器得到数据，它会把部分结果保存到一个缓冲区并且开始发送。
• 如果遇到问题，管理器关闭连接，发送可读的解释信息，然后释放资源。

查询管理器

查询解析器首先解析查询并判断是否合法，然后重写查询，去除了无用的操作并且加入预优化部分。随后，查询被优化以便提升性能，并被转换为可执行代码和数据访问计划。最后计划被编译、执行。

查询解析器

查询解析器检查语法错误、关键字顺序、分析查询中的表和字段，并检查用户权限。在解析过程中，SQL 查询被转换为内部表示（通常是一个树）。

查询重写器

重写器按照一系列已知的规则对查询执行检测。如果查询匹配一种模式的规则，查询就会按照这条规则来重写。例如：

• 视图合并：将视图转换为它的 SQL 代码；
• 子查询扁平化：子查询是很难优化的，因此重写器会尝试移除子查询；
• 去除不必要的运算符：例如 DISTINCT 用在了 UNIQUE 约束列上；
• 排除冗余的联接：如果相同的 JOIN 条件出现两次，比如隐藏在视图中的 JOIN 条件，或者由于传递性产生的无用 JOIN，都会被消除；
• 常数计算赋值：计算常数运算结果；
• 分区裁剪（Partition pruning）：如果使用分区表，找到需要使用的分区；
• 物化视图重写（Materialized view rewrite）：如果有物化视图匹配查询谓词的一个子集，重写器将检查视图是否最新并修改查询，令查询使用物化视图而不是原始表；
• 自定义规则
• OLAP 转换

查询优化器

所有的现代数据库都在用基于成本的优化（即 CBO）来优化查询。道理是针对每个运算设置一个成本，通过应用成本最低廉的一系列运算，来找到最佳的降低查询成本的方法。

成本优化是一个复杂的过程，下面会讨论涉及到它的一些因素。

统计信息

当要求数据库收集统计信息时，数据库会计算下列值：

• 表中行和页的数量
• 表中每个列中的：唯一值、数据长度（最小，最大，平均）、数据范围（最小，最大，平均）
• 表的索引信息

这些统计信息会帮助优化器估计查询所需的磁盘 I/O、CPU 和内存使用。当然，也可以让数据库做高级统计直方图，计算列值分布情况的统计信息，例如出现最频繁的值、分位数等。统计信息保存在数据库元数据内。

存取路径

获取数据通常有以下模式：

• 全扫描：数据库完整的读一个表或索引。就磁盘 I/O 而言，很明显全表扫描的成本比索引全扫描要高昂。
• 范围扫描：在字段有索引时就可以使用索引范围扫描。不需要读取整个索引。
• 唯一扫描：只从索引中取一个值的时候使用。
• 根据 ROW ID 存取：多数情况下，如果数据库使用索引，它就必须查找与索引相关的行，这样就会用到根据 ROW ID 存取的方式。如果需要大量的根据 ROW ID 存取，数据库也许会选择全扫描。

联接运算符

首先，需要定义内关系和外关系。这里的关系可以是一个表、一个索引或上一个运算的中间结果。这里假定外关系为左侧数据集（有 N 个元素），内关系为右侧数据集（有 M 个元素）。

• 嵌套循环联接（Nested Loop Join）：针对外关系的每一行，查看内关系里的所有行来寻找匹配的行。实际上就是两层 for 循环。理论上的时间复杂度是 $O(N \times M)$ 。如果内关系足够小，可以将它读入内存。内关系也可以用索引代替。如果内关系太大无法装入内存，也可以使用成簇读取的方式（内外关系皆可用），尽量减少对磁盘的访问。
• 哈希联接（Hash Join）：读取内关系的所有元素，建立内存哈希表，同时对外关系的所有元素计算哈希值，来查询是否匹配。如果哈希函数创建了足够小规模的哈希桶，理论上的时间复杂度是 $O(N+M)$ 。也可以将两边都构建哈希表存入磁盘，随后进行逐个哈希桶的比较。
• 合并联接（Merge Join）：唯一产生排序的联接算法。首先两边都根据联接关键字排序，随后将排序后的输入源合并。联接时，只需依照排序顺序比较即可，不需要 “回头去找”。如果两个关系都已排好序（例如关系是联接条件里的一个索引），则时间复杂度为 $O(N+M)$ ，如果都需要排序，则为 $O(N \times \log{N}+M \times \log{M})$。

相关算法

多数时候，优化器找到的不是最佳的执行计划，而是一个 “不错” 的方案。

对于小规模的查询，采取粗暴的方式是有可能的。但是为了让中等规模的查询也能采取粗暴的方式，可以利用动态规划。大多数的执行计划拥有相同的子树，因此可以避免重复计算这些子树的成本。针对大规模查询，也可以用动态规划方法，但是要附加额外的规则（或者称为启发式算法）来减少可能性。

但是，当优化器面对一个非常大的查询，或者为了尽快找到答案（然而查询速度就快不起来了），会应用另一种算法，叫贪婪算法。原理是按照一个规则（或启发）以渐进的方式制定查询计划。在这个规则下，贪婪算法逐步寻找最佳算法，例如先处理一条 JOIN，接着每一步按照同样规则加一条新的 JOIN。

查询计划缓存

由于创建查询计划是耗时的，大多数据库把计划保存在查询计划缓存，来避免重复计算。如果一个表的统计变化超过了设置的阈值，关于该表的查询计划就从缓存中清除。

查询执行器

在这个阶段，优化的执行计划被编译为可执行代码。然后，如果有足够资源（内存、CPU），查询执行器就会执行它。计划中的操作符可以顺序或并行执行，这取决于执行器。为了获得和写入数据，查询执行器与数据管理器交互。

数据管理器

在这一步，查询管理器执行了查询，需要从表和索引获取数据，于是向数据管理器提出请求。但是有以下问题：

• 关系型数据库使用事务模型，所以，当其他进程在同一时刻使用或修改数据时，就无法得到这部分数据。
• 数据提取是数据库中速度最慢的操作，所以数据管理器需要足够聪明地获得数据并保存在内存缓冲区内。

缓存管理器

数据库的主要瓶颈是磁盘 I/O。为了提高性能，现代数据库使用缓存管理器。

查询执行器不会直接从文件系统拿数据，而是向缓存管理器索取。缓存管理器有一个内存缓存区，叫做缓冲池，从内存读取数据以显著地提升数据库性能。提升的量度取决于操作：

• 顺序访问（例如全扫描）还是随机访问（例如按照 ROW ID 访问）
• 读还是写

预读

缓存管理器需要在查询执行器使用数据之前得到数据，否则查询管理器不得不等待数据从缓慢的磁盘中读出来。查询执行器知道它将需要什么数据，因为它了解整个查询流，而且通过统计也了解磁盘上的数据。大概的过程是：当查询执行器处理它的某批数据时，会告诉缓存管理器预先装载下一批数据，同时可以清除上一批数据。

缓存管理器在缓冲池里保存所有的这些数据。为了确定一条数据是否有用，缓存管理器给缓存的数据添加了额外的信息（闩锁）。

有时查询执行器不知道它需要什么数据，有的数据库也不提供这个功能。这时候需要使用推测或顺序预读法。为了监控预读的工作状况，现代数据库引入了一个度量叫缓冲 / 缓存命中率，用来显示请求的数据在缓存中找到而不是从磁盘读取的频率。

缓冲只是容量有限的内存空间，加载和清除缓存需要一些磁盘和网络 I/O 的成本。如果拥有经常执行的查询，不应该每次都加载结果然后清除。这时候需要依靠缓冲区置换策略。这个策略使用 LRU（Least Recently Used，最近最少使用）算法，背后的原理是：在缓存里保留的数据是最近使用的，所以更有可能再次使用。

这个方法有一定的局限性，尤其是对一个大表执行全表扫描的情况。因此，对非常大的表来说，数据库通常使用直接路径来读取，即直接加载区块，来避免填满缓冲区。对于中等大小的表，数据库可以使用直接读取或缓存读取。如果选择缓存读取，数据库把区块置于 LRU 的尾部，防止清空当前缓冲区。还可以使用更高级版本的 LRU-K，其中 K 代表算法考虑了最后 K 次使用的情况，并对使用次数加权重。

写缓冲区

写缓冲区用来保存数据、成批刷入磁盘，而不是逐条写入数据从而造成很多单次磁盘访问。注意，缓冲区保存的是页（最小的数据单位）而不是行（逻辑上 / 人类习惯的观察数据的方式）。缓冲池内的页如果被修改了但还没有写入磁盘，就是脏页。有很多算法来决定写入脏页的最佳时机，但这个问题与事务的概念高度关联。

事务管理器

关于事务特性（ACID）、事务的隔离性问题、事务隔离级别的相关内容，可以参看 MySQL 相关笔记。

确保隔离性、一致性和原子性的真正问题是对相同数据的写操作（增、更、删）。如果（至少）有一个事务在修改其他事务读取的数据，数据库需要找个办法对其它事务隐藏这种修改。而且，它还需要确保这个修改操作不会被另一个看不到这些数据修改的事务擦除。这就是并发控制的问题。为了解决这个问题，多数数据库使用锁和 / 或数据版本控制。

锁

实现纯粹的隔离最简单的方法是：事务开始时获取锁，结束时释放锁。但是等待锁会浪费大量的时间。更快的方法是两段锁协议，事务分为两个阶段：

• 成长阶段：事务可以获得锁，但不能释放锁。
• 收缩阶段：事务可以释放锁（对于已经处理完而且不会再次处理的数据），但不能获得新锁。

这个规则可以很好地工作，但有个例外：如果修改了一条数据、释放了关联的锁后，事务被取消（回滚），而另一个事务读到了修改后的值，但最后这个值却被回滚。为了避免这个问题，所有独占锁必须在事务结束时释放。

真实的数据库使用更复杂的系统，涉及到更多类型的锁（比如意向锁，intention lock）和更多的粒度（行级锁、页级锁、分区锁、表锁、表空间锁），但是思路是相同的。

数据版本控制

版本控制的基本步骤：

• 每个事务可以在相同时刻修改相同的数据
• 每个事务有自己的数据拷贝（或者叫版本）
• 如果两个事务修改相同的数据，只接受一个修改，另一个将被拒绝，相关的事务回滚（或重新运行）

在这里，性能比悲观锁要高，原因是读事务与写事务不会相互阻塞，也减少了锁管理器带来的额外开销。除了两个事务写相同数据的时候，数据版本控制各个方面都比锁表现得更好，但是也会带来更大的磁盘空间消耗。

数据版本控制和锁机制是两种不同的见解：乐观锁和悲观锁。两者各有利弊，完全取决于使用场景（读多还是写多）。

日志管理器

为了提升性能，数据库把数据保存在内存缓冲区内。但如果当事务提交时服务器崩溃，崩溃时还在内存里的数据会丢失，这破坏了事务的持久性。如果把所有数据都写在磁盘上，服务器崩溃时最终数据可能只有部分写入磁盘，这破坏了事务的原子性。事务作出的任何修改必须是或者撤销，或者完成。

有两个方法解决这个问题：

• 影子副本 / 页（Shadow copies/pages）：每个事务创建自己的数据库副本（或部分数据库的副本），并基于这个副本来工作。一旦出错，这个副本就被移除；一旦成功，数据库立即把副本替换到数据中。
• 事务日志（Transaction log）：事务日志是一个存储空间，在每次写盘之前，数据库在事务日志中写入一些信息，这样当事务崩溃或回滚，数据库知道如何移除或完成尚未完成的事务。

WAL（预写式日志）

影子副本 / 页在运行较多事务的大型数据库时制造了大量磁盘开销，所以现代数据库使用事务日志。事务日志必须保存在稳定的存储上。多数数据库使用预写日志协议（Write-Ahead Logging Protocol，WAL）来处理事务日志。WAL 协议有 3 个规则：

• 每个对数据库的修改都产生一条日志记录，在数据写入磁盘之前日志记录必须写入事务日志。
• 日志记录必须按顺序写入。
• 当一个事务提交时，在事务成功之前，提交顺序必须写入到事务日志。

这个工作由日志管理器完成。简单的理解就是，日志管理器处于缓存管理器（cache manager）和数据访问管理器（data access manager，负责把数据写入磁盘）之间，每个事物操作在写入磁盘之前先写入事务日志。

ARIES

ARIES 代表 “数据库恢复原型算法”（Algorithms for Recovery and Isolation Exploiting Semantics）。事务的每一个操作（增 / 删 / 改）产生一条日志，由如下内容组成：

• LSN：唯一的日志序列号（Log Sequence Number），按时间顺序分配。
• TransID：产生操作的事务 ID。
• PageID：被修改的数据在磁盘上的位置。磁盘数据的最小单位是页。
• PrevLSN：同一个事务产生的上一条日志记录的链接。
• UNDO：取消本次操作的方法。比如，如果操作是一次更新，UNDO 将或者保存元素更新前的值 / 状态（物理 UNDO），或者回到原来状态的反向操作（逻辑 UNDO)。
• REDO：重复本次操作的方法。同样有两种方法。
• 其他字段：UndoNxtLSN 和 Type。

磁盘上每个页（保存数据的页）都记录着最后一个修改该数据操作的 LSN。每条日志都有一个唯一的 LSN，链接在一起的日志属于同一个事务。

日志缓冲区

为了防止写日志成为主要的瓶颈，数据库使用了日志缓冲区。当查询执行器要求做一次修改：

• 缓存管理器将修改存入自己的缓冲区；
• 日志管理器将相关的日志存入自己的缓冲区；
• 此时查询执行器认为操作完成，可以请求下一次修改；
• 接着日志管理器把日志写入事务日志；
• 接着缓存管理器把修改写入磁盘。

当事务提交，意味着事务每一个操作的 5 个步骤都完成了。写入事务日志是一项很快的操作，但是数据写盘相对复杂。

STEAL 和 FORCE 策略

出于能方面的原因，上述第 5 步有可能在提交之后完成，因为一旦发生崩溃，还有可能用 REDO 日志恢复事务。这叫做 NO-FORCE 策略。数据库可以选择 FORCE 策略来降低恢复时的负载。

另一个问题是，要选择数据是一步步的写入（STEAL 策略），还是缓冲管理器需要等待提交命令来一次性全部写入（NO-STEAL 策略）。选择 STEAL 还是 NO-STEAL 取决于想要快速写入但是从 UNDO 日志恢复缓慢，还是快速恢复。

策略之间的影响如下：

• STEAL / NO-FORCE 需要 UNDO 和 REDO：性能高，但是日志和恢复过程更复杂 (比如 ARIES)。多数数据库选择这个策略。
• STEAL / FORCE：只需要 UNDO。
• NO-STEAL / NO-FORCE：只需要 REDO。
• NO-STEAL / FORCE 什么也不需要：但性能最差，而且需要巨大的内存。

恢复阶段

ARIES 从崩溃中恢复有三个阶段：

• 分析阶段：恢复进程读取全部事务日志，来重建崩溃过程中所发生事情的时间线，决定哪个事务要回滚（所有未提交的事务都要回滚）、崩溃时哪些数据需要写盘。
• Redo 阶段：从分析中选中的一条日志记录开始，使用 REDO 来将数据库恢复到崩溃之前的状态：
  • 在 REDO 阶段，REDO 日志按照时间顺序处理（使用 LSN）；
  • 对每一条日志，恢复进程需要读取包含数据的磁盘页 LSN；
  • 如果 LSN（磁盘页）>= LSN（日志记录），说明数据已经在崩溃前写到磁盘（但是值已经被日志之后、崩溃之前的某个操作覆盖），所以不需要做什么；
  • 如果 LSN（磁盘页）< LSN（日志记录），那么磁盘上的页将被更新；
  • 即使将被回滚的事务，REDO 也需要做，因为这样简化了恢复过程。
• Undo 阶段：这一阶段回滚所有崩溃时未完成的事务。回滚从每个事务的最后一条日志开始，并且按照时间倒序处理 UNDO 日志（使用日志记录的 PrevLSN）。

恢复过程中，事务日志必须留意恢复过程的操作，以便写入磁盘的数据与事务日志相一致。一个解决办法是移除被取消的事务产生的日志记录，但是这个太困难了。相反，ARIES 在事务日志中记录补偿日志，来逻辑上删除被取消的事务的日志记录。

当事务被手动取消，或者被锁管理器取消（为了消除死锁），或仅仅因为网络故障而取消，那么分析阶段就不需要了。对于 REDO 和 UNDO 的信息在 2 个内存表中：

• 事务表（保存当前所有事务的状态）
• 脏页表（保存哪些数据需要写入磁盘）

当新的事务产生时，这两个表由缓存管理器和事务管理器更新。因为是在内存中，当数据库崩溃时它们也被破坏掉了。分析阶段的任务就是在崩溃之后，用事务日志中的信息重建上述的两个表。为了加快分析阶段，ARIES 提出了一个概念：检查点（check point），就是不时地把事务表和脏页表的内容，还有此时最后一条 LSN 写入磁盘。那么在分析阶段当中，只需要分析这个 LSN 之后的日志即可。

设计理论

名词解释

• 属性（attribute）：列的名字
• 依赖（relation）：列属性间存在的某种联系
• 元组（tuple）：每一个行
• 表（table）：由多个属性，以及众多元组所表示的各个实例组成
• 模式（schema）：逻辑结构（属性的集合）
• 域（domain）：数据类型
• 键（key）：由关系的一个或多个属性组成，任意两个键相同的元组，所有属性都相同。需要保证表示键的属性最少。一个关系可以存在好几种键，一般从这些候选键中选出一个作为主键（primary key）
• 候选键（candidate key）：由关系的一个或多个属性组成，候选键都具备键的特征，都有资格成为主键
• 超键（super key）：包含键的属性集合，无需保证属性集的最小化。每个键也是超键。可以认为是键的超集
• 外键（foreign key）：如果某一个关系 A 中的一个（组）属性是另一个关系 B 的键，则该（组）属性在 A 中称为外键
• 主属性（prime attribute）：所有候选键所包含的属性都是主属性
• 投影（projection）：选取特定的列
• 选择（selection）：按照一定条件选取特定元组
• 笛卡儿积（交叉连接，Cross join）：第一个关系每一行分别与第二个关系的每一行组合
• 自然连接（natural join）：第一个关系中每一行与第二个关系的每一行进行匹配，如果得到有交叉部分则合并，若无交叉部分则舍弃
• 连接（theta join）：即加上约束条件的笛卡儿积，先得到笛卡儿积，然后根据约束条件删除不满足的元组
• 外连接（outer join）：执行自然连接后，将舍弃的部分也加入，并且匹配失败处的属性用 NULL 代替
• 除法运算（division）：关系 R 除以关系 S 的结果为 T，则 T 包含所有在 R 但不在 S 中的属性，且 T 的元组与 S 的元组的所有组合在 R 中

数据库三范式

可以参看 MySQL 相关笔记。

规范设计

按照规范设计的方法，考虑数据库及其应用系统开发全过程，将数据库设计分为以下 6 个阶段：

• 需求分析：分析用户的需求，包括数据、功能和性能需求；
• 概念结构设计：主要采用 E-R 模型进行设计，包括 E-R 图；
• 逻辑结构设计：通过将 E-R 图转换成表，实现从 E-R 模型到关系模型的转换；
• 数据库物理设计：主要是为所设计的数据库选择合适的存储结构和存取路径；
• 数据库的实施：包括编程、测试和试运行；
• 数据库运行与维护：系统的运行与数据库的日常维护。

需求分析

分析方法常用 SA（Structured Analysis）结构化分析方法，SA 方法从最上层的系统组织结构入手，采用自顶向下，逐层分解的方式分析系统。在 SA 方法中，处理过程的处理逻辑常常借助判定表或判定树来描述。在处理功能逐步分解的同时，系统中的数据也逐级分解，形成若干层次的数据流图。

概念结构设计

整个数据库设计的关键，它通过对用户需求进行综合，归纳与抽象，形成了一个独立于具体 DBMS 的概念模型。通常有四类方法：

• 自顶向下。即首先定义全局概念结构的框架，再逐步细化。
• 自底向上。即首先定义各局部应用的概念结构，然后再将他们集成起来，得到全局概念结构。
• 逐步扩张。首先定义最重要的核心概念结构，然后向外扩张，以滚雪球的方式逐步生成其他的概念结构，直至总体概念结构。
• 混合策略。即自顶向下和自底向上相结合。

逻辑结构设计

将概念结构转换为某个 DBMS 所支持的数据模型，并将进行优化。在此阶段需要设计 E-R 图。各分 E-R 图之间的冲突主要有三类：属性冲突，命名冲突，结构冲突。E-R 图向关系模型的转换，要解决的问题是如何将实体性和实体间的联系转换为关系模式，如何确定这些关系模式的属性和码。

物理设计

为逻辑数据结构模型选取一个最适合应用环境的物理结构（包括存储结构和存取方法）。首先要对运行的事务详细分析，获得选择物理数据库设计所需要的参数，其次，要充分了解所用的 RDBMS 的内部特征，特别是系统提供的存取方法和存储结构。

常用的存取方法有：索引方法（目前主要是 B + 树索引），聚簇（Clustering）方法，HASH 方法。

E-R 图

E-R 即 Entity-Relationship，有三个组成部分：实体、属性、联系，用来进行关系型数据库系统的概念设计。

概略的步骤如下：

• 定义宏观行为：数据库的使用场景
• 确定 entities 及 relationships：存放信息的主题领域（表）及其关系
• 细化宏观行为：基于宏观行为，细化一系列微观行为
• 确定业务规则：常用于确定一对多，一对一，及多对多关系，以及相应的约束
• 确定所需数据：确定并列出合适的支持数据
• 标准化数据：消除数据冗余，按照三范式确保数据与正确的 table 或 relationship 相关联
• 考量关系：考量带有数据的关系，需要将关系转为 table；考量没有数据的关系，需要定义外键
• 检验设计：检查最开始定义的行为，确定可以获取行为所需要的所有数据
• 设计数据库表