关于后端:关系数据库如何工作

当谈到关系数据库时，我不禁想到短少了一些货色。它们到处都在应用。有许多不同的数据库：从小而有用的 SQLite 到弱小的 Teradata。然而，只有几篇文章解释了数据库的工作原理。你能够本人谷歌“关系数据库是如何工作的”，看看有多少后果。而且，这些文章很短。当初，如果您寻找最新的风行技术（大数据、NoSQL 或 JavaScript），您会发现更深刻的文章解释了它们的工作原理。

关系数据库是否太古老太无聊而无奈在大学课程、钻研论文和书籍之外进行解释？

作为开发人员，我厌恶应用我不了解的货色。而且，如果数据库曾经应用了 40 年，那必定是有起因的。多年来，我花了数百个小时来真正了解我每天应用的这些奇怪的黑匣子。关系数据库 十分 乏味，因为它们 基于有用且可重用的概念。如果您对理解数据库感兴趣，但从未有工夫或志愿深入研究这个宽泛的主题，那么您应该喜爱这篇文章。

只管本文的题目很明确，但本文的目标并不是要理解如何应用数据库 。因而， 您应该曾经晓得如何编写简略的连贯查问和根本的 CRUD 查问；否则你可能看不懂这篇文章。这是你惟一须要晓得的，我会解释其余的。

我将从一些计算机科学的货色开始，比方工夫复杂度。我晓得你们中的一些人厌恶这个概念，然而没有它，你就无奈了解数据库中的聪慧之处。因为这是一个微小的话题，我将专一于 我认为必不可少的内容：数据库解决 SQL 查问的形式 。我将只介绍 数据库背地的基本概念，以便在本文结尾处您对幕后产生的事件有一个很好的理解。

因为这是一篇波及许多算法和数据结构的长篇技术文章，请花点工夫浏览它。有些概念比拟难了解；您能够跳过它们，但依然能够理解总体思路。

对于常识渊博的您，本文或多或少分为 3 个局部：

• 低级和高级数据库组件概述
• 查问优化过程概述
• 事务和缓冲池治理概述

回归根源

很久以前（在一个边远的星系中……），开发人员必须确切地晓得他们正在编码的操作数量。他们对本人的算法和数据结构一目了然，因为他们累赘不起节约慢速计算机的 CPU 和内存。

在这一部分中，我将提醒您其中一些概念，因为它们对于了解数据库至关重要。我还将介绍 数据库索引 的概念。

O (1) 与 O (n 2)

现在，许多开发人员并不关怀工夫复杂度……他们是对的！

然而，当您解决大量数据（我不是在议论数千个数据）时，或者如果您正在为毫秒而战，那么了解这个概念就变得至关重要。你猜怎么着，数据库必须同时解决这两种状况！我不会让你腻烦很长时间，只是工夫去理解这个想法。这将有助于咱们当前了解 基于老本的优化 的概念。

这个概念

工夫复杂度用于查看算法对于给定数量的数据须要多 长时间。为了形容这种复杂性，计算机科学家应用数学大 O 表示法。该符号与一个函数一起应用，该函数形容了一个算法对于给定数量的输出数据须要多少次操作。

例如，当我说“这个算法在 O(some_function() ) 中”时，它意味着对于肯定数量的数据，该算法须要 some_function(a_certain_amount_of_data) 操作来实现它的工作。

重要的 不是数据量，而是 当数据量减少时操作数量减少的形式。工夫复杂度并没有给出确切的操作数量，而是一个好主见。

在此图中，您能够看到不同类型复杂性的演变。我应用对数刻度来绘制它。换句话说，数据的数量正在迅速从 1 减少到 10 亿。咱们能够看到：

• O(1)或常数复杂度放弃不变（否则它不会被称为常数复杂度）。
• 即便有数十亿数据，O(log(n))依然很低。
• 最蹩脚的复杂度是O(n 2)，其中操作数量迅速爆炸。
• 其余两个竞争我的项目正在迅速减少。_

例子

在数据量较少的状况下，O(1) 和 O(n 2)之间的差别能够忽略不计。例如，假如您有一个算法须要解决 2000 个元素。

• O(1) 算法将破费您 1 次操作
• O(log(n)) 算法将破费您 7 次操作
• O(n) 算法将破费您 2 000 次操作
• O(n*log(n)) 算法将破费您 14 000 次操作
• O(n 2) 算法将破费您 4 000 000 次操作

