数据库运行全流程

[toc]

全局概览

数据库是一个易于访问和修改的信息集合。不过简单的一堆文件也能达到这个效果。事实上，像SQLite这样最简单的数据库也只是一堆文件而已，但SQLite是精心设计的一堆文件，因为它允许你：

• 使用事务来确保数据的安全和一致性
• 快速处理百万条以上的数据

数据库一般可以用如下图形来理解：

总而言之，数据库是由多种互相交互的组件组成的。

核心组件：

• 进程管理器（**process manager**）**：很多数据库具备一个需要妥善管理的进程/线程池**。再者，为了实现纳秒级操作，一些现代数据库使用自己的线程而不是操作系统线程。
• **网络管理器（**network manager**）**：网路I/O是个大问题，尤其是对于分布式数据库。所以一些数据库具备自己的网络管理器。
• 文件系统管理器（**File system manager**）**：磁盘I/O是数据库的首要瓶颈**。具备一个文件系统管理器来完美地处理OS文件系统甚至取代OS文件系统，是非常重要的。
• **内存管理器（**memory manager**）**：为了避免磁盘I/O带来的性能损失，需要大量的内存。但是如果你要处理大容量内存你需要高效的内存管理器，尤其是你有很多查询同时使用内存的时候。
• **安全管理器（**Security Manager**）**：用于对用户的验证和授权。
• **客户端管理器（**Client manager**）**：用于管理客户端连接。
• ……

工具：

• **备份管理器（**Backup manager**）**：用于保存和恢复数据。
• 复原管理器（**Recovery manager**）**：用于崩溃后重启数据库到一个一致状态**。
• **监控管理器（**Monitor manager**）**：用于记录数据库活动信息和提供监控数据库的工具。
• ***Administration*管理器（***Administration** manager*）**：用于保存元数据（比如表的名称和结构），提供管理数据库、模式、表空间的工具。【译者注：好吧，我真的不知道Administration manager该翻译成什么，有知道的麻烦告知，不胜感激……】
• ……

查询管理器：

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

数据管理器：

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

在本文剩余部分，我会集中探讨数据库如何通过如下进程管理SQL查询的：

• 客户端管理器
• 查询管理器
• 数据管理器（含复原管理器）

客户端

客户端来处理客户端通信。客户端可以是一个网站或者一个应用。客户端管理器通过API提供不同方式来访问数据库。

当我们连接到数据库时：

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

查询管理器

这部分是数据库的核心部分。这部分主要处理我们写的SQL，将其转换为快速执行的代码，代码执行的结果被送到客户端管理器。步骤分为：

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

查询解释器

每一条SQL语句都要送到解析器来检查语法，如果我们的查询有错，解析器将拒绝该查询。

而且，解析器还会检查关键字是否使用正确的顺序，比如WHERE写在SELECT之前会被拒绝。

然后，解析器要分析查询中的表和字段，使用数据库元数据来检查：

• 表是否存在
• 表的字段是否存在
• 对某类型字段的运算是否可能（比如，我们不能将整数和字符串进行比较，也不能对一个整数使用substring 函数）

接着，解析器检查在查询中我们是否有权限来读取或写入表。

在解析过程中，SQL查询被转换为内部表示（通常为一个树）。如果一切正常，内部表示被送到查询重写器。

查询重写器

在这一步，我们已经又了查询的内部表示，重写器的目标是：

• 预优化查询
• 避免不必要的运算
• 帮助优化器找到合理的最佳解决方案

重写器按照一系列已知的规则对查询执行检测。如果查询匹配一种模式的规则，查询就会按照这条规则来重写。下面是（可选）规则的非详尽的列表：

• 视图合并：如果我们在查询中使用视图，视图就会转换为它的SQL代码
• 子查询扁平化：子查询是很难优化的，因此重写器会尝试移除子查询

比如：

SELECT PERSON.*

FROM PERSON

WHERE PERSON.person_key IN

