何时以及为什么数据库联接(join)会变得昂贵？

Question

何时以及为什么数据库联接(join)会变得昂贵？

databaseperformancejoinrelational-databasedenormalization

407

我正在研究数据库，并且关注关系型数据库的一些局限性。

我了解到，连接大型表格是非常昂贵的，但我不完全清楚其中的原因。DBMS需要执行什么操作来执行连接操作？哪里是瓶颈？
反规范化如何帮助克服这种费用？其他优化技术（例如索引）如何帮助？

欢迎分享个人经验！如果您要发布资源链接，请避免使用维基百科。我已知道该去哪里找。

关于这一点，我对BigTable和SimpleDB等云服务数据库使用的反规范化方法很感兴趣。请参见此问题。

- Rik

3

你也在考虑它的好处吗？ ;) - David Aldridge

1

我正在寻找一种客观的（如果有这样的东西）比较。优点、缺点、以及其他方面。 - Rik

云计算的预渲染方法是基于能够在各种情况下进行投注，避免“错误连接”问题。谷歌有一些关于他们自己系统的白皮书。非常有趣 - 扩展特殊情况的适用性的方法。 - Peter Wone

@PeterWone - 能否提供一些这些论文的参考资料？顺便回答一下你个人资料中的问题，Android是开源的——至少部分是，所以极客们跳上了这辆车。在普通大众看来，他们被认为是技术先进的，于是像旅鼠一样跟随着谷歌紧密而激烈的拥抱！有人还记得贝塔玛克斯吗？更接近我自己的心（和年代），MySQL（没有FOREIGN KEY）如何成为（并保持）世界上最受欢迎的“R”DBMS，当它与PostgreSQL（没有本地Windows版本）和Firebird（开源惨案）甚至SQLite竞争时？ - Vérace

这个问题太宽泛了，因为不同的数据库供应商在JOIN实现方面存在显著差异。 - Rick James

显示剩余4条评论

7个回答

50

大多数评论者未注意到在复杂关系型数据库中可用的广泛连接方法，而非规范化者总是忽略了维护非规范化数据的更高成本。并非每个连接都基于索引，并且数据库具有许多优化算法和连接方法，旨在降低连接成本。

无论如何，连接的成本取决于其类型和其他几个因素。它可能根本不昂贵-以下是一些示例。

哈希连接，在其中批量数据进行等值连接非常便宜，只有当哈希表无法缓存在内存中时，成本才会变得重要。无需索引。在连接的数据集之间进行等分区可以很好地帮助。
排序合并连接的成本由排序的成本驱动，而不是合并的成本-基于索引的访问方法几乎可以消除排序的成本。
基于索引的嵌套循环连接的成本由b-tree索引的高度和表块本身的访问驱动。它很快，但不适合批量连接。
基于集群的嵌套循环连接要便宜得多，每个连接行需要较少的逻辑IO'S-如果所连接的表都位于同一个集群中，则通过连接的行定位变得非常便宜。

数据库就是为了连接而设计的，它们在如何进行连接方面非常灵活，并且通常表现出色，除非连接机制出错。

- David Aldridge

我认为关键在于“如果有疑问，就问你的数据库管理员”。现代数据库是复杂的生物，需要学习才能理解。自1996年以来，我一直在使用Oracle，跟上新功能是一项全职工作。SQLserver自2005年以来也取得了巨大进步。它不是一个黑匣子！ - Guy

3

根据我的经验，有太多的数据库管理员从未听说过哈希连接，或者认为它们是普遍的坏事情。 - David Aldridge

36

我认为整个问题的前提是错误的。在大型表上进行联接并不一定代价高昂。事实上，高效进行联接是关系型数据库存在的主要原因之一。对大型集合进行联接通常是昂贵的，但你很少想要将大表 A 的全部内容与大表 B 的全部内容进行联接。相反，您编写查询时应只使用每个表的重要行，使得通过联接实际保留的集合更小。

此外，正如 Peter Wone 所提到的，您可以提高效率，这样只有每个记录的重要部分需要在内存中，直到最终结果集被实现。此外，在具有许多联接的大型查询中，您通常希望从较小的表集开始，并逐步向上处理较大的表集，以便在尽可能长的时间内保留在内存中的集合尽可能小。

如果正确执行，联接通常是比较、合并或过滤大量数据的最佳方法。

- Joel Coehoorn

1

@joel。反之亦然。大型数据集的连接可能很昂贵，有时是必需的，但除非a）您可以处理所需的IO和RAM并且b）您不经常这样做，否则不要经常这样做。考虑材料化视图、报告系统、实时与CoB报告。 - Guy

15

瓶颈基本上总是磁盘I/O，更具体地说是随机磁盘I/O（相比之下，顺序读取相当快，并且可以使用预读取策略进行缓存）。