O(1) 和 O(n 2)之间的差别仿佛很大（400 万），但您最多会在 2 毫秒内失落，这只是眨眼的工夫。事实上，以后的处理器[每秒能够解决数亿次操作。这就是为什么性能和优化在许多 IT 我的项目中不是问题的起因。

正如我所说，在面对大量数据时，理解这个概念依然很重要。如果这次算法须要解决 1 000 000 个元素（这对于数据库来说并不是那么大）：

• O(1) 算法将破费您 1 次操作
• O(log(n)) 算法将破费您 14 次操作
• O(n) 算法将破费您 1 000 000 次操作
• O(n*log(n)) 算法将破费您 14 000 000 次操作
• O(n 2) 算法将破费您 1 000 000 000 000 次操作

我没有做数学计算，但我会说应用 O(n 2) 算法你有工夫喝杯咖啡（甚至是第二杯！）。如果您在数据量上再加 0，您将有工夫小睡一会儿。

更深刻

给你一个想法：

• 在一个好的哈希表中搜寻失去一个 O(1) 中的元素
• 在均衡良好的树中搜寻会失去 O(log(n)) 的后果
• 在数组中搜寻会失去 O(n) 的后果
• 最好的排序算法具备 O(n*log(n)) 复杂度。
• 一个蹩脚的排序算法具备 O(n 2) 复杂度

留神：在接下来的局部中，咱们将看到这些算法和数据结构。

工夫复杂度有多种类型：

• 均匀状况
• 最好的状况
• 和最坏的状况

工夫复杂度通常是最坏的状况。

我只谈到了工夫复杂度，但复杂度也实用于：

• 算法的内存耗费
• 算法的磁盘 I/O 耗费

当然，还有比 n 2 更简单的复杂性，例如：

• n 4：太蹩脚了！我将提到的一些算法具备这种复杂性。
• 3 n：那更糟了！咱们将在本文两头看到的一种算法具备这种复杂性（并且它的确在许多数据库中应用）。
• 阶乘 n：即便数据量很少，您也永远不会失去后果。
• n n : 如果你最终遇到了这种复杂性，你应该问问本人 IT 是否真的是你的畛域……

留神：我没有给你大 O 符号的真正定义，而只是想法。您能够在 Wikipedia 上浏览这篇文章以理解实在（渐近）定义。

合并排序

当您须要对汇合进行排序时，您会怎么做？什么？你调用 sort() 函数……好吧，很好的答案……然而对于数据库，你必须理解这个 sort() 函数是如何工作的。

有几种很好的排序算法，所以我将专一于最重要的一种：归并排序 。你当初可能不明确为什么排序数据是有用的，但你应该在查问优化局部之后。此外，了解归并排序有助于咱们当前了解一种常见的数据库连贯操作，称为 归并连贯。

合并

像许多有用的算法一样，归并排序基于一个技巧：将 2 个大小为 N/2 的排序数组合并为一个 N 元素排序数组只须要 N 次操作。此操作称为 合并。

让咱们通过一个简略的例子来看看这意味着什么：

您能够在此图中看到，要结构最终的 8 个元素的排序数组，您只须要在 2 个 4 元素数组中迭代一次。因为两个 4 元素数组都已排序：

• 1）您比拟两个数组中的两个以后元素（第一次以后 = 第一次）
• 2）而后取最低的一个放入 8 元素数组中
• 3）而后转到数组中的下一个元素，你取了最低的元素
• 并反复 1,2,3 直到达到其中一个数组的最初一个元素。
• 而后，您将另一个数组的其余元素放入 8 元素数组中。

这是无效的，因为两个 4 元素数组都已排序，因而您不须要在这些数组中“返回”。

当初咱们曾经了解了这个技巧，这是我的合并排序伪代码。

归并排序将问题合成为更小的问题，而后找到更小的问题的后果失去初始问题的后果（留神：这种算法称为分治法）。如果您不理解此算法，请不要放心；我第一次看到的时候没看懂。如果它能够帮忙你，我认为这个算法是一个两阶段算法：

• 阵列被分成更小的阵列的划分阶段
• 将小数组放在一起（应用合并）以造成更大数组的排序阶段。

分工阶段

在划分阶段，应用 3 个步骤将阵列划分为繁多阵列。正式的步数是 log(N)（因为 N=8，log(N) = 3）。

我怎么晓得？

我是蠢才！一句话：数学。这个想法是每一步都将初始数组的大小除以 2。步数是您能够将初始数组除以 2 的次数。这是对数的准确定义（以 2 为底）。

分拣阶段

在排序阶段，您从酉数组开始。在每个步骤中，您利用多个合并，总成本为 N=8 操作：

• 在第一步中，您有 4 个合并，每个合并须要 2 个操作
• 在第二步中，您有 2 个合并，每个合并须要 4 个操作
• 在第三步中，您有 1 次合并，须要 8 次操作

因为有 log(N) 个步骤，因而总成本为 N * log(N) 个操作。

归并排序的威力

为什么这个算法如此弱小？

因为：

• 您能够批改它以缩小内存占用，办法是不创立新数组，而是间接批改输出数组。

留神：这种算法称为 [就地] 算法。

• 您能够批改它以同时应用磁盘空间和大量内存，而不会造成微小的磁盘 I/O 损失。这个想法是仅将以后解决的局部加载到内存中。当您须要对只有 100 兆字节内存缓冲区的数千兆字节表进行排序时，这一点很重要。

留神：这种算法称为[内部排序。

• 您能够批改它以在多个过程 / 线程 / 服务器上运行。

例如，分布式归并排序是[Hadoop]（大数据中的框架）的要害组件之一。

• 这个算法能够把铅变成金（实在的事实！）。

大多数（如果不是全副）数据库都应用这种排序算法，但它不是惟一的。如果您想理解更多信息，能够浏览这篇钻研论文，该论文探讨了数据库中常见排序算法的优缺点。

数组、树和哈希表

当初咱们理解了工夫复杂度和排序背地的想法，我必须通知你 3 个数据结构。这很重要，因为它们是 古代数据库的支柱 。我还将介绍 数据库索引 的概念。

少量

二维数组是最简略的数据结构。表能够看作是一个数组。例如：

这个二维数组是一个蕴含行和列的表：

• 每行代表一个主题
• 列形容主题的特色。
• 每列存储某种类型的数据（整数、字符串、日期……）。

尽管存储和可视化数据很棒，但当您须要寻找特定值时，它就很蹩脚了。

例如，如果您想查找在 UK 工作的所有人员，则 必须查看每一行以查找该行是否属于 UK。这将破费您 N 次操作（N 是行数），这还不错，但有没有更快的办法？这就是树木发挥作用的中央。

留神：大多数古代数据库都提供高级数组来无效地存储表，例如堆组织表或索引组织表。但它并没有扭转在一组列上疾速搜寻特定条件的问题。

树和数据库索引

二叉搜寻树是具备非凡性质的二叉树，每个节点中的键必须是：

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

让咱们看看它在视觉上意味着什么

这个想法

这棵树有 N=15 个元素。假如我正在寻找 208：

• 我从键为 136 的根开始。因为 136<208，我查看节点 136 的右子树。
• 398>208 所以，我看节点 398 的左子树
• 250>208 所以，我看节点 250 的左子树
• 200<208 所以，我查看节点 200 的右子树。然而 200 没有右子树，该值不存在（因为如果它的确存在，它将在 200 的右子树中）

当初假如我正在寻找 40

• 我从键为 136 的根开始。因为 136>40，我查看节点 136 的左子树。
• 80>40 所以，我看节点 80 的左子树
• 40=40，节点存在。我提取节点外行的 id（它不在图中）并查看给定行 id 的表。
• 晓得行 id 让我晓得数据在表中的准确地位，因而我能够立刻失去它。

最初，两次搜寻都让我损失了树内的层数。如果您仔细阅读无关合并排序的局部，您应该会看到有 log(N) 个级别。所以 搜寻的老本是 log(N)，还不错！

回到咱们的问题

然而这些货色十分形象，所以让咱们回到咱们的问题。设想一下代表上表中某人所在国家 / 地区的字符串，而不是一个愚昧的整数。假如您有一棵树，其中蕴含表的“国家”列：

• 如果你想晓得谁在英国工作
• 您查看树以获取代表英国的节点
• 在“英国节点”内，您将找到英国工人行的地位。

如果您间接应用数组，则此搜寻仅破费您 log(N) 次操作而不是 N 次操作。您方才设想的是一个 数据库索引。

您能够为任何一组列（一个字符串、一个整数、2 个字符串、一个整数和一个字符串、一个日期……）建设一个树索引，只有您有比拟键（即列组）的性能，所以您能够 在键之间 建设 程序（数据库中的任何根本类型都是这种状况）。

B+ 树索引

只管此树能够很好地获取特定值，然而当您须要获取 两个值之间的 多个元素 时，就会呈现一个大问题。这将破费 O(N)，因为您必须查看树中的每个节点并查看它是否在这两个值之间（例如，按程序遍历树）。此外，此操作对磁盘 I/O 不敌对，因为您必须读取残缺的树。咱们须要找到一种办法来无效地进行 范畴查问。为了解决这个问题，古代数据库应用了以前称为 B+Tree 的树的批改版本。在 B+ 树中：

• 只有最低节点（叶子）存储信息（关联表中行的地位）
• 其余节点只是在 搜寻过程中 路由 到正确的节点。

如您所见，有更多节点（多两倍）。实际上，您还有其余节点，即“决策节点”，它们将帮忙您找到正确的节点（存储相干表中行的地位）。然而搜寻复杂度依然在 O(log(N))（只有一个级别）。最大的不同是 最低节点链接到它们的后继节点。

应用此 B+Tree，如果您要查找 40 到 100 之间的值：

• 您只须要查找 40（如果 40 不存在，则为 40 之后的最靠近的值），就像您对前一棵树所做的那样。
• 而后应用指向继任者的间接链接收集 40 个继任者，直到达到 100 个。

假如您找到了 M 个后继树，并且树有 N 个节点。与前一棵树一样，搜寻特定节点的老本为 log(N)。然而，一旦你有了这个节点，你就能够在 M 个操作中取得 M 个后继者以及指向它们的后继者的链接。此搜寻仅破费 M + log(N)操作与前一棵树的 N 操作。此外，您不须要读取残缺的树（只需 M + log(N) 个节点），这意味着更少的磁盘使用量。如果 M 较低（如 200 行）而 N 较大（1 000 000 行），则差别很大。

然而有新的问题（再次！）。如果您在数据库中增加或删除一行（因而在关联的 B+Tree 索引中）：

• 您必须放弃 B+Tree 内节点之间的程序，否则您将无奈在凌乱中找到节点。
• 您必须在 B+Tree 中放弃尽可能低的级别数，否则 O(log(N)) 中的工夫复杂度将变为 O(N)。

换句话说，B+Tree 须要自排序和自均衡。值得庆幸的是，这能够通过智能删除和插入操作来实现。但这是有代价的：B+Tree 中的插入和删除都在 O(log(N)) 中。这就是为什么你们中的一些人据说 应用太多索引不是一个好主见的起因。实际上，您正在减慢 表中行的疾速插入 / 更新 / 删除，因为数据库须要应用每个索引的低廉 O(log(N)) 操作来更新表的索引。此外，增加索引意味着 事务管理器 的工作量更大（咱们将在文章开端看到这个管理器）。

留神：一位读者通知我，因为低级优化，B+Tree 须要齐全均衡。

哈希表

咱们最初一个重要的数据结构是哈希表。当您想疾速查找值时，它十分有用。此外，理解哈希表有助于咱们当前了解一种常见的数据库连贯操作，称为 哈希连贯 。这个数据结构也被数据库用来存储一些外部的货色（比方 锁表 或缓冲池，咱们稍后会看到这两个概念）

哈希表是一种数据结构，能够疾速找到带有键的元素。要构建哈希表，您须要定义：

• 元素 的要害
• 键的哈希函数 。键的计算哈希给出了元素的地位（称为 桶）。
• 比拟键的性能。找到正确的存储桶后，您必须应用此比拟在存储桶内找到您要查找的元素。

一个简略的例子

让咱们有一个直观的例子：

这个哈希表有 10 个桶。因为我很懒，我只画了 5 个桶，但我晓得你很聪慧，所以我让你设想其余 5 个。我应用的哈希函数是密钥的模 10。换句话说，我只保留元素键的最初一位来找到它的桶：

• 如果最初一位为 0，则元素最终在桶 0 中，
• 如果最初一位是 1，则元素最终在桶 1 中，
• 如果最初一位是 2，则元素最终在桶 2 中，
• …

我应用的比拟函数只是两个整数之间的相等。

假如您想要获取元素 78：

• 哈希表计算 78 的哈希码，即 8。
• 它在桶 8 中查找，它找到的第一个元素是 78。
• 它还给你元素 78
• 搜寻只须要 2 次操作（ 1 次用于计算哈希值，另一次用于查找桶内的元素）。

当初，假如您想要获取元素 59：

• 哈希表计算 59 的哈希码，即 9。
• 它在桶 9 中查找，它找到的第一个元素是 99。因为 99!=59，元素 99 不是正确的元素。
• 应用雷同的逻辑，它查看第二个元素 (9)、第三个 (79)、… 和最初一个 (29)。
• 该元素不存在。
• 搜寻须要 7 次操作。

一个好的哈希函数

如您所见，依据您要寻找的价值，老本是不一样的！

如果我当初用密钥的模 1 000 000 更改哈希函数（即取最初 6 位数字），第二次搜寻只需 1 次操作，因为桶 000059 中没有元素。真正的挑战是找到一个好的哈希函数将创立蕴含十分大量元素的桶。

在我的示例中，找到一个好的散列函数很容易。但这是一个简略的例子，当要害是：

• 一个字符串（例如一个人的姓氏）
• 2 个字符串（例如一个人的姓氏和名字）
• 2 个字符串和一个日期（例如一个人的姓氏、名字和出生日期）
• …

应用好的散列函数， 在散列表中的搜寻在 O(1)中。

数组与哈希表

为什么不应用数组？

哼，你问的很好。

• 哈希表能够 在内存中加载一半，而其余存储桶能够保留在磁盘上。
• 应用数组，您必须应用内存中的间断空间。如果您正在加载一个大表，那么 很难有足够的间断空间。
• 应用哈希表，您能够 抉择所需的键（例如国家和人的姓氏）。

无关更多信息，您能够浏览我对于 Java HashMap 的文章，它是一种高效的哈希表实现；您无需理解 Java 即可了解本文中的概念。

寰球概览

咱们刚刚看到了数据库中的根本组件。咱们当初须要退后一步来看看大局。

数据库是能够轻松拜访和批改的信息汇合。然而一堆简略的文件能够做同样的事件。事实上，像 SQLite 这样最简略的数据库无非就是一堆文件。然而 SQLite 是一组精心设计的文件，因为它容许您：

• 应用确保数据安全和连贯的事务
• 即便在解决数百万数据时也能疾速解决数据

更个别地，一个数据库能够看成下图：

在写这部分之前，我曾经浏览了多本书籍 / 论文，并且每个起源都有其代表数据库的形式。因而，不要过分关注我是如何组织这个数据库或如何命名流程的，因为我做出了一些抉择来适应本文的打算。重要的是不同的组件；总体思路是将 一个数据库划分为多个互相交互的组件。

外围组件：

• 过程管理器 ：许多数据库都有一个须要治理 的过程 / 线程池。此外，为了取得纳秒，一些古代数据库应用本人的线程而不是操作系统线程。
• 网络管理器：网络 I/O 是一个大问题，尤其是对于分布式数据库。这就是为什么有些数据库有本人的管理器的起因。
• 文件系统管理器 ： 磁盘 I/O 是数据库的第一个瓶颈。领有一个可能完满解决操作系统文件系统甚至替换它的管理器很重要。
• 内存管理器：为了防止磁盘 I/O 损失，须要大量内存。然而如果你解决大量的内存，你就须要一个高效的内存管理器。特地是当您同时应用内存进行许多查问时。
• 平安管理器：用于治理用户的身份验证和受权
• 客户端管理器：用于治理客户端连贯
• …

工具：

• 备份管理器：用于保留和复原数据库。
• 复原管理器 ：用于在解体后以 统一的状态 重新启动数据库
• 监控管理器：用于记录数据库的流动并提供监控数据库的工具
• 治理管理器：用于存储元数据（如表的名称和构造）并提供工具来治理数据库、模式、表空间……
• …

查问管理器：

• 查问解析器：查看查问是否无效
• 查问重写器：预优化查问
• 查问优化器：优化查问
• 查问执行 器：编译和执行查问

数据管理员：

• 事务管理器：处理事务
• 缓存管理器：在应用数据之前将数据放入内存，并在将数据写入磁盘之前将数据放入内存
• 数据拜访管理器：拜访磁盘上的数据

在本文的其余部分，我将重点介绍数据库如何通过以下过程治理 SQL 查问：

• 客户经理
• 查问管理器
• 数据管理器（我还将在这部分中包含复原管理器）

客户经理

客户经理是解决与客户沟通的局部。客户端能够是（Web）服务器或最终用户 / 最终应用程序。客户端管理器通过一组家喻户晓的 API 提供不同的形式来拜访数据库：JDBC、ODBC、OLE-DB …

它还能够提供专有的数据库拜访 API。

当您连贯到数据库时：

• 管理员首先查看您的 身份验证 （您的登录名和明码），而后查看您是否 有权 应用数据库。这些拜访权限由您的 DBA 设置。
• 而后，它会查看是否有过程（或线程）可用于治理您的查问。
• 它还查看数据库是否负载不重。
• 它能够稍等片刻以获取所需的资源。如果此期待超时，它将敞开连贯并给出可读的谬误音讯。
• 而后它将 您的查问发送到查问管理器 并解决您的查问
• 因为查询处理不是“全有或全无”的事件，一旦它从查问管理器获取数据，它就 会将 局部后果存储在缓冲区中并开始将 它们发送给您。
• 如果呈现问题，它会进行连贯，为您提供 可读的解释 并开释资源。

查问管理器

这部分是数据库的弱小之处 。在这部分，一个写得不好的查问被转换成一个 疾速 的可执行代码。而后执行代码并将后果返回给客户端管理器。这是一个多步骤操作：

• 首先 解析 查问以查看它是否无效
• 而后对其进行 重写 以删除无用的操作并增加一些预优化
• 而后对其 进行优化 以进步性能并转换为执行和数据拜访打算。
• 而后 编制打算
• 最初，它 被执行了

在这一部分中，我不会过多地议论最初两点，因为它们不太重要。

浏览完这部分后，如果您想更好地了解，我建议您浏览：

• 对于基于老本的优化的初步钻研论文（1979 年）：关系数据库管理系统中的拜访门路抉择。这篇文章只有 12 页，计算机科学的平均水平能够了解。
• 对于 DB2 9.X 如何优化查问的十分好的和深刻的介绍
• 一个对于 PostgreSQL 如何优化查问的很好的介绍。这是最容易取得的文档，因为它更多的是对于“让咱们看看 PostgreSQL 在这些状况下提供什么查问打算”而不是“让咱们看看 PostgreSQL 应用的算法”的演示。
• 对于优化的官网 SQLite 文档。它“容易”浏览，因为 SQLite 应用简略的规定。此外，它是惟一真正解释其工作原理的官网文档。
• 一个对于 SQL Server 2005 如何优化查问的很好的演示在这里
• 无关 Oracle 12c 中的优化的白皮书，请点击此处
• 来自“数据库系统概念”一书的作者的 2 门对于查问优化的实践课程，这里和这里。专一于磁盘 I/O 老本的良好浏览，但须要良好的 CS 程度。
• 另一门我感觉更容易上手的实践课程，但只关注连贯运算符和磁盘 I/O。

查问解析器

每个 SQL 语句都被发送到解析器，在那里查看语法是否正确。如果您在查问中出错，解析器将回绝该查问。例如，如果您写的是“SLECT …”而不是“SELECT …”，那么故事到此结束。

但这更深刻。它还查看关键字的应用程序是否正确。例如，SELECT 之前的 WHERE 将被回绝。

而后，剖析查问中的表和字段。解析器应用数据库的元数据来查看：

• 如果 表存在
• 如果表的 字段 存在
• 如果字段类型的 操作 是可能的（例如，您不能将整数与字符串进行比拟，则不能对整数应用 substring() 函数）

而后它会查看您是否 有权 读取（或写入）查问中的表。同样，这些对表的拜访权限是由您的 DBA 设置的。

在此解析期间，SQL 查问被转换为外部示意（通常是树）

如果一切正常，则外部示意将发送到查问重写器。

查问重写器

在这一步，咱们有一个查问的外部示意。重写器的指标是：

• 预优化查问
• 防止不必要的操作
• 帮忙优化器找到可能的最佳解决方案

重写器对查问执行一系列已知规定。如果查问合乎规定的模式，则利用该规定并重写查问。以下是（可选）规定的非详尽列表：

• 视图合并：如果您在查问中应用视图，则视图将应用视图的 SQL 代码进行转换。
• 子查问扁平化：子查问很难优化，因而重写器将尝试应用子查问批改查问以删除子查问。

例如

将被替换

• 删除不必要的运算符：例如，如果您应用 DISTINCT 而您有一个避免数据不惟一的 UNIQUE 束缚，则删除 DISTINCT 关键字。
• 冗余连贯打消：如果您有两次雷同的连贯条件，因为一个连贯条件暗藏在视图中，或者如果通过传递性存在无用的连贯，则将其删除。
• 恒定算术评估：如果您编写须要微积分的内容，则在重写期间计算一次。例如 WHERE AGE > 10+2 转换为 WHERE AGE > 12 并且 TODATE(“some date”) 转换为 datetime 格局的日期
• （高级）分区修剪：如果您应用分区表，重写器可能找到要应用的分区。
• （高级）物化视图重写：如果您的物化视图与查问中的谓词子集匹配，则重写器会查看视图是否是最新的并批改查问以应用物化视图而不是原始表。
• （高级）自定义规定：如果您有自定义规定来批改查问（如 Oracle 策略），那么重写器会执行这些规定
• （高级）Olap 转换：剖析 / 窗口函数、星形连贯、汇总 …… 也被转换（但我不确定它是由重写器还是优化器实现，因为这两个过程十分靠近，它必须依赖于数据库）。

而后，这个重写的查问被发送到查问优化器，乐趣开始了！

统计数据

在咱们理解数据库如何优化查问之前，咱们须要先谈谈 统计数据 ，因为 没有它们 ，数据库是愚昧的。如果您不通知数据库剖析本人的数据，它就不会这样做，并且会做出（十分）蹩脚的假如。

然而数据库须要什么样的信息呢？

我必须（简要地）谈谈数据库和操作系统是如何存储数据的。他们应用称为 页面或块 的 最小单位（默认为 4 或 8 KB）。这意味着，如果您只须要 1 KB，无论如何它都会破费您一页。如果页面占用 8 KB，那么您将节约 7 KB。

回到统计数据！当您要求数据库收集统计信息时，它会计算如下值：

• 表中的行数 / 页数

• 对于表中的每一列：

  • 不同的数据值
  • 数据值的长度（最小值、最大值、平均值）
  • 数据范畴信息（最小值、最大值、平均值）
• 无关表的索引的信息。

这些统计信息将帮忙优化器预计查问的 磁盘 I/O、CPU 和内存应用状况。

每列的统计信息十分重要。例如，如果表 PERSON 须要在 2 列上连贯：LAST_NAME、FIRST_NAME。通过统计数据，数据库晓得 FIRST_NAME 上只有 1 000 个不同的值，而 LAST_NAME 上只有 1 000 000 个不同的值。因而，数据库将连贯 LAST_NAME, FIRST_NAME 而不是 FIRST_NAME,LAST_NAME 上的数据，因为它产生的比拟较少，因为 LAST_NAME 不太可能雷同，所以大多数时候比拟的是 2（或 3）个第一个字符 LAST_NAME 就足够了。

但这些都是根本的统计数据。您能够要求数据库计算称为 直方图 的高级统计数据。直方图是对于列内值散布的统计信息。例如

• 最常见的值
• 分位数
• …

这些额定的统计数据将帮忙数据库找到更好的查问打算。特地是对于相等谓词（例如：WHERE AGE = 18）或范畴谓词（例如：WHERE AGE > 10 和 AGE <40），因为数据库将更好地理解这些谓词所波及的行数（留神：这个概念是选择性）。

统计信息存储在数据库的元数据中。例如，您能够查看（非分区）表的统计信息：

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

统计数据必须是最新 的。没有什么比数据库认为一个表只有 500 行而它有 1 000 000 行更蹩脚的了。统计数据的惟一毛病是 计算它们须要工夫。这就是为什么在大多数数据库中默认状况下不会主动计算它们的起因。数以百万计的数据很难计算出来。在这种状况下，您能够抉择仅计算根本统计信息或计算数据库样本的统计信息。

例如，当我在解决每个表中的数亿行的我的项目时，我抉择仅计算 10% 的统计信息，这导致了微小的工夫收益。对于这个故事，它被证实是一个蹩脚的决定，因为有时 Oracle 10G 为特定表的特定列抉择的 10% 与整体 100% 十分不同（这对于具备 100M 行的表来说不太可能产生）. 这个谬误的统计数据导致查问有时须要 8 小时而不是 30 秒；寻找根本原因的噩梦。这个例子显示了统计数据的重要性。

留神：当然，每个数据库都有更高级的统计信息。如果您想理解更多信息，请浏览数据库的文档。话虽如此，我试图理解统计数据的应用形式，我发现的最好的官网文档是来自 PostgreSQL 的文档。

查问优化器

所有古代数据库都应用基于 老本的优化（或CBO）来优化查问。这个想法是为每个操作设置一个老本，并通过应用最便宜的操作链来找到升高查问老本的最佳办法来取得后果。

为了了解老本优化器的工作原理，我认为最好有一个例子来“感触”这项工作背地的复杂性。在这一部分中，我将向您展现连贯 2 个表的 3 种罕用办法，咱们将很快看到，即便是简略的连贯查问也是优化的噩梦。在那之后，咱们将看到真正的优化器是如何实现这项工作的。

对于这些连贯，我将关注它们的工夫复杂度，但 数据库 优化器会计算 它们的CPU 老本、磁盘 I/O 老本和内存需要。工夫复杂度和 CPU 老本之间的区别在于，工夫老本十分近似（实用于像我这样的懒人）。对于 CPU 老本，我应该计算每个操作，例如加法、“if 语句”、乘法、迭代……此外：

• 每个高级代码操作都有特定数量的低级 CPU 操作。
• 无论您应用的是 Intel Core i7、Intel Pentium 4、AMD Opteron……，CPU 操作的老本都不雷同（就 CPU 周期而言）。换句话说，它取决于 CPU 架构。

应用工夫复杂度更容易（至多对我而言），有了它咱们依然能够失去 CBO 的概念。我有时会议论磁盘 I/O，因为它是一个重要的概念。请记住，瓶颈大部分工夫是磁盘 I/O 而不是 CPU 使用率。

索引

当咱们看到 B+Trees 时，咱们谈到了索引。请记住，这些 索引曾经排序。

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

此外，如果能够进步执行打算的老本，许多古代数据库能够仅为以后查问 动态创建长期索引。

拜访门路

在利用连贯运算符之前，您首先须要获取数据。以下是获取数据的办法。

留神：因为所有拜访门路的真正问题是磁盘 I/O，因而我不会过多探讨工夫复杂度。

全扫描

如果您已经浏览过执行打算，那么您肯定见过 残缺扫描 （或仅扫描）这个词。齐全扫描只是数据库齐全读取表或索引。 在磁盘 I/O 方面，表全扫描显然比索引全扫描更低廉。

范畴扫描

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

当然，您须要在字段 AGE 上有一个索引能力应用此索引范畴扫描。

咱们在第一局部曾经看到，范畴查问的工夫老本相似于 log(N) +M，其中 N 是该索引中的数据数，M 是对该范畴外行数的预计。因为统计信息，N 和 M 值都是已知的 （留神：M 是谓词 AGE >20 AND AGE<40 的选择性）。此外，对于范畴扫描，您不须要读取残缺索引，因而它 在磁盘 I/O 方面比残缺扫描更便宜。

独特的扫描

如果您只须要索引中的一个值，则能够应用 惟一扫描。

按行 ID 拜访

大多数状况下，如果数据库应用索引，则必须查找与索引关联的行。为此，它将应用按行 ID 拜访。

例如，如果您执行相似的操作

如果你有一个对于年龄列的人的索引，优化器将应用该索引来查找所有 28 岁的人，而后它会询问表中的关联行，因为索引只有对于年龄的信息并且你想晓得姓和名。

然而，如果当初你做相似的事件

PERSON 上的索引将用于与 TYPE_PERSON 连贯，但表 PERSON 不会通过行 id 拜访，因为您没有询问无关此表的信息。

尽管它对一些拜访很无效，但这个操作的真正问题是磁盘 I/O。如果您须要按行 ID 进行太多拜访，则数据库可能会抉择残缺扫描。

其余门路

我没有提供所有拜访门路。如果您想理解更多信息，能够浏览[Oracle 文档]。其余数据库的名称可能不同，但背地的概念是雷同的。

退出运营商

所以，咱们晓得如何获取咱们的数据，让咱们退出他们！

我将介绍 3 个常见的连贯运算符：Merge Join、Hash Join 和 Nested Loop Join。但在此之前，我须要引入新的词汇：外部关系 和内部关系。关系能够是：

• 一张桌子
• 一个索引
• 先前操作的两头后果（例如先前连贯的后果）

当您连贯两个关系时，连贯算法以不同的形式治理这两个关系。在本文的其余部分，我将假如：

• 外关系是左数据集
• 外部关系是正确的数据集

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

大多数时候，A JOIN B 的老本与 B JOIN A 的老本是不一样的。

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

注：N 和 M 是关系的基数。

嵌套循环连贯

嵌套循环连贯是最简略的一种。

这是想法：

• 对于内部关系中的每一行
• 您查看外部关系中的所有行以查看是否有匹配的行

这是一个伪代码：

因为是双迭代，所以 工夫复杂度为 O(N*M)

在磁盘 I/O 方面，对于内部关系中的 N 行中的每一行，外部循环须要从外部关系中读取 M 行。该算法须要从磁盘读取 N + N*M 行。然而，如果外部关系足够小，您能够将关系放入内存中，而后读取 M +N。通过这种批改，外部关系必须是最小的，因为它有更多的机会适宜内存。

就工夫复杂度而言，它没有区别，但就磁盘 I/O 而言，最好只读取一次这两种关系。

当然，外部关系能够用索引代替，这样对磁盘 I / O 会更好。

因为这个算法非常简单，所以如果外部关系太大而无奈放入内存，那么这里还有另一个对磁盘 I/O 更敌对的版本。这是想法：

• 而不是逐行读取两个关系，
• 你一束一束地浏览它们，并在内存中保留 2 束行（来自每个关系），
• 您比拟两束内的行并放弃匹配的行，
• 而后你从磁盘加载新的串并比拟它们
• 依此类推，直到没有要加载的束。

这是一个可能的算法：

应用此版本，工夫复杂度放弃不变，但磁盘拜访次数缩小：

• 在以前的版本中，该算法须要 N + N*M 次访问（每次拜访取得一行）。
• 在这个新版本中，磁盘拜访次数变为 number_of_bunches_for(outer)+ number_of_bunches_for(outer)* number_of_bunches_for(inner)。
• 如果减少束的大小，则会缩小磁盘拜访次数。

留神：每次磁盘拜访比以前的算法收集更多的数据，但这并不重要，因为它们是程序拜访（机械磁盘的真正问题是获取第一个数据的工夫）。

哈希连贯

散列连贯更简单，但在许多状况下比嵌套循环连贯老本更低。

哈希连贯的想法是：

• 1）从外部关系中获取所有元素
• 2）建设内存中的哈希表
• 3）一一获取外关系的所有元素
• 4）计算每个元素的 hash（用 hash 表的 hash 函数）找到内关系的关联桶
• 5）查找 bucket 中的元素和 outer table 的元素是否匹配

在工夫复杂度方面，我须要做一些假如来简化问题：

• 外部关系分为 X 个桶
• 散列函数为这两种关系简直平均地散布散列值。换句话说，桶大小雷同。
• 内部关系的元素与桶内所有元素之间的匹配会破费桶内元素的数量。

工夫复杂度为 (M/X) N + cost_to_create_hash_table(M) + cost_of_hash_functionN

如果 Hash 函数创立了足够多的小桶，那么 工夫复杂度是 O(M+N)

这是哈希连贯的另一个版本，它对内存更敌对，但对磁盘 I/O 更不敌对。这次：

• 1）您计算外部和内部关系的哈希表
• 2）而后你把它们放在磁盘上
• 3）而后你逐桶比拟 2 个关系（一个加载在内存中，另一个逐行读取）

合并退出

合并连贯是惟一产生排序后果的连贯。

留神：在这个简化的合并连贯中，没有内表或表面；他们都表演同样的角色。然而理论的实现会有所不同，例如，在解决反复项时。

合并连贯能够分为两个步骤：

1. （可选）排序连贯操作：两个输出都按连贯键排序。
2. 合并连贯操作：将排序后的输出合并在一起。

品种

咱们曾经谈到了归并排序，在这种状况下，归并排序是一种好的算法（但如果内存不是问题，则不是最好的）。

但有时数据集曾经排序，例如：

• 如果表是本机排序的，例如连贯条件上的索引组织表
• 如果关系是连贯条件上的索引
• 如果此连贯利用于在查问过程中已排序的两头后果

合并退出

这部分和咱们看到的归并排序的归并操作十分类似。然而这一次，咱们不是从两个关系中抉择每个元素，而是只从两个关系中抉择相等的元素。这是想法：

• 1）您比拟两个关系中的两个以后元素（第一次以后 = 第一个）
• 2）如果它们相等，则将两个元素都放入后果中，而后转到下一个元素以取得两个关系
• 3）如果不是，则转到与最低元素的关系的下一个元素（因为下一个元素可能匹配）
• 4) 并反复 1,2,3 直到达到其中一个关系的最初一个元素。

这是无效的，因为这两个关系都是排序的，因而您不须要在这些关系中“返回”。

该算法是一个简化版本，因为它不解决雷同数据在两个数组中屡次呈现（即屡次匹配）的状况。对于这种状况，实在版本“只是”更简单；这就是我抉择简化版本的起因。

如果两个关系都已排序，则 工夫复杂度为 O(N+M)

如果两个关系都须要排序，那么工夫复杂度就是对两个关系进行排序的老本：O(N*Log(N) + M*Log(M))

对于 CS 极客，这里有一个可能的算法来解决多个匹配（留神：我不是 100% 确定我的算法）：

哪一个是最好的？

如果有最好的连贯类型，就不会有多种类型。这个问题十分艰难，因为许多因素都在起作用，例如：

• 闲暇内存量：没有足够的内存你能够辞别弱小的哈希连贯（至多是残缺的内存哈希连贯）
• 2 个数据集 的大小。例如，如果您有一个十分小的表，嵌套循环连贯将比散列连贯快，因为散列连贯创立散列的老本很高。如果您有 2 个十分大的表，则嵌套循环连贯将占用大量 CPU。
• 索引 的存在。_ 应用 2 个 B+Tree 索引，理智的抉择仿佛是合并连贯
• 如果 须要对后果进行排序：即便您正在应用未排序的数据集，您也可能心愿应用代价昂扬的合并连贯（带有排序），因为最初后果将被排序并且您将可能链接另一个合并连贯的后果（或者可能是因为查问隐式 / 显式地要求应用 ORDER BY/GROUP BY/DISTINCT 操作的排序后果）
• 如果 关系曾经排序：在这种状况下，合并连贯是最佳候选
• 您正在执行的连贯类型：它是 等值连贯 （即：tableA.col1 = tableB.col2）吗？它是 内连贯 、 外连贯、笛卡尔 积还是 自连贯？某些联接在某些状况下无奈工作。
• 数据 散布。如果连贯条件上的数据有 偏差（例如，您要以姓氏连贯人，但许多人的姓氏雷同），则应用哈希连贯将是一场劫难，因为哈希函数会创立散布不均的存储桶。
• 如果您心愿连贯由 多个线程 / 过程执行

简化示例

咱们刚刚看到了 3 种类型的连贯操作。

当初假如咱们须要连贯 5 个表能力看到一个人的残缺视图。一个人能够有：

• 多部手机
• 多个邮件
• 多个地址
• 多个 BANK_ACCOUNTS

换句话说，咱们须要以下查问的疾速答案：

作为查问优化器，我必须找到解决数据的最佳形式。然而有 2 个问题：

• 我应该为每个联接应用哪种联接？

我有 3 个可能的连贯（哈希连贯、合并连贯、嵌套连贯），能够应用 0,1 或 2 个索引（更不用说有不同类型的索引）。

• 我应该抉择什么程序来计算连贯？

例如，下图显示了 4 个表上仅 3 个连贯的不同可能打算

所以这是我的可能性：

• 1）我应用蛮力办法

应用数据库统计数据，我 计算每个可能的打算的老本，并保留最好的一个。然而有很多可能性。对于给定的连贯程序，每个连贯都有 3 种可能性：HashJoin、MergeJoin、NestedJoin。因而，对于给定的连贯程序，有 3 4 种可能性。连贯排序是二叉树上的置换问题，有 (24)!/(4+1)! 可能的订单。对于这个非常简单的问题，我最终失去 3 4 (2*4)!/(4+1)! 可能性。

在非极客术语中，这意味着 27 216 个可能的打算。如果我当初增加合并连贯采纳 0,1 或 2 个 B+Tree 索引的可能性，则可能的计划数将变为 210 000。我是否遗记提及此查问非常简单？

• 2）我哭着辞掉了这份工作

这很迷人，但你不会失去你的后果，我须要钱来领取账单。

• 3）我只尝试了几个打算，并抉择了老本最低的一个。

因为我不是超人，我无奈计算每个打算的老本。相同，我能够 任意抉择所有可能打算的子集，计算它们的老本并为您提供该子集的最佳打算。

• 4）我利用智能 规定来缩小可能的打算数量。

有两种类型的规定：

我能够应用“逻辑”规定来打消无用的可能性，但它们不会过滤很多可能的打算。例如：“嵌套循环连贯的外部关系必须是最小的数据集”

我承受没有找到最佳解决方案并利用更踊跃的规定来缩小很多可能性。例如“如果关系很小，请应用嵌套循环连贯，并且永远不要应用合并连贯或哈希连贯”

在这个简略的例子中，我失去了很多可能性。但 真正的查问能够有其余关系运算符 ，如 OUTER JOIN、CROSS JOIN、GROUP BY、ORDER BY、PROJECTION、UNION、INTERSECT、DISTINCT …… 这意味着更多的可能性。

那么，数据库是如何做到的呢？

动静布局、贪婪算法和启发式

关系数据库尝试了我方才所说的多种办法。优化器的真正工作是在无限的工夫内找到一个好的解决方案。

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

对于小型查问，能够应用蛮力办法。然而有一种办法能够防止不必要的计算，这样即便是中等查问也能够应用蛮力办法。这称为动静布局。

动静布局

这两个词背地的想法是许多执行打算十分类似。如果您查看以下打算：

它们共享雷同的（A JOIN B）子树。因而，咱们无需在每个打算中计算此子树的老本，而是计算一次，保留计算的老本并在再次看到此子树时重用它。更正式地说，咱们面临着一个重叠的问题。为了防止对局部后果进行额定计算，咱们应用了记忆。

应用这种技术，而不是 (2*N)!/(N+1)! 工夫复杂度，咱们“只是”有 3 N。在咱们之前的 4 个连贯示例中，这意味着从 336 排序传递到 81。如果您 应用 8 个连贯（不大）进行更大的查问，这意味着从 57 657 600 传递到 6561。

对于 CS 极客，这是我在我曾经给你的正式课程中找到的算法。我不会解释这个算法，所以只有当你曾经晓得动静编程或者你对算法很相熟时才浏览它（你曾经被正告过！）：

对于更大的查问，您依然能够应用动静编程办法，但应用额定的规定（或 启发式）来打消可能性：

• 如果咱们只剖析某种类型的打算（例如：左深树），咱们最终会失去 n*2 n 而不是 3 n

• 如果咱们增加逻辑规定来防止某些模式的打算（例如“如果将表作为给定谓词的索引，则不要尝试在表上进行合并连贯，而只在索引上尝试”），它将缩小可能性的数量，而无需挫伤到最好的解决方案。
• 如果咱们在流程上增加规定（例如“在所有其余关系操作之前执行连贯操作”），它也会缩小很多可能性。
• …

贪婪算法

然而对于一个十分大的查问或有一个十分快的答案（但不是一个十分快的查问），应用另一种类型的算法，贪婪算法。

这个想法是遵循规定（或 启发式）以增量形式构建查问打算。应用此规定，贪婪算法一步一步地找到问题的最佳解决方案。该算法以一个 JOIN 开始查问打算。而后，在每一步，算法应用雷同的规定向查问打算增加一个新的 JOIN。

让咱们举一个简略的例子。假如咱们有一个在 5 个表（A、B、C、D 和 E）上具备 4 个连贯的查问。为了简化问题，咱们只是将嵌套连贯作为可能的连贯。让咱们应用规定“应用老本最低的连贯”

• 咱们任意从 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。而后咱们放弃老本最低的打算。

顺便说一句，这个算法有一个名字：它叫做[最近邻算法。

我不会具体介绍，然而通过良好的建模和 N*log(N) 中的排序，这个问题能够 [很容易地解决。 对于残缺的动静编程版本 ，该算法的 老本在 O(N*log(N)) 与 O(3 N ) 之间。如果您有一个蕴含 20 个连贯的大查问，这意味着 26 对 3 486 784 401，差异很大！

这个算法的问题在于，如果咱们保留这个连贯并增加一个新连贯，咱们假如在 2 个表之间找到最佳连贯将为咱们提供最佳老本。但：

• 即便 A JOIN B 给出了 A、B 和 C 之间的最佳老本
• (A JOIN C) JOIN B 可能比 (A JOIN B) JOIN C 给出更好的后果。

为了改善后果，您能够应用不同的规定运行多个贪婪算法并放弃最佳打算。

其余算法

[如果您曾经厌倦了算法，请跳到下一部分，我要说的对于本文的其余部分并不重要]

寻找最佳打算的问题是许多 CS 钻研人员的沉闷研究课题。他们常常尝试为更准确的问题 / 模式找到更好的解决方案。例如，

• 如果查问是星型连贯（它是某种类型的多连贯查问），某些数据库将应用特定算法。
• 如果查问是并行查问，一些数据库会应用特定的算法
• …

还钻研了其余算法来代替大型查问的动静编程。贪婪算法属于更大的家族，称为 启发式算法。贪婪算法遵循规定（或启发式），保留它在上一步找到的解决方案，并“附加”它以找到以后步骤的解决方案。一些算法遵循规定并逐渐利用它，但并不总是放弃上一步中找到的最佳解决方案。它们被称为启发式算法。

例如，遗传算法 遵循一个规定，但通常不会保留最初一步的最佳解决方案：

• 一个解决方案代表一个可能的残缺查问打算
• 每一步都保留了 P 个解决方案（即打算），而不是一个解决方案（即打算）。
• 0) P 个查问打算是随机创立的
• 1) 只保留老本最好的打算
• 2）这些最好的打算混合起来产生 P 新闻打算
• 3）局部 P 新计划随机批改
• 4）步骤 1、2、3 反复 T 次
• 5) 而后你保留上一个循环的 P 打算中的最佳打算。