(SELECT MAILS.person_key

FROM MAILS

WHERE MAILS.mail LIKE 'christophe%'

会被转换为：

SELECT PERSON.*

FROM PERSON, MAILS

WHERE PERSON.person_key = MAILS.person_key

and MAILS.mail LIKE 'christophe%'

• 去除不必要的运算符：比如，如果我们用了DISTINCT，而其实我们有UNIQUE约束，那么DISTINCT关键字就被去掉了
• 排除冗余的联接：如果相同的JOIN条件出现两次，比如隐藏在视图中的JOIN条件，或者由于传递性产生的无用JOIN，都会被消除
• 常数计算赋值：如果我们的查询需要计算，那么在重写过程中计算会执行一次。比如 WHERE AGE > 10 + 2 会转换为 WHERE AGE > 12， TODATE(“日期字符串”) 会被转换为 datetime 格式的日期

重写后的查询接着送到优化器。

统计

研究数据库如何优化查询之前我们需要谈谈统计，因为没有统计的数据库是很笨的。除非我们明确指示，数据库是不会分析自己的数据的。没有分析会导致数据库做出糟糕的假设。

但是，数据库需要什么类型的信息呢？

我们必须谈谈数据库和操作系统如何保存数据。两者使用的最小单位叫做页。这就是说我们如果仅需要 1KB，也会占用一个页，即使 1KB 只占了一个页的四分之一，浪费了其中的四分之三。

回来继续说统计！当我们要求数据库收集统计信息，数据库会计算下列值：

• 表中行和页的数量
• 表中每个列中的：
  • 唯一值
  • 数据长度
  • 数据范围
• 表的索引信息

这些统计信息会帮助优化器估计查询所需的磁盘IO、CPU和内存使用。

对每个列的统计非常重要。比如，

如果一个表的 PERSON 需要联接 2 个列：LAST_NAME，FIRST_NAME。根据统计信息，数据库知道 FIRST_NAME 只有 1000 个不同的值， LASTNAME 有 1000000 个不同的值。因此，数据库就会按照 LAST_NAME，FIRST_NAME 联接。

因为 LAST_NAME 不大可能重复，多数情况下比较 LAST_NAME 的头 2、3 个字符就够了，这将大大减少比较大次数。

不过，这些只是基本的统计。我们可以让数据库做一种高级统计，叫直方图。直方图是列值分布情况的统计信息。比如：

• 出现最频繁的值
• 分位数

这些额外的统计会帮助数据库找到更佳的查询计划，尤其是对于等式谓词（比如 WHERE AGE = 18）或范围谓词（比如 WHERE AGE > 10 and AGE < 40），因为数据库可以更好的了解这些谓词相关的数字类型数据行。

统计信息保存在数据库元数据内，例如（非分区）表的统计信息位置：

• Oracle：USER/ALL/DBA_TABLES 和 USER/ALL/DBA_TAB_COLUMNS
• DB2：SYSCAT.TABLES 和 SYSCAT.COLUMNS

统计信息必须及时更新。如果一个表有 1000000 行而数据库认为它只有 500 行，没有比这更糟糕的了。统计唯一的不利之处是需要时间来计算，这就是为什么数据库大多默认情况下不会自动计算统计信息。数据达到百万级别时统计会变得困难，这时候，我们可以选择做基本统计或者在一个数据库样本上执行统计。

举个例子，假如有个需求需要处理每表上亿条数据的库，我选择只统计10%，结果造成了巨大的时间消耗。这很明显是个糟糕的决定，因为有时候 Oracle 10G 从特定表的特定列中选出的 10% 跟全部 100% 有很大不同（但对于拥有一亿行数据的表，这种情况极少发生）。这次错误的统计导致了一个本应30秒完成的查询最后执行了 8 小时。这个例子显示了统计的重要性。

查询优化器

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

为了理解成本优化器的原理，我觉得最好用个例子来感受一下这个任务背后的复杂性。这里给出联接2个表的3个方法，我们很快就能看到即便一个简单的联接查询对于优化器来说都是个恶梦。之后，我们会了解真正的优化器是怎么做的。

对于这些联接操作，我们要专注于它们的时间复杂度，但是，数据库优化器计算的是他们的CPU成本、IO和内存需求。时间复杂度和CPU成本的区别是，时间成本是个近似值。而CPU成本，包括来所有的运算，比如：加法、条件判断、迭代、乘法以及：

• 每一个高级代码运算都要特定数量的低级CPU运算
• 对于Intel Core i7 以及不同的 CPU….等，CPU等运算成本是不同的，也就是它取决于CPU的架构

使用时间复杂度就容易多了。由于IO是个重要概念，而且大多数时候瓶颈在于磁盘IO而不是CPU使用。

索引

在研究B+树的时候我们谈到了索引，要记住一点，索引都是已经排了序的。

另外，很多现代数据库为了改善执行计划的成本，可以仅为当前查询动态地生成临时索引。

存取路径

在应用联接运算符之间，我们需要获得数据。以下就是数据的获取方法。

全扫描

如果你读过执行计划，一定看到过「全扫描」。简单的说全扫描就是数据库完整的读一个表或索引。就磁盘IO而言，很明显全表扫描的成本比索引全扫描要高昂。

范围扫描

其他类型的扫描有索引范围扫描，比如当我们使用谓词 “WHERE AGE > 20 AND AGE < 40” 的时候它就会发生。

当然，我们需要在 AGE 字段上有索引才能用到索引范围扫描。

范围查询的时间复杂度是 O(logN + M)，这里的N是索引的数据量，M是范围内估测的行数。多亏有了统计我们才能知道N和M的值。另外范围扫描时，我们不需要读取整个索引，因此在磁盘IO方面没有全扫描那么昂贵。

唯一扫描

如果我们只需要从索引中取一个值可以用唯一扫描。

根据 ROW ID 存取

多数情况下，如果数据库使用索引，它就必须查找与索引相关的行，这样就会用到根据 ROW ID 存取的方式。

例如运行：

SELECT LASTHAME, FIRSTNAME from PERSON WHERE AGE = 28

如果person表的age列有索引，优化器会使用索引找到所有年龄为28的人，然后它会去表中读取相关的行，这是因为索引中只有age的信息而我们要的是姓名。

但是，假如我们换个做法：

SELECT TYPE_PERSON.CATEGORY from PERSON, TYPE_PERSON

WHERE PERSON.AGE = TYPE_PERSON.AGE

PERSON 表的索引会用来联接 TYPE_PERSON 表，但是 PERSON 表不会根据行 ID 存取，因为我们并没有要求这个表内的信息。

虽然这个方法在少量存取时表现很好，这个运算的真正问题其实是磁盘IO。假如需要大量的根据行ID存取，数据库也许会选择全扫描。

联接运算符

那么，我们知道如何获取数据了，那现在就把它们联接起来。

我要展现的是3个常用联接运算符：合并联接（Merge Join），哈希联接（Hash Join）和嵌套循环联接（Nested Loop Join）。

但是在此之前，我需要引入新词汇来：内关系和外关系【“内关系和外关系” 这个说法来源不明，跟查询的“*内联接（INNER JOIN）* 、*外联接（OUTER JOIN）* ” 不是一个概念 。只查到百度百科词条：*关系数据库* 里提到“每个表格（有时被称为一个关系）……” 。 其他参考链接 “*Merge Join”* “*Hash Join”* “*Nested Loop Join”* 】 。 一个关系可以是：

• 一个表
• 一个索引
• 上一个运算的中间结果

当我们联接两个关系时，联接算法对两个关系的处理是不同的。在本文中，假定：

• 外关系是左侧数据集
• 内关系是右侧数据集

比如，A JOIN B 是 A 和 B 的联接，这里 A 是外关系，B是内关系。

多数情况下，A JOIN B 的成本跟 B JOIN A 的成本是不同的。

在这一部分，还假定外关系有 N 个元素，内关系有 M 个元素。要记住，真正的优化器通过统计知道 N 和 M 的值。

嵌套循环联接

嵌套循环联接是最简单的。

道理如下：

• 针对外关系的每一行
• 查看内关系里的所有行来寻找匹配的行

下面是伪代码：

nested_loop_join(array outer, array inner)

  for each row a in outer

    for each row b in inner

      if (match_join_condition(a,b))

        write_result_in_output(a,b)

      end if

    end for

   end for

由于这是个双迭代，时间复杂度是O(N*M)。

在磁盘 IO 方面，针对 N 行外关系的每一行，内部循环需要从内关系读取 M 行。这个算法需要从磁盘读取 N + N*M 行。但是，如果内关系足够小，我们可以吧它读入内存，那么就只剩下 M + N 次读取。这样修改之后，内关系必须是最小的，因为它有更大机会装入内存。

在 CPu 成本方面没有什么区别，但是在磁盘 IO 方面，最好最好的是，每个关系值读取一次。

当然，内关系可以由索引代替，对磁盘 IO 更有利。

由于这个算法非常简单，下面这个版本在内关系太大无法装入内存时，对磁盘IO更加有利。道理如下：

• 为了避免逐行读取两个关系
• 你可以成簇读取，把（两个关系里读到的）两簇数据行保存到内存中
• 比较两簇数据，保留匹配的
• 然后从磁盘加载新的数据簇来继续比较
• 直到加载了所有数据

可能的算法如下：

// improved version to reduce the disk I/O.

nested_loop_join_v2(file outer, file inner)

  for each bunch ba in outer

  // ba is now in memory

    for each bunch bb in inner

        // bb is now in memory

        for each row a in ba

          for each row b in bb

            if (match_join_condition(a,b))

              write_result_in_output(a,b)

            end if

          end for

       end for

    end for

   end for

使用这个版本，时间复杂度没有变化，但是磁盘访问降低了：

• 用前一个版本，算法需要 N + N*M
• 用新版本，磁盘访问变为 外关系的数据簇数量 + 外关系的数据簇数量*内关系的数据簇数量
• 增加数据簇的尺寸，可以降低磁盘访问

哈希联接

哈希联接更复杂，不过在很多场合比嵌套循环联接成本低。

哈希联接的原理是：

1. 读取内关系的所有元素
2. 在内存里建一个哈希表
3. 逐条读取外关系的所有元素
4. 计算每个元素的哈希值，来查找内关系里相关的哈希痛内
5. 是否与外关系的元素匹配

在时间复杂度方面需要做些假设来简化问题：

• 内关系被划分成了X个哈希桶
• 哈希函数几乎均匀地分布每个关系内数据的哈希值，就是说哈希桶大小一致
• 外关系的元素与哈希桶内的所有元素的匹配，成本是哈希桶内元素的数量

时间复杂度是 (M/X) * (N/X) + 创建哈希表的成本(M) + 哈希函数的成本 * N。如果哈希函数创建了足够小规模的哈希桶，那么复杂度就是O(M+N).

还有个哈希联接的版本，对内存有利但是对磁盘IO不利：

1. 计算内关系和外关系双方的哈希表
2. 保存哈希表到磁盘
3. 然后逐个哈希桶比较（其中一个读入内存，另一个逐行读取）

合并联接

合并联接是唯一产生排序到联接算法。

注：这个简化到合并联接不区分内表和外表：两个表扮演同样的角色。但是真实的实现方式是不同的，比如当处理重复值时。

1. （可选）排序联接运算：两个输入源都按照联接关键字排序
2. 合并联接运算：排序后的输入源合并到一起

排序

我们知道合并排序（一种排序算法），在这里合并联接（用的就是合并排序）是个很好的算法（但是并非最好的，如果内存够用的话，还是哈希联接更好）。

然而有时数据集已经排序了，比如：

• 如果表内部就是有序的，比如联接条件里一个索引组织表
• 如果关系是联接条件里的一个索引
• 如果联接应用在一个查询中已经排序的中间结果

合并联接

这部分与我们研究过的合并排序中的合并运算非常相似。不过这一次呢，我们不是从两个关系里挑选所有元素，而是只挑选相同的元素。道理如下：

1. 在两个关系中，比较当前元素（当前 = 头一次出现的第一个）
2. 如果相同，就把两个元素都放入结果，再比较两个关系里的下一个元素
3. 如果不同，就去带有最小元素的关系里找下一个元素
4. 重复1，2，3步骤直至其中一个关系的最后一个元素（合并排序，如果有一方遍历完了，排序结束，将另一方剩余的元素之间全部拼接到后面）

因为两个关系都是已经排序的，我们不需要「回头找」。

该算法是个简化版，因为它没有处理两个序列中相同数据出现多次的情况。

如果两个关系都已经排序，时间复杂度是O(N+M)

如果两个关系需要排序，时间复杂度是对两个关系排序的成本：O(NlogN + MlogM)

那么算法的完整版呢？如何处理多重匹配呢？请看下面的算法：

mergeJoin(relation a, relation b)

  relation output

  integer a_key:=0;

  integer  b_key:=0;
 

  while (a[a_key]!=null and b[b_key]!=null)

     if (a[a_key] < b[b_key])

      a_key++;

     else if (a[a_key] > b[b_key])

      b_key++;

     else //Join predicate satisfied

      write_result_in_output(a[a_key],b[b_key])

      //We need to be careful when we increase the pointers

      if (a[a_key+1] != b[b_key])

        b_key++;

      end if

      if (b[b_key+1] != a[a_key])

        a_key++;

      end if

      if (b[b_key+1] == a[a_key] && b[b_key] == a[a_key+1])

        b_key++;

        a_key++;

      end if

    end if

  end while

哪个算法最好？

如果有最好的，就没必要分这么多类型了。需要考虑多因素来区分使用哪种算法：

• 空闲内存：没有足够的内存的话就尽量别使用哈希联接
• 两个数据集的大小：比如，如果一个大表联接一个很小的表，那么嵌套循环联接就比哈希联接要快，因为后者有创建哈希的高昂成本；如果两个表都非常大，那么NLJ的CPU成本就很高
• 是否有索引：有两个B+树索引的话，聪明的选择似乎是合并联接
• 结果是否需要排序：即使用到的是未排序的数据集，我们也可能想用成本较高的合并联接（待排序），因为最终得到排序的结果后，我们可以把它和另一个合并联接串起来
• 关系是否已经排序：这时候合并联接是最好的选项
• 联接的类型：是等值联接（比如 tableA.col1 = tableB.col2 ）？ 还是内联接？外联接？笛卡尔乘积？或者自联接？有些联接在特定环境下是无法工作的。
• 数据的分布：如果联接条件的数据是倾斜的（比如根据姓氏来联接人，但是很多人同姓），用哈希联接是个灾难，因为哈希函数将产生分布极不均匀的哈希桶

简化的例子

我们已经研究了3种类型的联接操作。

现在，比如说我们要联接5个表，来获得一个人的全部信息。一个人可以有：

• 多个手机号
• 多个邮箱
• 多个地址
• 多个银行帐户

换句话说，我们需要用下面的查询快速得到答案：

SELECT * from PERSON, MOBILES, MAILS, ADRESSES, BANK_ACCOUNTS

WHERE

PERSON.PERSON_ID = MOBILES.PERSON_ID

AND PERSON.PERSON_ID = MAILS.PERSON_ID

AND PERSON.PERSON_ID = ADRESSES.PERSON_ID

AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID

作为一个查询优化器，我们必须找到处理数据最好的方法。但有 2 个问题：

• 每个联接使用哪种类型？我有三种可选（哈希、合并和嵌套），同时可能用到0，1或2个索引（不必说还有很多种类型的索引）
• 按什么顺序执行联接？比如，下图显示了针对4个表仅仅3次联接，可能采用的执行计划：

那么下面就是我可能采取的方法：

1. 采取粗暴的方式。用数据库统计，计算每种可能的执行计划的成本，保留最佳方案。但是，会有很多可能性。对于一个给定顺序的联接操作，每个联接有三种可能性：哈希、合并和嵌套，那么总共有3^4种可能性。确定联接的顺序是个二叉树的排列问题，会有（24）！/(4+1)! 种可能的顺序。对于本例，最后会得到 3^4(2*4)!/(4+1)!种可能。 抛开专业术语，那相当于27216种可能性。如果给合并联接加上使用0，1或2个B+树索引，可能性就变成了210000种。但是这个查询本来不是很简单吗？
2. 只尝试几种执行计划，挑一个成本最低的。

但是，数据库是如何处理的呢？

动态编程，贪婪算法和启发式算法。

关系型数据库会尝试我刚提到的多种方法，优化器真正的工作是在有限时间里找到一个好的解决方案。

多数时候，优化器找到的不是最佳的方案，而是一个不错的。

对于小规模的查询，采取暴力的方式是可以的，但是为了让中等规模的查询也能采取粗暴方法，我们有办法避免不必要的计算，这就是动态编程。

动态编程

这几个字背后的理念是，很多执行计划是非常相似的。看下图这几种计划：

它们都有相同的子树（A JOIN B），所以，不必在每个计划中计算这个子树的成本，计算一次，保存结果，当再遇到这个子树时重用。用更正规的说法，我们面对的是个重叠问题。为了避免对部分结果的重复计算，我们使用记忆法。

针对大规模查询，也可以使用动态编程方法，但是要附加额外的规则（或者成为启发式算法）来减少可能性。

• 如果我们仅分析一个特定类型的计划（例如左深树）我们得到的n*2^n 而不是3^n
• 如果我们加上逻辑规则来避免一些模式的计划（像 如果一个表有针对指定谓词的索引，就不要对表尝试合并联接，要对索引），就会在不给最佳方案造成过多伤害的前提下，减少可能性的数量
• 如果我们在流程里增加规则（像 联接运算先于其他所有的关系运算），也能减少大量的可能性
• ……

贪婪算法

但是，优化器面对一个非常大的查询，或者为了尽快找到答案（然而查询速度就快不起来了），会应用另一种算法，叫贪婪算法。

原理是按照一个规则（或启发）以渐进的方式制定查询计划。在这个规则下，贪婪算法逐步寻找最佳算法，先处理一条JOIN，接着每一步按照同样规则加一条新的JOIN。

来看个简单的例子。比如一个针对5张表（A,B,C,D,E）4次JOIN查询，为了简化我们把嵌套JOIN作为可能的联接方式，按照「使用最低成本的联接」规则。

• 直接从 5 个表里选一个开始（比如A）
• 计算每一个与 A 的联接（A作为内关系或外关系
• 发现 “A JOIN B”成本最低
• 计算每一个与 “A JOIN B”的结果联接的成本 （“A JOIN B”作为内关系或外关系）
• 发现“（A JOIN B） JOIN C”成本最低
• 计算每一个与“（A JOIN B） JOIN C”的结果联接的成本…
• 最后确定执行计划“( ( (A JOIN B) JOIN C) JOIN D ) JOIN E )”

