Bitmap Index OR

在测试bitmap index的时候,发现oracle在处理OR这个谓词条件的时候,返回的cardinality在10.2.0.3和11.2.0.4(including 12.1.0.2)版本下是不同的,11gr2的结果从数学上是对的,优化器在不断的进步。
测试脚本来自Cost Based Oracle Fundermentals的第八章bitmap_or.sql。

数据分布信息如下

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           1000     999000       .001
N2                           1000     999000       .001
SMALL_VC                  1000000          0    .000001

在10.2.0.3中的执行计划和10053信息如下

------------------------------------------------+-----------------------------------+
| Id  | Operation                     | Name    | Rows  | Bytes | Cost  | Time      |
------------------------------------------------+-----------------------------------+
| 0   | SELECT STATEMENT              |         |       |       |     2 |           |
| 1   |  TABLE ACCESS BY INDEX ROWID  | T1      |  1999 |   25K |     2 |  00:00:01 |
| 2   |   BITMAP CONVERSION TO ROWIDS |         |       |       |       |           |
| 3   |    BITMAP OR                  |         |       |       |       |           |
| 4   |     BITMAP INDEX SINGLE VALUE | T1_I1   |       |       |       |           |
| 5   |     BITMAP INDEX SINGLE VALUE | T1_I2   |       |       |       |           |
------------------------------------------------+-----------------------------------+
Predicate Information:
----------------------
4 - access("N1"=50000)
5 - access("N2"=50000)
 
Content of other_xml column
===========================
  db_version     : 10.2.0.3
  parse_schema   : BLUE
  plan_hash      : 3072958973
  Outline Data:
  /*+
    BEGIN_OUTLINE_DATA
      IGNORE_OPTIM_EMBEDDED_HINTS
      OPTIMIZER_FEATURES_ENABLE('10.2.0.3')
      ALL_ROWS
      OUTLINE_LEAF(@"SEL$1")
      BITMAP_TREE(@"SEL$1" "T1"@"SEL$1" OR(1 1 ("T1"."N1") 2 ("T1"."N2")))
    END_OUTLINE_DATA
  */

10.2.0.3下的10053 trace信息

***************************************
BASE STATISTICAL INFORMATION
***********************
Table Stats::
  Table: T1  Alias: T1
    #Rows: 1000000  #Blks:  2488  AvgRowLen:  13.00
Index Stats::
  Index: T1_I1  Col#: 1
    LVLS: 1  #LB: 25  #DK: 1000  LB/K: 1.00  DB/K: 1.00  CLUF: 1042.00
  Index: T1_I2  Col#: 2
    LVLS: 1  #LB: 25  #DK: 1000  LB/K: 1.00  DB/K: 1.00  CLUF: 1042.00
