我正在研究数据库，我正在研究关系数据库的一些局限性 .
我'm getting that joins of large tables is very expensive, but I'我不完全确定为什么 . DBMS需要做什么才能执行连接操作，瓶颈在哪里？
非规范化如何帮助克服这种费用？其他优化技术（例如索引）如何帮助？
欢迎个人经历！如果您要发布资源链接，请避免使用Wikipedia . 我知道在哪里找到它 .
与此相关，我想知道 Cloud 服务数据库（如BigTable和SimpleDB）使用的非规范化方法 . 见this question .
7 回答
非规范化以提高性能？这听起来令人信服，但它并不成立 .
Chris Date与Ted Codd博士一起成为关系数据模型的最初支持者，对于反对正常化的错误信息已经没有耐心，并且使用科学方法系统地拆除它们：他获得了大型数据库并测试了这些断言 .
我认为他是在1988-1991的关系数据库文章中写的，但这本书后来被卷入了数据库系统简介的第六版，这是关于数据库理论和设计的权威文本，在我写的第八版中，可能仍然存在在未来几十年的印刷中 . Chris Date是这个领域的专家，当时我们大多数人还在赤脚跑来跑去 .
他发现：
其中一些是针对特殊情况的
所有这些都未能为一般用途付清
对于其他特殊情况，所有这些都显着恶化
这一切都回归到减轻工作集的大小 . 涉及正确设置索引的正确选择键的连接是便宜的，并不昂贵，因为它们允许在实现行之前对结果进行大量修剪 .
实现结果涉及批量磁盘读取，这是练习中最昂贵的一个方面 . 相反，执行连接在逻辑上要求仅检索键 . 在实践中，甚至不提取键值：键哈希值用于连接比较，减少多列连接的成本并从根本上降低涉及字符串比较的连接的成本 . 不仅可以更加适合缓存，还可以减少磁盘读取量 .
此外，一个好的优化器将选择最严格的条件并在它执行连接之前应用它，非常有效地利用连接的高选择性和高基数的索引 .
不可否认，这种类型的优化也可以应用于非规范化数据库，但是那些想要对模式进行非规范化的人通常不会在（如果）设置索引时考虑基数 .
重要的是要理解表扫描（在生成连接的过程中检查表中的每一行）在实践中是罕见的 . 只有在满足以下一个或多个条件时，查询优化器才会选择表扫描 .
关系中少于200行（在这种情况下扫描会更便宜）
连接列上没有合适的索引（如果它们被索引's meaningful to join on these columns then why aren'？修复它）
在比较列之前需要类型强制（WTF？！修复它或回家） SEE END NOTES FOR ADO.NET ISSUE
比较的一个参数是表达式（无索引）
执行操作比不执行操作更昂贵 . 但是，执行错误的操作，被迫进入无意义的磁盘I / O，然后在执行您真正需要的连接之前丢弃浮渣，要贵得多 . 即使预先计算了"wrong"操作并且合理地应用了索引，仍然存在严重的惩罚 . 非正规化以预先计算连接 - 尽管存在更新异常 - 是对特定连接的承诺 . 如果你需要一个不同的联盟，那么这个承诺会让你付出很大的代价 .
如果有人想提醒我这是一个不断变化的世界，我想你会发现更大的数据集在gruntier硬件上只是夸大了Date发现的传播 .
对于所有从事计费系统或垃圾邮件生成工作的人（对你感到羞耻），并且愤怒地设置键盘告诉我你知道非正规化更快的事实，对不起但是你生活在一个特殊的案例 - 特别是，您按顺序处理所有数据的情况 . 这不是一般情况，你的理由是合理的战略 .
你没有理由错误地概括它 . 有关在数据仓库方案中正确使用非规范化的更多信息，请参阅注释部分的末尾 .
我也想回应
什么负荷的bollocks . 限制尽早应用，最先限制最严格 . 你've read the theory, but you haven' t了解它 . 连接仅由查询优化器视为"cartesian products to which predicates apply" . 这是一种符号表示（实际上是规范化），以促进符号分解，因此优化器可以生成所有等效转换并按成本和选择性对它们进行排序，以便它可以选择最佳查询计划 .
您将获得优化器生成笛卡尔积的唯一方法是无法提供谓词：
SELECT * FROM A,B注意事项
David Aldridge提供了一些重要的附加信息 .
除了索引和表扫描之外，确实存在各种其他策略，并且现代优化器将在生成执行计划之前将它们全部花费 .
一条实用建议：如果它可以用作外键，则将其编入索引，以便优化器可以使用索引策略 .
我曾经比MSSQL优化器更聪明 . 这改变了两个版本 . 现在它通常教我 . 从一个非常真实的意义上说，它是一个专家系统，在一个充分关闭的领域中编纂许多非常聪明的人的智慧，以便基于规则的系统是有效的 .
“Bollocks”可能是不熟练的 . 我被要求不那么傲慢，并提醒数学不要说谎 . 这是事实，但并非所有数学模型的含义都必须从字面上理解 . 负数的平方根非常方便，如果你仔细避免检查它们的荒谬（双关语），并且在你试图解释你的等式之前，确定你已经全部取消它们 .
我如此野蛮地回应的原因是，措辞的说法是这样说的
这可能不是什么意思，但它是写的，它绝对是不真实的 . 笛卡尔积是一种关系 . 连接是一种功能 . 更具体地，连接是关系值函数 . 使用空谓词将生成笛卡尔积，并检查它是否对数据库查询引擎进行了一次正确性检查，但没有人在实践中写入无约束连接，因为它们在课堂外没有实际 Value .
我之所以这样称呼是因为我不希望读者陷入混淆模型和建模事物的古老陷阱中 . 模型是近似值，故意简化以便于操作 .
选择表扫描连接策略的截止值可能因数据库引擎而异 . 它受到许多实现决策的影响，例如树节点填充因子，键值大小和算法的细微差别，但从广义上讲，高性能索引的执行时间为k log n c . C项是固定开销，主要由设置时间构成，曲线的形状意味着你没有得到回报（与线性搜索相比），直到n为数百 .
有时非正规化是一个好主意
非规范化是对特定连接策略的承诺 . 如前所述，这会干扰其他连接策略 . 但是如果你有大量的磁盘空间，可预测的访问模式以及处理大部分或全部的趋势，那么预先计算连接是非常值得的 .
您还可以确定操作通常使用的访问路径，并预先计算这些访问路径的所有连接 . 这是数据仓库背后的前提，或者至少它是由那些知道他们为什么要做他们正在做的事情的人 Build 的，而不仅仅是为了遵守流行语 .
通过规范化事务处理系统的批量转换定期生成适当设计的数据仓库 . 这种操作和报告数据库的分离具有消除OLTP和OLAP之间冲突的非常理想的效果（在线事务处理即数据输入和在线分析处理即报告） .
这里重要的一点是，除了定期更新外，数据仓库是只读的 . 这使得更新异常的问题变得没有实际意义 .
不要弄错你的OLTP数据库（发生数据输入的数据库）的非规范化 . 结算运行可能会更快但如果你这样做，你会得到更新异常 . 有没有试过让读者文摘停止向你发送东西？
这些天磁盘空间很便宜，所以要把自己打倒 . 但是，非规范化只是数据仓库的一部分 . 从预先计算的累计值中获得了更大的性能提升：每月总计，这类事情 . 它始终是关于减少工作集 .
ADO.NET类型不匹配的问题
假设您有一个包含varchar类型的索引列的SQL Server表，并使用AddWithValue传递一个限制此列查询的参数 . C＃字符串是Unicode，因此推断的参数类型将是NVARCHAR，它与VARCHAR不匹配 .
VARCHAR到NVARCHAR是一个扩大的转换，所以它隐含发生 - 但告别索引，并祝你好运 .
“计算磁盘命中率”（Rick James）
如果所有内容都缓存在RAM中，
JOINs相当便宜 . 也就是说，规范化没有太多的性能损失 .如果"normalized"模式导致
JOINs大量命中磁盘，但等效的"denormalized"模式不必命中磁盘，则非规范化会赢得性能竞争 .大多数评论者没有注意到的是复杂的RDBMS中可用的各种连接方法，并且非规范化器总是掩盖维护非规范化数据的更高成本 . 并非每个连接都基于索引，并且数据库具有许多用于加入的优化算法和方法，旨在降低连接成本 .
在任何情况下，连接的成本取决于其类型和一些其他因素 . 它根本不需要昂贵 - 一些例子 .
散列连接（其中批量数据是等距的）确实非常便宜，并且如果散列表不能缓存在内存中，则成本才会变得很大 . 无需索引 . 连接数据集之间的等分区可以提供很大帮助 .
排序合并连接的成本是由排序成本而不是合并驱动的 - 基于索引的访问方法实际上可以消除排序成本 .
索引上嵌套循环连接的开销由b-tree索引的高度和表块本身的访问权限驱动 . 它很快，但不适合批量连接 .
基于集群的嵌套循环连接要便宜得多，每个连接行需要的逻辑IO IO更少 - 如果连接的表都在同一个集群中，那么通过连接行的共置，连接变得非常便宜 .
数据库旨在加入，并且它们在执行操作时非常灵活，并且通常非常高效，除非它们使连接机制出错 .
我认为整个问题都是基于错误的前提 . 加入大 table 不一定很贵 . 事实上， doing joins efficiently is one of the main reasons relational databases exist 根本就没有 . 大型集合上的连接通常很昂贵，但是很少想要将大型表A的全部内容与大型表B的全部内容连接起来 . 相反，您编写查询时只使用每个表的重要行并且连接保留的实际集合仍然较小 .
此外，您还具有Peter Wone提到的效率，这样只有每条记录的重要部分才能在内存中，直到最终结果集具体化为止 . 此外，在具有许多联接的大型查询中，您通常希望从较小的表集开始，然后逐步使用大表集，以便保留在内存中的集尽可能地尽可能小 .
正确完成后，连接通常是比较，组合或过滤大量数据的最佳方式 .
瓶颈几乎总是磁盘I / O，更具体地说 - 随机磁盘I / O（相比之下，顺序读取相当快，可以通过预读策略进行缓存） .
联接可以增加随机搜索 - 如果你更好.1709515_d .
单个非规范化表具有类似的问题 - 行很大，因此不太适合单个数据页 . 如果你需要远离另一个的行（并且大行大小使它们更远），那么你'll have more random I/O. Again, a table scan may be forced to avoid this. But, this time, your table scan has to read more data because of the large row size. Add to that the fact that you' re将数据从单个位置复制到多个位置，并且RDBMS具有更多的读取（和缓存） .
使用2个表，您还可以获得2个聚簇索引 - 并且通常可以索引更多（因为插入/更新开销较少），这可以大大提高性能（主要是，因为索引（相对）小，快速读取磁盘（或缓存便宜），并减少需要从磁盘读取的表行数量 .
关于连接的唯一开销来自于找出匹配的行 . Sql Server使用3种不同类型的连接（主要基于数据集大小）来查找匹配的行 . 如果优化器选择了错误的连接类型（由于统计信息不准确，索引不足或只是优化器错误或边缘情况），它可能会极大地影响查询时间 .
循环连接对于（至少1个）小数据集来说是非常便宜的 .
合并连接首先需要两种数据集 . 但是，如果您加入索引列，则索引已经排序，无需进一步的工作 . 否则，排序会产生一些CPU和内存开销 .
散列连接需要内存（用于存储散列表）和CPU（用于构建散列） . 同样，这与磁盘I / O相比相当快 . 但是，如果没有足够的RAM来存储哈希表，Sql Server将使用tempdb来存储部分哈希表和找到的行，然后一次只处理哈希表的一部分 . 与所有磁盘一样，这是相当慢的 .
在最佳情况下，这些不会导致磁盘I / O - 因此从性能角度来看可以忽略不计 .
总而言之，在最坏的情况下 - 从x连接表中读取相同数量的逻辑数据实际上应该更快，因为它来自单个非规范化表，因为磁盘读取较小 . 要读取相同数量的物理数据，可能会有一些轻微的开销 .
由于查询时间通常由I / O成本决定，并且数据的大小不会因非规范化而改变（减去一些非常微小的行开销），因此只需将表合并在一起就不会带来巨大的好处 . 倾向于提高性能的非规范化类型IME是缓存计算值而不是读取计算它们所需的10,000行 .
您加入表格的顺序非常重要 . 如果您有两组数据，请尝试以某种方式构建查询，以便首先使用最小的数据来减少查询必须处理的数据量 .
对于某些数据库而言无关紧要，例如MS SQL在大多数情况下确实知道正确的连接顺序 . 对于某些人（如IBM Informix），订单会产生重大影响 .
当您考虑连接的复杂性类时，决定是否进行非规范化或规范化是一个相当简单的过程 . 例如，当查询为O（k log n）时，我倾向于使用规范化来设计我的数据库，其中k是相对于所需输出幅度的 .
非规范化和优化性能的简单方法是考虑规范化结构的更改如何影响非规范化结构 . 然而，它可能是有问题的，因为它可能需要事务逻辑来处理非规范化的结构化 .
关于正常化和非规范化的争论不会结束，因为问题是巨大的 . 自然解决方案需要两种方法存在许多问题 .
作为一般规则，我总是存储一个可以重构的规范化结构和非规范化缓存 . 最终，这些缓存可以帮助我解决未来的规范化问题 .
阐述别人的话，
加入只是笛卡儿的产品，有一些唇彩 . {1,2,3,4} X {1,2,3}会给我们12个组合（nXn = n ^ 2） . 此计算集充当应用条件的参考 . DBMS应用条件（如左右两个都是2或3）给出匹配条件 . 实际上它更优化但问题是相同的 . 对集合大小的更改会以指数方式增加结果大小 . 消耗的内存量和CPU周期均以指数形式实现 .
当我们非规范化时，我们完全避免这种计算，想到有一个彩色粘性，附在你书的每一页上 . 您可以使用引用推断出信息 . 我们付出的代价是我们正在妥协DBMS的本质（数据的最佳组织）