你做的循环越多，打算就会越好。

是魔法吗？不，这是自然法则：适者生存！

仅供参考，遗传算法是在 [PostgreSQL] 中实现的，但我无奈找到它们是否默认应用。

数据库中还应用了其余启发式算法，例如模拟退火、迭代改良、两阶段优化……但我不晓得它们目前是用于企业数据库还是仅用于钻研数据库。

无关更多信息，您能够浏览以下钻研文章，其中介绍了更多可能的算法：Review of Algorithms for the Join Ordering Problem in Database Query Optimization

真正的优化器

【你能够跳到下一部分，我要说什么不重要】

然而，所有这些废话都是十分实践的。因为我是开发人员而不是钻研人员，所以我喜爱 具体的例子。

让咱们看看 [SQLite 优化器] 是如何工作的。这是一个轻量级数据库，因而它应用基于贪婪算法的简略优化和额定规定来限度可能性的数量：

• SQLite 抉择永远不会在 CROSS JOIN 运算符中从新排序表
• 连贯被实现为嵌套连贯
• 外连贯总是依照它们呈现的程序进行评估
• …
• 在 3.8.0 版本之前，SQLite 在搜寻最佳查问打算时应用“最近邻”贪婪算法

等一下……咱们曾经看过这个算法了！如许偶合！

