数据库连接何时以及为何昂贵？

StackOverflow https://stackoverflow.com/questions/173726

题

我正在对数据库进行一些研究，并且正在研究关系数据库的一些限制。

我发现大表的连接非常昂贵，但我不完全确定为什么。DBMS需要做什么来执行连接操作，瓶颈在哪里？
非规范化如何帮助克服这一费用？其他优化技术（例如索引）有何帮助？

欢迎个人经历！如果您要发布资源链接，请避免使用维基百科。我已经知道在哪里可以找到它了。

与此相关，我想知道 BigTable 和 SimpleDB 等云服务数据库使用的非规范化方法。看 这个问题.

有帮助吗？

解决方案

非规范化以提高性能？听起来很有说服力，但站不住脚。

Chris Date 与 Ted Codd 博士一起是关系数据模型的最初支持者，他对反对标准化的错误论点失去了耐心，并使用科学方法系统地推翻了它们：他拥有庞大的数据库并且 经测试 这些断言。

我认为他写在 1988-1991 年关系数据库著作 但这本书后来被编入了第六版 数据库系统简介, ，即 这 关于数据库理论和设计的权威文本，在我撰写时已是第八版，并且可能在未来几十年内继续印刷。当我们大多数人还赤脚奔跑时，克里斯·戴特（Chris Date）就是这个领域的专家。

他发现：

  • 其中一些适用于特殊情况
  • 所有这些都无法满足一般用途
  • 对于其他特殊情况，所有这些都明显更糟

这一切都归结于减小工作集的大小。涉及正确选择的键和正确设置的索引的连接是便宜的，而不是昂贵的，因为它们允许对结果进行显着的修剪 前 这些行被具体化了。

实现结果涉及批量磁盘读取，这是该练习中成本最高的一个数量级。相比之下，执行连接在逻辑上只需要检索 键. 。实际上，甚至连键值都不会被获取：键哈希值用于连接比较，减轻多列连接的成本，并从根本上降低涉及字符串比较的连接成本。不仅会更适合缓存，而且需要执行的磁盘读取也会少得多。

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

诚然，这种类型的优化也可以应用于非规范化数据库，但是那些人 想 当（如果）他们设置索引时，非规范化模式通常不会考虑基数。

重要的是要理解表扫描（在生成连接的过程中检查表中的每一行）在实践中很少见。仅当满足以下一项或多项条件时，查询优化器才会选择表扫描。

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

执行某项操作比不执行该操作的成本更高。然而，执行 错误的 操作，被迫进行无意义的磁盘 I/O，然后在执行您真正需要的连接之前丢弃糟粕，是 很多 更贵。即使预先计算了“错误”的操作并且合理地应用了索引，仍然存在显着的惩罚。非规范化以预先计算连接（尽管会带来更新异常）是对特定连接的承诺。如果您需要一个 不同的 加入，这个承诺会让你付出代价 大的.

如果有人想提醒我这是一个不断变化的世界，我想你会发现更糟糕的硬件上更大的数据集只会夸大 Date 发现的传播范围。

对于所有从事计费系统或垃圾邮件生成器工作的人（为你们感到羞耻），并愤怒地把手放在键盘上告诉我，你们知道非规范化更快的事实，抱歉，但你们生活在一个特殊的环境中。案例 - 具体来说，您处理的案例 全部 的数据，按顺序。这不是一般情况，而且你 是 你的策略是合理的。

你是 不是 错误地概括它是合理的。有关在数据仓库场景中适当使用非规范化的更多信息，请参阅注释部分的末尾。

我也想回复一下

连接只是带有一些唇彩的笛卡尔积

真是一堆废话。尽早实施限制，最严格的首先实施。你读过这个理论，但你还没有理解它。连接是 治疗过的 作为“谓词适用的笛卡尔积” 仅有的 由查询优化器。这是一种符号表示（实际上是标准化），以促进符号分解，以便优化器可以生成所有等效的转换，并按成本和选择性对它们进行排序，以便它可以选择最佳查询计划。

