Cardinality的计算

在数据库中如果我们使用CBO作为优化器，那么一条SQl语句的执行就会有多种执行路径，但是有一点需要注意，CBO会计算各个执行路径的访问代价，从而选择代价最小的执行路径作为我们的执行计划。通过10053事件可以trace出这样的一个过程。那么CBO在做访问路径估算的时候有一个很重要的参数作为我们计算Cost的因数，这个就是我们通常所说的扫描字段的集的势(Cardinality).关于这个值的计算比较的复杂，这里我先讨论一下使用绑定变量的情况下集的势的计算。

一般公式如下：

Cardinality=MAX(Cardinality Factor * Rowcount，1)

那么直接影响我们Cardinality结果的的其实就是Cardinality因子(Cardinality Factor).这个因子是怎么计算的呢？来看一下在不同情况下的Cardinality Factor的计算

***********
索引字段
***********
如果我们在字段上面建立了索引，或者是对多个字段建立了一个复合索引。这个索引字段的计算方式有多种

对于这个字段的查询条件是"="的情况下,那么我们的Cardinality Factor的计算公式就如下：
------------------------------------------------------------------------------------------------------------

Cardinality Factor = 1 / 字段上的唯一值的数量

来看个例子:

C:\>sqlplus /nolog

SQL*Plus: Release 9.2.0.8.0 - Production on 星期二 1月 15 12:50:38 2008

Copyright (c) 1982, 2002, Oracle Corporation.  All rights reserved.

SQL> conn / as sysdba;
已连接。
SQL> create table t ( a number , b char(1), c char(5));

表已创建。

SQL> create index t_idx1 on t (b,c);

索引已创建。

SQL> begin
  2     for i in 1 .. 1000 loop
  3      insert into t values(i,mod(i,10),mod(i,13));
  4     end loop;
  5     commit;
  6  end;
  7  /

PL/SQL 过程已成功完成。

SQL> analyze table t compute statistics
  2  for table
  3  for all indexes
  4  for all indexed columns;

表已分析。

SQL> select count(distinct b) from t;

COUNT(DISTINCTB)
----------------
              10

SQL> select count(distinct c) from t;

COUNT(DISTINCTC)
----------------
              13

SQL> select count(*) from
  2  (select distinct b,c from t);

  COUNT(*)
----------
       130

我们来看看column b的cardinality

SQL> variable V char
SQL> exec :V := 8

PL/SQL 过程已成功完成。

SQL> set autotrace traceonly
SQL> select /*+index(t t_idx1)*/ * from t where b=:V;

已选择100行。

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=41 Card=100 Bytes=15
          00)

   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'T' (Cost=41 Card=100 Byt
          es=1500)

   2    1     INDEX (RANGE SCAN) OF 'T_IDX1' (NON-UNIQUE) (Cost=2 Card
          =100)

这里我们可以看到索引的范围扫描中 Card=100,
这个Cardinality的结果就是通过 round(1/10 * 1000) = 100,其中 1/10 这个10就是我们b列中唯一键的数量 得出的结果就是我们的集的式因子(Cardinality Factor)。需要注意的是(Cardinality Factor = 1/字段上唯一值的数量)公式只适用于"="的情况下

我们来看看column c的cardinality

SQL> variable V char
SQL> exec :V := 3

PL/SQL 过程已成功完成。

SQL> select /*+index(t t_idx1)*/ * from t where c=:V;

已选择77行。

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=35 Card=77 Bytes=115
          5)

   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'T' (Cost=35 Card=77 Byte
          s=1155)

   2    1     INDEX (FULL SCAN) OF 'T_IDX1' (NON-UNIQUE) (Cost=5 Card=
          77)

这里我们可以看到索引的全扫描中 Card=77,
这个Cardinality的结果就是通过 round(1/13 * 1000) = 100,其中 1/13 这个13就是我们c列中唯一键的数量 得出的结果就是我们的集的式因子(Cardinality Factor)。需要注意的是(Cardinality Factor = 1/字段上唯一值的数量)公式只适用于"="的情况下

那么如果索引字段的查询条件是"<" ">" "<=" ">=" 那么我们计算Cardinality Factor的公式就为
------------------------------------------------------------------------------------------------------------

Cardinality Factor = (1 / 字段上的唯一值的数量) + (1 / 记录数)

比如：
SQL> select /*+index(t t_idx1)*/ * from t where b > :V;

已选择600行。

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=2 Card=101 Bytes=151
          5)

   1    0   TABLE ACCESS (FULL) OF 'T' (Cost=2 Card=101 Bytes=1515)

这里Cardnality就是等于[ (1/10) + (1/1000) ] * 1000 = 101

如果索引字段的查询条件是in,那么我们的公式就为：
---------------------------------------------------------------------------

Cardinality Factor = in条件中的变量数 / 字段上的唯一值的数量

比如:
SQL> variable A char
SQL> variable B char
SQL> variable C char
SQL> exec :A := 2

PL/SQL 过程已成功完成。

SQL> exec :B := 3

PL/SQL 过程已成功完成。

SQL> exec :C := 4

PL/SQL 过程已成功完成。

SQL> select /*+index(t t_idx10*/ * from t where b in (:A,:B,:C);

