Fallacies Of The CBO

词汇：

NDV                     唯一值的数目。A.k.a NUM_DISTINCT

Selectivity             表示行集中选定行的比例

FF（FILTER FACTOR）     选择性的另外一个说法，特别用于多谓词的组合选择性

Cardinality             行集中的行数目

Base cardinality        基表中行的数目

Effective cardinality   从基表中选择的行估计数目。依赖于在基表上不同列指定的谓词

Join cardinality        两个行集连接时产生的行数目。由两个行集的cardinality产生，等于连接谓词Selectivity的乘积

Distinct cardinality    行集中某列上唯一值的数目

Group cardinality       GROUP BY操作后行集中产生的行数目

§1.1  CBO

Selectivity（选择性）：表示行集中行的比例。行集可以是基表、视图或者连接、Group By操作的结果。选择性与查询条件绑定。选择性表示行集中有多少行通过谓词测试。选择性的范围是0.0到1.0。0.0表示没有行，1.0表示所有行。

Cardinality（基数）：表示行级中的行数目。行集可以是基表、视图或者连接、Group By操作的结果。基数的有效性依赖于基表中不同的谓词，这是因为每个谓词作为基表中选择行的连续过滤器。有效的基数通过基本基数和所有表中谓词选择性的组合。如果表上没有谓词，有效性基数等于基本基数，连接基数是两个行级连接在一起的时候产生的行数目。连接是通过作为结果过滤器的连接谓词的两个行集的笛卡儿积。连接基数等于连接谓词选择性的乘积。

1.     基本访问成本

基表访问成本

表扫描：nblks/k（k取决于oracle的版本和初始化参数db_file_multiblock_read_count）

唯一扫描：blevel + 1

快速全扫描：leaf_blocks/k

索引：blevel + FF*leaf_blocks

范围扫描：blevel+FF*leaf_blocks+FF*clustering_factor

Selectivity=FF=估计card/基表card ó 估计card=FF*基表card

其中FF表示过滤因子，基表card表示基表的行数目比如(NUM_ROWS)。

2.      连接成本

嵌套循环连接

对于外部行集中每一行，都需要访问内部行集以查找所有匹配的行用于连接。因此，在嵌套循环连接中，内部行集访问的次数与外部行集的行数目一致。

成本 ＝ 外部访问成本 ＋ （内部访问成本*外部基数性）

排序合并连接

将要连接的两个行集在没有按照键值排序情况下先按连接键排序

成本 ＝ 外部访问成本 ＋ 内部访问成本＋ 排序成本（如果需要排序）

散列连接

内部行集在内存中散列并使用连接键建立散列表。外部行集中的每行被散列，散列表用于探查所有连接匹配的行。假如内部行集非常大，那么只有一部分在内存中散列，该部分称为散列分区。外部行集中的每一行散列用于在散列分区中探查匹配的行。然后内部行集的下一部分在内存中散列，外部行集的每一行散列用于在散列分区中探查匹配的行，该过程重复直到内部行集的所有分区都用完。

成本 ＝ （外部访问成本*散列分区编号） ＋ 内部访问成本

这三种连接方法有自己本身的成本公式但都依赖于外部的、内部的基本访问成本和它们有效的基数性。

3.      其他成本

辅助成本比如GROUP BY/ORDER BY的排序通常与操作所基于数据的大小、基数性有关。

我们看到访问计划的成本是组件的估计基数性的函数，这就是基数性估计精确性的重要性了。依赖于估计基数性的成本是两个不同执行计划不能比较的原因之一。

4.      假定

在关系数据库中查询优化的整个问题其实就是关系理论的深入。有三个核心假定――作者称为缪论，因为它们通常是错误的。

§1.2  缪论一：统一分布式假定

有三种不同形式的分布式假定：A－列值在表所有物理块中均匀分布；B－假定列值在表中所有行中均匀分布；（A、B均独立的可为真或假）C－属性值在值谱上均匀分布，比如在最大和最小值之间。

1.      列值在所有块中统一分布

该假定不会营销基数性估计但会纯粹和直接的影响索引访问的成本。

值得注意的是，统一分布假定表示最坏的情况：列值的更好集群性访问成本越低。如果含有特定列值的所有n行都在1个块中存在，访问的I/O成本是1而不是在统一分布时的n。（参考www.hostos.com）。

2.      所有行上列值的统一分布

属性值的分布频率通常伴随有权值或者是“Zipf”分布。

解决方法

使用histograms（柱状图）。

但查询使用了绑定变量，如果没有柱状图，密度等于1/NDV，有柱状图密度的计算会不同，柱状图甚至会在使用绑定变量的查询中也有所不同。通过使用不同数目的桶，可以产生密度的不同值和基数性估计。

3.      属性值在给定值范围上均匀分布

比如id值的分布为0，1－12，998－999，NDV＝15。

解决方法

使用列上的柱状图。

§1.3  缪论二：谓词依赖性假定

当表上有多于一个的谓词，单个谓词的选择性通过下面的规则组合：

P1 AND P2    S(P1&P2) = S(P1)*S(P2)

P1 OR  P2    S(P1|P2) = S(P1) + S(P2) – [S(P1)*S(P2)]

解决方法

如果谓词不是独立的，对于不正确的选择性和基数估计是无法更正的。

§1.4  缪论三：连接一致假定

连接一致假定意思是一张表中的一行近似相等于与第二张表的任意行连接。【The join uniformity assumption states that a row from one table is equally likely to join with any row from the second table.】

其他相关内容：

http://space.itpub.net/756652/viewspace-470124