数据库工作原理

本文翻译自How does a relational database work

当提到关系型数据库时，我已经不认为其中有什么缺少的东西了。它们应用于各种场景。现在有着各种不同的数据库：从小型便于使用的SQLite到强大的Teradata。但是，只有少量的文章解释了数据库是如何工作的。你可以搜索“关系型数据库是如何工作的”来看看有多少结果。此外，这些文章都很短。现在，如果你找最新的流行技术（Bigdata、NoSQL或JavaScript），你会找到更多深入解释它们是如何工作的文章。

关系型数据库是不是太老了，太无趣了，以至于无法在大学课程、研究论文或书籍外进行解释？

作为一个开发者，我痛恨用而不知，而且，数据库已经被使用了近40年了，这一定是有道理的。这些年里，我花费了上百个小时用来真正的理解这些每天我都在用的黑盒。关系型数据库是非常有趣的，因为它们基于高效与可重用的概念。如果你对理解数据库这事感兴趣并想要深入研究这个广泛的主题，但又没有时间，那这篇文章你一定会喜欢。

虽然本文的标题非常明确，但本文的目的并不是用于理解如何使用数据库的。因此，你需要具备SQL语句的基本查询知识（如join，CRUD语句）；否则你可能无法理解本文，这是你唯一需要具备能力，其他的我都会在本文中有解释。

我将会从计算机科学方面开始，例如时间复杂度。我知道有些人讨厌这个概念，但没有它，你无法理解数据库内在巧妙之处。由于这是一个很大的主题项，我将会专注于那些我觉得是最重要的内容：数据库处理SQL查询的方式。我将只介绍数据库背后的基本概念，这样在读完本文后，您就会对底层所发生的事情有一个很好的了解。

由于这是一篇涉及许多算法和数据结构的长篇技术文章，所以请慢慢阅读。有些概念比较晦涩难懂，即使你跳过部分对整体理解不会有影响。

为了便于读者理解，这边文章可以至少分为三部分。

• 数据库的底层与高层组件概述
• 查询优化过程概述
• 事务和缓冲池管理的概述

目录

• 数据库工作原理
  • 1.基础知识
  • 2.全局概述
  • 3.客户端管理器
  • 4.查询管理器
  • 5.数据管理器
  • 6.事务管理器
  • 7.结论

基础知识

很久之前的开发者必须在编码时确切的知道代码中确切的操作次数，他们将算法和数据结构熟记于心，因为他们不能承担浪费CPU和内存的代价（硬件成本高昂的时代）。

在这一章节中，我将提及其中的一些概念，因为这些是理解数据库所必需的知识，同时我还会介绍数据库索引的概念。

O(1)和 O(n2)

当下，大部分的开发人员不会关心时间复杂度，或许他们是对的。但当你处理庞大的数据量时（这可不是指的数千），或是为了争取毫秒级的效率时，理解这个概念就变得非常重要了。你得知道，数据库必须处理这两种情况。我不会让你厌烦很长时间，只是稍花点时间理解这个想法，这将有助于我们以后理解“基于成本优化”(CBO)的概念。

概念

例如，当说这个算法在O(some_function())时，它意味着对于一定量的数据，算法需要some_function(a_certain_amount_of_data)操作来完成这个工作。

重要的不是数据量，而是数据量增加时，操作数增加的方式。时间复杂度并不能给出操作的确切数量，但这是个好理念。

在这个图中，您可以看到不同类型复杂度的曲线。我用对数标度来表示。换句话说，数据的数量正在迅速从10亿增长到10亿。我们可以看到:

• O(1)或常数复杂度保持不变(否则就不叫常数复杂度)
• O(log(n)) 即使在数据量为十亿的情况下，也保持稳定。
• 最糟糕的复杂度是O(n2)，其操作数量会迅速激增
• 另外两个复杂度也增长的很快

例子

在数据量少时，O(1)和O(n2)之间的差异可以忽略不计。假设有一个需要处理2000个元素的算法。

• O(1) 算法需要一次操作
• O(log(n))算法需要进行7次操纵
• O(n) 算法需要进行2000次操作
• O(n*log(n))算法需要进行14000次操作
• O(n2)算法需要进行3000000次操作

O(1)和O(n2)之间的差异似乎很大(400万)，但你最多会损失2毫秒，只是眨眼的时间。实际上，当前的处理器每秒可以处理数亿次操作。这就是为什么性能优化在许多IT项目中不是一个问题。

正如我所说，在面对大数据量时，了解这个概念仍然很重要。如果这一次算法需要处理1 000 000个元素(对于数据库来说不算大):

• O(1) 算法需要一次操作
• O(log(n))算法需要进行14次操纵
• O(n) 算法需要进行1000000次操作
• O(n*log(n))算法需要进行14000000次操作
• O(n2)算法需要进行1000000000000次操作

常用数据结构的复杂度

• 在一个好的哈希表中进行搜索，获取一个元素的时间复杂度是O(1)
• 在平衡良好的树中进行搜索，获取一个元素的时间复杂度是O(log(n))
• 在数组中搜索的时间复杂度是O(n)
• 最好的排序算法复杂度为O(n*log(n))
• 一个糟糕的排序算法时间复杂读是O(n2)

在下面内容中，我们一起来看看这些算法和数据结构。

时间复杂度有多种情况

• 正常情况
• 最好情况
• 最坏情况

时间复杂度通常是指最糟糕的情况

我只讲了时间复杂度，但复杂度也适用于

• 算法对于内存得消耗
• 算法对于磁盘IO的消耗

当然也有比n的平方更糟糕的复杂度，例如：

• n的四次方：槽糕透了，一些算法具有这种复杂度，之后我会讲到
• n的三次方：非常糟糕，下文中会说到具有这种复杂度的算法（事实上很多数据库中都使用了这类算法）
• n的阶乘：即使是小数据量的情况下，也无法得到预期结果。
• n的n次方：如果用上这种复杂度，那真该扪心自问，IT行业是否真的适合了

注意：我没有给出大O符号的真正意义，只是给出了概念，可以在wiki百科上阅读关于这个符号的概念。

归并排序

当需要对集合排序时，应该怎么做?什么?你说可以调用sort()函数……好的，回答得很好……但是对于数据库，您必须了解sort()函数是如何工作的。

有几种很好的排序算法，而我会着重于最重要的：归并排序 。你可能现在还不理解为什么排序算法是非常有用的，但在查询优化部分后，你就能理解其原因了。此外，理解归并排序有助于往后理解一个数据库的常规操作，那就是合并连接（merge join）

merge

与那些有用的算法一样，归并排序基于一个技巧：将大小为N/2的两个排序数组合并到一个N元素排序数组只需要N次操作。这个操作过程我们称之为归并。

让我们来通过这个简单的例子来理解：

图中可见，构建一个最终排序的8个元素的数组，你只需要将2个4元素数组迭代一次。这是由于2个4元素数组都已经被排好序了。

• 1) 比较当前两个数组中的第一个元素
• 2) 然后将最小的元素放入到8个元素数组中
• 3) 然后移到你取了最小元素的数组的下一个元素
• 重复上述三步，直到其中一个数组的最后一个元素
• 然后取另一个数组的元素放入8个元素的数组中

这是可行的，因为两个4元素数组都是排序的，因此你不需要在数组中回移。

现在我们对这个有了解后就可以查看下面的归并排序伪码了：

array mergeSort(array a)
   if(length(a)==1)   
      return a[0];
   end if  

//recursive calls
[left_array right_array] := split_into_2_equally_sized_arrays(a); array new_left_array := mergeSort(left_array);
array new_right_array := mergeSort(right_array);

//merging the 2 small ordered arrays into a big one
array result := merge(new_left_array,new_right_array);
return result;

归并排序将问题拆分为较小的问题，然后找到小问题的结果，从而得到最初问题的结果。（注意，这种算法我们称之为分治算法）。如果你不理解这个算法，不要担心;我第一次看的时候还不明白。如果它可以帮助你，我认为这个算法是一个两阶段的算法:

• 划分阶段，即是将一个数组拆分为更小的数组
• 排序阶段，即将小组数使用归并的方式合并成一个较大的数组

Division Phase

在划分阶段，使用3步将数组划分为单元数组。正式的步骤数是log(N)(因为N=8，所以log(N) = 3)。

这是怎么得出的结论？一个词：数学。其思想是每一步将初始数组的大小除以2.步骤的数量是将初始数组除以2的次数，这就是对数（以2为底）的精确定义。

Sorting Phase

在排序阶段，从单个组数开始，在每一步，你接受多个合并，其总成本是N=8操作:

• 在第一步中，你有4个合并，每个合并需要2个操作
• 在第二步中，你有2个合并，每个合并需要4个操作
• 在第三步，你有一个合并，这需要8个操作

归并排序效率

为何这个算法效率这么高？

原因：

• 可以修改它以减少内存占用，方法是不创建新数组，而是直接修改输入数组。（注意:这种算法称为in-place）
• 可以修改它，以便同时使用磁盘空间和少量内存，而不会造成巨大的磁盘I/O损失。其思想是在内存中只加载当前正在处理的部分。当您需要对一个只有100 mb内存缓冲区进行多个GB级的表进行排序时，这一点非常重要。（注意：这种算法我们称之为external sorting）
• 您可以修改它以在多个进程/线程/服务器上运行。（例如，分布式归并排序是[Hadoop]的关键组件之一）
• 这个算法可以点石为金

大多数数据库都使用这种排序算法，但它不是惟一的。如果您想了解更多信息，可以阅读这篇讨论数据库中常见排序算法的优缺点的研究论文。

Array, Tree and Hash table

既然我们已经理解了时间复杂度和排序背后的思想，我必须告诉你3种数据结构。这很重要，因为它们是现代数据库的基础。接下来我还将介绍数据库索引的概念。

Array

二维数组是最简单的数据结构。表可以看作一个数组。例如:

这个二维数组是一个包含行和列的表:

• 每一行代表一个主题
• 列描述主题的特征。
• 每个列存储特定类型的数据(整数、字符串、日期…)。