如果您跳转并读取大表的小部分，则连接可能会增加随机查找。但是，查询优化器会寻找那些内容并将其转换为顺序表扫描（丢弃不需要的行），如果认为那样更好。

单个非规范化表存在类似的问题 - 行很大，因此较少适合单个数据页。如果您需要位于另一个位置远的行（且由于大行大小而使它们更分散），则您将有更多的随机I/O。同样，可能会被强制执行表扫描以避免这种情况。但是，这一次，由于行大小较大，您的表扫描必须读取更多的数据。再加上您正在从单个位置复制数据到多个位置，RDBMS必须读取（和缓存）更多数据。

使用2个表，您还可以获得2个聚集索引，并且通常可以索引更多内容（由于更少的插入/更新开销），这可以极大地提高性能（主要是因为索引是（相对）小的，从磁盘快速读取（或便宜缓存），并减少您需要从磁盘中读取的表行数）。

关于连接的唯一开销来自于找到匹配行。 Sql Server使用3种不同类型的连接，主要基于数据集大小，以查找匹配行。如果优化器选择了错误的连接类型（由于不准确的统计信息，不充分的索引或仅是优化器错误或边缘情况），它可能会极大地影响查询时间。

循环连接对于（至少1个）小数据集相当便宜。
合并连接首先需要对两个数据集进行排序。但是，如果您在索引列上进行连接，则索引已经排序，无需进一步处理。否则，在排序时存在一些CPU和内存开销。

哈希连接需要内存(用于存储哈希表)和CPU(用于构建哈希表)，相对于磁盘I/O，这都比较快。然而，如果没有足够的RAM来存储哈希表，SQL Server将使用tempdb来存储部分哈希表和找到的行，然后一次只处理部分哈希表。与所有磁盘相关的事物一样，这很慢。

在最理想的情况下，它们不会导致磁盘I/O，因此从性能角度来看可以忽略不计。

总的来说，最坏的情况是，从x个联接表中读取相同数量的逻辑数据与从单个非规范化表中读取相同数量的逻辑数据速度应该是相同的，因为磁盘读取更小。要读取相同数量的物理数据，则可能会有一些轻微的开销。

由于查询时间通常由I/O成本主导，并且通过非规范化使数据大小不发生变化(减去一些非常微小的行开销)，所以仅仅将表合并在一起并不能带来太大的好处。根据我的经验，倾向于提高性能的非规范化类型是缓存计算值而不是读取需要计算这些值所需的10,000行。

- Mark Brackett

减少随机寻址：这是个好点子，尽管一个带有大缓存的好RAID控制器会执行电梯读写。 - Peter Wone

本帖中最佳答案！涵盖了对磁盘、CPU和RAM的最重要方面及其影响。然而，有关非规范化的结论仅适用于读取大量数据。现代应用程序通常处理分页请求并输出适度的结果。在这种情况下，非规范化胜出。 - Alex Klaus

3

你连接表的顺序非常重要。如果你有两个数据集，请尽量以最小的数据集优先构建查询，以减少查询需要处理的数据量。

对于某些数据库来说，这并不重要，例如MS SQL大多数情况下都知道正确的连接顺序。但对于一些数据库（如IBM Informix），连接顺序就很重要了。

- Ilya Kochetov

1

一般来说，一个合适的查询优化器不会受到连接或表格列出的顺序的影响，并且将自行确定执行连接的最有效方式。 - David Aldridge

7

MySQL、Oracle、SQL Server、Sybase、PostgreSQL 等数据库在连接操作中对于表的顺序不作要求。我曾经使用过 DB2，据我所知它也不关心你把它们放在什么样的顺序里。但是这并不是通用情况下有帮助的建议。 - Matt Rogish

MSSQL在其优化器中使用修剪算法来防止分析性麻痹（这似乎也会发生在机器上），这有时可能使联接序列变得重要。 - Peter Wone

是的，有一些边缘情况会“有点”重要（连接许多表），但一般来说，这并不是大多数 SQL 开发人员应该花费任何脑力的事情。我更希望他们首先关注索引和查询优化。 - Matt Rogish

1

@Matt，我曾经看到Oracle 9i通过调整连接顺序执行非常不同的优化和查询计划。也许从10i版本开始这种情况已经改变了？ - Camilo Díaz Repka

显示剩余2条评论

0

在考虑连接的复杂度类时，决定是否进行反规范化或规范化是一个相当简单的过程。例如，当查询为O(k log n)（其中k与所需输出量相关）时，我倾向于使用规范化来设计我的数据库。

一种简单的反规范化和优化性能的方法是考虑如何更改规范化结构会影响到反规范化结构。然而，这可能需要事务逻辑来处理反规范化结构，因此可能会出现问题。

