提问



我正在研究数据库,我正在研究关系数据库的一些局限性。


我认为大桌子的连接非常昂贵,但我不能完全确定原因。 DBMS需要做什么才能执行连接操作,瓶颈在哪里?

非规范化如何帮助克服这种费用?其他优化技术(例如索引)如何帮助?


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


与此相关,我想知道云服务数据库使用的非规范化方法,如BigTable和SimpleDB。请参阅此问题。

最佳参考


非规范化以提高性能?这听起来很有说服力,但它并没有水。


Chris Date与Ted Codd博士一起成为关系数据模型的最初支持者,对错误的反对规范化的论点没有耐心,并使用科学方法系统地拆除它们:他获得了大型数据库并且测试了这些断言。


我认为他是在关系数据库写作1988-1991 中编写的,但是本书后来被编入了数据库系统简介的第六版,它是 em>关于数据库理论和设计的权威性文本,在我写的第八版中,可能会在未来几十年保持印刷。 Chris Date是这个领域的专家,当时我们大多数人还在赤脚跑来跑去。


他发现:



  • 其中一些人举行特殊情况

  • 所有这些都无法为一般用途付清

  • 对于其他特殊情况,所有这些都显着恶化



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


实现结果涉及批量磁盘读取,这是练习中最昂贵的一个方面。相反,执行连接在逻辑上只需要检索键。在实践中,甚至不提取键值:键哈希值用于连接比较,减少多列连接的成本并从根本上降低涉及字符串比较的连接的成本。不仅更适合缓存,还有更少的磁盘读取功能。


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


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


重要的是要理解表扫描(在生成连接的过程中检查表中的每一行)在实践中很少见。只有在满足以下一个或多个条件时,查询优化器才会选择表扫描。



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

  • 连接列上没有合适的索引(如果加入这些列有意义,那么为什么它们没有被索引?修复它)

  • 在比较列之前需要类型强制(WTF?!修复它或回家)查看ADO.NET问题的结束说明

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



执行操作比不执行操作更昂贵。但是,执行错误的操作,强制进入无意义的磁盘I/O,然后在执行您真正需要的连接之前丢弃浮渣,很多更昂贵。即使预先计算了错误操作并且合理地应用了索引,仍然存在重大损失。非正规化以预先计算连接 - 尽管存在更新异常 - 是对特定连接的承诺。如果您需要不同的加入,则该承诺将耗费您 big 。


如果有人想提醒我这是一个不断变化的世界,我想你会发现更大的硬件数据集只会夸大Date的调查结果。


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


你错误地概括了 。有关在数据仓库方案中正确使用非规范化的更多信息,请参阅说明部分的末尾。


我也想回应



  加入只是笛卡儿的产品,有一些唇彩



什么负荷的bollocks。限制尽早应用,首先限制最多。你已经阅读了这个理论,但你还没理解它。通过查询优化器将联接视为作为谓词适用的笛卡尔产品 。这是一种符号表示(实际上是规范化),以促进符号分解,因此优化器可以生成所有等效变换并按成本和选择性对它们进行排序,以便它可以选择最佳查询计划。


您将获得优化器生成笛卡尔积的唯一方法是无法提供谓词:SELECT * FROM A,B





备注






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


除了索引和表扫描之外,确实存在各种其他策略,现代优化器将在生成执行计划之前将它们全部花费。


一条实用的建议:如果它可以用作外键然后对其进行索引,那么优化器的索引策略可用。


我曾经比MSSQL优化器更聪明。这改变了两个版本。现在它通常会教授 me 。从一个非常真实的意义上说,它是一个专家系统,在一个充分关闭的领域中编纂许多非常聪明的人的智慧,以便基于规则的系统是有效的。





Bollocks可能是不熟练的。我被要求不那么傲慢并且提醒数学并不是谎言。这是事实,但并非数学模型的所有含义都必须从字面上理解。如果你小心避免检查它们的荒谬性,那么负数的平方根非常方便(双关语)并且在你试图解释你的等式之前,确定你已经全部取消它们。


我如此野蛮地回应的原因是,措辞的陈述说明了这一点



  加入是笛卡儿产品......



这可能不是那个意思,但是写的是什么,而且它是绝对不真实的。笛卡儿产品是一种关系。连接是一种功能。更具体地说,连接是一种关系 - 使用空谓词,它将生成一个笛卡尔积,并检查它是否对数据库查询引擎进行了一次正确性检查,但没有人在实践中写入无约束连接,因为它们在教室外没有实际价值。


我之所以这样称呼是因为我不希望读者陷入将模型与模型混淆的古老陷阱中。模型是近似的,为了方便操作而故意简化。





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





有时非规范化是一个好主意



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


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


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


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


不要错误地将你的OLTP数据库(发生数据输入的数据库)进行非规范化。对于计费运行来说可能会更快但是如果这样做你会得到更新异常。曾经试图让读者的摘要停止发送你的东西?


这些天磁盘空间很便宜,所以要把自己打倒。但非规范化只是数据仓库的一部分。从预先计算的累计值中获得了更大的性能提升:每月总计,这类事情。它总是关于减少工作集。





类型不匹配的ADO.NET问题



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


VARCHAR到NVARCHAR是一个扩大的转换,所以它隐含发生 - 但告别索引,并祝你好运。





计算磁盘命中率(Rick James)



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


如果规范化模式导致JOINs大量命中磁盘,但等效的非规范化模式不必触及磁盘,则非规范化会赢得性能竞争。



  原作者的评论:现代数据库引擎非常擅长组织访问顺序,以最大限度地减少连接操作期间的缓存未命中。尽管如此,上述情况可能会被误解为暗示连接在大数据上必然存在问题。这将导致缺乏经验的开发人员做出糟糕的决策。


其它参考1


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


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



  • 批量连接,其中批量数据是等距的,确实非常便宜,并且如果哈希表不能缓存在内存中,则成本才会变得显着。无需索引。在连接的数据集之间进行等分区可以提供很大的帮助。

  • 排序合并连接的成本是由排序成本而不是合并驱动的 - 基于索引的访问方法实际上可以消除排序成本。

  • 索引上嵌套循环连接的开销由b-tree索引的高度和表块本身的访问权限驱动。它很快,但不适合批量连接。

  • 基于群集的嵌套循环连接要便宜得多,每个连接行需要更少的逻辑ALS - 如果连接的表都在同一个群集中,则通过连接行的共置,连接变得非常便宜。



数据库旨在加入,并且他们在如何操作方面非常灵活,并且通常非常高效,除非他们得到错误的连接机制。

其它参考2


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


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


如果操作正确,连接通常是最佳方式,可以对大量数据进行比较,组合或过滤。

其它参考3


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

其它参考4


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


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

其它参考5


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


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


关于规范化和非规范化的争论并没有结束,因为问题是巨大的。自然解决方案需要两种方法存在许多问题。


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

其它参考6


阐述别人的话,


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


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