虽然存储和可视化数据很好，但是当您需要查找特定的值时，它就很糟糕了。

例如，如果你想找到所有在英国工作的人，你必须查看每一行，看看这一行是否属于英国。这将消耗你N个操作 (N是行数)，这并不坏，但有没有更快的方法?这就是树结构发挥作用的地方。

注意:大多数现代数据库提供高级数组来有效地存储表，如堆组织的表或索引组织的表。但这并没有改变在一组列上快速搜索特定条件的问题。

树和数据库索引

二叉搜索树是具有特殊属性的二叉树，每个节点的键必须是:

• 大于存储在左子树中的所有键
• 小于存储在右子树中的所有键

我们来直观地看看这是什么意思。

这个数有15个元素，让我们来检索下208试试：

• 我从键值为136的根开始。因为136<208，所以我查看节点136的右子树。
• 因为398>208，我查看节点398的左子树
• 因为250>208，我查看节点250的左子树
• 因为200<208，我查看节点200的左子树。但是200没有右子树，这个值不存在(因为如果它存在，它应该是200节点的子树)

现在我们再来检索下40试试：

• 我从键值为136的根开始。因为i136>40开始，我查看节点136的左子树。

• 因为80>40，我查看节点80的左子树

• 40= 40，节点存在，我提取节点内的行id(它不在图中)，并查看表中给定的行id。

• 知道行id让我知道数据在表上的确切位置，因此我可以立即获得它。

  最后，这两种搜索都消耗了树内的层数。如果您仔细阅读归并排序的部分，您应该会看到有log(N)层。所以二叉树搜索的代价是log(N)，还不错!

  但是这个东西很抽象，所以我们回到我们的问题。如果不是整数，而是表示上表中某个国家的字符串。假设你有一个包含表中“国家”列的树:

• 如果你想知道谁在英国工作

• 你如何查看树得到代表英国的节点

• 在“UK节点”中，您将找到英国工人的行位置。

这个搜索仅需要log(N)操作，而不是N个操作（如果直接使用数组的话）。你刚才想象的就是一个数据库索引。

你可以建立一个树索引对于任何一组列,只要你有一个函数比较键,用于键的顺序。

B+树索引

虽然这个树在获取特定值时非常好用，但是当你需要在两个值之间获取多个元素时，就有大问题了。它将花费O(N)，因为您必须查看树中的每个节点，并检查它是否位于这两个值之间(例如，使用树的顺序遍历)。此外，由于你需要遍历整课树，这对于磁盘读写是不友好的。我们需要找到一个方法来有效的做范围查找。为了解决这个问题，现代数据库使用以前的树的一个修改版本，称为B+树。

在B +树中:

• 只有最低节点(叶节点)存储信息(相关表中行位置)
• 其他节点只是用于在搜索过程中，路由到正确的节点。

可以看到，节点更多(多了两倍)。实际上，您还有其他节点，即“决策节点”，它将帮助您找到正确的节点(在关联的表中存储行位置)。但是搜索复杂度仍然是O(log(N))。最大的区别是，最低的节点链接到它们的后续的节点。

在这个B+树中，如果你想找40到100之间的值:

• 你只需要寻找40(或者40之后的最近的值，如果40不存在的话)，就像之前的树一样。
• 然后收集40的继任者使用直接链接到后面的节点，直到你达到100。

假设有M个叶子结点，树有N个结点。对特定节点的搜索开销与前一棵树一样是log(N)。但使用这种树时，一旦定位一个节点，你可以通过M次操作获取M个节点。这个搜索的开销是M+log（N）次操作，相比N次操作（即二叉树）。此外，你不需要读取整课树，这意味着更少的磁盘操作。如果M很低(比如200行)而N很大(1 000 000行)，则会有很大的不同。

但新的问题又出现了。如果在数据库中添加或删除一行(在相关的B+树索引中):

• 你必须保持在B+树的节点之间的顺序，否则你将无法通过无序的节点来查找。
• 你必须在B+树中保持尽可能少的层级数，否则O(log(N))中的时间复杂度将变成O(N)。

换句话说，B+树需要是自有序和自平衡的。幸运的是，通过智能删除和插入操作，这是可能的。但是这是有代价的:在B+树中的插入和删除的开销在O(log(N))。这就是为什么有些人听说使用太多索引不是一个好主意。因为这样减慢了表中行的快速插入/更新/删除，当数据库需要更新表的索引时，每个索引都需要执行代价高昂的O(log(N))操作。此外，添加索引意味着事务管理器的工作量被增加了(我们将在本文的最后介绍这个管理器)。

