带读 IBM 关系型数据库经典论文

壹扪心自问

一条 SQL 可能在很多人看来是 select , 那是业务；部分人看来，却是一棵棵树，语法树，那是 DBA；少部分人会分析磁盘开销，笛卡尔统计值，时空复杂度，那是内核设计。

扪心自问，你是属于哪一种？

贰关系引擎

| 来源：Access Path Selection...( P.Griffiths Selinger )

| 翻译：Lenis

从 1979 年开始，关系数据库引擎的本质结构一直都没有太多变化，所以优化的步骤看上去也就是那么几条军规。比如从解析出发，经历成本评估，选择最优化，执行。

关于优化，我们能做的也就是从成本评估这里找到突破口。

而成本评估，就是考验对计算机内部结构的理解，随机读，顺序读，磁盘转速，字段密度（也就是统计信息）。

COST = PAGE IO + W*(RSI CALLS)

是多么经典的成本计算公式！当然现在慢慢演化了，更具体的要参考《数据库索引优化与设计》，一本讲评估的好书（我会在星球持续写写这本书的精华部分，也是带读）。Fenng 翻译的《成本优化器》对于研究 Oracle 也是极好的参考手册。碰到执行计划异常，首先考虑是否 statistics(统计信息：包括密度，记录数等）及时更新。在 statistics 及时更新的情况下，通常由于 parameter sniff 需要指定 recompile hint 去改变执行计划。

叁执行计划误区

在分析执行计划优劣的时候，往往大家都会有个误区：执行计划一定是选择最优的那个。

其实真不是。

当查询设计到仅仅一张表的时候，评估成本可以很简单。遍历所有可能的执行计划，在其中找到一个最低成本的计划执行便可。

我们的查询（通常情况下）会超过 2 张表，甚至是 5-6 个表，往往这类查询在 OLAP 系统中经常出现。此时的执行计划组合可能有很多种。遍历这些可能的执行计划，就会耗去很多时间。如果要找到最优的计划，说不定找到这个计划的时间，都比执行该计划要花更多时间。

所以，查询最优执行计划的时间也是要考虑在优化器的算法中。在尽可能短的时间里，找到还算不错的执行计划便可。而不是每次都把所有可能的执行计划都去评估一下成本，再选择最优的那个。

肆查询路径

这篇论文最有意思的地方在于，他讲述的 access path 极为有用。

access path 的选择大方向有两种，一是全扫描，二是走索引。都知道走索引快，但也不绝对，查询引擎如何影响 access path 的选择，是所有优化中必须要考虑的问题。

本质上，研究 access path 就是在研究每条路径的时间复杂度。因为被 statistics(统计信息）掩盖的笛卡尔积，可能得不到及时更新而产生错误的 access path 导致查询变慢。

假设：表 sales 中有 200 万条数据，而 product 字段的 Phone 值比列占到总记录的 80%。那么下列查询是否有必要建立索引呢？

SELECT product,COUNT(ID) AS OrderCnt  FROM sales  GROUP BY product

如果是这样呢：

SELECT product,SUM(Amount) AS Amt  FROM sales  WHERE product ='Phone'

后一个影响 access plan 的就属 order 了。

order 分为两种：有序和无序。

有序的 order 是我们查询时指定的。比如 group by , order by. 我们需要结果按照一定的顺序排列，就使用 order by 指定。这种 Order 我们称其为 interesting order.

假设，sales 表有这么个查询：

SELECT product, sales_date FROM sales  WHERE product='Phone' ORDER BY sales_date ASC

如果有两个索引，分别是： (product), (product,sales_date) 大家猜猜优化器会选择哪个索引？当我们的查询是无序的时候，两个索引都可以走，但要求排序时，对索引的要求就高了。

access plan 比较复杂的一类莫过于 Join.

Join 总体上分 3 大类： Nested Loop (嵌套式循环) Merge Join (合并式) Hash Join (哈希式)

为了保持和业界术语一致，我们（包括任何正规教材）采用的是英文来解释每种概念。有时候用中文，在沟通交流时，会比较费解。

在 Join 的概念中，搞清楚 Outer Table（Build Table）和 Inner (Prorbe) Table 非常重要。直接决定表访问的物理路径。

Join(Nested Loops Join) 的实现基本流程：

从 Outer Table 读取第一条满足条件的记录；
依据 Join 条件，从 Inner Table 中读取满足条件的记录；
从 Outer Table 读取第二条满足条件的记录；
依据 Join 条件，从 Inner Table 中读取满足条件的记录；
从 Outer Table 依次读取下一条满足条件的记录，重复 2 - 4 的过程，直到所有 Outer Table 中所有满足条件的记录都遍历完毕。查询结束！

决定哪张表作为 Outer Table ，哪张表作为 Inner Table 可以很大程度上改变查询的性能。假如大表作为 Outer Table, 小表作为 Inner Table, 虽然遍历大表的时间会长，但小表的访问时间会少，带给小表的影响就小；反之，大表作为 Inner Table 就会给查询和更新带来冲突，影响并发。我们要做的事情，就是将两个表尽可能用最少数据量做 Join.

伍殊途同归

简单过了下这篇来自 IBM 的经典论文，虽然文章小，但信息量极大。达到可以用下面的脑图来扩展：