当谈到关系数据库时,我不禁想到缺少了一些东西。它们到处都在使用。有许多不同的数据库:从小而有用的 SQLite 到强大的 Teradata。但是,只有几篇文章解释了数据库的工作原理。你可以自己谷歌“关系数据库是如何工作的”,看看有多少结果。而且,这些文章很短。现在,如果您寻找最新的流行技术(大数据、NoSQL 或 JavaScript),您会发现更深入的文章解释了它们的工作原理。
关系数据库是否太陈旧太无聊而无法在大学课程、研究论文和书籍之外进行解释?
作为开发人员,我讨厌使用我不理解的东西。而且,如果数据库已经使用了 40 年,那肯定是有原因的。多年来,我花了数百个小时来真正理解我每天使用的这些奇怪的黑匣子。 关系数据库 非常有趣,因为它们基于有用且可重用的概念。如果您对了解数据库感兴趣,但从未有时间或意愿深入研究这个广泛的主题,那么您应该喜欢这篇文章。
尽管本文的标题很明确,但本文的目的并不是要了解如何使用数据库。因此,您应该已经知道如何编写简单的连接查询和基本的 CRUD 查询;否则你可能看不懂这篇文章。这是你唯一需要知道的,我会解释其他的。
我将从一些计算机科学的东西开始,比如时间复杂度。我知道你们中的一些人讨厌这个概念,但是没有它,你就无法理解数据库中的聪明之处。由于这是一个巨大的话题,我将专注于我认为必不可少的内容:数据库处理 SQL 查询的方式。我将只介绍数据库背后的基本概念,以便在本文结尾处您对幕后发生的事情有一个很好的了解。
由于这是一篇涉及许多算法和数据结构的长篇技术文章,请花点时间阅读它。有些概念比较难理解;您可以跳过它们,但仍然可以了解总体思路。
对于知识渊博的您,本文或多或少分为 3 个部分:
很久以前(在一个遥远的星系中……),开发人员必须确切地知道他们正在编码的操作数量。他们对自己的算法和数据结构了如指掌,因为他们负担不起浪费慢速计算机的 CPU 和内存。
在这一部分中,我将提醒您其中一些概念,因为它们对于理解数据库至关重要。我还将介绍数据库索引的概念。
如今,许多开发人员并不关心时间复杂度……他们是对的!
但是,当您处理大量数据(我不是在谈论数千个数据)时,或者如果您正在为毫秒而战,那么理解这个概念就变得至关重要。你猜怎么着,数据库必须同时处理这两种情况!我不会让你厌烦很长时间,只是时间去了解这个想法。这将有助于我们以后理解 基于成本的优化的概念。
时间复杂度用于查看算法对于给定数量的数据需要多长时间。为了描述这种复杂性,计算机科学家使用数学大 O 表示法。该符号与一个函数一起使用,该函数描述了一个算法对于给定数量的输入数据需要多少次操作。
例如,当我说“这个算法在 O( some_function() ) 中”时,它意味着对于一定数量的数据,该算法需要 some_function(a_certain_amount_of_data) 操作来完成它的工作。
重要的不是数据量,而是当数据量增加时操作数量增加的方式。时间复杂度并没有给出确切的操作数量,而是一个好主意。
在此图中,您可以看到不同类型复杂性的演变。我使用对数刻度来绘制它。换句话说,数据的数量正在迅速从 1 增加到 10 亿。我们可以看到:
在数据量较少的情况下,O(1) 和 O(n 2 )之间的差异可以忽略不计。例如,假设您有一个算法需要处理 2000 个元素。
O(1) 和 O(n 2 )之间的差异似乎很大(400 万),但您最多会在 2 毫秒内丢失,这只是眨眼的时间。事实上,当前的处理器[每秒可以处理数亿次操作。这就是为什么性能和优化在许多 IT 项目中不是问题的原因。
正如我所说,在面对大量数据时,了解这个概念仍然很重要。如果这次算法需要处理 1 000 000 个元素(这对于数据库来说并不是那么大):
我没有做数学计算,但我会说使用 O(n 2 ) 算法你有时间喝杯咖啡(甚至是第二杯!)。如果您在数据量上再加 0,您将有时间小睡一会儿。
给你一个想法:
注意:在接下来的部分中,我们将看到这些算法和数据结构。
时间复杂度有多种类型:
时间复杂度通常是最坏的情况。
我只谈到了时间复杂度,但复杂度也适用于:
当然,还有比 n 2更复杂的复杂性,例如:
注意:我没有给你大 O 符号的真正定义,而只是想法。您可以在Wikipedia上阅读这篇文章以了解真实(渐近)定义。
当您需要对集合进行排序时,您会怎么做?什么?你调用 sort() 函数……好吧,很好的答案……但是对于数据库,你必须了解这个 sort() 函数是如何工作的。
有几种很好的排序算法,所以我将专注于最重要的一种:归并排序。你现在可能不明白为什么排序数据是有用的,但你应该在查询优化部分之后。此外,理解归并排序有助于我们以后理解一种常见的数据库连接操作,称为归并连接。
像许多有用的算法一样,归并排序基于一个技巧:将 2 个大小为 N/2 的排序数组合并为一个 N 元素排序数组只需要 N 次操作。此操作称为合并。
让我们通过一个简单的例子来看看这意味着什么:
您可以在此图中看到,要构造最终的 8 个元素的排序数组,您只需要在 2 个 4 元素数组中迭代一次。由于两个 4 元素数组都已排序:
这是有效的,因为两个 4 元素数组都已排序,因此您不需要在这些数组中“返回”。
现在我们已经理解了这个技巧,这是我的合并排序伪代码。
归并排序将问题分解为更小的问题,然后找到更小的问题的结果得到初始问题的结果(注意:这种算法称为分治法)。如果您不了解此算法,请不要担心;我第一次看到的时候没看懂。如果它可以帮助你,我认为这个算法是一个两阶段算法:
在划分阶段,使用 3 个步骤将阵列划分为单一阵列。正式的步数是 log(N)(因为 N=8,log(N) = 3)。
我怎么知道?
我是天才!一句话:数学。这个想法是每一步都将初始数组的大小除以 2。步数是您可以将初始数组除以 2 的次数。这是对数的精确定义(以 2 为底)。
在排序阶段,您从酉数组开始。在每个步骤中,您应用多个合并,总成本为 N=8 操作:
由于有 log(N) 个步骤,因此总成本为 N * log(N) 个操作。
为什么这个算法如此强大?
因为:
注意:这种算法称为就地算法。
注意:这种算法称为[外部排序。
例如,分布式归并排序是Hadoop(大数据中的框架)的关键组件之一。
大多数(如果不是全部)数据库都使用这种排序算法,但它不是唯一的。如果您想了解更多信息,可以阅读这篇研究论文,该论文讨论了数据库中常见排序算法的优缺点。
现在我们了解了时间复杂度和排序背后的想法,我必须告诉你 3 个数据结构。这很重要,因为它们是现代数据库的支柱。我还将介绍数据库索引的概念。
二维数组是最简单的数据结构。表可以看作是一个数组。例如:
这个二维数组是一个包含行和列的表:
虽然存储和可视化数据很棒,但当您需要寻找特定值时,它就很糟糕了。
例如,如果您想查找在 UK 工作的所有人员,则必须查看每一行以查找该行是否属于 UK。这将花费您 N 次操作(N 是行数),这还不错,但有没有更快的方法?这就是树木发挥作用的地方。
注意:大多数现代数据库都提供高级数组来有效地存储表,例如堆组织表或索引组织表。但它并没有改变在一组列上快速搜索特定条件的问题。
二叉搜索树是具有特殊性质的二叉树,每个节点中的键必须是:
让我们看看它在视觉上意味着什么
这棵树有 N=15 个元素。假设我正在寻找 208:
现在假设我正在寻找 40
最后,两次搜索都让我损失了树内的层数。如果您仔细阅读有关合并排序的部分,您应该会看到有 log(N) 个级别。所以搜索的成本是 log(N),还不错!
但是这些东西非常抽象,所以让我们回到我们的问题。想象一下代表上表中某人所在国家/地区的字符串,而不是一个愚蠢的整数。假设您有一棵树,其中包含表的“国家”列:
如果您直接使用数组,则此搜索仅花费您 log(N) 次操作而不是 N 次操作。您刚才想象的是一个数据库索引。
您可以为任何一组列(一个字符串、一个整数、2 个字符串、一个整数和一个字符串、一个日期……)建立一个树索引,只要您有比较键(即列组)的功能,所以您可以在键之间建立顺序 (数据库中的任何基本类型都是这种情况)。
尽管此树可以很好地获取特定值,但是当您需要获取两个值之间的**多个元素 时,就会出现一个大问题。这将花费 O(N),因为您必须查看树中的每个节点并检查它是否在这两个值之间(例如,按顺序遍历树)。此外,此操作对磁盘 I/O 不友好,因为您必须读取完整的树。我们需要找到一种方法来有效地进行范围查询**。为了解决这个问题,现代数据库使用了以前称为 B+Tree 的树的修改版本。在 B+树中:
如您所见,有更多节点(多两倍)。实际上,您还有其他节点,即“决策节点”,它们将帮助您找到正确的节点(存储相关表中行的位置)。但是搜索复杂度仍然在 O(log(N)) (只有一个级别)。最大的不同是最低节点链接到它们的后继节点。
使用此 B+Tree,如果您要查找 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(log(N)) 操作来更新表的索引。此外,添加索引意味着事务管理器的工作量更大(我们将在文章末尾看到这个管理器)。
注意:一位读者告诉我,由于低级优化,B+Tree 需要完全平衡。
我们最后一个重要的数据结构是哈希表。当您想快速查找值时,它非常有用。此外,了解哈希表有助于我们以后理解一种常见的数据库连接操作,称为哈希连接。这个数据结构也被数据库用来存储一些内部的东西(比如锁表或缓冲池,我们稍后会看到这两个概念)
哈希表是一种数据结构,可以快速找到带有键的元素。要构建哈希表,您需要定义:
让我们有一个直观的例子:
这个哈希表有 10 个桶。由于我很懒,我只画了 5 个桶,但我知道你很聪明,所以我让你想象其他 5 个。我使用的哈希函数是密钥的模 10。换句话说,我只保留元素键的最后一位来找到它的桶:
我使用的比较函数只是两个整数之间的相等。
假设您想要获取元素 78:
现在,假设您想要获取元素 59:
如您所见,根据您要寻找的价值,成本是不一样的!
如果我现在用密钥的模 1 000 000 更改哈希函数(即取最后 6 位数字),第二次搜索只需 1 次操作,因为桶 000059 中没有元素。真正的挑战是找到一个好的哈希函数将创建包含非常少量元素的桶。
在我的示例中,找到一个好的散列函数很容易。但这是一个简单的例子,当关键是:
使用好的散列函数, 在散列表中的搜索在 O(1)中。
为什么不使用数组?
哼,你问的很好。
有关更多信息,您可以阅读我关于Java HashMap的文章,它是一种高效的哈希表实现;您无需了解 Java 即可理解本文中的概念。
我们刚刚看到了数据库中的基本组件。我们现在需要退后一步来看看大局。
数据库是可以轻松访问和修改的信息集合。但是一堆简单的文件可以做同样的事情。事实上,像 SQLite 这样最简单的数据库无非就是一堆文件。但是 SQLite 是一组精心设计的文件,因为它允许您:
更一般地,一个数据库可以看成下图:
在写这部分之前,我已经阅读了多本书籍/论文,并且每个来源都有其代表数据库的方式。因此,不要过分关注我是如何组织这个数据库或如何命名流程的,因为我做出了一些选择来适应本文的计划。重要的是不同的组件;总体思路是将一个数据库划分为多个相互交互的组件。
核心组件:
工具:
查询管理器:
数据管理员:
在本文的其余部分,我将重点介绍数据库如何通过以下过程管理 SQL 查询:
客户经理是处理与客户沟通的部分。客户端可以是(Web)服务器或最终用户/最终应用程序。客户端管理器通过一组众所周知的 API 提供不同的方式来访问数据库:JDBC、ODBC、OLE-DB ...
它还可以提供专有的数据库访问 API。
当您连接到数据库时:
这部分是数据库的强大之处。在这部分,一个写得不好的查询被转换成一个快速的可执行代码。然后执行代码并将结果返回给客户端管理器。这是一个多步骤操作:
在这一部分中,我不会过多地谈论最后两点,因为它们不太重要。
阅读完这部分后,如果您想更好地理解,我建议您阅读:
每个 SQL 语句都被发送到解析器,在那里检查语法是否正确。如果您在查询中出错,解析器将拒绝该查询。例如,如果您写的是“SLECT ...”而不是“SELECT ...”,那么故事到此结束。
但这更深入。它还检查关键字的使用顺序是否正确。例如,SELECT 之前的 WHERE 将被拒绝。
然后,分析查询中的表和字段。解析器使用数据库的元数据来检查:
然后它会检查您是否有权读取(或写入)查询中的表。同样,这些对表的访问权限是由您的 DBA 设置的。
在此解析期间,SQL 查询被转换为内部表示(通常是树)
如果一切正常,则内部表示将发送到查询重写器。
在这一步,我们有一个查询的内部表示。重写器的目标是:
重写器对查询执行一系列已知规则。如果查询符合规则的模式,则应用该规则并重写查询。以下是(可选)规则的非详尽列表:
例如
将被替换
然后,这个重写的查询被发送到查询优化器,乐趣开始了!
在我们了解数据库如何优化查询之前,我们需要先谈谈统计数据,因为没有它们 ,数据库是愚蠢的。如果您不告诉数据库分析自己的数据,它就不会这样做,并且会做出(非常)糟糕的假设。
但是数据库需要什么样的信息呢?
我必须(简要地)谈谈数据库和操作系统是如何存储数据的。他们使用称为页面或块**的** 最小单位(默认为 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 ),因为数据库将更好地了解这些谓词所涉及的行数(注意:这个概念是选择性)。
统计信息存储在数据库的元数据中。例如,您可以查看(非分区)表的统计信息:
统计数据必须是最新的。没有什么比数据库认为一个表只有 500 行而它有 1 000 000 行更糟糕的了。统计数据的唯一缺点是计算它们需要时间。这就是为什么在大多数数据库中默认情况下不会自动计算它们的原因。数以百万计的数据很难计算出来。在这种情况下,您可以选择仅计算基本统计信息或计算数据库样本的统计信息。
例如,当我在处理每个表中的数亿行的项目时,我选择仅计算 10% 的统计信息,这导致了巨大的时间收益。对于这个故事,它被证明是一个糟糕的决定,因为有时 Oracle 10G 为特定表的特定列选择的 10% 与整体 100% 非常不同(这对于具有 100M 行的表来说不太可能发生) . 这个错误的统计数据导致查询有时需要 8 小时而不是 30 秒;寻找根本原因的噩梦。这个例子显示了统计数据的重要性。
注意:当然,每个数据库都有更高级的统计信息。如果您想了解更多信息,请阅读数据库的文档。话虽如此,我试图了解统计数据的使用方式,我发现的最好的官方文档是来自 PostgreSQL的文档。
所有现代数据库都使用基于成本的优化(或CBO)来优化查询。这个想法是为每个操作设置一个成本,并通过使用最便宜的操作链来找到降低查询成本的最佳方法来获得结果。
为了理解成本优化器的工作原理,我认为最好有一个例子来“感受”这项任务背后的复杂性。在这一部分中,我将向您展示连接 2 个表的 3 种常用方法,我们将很快看到,即使是简单的连接查询也是优化的噩梦。在那之后,我们将看到真正的优化器是如何完成这项工作的。
对于这些连接,我将关注它们的时间复杂度,但数据库 优化器会计算它们的CPU 成本、磁盘 I/O 成本和内存需求。时间复杂度和 CPU 成本之间的区别在于,时间成本非常近似(适用于像我这样的懒人)。对于 CPU 成本,我应该计算每个操作,例如加法、“if 语句”、乘法、迭代……此外:
使用时间复杂度更容易(至少对我而言),有了它我们仍然可以得到 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 访问。
例如,如果您执行类似的操作
如果你有一个关于年龄列的人的索引,优化器将使用该索引来查找所有 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 更友好的版本。这是想法:
这是一个可能的算法:
使用此版本,时间复杂度保持不变,但磁盘访问次数减少:
注意:每次磁盘访问比以前的算法收集更多的数据,但这并不重要,因为它们是顺序访问(机械磁盘的真正问题是获取第一个数据的时间)。
散列连接更复杂,但在许多情况下比嵌套循环连接成本更低。
哈希连接的想法是:
在时间复杂度方面,我需要做一些假设来简化问题:
时间复杂度为 (M/X) _N + cost_to_create_hash_table(M) + cost_of_hash_function_N
如果 Hash 函数创建了足够多的小桶,那么时间复杂度是 O(M+N)
这是哈希连接的另一个版本,它对内存更友好,但对磁盘 I/O 更不友好。这次:
合并连接是唯一产生排序结果的连接。
注意:在这个简化的合并连接中,没有内表或外表;他们都扮演同样的角色。但是实际的实现会有所不同,例如,在处理重复项时。
合并连接可以分为两个步骤:
种类
我们已经谈到了归并排序,在这种情况下,归并排序是一种好的算法(但如果内存不是问题,则不是最好的)。
但有时数据集已经排序,例如:
合并加入
这部分和我们看到的归并排序的归并操作非常相似。但是这一次,我们不是从两个关系中选择每个元素,而是只从两个关系中选择相等的元素。这是想法:
这是有效的,因为这两个关系都是排序的,因此您不需要在这些关系中“返回”。
该算法是一个简化版本,因为它不处理相同数据在两个数组中多次出现(即多次匹配)的情况。对于这种情况,真实版本“只是”更复杂;这就是我选择简化版本的原因。
如果两个关系都已排序,则时间复杂度为 O(N+M)
如果两个关系都需要排序,那么时间复杂度就是对两个关系进行排序的成本:O(N*Log(N) + M*Log(M))
对于 CS 极客,这里有一个可能的算法来处理多个匹配(注意:我不是 100% 确定我的算法):
如果有最好的连接类型,就不会有多种类型。这个问题非常困难,因为许多因素都在起作用,例如:
我们刚刚看到了 3 种类型的连接操作。
现在假设我们需要连接 5 个表才能看到一个人的完整视图。一个人可以有:
换句话说,我们需要以下查询的快速答案:
作为查询优化器,我必须找到处理数据的最佳方式。但是有2个问题:
我有 3 个可能的连接(哈希连接、合并连接、嵌套连接),可以使用 0,1 或 2 个索引(更不用说有不同类型的索引)。
例如,下图显示了 4 个表上仅 3 个连接的不同可能计划
所以这是我的可能性:
使用数据库统计数据,我计算每个可能的计划的成本,并保留最好的一个。但是有很多可能性。对于给定的连接顺序,每个连接都有 3 种可能性:HashJoin、MergeJoin、NestedJoin。因此,对于给定的连接顺序,有 3 4种可能性。连接排序是二叉树上的置换问题,有 (24)!/(4+1)! 可能的订单。对于这个非常简单的问题,我最终得到 3 4 (2*4)!/(4+1)! 可能性。
在非极客术语中,这意味着 27 216 个可能的计划。如果我现在添加合并连接采用 0,1 或 2 个 B+Tree 索引的可能性,则可能的计划数将变为 210 000。我是否忘记提及此查询非常简单?
这很诱人,但你不会得到你的结果,我需要钱来支付账单。
由于我不是超人,我无法计算每个计划的成本。相反,我可以任意选择所有可能计划的子集,计算它们的成本并为您提供该子集的最佳计划。
有两种类型的规则:
我可以使用“逻辑”规则来消除无用的可能性,但它们不会过滤很多可能的计划。例如:“嵌套循环连接的内部关系必须是最小的数据集”
我接受没有找到最佳解决方案并应用更积极的规则来减少很多可能性。例如“如果关系很小,请使用嵌套循环连接,并且永远不要使用合并连接或哈希连接”
在这个简单的例子中,我得到了很多可能性。但真正的查询可以有其他关系运算符,如 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 极客,这是我在我已经给你的正式课程中找到的算法。我不会解释这个算法,所以只有当你已经知道动态编程或者你对算法很熟悉时才阅读它(你已经被警告过!):
对于更大的查询,您仍然可以使用动态编程方法,但使用额外的规则(或启发式)来消除可能性:
但是对于一个非常大的查询或有一个非常快的答案(但不是一个非常快的查询),使用另一种类型的算法,贪心算法。
这个想法是遵循规则(或启发式)以增量方式构建查询计划。使用此规则,贪心算法一步一步地找到问题的最佳解决方案。该算法以一个 JOIN 开始查询计划。然后,在每一步,算法使用相同的规则向查询计划添加一个新的 JOIN。
让我们举一个简单的例子。假设我们有一个在 5 个表(A、B、C、D 和 E)上具有 4 个连接的查询。为了简化问题,我们只是将嵌套连接作为可能的连接。让我们使用规则“使用成本最低的连接”
由于我们任意从 A 开始,我们可以对 B 应用相同的算法,然后是 C,然后是 D,然后是 E。然后我们保持成本最低的计划。
顺便说一句,这个算法有一个名字:它叫做[最近邻算法。
我不会详细介绍,但是通过良好的建模和 N*log(N) 中的排序,这个问题可以[很容易地解决。对于完整的动态编程版本,该算法的成本在 O(N*log(N)) 与 O(3 N ) 之间。如果您有一个包含 20 个连接的大查询,这意味着 26 对 3 486 784 401,差别很大!
这个算法的问题在于,如果我们保留这个连接并添加一个新连接,我们假设在 2 个表之间找到最佳连接将为我们提供最佳成本。但:
为了改善结果,您可以使用不同的规则运行多个贪心算法并保持最佳计划。
如果您已经厌倦了算法,请跳到下一部分,我要说的对于本文的其余部分并不重要
寻找最佳计划的问题是许多 CS 研究人员的活跃研究课题。他们经常尝试为更精确的问题/模式找到更好的解决方案。例如,
还研究了其他算法来替代大型查询的动态编程。贪心算法属于更大的家族,称为启发式算法。贪心算法遵循规则(或启发式),保留它在上一步找到的解决方案,并“附加”它以找到当前步骤的解决方案。一些算法遵循规则并逐步应用它,但并不总是保持上一步中找到的最佳解决方案。它们被称为启发式算法。
例如,遗传算法遵循一个规则,但通常不会保留最后一步的最佳解决方案:
你做的循环越多,计划就会越好。
是魔法吗?不,这是自然法则:适者生存!
仅供参考,遗传算法是在PostgreSQL中实现的,但我无法找到它们是否默认使用。
数据库中还使用了其他启发式算法,例如模拟退火、迭代改进、两阶段优化……但我不知道它们目前是用于企业数据库还是仅用于研究数据库。
有关更多信息,您可以阅读以下研究文章,其中介绍了更多可能的算法: Review of Algorithms for the Join Ordering Problem in Database Query Optimization
【你可以跳到下一部分,我要说什么不重要】
但是,所有这些废话都是非常理论的。因为我是开发人员而不是研究人员,所以我喜欢具体的例子。
让我们看看SQLite 优化器是如何工作的。这是一个轻量级数据库,因此它使用基于贪心算法的简单优化和额外规则来限制可能性的数量:
等一下……我们已经看过这个算法了!多么巧合!
让我们看看另一个优化器是如何完成他的工作的。IBM DB2 就像所有的企业数据库一样,但我将专注于这个,因为它是我在切换到大数据之前真正使用的最后一个。
我们会了解到 DB2 优化器允许您使用 7 种不同级别的优化:
我们可以看到DB2 使用了贪心算法和动态编程。当然,他们不共享他们使用的启发式方法,因为查询优化器是数据库的主要功能。
仅供参考,默认级别为 5。默认情况下,优化器使用以下特性:
,具有:
默认情况下,DB2 对连接排序使用受启发式限制的动态编程。
其他条件(GROUP BY、DISTINCT…)由简单的规则处理。
由于创建计划需要时间,因此大多数数据库将计划存储到查询计划缓存中,以避免对同一查询计划进行无用的重新计算。这是一个很大的话题,因为数据库需要知道何时更新过时的计划。这个想法是设置一个阈值,如果一个表的统计数据已经超过这个阈值,那么涉及这个表的查询计划就会从缓存中清除。
在这个阶段,我们有一个优化的执行计划。这个计划被编译成可执行代码。然后,如果有足够的资源(内存、CPU),则由查询执行器执行。计划中的操作符(JOIN、SORT BY ...)可以按顺序或并行方式执行;这取决于执行人。为了获取和写入其数据,查询执行器与数据管理器交互,这是本文的下一部分。
在这一步,查询管理器正在执行查询并需要来自表和索引的数据。它要求数据管理器获取数据,但有两个问题:
在这一部分中,我们将看到关系数据库如何处理这两个问题。我不会谈论数据管理器获取数据的方式,因为它不是最重要的(这篇文章已经够长了!)。
正如我已经说过的,数据库的主要瓶颈是磁盘 I/O。为了提高性能,现代数据库使用缓存管理器。
查询执行器不是直接从文件系统获取数据,而是向缓存管理器请求数据。缓存管理器有一个称为缓冲池的内存缓存。从内存中获取数据极大地加速了数据库。很难给出一个数量级,因为它取决于您需要执行的操作:
以及数据库使用的磁盘类型:
但我想说memory 比 disk 快 100 到 100k 倍。
但是,这会导致另一个问题(与数据库一样……)。缓存管理器需要在查询执行器使用它们之前获取内存中的数据;否则查询管理器必须等待来自慢速磁盘的数据。
这个问题称为预取。查询执行器知道它需要的数据,因为它知道查询的完整流程,并且知道磁盘上的数据和统计信息。这是想法:
CM 将所有这些数据存储在其缓冲池中。为了知道是否仍然需要数据,缓存管理器添加了有关缓存数据的额外信息(称为锁存器)。
有时查询执行器不知道它需要什么数据,并且一些数据库不提供此功能。相反,他们使用推测预取(例如:如果查询执行器请求数据 1、3、5,它可能会在不久的将来请求 7、9、11)或顺序预取(在这种情况下,CM 只是从磁盘加载询问后的下一个连续数据)。
为了监控预取的工作情况,现代数据库提供了一个称为缓冲区/缓存命中率的指标。命中率显示在缓冲区高速缓存中找到请求数据而不需要磁盘访问的频率。
但是,缓冲区是有限的内存量。因此,它需要删除一些数据才能加载新数据。加载和清除缓存在磁盘和网络 I/O 方面是有代价的。如果您有一个经常执行的查询,那么始终加载然后清除此查询使用的数据将不会有效。为了解决这个问题,现代数据库使用缓冲区替换策略。
大多数现代数据库(至少 SQL Server、MySQL、Oracle 和 DB2)都使用 LRU 算法。
LRU代表Least Recently U sed 。_ 该算法背后的想法是将最近使用过的数据保存在缓存中,因此更有可能再次使用。
这是一个视觉示例:
为了便于理解,我假设缓冲区中的数据没有被闩锁锁定(因此可以被删除)。在这个简单的示例中,缓冲区可以存储 3 个元素:
该算法运行良好,但存在一些限制。如果对大表进行全扫描怎么办?换句话说,当表/索引的大小大于缓冲区的大小时会发生什么?使用此算法将删除缓存中所有先前的值,而来自全扫描的数据可能只使用一次。
为了防止这种情况发生,一些数据库添加了特定的规则
“对于非常大的表,数据库通常使用直接路径读取,直接加载块 ...,以避免填充缓冲区缓存。对于中等大小的表,数据库可以使用直接读取或缓存读取。如果它决定使用缓存读取,那么数据库会将块放在 LRU 列表的末尾,以防止扫描有效地清除缓冲区缓存。”
还有其他可能性,例如使用称为 LRU-K 的 LRU 的高级版本。例如 SQL Server 使用 LRU-K 表示 K =2。
这个算法背后的想法是考虑到更多的历史。使用简单的 LRU(对于 K=1 也是 LRU-K),该算法仅考虑上次使用数据的时间。使用 LRU-K:
权重的计算成本很高,这就是 SQL Server 只使用 K=2 的原因。对于可接受的开销,该值表现良好。
当然还有其他算法来管理缓存,比如
一些数据库允许使用默认算法之外的另一种算法。
我只讨论了在使用它们之前加载数据的读取缓冲区。但是在数据库中,您也有写入缓冲区,用于存储数据并将它们成批刷新到磁盘上,而不是一个接一个地写入数据并产生许多单个磁盘访问。
请记住,缓冲区存储页面(最小的数据单元)而不是行(这是查看数据的逻辑/人为方式)。如果页面已被修改且未写入磁盘,则缓冲池中的页面为脏页面。有多种算法可以决定在磁盘上写入脏页的最佳时间,但它与事务的概念高度相关,这是本文的下一部分。
最后但同样重要的是,这部分是关于事务管理器的。我们将看到这个过程如何确保每个查询在其自己的事务中执行。但在此之前,我们需要了解 ACID 事务的概念。
ACID 事务是一个确保 4 件事的工作单元:
在同一事务中,您可以运行多个 SQL 查询来读取、创建、更新和删除数据。当两个事务使用相同的数据时,混乱就开始了。典型的例子是从账户 A 到账户 B 的转账。假设您有 2 笔交易:
如果我们回到ACID属性:
你可以跳到下一部分,我要说的对于文章的其余部分并不重要
许多现代数据库不使用纯隔离作为默认行为,因为它会带来巨大的性能开销。SQL 规范定义了 4 个隔离级别:
例如,如果事务 A 执行“SELECT count(1) from TABLE_X”,然后事务 B 在 TABLE_X 中添加并提交新数据,如果事务 A 再次执行 count(1),则该值将不是相同的。
这称为幻读。
这称为不可重复读取。
这称为脏读。
大多数数据库都添加了自己的自定义隔离级别(如 PostgreSQL、Oracle 和 SQL Server 使用的快照隔离)。此外,大多数数据库并未实现 SQL 规范的所有级别(尤其是未提交读级别)。
用户/开发人员可以在连接开始时覆盖默认的隔离级别(这是添加的非常简单的代码行)。
确保隔离、一致性和原子性的真正问题是对相同数据的写操作(添加、更新和删除):
这个问题叫做并发控制。
解决这个问题最简单的方法是逐个(即顺序)运行每个事务。但这根本不可扩展,并且只有一个内核在多处理器/内核服务器上工作,效率不高……
解决此问题的理想方法是,每次创建或取消事务时:
更正式地说,这是一个具有冲突时间表的调度问题。更具体地说,这是一个非常困难且占用 CPU 资源的优化问题。企业数据库不能等待数小时才能为每个新事务事件找到最佳时间表。因此,他们使用不太理想的方法,导致在冲突事务之间浪费更多时间。
为了处理这个问题,大多数数据库都使用锁和/或数据版本控制。由于这是一个很大的话题,我将专注于锁定部分,然后我将谈谈数据版本控制。
锁定背后的想法是:
这称为排他锁。
但是对只需要读取数据的事务使用排他锁是非常昂贵的,因为它会迫使只想读取相同数据的其他事务等待。这就是为什么还有另一种锁,共享锁的原因。
使用共享锁:
尽管如此,如果将数据作为排他锁,则只需要读取数据的事务将不得不等待排他锁结束才能在数据上放置共享锁。
锁管理器是提供和释放锁的进程。在内部,它将锁存储在哈希表中(其中键是要锁定的数据)并知道每个数据:
但是锁的使用会导致两个事务永远等待一个数据的情况:
在这个图中:
这称为死锁。
在死锁期间,锁管理器选择取消(回滚)哪个事务以消除死锁。这个决定并不容易:
但是在做出这个选择之前,它需要检查是否存在死锁。
哈希表可以看作是一个图形(如前面的图)。如果图中存在循环,则存在死锁。由于检查循环的成本很高(因为所有锁的图都很大),所以经常使用一种更简单的方法:使用timeout。如果在此超时时间内没有给出锁,则事务进入死锁状态。
锁管理器还可以在提供锁之前检查该锁是否会造成死锁。但是再次完美地完成它在计算上是昂贵的。因此,这些预先检查往往是一套基本规则。
确保纯隔离的最简单方法是在事务开始时获取锁并在事务结束时释放锁。这意味着事务在开始之前必须等待它的所有锁,并且事务持有的锁在事务结束时被释放。它可以工作,但 会浪费大量时间来等待所有锁。
一种更快的方法是两阶段锁定协议(由 DB2 和 SQL Server 使用),其中一个事务被分为两个阶段:
这两条简单规则背后的想法是:
该协议运行良好,除非修改数据并释放关联锁的事务被取消(回滚)。您最终可能会遇到另一个事务读取修改后的值而该值将被回滚的情况。为避免此问题,必须在事务结束时释放所有排他锁。
当然,真正的数据库使用更复杂的系统,涉及更多类型的锁(如意向锁)和更多粒度(行、页、分区、表、表空间上的锁),但这个想法仍然是相同的。
我只介绍了纯基于锁的方法。数据版本控制是解决此问题的另一种方法。
版本控制背后的想法是:
它提高了性能,因为:
一切都比锁好,除非两个事务写入相同的数据。此外,您很快就会得到巨大的磁盘空间开销。
数据版本控制和锁定是两种不同的愿景:乐观锁定与悲观锁定。它们都有优点和缺点;这实际上取决于用例(更多读取与更多写入)。对于数据版本控制的演示,我推荐这个关于 PostgreSQL 如何实现多版本并发控制的非常好的演示。
一些数据库,如 DB2(直到 DB2 9.7)和 SQL Server(快照隔离除外)只使用锁。其他如 PostgreSQL、MySQL 和 Oracle 使用涉及锁和数据版本控制的混合方法。我不知道仅使用数据版本控制的数据库(如果您知道基于纯数据版本控制的数据库,请随时告诉我)。
更新 08/20/2015 一位读者告诉我:
Firebird 和 Interbase 使用没有记录锁定的版本控制。 版本控制对索引有一个有趣的影响:有时唯一索引包含重复项,索引的条目可能比表的行多,等等。
如果您阅读了有关不同隔离级别的部分,则当您增加隔离级别时,您会增加锁的数量,因此会浪费事务等待其锁的时间。这就是为什么大多数数据库默认不使用最高隔离级别(Serializable)的原因。
我们已经看到,为了提高性能,数据库将数据存储在内存缓冲区中。但是,如果在提交事务时服务器崩溃了,那么在崩溃期间您将丢失仍在内存中的数据,这会破坏事务的持久性。
您可以将所有内容都写入磁盘,但如果服务器崩溃,您最终会在磁盘上写入一半的数据,这会破坏事务的原子性。
事务写入的任何修改都必须撤消或完成。
要解决这个问题,有两种方法:
当在涉及许多事务的大型数据库上使用时,卷影副本/页面会产生巨大的磁盘开销。这就是现代数据库使用事务日志的原因。事务日志必须存储在稳定的存储器上。我不会深入讨论存储技术,但必须使用(至少)RAID 磁盘来防止磁盘故障。
WAL 协议是一组 3 条规则:
这项工作由日志管理器完成。一种简单的查看方式是,在缓存管理器和数据访问管理器(将数据写入磁盘)之间,日志管理器在事务日志上写入每个更新/删除/创建/提交/回滚,然后再将它们写入磁盘。容易,对吧?
错误的答案!经历了这么多,你应该知道,与数据库相关的一切都受到“数据库效应”的诅咒。更严重的是,问题在于找到一种在保持良好性能的同时写入日志的方法。如果事务日志上的写入速度太慢,它们会减慢一切。
1992 年,IBM 研究人员“发明”了 WAL 的增强版本,称为 ARIES。大多数现代数据库或多或少都在使用 ARIES。逻辑可能不一样,但 ARIES 背后的概念无处不在。我之所以引用发明是因为,根据麻省理工学院的这门课程,IBM 研究人员所做的“只不过是编写了事务恢复的良好实践”。由于我在 ARIES 论文发表时才 5 岁,所以我不在乎这些来自苦涩研究人员的旧八卦。事实上,在我们开始最后一个技术部分之前,我只是为了让您休息一下。我已经阅读了大量关于 ARIES 的研究论文,我觉得它非常有趣!在这一部分中,我只会给你一个 ARIES 的概述,但如果你想要真正的知识,我强烈建议你阅读这篇论文。
ARIES 代表A algorithms for Recovery and I solation E xploiting Semantics。
这种技术的目的是双重的:
数据库必须回滚事务有多种原因:
有时(例如,在网络故障的情况下),数据库可以恢复事务。
这怎么可能?要回答这个问题,我们需要了解日志记录中存储的信息。
事务期间的每个操作(添加/删除/修改)都会产生一个日志。此日志记录由以下部分组成:
例如,如果操作是更新,UNDO 将存储更新之前更新元素的值/状态(物理 UNDO)或返回到先前状态的反向操作(逻辑 UNDO)**。
同样,有两种方法可以做到这一点。您可以在操作后存储元素的值/状态,也可以存储操作本身以重播它。
此外,磁盘上的每个页面(存储数据,而不是日志)都有上次修改数据的操作的日志记录 (LSN) 的 ID。
* LSN 的给出方式比较复杂,因为它与日志的存储方式相关联。但这个想法保持不变。
**ARIES 仅使用逻辑 UNDO,因为处理物理 UNDO 实在是一团糟。
注意:据我所知,只有 PostgreSQL 没有使用 UNDO。它使用垃圾收集器守护进程来删除旧版本的数据。这与 PostgreSQL 中数据版本控制的实现有关。
为了让您更好地了解,这里是由查询“UPDATE FROM PERSON SET AGE = 18;”生成的日志记录的可视化和简化示例。假设这个查询在事务 18 中执行。
每个日志都有一个唯一的 LSN。链接的日志属于同一个事务。日志按时间顺序链接(链表的最后一个日志是最后一个操作的日志)。
为了避免日志写入成为主要瓶颈,使用了日志缓冲区。
当查询执行器要求修改时:
提交事务时,意味着对于事务中的每个操作,步骤 1、2、3、4、5 都已完成。在事务日志中写入速度很快,因为它只是“在事务日志的某处添加日志”,而在磁盘上写入数据更为复杂,因为它“以一种可以快速读取数据的方式写入数据”。
出于性能原因,第 5 步可能会在提交之后完成,因为在发生崩溃的情况下,仍然可以使用 REDO 日志恢复事务。这称为不强制政策。
数据库可以选择一个 FORCE 策略(即第 5 步必须在提交之前完成)以降低恢复期间的工作量。
另一个问题是选择是否将数据逐步写入磁盘(STEAL 策略),或者缓冲区管理器是否需要等到提交命令一次写入所有内容(NO-STEAL)。STEAL 和 NO-STEAL 之间的选择取决于您想要什么:使用 UNDO 日志的快速写入和长时间恢复还是快速恢复?
以下是这些政策对恢复的影响的摘要:
好的,所以我们有很好的日志,让我们使用它们!
假设新实习生使数据库崩溃(规则 1:始终是实习生的错)。您重新启动数据库并开始恢复过程。
ARIES 通过三遍从崩溃中恢复:
在重做阶段,REDO 日志按时间顺序处理(使用 LSN)。
对于每个日志,恢复过程读取磁盘上包含要修改的数据的页面的 LSN。
如果 LSN(page_on_disk)>=LSN(log_record),则表示数据在崩溃之前已经写入磁盘(但该值被日志之后和崩溃之前发生的操作覆盖)所以什么都不做。
如果 LSN(page_on_disk)<LSN(log_record) 则更新磁盘上的页面。
甚至对于将要回滚的事务也完成了重做,因为它简化了恢复过程(但我确信现代数据库不会这样做)。
在恢复过程中,事务日志必须被警告恢复过程所做的操作,以便写入磁盘的数据与写入事务日志的数据同步。一个解决方案可能是删除正在撤消的事务的日志记录,但这非常困难。相反,ARIES 在事务日志中写入补偿日志,从逻辑上删除正在删除的事务的日志记录。
当事务被“手动”取消或由锁管理器(以停止死锁)或仅仅因为网络故障而取消时,则不需要分析通过。事实上,关于 REDO 和 UNDO 的信息可以在 2 个内存表中找到:
这些表由缓存管理器和事务管理器针对每个新事务事件进行更新。由于它们在内存中,因此当数据库崩溃时它们会被销毁。
分析阶段的工作是在崩溃后使用事务日志中的信息重新创建两个表。*为了加快分析过程,ARIES 提供了检查点的概念。思路是不定时的将事务表和脏页表的内容以及本次写入时的最后一个LSN写入磁盘,这样在分析过程中,只分析这个LSN之后的日志。
在写这篇文章之前,我知道这个主题有多大,我知道写一篇关于它的深入文章需要时间。原来我很乐观,花了比预期多两倍的时间,但我学到了很多。
如果您想对数据库有一个很好的了解,我建议您阅读研究论文“数据库系统架构”。这是一个很好的数据库介绍(110 页),非 CS 人员也可以阅读。这篇论文帮助我找到了这篇文章的计划,它不像我的文章那样专注于数据结构和算法,而是更多地关注架构概念。
如果您仔细阅读本文,您现在应该了解数据库的强大功能。由于这是一篇很长的文章,让我提醒您我们所看到的:
但是数据库包含更多的聪明才智。例如,我没有谈到一些棘手的问题,例如:
因此,当您必须在有缺陷的 NoSQL 数据库和坚如磐石的关系数据库之间进行选择时,请三思。不要误会我的意思,一些 NoSQL 数据库很棒。但他们还很年轻,并且回答了涉及一些应用程序的特定问题。
总而言之,如果有人问您数据库是如何工作的,您现在可以回答:
关于关系数据库如何工作,你学废了么?
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。