ix_sel_with_filters

In Cost-Based Oracle erläutert Jonathan Lewis im vierten Kapitel die Grundlagen des Index Costing und verweist dabei auf die von Wolfgang Breitling im Jahr 2002 veröffentlichte Formel:

cost = blevel
       + ceiling(leaf_blocks * effective index selectivity)
       + ceiling(clustering_factor * effective table selectivity)

Völlig unproblematisch sind in dieser Rechnung die Faktoren blevel, leaf_blocks und clustering_factor, die man z.B. in der View user_indexes findet. Die beiden anderen Elemente effective index selectivity und effective table selectivity werden im CBO-Buch ebenfalls erläutert, aber ich hatte mir bisher nie die Mühe gemacht, zu prüfen, ob ich diese Erklärungen tatsächlich verstanden hatte. Das soll hiermit geändert werden.

Dabei scheint die effective index selectivity auch noch recht harmlos zu sein: sie ergibt sich aus der Kombination der Selektivitäten der für den Zugriff verwendeten Index-Spalten. leaf_blocks * effective index selectivity repräsentiert dabei die Kosten des Zugriffs auf die Index-Struktur, von der ein durch die effective index selectivity bestimmter Anteil gelesen werden muss.

Zur effective table selectivity schreibt Jonathan Lewis, sie solle "be based only on those predicates that can be evaluated in the index, before you reach the table." (S. 67) Da mir dieser Punkt noch immer nicht völlig klar ist dazu ein kleiner Test (mit 11.2.0.1):

-- Anlage einer Test-Tabelle mit einem zusammengesetzten Index
drop table test_ind_selectivity;

create table test_ind_selectivity tablespace test_ts
as
select rownum id
     , mod(rownum, 10) col1 -- 10 unterschiedliche Werte -> Selektivität: 0,1
     , mod(rownum, 100) col2 -- 100 unterschiedliche Werte -> Selektivität: 0,01 
     , mod(rownum, 1000) col3 -- 1000 unterschiedliche Werte -> Selektivität: 0,001  
     , lpad('*', 100, '*') pad
  from dual
connect by level <= 1000000;

exec dbms_stats.gather_table_stats(user, 'TEST_IND_SELECTIVITY', method_opt=>'FOR ALL COLUMNS SIZE 1')

create index test_ind_selectivity_ix1 on test_ind_selectivity(col1, col2, col3);

Für den Index ergeben sich folgende Statistiken:

select index_name
     , blevel
     , leaf_blocks
     , clustering_factor
  from user_indexes
 where table_name = upper('test_ind_selectivity');

INDEX_NAME                         BLEVEL LEAF_BLOCKS CLUSTERING_FACTOR
------------------------------ ---------- ----------- -----------------
TEST_IND_SELECTIVITY_IX1                2        2894           1000000

Ich könnte jetzt die tatsächlichen Kosten von Queries ermitteln und versuchen, passende Werte für die Selektivitäten einzusetzen, aber ich mache mir die Sache ganz einfach und erzeuge ein 10053er Trace:

ALTER SESSION SET EVENTS '10053 trace name context forever, level 1';

select /*+ index(test_ind_selectivity) test1 */ count(id) from test_ind_selectivity where col1 = 1;

select /*+ index(test_ind_selectivity) test2 */ count(id) from test_ind_selectivity where col1 = 1 and col2 = 1;

select /*+ index(test_ind_selectivity) test3 */ count(id) from test_ind_selectivity where col1 = 1 and col2 = 1 and col3 = 1;

select /*+ index(test_ind_selectivity) test4 */ count(id) from test_ind_selectivity where col1 = 1 and col3 = 1;

ALTER SESSION SET EVENTS '10053 trace name context OFF';

Für die Queries ergeben sich folgende Trace-Inhalte:

Fall 1: where col1 = 1

***************************************
BASE STATISTICAL INFORMATION
***********************
Table Stats::
  Table: TEST_IND_SELECTIVITY  Alias: TEST_IND_SELECTIVITY
    #Rows: 1000000  #Blks:  16907  AvgRowLen:  116.00
Index Stats::
  Index: TEST_IND_SELECTIVITY_IX1  Col#: 2 3 4
    LVLS: 2  #LB: 2894  #DK: 1000  LB/K: 2.00  DB/K: 1000.00  CLUF: 1000000.00
    User hint to use this index