规范化和反规范化的争论不会结束，因为问题很多。有许多问题需要同时采用这两种方法才能得到自然解决方案。

作为一般规则，我总是存储规范化结构和可以重建的反规范化缓存。最终，这些缓存可以帮助我解决未来的规范化问题。

- MathGladiator

-8

深入探讨他人所说的话，

连接就是一些带有唇彩的笛卡尔积。 {1,2,3,4}X{1,2,3} 将给我们12个组合（nXn=n^2）。这个计算出的集合作为一个参考，在其上应用条件（例如左右两边都是2或3），数据库管理系统将条件应用于给出与之匹配的条件。实际上，它更加优化，但问题是相同的。集合大小的变化会以指数形式增加结果大小。所有消耗的内存和CPU周期都受到指数级影响。

当我们非规范化时，我们完全避免了这种计算，想象一下每一页书上都贴着有颜色的便签，您可以在不使用参考的情况下推断信息。我们付出的代价是牺牲了DBMS的本质（数据的最佳组织）。

- questzen

4

这篇文章很好地阐述了为什么应该让数据库管理系统执行连接操作——因为数据库管理系统的设计师们一直在思考这些问题，并且想出了比计算机科学101方法更有效的方式。 - David Aldridge

2

@David：同意。数据库管理系统优化器程序员是一些非常聪明的人。 - Matt Rogish

1

这个答案是不正确的。如果你的查询针对一个规范化、索引化的数据库，并且有任何类型的过滤器或连接条件，优化器将会找到一种避免笛卡尔积并最小化内存使用和 CPU 循环的方法。如果你确实想要选择笛卡尔积，那么在规范化或非规范化的数据库中使用的内存是相同的。 - rileymcdowell

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Wone · Accepted Answer

反规范化以提高性能？听起来很有说服力，但事实并非如此。

克里斯·戴特（Chris Date）与特德·科德博士一起成为关系数据模型的最初倡导者，在对抗反规范化的错误论证上耐心耗尽后，他运用科学方法进行了系统的破坏：他获得了大型数据库并测试了这些主张。

我认为他在《关系数据库写作1988-1991》中写了这个内容，但这本书后来被编入第六版的《数据库系统概论》中，后者是关于数据库理论和设计的权威文本，在我写作本文时已经是第八版，并有可能保持出版数十年。当我们中的大多数人还赤脚奔跑时，克里斯·戴特就是这个领域的专家。

他发现：

其中一些适用于特殊情况
所有这些都无法在通用情况下得到回报
对于其他特殊情况，所有这些情况都明显更糟

这一切归结为减少工作集大小。涉及正确选择的键和正确设置索引的连接是便宜的，而不是昂贵的，因为它们允许在行材料化之前对结果进行大量修剪。

将结果材料化涉及批量磁盘读取，这是整个过程中最昂贵的方面。相比之下，执行连接逻辑上仅需要检索关键字。实际上，甚至不会提取关键值：键哈希值用于连接比较，缓解了多列连接的成本，并极大地减少了涉及字符串比较的连接成本。不仅更多的内容可以适应高速缓存，还可以减少磁盘读取量。

此外，优秀的优化器将选择最严格的条件并在执行连接之前应用它，非常有效地利用基数高的索引上连接的高选择性。

诚然，这种类型的优化也可以应用于反规范化的数据库，但通常想要反规范化模式的人在设置索引时（如果有的话）通常不考虑基数问题。

重要的是要理解，在实践中，表扫描（在生成连接期间检查表中每一行）很少出现。只有在以下情况下，查询优化器才会选择表扫描：

关系中的行数少于200行（在这种情况下，扫描会更便宜）
连接列上没有合适的索引（如果可以在这些列上连接，则为什么不索引？修复它）
在比较列之前需要类型强制转换（WTF？！修理或回家）请参阅ADO.NET问题的末尾注释
比较的其中一个参数是表达式（没有索引）

