什么时候以及为什么数据库连接昂贵?

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

与Ted Codd博士合作的Chris Date是关系数据模型的最初支持者,他对反对标准化的误传论点失去了耐心,并用科学的方法系统地推翻了它们:他得到了大量的数据库和 测试 这些断言。

我想是他写的 关系数据库写作1988-1991 但这本书后来被卷进了第六版 数据库系统简介 ,这就是 这个 关于数据库理论和设计的权威文本,在我写的第八版中,可能会在未来几十年内保持印刷。克里斯·达特是这个领域的专家,当时我们大多数人仍然赤脚跑步。

他发现:

• 其中一些是为特殊情况保留的
• 所有这些都不能用于一般用途
• 对于其他特殊情况,所有这些情况都明显更糟。

这一切又回到了减少工作集的大小。包含正确选择的键和正确设置的索引的联接是便宜的,而不是昂贵的,因为它们允许对结果进行显著的修剪。 之前 这些行被具体化了。

具体化结果涉及批量磁盘读取,这是按数量级计算的最昂贵的方面。相比之下,执行联接在逻辑上只需要检索 钥匙 . 在实践中,甚至不提取键值:键哈希值用于联接比较,降低了多列联接的成本,并从根本上降低了涉及字符串比较的联接的成本。不仅可以在高速缓存中容纳更多的数据,而且可以进行更少的磁盘读取。

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

诚然,这种类型的优化也可以应用于非规范化的数据库,但这类人 希望 要使模式非规范化,通常在设置索引时不考虑基数。

重要的是要了解表扫描(在生成联接过程中检查表中的每一行)在实践中是罕见的。查询优化程序将仅在以下一个或多个保持不变时选择表扫描。

• 关系中的行数少于200(在这种情况下,扫描将更便宜)
• 在联接列上没有合适的索引(如果在这些列上联接是有意义的,那么为什么不为它们编制索引呢?修复它)
• 在比较列之前需要强制类型(wtf?!修好它或回家) 有关ADO.NET问题,请参阅尾注。
• 比较的一个参数是表达式(没有索引)

执行操作比不执行操作要昂贵。但是,执行 错误的 在执行您真正需要的连接之前,被强制进入无意义的磁盘I/O,然后丢弃渣滓的操作是 许多的 更贵。即使预先计算出“错误”操作并合理应用了索引,仍然会受到严重的惩罚。对一个连接进行非规范化预计算——尽管需要更新异常——是对一个特定连接的承诺。如果你需要 不同的 加入吧,这项承诺会让你付出代价的 大的 .

如果有人想提醒我这是一个不断变化的世界,我想你会发现Gruntier硬件上更大的数据集只是夸大了日期发现的传播。

对于所有在计费系统或垃圾邮件生成器上工作的人(对你来说很遗憾),他们愤怒地用手按键盘告诉我,你知道非规范化速度更快,对不起,但你生活在一个特殊的情况下——特别是你处理的情况。 全部的 数据的顺序。这不是一般情况,你 是 你的策略是合理的。

你是 不 错误地概括它是正当的。有关在数据仓库场景中适当使用非规范化的更多信息,请参阅“说明”部分的末尾。

我还想回复

连接只是笛卡尔积和一些唇彩。

真是胡说八道。限制尽可能早地应用,首先是最严格的限制。你读过这个理论,但你还不明白。连接是 治疗 作为“谓词适用的笛卡尔积” 只有 通过查询优化程序。这是一种符号表示(实际上是一种归一化),以便于符号分解,这样优化者就可以生成所有等价的转换,并按成本和选择性对它们进行排序,以便选择最佳的查询计划。

唯一能让乐观者产生笛卡尔积的方法就是不能提供谓词: SELECT * FROM A,B

笔记

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

除了索引和表扫描之外,确实还有很多其他的策略,现代的乐观主义者会在制定执行计划之前把它们都花掉。

一条实用的建议:如果它可以用作外键,那么索引它,这样索引策略就是 可获得的 致乐观者。

我以前比MSSQL乐观主义者聪明。这在两个版本之前改变了。现在它一般都是教人的 我 .在一个非常真实的意义上,它是一个专家系统,将许多非常聪明的人的智慧编纂在一个完全封闭的领域中,这样一个基于规则的系统是有效的。