• 从 3.8.0 版本（2015 年公布）开始，SQLite 在搜寻最佳查问打算时应用“”贪婪算法

让咱们看看另一个优化器是如何实现他的工作的。IBM DB2 就像所有的企业数据库一样，但我将专一于这个，因为它是我在切换到大数据之前真正应用的最初一个。

咱们会理解到 DB2 优化器容许您应用 7 种不同级别的优化：

• 对连贯应用贪婪算法

  • 0 – 最小优化，应用索引扫描和嵌套循环连贯并防止一些查问重写
  • 1 – 低优化
  • 2 – 全面优化

• 对连贯应用动静编程

  • 3 – 适度优化和粗略近似
  • 5 – 全面优化，应用所有具备启发式的技术
  • 7 – 相似于 5 的齐全优化，没有启发式
  • 9 – 最大优化不遗余力 / 费用 思考所有可能的连贯订单，包含笛卡尔积

咱们能够看到DB2 应用了贪婪算法和动静编程。当然，他们不共享他们应用的启发式办法，因为查问优化器是数据库的次要性能。

仅供参考，默认级别为 5。默认状况下，优化器应用以下个性：

• 应用所有可用的统计信息，包含频繁值和分位数统计信息。
• 利用所有查问重写规定（包含具体化查问表路由），但仅在极少数状况下实用的计算密集型规定除外。