因为我们是武断地从表 A 开始，我们可以把同样地算法用在 B，然后 C，然后 D，E。最后保留成本最低的执行计划。

顺便说一句，这个算法有一个名字，叫最近邻居算法。

抛开细节不谈，只需一个良好的模型和一个 NlogN 复杂度的排序，问题就轻松解决了。这个算法的复杂度是O（NlogN），对比一下完全动态编程的O(3^N)。如果你有个20联接的大型查询，这意味着26 vs 3486784401，天壤之别。

• 即使在A，B，C之间，A JOIN B 可得最低成本
• 但是（A JOIN C） JOIN B 也许比 (A JOIN B) JOIN C 更好

为了改善这一状况，我们可以使用基于不同规则的贪婪算法，并保留最佳的执行计划

查询计划缓存

由于创建查询计划是耗时的，大多数据库把计划保存在查询计划缓存，来避免重复计算。这个话题比较大，因为数据库需要知道什么时候更新过时的计划。办法是设置一个上限，如果一个表的统计变化超过了上限，关于该表的查询计划就从缓存中清除。

查询执行器

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

数据管理器

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

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

在这一部分，我没看看关系型数据库是如何处理这两个问题的。我不会讲数据库管理器是怎么获得数据的，因为这不是最重要的。

缓存管理器