已选择300行。

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=2 Card=300 Bytes=450
          0)

   1    0   TABLE ACCESS (FULL) OF 'T' (Cost=2 Card=300 Bytes=4500)

这里我们可以看到全表扫描中 Card=300,
这个Cardinality的结果就是通过 round(3/10 * 1000) = 300,其中 3/10 这个3就是我们b列中in中的变量数得出的结果就是我们的集的式因子(Cardinality Factor)。

如果索引字段的查询条件是"<>",那么我们的公式就为：
-----------------------------------------------------------------------------

Cardinality Factor = ( 1 - (1 / 字段上的唯一值的数量 ) )

可以想想这是 "=" 的一个补集

比如
SQL> select /*+index(t t_idx1)*/ * from t where c <> :V;

已选择923行。

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=365 Card=923 Bytes=1
          3845)

   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'T' (Cost=365 Card=923 By
          tes=13845)

   2    1     INDEX (FULL SCAN) OF 'T_IDX1' (NON-UNIQUE) (Cost=5 Card=
          923)

在这里我们可以看到索引的全扫描中 Card=923,
这个Cardinality的结果就是通过 round((1-1/13) * 1000) = 923,其中 1/13 这个13就是我们c列中唯一键的数量,其结果被1减去后得出的结果就是我们的集的式因子(Cardinality Factor)。

如果查询条件为not in的时候，Cardinality的结果是根据not in中变量作为阶乘得出的公式为：
------------------------------------------------------------------------------------------------------------

Cardinality Factor = ( 1 - (1 / 字段上的唯一值的数量 ) ) ^ (not in 变量数)

SQL> select /*+index(t t_idx1)*/ * from t where b not in (:A,:B,:C);

已选择700行。

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=290 Card=729 Bytes=1
          0935)

   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'T' (Cost=290 Card=729 By
          tes=10935)

   2    1     INDEX (FULL SCAN) OF 'T_IDX1' (NON-UNIQUE) (Cost=5 Card=
          729)

在这里我们可以看到索引的全扫描中 Card=729,
这个Cardinality的结果就是通过 round((1-1/10)^3 * 1000) = 729,其中 1/10 这个10就是我们b列中唯一键的数量,其结果被1减去后得出的结果,然后再^3,就是我们的集的式因子(Cardinality Factor)。

**************
非索引字段
**************
当查询条件为"="或者是"in"的时候,非索引字段的Cardinality Factor的计算公式为：
-----------------------------------------------------------------------------------------------------------

Cardinality Factor = 1 / 100

比如：
SQL> select * from t where a = :V;

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=2 Card=10 Bytes=150)
   1    0   TABLE ACCESS (FULL) OF 'T' (Cost=2 Card=10 Bytes=150)

在这里我们可以看到索引的全扫描中 Card=10,
这个Cardinality的结果就是通过 round((1/100) * 1000) = 10

当查询条件为"<",">","<=",">=","<>","not in",非索引字段的Cardinality Factor的计算公式为：
-------------------------------------------------------------------------------------------------------------

Cardinality Factor = 1 / 20

比如:

SQL> select * from t where a >= :V;

已选择991行。

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=2 Card=50 Bytes=750)
   1    0   TABLE ACCESS (FULL) OF 'T' (Cost=2 Card=50 Bytes=750)

SQL> select * from t where a <= :V;

已选择9行。

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=2 Card=50 Bytes=750)
   1    0   TABLE ACCESS (FULL) OF 'T' (Cost=2 Card=50 Bytes=750)

SQL> select * from t where a <> :V;

已选择999行。

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=2 Card=50 Bytes=750)
   1    0   TABLE ACCESS (FULL) OF 'T' (Cost=2 Card=50 Bytes=750)

在这里我们可以看到索引的全扫描中 Card=50,
这个Cardinality的结果就是通过 round((1/20) * 1000) = 50

********
多字段
********
其公式只有一个就是：

Cardinality Factor = 字段1的Cardinality Factor * 字段2的Cardinality Factor * ... * 字段n的Cardinality Factor

SQL> select /*+index(t t_idx1)*/ * from t where b > :V and c =:A;

已选择46行。

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=6 Card=8 Bytes=120)
   1    0   TABLE ACCESS (BY INDEX ROWID) OF 'T' (Cost=6 Card=8 Bytes=
          120)

   2    1     INDEX (RANGE SCAN) OF 'T_IDX1' (NON-UNIQUE) (Cost=2 Card
          =101)

首先我们看b>:v的Cardinality Factor = (1/10) + (1/1000)
c=:A的Cardinality Factor = (1/13)
所以这个cardinality factor的结果就是 = 0.101 * 0.0769 = 0.0077669
那么Cardinality = round(0.0077669  * 1000) = 8

**********
全表扫描
**********
Cardinality Factor=1;

我们以下查询的Cardinality的结果就为：
SQL> select * from t;

已选择1000行。

Execution Plan
----------------------------------------------------------
   0      SELECT STATEMENT ptimizer=CHOOSE (Cost=2 Card=1000 Bytes=15
          000)

   1    0   TABLE ACCESS (FULL) OF 'T' (Cost=2 Card=1000 Bytes=15000)

恩，就是1*1000=1000