• 应用动静编程连贯枚举

  ，具备：

  • 限度应用复合外部关系
  • 对波及查找表的星型模式应用笛卡尔积的限度
• 思考了宽泛的拜访办法，包含列表预取（留神：将看到是什么意思）、索引 ANDing（留神：与索引的非凡操作）和物化查问表路由。

默认状况下，DB2 对连贯排序应用受启发式限度的动静编程。

其余条件（GROUP BY、DISTINCT…）由简略的规定解决。

查问打算缓存

因为创立打算须要工夫，因而大多数数据库将打算存储到 查问打算缓存 中，以防止对同一查问打算进行无用的从新计算。这是一个很大的话题，因为数据库须要晓得何时更新过期的打算。这个想法是设置一个阈值，如果一个表的统计数据曾经超过这个阈值，那么波及这个表的查问打算就会从缓存中革除。

查问执行器

在这个阶段，咱们有一个优化的执行打算。这个打算被编译成可执行代码。而后，如果有足够的资源（内存、CPU），则由查问执行器执行。打算中的操作符（JOIN、SORT BY …）能够按程序或并行形式执行；这取决于执行人。为了获取和写入其数据，查问执行器与数据管理器交互，这是本文的下一部分。

数据管理员

在这一步，查问管理器正在执行查问并须要来自表和索引的数据。它要求数据管理器获取数据，但有两个问题：