我已经说过，数据库的主要瓶颈就是磁盘IO。为了提高性能，现代数据库使用缓存管理器。

查询执行器不会直接从文件系统拿数据，而是向缓存管理器要。缓存管理器有一个内存缓存去，叫缓冲池，从内存读取数据显著地提升数据库性能。对此很难给出一个数量级，因为这取决于我们需要的是哪种操作：

• 顺序访问（比如 全扫描） vs 随机访问（比如 按照row id 访问）
• 读还是写

以及数据库使用的磁盘类型：

• 7.2k/10k/15k rpm 的硬盘
• …

要我说，内存比磁盘快了100到10万倍。

然而，这导致了另一个问题，缓存管理器需要在查询执行器使用数据之前得到数据，否则查询管理器不得不等待数据从缓慢的磁盘中读出来。

预读

这个问题叫预读。查询执行器知道它将需要什么数据，因为它了解整个查询流，而且通过统计也了解磁盘上的数据。道理是这样的：

• 当查询执行器处理它的第一批数据时
• 会告诉缓存管理器预先状态第二批数据
• 当开始处理第二批数据时
• 告诉缓存管理器预先装载第三批数据，并且告诉缓存管理器第一批数据可以从缓存里清理掉了
• …

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

有时查询执行器不知道它需要什么数据，有的数据库也不提供这个功能。相反，它们使用一种推测与预读法（比如，入股查询执行器想要数据1、3、5，它不久后很可能会要7、9、11），或者顺序预读法（这时候缓存管理器只是读取一批数据后简单地从磁盘加载下一批连续数据）。