***************************************
SINGLE TABLE ACCESS PATH
  Column (#1): N1(NUMBER)
    AvgLen: 2.00 NDV: 1000 Nulls: 999000 Density: 1.0000e-03 Min: 0 Max: 999000
  Column (#2): N2(NUMBER)
    AvgLen: 2.00 NDV: 1000 Nulls: 999000 Density: 1.0000e-03 Min: 0 Max: 999000
  Table: T1  Alias: T1     
    Card: Original: 1000000  Rounded: 1999  Computed: 1999.00  Non Adjusted: 1999.00
  Access Path: TableScan
    Cost:  563.99  Resp: 563.99  Degree: 0
      Cost_io: 546.00  Cost_cpu: 287708123
      Resp_io: 546.00  Resp_cpu: 287708123
  ****** trying bitmap/domain indexes ******
  Access Path: index (AllEqRange)
    Index: T1_I1
    resc_io: 1.00  resc_cpu: 8171
    ix_sel: 1.0000e-06  ix_sel_with_filters: 1.0000e-06
    Cost: 1.00  Resp: 1.00  Degree: 0
  Access Path: index (AllEqRange)
    Index: T1_I2
    resc_io: 1.00  resc_cpu: 8171
    ix_sel: 1.0000e-06  ix_sel_with_filters: 1.0000e-06
    Cost: 1.00  Resp: 1.00  Degree: 0
  Access path: Bitmap index - accepted
    Cost: 2.41 Cost_io: 2.41 Cost_cpu: 19920 Sel: 2.0000e-06
    Not believed to be index-only
  Best:: AccessPath: IndexBitmap
         Cost: 2.41  Degree: 1  Resp: 2.41  Card: 1999.00  Bytes: 0

GENERAL PLANS
***************************************
Considering cardinality-based initial join order.
Permutations for Starting Table :0
***********************
Join order[1]:  T1[T1]#0
***********************
Best so far: Table#: 0  cost: 2.4123  card: 1999.0000  bytes: 25987
(newjo-stop-1) k:0, spcnt:0, perm:1, maxperm:80000
*********************************
Number of join permutations tried: 1
*********************************
Final - All Rows Plan:  Best join order: 1
  Cost: 2.4123  Degree: 1  Card: 1999.0000  Bytes: 25987
  Resc: 2.4123  Resc_io: 2.4111  Resc_cpu: 19920
  Resp: 2.4123  Resp_io: 2.4111  Resc_cpu: 19920

对于上述的cardinality的返回,oracle优化器直接使用1000000 * density = 1000000 * 0.001 = 1000,OR操作一下2000 – 1(overlap) = 1999.

在12.1.0.2下

-------------------------------------------------------+-----------------------------------+
| Id  | Operation                            | Name    | Rows  | Bytes | Cost  | Time      |
-------------------------------------------------------+-----------------------------------+
| 0   | SELECT STATEMENT                     |         |       |       |     2 |           |
| 1   |  TABLE ACCESS BY INDEX ROWID BATCHED | T1      |     2 |    26 |     2 |  00:00:01 |
| 2   |   BITMAP CONVERSION TO ROWIDS        |         |       |       |       |           |
| 3   |    BITMAP OR                         |         |       |       |       |           |
| 4   |     BITMAP INDEX SINGLE VALUE        | T1_I1   |       |       |       |           |
| 5   |     BITMAP INDEX SINGLE VALUE        | T1_I2   |       |       |       |           |
-------------------------------------------------------+-----------------------------------+
Predicate Information:
----------------------
4 - access("N1"=50000)
5 - access("N2"=50000)
 
Content of other_xml column
===========================
  db_version     : 12.1.0.2
  parse_schema   : BLUE
  plan_hash_full : 243133367
  plan_hash      : 711745958
  plan_hash_2    : 243133367
  Outline Data:
  /*+
    BEGIN_OUTLINE_DATA
      IGNORE_OPTIM_EMBEDDED_HINTS
      OPTIMIZER_FEATURES_ENABLE('12.1.0.2')
      DB_VERSION('12.1.0.2')
      ALL_ROWS
      OUTLINE_LEAF(@"SEL$1")
      BITMAP_TREE(@"SEL$1" "T1"@"SEL$1" OR(1 1 ("T1"."N1") 2 ("T1"."N2")))
      BATCH_TABLE_ACCESS_BY_ROWID(@"SEL$1" "T1"@"SEL$1")
    END_OUTLINE_DATA
  */

10053 信息如下

 ****** trying bitmap/domain indexes ******
 ****** Costing Index T1_I1
  SPD: Return code in qosdDSDirSetup: NOCTX, estType = INDEX_SCAN
  SPD: Return code in qosdDSDirSetup: NOCTX, estType = INDEX_FILTER
  Access Path: index (AllEqRange)
    Index: T1_I1
    resc_io: 1.000000  resc_cpu: 8171
    ix_sel: 1.0000e-06  ix_sel_with_filters: 1.0000e-06 
    Cost: 1.000561  Resp: 1.000561  Degree: 0
 ****** Costing Index T1_I2
  SPD: Return code in qosdDSDirSetup: NOCTX, estType = INDEX_SCAN
  SPD: Return code in qosdDSDirSetup: NOCTX, estType = INDEX_FILTER
  Access Path: index (AllEqRange)
    Index: T1_I2
    resc_io: 1.000000  resc_cpu: 8171
    ix_sel: 1.0000e-06  ix_sel_with_filters: 1.0000e-06 
    Cost: 1.000561  Resp: 1.000561  Degree: 0
  Bitmap nodes:
    Used T1_I1
      Cost = 1.000561, sel = 1.0000e-06
    Used T1_I2
      Cost = 1.000561, sel = 1.0000e-06
  Bitmap nodes:
    Used  bitmap node 
  Access path: Bitmap index - accepted
    Cost: 2.408188 Cost_io: 2.406821 Cost_cpu: 19890.032424 Sel: 2.0000e-06
    Not Believed to be index-only
  ****** finished trying bitmap/domain indexes ******
  Best:: AccessPath: IndexBitmap
         Cost: 2.408188  Degree: 1  Resp: 2.408188  Card: 1.999999  Bytes: 0.000000


GENERAL PLANS
***************************************
Considering cardinality-based initial join order.
Permutations for Starting Table :0
Join order[1]:  T1[T1]#0
***********************
Best so far:  Table#: 0  cost: 2.408188  card: 1.999999  bytes: 26.000000

对于这个cardinality的由来,推测oracle的优化器是按照distinct value的个数 * density获取到的,然后or操作,上述的是1000 * 0.001 = 1,OR操作为2,但是10053中给出的确是1.999999。
接下来开始验证一下猜测,修改脚本创建更多的测试数据。测试分为修改distinct value的个数和修改density两个部分。第一部分创建表后distinct value分别为2000个、4000个和8000个,对应的数据行数是100w、200w、400w,经过测试发现cardinality确实是按照distincet* density的个数产生的cardinality。接着继续测试density的变更对于cardinality的影响。
测试结果数据如下,输出的格式为上面为数据分布,下面为其对应的执行计划输出。
修改density的脚本

EXEC DBMS_STATS.SET_COLUMN_STATS(USER,'T1','N1',DENSITY=>0.9);
EXEC DBMS_STATS.SET_COLUMN_STATS(USER,'T1','N2',DENSITY=>0.9);

实验记录如下

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           8000    3992000    .000125
N2                           8000    3992000    .000125
SMALL_VC                  4000000          0  .00000025
-----------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost  |
-----------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       |     2 |    26 |     3 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    |     2 |    26 |     3 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |       |       |       |       |
|   3 |    BITMAP OR                        |       |       |       |       |
|*  4 |     BITMAP INDEX SINGLE VALUE       | T1_I1 |       |       |       |
|*  5 |     BITMAP INDEX SINGLE VALUE       | T1_I2 |       |       |       |
-----------------------------------------------------------------------------

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           8000    3992000         .5
N2                           8000    3992000    .000125
SMALL_VC                  4000000          0  .00000025
-----------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost  |
-----------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       |  4001 | 52013 |   706 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    |  4001 | 52013 |   706 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |       |       |       |       |
|   3 |    BITMAP OR                        |       |       |       |       |
|*  4 |     BITMAP INDEX SINGLE VALUE       | T1_I1 |       |       |       |
|*  5 |     BITMAP INDEX SINGLE VALUE       | T1_I2 |       |       |       |
-----------------------------------------------------------------------------

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           8000    3992000         .1
N2                           8000    3992000         .1
SMALL_VC                  4000000          0  .00000025
---------------------------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       |  1600 | 20800 |   303   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    |  1600 | 20800 |   303   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |       |       |       |            |          |
|   3 |    BITMAP OR                        |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE       | T1_I1 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE       | T1_I2 |       |       |            |          |
---------------------------------------------------------------------------------------------

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           8000    3992000         .2
N2                           8000    3992000         .2
SMALL_VC                  4000000          0  .00000025
---------------------------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       |  3199 | 41587 |   561   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    |  3199 | 41587 |   561   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |       |       |       |            |          |
|   3 |    BITMAP OR                        |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE       | T1_I1 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE       | T1_I2 |       |       |            |          |
---------------------------------------------------------------------------------------------

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           8000    3992000         .3
N2                           8000    3992000         .3
SMALL_VC                  4000000          0  .00000025
---------------------------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       |  4799 | 62387 |   781   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    |  4799 | 62387 |   781   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |       |       |       |            |          |
|   3 |    BITMAP OR                        |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE       | T1_I1 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE       | T1_I2 |       |       |            |          |
---------------------------------------------------------------------------------------------

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           8000    3992000         .5
N2                           8000    3992000         .5
SMALL_VC                  4000000          0  .00000025
-----------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost  |
-----------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       |  7996 |   101K|  1188 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    |  7996 |   101K|  1188 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |       |       |       |       |
|   3 |    BITMAP OR                        |       |       |       |       |
|*  4 |     BITMAP INDEX SINGLE VALUE       | T1_I1 |       |       |       |
|*  5 |     BITMAP INDEX SINGLE VALUE       | T1_I2 |       |       |       |
-----------------------------------------------------------------------------

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           8000    3992000         .6
N2                           8000    3992000         .6
SMALL_VC                  4000000          0  .00000025
---------------------------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       |  9594 |   121K|  1269   (1)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    |  9594 |   121K|  1269   (1)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |       |       |       |            |          |
|   3 |    BITMAP OR                        |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE       | T1_I1 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE       | T1_I2 |       |       |            |          |
---------------------------------------------------------------------------------------------

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           8000    3992000         .7
N2                           8000    3992000         .7
SMALL_VC                  4000000          0  .00000025
---------------------------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       | 11192 |   142K|  1387   (1)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    | 11192 |   142K|  1387   (1)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |       |       |       |            |          |
|   3 |    BITMAP OR                        |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE       | T1_I1 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE       | T1_I2 |       |       |            |          |
---------------------------------------------------------------------------------------------

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           8000    3992000         .8
N2                           8000    3992000         .8
SMALL_VC                  4000000          0  .00000025
---------------------------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       | 12790 |   162K|  1489   (1)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    | 12790 |   162K|  1489   (1)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |       |       |       |            |          |
|   3 |    BITMAP OR                        |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE       | T1_I1 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE       | T1_I2 |       |       |            |          |
---------------------------------------------------------------------------------------------

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           8000    3992000        .05
N2                           8000    3992000        .05
SMALL_VC                  4000000          0  .00000025
---------------------------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       |   800 | 10400 |   159   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    |   800 | 10400 |   159   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |       |       |       |            |          |
|   3 |    BITMAP OR                        |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE       | T1_I1 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE       | T1_I2 |       |       |            |          |
---------------------------------------------------------------------------------------------

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           8000    3992000        .04
N2                           8000    3992000        .04
SMALL_VC                  4000000          0  .00000025
---------------------------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       |   640 |  8320 |   128   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    |   640 |  8320 |   128   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |       |       |       |            |          |
|   3 |    BITMAP OR                        |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE       | T1_I1 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE       | T1_I2 |       |       |            |          |
---------------------------------------------------------------------------------------------

COLUMN_NAME          NUM_DISTINCT  NUM_NULLS    DENSITY
-------------------- ------------ ---------- ----------
N1                           8000    3992000       .005
N2                           8000    3992000       .006
SMALL_VC                  4000000          0  .00000025
---------------------------------------------------------------------------------------------
| Id  | Operation                           | Name  | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |       |    88 |  1144 |    20   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID BATCHED| T1    |    88 |  1144 |    20   (0)| 00:00:01 |
|   2 |   BITMAP CONVERSION TO ROWIDS       |       |       |       |            |          |
|   3 |    BITMAP OR                        |       |       |       |            |          |
|*  4 |     BITMAP INDEX SINGLE VALUE       | T1_I1 |       |       |            |          |
|*  5 |     BITMAP INDEX SINGLE VALUE       | T1_I2 |       |       |            |          |
---------------------------------------------------------------------------------------------

从上面的数据可以看到,当dentity小于0.1(或者是0.1到某个数值之间的数值),oracle优化器计算出来的cardinality严格按照num_distinct * density *2来计算bitmap index的OR操作。当density大于0.2之后(或许不到0.2,需要测试),优化器计算出来的cardinality会稍微比理论值少一些,随着density越接近1,这个差值也就稍微大一些,比如density为0.8的时候cardinality为12790(理论12800)。

此条目发表在bitmap, CBO分类目录。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s