让优化器生成笛卡尔积的唯一方法是不提供谓词： SELECT * FROM A,B

笔记

大卫·奥尔德里奇提供了一些重要的附加信息。

除了索引和表扫描之外，确实还有多种其他策略，现代优化器将在生成执行计划之前将它们全部消耗殆尽。

一个实用的建议：如果可以作为外键则对其建立索引，这样索引策略就是 可用的 给优化器。

我曾经比MSSQL优化器更聪明。两个版本前就改变了。现在一般都教 我. 。从真正的意义上来说，它是一个专家系统，将许多非常聪明的人的所有智慧编入一个足够封闭的领域，使得基于规则的系统是有效的。

“胡说八道”可能有些不机智。他们要求我不要那么傲慢，并提醒我数学不会说谎。这是事实，但并非数学模型的所有含义都必须从字面上理解。如果你小心地避免检查它们的荒谬性（双关语），并确保在尝试解释方程之前将它们全部取消，那么负数的平方根会非常方便。

我之所以做出如此野蛮的回应，是因为该声明的措辞是这样的：

加入 是 笛卡尔积...

这可能不是本意，但它 是 所写的内容，绝对是不真实的。笛卡尔积是一种关系。连接是一个函数。更具体地说，连接是关系值函数。使用空谓词，它将产生笛卡尔积，检查它是否这样做是对数据库查询引擎的正确性检查，但在实践中没有人编写无约束连接，因为它们在课堂之外没有实际价值。

我之所以这么说，是因为我不想让读者陷入将模型与建模对象混淆的古老陷阱。模型是一种近似值，是为了方便操作而故意简化的。

表扫描连接策略选择的截止点可能因数据库引擎而异。它受到许多实现决策的影响，例如树节点填充因子、键值大小和算法的微妙之处，但一般来说，高性能索引的执行时间为 k 日志 n + C. 。C 项是固定开销，主要由设置时间组成，并且曲线的形状意味着您不会获得回报（与线性搜索相比），直到 n 有数百个。

有时非规范化是个好主意

非规范化是对特定连接策略的承诺。如前所述，这会干扰 其他 加入策略。但是，如果您拥有大量磁盘空间、可预测的访问模式，并且倾向于处理大部分或全部磁盘空间，那么预先计算联接可能非常值得。

您还可以找出您的操作通常使用的访问路径，并预先计算这些访问路径的所有联接。这是数据仓库背后的前提，或者至少当它们是由那些知道为什么要做他们正在做的事情的人构建的，而不仅仅是为了遵守流行语时。

正确设计的数据仓库是通过标准化事务处理系统的批量转换定期生成的。操作和报告数据库的这种分离具有消除OLTP和OLAP（在线事务处理，即数据输入和在线分析处理，即报告）之间的冲突的非常理想的效果。

这里重要的一点是，除了定期更新之外，数据仓库还 只读. 。这使得更新异常的问题变得毫无意义。

不要错误地对 OLTP 数据库（发生数据输入的数据库）进行非规范化。计费运行可能会更快，但如果这样做，您将收到更新异常。是否曾经尝试过让《读者文摘》停止向您发送内容？

如今磁盘空间很便宜，因此请淘汰自己。但非规范化只是数据仓库故事的一部分。更大的性能提升来自于预先计算的汇总值：每月总计，诸如此类的事情。它是 总是 关于减少工作集。

ADO.NET 类型不匹配问题

假设您有一个 SQL Server 表，其中包含 varchar 类型的索引列，并且您使用 AddWithValue 来传递限制对此列的查询的参数。C# 字符串是 Unicode，因此推断的参数类型将为 NVARCHAR，这与 VARCHAR 不匹配。

VARCHAR 到 NVARCHAR 是一种扩大的转换，因此它是隐式发生的 - 但请告别索引，祝你好运找出原因。

“计算磁盘点击次数”（里克·詹姆斯）

如果所有内容都缓存在 RAM 中， JOINs 相当便宜。也就是说，归一化没有太多作用 绩效惩罚.

