何时以及为什么数据库加入昂贵？

Question

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

我得到大桌子的连接是非常昂贵的,但我不完全确定为什么.DBMS需要做什么才能执行连接操作,瓶颈在哪里？
非规范化如何帮助克服这种费用？其他优化技术(例如索引)如何帮助？

欢迎个人经历!如果您要发布资源链接,请避免使用Wikipedia.我知道在哪里找到它.

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

Answer 1

非规范化以提高性能？这听起来令人信服,但它并不成立.

与Ted Codd博士合作的Chris Date是关系数据模型的最初支持者,对于反对正常化的错误信息已经没有耐心,并且使用科学方法系统地拆除它们:他获得了大型数据库并进行了测试这些断言.

我觉得他写了它在关系数据库著作1988-1991但是这本书后来被卷成六版数据库系统概论,这是该关于数据库理论和设计权威文本,在我写的第八版中,可能仍然存在在未来几十年的印刷中.Chris Date是这个领域的专家,当时我们大多数人还在赤脚跑来跑去.

他发现:

• 其中一些是针对特殊情况的
• 所有这些都无法为一般用途付清
• 对于其他特殊情况,所有这些都明显更糟

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

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

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

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

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

• 关系中少于200行(在这种情况下,扫描会更便宜)
• 连接列上没有合适的索引(如果在这些列上加入是有意义的,那么为什么它们不被索引？修复它)
• 在比较列之前需要类型强制(WTF？!修复它或回家)查看ADO.NET ISSUE的结束注释
• 比较的一个参数是表达式(无索引)

执行操作比不执行操作更昂贵.但是,执行错误的操作,被迫进入无意义的磁盘I/O,然后在执行您真正需要的连接之前丢弃浮渣,要贵得多.即使预先计算了"错误"操作并且合理地应用了索引,仍然存在重大损失.非正规化以预先计算连接 - 尽管存在更新异常 - 是对特定连接的承诺.如果你需要一个不同的联盟,那么这个承诺会让你付出很大的代价.

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

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

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

我也想回应

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

什么负荷的bollocks.限制尽早应用,最先限制最严格.你已经读过这个理论,但你还没有理解它.连接被处理为"对哪些谓词用于笛卡尔产品" 仅由查询优化器.这是一种符号表示(实际上是规范化),以促进符号分解,因此优化器可以生成所有等效转换并按成本和选择性对它们进行排序,以便它可以选择最佳查询计划.

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

笔记

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

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

一条实用建议:如果它可以用作外键,则将其编入索引,以便优化器可以使用索引策略.

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

"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大量命中磁盘,但等效的"非规范化"模式不必触及磁盘,则非规范化会赢得性能竞争.

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

Answer 2

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

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

• 散列数据是等距的散列连接确实非常便宜,并且如果散列表不能缓存在内存中,则成本才会变得很大.无需索引.连接数据集之间的等分区可以提供很大帮助.
• 排序合并连接的成本是由排序成本而不是合并驱动的 - 基于索引的访问方法实际上可以消除排序成本.
• 索引上嵌套循环连接的开销由b树索引的高度和表块本身的访问权限驱动.它很快,但不适合批量连接.
• 基于集群的嵌套循环连接要便宜得多,每个连接行需要的逻辑IO IO更少 - 如果连接的表都在同一个集群中,则通过连接行的共置,连接变得非常便宜.

数据库旨在加入,并且它们在执行操作时非常灵活,并且通常非常高效,除非它们使连接机制出错.

Answer 3

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

此外,您还具有Peter Wone提到的效率,这样只有每条记录的重要部分才能在内存中,直到最终结果集具体化为止.此外,在具有许多联接的大型查询中,您通常希望从较小的表集开始,然后逐步使用大表集,以便保留在内存中的集尽可能地尽可能小.

正确完成后,连接通常是比较,组合或过滤大量数据的最佳方式.

Answer 4

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