为了监控预读读工作状况，现代数据库引入了一个度量叫缓冲/缓存命中率，用来显示请求读数据在缓存中找到而不是从磁盘读取的频率。

注：糟糕的缓存命中率不总是意味着缓存工作状态不佳。

缓冲只是容量有限的内存空间，因此，为了加载新的数据，它需要移除一些数据。加载和清除缓存需要一些磁盘和网络IO的成本。如果我们有一个经常执行的查询，那么每次都把查询结果加载然后清楚，效率就太低了。现代数据库通过缓冲区置换策略解决这个问题。比如 LRU、LFU以及变种LRU-K、HashLRU、HashLFU以及ARC等等。具体的就不过多介绍了。

缓冲区置换策略

常见的缓冲区置换策略有 LRU、LFU以及变种LRU-K、HashLRU、HashLFU以及ARC等等。具体的就不过多介绍了。

写缓冲区

我只探讨了读缓存——在使用之前预先加载数据。用来保存数据、成批刷入磁盘，而不是逐条写入数据从而造成很多单词磁盘访问。

要记住，缓冲区保存的是页（最小的数据单位）而不是行/缓冲池中的页如果被修改了但还没有写入磁盘，就是脏页。有很多算法来决定写入脏页的最佳时机，但这个问题与事务的概念高度关联，下面我们就谈谈事务。

