Donnerstag, Dezember 22, 2011

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.

Kommentare:

  1. Hallo Martin,

    ein Versuch, die verschiedenen Punkte aufzuklären:

    - Der Grund für die "ColGroup" und die von Dir nicht erwarteten Selektivitäten liegt in der Tatsache, dass der Optimizer die Statistiken des kombinierten Index verwendet für diese drei Spalten. Und der Index hat nun mal nur 1.000 eindeutige Werte, insofern kann die Selektivität der Gruppe dieser Spalten nicht über 0.001 hinausgehen: Du hast einen klassischen Fall von korrelierten Spaltenwerten gebaut, und da keine Extended Statistics da sind, verwendet der Optimizer eben die Index-Statistiken (und tut das auch schon in 10g wo es keine Extended Statistics gibt, denke ich)

    - Die unterschiedlichen Selektivitäten für den Index-Zugriff beschreiben, was direkt über den sog. ACCESS-Pfad gefunden werden kann, und was darüber hinaus bei einem weiterführenden SCAN dieser Daten noch im Index gefiltert werden kann, bevor auf die Tabelle zugegriffen wird.

    - Die ACCESS und FILTER-Bedingungen auf dem Index sagen Dir, dass nur "COL1"=1 für den tatsächlichen ACCESS-Zugriff in den Index verwendet werden kann. "COL3"=1 kann nur unter bestimmten Bedingungen verwendet werden, um etwas Arbeit zu sparen, daher taucht es auch noch in ACCESS auf (was ich persönlich eher verwirrend finde, eine schöne Erklärung dazu gibt es z.B. hier: http://use-the-index-luke.com/sql/where-clause/searching-for-ranges/greater-less-between-tuning-sql-access-filter-predicates). Das wichtige ist, dass "COL3"=1 nur durch FILTERN der Index-Daten bei dem RANGE SCAN angewendet werden kann, da COL2 übersprungen wurde und damit die Ordnung im Index nicht mehr verwendet werden kann für einen direkten Zugriff.

    Tatsächlich sind ja in Deinem Fall 10% der Index-Blöcke durchsucht worden 296 von 2894) - es sind also 100.000 Sätze im Index gelesen worden, von denen durch FILTERN nur noch 1.000 übrig geblieben sind.

    Es wäre sehr hilfreich, wenn Oracle zwei A-Rows-Statistiken führen würde: Anzahl der Rows "processed" und Anzahl der Rows "generated". Leider zeigt Oracle nur letzteres an, das erste wäre aber sehr, sehr hilfreich in vielen Fällen. Es würde nämlich die von Dir erwarteten 100.000 anzeigen

    Schöne Feiertage und einen guten Rutsch!

    Randolf

    AntwortenLöschen
  2. Hallo Randolf,

    vielen Dank für die Erläuterungen.

    Dass der CBO im Fall der Kombination aller drei Index-Spalten die Index-Statistiken verwendet, leuchtet ein, war mir aber nicht klar.

    Mein Verständnis der ACCESS- und FILTER-Prädikate entsprach, denke ich, Deinen Erklärungen, aber ich hatte die Buffers-Angabe nicht beachtet - und schließe mich an: COL3 ist als ACCESS-Prädikat irritierend. Außerdem hatte ich das FILTER-Prädikat aus irgendeinem Grund dem Tabellenzugriff zugeschlagen und übersehen, dass es ja schon in Schritt 3 auftritt (was inhaltlich natürlich auch völlig plausibel ist).

    Ich wünsche ebenfalls frohe Weihnachten und ein Gutes Neues Jahr.

    Martin

    AntwortenLöschen