database - 数据库连接何时以及为何成本高昂？

Question

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

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

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

与此相关，我想知道 BigTable 和 SimpleDB 等云服务数据库使用的非规范化方法。见 this question .

Answer 1

非规范化以提高性能？这听起来很有说服力，但它不成立。

Chris Date 与 Ted Codd 博士一起是关系数据模型的最初支持者，他对反对规范化的错误观点失去了耐心，并使用科学方法系统地摧毁了它们:他获得了大型数据库并测试了这些断言。

我认为他是在 Relational Database Writings 1988-1991 中写的，但这本书后来被编入了数据库系统导论的第六版，这是数据库理论和设计的权威教材，在我写的第八版中，可能会保留下来在 future 几十年打印。当我们大多数人还赤脚跑来跑去时，Chris Date 是该领域的专家。

他发现:

其中一些适用于特殊情况

所有这些都无法支付一般用途

对于其他特殊情况，所有这些都明显更糟

这一切都回到了减轻工作集的大小。包含正确选择的键和正确设置的索引的连接是便宜的，而不是昂贵的，因为它们允许在行实现之前对结果进行大量修剪。

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

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

诚然，这种类型的优化也可以应用于非规范化数据库，但是那些想要对模式进行非规范化的人通常不会在(如果)设置索引时考虑基数。

了解表扫描(在生成连接的过程中检查表中的每一行)在实践中很少见，了解这一点很重要。仅当以下一项或多项成立时，查询优化器才会选择表扫描。

关系中的行少于 200 行(在这种情况下，扫描会更便宜)

连接列上没有合适的索引(如果连接这些列有意义，那么为什么不将它们编入索引？修复它)

在比较列之前需要类型强制转换(WTF？!修复它或回家)请参阅 ADO.NET 问题的结尾说明

比较的参数之一是表达式(无索引)

执行操作比不执行更昂贵。但是，执行错误的操作，被迫进行无意义的磁盘 I/O，然后在执行真正需要的连接之前丢弃渣滓，代价要高得多。即使预先计算了“错误”的操作并且合理地应用了索引，仍然存在显着的惩罚。非规范化以预先计算连接 - 尽管需要更新异常 - 是对特定连接的 promise 。如果你需要一个不同的加入，那么这个 promise 会让你付出很大的代价。

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

对于所有在计费系统或垃圾邮件生成器上工作的人(真为你感到羞耻)并且愤怒地 Handlebars 放在键盘上告诉我你知道非规范化更快的事实，对不起，但你生活在一个特殊的地方案例 - 特别是，您按顺序处理所有数据的案例。这不是一般情况，您的策略是合理的。

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

我也想回复

Joins are just cartesian products with some lipgloss

真是一堆废话。尽早应用限制，最先应用限制。你已经阅读了理论，但你还没有理解它。联接仅被查询优化器视为“谓词适用的笛卡尔积”。这是一种符号表示(实际上是一种规范化)以促进符号分解，因此优化器可以生成所有等效转换并按成本和选择性对它们进行排名，以便它可以选择最佳查询计划。

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

David Aldridge 提供了一些重要的附加信息。

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

一条实用的建议:如果它可以用作外键，则对其进行索引，以便优化器可以使用索引策略。

我曾经比 MSSQL 优化器更聪明。这在两个版本前发生了变化。现在它通常教我。在非常真实的意义上，它是一个专家系统，它在一个足够封闭的领域内汇集了许多非常聪明的人的所有智慧，因此基于规则的系统是有效的。

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

我如此野蛮地回应的原因是声明的措辞是这样说的

Joins are cartesian products...

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

我之所以这么说是因为我不希望读者陷入将模型与建模的事物混淆的古老陷阱。模型是一种近似值，为方便操作而特意简化。

选择表扫描连接策略的截止点可能因数据库引擎而异。它受许多实现决策的影响，例如树节点填充因子、键值大小和算法的微妙之处，但广义上讲，高性能索引的执行时间为 k log n + c。 C 项是主要由设置时间构成的固定开销，曲线的形状意味着在 n 达到数百个之前您不会得到返回(与线性搜索相比)。

有时非规范化是个好主意

非规范化是对特定连接策略的 promise 。如前所述，这会干扰其他连接策略。但是，如果您有大量磁盘空间、可预测的访问模式以及处理大部分或全部磁盘空间的趋势，那么预先计算连接可能非常值得。

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

设计合理的数据仓库是通过从规范化的事务处理系统中进行批量转换而定期生成的。操作和报告数据库的这种分离对于消除 OLTP 和 OLAP(在线事务处理，即数据输入，以及在线分析处理，即报告)之间的冲突具有非常理想的效果。

这里重要的一点是，除了定期更新之外，数据仓库是只读的。这使得更新异常的问题没有实际意义。

不要犯非规范化 OLTP 数据库(发生数据输入的数据库)的错误。计费运行可能会更快，但如果你这样做，你会得到更新异常。曾经试图让读者文摘停止向您发送东西吗？

这些天磁盘空间很便宜，所以让自己振作起来。但非规范化只是数据仓库故事的一部分。更大的性能提升来自预先计算的汇总值:每月总计，诸如此类。它总是关于减少工作集。

类型不匹配的 ADO.NET 问题

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

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

“计算磁盘命中数”(里克·詹姆斯)

如果所有内容都缓存在 RAM 中， JOINs比较便宜。也就是说，规范化没有太多的性能损失。

如果“规范化”模式导致 JOINs多次访问磁盘，但等效的“非规范化”模式不必访问磁盘，然后非规范化赢得了性能竞争。

Comment from original author: Modern database engines are very good at organising access sequencing to minimise cache misses during join operations. The above, while true, might be miscontrued as implying that joins are necessarily problematically expensive on large data. This would lead to cause poor decision-making on the part of inexperienced developers.