如果“标准化”模式导致 JOINs 大量访问磁盘，但等效的“非规范化”模式不必访问磁盘，那么非规范化就赢得了性能竞争。

原作者评论：现代数据库引擎非常擅长组织访问顺序，以最大限度地减少连接操作期间的缓存未命中。上述内容虽然正确，但可能会被误解为暗示连接在大数据上必然会带来昂贵的问题。这将导致缺乏经验的开发人员做出糟糕的决策。

其他提示

大多数评论者没有注意到的是，复杂的 RDBMS 中可以使用多种连接方法，而非规范化器总是掩盖维护非规范化数据的较高成本。并非每个联接都基于索引，并且数据库具有许多用于联接的优化算法和方法，旨在降低联接成本。

无论如何，连接的成本取决于其类型和其他一些因素。它根本不需要很昂贵——举一些例子。

  • 散列连接（其中对大量数据进行等连接）确实非常便宜，并且只有当散列表无法缓存在内存中时，成本才会变得显着。无需索引。连接数据集之间的等分区会很有帮助。
  • 排序合并连接的成本是由排序成本而不是合并成本决定的——基于索引的访问方法实际上可以消除排序成本。
  • 索引上嵌套循环连接的成本由 B 树索引的高度和表块本身的访问决定。它速度很快，但不适合批量连接。
  • 基于集群的嵌套循环连接要便宜得多，每个连接行所需的逻辑 IO 更少——如果连接的表都在同一个集群中，那么通过连接行的共置，连接变得非常便宜。

数据库被设计为连接，并且它们的执行方式非常灵活，并且通常非常高性能，除非它们的连接机制错误。

我认为整个问题是基于错误的前提。大型表上的连接不必然是昂贵的。实际上，有效地进行连接是关系数据库存在的主要原因之一。加入大型集通常很昂贵，但是很少想要将大表A的全部内容与大表B的全部内容一起加入。相反，您编写的查询使得仅使用每个表的重要行，并且连接保留的实际集保持较小。

此外，您还具有Peter Wone提到的效率，因此在实现最终结果集之前，只有每条记录的重要部分需要在内存中。此外，在具有许多联接的大型查询中，您通常希望从较小的表集开始，然后逐步使用大表集，以便保留在内存中的集尽可能地尽可能小。

如果操作正确，联接通常是最佳方式来比较，组合或过滤大量数据。

瓶颈还蛮多的 总是 磁盘 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 成本主导，并且数据大小不会因非规范化而改变（减去一些非常小的行开销），因此仅将表合并在一起并不会带来巨大的好处。倾向于提高性能的非规范化类型 IME 是缓存计算值，而不是读取计算它们所需的 10,000 行。

您加入表格的顺序非常重要。如果您有两组数据，请尝试以某种方式构建查询，以便首先使用最小的数据来减少查询必须处理的数据量。

对于某些数据库而言无关紧要，例如MS SQL在大多数情况下确实知道正确的连接顺序。 对于某些人（如IBM Informix），订单会产生重大影响。

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

对异常化和优化性能的简单方法是考虑规范化结构的更改如何影响非规范化结构。然而，它可能会有问题，因为它可能需要事务逻辑来处理非规范化的结构化。

关于正常化和非规范化的争论不会结束，因为问题是巨大的。自然解决方案需要两种方法存在许多问题。

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

阐述别人所说的话，

加入只是具有一些唇彩的笛卡儿产品。 {1,2,3,4} X {1,2,3}会给我们12个组合（nXn = n ^ 2）。此计算集充当应用条件的参考。 DBMS应用条件（如左右两个都是2或3）给出匹配条件。实际上它更优化但问题是相同的。对集合大小的更改会以指数方式增加结果大小。消耗的内存量和CPU周期均以指数形式实现。

当我们非规范化时，我们完全避免这种计算，想想有一个彩色粘性，附在你书的每一页上。您可以使用引用推断出信息。我们付出的代价是我们正在妥协DBMS的本质（数据的最佳组织）

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top