更多的细节，你可以看看维基百科关于B+树的文章。如果你想要一个B +树在数据库方面的实现,看看这两篇文章(http://blog.jcole.us/2013/01/07/the-physical-structure-of-innodb-index-pages/)和(http://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/)这两篇文章来自MySQL的核心开发人员。它们都是关于innoDB (MySQL的引擎)如何处理索引的文章。

Hash Table

最后一个重要的数据结构是哈希表。当您希望快速查找值时，它非常有用。此外，理解哈希表将帮助我们以后理解一个名为hash join的常规的数据库连接操作。数据库也使用此数据结构来存储一些内部内容(如锁表或缓冲池，稍后我们将看到这两个概念)

哈希表是这种数据结构，可以快速使用键来找到的元素，要构建一个哈希表，你需要定义：

• 元素的键
• 键的哈希算法。用于计算键的散列值，从而得知元素的位置(称为bucket)
• 一个比较键的函数，一旦你找到正确含有你需要指定查找元素的bucket，就需要使用比较方法在bucket中找到元素。

一个简单例子

我们来看一个可视化例子：

这个哈希表有10个buckets。因为我很懒，我只画了5个桶但是我知道你很聪明，所以我让你想象其他5个。我使用的哈希函数是键的模10。换句话说，我只保留一个元素的键的最后一位来找到它的bucket:

• 如果元素的最后一位数字是0，则该元素最终在bucket 0中
• 如果元素的最后一位数字是1，则该元素最终在bucket 1中
• 如果元素的最后一位数字是2，则该元素最终在bucket 2中
• ...

我使用的比较函数就是两个整数之间的等式。

假设你想要得到元素78:

• 哈希表计算的哈希码为78，即8。
• 它在桶8中查找，它找到的第一个元素是78。
• 它会返回78元素
• 搜索仅花费2个操作(1个用于计算哈希值，另一个用于查找桶内的元素)。

现在，假设你想要得到元素59:

• 哈希表计算的哈希码为59，即9
• 在bucket 9中查找，它找到的第一个元素是99。自99年以来!=59，元素99不是正确的元素。
• 使用相同的逻辑，它查看第二个元素(9)、第三个元素(79)、…和最后一个元素(29)。
• 元素不存在。
• 搜索使用了7个操作

好的hash函数

正如您所看到的，根据您所寻找的值，代价是不一样的!

如果我现在用键的1 000 000的模(即取最后6位数字)来做为哈希函数，那么第二次搜索只需要一个操作，因为在bucket 000059中没有元素。真正的挑战是找到一个好的哈希函数，它将创建包含非常少量元素的bucket。

在我的例子中，找到一个好的哈希函数是很容易的。但这是一个简单的例子，当键是如下情况时，找到一个好的哈希函数是有难度的:

• 一个字符串(例如一个人的姓)
• 2个字符串(例如一个人的姓和名)
• 2个字符串和一个日期(例如一个人的姓、名和出生日期)

使用一个高效的hash函数，在hash表中查找元素的复杂度是O(1)

数组和hash表

为什么不使用数组呢?

嗯，你问了一个好问题。

• 哈希表可以在内存中加载一半，其他桶可以留在磁盘上。

• 当使用数组时，你必须使用一个连续的空间在内存。如果您正在加载一个大的表，那么拥有足够的连续的内存空间是非常困难的。

• 使用哈希表，您可以选择您想要的键(例如国家和一个人的名字)。

要了解更多信息，您可以阅读文章Java HashMap ，这是一个高效的散列表实现;您不需要了解Java就可以理解本文中的概念。

全局概述

我们已经看到了数据库中的基础组件。我们现在需要退一步来看看全局。

数据库是一组可以方便地访问和修改的信息。但是一堆简单的文件也可以做到这一点。事实上，像SQLite这样最简单的数据库只不过是一堆文件。但是SQLite是一组精心制作的文件，因为它允许您:

• 使用事务以确保数据安全和一致
• 快速处理数据，即使你正在处理数百万的数据

一般而言，数据库可以有如下部分:

在写这一部分之前，我已经阅读了许多书籍/论文，以及各种描述讨论数据库相关的资料。因此，不要过多地关注我如何组织这个数据库或如何命名这些过程，因为我做了一些选择来适应本文的规划。重要的是不同的组成部分，其中心思想是数据库如何划分为多个相互交互的组件。

核心组件：

• 进程管理器: 许多数据库都有一个用于管理的进程/线程池。此外，为了获得纳秒级的速度，一些现代数据库使用自己的线程而不是操作系统线程。
• 网络管理器: 网络I/O是一个大问题，特别是对于分布式数据库。这就是为什么有些数据库有自己的管理器。
• 文件系统管理器:磁盘I/O是数据库的第一个瓶颈。拥有一个能够完美地处理操作系统文件系统甚至替换它的管理器是很重要的。
• 内存管理器:为了避免磁盘I/O的损失，需要大量的随机存储内存。但如果处理大量内存，则需要高效的内存管理器。特别是当您同时有许多使用内存的查询时。
• 安全管理器:用于管理用户的身份验证和授权
• 客户端管理器:用于管理客户端连接

工具：

• 备份管理器: 用于保存和恢复数据库。
• 恢复管理器: 用于在崩溃后，将数据库重新启动恢复到一致性的状态
• 监控管理器: 用于记录数据库的活动并提供监视数据库的工具
• 管理员管理器: 用于存储元数据(如表的名称和结构)，并提供工具来管理数据库、模式、表空间……

查询管理：

• 查询解析器：检查查询是否有效
• 查询重写器：预先优化一个查询
• 查询优化器：优化一个查询
• 查询优化器：编译和执行一个查询

数据管理：

• 事务管理器: 处理事务
• 缓存管理器:在使用数据之前将数据放入内存，在将数据写入磁盘之前将数据放入内存
• 数据访问管理器:访问磁盘上的数据

在本文的其余部分，我将重点介绍数据库如何通过如下过程管理SQL查询:

• 客户端管理器
• 查询管理器
• 数据管理器(在本部分中我还将包括恢复管理器)

客户端管理器

客户端管理器是处理与客户端通信的部分。客户端可以是(web)服务器，也可以是终端用户/终端应用程序。客户端管理器提供了通过一组通用的api做为访问数据库的不同方方式:JDBC、ODBC、OLE-DB…

它还可以提供专用的数据库访问api。

当你连接到一个数据库:

• 管理员首先检查您的身份验证(您的登录名和密码)，然后检查您是否有授权使用数据库。这些访问权限是由DBA设置的。
• 然后，它检查是否有一个进程(或线程)可用来管理您的查询。
• 它还检查数据库是否处在在重负载状态。
• 它可以等待片刻，以获得所需的资源。如果此等待超时，则关闭连接并给出可读的错误消息。
• 然后它发送您的查询到查询管理器，并且此时您的查询将被处理
• 由于查询处理不是一个“全部或没有”的事情，一旦它从查询管理器获取数据，它将 部分结果存储在一个缓冲区，并开始发送给你。
• 如果出现问题，它会停止连接，给你一个可读的解释，并释放资源。

查询管理器

这部分是数据库的强大之处。在这一部分中，一个写得不好的查询被转换成一个快速可执行代码。然后代码将被执行，并且结果会被返回给客户端管理器。这是一个多步骤的操作:

• 首先对查询进行解析，以查看它是否有效
• 然后将会重写，用于删除无用的操作，并添加一些预优化
• 然后查询将被优化以提高性能，并转换为执行和数据访问计划。
• 然后这个计划被编译
• 最后，它被执行

读完这部分后，如果你想更好的理解，我推荐你阅读:

• 关于CBO的最初研究论文(1979):关系数据库管理系统中的访问路径选择。这篇文章只有12页，并且只有有计算机科学的平均水平就可以理解。

  https://www.cs.berkeley.edu/~brewer/cs262/3-selinger79.pdf

• 一篇非常好的和深入的，关于DB2 9.x 的查询优化的的介绍。

  http://infolab.stanford.edu/~hyunjung/cs346/db2-talk.pdf

• 一篇关于PostgreSQL如何优化查询的很好的介绍。这是最易访问的文档，因为它更多的是关于“让我们看看PostgreSQL在这些情况下提供了什么查询计划”，而不是“让我们看看PostgreSQL使用的算法”。

  http://momjian.us/main/writings/pgsql/optimizer.pdf

• 关于优化的官方SQLite文档。它很容易阅读，因为SQLite使用简单的规则。此外，这是唯一的官方文件，真正解释了它是如何工作的。

  https://www.sqlite.org/optoverview.html

• 关于SQL Server 2005如何优化查询的一个很好的介绍

  https://blogs.msdn.com/cfs-filesystemfile.ashx/__key/communityserver-components-postattachments/00-08-50-84-93/QPTalk.pdf

• 关于Oracle 12c优化器的白皮书

  http://www.oracle.com/technetwork/database/bi-datawarehousing/twp-optimizer-with-oracledb-12c-1963236.pdf

• 两位作者关于查询优化的理论课程。很好的着重描述磁盘I/O卡西奥，是计算机科学所必需的。

  http://codex.cs.yale.edu/avi/db-book/db6/slide-dir/PPT-dir/ch12.ppt

  http://codex.cs.yale.edu/avi/db-book/db6/slide-dir/PPT-dir/ch13.ppt

• 另一个理论课程，我发现它更容易阅读，但它只关注连接操作符和磁盘I/O。

  https://www.informatik.hu-berlin.de/de/forschung/gebiete/wbi/teaching/archive/sose05/dbs2/slides/09_joins.pdf

查询解析

每个SQL语句都被发送到解析器，在那里检查语法是否正确。如果您在查询语句有问题，解析器将拒绝该查询。例如，如果你写的是“SLECT…”而不是“SELECT…”，故事到此结束。

但除此以外。它还检查关键字是否按正确的顺序使用。例如，where在select之间的查询语句被拒绝。

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

• 表是否存在
• 字段是否存在
• 字段类型的操作是否正确(例如，您不能将整数与字符串进行比较，您不能在整数上使用substring()函数)

然后，它将检查您是否具有读取(或写入)查询中的表的授权。同样，这些表上的访问权限是由DBA设置的。

在此解析过程中，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在一个有唯一的约束的数据，那么DISTINCT关键字将被删除。
• 冗余连接消除:如果你有两个相同的连接条件，因为一个连接条件隐藏在一个视图中，或者根据传递性有一个无用的连接，它被删除。
• 常量算术计算:如果你写的东西需要微积分，那么它在重写过程中计算一次。例如，将age >10+2 转换为 age>12和TODATE("some date")转换为日期时间格式的日期
• (高级)分区剪裁:如果您使用的是分区表，则重写器能够找到要使用的分区。
• (高级)物化视图重写:如果您有一个物化视图，它匹配查询中谓词的一个子集，则重写器检查该视图是否是最新的，并修改查询以使用物化视图而不是原始表。
• (高级)自定义规则:如果您有自定义规则来修改查询(如Oracle策略)，则重写器将执行这些规则
• (高级)Olap转换:分析/窗口函数，星型连接，rollup…也将被转换(但我不确定这是由重写器或优化器完成的，因为这两个过程非常接近，它取决于数据库)。

然后，将这个重写的查询发送给查询优化器，这才是有趣开始!

统计

在描述一个数据库如何优化一个查询之前，我们需要谈谈统计数据，因为没有的话，一个数据库是愚蠢的。如果你不告诉数据库去分析它自己的数据，它就不会去做，而且会做出（非常）糟糕的假设。

但是数据库需要什么样的信息呢?

我必须(简要地)谈一下数据库和操作系统如何存储数据。他们使用的最小单位，我们称之为一页或一个块(默认为4或8KB)。这意味着，如果你只需要1KB，它将无论如何都消耗一页。如果一页占用8KB，那么将浪费7KB。

回到统计数据!当您要求数据库收集统计数据时，它计算的值如下:

• 一个表包含的行/页数
• 对于表中的每一列:
  • 不同的数据值
  • 数据值的长度(min、max、average)
  • 数据范围信息(最小、最大、平均)
• 表的索引信息。 这些统计数据将帮助优化器估计查询的磁盘I/O、CPU和内存使用量

每一列的统计数据非常重要。例如，如果需要在表PERSON上JOIN两个列: LAST_NAME、FIRST_NAME。通过统计数据，数据库知道FIRST_NAME上只有1,000个不同的值，LAST_NAME上有1,000,000个不同的值。因此，数据库将以LAST_NAME，FIRST_NAME的顺序关联，而不是FIRST_NAME，LAST_NAME顺序的方式，因为它产生的比较要少得多，因为LAST_NAME不太可能是相同的，所以大多数情况下，对LAST_NAME的前2(或3)个字符进行比较就足够了。

但这些都是基本的统计数据。您可以要求数据库计算称为柱状图的高级统计数据。柱状图是关于列内值分布的统计信息。例如

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

这些额外的统计信息将帮助数据库找到更好的查询计划。特别是对于相等谓词(例如 where AGE = 18)或范围谓词(例如 where AGE > 10 and AGE <40)，因为数据库可以更好地了解这些谓词所涉及的行数(注意:这个概念的技术术语是selectivity)。

统计数据存储在数据库的元数据中。例如，你可以看到(非分区)表的统计数据:

• 在Oracle中的 USER/ALL/DBA_TABLES和USER/ALL/DBA_TAB_COLUMNS
• 在DB2中的SYSCAT.TABLES 和 SYSCAT.COLUMNS。

统计数字必须是最新的。没有什么比数据库认为一个表只有500行而它却有100万行更糟糕的了。统计数据的唯一缺点是计算它们需要时间。这就是大多数数据库默认情况下不会自动计算它们的原因。数百万的数据使得计算它们变得很困难。在这种情况下，可以选择只计算基本统计信息，也可以选择计算数据库样本的统计信息。

例如，当我在一个项目中处理每个表中的数亿行时，我选择只计算10%的统计数据，这带来了巨大的时间收益。就本文来说，这是一个糟糕的决定，因为Oracle 10G为特定表的特定列选择的10%有时与100%非常不同(对于具有100万行的表，这种情况不太可能发生)。这个错误的统计数据导致查询有时花费8小时而不是30秒;找到根本原因是一场噩梦。这个例子显示了统计数据的重要性。

注意：当然，每个数据库都会有更高级的统计信息。如果您想了解更多，请阅读数据库的文档。话虽如此，我还是试图了解统计数据是如何使用的，我找到的最好的官方文档是来自PostgreSQL。

查询优化器

所有现代数据库都使用基于成本的优化(或CBO)来优化查询。其思想是为每个操作设置一个成本，并通过使用最便捷的操作链来获得结果，从而找到降低查询成本的最佳方法。

为了理解CBO是如何工作的，我认为最好有一个例子来“感受”这个任务背后的复杂性。在这一部分中，我将介绍连接两个表的3种常见方法，我们很快就会发现，即使是一个简单的连接查询也很难优化。之后，我们将看到真正的优化器是如何完成这项工作的。

对于这些连接，我将关注它们的时间复杂度，但是数据库优化器计算它们的CPU开销、磁盘I/O开销和内存占用。时间复杂度和CPU成本之间的区别是，时间成本非常接近(对于像我这样的懒家伙来说)。对于CPU开销，我应该计算每一个操作，比如加法、“if语句”、乘法、迭代……

• 每个高级代码操作都有特定数量的底层的CPU操作。
• CPU操作的开销是不一样的(就CPU周期而言)，无论你使用的是英特尔酷睿i7，英特尔奔腾4,AMD Opteron…换句话说，它取决于CPU架构。

利用时间复杂性更容易(至少对我来说是这样)，使用它，我们仍然可以得到CBO的概念。我有时会讨论磁盘I/O，因为它是一个重要的概念。请记住，瓶颈主要是磁盘I/O，而不是CPU使用量。

indexes

我们在B+树章节中，已经讨论了索引。只需要记住这些索引已经排好序了。

仅供参考，还有其他类型的索引，如位图索引。它们在CPU、磁盘I/O和内存方面提供的成本与B+树索引不同。

此外，如果能够改善执行计划的成本，许多现代数据库可以动态地为当前查询创建临时索引。

Access Path

在应用连接操作符之前，首先需要获取数据。以下是获取数据的方法。

注意:由于所有访问路径的真正问题是磁盘I/O，所以我不会过多地讨论时间复杂性。

Full scan

如果你曾经读过一个执行计划，你一定见过一个词，全扫描(或者只是扫描)这个词。全表扫描就是数据库完全读取一个表或一个索引。在磁盘I/O方面，表的全扫描显然比索引的全扫描开销更为大。

Range scan

还有其他类型的扫描，如索引范围扫描。例如，当您使用诸如“WHERE AGE > 20 AND AGE <40”之类的谓词时，可以使用它。

当然，您需要在字段AGE上有一个索引来使用这个索引范围扫描。

我们在第一部分中已经看到，范围查询的时间成本类似于log(N) +M，其中N是该索引中的数据数量，M是对该范围内的行数的估计。得益与统计数据，N和M值都是已知的(注意:M是谓词AGE >20和AGE<40的选择性)。此外，对于范围扫描，您不需要读取完整的索引，因此就磁盘I/O而言，它的成本比全表扫描要低。

Unique scan

如果你只需要索引中的一个值，你可以使用唯一扫描。

Access by row id

大多数情况下，如果数据库使用索引，它将不得不查找与索引关联的行。为此，它将使用row id进行访问。

例如，做了如下操作

SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28

有的person表有age列索引,优化器将使用索引来查找所有age为28的元素，因为索引只有age的信息，而想知道lastname 和firstname，就需要它关联到表中的行。

但如果你进行如下操作

SELECT TYPE_PERSON.CATEGORY from PERSON ,TYPE_PERSON WHERE PERSON.AGE = TYPE_PERSON.AGE

PERSON上的索引将用于与TYPE_PERSON连接，但是PERSON表不会通过row id访问，因为您没有询问这个表上的信息。

尽管它对于一些访问非常有效，但是这种操作的真正问题是磁盘I/O。如果您需要太多的row id访问，数据库可能会选择全扫描。

Others paths

我没有给出所有的访问路径。如果您想了解更多信息，可以阅读Oracle文档。其他数据库所使用的名称可能不相同，但其背后的概念是相同的。

Join操作

前边讲了如何获取数据，下面来看看如果进行Join。

我将介绍3种常见的连接操作:merge join、hash join和nested loop join。但是在这之前，我需要介绍一些新的词汇: 内部关系和外部关系。一个关系可以是:

• 一个表
• 一个索引
• 前一个操作的中间结果(例如前一个连接的结果)

当连接两个关系时，join算法以不同的方式管理这两个关系。在本文的其余部分，我将假设:

• 外部关系是左数据集

• 内部关系是右数据集

  例如，A join B是A和B之间的连接，其中A是外部关系，B是内部关系。

大多数情况下，A JOIN B的成本与B JOIN A的成本是不一样的

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

注意:N和M是关联的基数。

Nested loop join

Nested loop join是最简单的。

概念如下：

• 遍历外关联的每一行
• 查看内关联中的所有行，查看是否有匹配的行

伪码如下：

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)