Access path analysis for TEST_IND_SELECTIVITY
***************************************
SINGLE TABLE ACCESS PATH 
  Single Table Cardinality Estimation for TEST_IND_SELECTIVITY[TEST_IND_SELECTIVITY] 
  Table: TEST_IND_SELECTIVITY  Alias: TEST_IND_SELECTIVITY
    Card: Original: 1000000.000000  Rounded: 100000  Computed: 100000.00  Non Adjusted: 100000.00

  Access Path: index (RangeScan)
    Index: TEST_IND_SELECTIVITY_IX1
    resc_io: 100292.00  resc_cpu: 751223460
    ix_sel: 0.100000  ix_sel_with_filters: 0.100000 
    Cost: 100292.15  Resp: 100292.15  Degree: 1
  Best:: AccessPath: IndexRange
  Index: TEST_IND_SELECTIVITY_IX1
         Cost: 100292.15  Degree: 1  Resp: 100292.15  Card: 100000.00  Bytes: 0

***************************************

Die ix_sel repräsentiert im 10053er Trace die effective index selectivity, während die ix_sel_with_filters für die effective table selectivity steht. Beide Werte sind für die erste Query 0,1 - und entsprechen damit der Selektivität der Einzel-Spalte. Setzt man die Werte in die Formel ein, ergibt sich:

• blevel + ceiling(leaf_blocks + effective index selectivity) + ceiling(clustering_factor * effective table selectivity)
• 2 + ceil(2894 * 0,1) + ceil(1000000 * 0,1)
• 2 + 290 + 100000 = 100292

Das passt dann schon mal zur resc_io, die offenbar den I/O-Anteil der Kosten darstellt. Die zusätzlichen 0,15 in den Kosten sind dann vermutlich der CPU-Anteil.

Fall 2: where col1 = 1 and col2 = 1

***************************************
BASE STATISTICAL INFORMATION
***********************
Table Stats::
  Table: TEST_IND_SELECTIVITY  Alias: TEST_IND_SELECTIVITY
    #Rows: 1000000  #Blks:  16907  AvgRowLen:  116.00
Index Stats::
  Index: TEST_IND_SELECTIVITY_IX1  Col#: 2 3 4
    LVLS: 2  #LB: 2894  #DK: 1000  LB/K: 2.00  DB/K: 1000.00  CLUF: 1000000.00
    User hint to use this index