• 关系数据库应用事务模型。因而，您无奈随时获取任何数据，因为其他人可能同时应用 / 批改数据。
• 数据检索是数据库中最慢的操作，因而数据管理器须要足够智能以获取数据并将数据保留在内存缓冲区中。

在这一部分中，咱们将看到关系数据库如何解决这两个问题。我不会议论数据管理器获取数据的形式，因为它不是最重要的（这篇文章曾经够长了！）。

缓存管理器

正如我曾经说过的，数据库的次要瓶颈是磁盘 I/O。为了进步性能，古代数据库应用缓存管理器。

查问执行器不是间接从文件系统获取数据，而是向缓存管理器申请数据。缓存管理器有一个称为 缓冲池 的内存缓存。从内存中获取数据极大地减速了数据库。很难给出一个数量级，因为它取决于您须要执行的操作：

• 程序拜访（例如：全扫描）与随机拜访（例如：按行 ID 拜访），
• 读与写

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

• 7.2k/10k/15k 转硬盘
• 固态硬盘
• RAID 1/5/…

但我想说memory 比 disk 快 100 到 100k 倍。

然而，这会导致另一个问题（与数据库一样……）。缓存管理器须要在查问执行器应用它们之前获取内存中的数据；否则查问管理器必须期待来自慢速磁盘的数据。

预取

这个问题称为预取。查问执行器晓得它须要的数据，因为它晓得查问的残缺流程，并且晓得磁盘上的数据和统计信息。这是想法：

• 当查问执行器正在解决它的第一批数据时
• 它要求缓存管理器预加载第二组数据
• 当它开始解决第二组数据时
• 它要求 CM 预加载第三组，并告诉 CM 能够从缓存中革除第一组。
• …

CM 将所有这些数据存储在其缓冲池中。为了晓得是否依然须要数据，缓存管理器增加了无关缓存数据的额定信息（称为 锁存器）。

有时查问执行器不晓得它须要什么数据，并且一些数据库不提供此性能。相同，他们应用揣测预取（例如：如果查问执行器申请数据 1、3、5，它可能会在不久的未来申请 7、9、11）或程序预取（在这种状况下，CM 只是从磁盘加载询问后的下一个间断数据）。

为了监控预取的工作状况，古代数据库提供了一个称为 缓冲区 / 缓存命中率 的指标。命中率显示在缓冲区高速缓存中找到申请数据而不须要磁盘拜访的频率。

然而，缓冲区是 无限 的内存量。因而，它须要删除一些数据能力加载新数据。加载和革除缓存在磁盘和网络 I/O 方面是有代价的。如果您有一个常常执行的查问，那么始终加载而后革除此查问应用的数据将不会无效。为了解决这个问题，古代数据库应用缓冲区替换策略。

缓冲替换策略

大多数古代数据库（至多 SQL Server、MySQL、Oracle 和 DB2）都应用 LRU 算法。

LRU

LRU代表Least Recently U sed。_ 该算法背地的想法是将最近应用过的数据保留在缓存中，因而更有可能再次应用。

这是一个视觉示例：

为了便于了解，我假如缓冲区中的数据没有被闩锁锁定（因而能够被删除）。在这个简略的示例中，缓冲区能够存储 3 个元素：

• 1：缓存管理器应用数据 1 并将数据放入空缓冲区
• 2：CM 应用数据 4，将数据放入半载缓冲区
• 3：CM 应用数据 3，将数据放入半载缓冲区
• 4：CM 应用数据 9. 缓冲区已满，因而 数据 1 被删除 ，因为它是最近应用的最初一个数据。数据 9 被增加到缓冲区中
• 5：CM 应用数据 4。数据 4 曾经在缓冲区中，因而它再次成为第一个最近应用的数据。
• 6：CM 应用数据 1。缓冲区已满，因而 数据 9 被删除 ，因为它是最近应用的最初一个数据。数据 1 被增加到缓冲区中
• …

该算法运行良好，但存在一些限度。如果对大表进行全扫描怎么办？换句话说，当表 / 索引的大小大于缓冲区的大小时会产生什么？应用此算法将删除缓存中所有先前的值，而来自全扫描的数据可能只应用一次。

改良

为了避免这种状况产生，一些数据库增加了特定的规定

“对于十分大的表，数据库通常应用间接门路读取，间接加载块 […]，以防止填充缓冲区缓存。对于中等大小的表，数据库能够应用间接读取或缓存读取。如果它决定应用缓存读取，那么数据库会将块放在 LRU 列表的开端，以避免扫描无效地革除缓冲区缓存。”

还有其余可能性，例如应用称为 LRU-K 的 LRU 的高级版本。例如 SQL Server 应用 LRU-K 示意 K =2。

这个算法背地的想法是思考到更多的历史。应用简略的 LRU（对于 K=1 也是 LRU-K），该算法仅思考上次应用数据的工夫。应用 LRU-K：

• 它思考了 上次应用数据的 K 次。
• 对数据的应用次数赋予 权重
• 如果将一堆新数据加载到缓存中，则不会删除旧但常常应用的数据（因为它们的权重更高）。
• 然而如果不再应用旧数据，该算法就无奈将旧数据保留在缓存中。
• 因而，如果不应用数据，权重会 随着工夫的推移而升高。

权重的计算成本很高，这就是 SQL Server 只应用 K=2 的起因。对于可承受的开销，该值体现良好。

其余算法

当然还有其余算法来治理缓存，比方

• 2Q（相似 LRU-K 的算法）
• CLOCK（相似 LRU-K 的算法）
• MRU（最近应用，应用与 LRU 雷同的逻辑，但有另一个规定）
• LRFU（最近起码和常常应用）
• …

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

写缓冲区

我只探讨了在应用它们之前加载数据的读取缓冲区。然而在数据库中，您也有写入缓冲区，用于存储数据并将它们成批刷新到磁盘上，而不是一个接一个地写入数据并产生许多单个磁盘拜访。

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

事务管理器

最初但同样重要的是，这部分是对于事务管理器的。咱们将看到这个过程如何确保每个查问在其本人的事务中执行。但在此之前，咱们须要理解 ACID 事务的概念。

我吃酸了

ACID 事务是一个确保 4 件事 的工作单元：

• 原子性 ：交易是“全有或全无”，即便它继续 10 小时。如果事务解体，状态会回到事务之前（事务 回滚）。
• 隔离：如果 2 个事务 A 和 B 同时运行，事务 A 和 B 的后果必须雷同，无论 A 在事务 B 之前 / 之后 / 期间实现。
• 长久 性：一旦事务 提交（即胜利完结），无论产生什么（解体或谬误），数据都保留在数据库中。
• 一致性：只有无效数据（在关系束缚和性能束缚方面）被写入数据库。一致性与原子性和隔离性无关。

在同一事务中，您能够运行多个 SQL 查问来读取、创立、更新和删除数据。当两个事务应用雷同的数据时，凌乱就开始了。典型的例子是从账户 A 到账户 B 的转账。假如您有 2 笔交易：