事务管理器

最后但同样重要的，是事务管理器，我们将看到这个进程是如何保证每个查询在自己的事务内执行的。但开始之前，我们需要理解ACID事务的概念。

“I‘m on acid”

一个ACID事务是一个工作单元，它要保证4个属性：

• 原子性：事务「要么全部完成，要么全部取消」，即使它持续运行10个小时。如果事务崩溃，状态回滚到事务之前。
• 隔离性：如果2个事务A和B同时运行，事务A和B最终的结果是相同的（不会因为结束的时期变化导致结果发生变化），不管A是结束于B之前/之后/运行期间
• 持久性：一旦事务提交（也就是成功执行），不管发生什么，数据要保存到数据库中
• 一致性：只有合法的数据（依照关系约束和函数约束）能写入数据库，一致性与原子性和隔离性有关

在同一个事务内，我们可以运行多个SQL查询来读取、创建、更新和删除数据。当两个事务使用相同的数据，麻烦就来了。经典的例子是从帐号A到账户B到汇款。假设有2个事务：

• 事务1（T1）从账户A取出100美元给账户B
• 事务2（T2）从账户A取出50美元给账户B

我们回来看看ACID属性：

• 原子性确保不管T1期间发生什么（服务器崩溃、网络中断…），你不能出现账户A取走了100美元但没有给账户B到现象（这就是数据不一致的情况）
• 隔离性确保如果T1和T2同时发生，最后A将减少150美元，B将得到150美元，而不是其他结果，比如因为T2部分抹除了T1的行为，A减少150美元而B只得到50美元（这也是不一致状态）
• 持久性确保如果T1刚刚提交，数据库就发生崩溃，T1不会消失得无影无踪
• 一致性确保钱不会在系统内生成或销毁

并发控制

确保隔离性、一致性和原子性的真正问题是对相同数据的写操作（增、更、删）：

• 如果所有事务只是读取数据，它们可以同时工作，不会更改另一个事务的行为
• 如果有一个事务在修改其他事务读取的数据，数据库需要找个办法对其他事务隐藏这种修改。而且，他还需要确保这个修改操作不会被另一个看不到这些数据修改的事务擦擦除

这个问题叫并发控制。

最简单的做法是依次执行每个事务，但这样就完全没有伸缩性了，在一个多处理器/多核服务器上只有一个核心在工作，效率很低。

理想的办法是，每次一个事务创建或取消时：

• 监控所有事务的所有操作
• 检查是否 2 个或者更多事务的部分操作因为读取/修改相同的数据而存在冲突
• 重新编排冲突事务中的操作来减少冲突的部分
• 按照一定的顺序执行冲突的部分（同时非冲突事务仍然在并发运行）
• 考虑事务有可能被取消

用更正规的说法，这是对冲突的调度问题。更具体点说，这是个非常困难而且CPU开销很大的优化问题。企业级数据库无法承担几个小时，来寻找每个新事务活动最好的调度，因此就使用不那么理想的方式以避免更多的时间浪费在解决冲突上。

锁管理器

为了解决这个问题，多数数据库使用锁/或数据版本控制。这是个很大的话题。

悲观锁

原理是：

• 如果一个事务需要一条数据
• 它就把数据锁住
• 如果另一个事务也需要这条数据
• 它就必须等待第一个事务释放这条数据。

但是对一个仅仅读取数据的事务使用悲观锁非常昂贵，因为这会迫使其他只需要读取相同数据的事务等待。因此就有了另一种锁，共享锁。

共享锁是这样的：

• 如果一个事务只需要读取数据A
• 它会给数据A加上共享锁并读取
• 如果第二个事务也需要仅仅读取数据A
• 它会给数据A加上共享锁并读取
• 如果第三个事务需要修改数据A
• 它会给数据A加上悲观锁，但是必须等待另外两个事务释放它们的共享锁。