对于磁盘I/O，在循环读取外部关联中的N行时，内部循环需要从内部关联中读取M行。这个算法需要从磁盘中读取N + N*M行。但是，如果内部关系足够小，你可以把这个关系放到内存中，只需要读取M +N次。通过这种调整，内部关系必须是最小的关系，因为它有更多的机会来适应内存。

在时间复杂度方面没有区别，但在磁盘I/O方面，最好是一次读取这两个关系。

当然，内部关系可以用索引代替，这对磁盘I/O更有益。

由于这个算法非常简单，所以如果 inner relation太大而无法装入内存，这里有另一个版本的磁盘I/O更友好。这个想法是这样的:

• 不是逐行读取两个关系，
• 以小批量的方式地读，并在内存中保存小批量数据，
• 比较两个批量数据里面的行，并保持匹配的行，
• 然后从磁盘加载新的批量数据，并进行比较
• 如此类推，直到没有批量数据可以加载。

这里是一个可行的算法：

// 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次访问(每次访问一个行)。
• 有了这个新版本，访问磁盘的次数变成了number_of_bunches_for(outer)+ number_of_bunches_for(outer)* number_of_bunches_for(inner)。
• 如果你增加批量读取的大小，就能减少了磁盘访问的数量。

注意:与以前的算法相比，每个磁盘访问会收集更多的数据，但这并不重要，因为它们是顺序访问(机械磁盘的真正问题是获取第一个数据的时间)。

Hash Join

hash join相比nested loop jon要复杂，但在多数的使用场景下代价更小

hash join的概念是:

• 1)从 inner relation中获取所有元素
• 2)建立内存中的哈希表
• 3)将outer relation的所有元素逐一获取
• 4)计算每个元素的哈希值(使用哈希表的哈希函数)，找到inner relation的关联bucket
• 5)查找bucket中的元素与外部表中的元素是否匹配

在时间复杂度方面，我需要做一些假设来简化问题:

• inner relation 被分成X个桶
• 哈希函数几乎均匀分布哈希值的两个关系。换句话说，桶的大小是相等的。
• outer relation的一个元素与桶内所有元素的匹配的代价，与桶内元素的数量有关。

时间复杂度为(M/X) N + cost_to_create_hash_table(M) + cost_of_hash_functionN

如果哈希函数创建了足够的小桶，那么时间复杂度为O(M+N)

这是另一个版本的散列连接，它对内存友好，但对磁盘I/O不友好。流程:

• 1)计算 inner relations和 outer relations的哈希表
• 2)然后把它们存放在磁盘上
• 3)然后逐个bucket 比较两个关系(一个在内存中加载，另一个在内存中逐行读取)

Merge join

merge join是唯一产生排序结果的连接方式。

注意:在这个简化的 merge join中，没有内部表或外部表;他们都扮演着同样的角色。但是真正的实现会有所不同，例如在处理重复记录时。

合并连接可以分为两个步骤:

1. (可选)排序连接操作:两个输入都按连接键排序。
2. Merge join 操作:将排序后的输入合并在一起。

• Sort

我们已经讨论过归并排序，在这种情况下，归并排序是一种好的算法(但如果内存并不足够富裕时，就不是最好的算法)。

但有时数据集已经排序，例如:

• 如果表是原生已经排序的，例如连接条件下的索引组织表

• 如果关联的连接条件上是索引

• 如果此关联应用于查询过程中已排序的中间结果

• Merge join

这部分与我们看到的归并排序的归并操作非常相似。但是这一次，我们不是从两个关系中选择每个元素，而是从两个相等的关系中选择元素。这个想法是这样的:

• 1)比较两个关系中的当前元素(当前=第一次)
• 2)如果它们相等，那么将两个元素都放入结果中，然后转到两个关系的下一个元素
• 3)如果不是，则转到下一个元素，查找与排序最低元素的关联(因为下一个元素可能匹配)
• 4)重复1、2、3，直到找到关系中的最后一个元素。

这是可行的，因为两个关系都是排序的，因此您不需要在这些关系中“返回”。

这个算法是一个简化的版本，因为它不处理相同的数据在两个数组中出现多次的情况(也就是多个匹配上的情况)。真正的版本在这种情况下更复杂;这就是为什么我选择了一个简化的版本。

如果两个关联都已排序，则时间复杂度为O(N+M)

如果两个关系都需要排序，那么时间复杂度就是对两个关联排序的代价:O(N*Log(N) + M*Log(M))

对于计算机科学爱好者来说，这里有一个可能的算法，可以处理多个匹配(注意:我不是100%肯定我的算法):

mergeJoin(relation a, relation b)
  relation output
  integer a_key:=0;
  integer b_key:=0;
  
  while(a[a_key]!=null or 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
    //i.e. a[a_key] == b[b_key]
    
    //count the number of duplicates in relation a
    integer nb_dup_in_a = 1:
    while(a[a_key]==a[a_key+nb_dup_in_a])
      nb_dup_in_a++;
      //count the number of duplicates in relation b
      integer dup_in_b = 1:
      while (b[b_key]==b[b_key+nb_dup_in_b])
        nb_dup_in_b++;
        
        //write the duplicates in output
        for (int i = 0; i< nb_dup_in_a ; i++) 
          for (int j = 0; i< nb_dup_in_b ; i++)
            write_result_in_output(a[a_key+i],b[b_key+j]) 
        a_key=a_key + nb_dup_in_a- 1;
        b_key=b_key + nb_dup_in_b-1;
        
        end if
      end while

哪个更好？

如果有最好的连接类型，就不会有这些多种类型。这个问题很难，因为有很多因素在起作用，比如:

• 可用内存:没有足够的内存，您可以与强大的hash join告别了（至少是完整的内存hash join)
• 两个数据集的大小。例如，如果您有一个包含非常小的表的大表，那么nested loop join将比hash join更快，因为hash join创建散列的开销很大。如果您有两个非常大的表，nested loop join将非常占用CPU开销。
• 是否有索引。对于两个b +树索引，可以明智的选择merge join
• 如果结果需要排序:即使你使用无序的数据集,您可能想要使用一个代价高昂的merge join,因为最后的结果排序,你可以将结果与另一个merge join关联
• 如果关联已经排序:在这种情况下，merge join是最好的选择方案
• 你正在做的连接的类型:它是一个等价连接(即tableA.col1 = tableB.col2) ?它是一个内连接，一个外连接，一个笛卡尔积还是一个自连接?一些连接在某些情况下不能工作。
• 数据分布。如果连接条件中的数据是歪斜的(例如，您按照人们的姓连接他们，但是许多人的姓都是一样的)，那么使用hash join将是一场灾难，因为散列函数将创建不均匀分布的bucket。
• 如果您想要多线程/进程执行联接