• 交易 1 从账户 A 中取出 100 美元并将其提供给账户 B
• 交易 2 从账户 A 中取出 50 美元并将其提供给账户 B

如果咱们回到 ACID 属性：

• 原子性 确保无论在 T1 期间产生什么（服务器解体、网络故障……），您都不会陷入 100 美元从 A 提取而没有给 B 的状况（这种状况是不统一的状态）.
• Isolation确保如果 T1 和 T2 同时产生，最终 A 将取得 150 美元，B 将取得 150 美元，而不是，例如，A 取得 150 美元，B 仅取得 50 美元，因为 T2 已局部打消了这些动作 T1 的状态（这种状况也是不统一的状态）。
• 长久 性确保如果数据库在 T1 提交后立刻解体，T1 不会隐没。
• 一致性 确保零碎中不会创立或销毁任何货币。

[你能够跳到下一部分，我要说的对于文章的其余部分并不重要]

许多古代数据库不应用纯隔离作为默认行为，因为它会带来微小的性能开销。SQL 标准定义了 4 个隔离级别：

• 可序列化（SQLite 中的默认行为）：最高级别的隔离。同时产生的两个事务是 100% 隔离的。每笔交易都有本人的“世界”。
• 可反复读取（MySQL 中的默认行为）：每个事务都有本人的“世界”，除了一种状况。如果一个事务胜利完结并增加了新数据，这些数据将在其余仍在运行的事务中可见。然而，如果 A 批改数据并胜利完结，则该批改将不会在仍在运行的事务中可见。因而，事务之间的这种隔离中断仅与新数据无关，与现有数据无关。

例如，如果事务 A 执行“SELECT count(1) from TABLE_X”，而后事务 B 在 TABLE_X 中增加并提交新数据，如果事务 A 再次执行 count(1)，则该值将不是雷同的。

这称为 幻读。

• 已提交读取（Oracle、PostgreSQL 和 SQL Server 中的默认行为）：这是可反复读取 + 新的隔离中断。如果事务 A 读取数据 D，而后该数据被事务 B 批改（或删除）并提交，如果 A 再次读取数据 D，它将看到 B 对数据所做的批改（或删除）。

这称为 不可反复读取。

• Read uncommitted：最低级别的隔离。这是一个读取提交 + 一个新的隔离冲破。如果事务 A 读取数据 D，而后该数据 D 被事务 B（未提交且仍在运行）批改，如果 A 再次读取数据 D，它将看到批改后的值。如果事务 B 回滚，那么 A 第二次读取的数据 D 没有任何意义，因为它已被从未产生过的事务 B 批改（因为它已回滚）。

这称为 脏读。

大多数数据库都增加了本人的自定义隔离级别（如 PostgreSQL、Oracle 和 SQL Server 应用的快照隔离）。此外，大多数数据库并未实现 SQL 标准的所有级别（尤其是未提交读级别）。

用户 / 开发人员能够在连贯开始时笼罩默认的隔离级别（这是增加的非常简单的代码行）。

并发管制

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

• 如果所有事务都只是读取数据，它们能够同时工作而无需批改另一个事务的行为。
• 如果（至多）其中一个事务正在批改其余事务读取的数据，则数据库须要找到一种办法来对其余事务暗藏此批改。此外，它还须要确保这个批改不会被另一个没有看到批改数据的事务擦除。

这个问题叫做 并发管制。

解决这个问题最简略的办法是一一（即程序）运行每个事务。但这基本不可扩大，并且只有一个内核在多处理器 / 内核服务器上工作，效率不高……

解决此问题的现实办法是，每次创立或勾销事务时：

• 监控所有交易的所有操作
• 查看 2 个（或更多）事务的局部是否因为它们正在读取 / 批改雷同的数据而发生冲突。
• 从新排序抵触事务中的操作以缩小抵触局部的大小
• 以特定程序执行抵触局部（当非抵触事务仍在并发运行时）。
• 思考到能够勾销交易。

更正式地说，这是一个具备抵触时间表的调度问题。更具体地说，这是一个十分艰难且占用 CPU 资源的优化问题。企业数据库不能期待数小时能力为每个新事务事件找到最佳时间表。因而，他们应用不太现实的办法，导致在抵触事务之间节约更多工夫。

锁管理器

为了解决这个问题，大多数数据库都应用 锁和 / 或 数据版本控制。因为这是一个很大的话题，我将专一于锁定局部，而后我将谈谈数据版本控制。

乐观锁定

锁定背地的想法是：

• 如果交易须要数据，
• 它锁定数据
• 如果另一笔交易也须要这些数据，
• 它必须等到第一个事务开释数据。

这称为 排他锁。

然而对只须要读取数据的事务应用排他锁是十分低廉的，因为 它会迫使只想读取雷同数据的其余事务期待 。这就是为什么还有另一种锁， 共享锁 的起因。

应用共享锁：

• 如果一个事务只须要读取一个数据 A，
• 它“共享锁定”数据并读取数据
• 如果第二个事务也只须要读取数据 A，
• 它“共享锁定”数据并读取数据
• 如果第三个事务须要批改数据 A，
• 它“排他锁”数据，但它必须等到其余 2 个事务开释它们的共享锁能力将其排他锁利用于数据 A。

尽管如此，如果将数据作为排他锁，则只须要读取数据的事务将不得不期待排他锁完结能力在数据上搁置共享锁。

锁管理器是提供和开释锁的过程。在外部，它将锁存储在哈希表中（其中键是要锁定的数据）并晓得每个数据：

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

僵局

然而锁的应用会导致两个事务永远期待一个数据的状况：

在这个图中：

• 事务 A 对 data1 有排他锁，正在期待获取 data2
• 事务 B 对 data2 有排他锁，正在期待获取 data1

这称为 死锁。

在死锁期间，锁管理器抉择勾销（回滚）哪个事务以打消死锁。这个决定并不容易：

• 杀死批改数据量起码的事务是否更好（因而这将产生最便宜的回滚）？
• 因为另一个事务的用户期待的工夫更长，所以杀死年龄最小的事务会更好吗？
• 杀死须要更少工夫实现的事务（并防止可能的饥饿）是否更好？
• 在回滚的状况下，有多少事务会受到此回滚的影响？

然而在做出这个抉择之前，它须要查看是否存在死锁。

哈希表能够看作是一个图形（如后面的图）。如果图中存在循环，则存在死锁。因为查看循环的老本很高（因为所有锁的图都很大），所以常常应用一种更简略的办法：应用timeout。如果在此超时工夫内没有给出锁，则事务进入死锁状态。

锁管理器还能够在提供锁之前查看该锁是否会造成死锁。然而再次完满地实现它在计算上是低廉的。因而，这些事后查看往往是一套根本规定。

两相锁定

确保纯隔离的 最简略办法 是在事务开始时获取锁并在事务完结时开释锁。这意味着事务在开始之前必须期待它的所有锁，并且事务持有的锁在事务完结时被开释。它能够工作，但 会节约大量工夫 来期待所有锁。

一种更快的办法是 两阶段锁定协定（由 DB2 和 SQL Server 应用），其中一个事务被分为两个阶段：

• 事务能够获取锁但不能开释任何锁的 增长阶段。
• 事务能够开释锁的 膨胀阶段（在它曾经解决并且不会再次解决的数据上），但无奈取得新锁。

这两条简略规定背地的想法是：

• 开释不再应用的锁以缩小期待这些锁的其余事务的等待时间
• 以避免事务在事务开始后批改数据并因而与事务获取的第一个数据不统一的状况。

该协定运行良好，除非批改数据并开释关联锁的事务被勾销（回滚）。您最终可能会遇到另一个事务读取批改后的值而该值将被回滚的状况。为防止此问题，必须在事务完结时开释所有排他锁。

几句话

当然，真正的数据库应用更简单的零碎，波及更多类型的锁（如意向锁）和更多粒度（行、页、分区、表、表空间上的锁），但这个想法依然是雷同的。

我只介绍了纯基于锁的办法。数据版本控制是解决此问题的另一种办法。

版本控制背地的想法是：

• 每个事务能够同时批改雷同的数据
• 每个事务都有本人的数据正本（或版本）
• 如果 2 个事务批改了雷同的数据，则只承受一个批改，另一个将被回绝，并且关联的事务将被回滚（并且可能从新运行）。

它进步了性能，因为：

• 读取器事务不会阻止写入器事务
• 写入器事务不会阻止读取器事务
• “胖而慢”的锁管理器没有开销

所有都比锁好，除非两个事务写入雷同的数据。此外，您很快就会失去微小的磁盘空间开销。

数据版本控制和锁定是两种不同的愿景：乐观锁定与乐观锁定。它们都有长处和毛病；这实际上取决于用例（更多读取与更多写入）。对于数据版本控制的演示，我举荐这个对于 PostgreSQL 如何实现多版本并发管制的十分好的演示。

一些数据库，如 DB2（直到 DB2 9.7）和 SQL Server（快照隔离除外）只应用锁。其余如 PostgreSQL、MySQL 和 Oracle 应用波及锁和数据版本控制的混合办法。我不晓得仅应用数据版本控制的数据库（如果您晓得基于纯数据版本控制的数据库，请随时通知我）。

[更新 08/20/2015] 一位读者通知我：

Firebird 和 Interbase 应用没有记录锁定的版本控制。
版本控制对索引有一个乏味的影响：有时惟一索引蕴含反复项，索引的条目可能比表的行多，等等。

如果您浏览了无关不同隔离级别的局部，则当您减少隔离级别时，您会减少锁的数量，因而会节约事务期待其锁的工夫。这就是为什么大多数数据库默认不应用最高隔离级别（Serializable）的起因。

日志管理器

咱们曾经看到，为了进步性能，数据库将数据存储在内存缓冲区中。然而，如果在提交事务时服务器解体了，那么在解体期间您将失落仍在内存中的数据，这会毁坏事务的持久性。

您能够将所有内容都写入磁盘，但如果服务器解体，您最终会在磁盘上写入一半的数据，这会毁坏事务的原子性。

