377

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

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

欢迎亲身体验！如果您要发布资源链接，请避免使用 Wikipedia。我知道在哪里可以找到那个了。

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

4

7 回答 7

500

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

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

我认为他在Relational Database Writings 1988-1991中写了这本书，但这本书后来被纳入数据库系统简介的第六版，这是关于数据库理论和设计的权威书籍，在我写的第八版中并且可能会保留印刷数十年。当我们大多数人还赤脚跑来跑去的时候，Chris Date 是这个领域的专家。

他发现：

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

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

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

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

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

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

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

执行一个操作比不执行它更昂贵。但是，执行错误的操作，被迫进行无意义的磁盘 I/O，然后在执行真正需要的连接之前丢弃渣滓，代价要高得多。即使预先计算了“错误”操作并且已合理应用索引，仍然存在重大损失。预先计算连接的非规范化 - 尽管需要更新异常 - 是对特定连接的承诺。如果您需要不同的加入，那么该承诺将使您付出巨大的代价。

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

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

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

我也想回复

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

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

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

笔记

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

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

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

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

“胡说八道”可能是不圆滑的。我被要求不要那么傲慢，并提醒我数学不会说谎。这是真的，但并非数学模型的所有含义都必须按字面意思理解。如果您仔细避免检查它们的荒谬性（双关语）并确保在尝试解释方程之前将它们全部取消，则负数的平方根非常方便。

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

联接是笛卡尔积...

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

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

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

有时非规范化是个好主意

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

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

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

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

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

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

类型不匹配的 ADO.NET 问题

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

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

“计算磁盘命中数”（里克·詹姆斯）

如果一切都缓存在 RAM 中，JOINs则相当便宜。也就是说，归一化并没有太大的性能损失。

如果“规范化”模式导致JOINs大量磁盘命中，但等效的“非规范化”模式不必命中磁盘，则非规范化赢得了性能竞争。

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

于 2008-10-06T12:16:04.003 回答
48

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

在任何情况下，连接的成本取决于其类型和其他一些因素。它根本不需要昂贵 - 一些例子。

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

数据库被设计为连接，它们在如何连接方面非常灵活，并且通常非常高效，除非它们的连接机制错误。

于 2008-10-06T12:48:38.930 回答
31

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

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

如果操作得当，连接通常是比较、组合或过滤大量数据的最佳方式。

于 2008-10-06T13:53:32.857 回答
14

瓶颈几乎总是磁盘 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 行。

于 2008-11-03T23:33:32.180 回答
3

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

对于某些数据库，这无关紧要，例如 MS SQL 在大多数情况下确实知道正确的连接顺序。对于某些人（如 IBM Informix）来说，顺序决定了一切。

于 2008-10-06T09:58:51.877 回答
0

当您考虑连接的复杂性类别时，决定是去规范化还是规范化是一个相当简单的过程。例如，当查询为 O(k log n) 时，我倾向于使用规范化设计我的数据库，其中 k 与所需的输出幅度相关。

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

由于问题非常广泛，因此关于规范化和非规范化的辩论不会结束。在许多问题中，自然解决方案需要这两种方法。

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

于 2009-09-20T12:25:28.203 回答
-8

详细说明其他人所说的，

加入只是带有一些唇彩的笛卡尔产品。{1,2,3,4}X{1,2,3} 会给我们 12 种组合 (nXn=n^2)。此计算集充当应用条件的参考。DBMS 应用条件（例如左右均为 2 或 3）为我们提供匹配条件。实际上它更优化，但问题是一样的。对集合大小的更改将成倍增加结果大小。消耗的内存量和 CPU 周期都以指数形式影响。

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

于 2008-10-06T11:09:55.870 回答