同样，如果一块数据被加上悲观锁，一个只需要读取该数据的事务必须等待悲观锁释放才能给该数据加上共享锁。

锁管理器是添加和释放锁的进程，在内部用一个哈希表保存锁信息（关键字是被锁的数据），并且了解每一块数据是：

• 被哪个事务加的锁
• 哪个事务在等待数据解锁

死锁

但是使用锁会导致一种情况，2 个事务永远在等待一块数据：

• 事务A 给 数据1 加上排他锁并且等待获取数据2
• 事务B 给 数据2 加上排他锁并且等待获取数据1

在死锁发生时，锁管理器要选择回滚一个事务，以便消除死锁。这可是个艰难的决定：

• 杀死数据修改量最少的事务（这样能减少回滚的成本）？
• 杀死持续时间最短的事务，因为其他事务的用户等待的时间更长？
• 杀死能用更少时间结束的事务（避免可能的资源饥荒）？
• 一旦发生回滚，有多少事务会收到回滚的影响？

在作出选择之前，锁管理器需要检查是否有死锁存在。

哈希表可以看作是个图表，图中出现循环就说明有死锁。由于检查循环是昂贵的（所有锁组成的图表是很庞大的），经常会通过简单的途径解决：使用超时设定。如果一个锁在超时时间内没有加上，那么事务就进入死锁状态。

锁管理器也可以在加锁之前检查该锁会不会变成死锁，但是想要完美的做到这一点还是很昂贵的。因此这些预检经常设置一些基本规则。

两段锁

实现纯粹的隔离最简单的办法：事务开始时获取锁，结束时释放锁。就是说，事务开始前必须等待确保自己能加上所有的锁，当事务结束时释放自己持有的锁。这是行得通的，但是为了等待所有的锁，大量的时间被浪费了。

更快的方法是两段锁协议，在这里，事务分为两个阶段：

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

这两条简单规则背后的原理是：

• 释放不再使用的锁，来降低其他事务的等待时间
• 防止发生这类情况：事务最初获得的数据，在事务开始后被修改，当事务重新读取该数据时发生不一致

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

两段式锁同样会出现死锁，需要依靠数据库的死锁检测机制或超时机制来解除。

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

我只探讨纯粹基于锁的方法，数据版本控制是解决这个问题（隔离问题）的另一个方法。

版本控制是这样的：

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

这将提高性能，因为：

• 读事务不会阻塞写事务
• 写事务不会阻塞读事务
• 没有臃肿缓慢的锁管理器带来的额外消耗

除了两个事务写相同数据的时候，数据版本控制各个方面都比锁表现得更好。只不过，磁盘空间会消耗巨大。

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

日志管理器

我们已经知道，为了提升性能，数据库把数据保存在内存缓冲区内。但如果当事务提交时服务器崩溃，崩溃时还在内存里的数据会丢失，这破坏了事务的持久性。

你可以把所有数据都写在磁盘上，但是如果服务器崩溃，最终数据可能只有部分写入磁盘，这破坏了事务的原子性。

事务作出的任何修改必须是撤销，或者完成。

有 2 个办法解决这个问题：

• 影子副本/页：每个事务创建自己的数据库副本，并基于这个副本来工作。一旦出错，这个副本就被移除；一旦成功，数据库立即使用文件系统的一个把戏，把副本替换到数据中，然后删掉旧数据。
• 事务日志：事务日志是一个存储空间，在每次写盘之前，数据库在事务日志中写入一些信息，这样当事务崩溃或回滚，数据库知道如何移除或完成尚未完成的事务

WAL（预写式日志）

影子副本/页在运行较多事务的大型数据库时制造了大量磁盘开销，所以现代数据库使用事务日志。事务日志必须保存在稳定的存储上，以防磁盘故障。

多数数据库使用预写日志协议来处理事务日志。WAL协议有3个规则：

1. 每个对数据库的修改都产生一条日志记录，在数据写入磁盘之前日志记录必须写入事务日志
2. 日志记录必须按顺序写入；记录A发生在记录B之前，则A必须写在B之前
3. 当一个事务提交时，在事务成功之前，提交顺序必须写入事务日志

这个工作由日志管理器完成。简单的理解就是，日志管理器处于缓存管理器和数据访问管理器（负责把数据写入磁盘）之间，每个 update / delete/ create/ commit / rollback 操作在写入磁盘之前先写入事务日志。简单，对吧？

错误！问题在于，如何找到写日志的同时保持良好的性能的方法。如果事务日志写得太慢，整体都会慢下来。

ARIES

ARIES 代表『数据库恢复原型算法』（Algorithms for Recovery and Isolation Exploiting Semantics）。

这个技术要达到一个双重目标：

1. 写日志的同时保持良好性能
2. 快速和可靠的数据恢复

有多个原因让数据库不得不回滚事务：

• 因为用户取消
• 因为服务器或网络故障
• 因为事务破坏了数据库完整性（比如一个列有唯一性约束而事务添加了重复值）
• 因为死锁

有时候（比如网络出现故障），数据库可以恢复事务。