Access path analysis for TEST_IND_SELECTIVITY
***************************************
SINGLE TABLE ACCESS PATH 
  Single Table Cardinality Estimation for TEST_IND_SELECTIVITY[TEST_IND_SELECTIVITY] 
  ColGroup (#1, Index) TEST_IND_SELECTIVITY_IX1
    Col#: 2 3 4    CorStregth: -1.00
  ColGroup Usage:: PredCnt: 2  Matches Full:  Partial: 
  Table: TEST_IND_SELECTIVITY  Alias: TEST_IND_SELECTIVITY
    Card: Original: 1000000.000000  Rounded: 1000  Computed: 1000.00  Non Adjusted: 1000.00
  ColGroup Usage:: PredCnt: 2  Matches Full:  Partial: 
  ColGroup Usage:: PredCnt: 2  Matches Full:  Partial: 
  Access Path: index (RangeScan)
    Index: TEST_IND_SELECTIVITY_IX1
    resc_io: 1005.00  resc_cpu: 7547047
    ix_sel: 0.001000  ix_sel_with_filters: 0.001000 
    Cost: 1005.00  Resp: 1005.00  Degree: 1
  Best:: AccessPath: IndexRange
  Index: TEST_IND_SELECTIVITY_IX1
         Cost: 1005.00  Degree: 1  Resp: 1005.00  Card: 1000.00  Bytes: 0

***************************************

In diesem Fall sind beide Selektivitäten auf 0,001 (also das Produkt der Selektivitäten der Einzelspalten 0,1 * 0,01) gesetzt, was auch wieder den Erwartungen entspricht. In der Formel ergibt sich für die Komponenten 2 + 3 + 1000.

Fall 3: where col1 = 1 and col2 = 1 and col3 = 1

***************************************
BASE STATISTICAL INFORMATION
***********************
Table Stats::
  Table: TEST_IND_SELECTIVITY  Alias: TEST_IND_SELECTIVITY
    #Rows: 1000000  #Blks:  16907  AvgRowLen:  116.00
Index Stats::
  Index: TEST_IND_SELECTIVITY_IX1  Col#: 2 3 4
    LVLS: 2  #LB: 2894  #DK: 1000  LB/K: 2.00  DB/K: 1000.00  CLUF: 1000000.00
    User hint to use this index
Access path analysis for TEST_IND_SELECTIVITY
***************************************
SINGLE TABLE ACCESS PATH 
  Single Table Cardinality Estimation for TEST_IND_SELECTIVITY[TEST_IND_SELECTIVITY] 
  ColGroup (#1, Index) TEST_IND_SELECTIVITY_IX1
    Col#: 2 3 4    CorStregth: 1000.00
  ColGroup Usage:: PredCnt: 3  Matches Full: #1  Partial:  Sel: 0.0010
  Table: TEST_IND_SELECTIVITY  Alias: TEST_IND_SELECTIVITY
    Card: Original: 1000000.000000  Rounded: 1000  Computed: 1000.00  Non Adjusted: 1000.00
  ColGroup Usage:: PredCnt: 3  Matches Full: #1  Partial:  Sel: 0.0010
  ColGroup Usage:: PredCnt: 3  Matches Full: #1  Partial:  Sel: 0.0010
  Access Path: index (AllEqRange)
    Index: TEST_IND_SELECTIVITY_IX1
    resc_io: 1005.00  resc_cpu: 7567047
    ix_sel: 0.001000  ix_sel_with_filters: 0.001000 
    Cost: 1005.00  Resp: 1005.00  Degree: 1
  Best:: AccessPath: IndexRange
  Index: TEST_IND_SELECTIVITY_IX1
         Cost: 1005.00  Degree: 1  Resp: 1005.00  Card: 1000.00  Bytes: 0

***************************************

Die Werte für ix_sel und ix_sel_with_filters sind mit denen in Fall 2 identisch. Ein offensichtlicher Unterschied sind die Angaben unter Partial und CorStregth (wo vielleicht ein n fehlt) - zu diesen Einträgen im CBO-Trace hat Randolf Geist im Rahmen einer Untersuchung von Korrelationseffekten und extended statistics (die wiederum auf einen Artikel von Riyaj Shamsudeen Bezug nimmt) gelegentlich ein paar Erläuterungen gegeben, die ich so interpretiere, dass die Angaben etwas über die Korrelation der Spaltenwerte aussagen und durch extended statistics und Histogramme beeinflusst werden können. Die Werte in Fall 3 scheinen anzudeuten, dass der CBO die Korrelation der Spalten erkennt, aber wie er das macht, ist mir unklar, da keine extended statistics erzeugt wurden (und auch keine Histogramme: method_opt=>'FOR ALL COLUMNS SIZE 1'). In jedem Fall entsprechen die Kosten exakt denen von Fall 2.

Nachtrag 24.12.2011: Die Antwort auf meine Frage liefert Randolf Geists Kommentar: im gegebenen Fall eines Zugriffs mit Einschränkung auf alle Index-Spalten kann der CBO die Index-Statistiken verwenden, statt sich mit der indirekten Bestimmung über die Tabellenspalten-Statistiken behelfen zu müssen.

Fall 4: where col1 = 1 and col3 = 1

***************************************
BASE STATISTICAL INFORMATION
***********************
Table Stats::
  Table: TEST_IND_SELECTIVITY  Alias: TEST_IND_SELECTIVITY
    #Rows: 1000000  #Blks:  16907  AvgRowLen:  116.00
Index Stats::
  Index: TEST_IND_SELECTIVITY_IX1  Col#: 2 3 4
    LVLS: 2  #LB: 2894  #DK: 1000  LB/K: 2.00  DB/K: 1000.00  CLUF: 1000000.00
    User hint to use this index
Access path analysis for TEST_IND_SELECTIVITY
***************************************
SINGLE TABLE ACCESS PATH 
  Single Table Cardinality Estimation for TEST_IND_SELECTIVITY[TEST_IND_SELECTIVITY] 
  ColGroup (#1, Index) TEST_IND_SELECTIVITY_IX1
    Col#: 2 3 4    CorStregth: -1.00
  ColGroup Usage:: PredCnt: 2  Matches Full:  Partial: #1 (2 4 )  Sel: 0.0010
  Table: TEST_IND_SELECTIVITY  Alias: TEST_IND_SELECTIVITY
    Card: Original: 1000000.000000  Rounded: 1000  Computed: 1000.00  Non Adjusted: 1000.00
kkofmx: index filter:"TEST_IND_SELECTIVITY"."COL3"=1


  ColGroup Usage:: PredCnt: 2  Matches Full:  Partial: #1 (2 4 )  Sel: 0.0010
  ColGroup Usage:: PredCnt: 2  Matches Full:  Partial: #1 (2 4 )  Sel: 0.0010
  Access Path: index (skip-scan)
    SS sel: 0.001000  ANDV (#skips): 100.000000
    SS io: 300.000000 vs. index scan io: 8455.000000
    Skip Scan rejected
  Access Path: index (RangeScan)
    Index: TEST_IND_SELECTIVITY_IX1
    resc_io: 1292.00  resc_cpu: 29410900
    ix_sel: 0.100000  ix_sel_with_filters: 0.001000 
 ***** Logdef predicate Adjustment ****** 
 Final IO cst 0.00 , CPU cst 50.00
 ***** End Logdef Adjustment ****** 
    Cost: 1292.01  Resp: 1292.01  Degree: 1
  Best:: AccessPath: IndexRange
  Index: TEST_IND_SELECTIVITY_IX1
         Cost: 1292.01  Degree: 1  Resp: 1292.01  Card: 1000.00  Bytes: 0

***************************************

In diesem Fall erscheinen nur die führende und die letzte Spalte des Index in der WHERE-Bedingung. Einleuchtend ist deshalb die ix_sel, die nur die Selektivität der führenden Spalte berücksichtigt: aufgrund der Einschränkung müssen 10% der Index-Struktur durchsucht werden, um alle Sätze mit col1 = 1 zu ermitteln, ehe dann die Filterung auf col3 = 1 erfolgen kann. Aber die ix_sel_with_filters ist mir nicht ganz klar, denn sie ergibt sich nicht aus der Selektivität der beiden Spalten (0,1 * 0,001 wären 0,0001). Möglicherweise ist auch hier eine Korrelationsbestimmung im Spiel, denn die ix_sel_with_filters = 0.001000 entspricht der Angabe in:  Partial: #1 (2 4 ) Sel: 0.0010. Auch in diesem Fall ist mir unklar, wie der CBO die Korrelation erkennen kann.

Interessant ist darüber hinaus noch der Plan für die vierte Query, der sich im CBO-Trace ebenfalls findet:

============
Plan Table
============
----------------------------------------------------------------+-----------------------------------+
| Id  | Operation                     | Name                    | Rows  | Bytes | Cost  | Time      |
----------------------------------------------------------------+-----------------------------------+
| 0   | SELECT STATEMENT              |                         |       |       |  1292 |           |
| 1   |  SORT AGGREGATE               |                         |     1 |    12 |       |           |
| 2   |   TABLE ACCESS BY INDEX ROWID | TEST_IND_SELECTIVITY    |  1000 |   12K |  1292 |  00:00:07 |
| 3   |    INDEX RANGE SCAN           | TEST_IND_SELECTIVITY_IX1|  1000 |       |   292 |  00:00:02 |
----------------------------------------------------------------+-----------------------------------+
Predicate Information:
----------------------
3 - access("COL1"=1 AND "COL3"=1)
3 - filter("COL3"=1)

Hier erscheinen col1 und col3 als access-Prädikate und col3 dann noch einmal als Filter-Prädikat. Ich hatte erwartet, dass nur col1 als access-Prädikat verwendbar wäre und deshalb 100000 Sätze über den Index gelesen werden müssten, ehe die zusätzliche Filterung auf col3 = 1 erfolgen könnte, aber das ist offenbar nicht der Fall, wie die Ausführungsinformationen belegen:

select plan_table_output
  from table( dbms_xplan.display_cursor ( NULL, NULL, 'allstats'));

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------------------------
SQL_ID  gj6fuawjzpr51, child number 0
-------------------------------------
select /*+ index(test_ind_selectivity) gather_plan_statistics */
count(id) from test_ind_selectivity where col1 = 1 and col3 = 1

Plan hash value: 779399104

-------------------------------------------------------------------------------------------------------------------
| Id  | Operation                    | Name                     | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
-------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |                          |      1 |        |      1 |00:00:00.03 |    1296 |
|   1 |  SORT AGGREGATE              |                          |      1 |      1 |      1 |00:00:00.03 |    1296 |
|   2 |   TABLE ACCESS BY INDEX ROWID| TEST_IND_SELECTIVITY     |      1 |   1000 |   1000 |00:00:00.01 |    1296 |
|*  3 |    INDEX RANGE SCAN          | TEST_IND_SELECTIVITY_IX1 |      1 |   1000 |   1000 |00:00:00.01 |     296 |
-------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   3 - access("COL1"=1 AND "COL3"=1)
       filter("COL3"=1)

Tatsächlich liefert der Index-Zugriff also nur die 1000 relevanten Sätze, kann also die fehlende Spalte col2 überspringen - was durchaus plausibel ist, aber nicht unbedingt das, was ich erwartet hatte.

Nachtrag 24.12.2011: auch dazu liefert Randolf Geist in seinem Kommentar die Erklärung: der ACCESS liefert 296 von 1296 Blocks (und 100.000 Sätze) und anschließend erfolgt die FILTERung auf 1.000 Sätze. Das Erscheinen von col3 als ACCESS-Prädikat dient dabei offenbar nur zur Verwirrung... Hilfreich wär's, wenn die Informationen zum ACCESS auch noch bei den A-Rows auftauchen würden, wie Randolf unten anmerkt. Eine schöne Erklärung zur Interpretation von FILTER-Prädikaten in Index-Scan-Steps (und überhaupt zur Rolle von ACCESS- und FILTER-Prädikaten) findet man hier und hier bei Markus Winand.

Einmal mehr bin ich nicht unbedingt dort angelangt, wo ich hin wollte - nämlich bei einem klaren Verständnis der ix_sel_with_filters, aber für heute genügt's mir.