想要获取更多的信息，你可以读DB2，ORACLE or SQL Server的文档.

最简例子

我们已经看到了三种类型的连接操作。

现在，假设我们需要连接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

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

• 我应该为每个连接使用什么类型的连接?

我有3种可能的连接(Hash Join, Merge Join, Nested Join)，可以使用0、1或2个索引(更不用说还有不同类型的索引了)。

• 我应该选择什么顺序来计算连接?

例如，下图显示了仅针对4个表的3个连接的不同可能计划

这就是我提出的可能性:

• 1)我使用蛮力方法

使用数据库统计，我计算每一个可能的计划的成本，我保留最好的一个。但是有很多可能性。对于给定的联接顺序，每个联接都有3种可能:HashJoin、MergeJoin、NestedJoin。对于给定的连接顺序有34种可能。连接顺序是一个在二叉树上的排列问题，并且有(2*4)!/(4+1)!可能的订单。对于这个非常简单的问题，我最终得到34(24)!/(4+1)!的可能性。

在非极客的术语中，它意味着27 216种可能的计划。如果我现在添加了合并连接使用0、1或2个B+树索引的可能性，那么可能的计划数量就变成了210 000个。我忘记说过这个查询非常简单吗?

• 2)我哭了，辞掉了这份工作

这很诱人，但你不会得到你的结果，我需要钱来支付账单。

• 3)我只试了几个方案，选择成本最低的那个。

因为我不是超人，所以我无法计算每个计划的成本。相反，我可以从所有可能的计划中任意选择一个子集，计算它们的成本，然后给出这个子集的最佳计划。

• 4)我应用智能规则来减少可能的计划的数量

有两种类型的规则:

我可以使用“逻辑”规则来排除无用的可能性，但它们不会过滤很多可能的计划。例如:“nested loop join的内部关联必须是最小的数据集”

我接受找不到最佳解决方案的事实，并采用更激进的规则来大幅减少可能性的数量。例如，“如果关联很小，则使用nested loop join，而决不使用 merge join 或 hash join”

在这个简单的例子中，我得到了许多可能性。但是一个真正的查询可以有其他的关系操作符，比如 OUTER JOIN、CROSS JOIN、GROUP BY、ORDER BY、PROJECTION、UNION、INTERSECT、DISTINCT ……，这意味着有更多的可能性。

那么，数据库是如何做的?

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

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

大多数时候，优化器不是找到最好的解决方案，而是找到一个“好的”解决方案。

对于小的查询，可以使用蛮力方法。但是有一种方法可以避免不必要的计算，这样即使中等的查询也可以使用蛮力方法。这叫做动态规划。

Dynamic Programming

这两个词背后的意思是很多执行计划是非常相似的。如果你看看下面的计划:

它们共享相同的(A JOIN B)子树。因此，不必在每个计划中计算这个子树的代价，我们可以计算一次，保存计算出的代价，并在再次看到这个子树时重用它。更正式地说，我们面临的是一个重叠的问题。为了避免部分结果的额外计算，我们使用记忆法。

使用这种技术，而不是(2*N)!/(N+1)!时间复杂度，而只有3N。在我们前面的4个连接示例中，它意味着从336降低到81。如果您使用一个包含8个连接的更大的查询(并不大)，这意味着从57 657 600降低到6561。

对于计算机科学极客们，这是我在我已经给你们上过的正式课程中找到的一个算法。我不会解释这个算法，所以只有当你已经知道动态编程或如果你擅长算法时可以阅读这篇文章。

procedure findbestplan(S)
if (bestplan[S].cost infinite)
   return bestplan[S]
   // else bestplan[S] has not been computed earlier, compute it now
   if (S contains only 1 relation)
     set bestplan[S].plan and bestplan[S].cost based on the best way
     of accessing S /* Using selections on S and indices on S */ 
   else  for each non-empty subset S1 of S such that S1 != S
   P1= findbestplan(S1)
   P2= findbestplan(S - S1)
   A = best algorithm for joining results of P1 and P2
   cost = P1.cost + P2.cost + cost of A
   if cost < bestplan[S].cost
     bestplan[S].cost = cost
     bestplan[S].plan = “execute P1.plan; execute P2.plan;
          join results of P1 and P2 using A”
return bestplan[S]

对于更大的查询，你仍然可以使用动态编程方法，但是要使用额外的规则(或启发式)来消除可能性

• 如果我们只分析特定类型的计划(例如:左深树)，我们最终得到的是n*2n，而不是3n

• 如果我们添加逻辑规则来避免某些模式的计划(比如“如果一个表是给定谓词的索引，那么不要尝试在表上进行合并连接，而只在索引上尝试”)，那么它将减少可能性的数量，而不会影响获得尽可能好的解决方案。
• 如果我们在流程上添加规则(比如“在所有其他关系操作之前执行连接操作”)，它也会减少很多可能性。

贪婪算法

但是对于一个非常大的查询或者有一个非常快的答案(但不是一个非常快的查询)，则使用另一种类型的算法，即贪心算法。

其思想是遵循规则(或启发式)以增量方式构建查询计划。有了这个规则，贪婪算法就能一步一步地找到问题的最佳解决方案。该算法使用一个连接启动查询计划。然后，在每个步骤中，算法使用相同的规则向查询计划添加新的连接。

让我们举一个简单的例子。假设我们有一个查询，它包含5个表(a、B、C、D和E)上的4个连接。让我们使用“使用成本最低的连接”规则

• 我们任意从5个表中的一个开始(我们选A)
• 我们计算每个与A连接的成本 (A是内部或外部的关系)。
• 我们发现A连接B的成本最低。
• 然后我们计算每个与 A JOIN B子集的连接代价(A join B成为inner relation或 outer relation)。
• 我们发现(A jion B)连接C的代价最高。
• 然后我们用(A jion B)连接C的结果计算每个连接的成本…
• ....
• 最后，我们找到了计划((A JOIN B) JOIN C) JOIN D) JOIN E)

因为我们任意地从A开始，我们可以对B应用相同的算法，然后是C，然后是D，然后是e，然后我们保持这个计划的最低成本。

顺便说一下，这个算法有一个名字:它叫做最近邻算法。

我不会进入细节,但有一个很好的建模easily be solved和一种N * log (N)的排序用于解决这个问题。该算法的代价是O(N*log(N)) vs O(3N)对于完整的动态规划版本。如果您有一个包含20个连接的大查询，这意味着26对3 486 784 401，一个很大的区别!

这个算法的问题是，我们假设，找到两个表最佳的连接方式，并在找寻最佳的连接方式的过程中，保留两表连接的前提下，加入新表连接，从而找到多表的最佳连接方式。但是:

• 即使A连接B给出了A、B和C之间的最低代价
• (A JOIN C) JOIN B可能比(A JOIN B) JOIN C的结果更好。

为了改善结果，可以使用不同的规则运行多个贪婪算法，并保持最佳计划。

其他算法

寻找最佳方案是许多计算机科学研究人员的一个活跃的研究课题。他们常常试图为更精确的问题/模式找到更好的解决方案。例如,

• 如果查询是星型连接(它是某种类型的多连接查询)，一些数据库将使用特定的算法。
• 如果查询是并行查询，一些数据库将使用特定的算法
• ...

还有其他算法的研究，用来代替动态规划的大查询。贪心算法属于一个较大的家族，称为启发式算法。贪婪算法遵循一个规则(或启发式)，保持它在前一步找到的解决方案，并“附用”它来找到当前步骤的解决方案。有些算法遵循一个规则，并以一种循序渐进的方式应用它，但并不总是保持在前一步中找到的最佳解决方案。它们被称为启发式算法。

例如，遗传算法遵循一个规则，但最后一步的最佳解决方案往往不保持:

• 一个解决方案表示一个可能的完整查询计划
• 不是一个解决方案(即计划)，而是P个解决方案(即计划)保持在每个步骤。
• 0) P查询计划是随机创建的
• 1)只保留代价最低的计划
• 2)这些最好的计划混合在一起就能产生P个新计划
• 3)有些新计划是随机修改的
• 4)步骤1、2、3重复T次
• 5)然后从最后一个循环的P计划中保留最佳计划。

你做的循环越多，你的计划就会越好。

这是魔法吗?不，这是自然法则:适者生存!

顺便说一句，遗传算法是在PostgreSQL中实现的，但我无法找到它们是否被默认使用。

数据库中还有其他启发式算法，比如Simulated Annealing,Iterative Improvement,两阶段优化……但我不知道它们目前是用于企业数据库，还是只用于研究数据库。

有关更多信息，可以阅读下面的研究文章，其中介绍了更多可能的算法:数据库查询优化中连接排序问题算法综述

Real optimizers

[你可以跳到下一部分，我要说的并不重要]

但是，所有这些都是理论性的。因为我是一名开发人员，而不是研究员，所以我喜欢具体的例子。

让我们看看SQLite优化器是如何工作的。这是一个轻量级的数据库，所以它使用了一个简单的优化基于一个贪婪算法与额外的规则来限制可能性的数量:

• SQLite选择从不在交叉连接操作符中，重新排序表

• 连接 以nested joins的方式实现

• 外部连接总是按照它们发生的顺序计算

• -…

• -在3.8.0版本之前，SQLite在搜索最佳查询计划时使用“最近邻贪婪算法

  等等，我们已经看过这个算法了!真是巧了!

• 自3.8.0版本(2015年发布)以来，SQLite在搜索最佳查询计划时使用了N近邻贪婪算法

让我们看看另一个优化器是如何工作的。IBM DB2与所有的企业数据库一样，但我将重点介绍这个数据库，因为它是我在转换到大数据之前真正使用过的最后一个数据库。

如果我们查看官方文档，我们会了解到DB2优化器允许您使用7种不同级别的优化:

• 使用贪婪算法的连接

  • 0 最小优化，使用索引扫描和嵌套循环连接，并且避免一些查询重写
  • 1 低优化
  • 2 完全优化

• 使用动态编程的连接

  • 3 中度优化和粗略近似
  • 5 充分优化，使用启发式的所有技术
  • 7 完全优化类似于5，没有启发式
  • 9 最大优化不遗余力/不惜代价考虑所有可能的连接次序，包括笛卡尔产品

  我们可以看到，DB2使用贪婪算法和动态编程。当然，由于查询优化器是数据库的主要驱动力，所以它们不会共享它们所使用的启发法。

仅供参考，默认级别为5。默认情况下，优化器使用以下特征:

• 使用所有可用的统计数据，包括频率值和分位数统计数据。
• 应用所有查询重写规则(包括物化查询表路由)，但计算密集型规则只适用于非常罕见的情况。
• 动态编程连接枚举，使用:
  • 限制只用复合内部关系
  • 限制使用对涉及查找表的星型模式笛卡尔积
• 广泛的访问方法被考虑，包括列表预取(注意:将看到什么是意思)，索引的结束(注意:一个特殊的操作与索引)，物化查询表路由。

默认情况下，DB2对连接顺序使用受启发法限制的动态编程。

其他条件(GROUP BY、DISTINCT…)由简单的规则处理。

Query Plan Cache

由于创建计划需要时间，大多数数据库将计划存储到查询计划缓存中，以避免对相同查询计划进行不必要的重新计算。这是一个很大的主题，因为数据库需要知道何时更新过时的计划。其主旨是设置一个阈值，如果一个表的统计数据超过了这个阈值，那么涉及该表的查询计划将从缓存中清除。

查询执行器

在这个阶段，我们有一个已优化过的执行计划。这个计划被编译成一个可执行的代码。然后，如果有足够的资源(内存、CPU)，则由查询执行程序执行。计划中的操作符(JOIN、SORT BY…)可以按顺序或并行方式执行;这取决于执行器。为了获取和写入数据，查询执行器与数据管理器进行交互，这是本文的下一部分。

数据管理器

data_manager

在此步骤中，查询管理器正在执行查询并需要来自表和索引的数据。它要求数据管理器获取数据，但是有两个问题:

• 关系数据库使用事务模型。因此，您不能在任何时候获取任何数据，因为其他人可能同时在使用/修改数据。
• 数据检索是数据库中最慢的操作，因此数据管理器需要足够智能来获取和保存内存缓冲区中的数据。

在本部分中，我们将看到关系数据库如何处理这两个问题。我不会讨论数据管理器获取数据的方式，因为它不是最重要的(这篇文章够长了!)

缓存管理器

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

cache_manager

查询执行程序不是直接从文件系统获取数据，而是将数据请求到缓存管理器。缓存管理器有一个名为缓冲池的内存缓存。从内存中获取数据极大地提高了数据库的速度。很难给出一个数量级，因为这取决于你需要做的操作:

• 顺序访问(例如:全扫描)vs随机访问(例如:按行id访问)，

• 读和写

  数据库使用的磁盘类型:

  • 72k /10k/15k转/分钟硬盘
  • SSD
  • RAID 1/5 /…

  但是我要说内存比磁盘快100到100k倍。

但是，这会导致另一个问题(与数据库一样……)。缓存管理器需要在查询执行器使用数据之前获取数据;否则，查询管理器必须等待来自慢速磁盘的数据。

预读取

这个问题称为预读取。查询执行程序知道它需要的数据，因为它知道查询的完整流程，并且知道磁盘上的数据和统计信息。这个主旨是这样的:

• 当查询执行器处理它的第一批数据时
• 它要求缓存管理器预加载第二批数据
• 当它开始处理第批组数据时
• 它要求缓存管理器预加载第三批，并通知缓存管理器的第一批数据可以从缓存中清除。
• …

缓存管理器将所有这些数据存储在其缓冲池中。为了知道是否仍然需要数据，缓存管理器添加了关于缓存数据的额外信息(称为latch)。

有时，查询执行器不知道需要什么数据，有些数据库不提供此功能。相反，它们使用推测性的预取(例如:如果查询执行器请求数据1、3、5，它可能在会提前请求数据7、9、11)或顺序预取(在这种情况下，缓存管理器只是在请求的数据之后从磁盘加载下一个连续的数据)。

为了监视预取的工作情况，现代数据库提供了一个名为缓存命中率的监控。命中率显示了在不需要磁盘访问的情况下，在缓冲区缓存中找到请求数据的频率。

注意:较差的缓存命中率并不总是意味着缓存不能正常工作。要了解更多信息，可以阅读 Oracle documentation。

但是，缓冲区是有限的内存。因此，它需要删除一些数据才能加载新的数据。加载和清除缓存需要付出磁盘和网络I/O方面的代价。如果您有一个经常执行的查询，那么总是加载然后清除此查询使用的数据是低效的。为了处理这个问题，现代数据库使用缓冲区替换策略。

5.3. 缓存替换策略

• LRU

LRU 代表 Least Recently Used。此算法背后的思想是将最近使用过的数据保存在缓存中，因此更有可能再次使用。

这是一个虚拟的例子：

为了便于理解，我假设缓冲区中的数据没有被锁存器锁定(因此可以删除)。在这个简单的例子中，缓冲区可以存储3个元素:

• 1:缓存管理器使用数据1并将数据放入空缓冲区
• 2: CM使用数据4并将数据放入半加载的缓冲区
• 3: CM使用数据3并将数据放入半加载的缓冲区
• 4: CM使用数据9。缓冲区已满，因此数据1被删除 ，因为它是最后的近期使用的数据。数据9被添加到缓冲区中
• 5: CM使用数据4。数据4已经在缓冲区中，因此它再次成为第一个最近使用的数据。
• 6: CM使用数据1。缓冲区已满，因此数据接9被删除，因为它是最后的近期使用的数据。将数据1添加到缓冲区中
• …

该算法运行良好，但存在一定的局限性。如果在一个大的表上有一个完整的扫描呢?换句话说，当表/索引的大小超过缓冲区的大小时，会发生什么情况?使用此算法将删除缓存中的所有以前的值，而来自完整扫描的数据可能只使用一次。

改进

为了防止这种情况发生，一些数据库添加了特定的规则。例如，根据Oracle文档:

对于非常大的表，数据库通常使用直接路径读取，直接加载块，以避免填充缓冲区缓存。对于中等大小的表，数据库可以使用直接读取或缓存读取。如果决定使用缓存读取，那么数据库会将这些块放在LRU列表的末尾，以防止扫描有效地清除缓存。

还有其他的可能性，比如使用LRU的高级版本LRU- k。例如，SQL Server使用LRU-K表示K =2。

这个算法背后的思想是考虑到更多的历史。对于简单的LRU，算法只考虑最后一次使用数据的时间。LRU-K:

• 它考虑了K的数据最后一次使用。
• 一个权重放在的次数的数据被使用
• 如果一堆新数据被加载到缓存中，旧的但经常使用的数据不会被删除(因为它们的权重更高)。
• 但是如果旧数据不再使用，算法就不能将它们保存在缓存中。
• 因此，权重减少随着时间的推移，如果数据没有使用。

权重的计算是昂贵的，这就是为什么SQL Server只使用K=2。对于可接受的开销，这个值执行得很好。

要更深入地了解LRU-K，可以阅读原始的研究论文(1993):数据库磁盘缓冲的lru-k页面替换算法

其他算法

当然还有其他的算法来管理缓存:

• 2Q(类LRU-K算法)
• 时钟(类似于LRU-K的算法)
• MRU(最近使用，与LRU使用相同的逻辑，但有另一个规则)
• LRFU(最近使用频率最高)
• …

一些数据库允许使用默认算法之外的另一种算法。

写缓存

我只讨论了在使用数据之前加载数据的读缓冲区。但是在数据库中，也有写缓冲区，它存储数据并将它们按组刷新到磁盘上，而不是逐个写入数据，那样会产生许多单独的磁盘访问。

请记住，缓冲区存储的是页(最小的数据单元)，而不是行(这是一种逻辑/人工的数据查看方式)。如果缓冲池中的页已被修改且未写入磁盘，则该页为脏。有多种算法可以决定在磁盘上写入脏页面的最佳时间，但是它与事务的概念高度相关，这是本文的下一部分。

事务管理器

最后，这一部分是关于事务管理器的。我们将看到这个过程如何确保每个查询在自己的事务中执行。但是在此之前，我们需要了解ACID事务的概念。

ACID

ACID事务是一个工作单元，它确保4件事情:

• 原子性:事务是“全部或没有”，即使它持续10个小时。如果事务崩溃，则状态回到事务之前(事务被回滚)。
• 隔离:如果两个事务A和B同时运行，无论A是否在事务B之前/之后/期间完成，事务A和B的结果必须相同。
• 持久性:一旦事务提交(即成功结束)，无论发生什么(崩溃或错误)，数据都将保留在数据库中。
• 一致性:只有有效的数据(在关系约束和功能约束方面)被写入数据库。一致性与原子性和隔离性有关。

在同一事务期间，可以运行多个SQL查询来读取、创建、更新和删除数据。当两个事务使用相同的数据时，混乱就开始了。经典的例子是账户a向账户b的转账。假设你有两笔交易:

• 交易1，从A账户取出100美元给B账户
• 交易2，从A账户取出50美元给B账户

如果我们回到ACID属性:

• 原子性确保无论在T1期间发生什么(服务器崩溃、网络故障……)，您都不会出现从a中取出100美元而没有给B的情况(这种情况是不一致的状态)。
• 隔离性确保如果T1和T2发生在同一时间,最后将150 B得到150美元,例如,一个150美元和B给50美元因为T2的行为部分抹去T1(这种情况下也是一个不一致的状态)。
• 持久性确保T1不会消失在空气中，如果数据库崩溃后，只是T1被提交。
• 一致性确保在系统中没有创建或销毁任何金钱。