“胡说八道”可能不太老练。我被要求不要那么傲慢,并提醒我数学不是谎言。这是事实,但并非所有数学模型的含义都必须从字面上理解。如果你仔细地避免检查它们的荒谬性(双关语),并且在你试图解释你的方程之前,确保你把它们全部取消,那么负数的平方根非常方便。

我之所以如此粗暴地回答,是因为措辞如此的声明表明

联接 是 笛卡尔积…

这也许不是原意,但它 是 写的东西,绝对是不真实的。笛卡尔积是一种关系。连接是一个函数。更具体地说,联接是一个关系值函数。对于空谓词,它将生成笛卡尔积,检查它是否这样做是对数据库查询引擎的正确性检查,但实际上没有人编写不受约束的联接,因为它们在课堂之外没有实际价值。

我之所以这么说是因为我不希望读者陷入一个古老的陷阱,把模型和模型化的东西混淆在一起。模型是一种近似值,为便于操作而有意简化。

选择表扫描联接策略的截止值可能因数据库引擎而异。它受许多实现决策的影响,例如树节点填充因子、键值大小和算法的细微之处,但一般来说,高性能索引的执行时间为 K 日志 n + C . C项是一个固定的开销,主要由设置时间构成,曲线的形状意味着直到 n 在数百个。

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

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

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

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

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

不要犯将OLTP数据库(发生数据输入的数据库)非规范化的错误。计费运行可能更快,但如果这样做,您将得到更新异常。有没有试过让读者文摘停止给你发东西?

磁盘空间现在很便宜,所以把你自己搞砸吧。但对于数据仓库来说,非规范化只是其中的一部分。更大的性能提升来自于预先计算的汇总值:每月总计,诸如此类。它是 总是 关于减少工作集。

ADO.NET类型不匹配问题

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

varchar到nvarchar是一个扩展的转换,所以它是隐式发生的——但请告别索引,并祝您好运找出原因。

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

如果所有内容都缓存在RAM中, JOINs 相当便宜。也就是说,正常化没有太多 性能代偿 .

如果“规范化”模式导致 联接 要想大量命中磁盘,但等效的“非规范化”模式不必命中磁盘,那么非规范化就赢得了性能竞争。

原始作者的评论:现代数据库引擎非常擅长组织访问顺序,以最小化连接操作中的缓存未命中。尽管上述说法是正确的,但可能被误解为暗示连接在大数据上必然存在问题性的昂贵性。这将导致缺乏经验的开发人员做出糟糕的决策。

大多数评论者没有注意到复杂RDBMS中广泛的连接方法,而非规范化者总是掩盖维护非规范化数据的较高成本。并不是每个连接都是基于索引的,数据库中有许多优化的算法和方法来连接,这些算法和方法旨在降低连接成本。

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

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

数据库是为连接而设计的,它们在如何连接方面非常灵活,并且通常非常有性能,除非它们使连接机制出错。

我认为整个问题都是基于一个错误的前提。大桌子上的连接是 不 一定很贵。事实上, 有效地进行连接是关系数据库存在的主要原因之一 完全。大连接 集合 通常是昂贵的,但很少要将大表A的全部内容与大表B的全部内容连接起来。相反,编写查询时 只有重要的几行 在每个表中,联接所保留的实际集保持较小。

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

如果处理得当,连接通常是 最佳方法 对大量数据进行比较、组合或过滤。

瓶颈相当大 总是 磁盘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正在缓存计算值,而不是读取计算值所需的10000行。

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

对于某些数据库来说,这并不重要,例如,MS SQL在大多数情况下都知道正确的连接顺序。 对于某些人(如IBMInformix),订单带来了所有的不同。

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

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

规范化和非规范化的争论不会结束,因为问题是巨大的。自然解决方案需要两种方法的地方有很多问题。

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

阐述别人的话,

连接只是笛卡尔产品和一些唇彩。1,2,3,4 x 1,2,3将给我们12个组合(n x n=n^2)。此计算集用作应用条件的引用。DBMS应用条件(如左右都是2或3)来给我们提供匹配条件。实际上,它更为优化,但问题是相同的。对集合大小的更改将以指数形式增加结果大小。消耗的内存和CPU周期的数量都以指数形式受到影响。

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