进行操作比不进行操作更昂贵。然而，执行 错误的 操作，被迫进行无意义的磁盘 I/O，然后在执行实际需要的连接之前丢弃冗余数据，这是更加昂贵的。即使 "错误" 操作已经预计算并且索引已经合理应用，仍然存在重大惩罚。将数据去规范化以预先计算连接,尽管会出现更新异常，但是这是对特定连接的承诺。如果您需要一个不同的连接，则此承诺将花费您高额成本。
如果有人想提醒我这是一个变化的世界，那么我认为你会发现更大的数据集和更强大的硬件只会夸大 Date 的发现结果。
对于所有在计费系统或垃圾邮件生成器（真丢人）上工作的人们，他们不屑地把手放在键盘上告诉我，去规范化更快，对不起，但是您处于一种特殊情况下—具体来说，您处理所有数据，按顺序。这不是一般情况，你们采取的策略是正确的。
您没有正当理由将其错误地概括。有关数据仓库方案中去规范化使用的更多信息，请参见备注部分的末尾。
我还想回应引用块中的话:
“连接只是带些唇彩的笛卡尔积。”
真是一派胡言。限制要尽可能地早应用，最严格的先应用。你读过理论，但你没有理解它。连接仅被视为 “适用于谓词的笛卡尔乘积”，仅由查询优化器处理。这是符号表示（实际上是规范化），以便于符号分解，使优化器能够生成所有等效转换，并通过成本和选择性对它们进行排名，以便选择最佳查询计划。
您唯一能让优化器产生笛卡尔积的方式是未提供谓词：SELECT * FROM A,B 注释： David Aldridge 提供了一些重要的额外信息。除了索引和表扫描之外，确实有各种其他策略，并且现代优化器将在生成执行计划之前对它们进行成本估算。一个实用的建议：如果可以用作外键，则对其进行索引，以便优化器可用索引策略。我曾经比 MSSQL 优化器聪明。两个版本之前就改变了。现在通常是它在教导我。它在非常真实的意义上是一种专家系统，将许多非常聪明的人的所有智慧在一个足够封闭的领域进行编码，以便规则为基础的系统有效。“胡说八道”可能有些不得体。我被要求少一点傲慢，并且被提醒数学并不会说谎。这是正确的，但并不是数学模型的所有含义都应该被字面解释。如果你小心避免检查它们的荒谬性（双关语），并确保在解释方程之前将它们全部消除，那么负数的平方根非常有用。我之所以如此激烈地回应是因为该语句所述的内容是：“连接是笛卡尔积……”这可能不是作者原意，但这就是写下来的，而且这是明显错误的。笛卡尔积是一个关系，连接是一个函数，更具体地说，连接是一个产生关系值的函数。使用空谓词，它将产生笛卡尔积，并检查它是否确实如此是数据库查询引擎的一项正确性检查。但是在实践中没有人编写无限制的连接，因为除了教室外，它们没有任何实际价值。我指出这一点是因为我不希望读者陷入将模型与被建模事物混淆的古老陷阱中。模型是一种近似，专门简化以便于方便操作。表扫描连接策略的选择截止时间可能因数据库引擎而异。它受多种实现决策的影响，例如树节点填充因子、键值大小和算法的微妙之处，但总体而言，高性能索引的执行时间为k log n + c。 C项是固定的开销，主要由设置时间组成，曲线的形状意味着与线性搜索相比，直到n达到几百时才能获得回报。有时候非规范化是一个好主意。非规范化是对特定连接策略的一项承诺。正如前面提到的，这会干扰其他连接策略。但如果你有大量的磁盘空间、可预测的访问模式，并且倾向于处理大部分或全部数据，则预先计算连接可以非常有价值。您还可以确定操作通常使用的访问路径并预先计算所有这些访问路径的连接。这是数据仓库背后的原理，至少在那些由知道自己在做什么的人构建的数据仓库中是这样的，而不是为了符合流行语的要求而构建的。一个正确设计的数据仓库通过定期将其从归一化的交易处理系统转换出来而产生。这种操作和报告数据库的分离具有非常理想的效果，可以消除OLTP和OLAP（在线事务处理即数据输入以及在线分析处理即报告）之间的冲突。这里一个重要的问题是，除了定期更新之外，数据仓库是只读的。这使得更新异常的问题无意义。请勿将您的OLTP数据库（数据输入发生的数据库）去规范化。这可能会加快账单运行速度，但如果这样做，您将会遇到更新异常。曾经试过让《读者文摘》停止给你发送杂志吗？如今，磁盘空间很便宜，所以尽管放心使用。但规范化只是数据仓库中的一部分。更大的性能提升来自于预计算的滚动值：例如月度总数等。这永远都是关于减少工作集。 ADO.NET类型不匹配问题假设您有一个包含索引列类型为varchar的SQL Server表，并使用AddWithValue传递参数约束对此列进行查询。C#字符串是Unicode，因此推断的参数类型将为NVARCHAR，而不是VARCHAR。 VARCHAR到NVARCHAR是一种扩展转换，因此它会隐式发生 - 但是说再见索引，并祝你好运弄清原因。 "计算磁盘访问次数"（Rick James）如果所有内容都缓存在RAM中，JOIN操作相当便宜。也就是说，规范化并没有太多性能惩罚。如果“规范化”模式导致JOIN操作经常访问磁盘，而等效的“去规范化”模式不需要访问磁盘，那么去规范化会在性能竞争中获胜。原作者的评论：现代数据库引擎非常擅长组织访问序列以最小化联接操作期间的缓存未命中。上面这一点虽然正确，但可能被曲解为联接对大型数据必然具有问题。这将导致经验不足的开发人员做出错误决策。