五 [译]数据库是如何工作查询管理器( 二 ) _关联

举个栗子，当我处理每个表都有百万行的数据的项目时，我选择只计算10%的统计信息，这让我耗费巨大的时间。事实证明是个糟糕的决定。因为有时候在 10G 给特定的表的特定的列选择统计10%和统计所有的100%是非常不同的（对于一百万个行以内的表不太可能发生）。这个错误的统计导致有时一个查询要用8个小时而不是30秒，而且寻找根源也是个噩梦。这个例子让我们看到统计是多么的重要。
注意：当然，每个数据库都有有很多高级的统计特性。如果你想知道更多，要看下数据可的文档。正如我所言，我会尝试明白如何使用统计而我发现一个最官方的文档是。
查询优化器
所有现代数据库都用基于成本的优化(CBO)去优化查询。这思想是每个操作都放一个成本值，通过用最少成本的操作获取结果的方式，来寻找降低查询成本最好的方式。
为了明白一个基于成本的优化器是如何工作的，用一个去例子“感受”下这个任务背后的复杂度，我想应该是不错的。在这部分，我将为你介绍连接2个表的3种普通方法，并且我们将能很看到，一个简单的连接查询优化也是个噩梦。在此之后，我们将看到真正的优化器上是如何工作的。
关于这些关联，我将会把重点放在他们的时间复杂度，但数据库的优化器会计算它们的CPU成本、磁盘 I/O 和内存需求。时间复杂度和CPU的成本是非常接近的(对于像我一样懒的人来讲) 。对于 CPU 的成本，我应该计算每个操作箱加法，“if语句”，一个乘法，迭代。。。更多：
使用时间复杂度更容易（至少对于我来讲），而使用它我们仍然能得到 CBO 的概念。我有时会讲磁盘 I/O，因为这也是个重要的概念。值得注意的是，大多数的瓶颈是磁盘I/O而不是CPU的使用率
索引
当看到 B+ 树的时候，我们会谈及 B+ 树。要记得，索引都是已排序的。
仅供参考，还有很多其他类型的索引，比如位图索引( ) 。与B +树索引相比，它们在CPU，磁盘I / O和内存方面的成本不同。
此外，很多现代的数据库中，如果动态创建临时索引能改善执行计划的成本，就会对当前的查询使用。
访问方式
在使用你的关联操作符（JOIN）之前，你首先要获取你的数据。下面是如何获取数据的方式
注意：因为访问途径的实际的问题是磁盘 I/O，所以我不会讨论太多时间复杂度
全局扫描
如果你读过执行计划，你会肯定曾经看过这个单词全局扫描（full scan 或只是扫描）。全局扫描是数据库读表或者完整的索引的简单方式。对磁盘I/O来讲，一个表的全局扫描的成本明显是比一个索引扫描贵得多。
范围扫描
有很多其他类型的扫描，如索引范围扫描。例如：当你使用谓词如“WHERE AGE > 20 AND AGE < 40” 当然如果你需要有一条 AGE 字段的索引你才能使用。我们已经在第一部分中看到，范围查询的时候复杂度大概是 log(N)+M, 其中 N 是索引中数据的数量，而 M 大概是这个范围内的行数。感谢统计信息，M 和 N 都是已知的(注意：对于谓词 AGE > 20 AND AGE < 40 来讲，M是可选择性的) 。此外，对于范围扫描来讲，你无需读全局索引，它在磁盘I/O上比全局扫描的成本更低
唯一扫描
如果你只需要索引中的一个值，则可以使用唯一扫描。
通过行ID访问
大多数情况下，如果数据库使用索引，则必须查找与索引关联的行。为此，它将使用行ID访问。例如，如果你做像这样的事
SELECT LASTNAME, FIRSTNAME from PERSON WHERE AGE = 28
如果你表中有字段 AGE 的索引，优化器将使用索引来查找年龄是 28 的所有人，并询问表中的关联行，因为索引只有关于年龄的信息，而你想知道姓氏和名字。但如果你现在做事是