这如何实现呢？为了回答这个问题，我们需要了解日志里保存的信息。

日志

事务的每一个操作（增删改查）产生一条日志，由以下内容组成：

• LSN：一个唯一的日志序列号（Log Sequence Number）。LSN是按时间顺序分配的 * ，这意味着如果操作 A 先于操作 B，log A 的 LSN 要比 log B 的 LSN 小。
• TransID：产生操作的事务ID。
• PageID：被修改的数据在磁盘上的位置。磁盘数据的最小单位是页，所以数据的位置就是它所处页的位置。
• PrevLSN：同一个事务产生的上一条日志记录的链接。
• UNDO：取消本次操作的方法。
  比如，如果操作是一次更新，UNDO将或者保存元素更新前的值/状态（物理UNDO），或者回到原来状态的反向操作（逻辑UNDO）。
• REDO：重复本次操作的方法。 同样的，有 2 种方法：或者保存操作后的元素值/状态，或者保存操作本身以便重复。
• …：（供您参考，一个 ARIES 日志还有 2 个字段：UndoNxtLSN 和 Type）。

进一步说，磁盘上每个页（保存数据的，不是保存日志的）都记录着最后一个修改该数据操作的LSN。

LSN 的分配其实更复杂，因为它关系到日志存储的方式。但道理事相同的。 ARIES 只使用逻辑 UNDO，因为处理物理 UNDO 太过混乱了。

为了说明这一点，这有一个简单的日志记录演示图，由 UPDATE FROM PERSON SET AGE = 18 产生，我们假设这个查询是事务 18 执行的。

每条日志都有一个唯一的 LSN，链接在一起的日志属于同一个事务。日志按照时间顺序链接（链接列表的最后一条日志是最后一个操作产生的）。

日志缓冲区

为了防止写日志成为主要的瓶颈，数据库使用了日志缓冲区。

当查询执行器要求做一次修改：

1. 缓存管理器将修改存入自己的缓冲区
2. 日志管理器将相关的日志存入自己的缓冲区
3. 到了这一步，查询执行器认为操作完成了（因此可以请求做另一次修改）
4. 接着日志管理器把日志写入事务日志，什么时候写日志由某算法来决定
5. 接着缓存管理器把修改写入磁盘，什么时候写盘由某算法来决定

当事务提交，意味着事务每一个操作的1 2 3 4 5 步骤都完成了。写事务日志是很快的，因为它只是「在事务日志某处增加一条日志」；而数据写盘就更复杂啦，因为要用能够快速读取的方式写入数据。

STEAL 和 FORCE 策略

出于性能方面的原因，第 5 步有可能在提交之后完成，因为一旦发生崩溃，还有可能用REDO日志恢复事务。这叫做 NO-FORCE策略。

数据库可以选择FORCE策略（比如第 5 步在提交之前必须完成）来降低恢复时的负载。

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

总结一下这些策略对恢复的影响：

• STEAL/NO-FORCE 需要 UNDO 和 REDO: 性能高，但是日志和恢复过程更复杂 (比如 ARIES)。多数数据库选择这个策略。 注：这是我从多个学术论文和教程里看到的，但并没有看到官方文档里显式说明这一点。
• STEAL/ FORCE 只需要 UNDO.
• NO-STEAL/NO-FORCE 只需要 REDO.
• NO-STEAL/FORCE 什么也不需要: 性能最差，而且需要巨大的内存。

关于恢复

Ok，有了不错的日志，我们来用用它们！

假设新来的实习生让数据库崩溃了，你重启了数据库，恢复过程开始了。

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

1. 分析阶段：恢复进程读取全部事务日志，来重建崩溃过程中所发生事情的时间线，决定哪个事务要回滚（所有未提交的事务都要回滚）、崩溃时哪些数据需要写盘
2. Redo阶段：这一关从分析中选中的一条日志记录开始，使用REDO来将数据库恢复到崩溃之前的状态

在REDO阶段，REDO日志按照时间顺序处理（使用LSN）。

对每一条日志，恢复进程需要读取包含数据的磁盘页LSN。

如果LSN（磁盘页）>= LSN（日志记录），说明数据已经在崩溃前写到磁盘（但是值已经被日志之后、崩溃之前的某个操作覆盖），所以不需要做什么。

如果LSN（磁盘页）< LSN（日志记录），那么磁盘上的页将被更新。

即使将被回滚的事务，REDO也是要做的，因为这样简化了恢复过程（但是我相信现代数据库不会这么做的）

1. Undo 阶段：这一阶段回滚所有崩溃时未完成的事务。回滚从每个事务的最后一条日志开始，并且按照时间倒序处理 UNDO 日志（使用日志记录的 PrevLSN）

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

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

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

当新的事务产生时，这两个表由缓存管理器和事务管理器更新。因为是在内存中，当数据库崩溃时它们也被破坏掉了。

分析阶段的任务就是在崩溃之后，用事务日志中的信息重建上述的两个表。为了加快分析阶段，ARIES提出了一个概念：检查点（check point），就是不时地把事务表和脏页表的内容，还有此时最后一条LSN写入磁盘。那么在分析阶段当中，只需要分析这个LSN之后的日志即可。