事务写入的任何批改都必须吊销或实现。

要解决这个问题，有两种办法：

• 影子正本 / 页面：每个事务都创立本人的数据库正本（或只是数据库的一部分）并在此正本上工作。如果呈现谬误，正本将被删除。如果胜利，数据库会立刻应用文件系统技巧从正本中切换数据，而后删除“旧”数据。
• 事务日志：事务日志是一个存储空间。在每次写入磁盘之前，数据库都会在事务日志中写入信息，以便在事务解体 / 勾销的状况下，数据库晓得如何删除（或实现）未实现的事务。

沃尔

当在波及许多事务的大型数据库上应用时，卷影正本 / 页面会产生微小的磁盘开销。这就是古代数据库应用 事务日志 的起因。事务日志必须存储在 稳固的存储器 上。我不会深刻探讨存储技术，但必须应用（至多）RAID 磁盘来避免磁盘故障。

WAL 协定是一组 3 条规定：

• 1）对数据库的每一次批改都会产生一条日志记录，在数据写入磁盘之前，必须将日志记录写入事务日志。
• 2) 日志记录必须按程序写入；产生在日志记录 B 之前的日志记录 A 必须写在 B 之前
• 3) 提交事务时，必须在事务胜利完结前将提交程序写入事务日志。

这项工作由日志管理器实现。一种简略的查看形式是，在缓存管理器和数据拜访管理器（将数据写入磁盘）之间，日志管理器在事务日志上写入每个更新 / 删除 / 创立 / 提交 / 回滚，而后再将它们写入磁盘。容易，对吧？

谬误的答案！经验了这么多，你应该晓得，与数据库相干的所有都受到“数据库效应”的咒骂。更重大的是，问题在于找到一种在保持良好性能的同时写入日志的办法。如果事务日志上的写入速度太慢，它们会减慢所有。

白羊座

1992 年，IBM 钻研人员“创造”了 WAL 的加强版本，称为 ARIES。大多数古代数据库或多或少都在应用 ARIES。逻辑可能不一样，但 ARIES 背地的概念无处不在。我之所以援用创造是因为，依据麻省理工学院的这门课程，IBM 钻研人员所做的“只不过是编写了事务复原的良好实际”。因为我在 ARIES 论文发表时才 5 岁，所以我不在乎这些来自香甜钻研人员的旧八卦。事实上，在咱们开始最初一个技术局部之前，我只是为了让您劳动一下。我曾经浏览了大量[对于 ARIES 的钻研论文]，我感觉它十分乏味！在这一部分中，我只会给你一个 ARIES 的概述，但如果你想要真正的常识，我强烈建议你浏览这篇论文。

ARIES 代表A algorithms for Recovery and I solation E xploiting Semantics。

这种技术的目标是双重的：

• 1)写日志时性能好
• 2) 疾速 牢靠的复原

数据库必须回滚事务有多种起因：

• 因为用户勾销了它
• 因为服务器或网络故障
• 因为事务毁坏了数据库的完整性（例如，您对列有 UNIQUE 束缚并且事务增加了反复项）
• 因为死锁

有时（例如，在网络故障的状况下），数据库能够复原事务。

这怎么可能？要答复这个问题，咱们须要理解日志记录中存储的信息。

日志

事务期间的每个 操作（增加 / 删除 / 批改）都会产生一个日志。此日志记录由以下局部组成：

• LSN：惟一的 Log S equence Number 。 此 LSN 按工夫程序给出 *。这意味着如果操作 A 产生在操作 B 之前，则日志 A 的 LSN 将低于日志 B 的 LSN。
• TransID：产生操作的事务的 id。
• PageID：批改数据在磁盘上的地位。磁盘上的最小数据量是一个页面，因而数据的地位就是蕴含数据的页面的地位。
• PrevLSN：指向同一事务产生的上一条日志记录的链接。
• UNDO：一种去除操作成果的办法

例如，如果操作是更新，UNDO 将存储更新之前更新元素的值 / 状态（物理 UNDO）或返回到先前状态的反向操作（逻辑 UNDO）**。

• REDO：重放操作的一种形式

同样，有两种办法能够做到这一点。您能够在操作后存储元素的值 / 状态，也能够存储操作自身以重播它。

• …：（仅供参考，ARIES 日志还有 2 个其余字段：UndoNxtLSN 和类型）。

此外，磁盘上的每个页面（存储数据，而不是日志）都有上次批改数据的操作的日志记录 (LSN) 的 ID。

* LSN 的给出形式比较复杂，因为它与日志的存储形式相关联。但这个想法放弃不变。

**ARIES 仅应用逻辑 UNDO，因为解决物理 UNDO 切实是一团糟。

留神：据我所知，只有 PostgreSQL 没有应用 UNDO。它应用垃圾收集器守护过程来删除旧版本的数据。这与 PostgreSQL 中数据版本控制的实现无关。

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

每个日志都有一个惟一的 LSN。链接的日志属于同一个事务。日志按工夫程序链接（链表的最初一个日志是最初一个操作的日志）。

日志缓冲区

为了防止日志写入成为次要瓶颈，应用了 日志缓冲区。

当查问执行器要求批改时：

• 1) 缓存管理器将批改存储在其缓冲区中。
• 2) 日志管理器将关联的日志存储在其缓冲区中。
• 3）在这一步，查问执行器认为操作曾经实现（因而能够要求其余批改）
• 4）而后（稍后）日志管理器将日志写入事务日志。何时写入日志的决定由算法实现。
• 5）而后（稍后）缓存管理器将批改写入磁盘。何时将数据写入磁盘的决定由算法实现。

提交事务时，意味着对于事务中的每个操作，步骤 1、2、3、4、5 都已实现。在事务日志中写入速度很快，因为它只是“在事务日志的某处增加日志”，而在磁盘上写入数据更为简单，因为它“以一种能够疾速读取数据的形式写入数据”。

STEAL 和 FORCE 政策

出于性能起因，第 5 步可能会在提交之后实现，因为在产生解体的状况下，依然能够应用 REDO 日志复原事务。这称为 不强制政策。

数据库能够抉择一个 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 什么都不须要：须要 最差的性能 和大量的 ram。

复原局部

好的，所以咱们有很好的日志，让咱们应用它们！

假如新实习生使数据库解体（规定 1：始终是实习生的错）。您重新启动数据库并开始复原过程。

ARIES 通过三遍从解体中复原：

• 1) 剖析过程：复原过程读取残缺的事务日志 *，以从新创立解体期间产生的事件的工夫线。它确定要回滚哪些事务（所有没有提交程序的事务都将回滚）以及解体时须要将哪些数据写入磁盘。
• 2) Redo pass：这个 pass 从剖析过程中确定的日志记录开始，并应用 REDO 将数据库更新到解体前的状态。

在重做阶段，REDO 日志按工夫程序解决（应用 LSN）。

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

如果 LSN(page_on_disk)>=LSN(log_record)，则示意数据在解体之前曾经写入磁盘（但该值被日志之后和解体之前产生的操作笼罩）所以什么都不做。

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

甚至对于将要回滚的事务也实现了重做，因为它简化了复原过程（但我确信古代数据库不会这样做）。

• 3) Undo pass : 这个 pass 回滚所有在解体时不残缺的事务。回滚从每个事务的最初一个日志开始，并以反工夫程序（应用日志记录的 PrevLSN）解决 UNDO 日志。

在复原过程中，事务日志必须被正告复原过程所做的操作，以便写入磁盘的数据与写入事务日志的数据同步。一个解决方案可能是删除正在吊销的事务的日志记录，但这十分艰难。相同，ARIES 在事务日志中写入弥补日志，从逻辑上删除正在删除的事务的日志记录。

当事务被“手动”勾销或由锁管理器（以进行死锁）或仅仅因为网络故障而勾销时，则不须要剖析通过。事实上，对于 REDO 和 UNDO 的信息能够在 2 个内存表中找到：

• 事务表（存储所有以后事务的状态）
• 脏页表（存储哪些数据须要写入磁盘）。

这些表由缓存管理器和事务管理器针对每个新事务事件进行更新。因为它们在内存中，因而当数据库解体时它们会被销毁。

分析阶段的工作是在解体后应用事务日志中的信息从新创立两个表。* 为了放慢剖析过程，ARIES 提供了 检查点 的概念。思路是不定时的将事务表和脏页表的内容以及本次写入时的最初一个 LSN 写入磁盘，这样在剖析过程中，只剖析这个 LSN 之后的日志。

总结

在写这篇文章之前，我晓得这个主题有多大，我晓得写一篇对于它的深刻文章须要工夫。原来我很乐观，花了比预期多两倍的工夫，但我学到了很多。

如果您想对数据库有一个很好的理解，我建议您浏览钻研论文“数据库系统架构”。这是一个很好的数据库介绍（110 页），非 CS 人员也能够浏览。这篇论文帮忙我找到了这篇文章的打算，它不像我的文章那样专一于数据结构和算法，而是更多地关注架构概念。

如果您仔细阅读本文，您当初应该理解数据库的弱小性能。因为这是一篇很长的文章，让我提醒您咱们所看到的：

• B+Tree 索引概述
• 数据库的全局概览
• 基于老本的优化概述，重点关注连贯运算符
• 缓冲池治理概述
• 事务管理概述

然而数据库蕴含更多的聪明才智。例如，我没有谈到一些辣手的问题，例如：

• 如何治理集群数据库和全局事务
• 如何在数据库仍在运行时拍摄快照
• 如何无效地存储（和压缩）数据
• 如何治理内存

因而，当您必须在有缺点的 NoSQL 数据库和坚如磐石的关系数据库之间进行抉择时，请三思。不要误会我的意思，一些 NoSQL 数据库很棒。但他们还很年老，并且答复了波及一些应用程序的特定问题。

总而言之，如果有人问您数据库是如何工作的，您当初能够答复：

对于关系数据库如何工作，你学废了么？