[如果你愿意，你可以跳到下一部分，我要说的内容对这篇文章的其余部分并不重要]

许多现代数据库没有将纯隔离作为默认行为，因为它带来了巨大的性能开销。SQL规范定义了4个隔离级别:

• Serializable (SQLite中的默认行为):最高级别的隔离。同时发生的两个事务是100%隔离的。每一笔交易都有自己的“世界”。
• Repeatable read (MySQL中的默认行为):除了一种情况外，每个事务都有自己的“世界”。如果一个事务成功结束并添加了新数据，这些数据将在另一个事务中可见，并且仍然在运行事务。但是，如果修改了数据并成功结束，那么修改将在仍然运行的事务中不可见。因此，事务间隔离的中断只与新数据有关，而与现有数据无关。

例如，如果事务a执行“SELECT count(1) from TABLE_X”，然后事务B在TABLE_X中添加并提交一个新数据，如果事务a再次执行count(1)，则该值将不相同。

这称为幻读。

• Read committed (Oracle, PostgreSQL和SQL Server的默认行为):这是一个可重复的读取一个新的隔离。如果一个事务a读取一个数据D，然后这个数据被事务B修改(或删除)并提交，如果a再次读取数据D，它将看到B对数据所做的修改(或删除)。

这称为不可重复读。

• 读取未提交:隔离的最低级别。这是一种读提交一种隔离的新突破。如果一个事务a读取一个数据D，然后这个数据D被一个事务B修改(未提交且仍在运行)，如果a再次读取数据D，它将看到修改后的值。如果事务B被回滚，那么由A第二次读取的数据D没有任何意义，因为它已经被一个从未发生过的事务B修改过(自从它被回滚以来)。

这叫做脏读。

大多数数据库都添加了自己的自定义隔离级别(比如PostgreSQL、Oracle和SQL Server使用的快照隔离)。而且，大多数数据库并没有实现SQL规范的所有级别(尤其是读未提交级别)。

用户/开发人员可以在连接开始时覆盖默认的隔离级别(只需添加非常简单的一行代码)。

并发控制

确保隔离、一致性和原子性的真正问题是对相同数据的写操作(添加、更新和删除):

• 如果所有的事务只是读取数据，他们可以在同一时间工作，而不修改另一个事务的行为。
• 如果(至少)其中一个事务正在修改其他事务读取的数据，那么数据库需要找到一种方法来对其他事务隐藏这种修改。此外，它还需要确保这个修改不会被另一个没有看到修改数据的事务删除。

此问题称为并发控制。

解决这个问题最简单的方法是一个一个地运行每个事务(即按顺序运行)。但那是完全不可扩展的，而且只有一个核心在多处理器/核心服务器上工作，效率不是很高……

解决这个问题的理想方法是，每次创建或取消一个事务时:

• 监察所有事务的所有操作
• 检查两个(或更多)事务的部分是否冲突，因为它们正在读取/修改相同的数据。
• 对冲突事务内部的操作进行重新排序，以减少冲突部分的大小
• 按一定顺序执行冲突部分(非冲突事务仍同时运行)。
• 考虑到一笔交易可以取消。

更正式地说，这是一个如何调度冲突的问题。更具体地说，这是一个非常困难和cpu昂贵的优化问题。企业数据库无法承受为每个新事务事件寻找最佳调度而等待数小时的代价。因此，他们使用不太理想的方法，导致在冲突的事务之间浪费更多的时间。

锁管理器

为了处理这个问题，大多数数据库使用锁和/或数据版本控制。由于这是一个很大的主题，所以我将重点讨论锁部分，然后再谈一谈数据版本控制。

Pessimistic locking

悲观锁

锁背后的思想是:

• 如果事务需要数据
• 它锁定数据
• 如果另一个事务也需要这些数据
• 它将不得不等到第一个事务释放数据。

这称为一个独占锁。

但是，为只需要读取数据的事务使用排他锁是非常昂贵的，因为它会迫使只想读取相同数据的其他事务等待。这就是为什么有另一种类型的锁，共享锁。

共享锁:

• 如果一个事务只需要读取一个数据a，
• 它“共享锁定”数据并读取数据
• 如果第二个事务也只需要读取数据a，
• 它“共享锁定”数据并读取数据
• 如果第三个事务需要修改数据a，
• 它“独占锁”数据，但它必须等待，直到2个其他事务释放他们的共享锁，以应用其独占锁的数据A。

但是，如果一个数据是一个排他锁，那么只需要读取数据的事务将不得不等待排他锁的结束，以便在数据上放置一个共享锁。

锁管理器是提供和释放锁的进程。在内部，它将锁存储在一个哈希表中(其中的键是要锁定的数据)，并知道每个数据:

• 哪些事务正在锁定数据
• 哪些事务正在等待数据

Deadlock

但是使用锁会导致两个事务永远等待一个数据:

在这个图:

• 事务A拥有data1的独占锁，正在等待获取data2
• 事务B拥有data2的独占锁，正在等待获取data1

这称为死锁。

在死锁期间，锁管理器将选择取消(回滚)哪个事务以消除死锁。这个决定并不容易:

• 是否最好终止修改最少数据量的事务?
• 如果另一个事务的用户已经等待了更长的时间，那么是否最好终止最年轻的事务?
• 是更好的杀死事务，将需要更少的时间来完成?
• 在回滚的情况下，有多少事务会受到回滚的影响?

但是在做出这个选择之前，它需要检查是否存在死锁。

可以将哈希表视为一个图(如前面的图所示)。如果图中有一个循环，则会出现死锁。由于检查周期的开销很大(因为包含所有锁的图非常大)，所以通常使用一种更简单的方法:使用timeout。如果在此超时内没有给出锁，事务将进入死锁状态。

锁管理器也可以在给锁之前检查这个锁是否会导致死锁。但是完美地完成它在计算上是很昂贵的。因此，这些预先检查通常是一组基本规则。

Two-phase locking

确保纯粹隔离的最简单方法是在事务开始时获取锁，并在事务结束时释放锁。这意味着一个事务在开始之前必须等待它的所有锁，并且在事务结束时释放事务持有的锁。它工作，但它产生了大量的时间浪费等待所有锁。

一个更快的方法是两阶段锁协议(由DB2和SQL Server使用)，其中一个事务分为两个阶段:

• 增长阶段，其中一个事务可以获得锁，但不能释放任何锁。
• 收缩阶段，一个事务可以释放锁(对数据，它已经处理，不会再处理)，但不能获得新的锁。

这两个简单规则背后的思想是:

• 释放不再使用的锁，以减少其他事务等待这些锁的时间
• 防止在事务开始后修改数据，因此与事务获得的第一个数据不一致的情况。

除非修改数据并释放关联锁的事务被取消(回滚)，否则此协议可以正常工作。您可能会遇到这样的情况:另一个事务读取修改后的值，而这个值将被回滚。为了避免这个问题，所有的排他锁必须在事务结束时释放。

A few words

当然，真正的数据库使用更复杂的系统，包括更多类型的锁(如意图锁)和更多粒度(行、页、分区、表、表空间上的锁)，但原理是一样的。

我只介绍了纯粹的基于锁的方法。数据版本控制是处理这个问题的另一种方法。

版本背后的思想是:

• 每个事务可以在同一时间修改相同的数据

• 每个事务都有自己的数据副本(或版本)

• 如果两个事务修改相同的数据，只有一个修改将被接受，另一个将被拒绝，相关的事务将被回滚(可能会重新运行)。

  它提高了性能，因为:

• 读取器事务不会阻塞写入器事务

• 写事务不会阻塞读事务

• 没有来自“臃肿与慢”锁管理器的开销

除了两个事务写入相同的数据外，一切都比锁好。此外，您很快就会得到一个巨大的磁盘空间开销。

数据版本控制和锁定是两种不同的视图:乐观锁定和悲观锁定。它们各有利弊;这实际上取决于用例(更多的读和更多的写)。对于一个关于数据版本控制的演讲，我推荐这个非常好的演讲来看看PostgreSQL是如何实现多版本并发控制的。

有些数据库，如DB2(直到DB2 9.7)和SQL Server(快照隔离除外)只使用锁。其他如PostgreSQL, MySQL和Oracle使用了一种混合的方法，包括锁和数据版本控制。我不知道数据库只使用数据版本控制(如果您知道一个基于纯数据版本控制的数据库，请告诉我)。

一位读者告诉我:

Firebird和Interbase使用版本控制，并没有使用行锁。版本控制对索引有一个有趣的影响:有时一个惟一的索引包含重复项，该索引的条目可能比表的行还多，等等。

如果您在不同的隔离级别上读取该部分，那么当您增加隔离级别时，您将增加锁的数量，从而增加事务等待它们的锁所浪费的时间。这就是为什么大多数数据库在默认情况下不使用最高的隔离级别(Serializable)。

像往常一样,您可以检查主要数据库的文档。MySQL,PostgreSQL,Oracle

日志管理器

我们已经看到，为了提高性能，数据库将数据存储在内存缓冲区中。但是，如果在提交事务时服务器崩溃，那么在崩溃期间您将丢失仍然在内存中的数据，这会破坏事务的持久性。

您可以将所有内容写到磁盘上，但是如果服务器崩溃，您将以一半的数据写到磁盘上而告终，这会破坏事务的原子性。

必须撤消或完成事务所写的任何修改。

要解决这个问题，有两种方法:

• 影子副本/页: 每个事务创建自己的数据库副本(或只是数据库的一部分)，并在这个副本上工作。如果出现错误，则删除该副本。如果成功，数据库立即使用文件系统技巧切换来自副本的数据，然后删除“旧的”数据。
• 事务日志:事务日志是一个存储空间。在每次写入磁盘之前，数据库会在事务日志中写入一个信息，以便在事务崩溃/取消时，数据库知道如何删除(或完成)未完成的事务。

WAL

当在涉及许多事务的大型数据库上使用影子副本时，会产生巨大的磁盘开销。这就是为什么现代数据库使用事务日志的原因。事务日志必须存储在稳定的存储中。我不会深入讨论存储技术，但是使用(至少)RAID磁盘是防止磁盘故障的必要手段。

