关系数据库如何工作

当谈到关系数据库时，我不禁想到缺少了一些东西。它们到处都在使用。有许多不同的数据库：从小而有用的 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 的 Wikipedia 文章。如果您想要在数据库中实现 B+Tree 的示例，请查看这篇文章以及来自 MySQL 核心开发人员的这篇文章。他们都专注于 innoDB（MySQL 的引擎）如何处理索引。

注意：一位读者告诉我，由于低级优化，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_function*N

如果 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）吗？它是内连接、外连接、笛卡尔积还是自连接？某些联接在某些情况下无法工作。
• 数据分布。如果连接条件上的数据有偏差（例如，您要以姓氏连接人，但许多人的姓氏相同），则使用哈希连接将是一场灾难，因为哈希函数会创建分布不均的存储桶。
• 如果您希望连接由多个线程/进程执行

有关更多信息，您可以阅读DB2、ORACLE或SQL Server文档。

简化示例

我们刚刚看到了 3 种类型的连接操作。

现在假设我们需要连接 5 个表才能看到一个人的完整视图。一个人可以有：

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

换句话说，我们需要以下查询的快速答案：

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

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

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

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

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

所以这是我的可能性：

• 1）我使用蛮力方法

使用数据库统计数据，我**计算每个可能的计划的成本，**并保留最好的一个。但是有很多可能性。对于给定的连接顺序，每个连接都有 3 种可能性：HashJoin、MergeJoin、NestedJoin。因此，对于给定的连接顺序，有 3 4种可能性。连接排序是二叉树上的置换问题，有 (2*4)!/(4+1)! 可能的订单。对于这个非常简单的问题，我最终得到 3 4 (24)!/(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在搜索最佳查询计划时使用“ N Nearest Neighbors ”贪心算法

让我们看看另一个优化器是如何完成他的工作的。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 只是从磁盘加载询问后的下一个连续数据）。

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

注意：缓存命中率低并不总是意味着缓存工作不正常。有关更多信息，您可以阅读Oracle 文档。

但是，缓冲区是有限的内存量。因此，它需要删除一些数据才能加载新数据。加载和清除缓存在磁盘和网络 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 被添加到缓冲区中
• …

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

改进

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

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

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

这个算法背后的想法是考虑到更多的历史。使用简单的 LRU（对于 K=1 也是 LRU-K），该算法仅考虑上次使用数据的时间。使用 LRU-K：

• 它考虑了上次使用数据的 K 次。
• 对数据的使用次数赋予权重
• 如果将一堆新数据加载到缓存中，则不会删除旧但经常使用的数据（因为它们的权重更高）。
• 但是如果不再使用旧数据，该算法就无法将旧数据保留在缓存中。
• 因此，**如果不使用数据，**权重会 随着时间的推移而降低。

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

想要更深入地了解 LRU-K，可以阅读原始研究论文（1993）：The LRU-K page replacement algorithm for database disk buffering。

其他算法

当然还有其他算法来管理缓存，比如

• 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）的原因。

与往常一样，您可以自行查看主要数据库（例如MySQL、PostgreSQL或Oracle）的文档。

日志管理器

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

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

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

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

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

沃尔

当在涉及许多事务的大型数据库上使用时，卷影副本/页面会产生巨大的磁盘开销。这就是现代数据库使用事务日志的原因。事务日志必须存储在稳定的存储器上。我不会深入讨论存储技术，但必须使用（至少）RAID 磁盘来防止磁盘故障。

大多数数据库（至少是 Oracle、SQL Server、DB2、PostgreSQL、MySQL 和 SQLite ）使用预写日志协议(WAL)处理事务日志。WAL 协议是一组 3 条规则：

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

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

错误的答案！经历了这么多，你应该知道，与数据库相关的一切都受到“数据库效应”的诅咒。更严重的是，问题在于找到一种在保持良好性能的同时写入日志的方法。如果事务日志上的写入速度太慢，它们会减慢一切。

白羊座

1992 年，IBM 研究人员“发明”了 WAL 的增强版本，称为 ARIES。大多数现代数据库或多或少都在使用 ARIES。逻辑可能不一样，但 ARIES 背后的概念无处不在。我之所以引用发明是因为，根据麻省理工学院的这门课程，IBM 研究人员所做的“只不过是编写了事务恢复的良好实践”。由于我在 ARIES 论文发表时才 5 岁，所以我不在乎这些来自苦涩研究人员的旧八卦。事实上，在我们开始最后一个技术部分之前，我只是为了让您休息一下。我已经阅读了大量关于 ARIES 的研究论文，我觉得它非常有趣！在这一部分中，我只会给你一个 ARIES 的概述，但如果你想要真正的知识，我强烈建议你阅读这篇论文。

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

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

• 1)写日志时性能好
• 2. 快速可靠的恢复

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

• 因为用户取消了它
• 由于服务器或网络故障
• 因为事务破坏了数据库的完整性（例如，您对列有 UNIQUE 约束并且事务添加了重复项）
• 因为死锁

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

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

日志

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

• LSN：唯一的LogS 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 数据库很棒。但他们还很年轻，并且回答了涉及一些应用程序的特定问题。

总而言之，如果有人问您数据库是如何工作的，您现在可以回答：

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

---

真诚地邀请您加入我们的大家庭,在这里不仅有技术知识分享,还有博主们之间的互帮互助.还不定期发红包,每月更有抽奖环节,游戏机和实体书相赠(包邮),让我们抱团取暖,抱团内卷.打造美好C站.期待您的加入.