大多数数据库(Oracle, SQL Server, DB2, PostgreSQL, MySQL and SQLite)处理事务日志使用Write-Ahead Logging protocol （WAL）。WAL协议有3条规则:

• 1)对数据库的每次修改都会产生一条日志记录，在将数据写到磁盘上之前，必须将日志记录写到事务日志中。
• 2)日志记录必须按顺序书写;发生在日志记录B之前的日志记录a必须写在B之前
• 3)事务提交后，必须在事务成功结束之前将提交操作写入事务日志。

这项工作由日志管理器完成。查看它的一个简单方法是，在缓存管理器和数据访问管理器(将数据写到磁盘上)之间，日志管理器在将事务日志写到磁盘上之前，将每个更新/删除/创建/提交/回滚写到事务日志上。这很容易，是吧?

其实并不然，!在经历了所有这些之后，您应该知道与数据库相关的一切都受到“数据库效率”的诅咒。更严重的问题是，如何在保持良好性能的同时编写日志。如果事务日志上的写操作太慢，则会降低所有操作的速度。

ARIES

1992年，IBM的研究人员“发明”了一种增强版的WAL，称为ARIES。大多数现代数据库或多或少都使用ARIES。逻辑可能不一样，但背后的概念是无处不在的。我把引用放在了invented(麻省理工学院的课程)上，因为根据这门课程(http://db.csail.mit.edu/6.830/lectures/lec15notes.pdf)， IBM的研究人员“只不过编写了事务恢复的良好实践”。自从我5岁时，ARIES的论文发表，我才不管那些研究人员的流言蜚语呢。我读了大量关于ARIES的研究论文，我发现它非常有趣!在这一部分，我只会给你一个ARIES的概述，但我强烈建议阅读论文，如果你想要一个真正的知识。

ARIES代表用于恢复和隔离使用语义的算法。

这项技术的目的有两个:

• 1)写日志时有好的表现
• 2)具有快速、可靠的恢复能力

数据库必须回滚事务的原因有很多:

• 因为用户取消了它
• 由于服务器或网络故障
• 因为事务破坏了数据库的完整性(例如，您在一个列上有一个惟一的约束，而事务添加了一个副本)
• 因为死锁

有时(例如，在网络故障的情况下)，数据库可以恢复事务。

这怎么可能?要回答这个问题，我们需要理解存储在日志记录中的信息。

The logs

事务中的每个操作(添加/删除/修改)生成一个日志。本日志记录由以下几部分组成:

• LSN:一个独特的日志序列号。这个LSN是按时间顺序给出的。这意味着如果操作A发生在操作B之前那么LSN (log A)就会小于LSN (log B)

• TransID:产生操作的事务的id。

• PageID:修改后的数据在磁盘上的位置。磁盘上的最小数据量是一个页面，因此数据的位置就是包含数据的页面的位置。

• PrevLSN:同一个事务产生的前一个日志记录的链接。

• 撤销:一种删除操作效果的方法

  例如，如果操作是一个更新，撤销将在更新之前存储更新元素的值/状态(物理撤销)，或者存储返回到前一个状态的反向操作(逻辑撤销)。

• 重做:重做操作的一种方式

• 同样地，有两种方法可以做到这一点。要么在操作之后存储元素的值/状态，要么在操作本身中重播它。

• (仅供参考，一个ARIES 日志有2个其他字段:UndoNxtLSN和类型)。

而且，磁盘上的每个页面(存储数据，而不是日志)都有最后一个修改数据的操作的日志记录(LSN)的id。

给出LSN的方式比较复杂，因为它与日志的存储方式相关联。但想法是一样的。

ARIES 只使用逻辑撤销，因为处理物理撤销实在是一团糟。

注:据我所知，只有PostgreSQL没有使用撤销。它使用一个垃圾收集器守护进程来删除旧版本的数据。这与PostgreSQL中数据版本控制的实现有关。

为了让您更好地理解，下面是查询“UPDATE FROM PERSON SET AGE = 18;”生成的日志记录的可视化和简化示例。假设这个查询在事务18中执行。

每个日志都有一个惟一的LSN。被链接的日志属于同一事务。日志按时间顺序链接(链接列表的最后一个日志是最后一个操作的日志)。

Log Buffer

为了避免日志写入成为主要的瓶颈，使用了日志缓冲区。

当查询执行器要求修改时:

• 1)缓存管理器将修改，存储在其缓冲区中。
• 2)日志管理器将相关日志，存储在其缓冲区中。
• 3)在这一步，查询执行程序认为操作已经完成(因此可以请求其他修改)
• 4)然后(稍后)日志管理器将日志写入事务日志。何时写入日志是由算法决定的。
• 5)然后(稍后)缓存管理器将修改写入磁盘。何时在磁盘上写入数据是由算法决定的。

当一个事务被提交时，它意味着对于事务中的每个操作，步骤1、2、3、4、5都被执行。写入事务日志是快速的，因为它只是“在事务日志的某个地方添加了一个日志”，而在磁盘上写入数据则更为复杂，因为它是以一种比读取数据更快的方式写入数据的。

STEAL and FORCE policies

出于性能原因，步骤5可能在提交之后执行，因为在发生崩溃的情况下，仍然可以使用重做日志恢复事务。这被称为无强制策略。

数据库可以选择一个FORCE策略(即在提交之前必须执行第5步)来降低恢复期间的工作负载。

另一个问题是选择是否在磁盘上一步一步地写入数据，还是缓冲区管理器需要等到提交命令才立即写入所有内容。在“偷”和“不偷”之间进行选择取决于您想要什么:使用撤消日志进行长时间恢复的快速写入还是快速恢复?

以下是这些策略对恢复的影响摘要:

• STEAL/NO-FORCE 需要撤销和重做: 最高性能，但提供更复杂的日志和恢复过程(如ARIES)。这是大多数数据库的选择。注:我在许多研究论文和课程中都读到过这个事实，但我在官方文件中找不到它(明确地)。
• STEAL/ FORCE 只需要UNDO。
• NO-STEAL/NO-FORCE 只需要REDO。
• NO-STEAL/FORCE 不需要任何东西:最差的表现和一个巨大的ram是需要的。

The recovery part

好的，我们有很好的log，让我们使用它们!

假设新的实习生破坏了数据。重新启动数据库，恢复过程就开始了。

ARIES 从崩溃中恢复过来需要三个步骤:

• 1)分析传递:恢复过程读取完整的事务日志，以重新创建崩溃期间发生的时间线。它确定要回滚哪些事务(所有没有提交订单的事务都回滚)，以及崩溃时需要将哪些数据写到磁盘上。
• 2)重做通过:此通过从分析期间确定的日志记录开始，并使用重做将数据库更新到崩溃之前的状态。

在重做阶段，重做日志按时间顺序处理(使用LSN)。

对于每个日志，恢复过程读取磁盘上包含要修改的数据的页面的LSN。

如果LSN(page_on_disk)>=LSN(log_record)，这意味着在崩溃之前已经在磁盘上写入了数据(但是该值被在日志之后和崩溃之前发生的操作覆盖了)，所以什么也不做。

如果LSN(page_on_disk)<LSN(log_record)，则更新磁盘上的页面。

即使对于将要回滚的事务，也会进行重做，因为它简化了恢复过程(但我相信现代数据库不会这样做)。

• 3)撤销传递:此传递回滚所有在崩溃时未完成的事务。回滚从每个事务的最后一个日志开始，并按反时间顺序处理撤消日志(使用日志记录的PrevLSN)。

在恢复期间，必须对事务日志发出关于恢复过程所做的操作的警告，以便磁盘上写的数据与事务日志中写的数据保持同步。解决方案可能是删除正在撤消的事务的日志记录，但这非常困难。相反，ARIES在事务日志中写入补偿日志，逻辑上删除被删除事务的日志记录。

当一个事务被“手动”取消，或者被锁管理器取消(以停止死锁)，或者仅仅是因为网络故障，那么分析传递就不需要了。事实上，关于重做和撤消操作的信息可以在两个内存表中找到:

• 事务表(存储所有当前事务的状态)
• 脏页表(存储哪些数据需要写到磁盘上)。

对于每个新的事务事件，缓存管理器和事务管理器将更新这些表。由于它们位于内存中，所以当数据库崩溃时它们将被销毁。

分析阶段的工作是使用事务日志中的信息在崩溃后重新创建两个表。为了加快分析过程，ARIES提供了检查点的概念。其思想是在磁盘上不定期地写入事务表和脏页表的内容，以及写入时的最后一个LSN，以便在分析过程中，只分析LSN之后的日志。

结论

在写这篇文章之前，我知道这个主题有多重要，我知道要写一篇深入的文章需要时间。结果我花了比预期多两倍的时间，但我学到了很多。

如果你想对数据库有一个很好的概述，我建议你阅读研究论文“[数据库系统的架构体系]”(http://db.cs.berkeley.edu/papers/fntdb07-architecture.pdf)。这是一个关于数据库的很好的介绍(110页)，而且它是非cs人员可以读懂的。这篇文章帮助我为这篇文章找到了一个计划，它不像我的文章那样关注数据结构和算法，而是更多地关注架构概念。

如果您仔细阅读这篇文章，您现在应该了解数据库是多么强大。由于这是一篇很长的文章，让我来回顾我们所看到的:

• B+树索引的概述
• 数据库的全局概览
• 概述CBO，重点关注连接操作符
• 缓冲池管理概述
• 事务管理概述

但是数据库包含了更多的精巧之处。例如，我没有谈论一些敏感的问题，比如:

• 如何管理集群数据库和全局事务
• 如何在做一个快照时，数据库仍保持运行
• 如何有效地存储(和压缩)数据
• 如何管理内存

因此，当您必须在有缺陷的NoSQL数据库和坚如磐石的关系数据库之间进行选择时，请三思。不要误解我，一些NoSQL数据库非常棒。但他们还很年轻，还在处理一些与应用程序有关的具体问题。

总之，如果有人问你数据库是如何工作的，你现在可以回答了。