Indizierung von NULL-Werten

Randolf Geist hat nach einer längeren Pause zuletzt wieder begonnen Blog-Artikel zu veröffentlichen, was mir sehr gut gefällt. In zwei Artikeln behandelt er die Effekte der Indizierung von NULL-Werten, insbesondere in Kombination mit IN/OR Prädikaten:

• Indexing Null Values - Part 1: zeigt zunächst ein Beispiel, in dem ein Index auf einem einzelnen Attribut durch Ergänzung einer Konstante dazu gebracht wird, auch NULL-Werte zu indizieren, was ein übliches Verfahren für derartige Fälle ist. Dieser Index wird dann auch für IS NULL Prädikate verwendet. Im Plan ist erwartungsgemäß zu sehen, dass ein weiteres Prädikat mit einer IN-Liste als Filter-Prädikat für die Tabelle auftaucht. Wenn man den Index neu erzeugt und dieses zweite Attribut als zweite Spalte des Index verwendet, führt die gleiche Query zu einem access-Prädikat für die NULL-Prüfung und einem Filter-Prädikat für die IN-Liste beim Index-Zugriff. Diese Filterung auf dem Index ist zwar günstiger als die Filterung in der Tabelle, aber eigentlich sollte es möglich sein, beide Prädikate im access zu verwenden. Dieser Effekt ist dann offenbar auch dafür verantwortlich, dass hier kein "inlist iterator" verwendet werden kann: anscheinend erlaubt die Implementierung hier keine Kombination der Prädikate aus IS NULL Prüfung und IN/OR Einschränkungen. Dieses Verhalten ändert sich, wenn man die Reihenfolge der Spalten im Index ändert und die Spalte der IS NULL Bedingung ans Ende der Spaltenliste setzt.
• Indexing Null Values - Part 2: behandelt das Verhalten von Bitmap Indizes in vergleichbaren Fällen. Hier ist der Bitmap Index mit mehreren Spalten natürlich eine unübliche Wahl - obwohl er bei entsprechender Datenverteilung ausgesprochen kompakt sein kann. Sichtbar wird, dass Oracle hier sehr merkwürdige Cost-Angaben erzeugt, die wenig mit dem tatsächlichen Aufwand beim Zugriff haben. Auch scheint die Darstellung von Filter- und Acces-Prädikaten im Plan nicht unbedingt viel mit der tatsächlichen Arbeit der runtime engine zu tun zu haben. Plausible Werte erhält man nur mit der vorgesehenen Verwendung einspaltiger Bitmap Indizes, obwohl der mehrspaltige Bitmap Index im Beispiel tatsächlich geringfügig effizienter ist.

Sollte die Serie fortgesetzt werden, ergänze ich die zugehörigen Artikel - vielleicht.

Wann ist ein Full Table Scan billiger als ein Index Fast Full Scan?

Und seit wann verwende ich in meinen Überschriften Fragezeichen? Fragen über Fragen. Aber eigentlich ist der Fall, den Jonathan Lewis in seinem aktuellen Blog-Artikel beschreibt, ebenso überschaubar wie erinnerungswürdig. Seine Fragen darin lauten: wieso werden die Kosten eines Full Table Scans auf einer Tabelle vom Optimizer als niedriger berechnet als die Kosten für den Index Fast Full Scan auf einem Index der Tabelle und warum ist der Index Fast Full Scan trotzdem effizienter in Hinblick auf die Laufzeit der Ausführung. Auf die Frage nach den Kosten gibt es eine wahrscheinliche und eine eher exotische Möglichkeit:

• die eher exotische Variante wäre: Index und Tabelle wurden mit unterschiedlichen Blockgrößen angelegt. Da eigentlich niemand (außer vielleicht dem Herrn Burleson) ohne gute Gründe (z.B. den Einsatz von Transportablen Tablespaces) auf die Idee kommt, mehrere Blockgrößen in einer Datenbank zu verwenden, tritt der Fall wohl eher selten auf.
• die wahrscheinlichere Erklärung ist: die Tabelle ist kleiner als der Index. Da ein Index Fast Full Scan (IFFS) tatsächlich ein Full Table Scan (FTS) des Index-Segments ist, basiert das Costing auf der Anzahl der Blocks im Segment. Wenn also die Tabelle kleiner ist als der Index, dann sind auch die Kosten des FTS niedriger als die des IFFS.

Im dem Artikel zugrunde liegenden OTN-Fall war tatsächlich die (aus meiner Sicht) wahrscheinlichere Variante Nr. 2 im Spiel: die Tabelle war kleiner als der Index. Grundsätzlich kann das leicht passieren, wenn eine Tabelle sehr schmal ist, da der Index ja immer noch zusätzlich zu den indizierten Spalten die rowid des Datensatzes enthält, aber im gegebenen Fall deuteten die Autotrace-Statistiken (consistent gets) nicht darauf hin, dass der Index größer war als die Tabelle. Die Ursache dafür war Compression, die für die Tabelle eingerichtet war, während der Index nicht komprimiert wurde - wobei natürlich auch noch zu berücksichtigen ist, dass die Index Compression technisch anders funktioniert als die Table Compression und unter jeweils anderen Voraussetzungen effektiv ist. Die Verwendung der Table Compression ist dann auch der Grund dafür, dass das Costing des Optimizers in diesem Fall den weniger effizienten Plan favorisiert: die Tabelle ist zwar geringfügig kleiner als der Index, aber das Entpacken der komprimierten Daten erfordert zusätzlichen CPU-Einsatz, so dass die Ausführung mit dem IFFS ein wenig schneller abläuft als die mit dem FTS. Interessant ist im Artikel auch, wie der Herr Lewis das Vorliegen der Table Compression und das Fehlen der Index Compression aus den Zahlen des zugehörigen CBO-Traces ermittelt, wobei das keine höhere Mathematik ist.

"Fixed Subqueries" und Partitionierte Tabellen

Jonathan Lewis weist in seinem aktuellen Scratchpad-Artikel darauf hin, dass neue Features des Optimizers nicht immer in allen relevanten Zusammenhängen folgerichtig integriert werden. Das Beispiel, an dem diese Schwierigkeit aufgezeigt wird, ist das der "fixed subqueries" - also Queries der Form "select 42 from dual" -, bei denen der Optimizer (seit 12c) dazu in der Lage ist, zu erkennen, dass der Wert 42 invariant ist, und daher bereits bei der Optimierung berücksichtigt werden kann. Im Artikel wird gezeigt, dass der Optimizer erwartungsgemäß dazu in der Lage ist, einschränkende Prädikate solcher "fixed subqueries" bei den Cardinality-Schätzungen korrekt zu berücksichtigen - und dass das nicht funktioniert, wenn der statische Wert durch eine Funktion verschleiert wird (also wenn satt 42 eine Funktion f(42) erscheint, die 42 zurückliefert). Wenn man aber statt einer einfachen eine partitionierte Tabelle verwendet, ergibt sich die erwähnte Uneinheitlichkeit: für den Fall der Funktionsverwendung ist das Verhalten folgerichtig, aber beim Einsatz des unveränderten Literalwertes wird dieser zwar bei der Cardinality-Schätzung berücksichtigt, nicht aber bei der Bestimmung der Pstart und Pstop values, die mit den Angaben KEY - KEY erscheinen - also zum Compile-Zeitpunkt anscheinend als unbekannt betrachtet werden. Offenbar ist das Verhalten also noch nicht in allen Zusammenhängen konsistent, was vermutlich in folgenden Releases korrigiert werden wird.

Grundlagen des kostenbasierten Optimizers

Jonathan Lewis hat für AllThingsOracle eine neue Serie Basics of the Cost Based Optimizer gestartet und liefert damit vermutlich eine neue Standardreferenz zum Thema. Allerdings weist der Autor darauf hin, dass die Serie eher einführenden Charakter besitzt und nicht allzu sehr auf die technischen Details eingeht, weshalb ich meine Zusammenfassungen eher knapp zu halten gedenke:

• Basics of the Cost Based Optimizer – Part 1: beschreibt die Grundlagen der Arbeit des Optimizers: um einen möglichst effektiven Zugriff zu ermöglichen erstellt er ein numerisches Modell basierend auf Informationen über den Daten (= Objektstatistiken), die Leistungsfähigkeit des Rechners (= Systemstatistiken) und die verfügbareb Ressourcen auf dem Rechner (= Konfiguration der Datenbank/Instanz). Dieses Modell ist natürlich nicht immer eine exakte Abbildung der realen Gegebenheiten und aus diesen Differenzen ergeben sich dann die Fehlentscheidungen des Optimizers. Dazu gibt es dann ein umfangreiches Beispiel eines Joins zweier Tabellen, die unter Verwendung unterschiedlicher Strategien miteinander gejoint werden können.
• Basics of the Cost Based Optimizer – Part 2: liefert Daten zu den in Teil 1 vorgestellten Objektdefinitionen (DDL) und zeigt, dass das Standardmodell relativ leicht zu Fehleinschätzungen führt, und wie man diese durch Konfigurationsänderungen korrigieren kann. Dabei enthalten die Daten eine Ungleichverteilung der Werte (skew). Im Beispiel werden die Optimizer-Kosten der Zugriffe sehr detailliert mit den zugehörigen I/O-Operationen auf Indizes und Tabellen verglichen. Zudem wird der durch ASM verzerrte Clustering Factor eines Index erläutert. Nach Korrektur des CF (durch Verwendung eines angemessenen table_cached_blocks-Parameters) verzichtet der Optimizer auf einen zunächst vorgesehenen Index Hash Join und verwendet stattdessen einen einfachen Index Range Scan mit folgendem Tabellenzugriff.
• Basics of the Cost Based Optimizer – Part 3: erläutert die Arbeitsweise und das Costing von Hash Joins und Nested Loops Joins. Im NL-Beispiel treten ausschließlich single block I/O Operationen auf, so dass die Reads im Plan mit rowsource statistics theoretisch exakt der cost Angabe entsprechen sollten: und das tun sie auch bei einer der beiden möglichen Reihenfolgen beim Tabellenzugriff, aber nicht bei der anderen, was mit dem Clustering der Daten zu tun hat (und der Effizienz des Cachings). Auch für den Hash Join ergibt sich eine sehr akkurate Cost-Angabe: in zwei der drei Test-Fälle ist das Modell also recht nah an der Realität. Aber im Fall von Nested Loops Joins kann der Optimizer die Caching Effekte nicht vorhersehen und neigt deshalb dazu, die Kosten für physical I/O zu überschätzen (was sich übrigens nicht solide durch die überholten Parameter optimizer_index_caching und optimizer_index_cost_adj korrigieren lässt).
• Basics of the Cost Based Optimizer – Part 4: erläutert die Rolle von Query Blocks und führt vor, welche Transformationen für ein Beispiel einer korrelierten Subquery möglich sind. Insbesondere weist er darauf hin, dass der Optimizer nicht immer die geeignetste Transformation auswählt, weshalb es wichtig ist, Einfluss auf die Umwandlungen nehmen zu können.
• Basics of the Cost Based Optimizer – Part 5: liefert zunächst eine knappe Zusammenfassung der älteren Artikel, da zwischen Teil 4 und Teil 5 der Serie ein gewisser Abstand lag. Im Anschluss werden die Begriffe cardinality (Anzahl Datensätze) und Selectivity (Anteil der Datensätze) eingeführt. Eine Hauptursache für ineffiziente Pläne ist das der Optimizer bei der Bestimmung der Selectivity oft keine präzise Informationsgrundlage hat - unter bestimmten Umständen kann er nur raten. Entsprechende Fälle sind:
• function(column) = constant: geschätzte Selectivity 1%. Korrigierbar mit virtual column.
• function(column) > constant: geschätzte Selectivity 5%. Beim range mit between wird daraus 5% * 5% = 0,25%. Korrigierbar mit virtual column.
• column = column: berücksichtigt die Anzahl distinkter Werte in beiden Spalten (1/greatest(num_distinct(col1), num_distinct(col2)). Korrigierbar mit dynamic sampling.
• combining columns: multipliziert die Selektivitäten, da der Optimizer unabhängige Werte erwartet. Korrigierbar mit extended statistics (column groups).
• Basics of the Cost Based Optimizer – part 6: beschäftigt sich mit vier Fällen, die in Teil 5 erwähnt, aber noch nicht erklärt worden waren. Ein erster Fall sind 5% Schätzungen für die Cardinality von Subqueries (mit einem "größer als" Prädikat), die man unter Umständen durch cardinality/opt_estimate Hints korrigieren kann. Ein zweiter Fall betrifft die Verwendung veralteter Statistiken, die einen unzutreffenden high_value etwa für Zeitangaben liefern, was durch häufiges Aktualisierung der Statistiken oder durch Setzen der high_values korrigiert werden kann. Die beiden letzten Fälle betreffen die Verwendung von Bind Variablen im Zusammenhang mit data skew, wobei einerseits die Begrenzung der maximalen Bucket-Anzahl auf 254 (in 11g) und die Verwendung von bind peeking eine Rolle spielen. Grundsätzlich gilt immer noch, dass Bind Variablen und Histogramme nicht gut miteinander harmonieren (weshalb der Einsatz von Literalen manchmal gar keine schlechte Idee ist).

Ich gehe davon aus, dass in der Serie noch weitere Artikel folgen werden, und diese werde ich dann voraussichtlich hier ergänzen.

Temp Table Transformation

Randolf Geist erläutert in seinem Blog das Verhalten der Temp Table Transformation, die hauptsächlich (aber nicht ausschließlich) dann anzutreffen ist, wenn eine CTE im Plan mehrfach referenziert wird und mindestens ein (Filter- oder Join-) Prädikat enthält, und weist insbesondere darauf hin, dass diese Transformation nicht kostenbasiert erfolgt, sondern automatisch. In Fällen, in denen eine zusätzliche Bedingung jenseits des CTE-Kontexts eine dramatische Reduzierung der Ergebnismenge hervorrufen würde, ist diese Materialisierung demnach ausgesprochen kontraproduktiv. Darüber hinaus rufen die materialiserten CTEs in solchen Fällen seit 11.2.0.4 offenbar extrem abwegige Cardinality-Schätzungen hervor, die in komplexeren Plänen sehr unglückliche Konsequenzen hervorrufen könnten. Insgesamt scheint es gute Gründe zu geben, die Materialisierung von CTEs sehr genau zu beobachten und ggf. durch den (nach wie vor undokumentierten) Inline-Hint zu vermeiden.

Nachtrag 22.05.2015: in einem Folgeartikel zeigt Randolf, dass die temp table transformation offenbar auch dazu führt, dass alle Spalten der CTE materialisiert werden und nicht nur die, die im Rahmen der folgenden Schritte tatsächlich benötigt werden. In vielen anderen Fällen ist Oracle sehr gut darin, die projection zu optimieren (Ausnahme: MERGE), aber hier ist das offenbar nicht so.

Korrektur der Join Cardinality

Laut Randolf Geist ist es "one of the most obvious weak spots of the optimizer: A filter on a table that is joined to another table that has a skewed value distribution in the FK column(s)." Der Satz ist die Antwort auf eine Frage im OTN-Forum, die ein recht kompaktes Beispiel enthielt, bei dem der Optimizer sich hinsichtlich der Cardinality eines Joins massiv verschätzt. Hier eine vereinfachte Version des einfachen Beispiels:

-- 11.2.0.1
drop table t1;
drop table t2;

create table t1
as
select rownum id
     , 'val_' || rownum col1
  from dual
connect by level <= 20;

create table t2
as
select case when rownum > 1000 then 20
            else mod(rownum, 19) + 1
            end id
  from dual
connect by level <= 10000;  

exec dbms_stats.gather_table_stats(user, 't1')
exec dbms_stats.gather_table_stats(user, 't2')

set autot on explain
 
select count(*)
  from t1
     , t2
 where t1.id = t2.id
   and t1.col1 = 'val_19'; 
   
select count(*)
  from t1
     , t2
 where t1.id = t2.id
   and t1.col1 = 'val_20';    
   
set autot off  

Das Skript liefert folgende Ergebnisse:

SQL> select count(*)
  2    from t1
  3       , t2
  4   where t1.id = t2.id
  5     and t1.col1 = 'val_19';

  COUNT(*)
----------
        52

Ausführungsplan
----------------------------------------------------------
Plan hash value: 906334482

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |    13 |     5  (20)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |    13 |            |          |
|*  2 |   HASH JOIN         |      |   500 |  6500 |     5  (20)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL| T1   |     1 |    10 |     2   (0)| 00:00:01 |
|   4 |    TABLE ACCESS FULL| T2   | 10000 | 30000 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------

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

   2 - access("T1"."ID"="T2"."ID")
   3 - filter("T1"."COL1"='val_19')

SQL> select count(*)
  2    from t1
  3       , t2
  4   where t1.id = t2.id
  5     and t1.col1 = 'val_20';

  COUNT(*)
----------
      9000

Ausführungsplan
----------------------------------------------------------
Plan hash value: 906334482

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |    13 |     5  (20)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |    13 |            |          |
|*  2 |   HASH JOIN         |      |   500 |  6500 |     5  (20)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL| T1   |     1 |    10 |     2   (0)| 00:00:01 |
|   4 |    TABLE ACCESS FULL| T2   | 10000 | 30000 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------

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

   2 - access("T1"."ID"="T2"."ID")
   3 - filter("T1"."COL1"='val_20')

Obwohl sich die Anzahl der Ergebnissätze massiv unterscheidet (52 zu 9000) schätzt der Optimizer die Join-Cardinality in beiden Fällen auf 500. Dieser Wert ergibt sich aus der Verwendung der Standard-Formeln zur Berechung von Join-Selectivity und -Cardinality:

Join Selectivity = 1 / greater(num_distinct(t1.id), num_distinct(t2.id))
Join Cardinality = Join Selectivity * cardinality t1 * cardinality t2

Im Beispiel ergibt sich:

Join Selectivity = 1 / greater(20, 20) = 0,05
Join Cardinality = 0,05 * 1 * 10000 = 500

Im gegebenen Fall kann der menschliche Betrachter zwar unmittelbar erkennen, dass ein Wert für col1 einen entsprechenden Wert für id bedingt, aber der Optimizer ist in einer weniger günstigen Situation: er besitzt jeweils nur die Statistiken einer Tabelle: er weiß, dass der Zugriff auf t1 nur einen Satz liefern wird, aber zum Zeitpunkt der Optimierung kann er nicht bestimmen, welchem Satz der zweiten Tabelle diese Angabe entsprechen wird: dazu müsste er den Join bereits durchführen. Auch Histogramme helfen in diesem Fall nicht. Allerdings nennt Randolf Geist zwei Möglichkeiten mit deren Hilfe der Optimizer zu korrekten Cardinalities für den Join kommt - wobei beide Varianten wiederum recht massive Nachteile mit sich bringen. In 11.2 kann man den Hint precompute_subquery einsetzen, der zwar nicht offiziell dokumentiert ist, aber von Tanel Poder recht detailliert beschreiben wurde. Im Plan ergibt sich durch die Verwendung des Hints ein recht merkwürdiges Bild:

select count(*)
  from t2
 where t2.id in (select /*+ precompute_subquery */ t1.id
                   from t1
                  where t1.col1 = 'val_20');

  COUNT(*)
----------
      9000

Ausführungsplan
----------------------------------------------------------
Plan hash value: 3321871023

---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |     3 |     2   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE    |      |     1 |     3 |            |          |
|*  2 |   TABLE ACCESS FULL| T2   |   500 |  1500 |     2   (0)| 00:00:01 |
---------------------------------------------------------------------------

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

   2 - filter("T2"."ID"=20)

exec dbms_stats.gather_table_stats(user, 't2', method_opt => 'for all columns size 254')

--> erneute Ausführung

Ausführungsplan
----------------------------------------------------------
Plan hash value: 3321871023

---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |     3 |     2   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE    |      |     1 |     3 |            |          |
|*  2 |   TABLE ACCESS FULL| T2   |  9000 | 27000 |     2   (0)| 00:00:01 |
---------------------------------------------------------------------------

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

   2 - filter("T2"."ID"=20)

In diesem Fall wird die Subquery vor der Optimierung der Haupt-Query ausgewertet und das Ergebnis des ersten Schritts bei der Planung des zweiten Schritts zugrunde gelegt. Für die id-Spalte in t2 müssen allerdings Histogramme vorliegen, damit die ungleiche Verteilung der Werte berücksichtigt werden kann. Allerdings stellt Randolf Geist fest: "However the PRECOMPUTE_SUBQUERY is undocumented (and comes with some odd behaviour for more complex queries), hence no good solution." In Oracle 12 gibt es als Alternative dazu noch das dynamic_sampling auf Level 11, das die Join-Cardinalities durch explizite Prüfung der Datengrundlage korrrigiert:

-- 12.1.0.1
select /*+ dynamic_sampling (11) */count(*)
  from t1
     , t2
 where t1.id = t2.id
   and t1.col1 = 'val_20';

Ausführungsplan
----------------------------------------------------------
Plan hash value: 906334482

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |    13 |    10   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |    13 |            |          |
|*  2 |   HASH JOIN         |      |  9000 |   114K|    10   (0)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL| T1   |     1 |    10 |     3   (0)| 00:00:01 |
|   4 |    TABLE ACCESS FULL| T2   | 10000 | 30000 |     7   (0)| 00:00:01 |
----------------------------------------------------------------------------

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

   2 - access("T1"."ID"="T2"."ID")
   3 - filter("T1"."COL1"='val_20')

Note
-----
   - dynamic statistics used: dynamic sampling (level=0)

Aber auch hier gilt:

However, this feature, too, comes at a price. At present I think one of the two row sources joined will be processed in its entirety during the sampling, so I don't think it's a viable option for large tables being joined, but I haven't done any exhaustive tests with this new feature. Since Oracle themselves don't enable it by default it looks like a bit experimental anyway.

Zu dieser Aussage passt die Beobachtung, dass ein zugehöriges SQL Trace (Event 10046) unter anderem Folgendes enthält:

SELECT /* DS_SVC */ /*+ cursor_sharing_exact dynamic_sampling(0) no_sql_tune 
  no_monitoring optimizer_features_enable(default) result_cache */ SUM(C1) 
FROM
 (SELECT /*+ qb_name("innerQuery") NO_INDEX_FFS( "T2#0")  */ 1 AS C1 FROM 
  "T2" "T2#0", "T1" "T1#1" WHERE ("T1#1"."COL1"='val_20') AND ("T1#1"."ID"=
  "T2#0"."ID")) innerQuery


call     count       cpu    elapsed       disk      query    current        rows
------- ------  -------- ---------- ---------- ---------- ----------  ----------
Parse        1      0.00       0.00          0          0          0           0
Execute      1      0.00       0.00          0          0          0           0
Fetch        1      0.00       0.00          0         22          0           1
------- ------  -------- ---------- ---------- ---------- ----------  ----------
total        3      0.00       0.00          0         22          0           1

Misses in library cache during parse: 0
Optimizer mode: ALL_ROWS
Parsing user id: 110     (recursive depth: 1)
Number of plan statistics captured: 1

Rows (1st) Rows (avg) Rows (max)  Row Source Operation
---------- ---------- ----------  ---------------------------------------------------
         1          1          1  RESULT CACHE  7cy3yc33w1z8m0wa5xpc39wqcb (cr=22 pr=0 pw=0 time=4854 us)
         1          1          1   SORT AGGREGATE (cr=22 pr=0 pw=0 time=4824 us)
      9000       9000       9000    HASH JOIN  (cr=22 pr=0 pw=0 time=5399 us cost=10 size=6500 card=500)
         1          1          1     TABLE ACCESS FULL T1 (cr=3 pr=0 pw=0 time=34 us cost=3 size=10 card=1)
     10000      10000      10000     TABLE ACCESS FULL T2 (cr=19 pr=0 pw=0 time=1922 us cost=7 size=30000 card=10000)

Unter den Row Source Operation-Angaben findet sich also noch die card=500 des ursprünglichen Plans - und das Ergebnis dieser Query wird dann zur Bestimmung der korrekten Cardinality verwendet: das scheint noch nicht unbedingt eine besonders effiziente Lösung zu sein.

Da der Artikel etwas länger geworden ist, spendiere ich ausnahmsweise ein Fazit: der Optimizer hat seine Probleme mit der Bestimmung von Join Kardinalitäten, wenn ein Filter auf einer Tabelle eingesetzt wird, die mit einer zweiten Tabelle gejoint wird, bei der für die Spalten des Foreign Key eine Ungleichverteilung vorliegt. Es gibt zwei mögliche Workarounds zur Korrektur dieser Fehleinschätzungen, aber diese Workarounds schaffen möglicherweise mehr Probleme als sie lösen. Ein expliziter Dank noch mal an Randolf Geist, der an dieser Stelle mal wieder erstaunliche Details geliefert hat.

Nachtrag 28.08.2014: Sayan Malakshinov weist darauf hin, dass der PRECOMPUTE_SUBQUERY-Hint für query blocks angegeben und somit im Zusammenspiel mit SQL Profiles, Baselines und Patches eingesetzt werden kann.

Cardinality für IN-Listen mit NULL-Werten in 12.1

Ein sperriger Titel für eine einfache Beobachtung. Vor etwas mehr drei Jahren hatte ich hier überprüft, wie sich die von Jonathan Lewis in Cost Based Oracle beschriebene Berechnung von Cardinalities für IN-Listen unterschiedlicher Struktur in neueren Releases verändert hatte. Zu den Fällen, die im Buch untersucht wurde, gehörten:

• wiederholte Werte
• Werte außerhalb des Korridors bekannter Werte (not between low_value and high_value)
• NULL-Werte

Wobei es zu jedem dieser Fälle unterschiedliche Varianten gab. Bereits in 11.2.0.1 verhielten sich alle untersuchten Fälle bis auf einen ganz plausibel. Der verbliebene Fall war die Behandlung von NULL-Werten - und diesen Fall habe ich mir jetzt noch mal mit 12.1.0.1 angesehen:

-- 12.1.0.1
create table test_inlist
as
select rownum pk_col
     , mod(rownum, 12) mon_col
     , lpad('*', 100, '*') pad_col
  from dual
connect by level <= 120000;

exec dbms_stats.gather_table_stats (ownname=>user, tabname=>'TEST_INLIST', estimate_percent=>dbms_stats.auto_sample_size)

select column_name
     , num_distinct
     , num_nulls
     , density
     , num_buckets
  from user_tab_columns
 where table_name = 'TEST_INLIST'
   and column_name = 'MON_COL';

COLUMN_NAME                    NUM_DISTINCT  NUM_NULLS    DENSITY NUM_BUCKETS
------------------------------ ------------ ---------- ---------- -----------
MON_COL                                  12          0 ,083333333           1

select count(*)
  from test_inlist
 where mon_col in (3, 25, null);

Plan hash value: 3620027018

----------------------------------------------------------------------------------
| Id  | Operation          | Name        | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |             |     1 |     3 |   529   (1)| 00:00:01 |
|   1 |  SORT AGGREGATE    |             |     1 |     3 |            |          |
|*  2 |   TABLE ACCESS FULL| TEST_INLIST | 10000 | 30000 |   529   (1)| 00:00:01 |
----------------------------------------------------------------------------------

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

   2 - filter("MON_COL"=3 OR "MON_COL"=25)

Die einschränkende Bedingung enthält somit einen Wert innerhalb des bekannten Wertebereichs (3), einen Wert weit jenseits des bekannten Wertebereichs (25) und einen NULL-Wert. In 11.2.0.1 wurde dafür noch eine Cardinality von 20000 berechnet: 10000 für den Wert 3, 0 für den Wert 25 und wieder 10000 für den Wert NULL. In 12.1 ist das Verhalten korrigiert, denn mon_col in (NULL) liefert natürlich kein Ergebnis, so dass die angenommenen 10000 dem tatsächlichen Ergebnis entsprechen.

Korrigierte CBO-Cardinality-Schätzungen für OR-Prädikate

Stefan Koehler weist in seinem Blog darauf hin, dass ein von Jonathan Lewis in Cost Based Oracle beschriebenes Problem in aktuelleren Releases behoben ist: OR-verknüpfte Range-Prädikate, die den kompletten Wertebereich einer Tabelle umfassen, werden nun in ein einfaches IS NOT NULL Prädikat umgewandelt. Das handliche Beispiel dafür ist in Blog und Buch eine Monatsliste mit der dafür definierten Einschränkung:

where MONTH_NO > 8 OR MONTH_NO <= 8

In 10.2.0.5 führte diese Ausgangslage noch zu einer Addition der ermittelten Cardinality beider Ranges, was zu einer (leichten) Unterschätzung der Anzahl führte (im Beispiel 986 statt 1200). Mit dem IS NOT NULL Prädikat, das der Optimizer hier (zumindest) seit 11.2 über einen Transformationsschritt einsetzen kann, kommt diese Fehleinschätzung nicht mehr zustande - wobei ich die Korrektur auch schon in 11.2.0.1 sehe (aber leider keine 11.1er Systeme zur Hand habe).

Da ich nicht glaube, dass Jonathan Lewis Zeit in eine überarbeitete Neuauflage von Cost Based Oracle investieren wird (was aus meiner Sicht bedauerlich, aber auch sehr verständlich ist), halte ich derartige Überprüfungen des im Buch beschriebenen Verhaltens unter Verwendung aktueller Releases für extrem nützlich und wichtig.

Änderung für NVL costing

Jonathan Lewis weist in seinem Blog darauf hin, dass die cardinality für Prädikate der Form: NVL(spalte, konstanter_datumswert) bis Version 11.1.0.7 mit dem Standardwert "5% for range-based predicate on function(col)" berechnet wurde, aber in 11.2.0.4 eine plausiblere Behandlung erfährt, die das Prädikat in den NULL-Fall und den Fall des Vergleichs der vorhandenen Werte aufspaltet, und dadurch deutlich zutreffendere Schätzungen liefert (was für ähnlich gelagerte Fälle auch schon in früheren Releases möglich war). Zwischen 11.2.0.1 und 11.2.0.3 scheint die Überarbeitung des Verhaltens allerdings erst einmal in die falsche Richtung geführt zu haben (wie die Kommentare zum Artikel zeigen). Erinnerungswürdig ist aber in jedem Fall dass dies wieder eine jener Optimierungen ist, die beim Upgrade eines Systems zur recht massiven Planänderungen führen können.

Kostenbasierte Optimierung mit Postgres

Mit den Details der kostenbasierten Optimierung von SQL-Queries in Oracle beschäftige ich mich, seit ich Jonathan Lewis' Standardwerk Cost Based Oracle zum ersten Mal gelesen habe - was ziemlich bald nach seiner Veröffentlichung im Jahr 2005 geschehen sein dürfte. Nachdem ich inzwischen etwa ein halbes Jahr lang mehr oder minder intensiv mit Postgres gearbeitet habe, bin ich nun endlich dazu gekommen, einen etwas genaueren Blick auf die kostenbasierte Optimierung in diesem RDBMS zu werfen, und dabei unter anderem zu folgenden Erkenntnissen gekommen:

• Die beeindruckend klar strukturierte online-Dokumentation für postgres enthält eine Menge von Detailinformationen zum Ablauf der Erzeugung des Ausführungsplans für eine Query und auch einige Erläuterungen zum Costing.
• Darüber hinaus kann man sich auch noch den Code der Costing-Komponente anschauen, insbesondere die Implementierung von costsize.c, die letztlich alle Fragen zum Costing beantworten dürfte. Wenn man aus dem Oracle-Kosmos kommt, in dem die Entscheidungen des Optimizers nur durch Induktion - sprich: Beobachtung und Interpretation des Verhaltens - zu erklären sind, ist diese Basis natürlich ein erstaunlicher Luxus. Wobei ich an dieser Stelle noch ergänzen möchte, dass der Oracle-Optimizer in dieser Hinsicht meiner Einschätzung nach sehr viel intensiver untersucht wurde als die entsprechenden Komponenten anderer RDBMS, die ihren Quellcode nicht offen legen.
• Da mir die Analyse des recht umfangreichen Codes in costsize.c zu aufwändig ist (was möglicherweise mehr über meine Code-Analyse-Fähigkeiten aussagt als über den Code), beschränke ich mich doch wieder auf die angesprochenen induktiven Strategien (und die allgemein bekannten Formeln).
• Die kostenbasierte Optimierung verwendet in ihren Kalkulationen diverse statistische Informationen zu den verwendeten Objekten (Tabellen, Indizes) und einige fest definierte Parameterwerte. Die statistischen Informationen können explizit über das ANALYZE-Kommando ermittelt werden, aber in der Regel übernimmt der autovacuum deamon diesen Job, der für diverse Maintenance-Aufgaben zuständig ist (vor allem auch für die automatische Reorganisation von Objekten zur Freigabe von Speicherplatz durch Ausführung des VACUUM-Kommandos).
• Zu den statistischen Informationen, die über ANALYZE gesammelt werden, gehören:
• die Tabellenstatistiken in pg_class:
• relpages: Anzahl der pages des Objekts auf der Festplatte (wobei eine page dem Block der Oracle-Nomenklatur entspricht).
• pg_class.reltuples: Anzahl der Datensätze.
• die Spaltenstatistiken in pg_stats:
• null_frac: Anteil von NULL-Werten.
• avg_width: durchschnittliche Spaltenbreite in Byte.
• n_distinct: Anzahl distinkter Werte in der Spalte.
• most_common_vals: eine Liste der populärsten (= am häufigsten auftretenden) Werte in der Spalte. Für Oracle entspricht diese Angabe den Informationen eines Histogramms - tatsächlich eines top-n-frequency Histogramms, das für Oracle erst in 12c eingeführt wurde, also eines Histogramms, das sich auf Informationen zur Häufigkeit der Top-n-Werte mit den meisten Wiederholungen beschränkt.
• most_common_freqs: die zu den Angaben in most_common_vals gehörigen Angaben zur Wiederholungshäufigkeit der Werte.
• correlation: die statistische Korrelation der logischen Sortierung der Spaltenwerte und ihrer physikalischen Sortierung auf der Platte. Diese Angabe besitzt also eine relativ große Nähe zum Clustering-Factor für Oracle-Indizes.
• Zusätzlich zu den statistischen Informationen werden im Costing unter anderem folgende Parameter berücksichtigt:
• seq_page_cost (default: 1): die Kosten eines Page-Zugriffs im Rahmen eines sequenziellen Scans (also eines Full Table Scans).
• random_page_cost (default: 4): Kosten für einen nicht-sequenziellen Page-Scan (also z.B. einen Index-Zugriff). Tatsächlich ist der nicht-sequenziellen Page-Scan im Verhältnis zum sequenziellen Scan deutlich teurer als der default-Faktor 4 andeutet, aber bei der Wahl der Defaults liegt die (durchaus plausible) Annahme zugrunde, dass die Index-Blocks relativ häufig im Cache zu finden sind.
• cpu_tuple_cost (default: 0.01): Kosten für das Abrufen einer Ergebniszeile in einem Select.
• cpu_index_tuple_cost (default: 0.005): Kosten für den Zugriff auf einen Index-Eintrag.
• cpu_operator_cost (default: 0.0025): Kosten für die Verwendung eines Operators oder einer Funktion.
• effective_cache_size (default: 128MB): Informationen zur Größe des Caches. Ein höherer Wert macht Index-Zugriffe wahrscheinlicher.

Dazu noch ein kleines Beispiel mit einigen harmlosen Costing-Berechnungen:

-- 9.3
-- Anlage einer Testtabelle mit 10000 Datensätzen
drop table t;

create table t
as
with
basedata as (
select * from generate_series(1, 10000) id
)
select id
     , mod(id, 10) col1
     , '**********************************'::text col2
  from basedata
;

-- manuelle Statistikerfassung
analyze t;

-- Ausgabe der erstellten Statistiken
select * from pg_class where relname = 't';
-[ RECORD 1 ]--+-------
relname        | t
relnamespace   | 2200
reltype        | 112466
reloftype      | 0
relowner       | 10
relam          | 0
relfilenode    | 112464
reltablespace  | 0
relpages       | 94
reltuples      | 10000
relallvisible  | 0
reltoastrelid  | 112467
reltoastidxid  | 0
relhasindex    | f
relisshared    | f
relpersistence | p
relkind        | r
relnatts       | 3
relchecks      | 0
relhasoids     | f
relhaspkey     | f
relhasrules    | f
relhastriggers | f
relhassubclass | f
relfrozenxid   | 23527
relacl         |
reloptions     |

select * from pg_stats where tablename = 't';
-[ RECORD 1 ]----------+-------------------------------------------------
schemaname             | public
tablename              | t
attname                | id
inherited              | f
null_frac              | 0
avg_width              | 4
n_distinct             | -1
most_common_vals       |
most_common_freqs      |
histogram_bounds       | {1,100,200,300,400,500,600,700,800,900,1000,1100
correlation            | 1
most_common_elems      |
most_common_elem_freqs |
elem_count_histogram   |
-[ RECORD 2 ]----------+-------------------------------------------------
schemaname             | public
tablename              | t
attname                | col1
inherited              | f
null_frac              | 0
avg_width              | 4
n_distinct             | 10
most_common_vals       | {0,1,2,3,4,5,6,7,8,9}
most_common_freqs      | {0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1}
histogram_bounds       |
correlation            | 0.10045
most_common_elems      |
most_common_elem_freqs |
elem_count_histogram   |
-[ RECORD 3 ]----------+-------------------------------------------------
schemaname             | public
tablename              | t
attname                | col2
inherited              | f
null_frac              | 0
avg_width              | 35
n_distinct             | 1
most_common_vals       | {**********************************}
most_common_freqs      | {1}
histogram_bounds       |
correlation            | 1
most_common_elems      |
most_common_elem_freqs |
elem_count_histogram   |

Erwähnenswert ist an dieser Stelle vielleicht noch, dass das Erzeugen von Datensätzen mit Hilfe von generate_series nicht nur komfortabel, sondern auch sehr schnell ist - was im Fall von 10000 Datensätzen natürlich noch keine Rolle spielt - und dass der über \x aktivierte erweiterte Ausgabemodus für psql eine nette Sache ist, da er eine automatische Transformation der Ausgabe von Spalten zu Zeilen hervorruft.

Costing für Full Table Scan

Das Costing für den Full Table Scan, der im postgres-Kontext als sequenzieller Scan bezeichnet wird, wird in der Dokumentation explizit erläutert und beruht auf der Kombination der Kosten für das Lesen der Tabellen-Pages mit den Kosten für den Zugriff auf die einzelnen Datensätze, also:

(disk pages read * seq_page_cost) 
+ (rows scanned * cpu_tuple_cost)

-- im Beispiel also:
(94 * 1.0) + (10000 * 0.01) = 194.00

-- explain liefert dazu:
explain select * from t;

                       QUERY PLAN
--------------------------------------------------------
 Seq Scan on t  (cost=0.00..194.00 rows=10000 width=43)

Die Kosten unterteilen sich dabei in start-up cost (0.00 für den sequentiellen Scan) und total cost, wobei letztere exakt der Formel entsprechen. Auch die width ergibt sich exakt aus den Angaben zu den Spalten (4 + 4 + 35 = 43).

Zusätzliche Filter-Bedingungen erhöhen im Fall des sequentiellen Scans die Kosten, da sie eine zusätzliche Prüfung erforderlich machen, die erst nach der Ermittlung aller Datensätze erfolgen kann - im gegebenen Fall steigen die Kosten um 25 (= rows scanned * cpu_operator_cost):

dbadmin=# explain select * from t where id = 1;
                     QUERY PLAN
----------------------------------------------------
 Seq Scan on t  (cost=0.00..219.00 rows=1 width=43)
   Filter: (id = 1)

Costing für Index-Zugriffe

Im Fall von Index-Zugriffen ist die Kostenberechnung deutlich schwieriger. Zunächst sind ein paar Punkte erwähnenswert, in denen sich postgres anders verhält als Oracle:

• Ein Index-Zugriff, der entweder sehr selektiv ist, oder über einen Index erfolgt, dessen Sortierung sehr stark der physikalischen Sortierung der Tabelle entspricht (also eine starke correlation der fraglichen Spalte in pg_stats besitzt; in Oracle wäre das ein günstiger Clustering Factor), wird über einen "Index Scan" durchgeführt.
• Für Zugriffe, bei denen eine relativ große Abweichung der Sortierung von Index und Tabelle zu erwarten ist, steigt postgres auf einen "Bitmap Index Scan" mit folgendem "Bitmap Heap Scan" um. Das bedeutet: postgres liest die Index-Einträge, sortiert dann die enthaltenen row locations und greift dann mit der sortierten Ergebnisliste auf die Tabellen-Pages zu. Der Sinn der Übung ist die Vermeidung von Mehrfachzugriffen auf die Tabellen-Pages die sich ergeben würden, wenn die row locations ungeordnet besucht werden würden. Das wäre jetzt ein guter Moment für den Einsatz einer illustrierenden Grafik, aber die habe ich gerade nicht zur Hand. Das Vorgehen gibt es seit Version 11 auch in Oracle und tritt in 12c als TABLE ACCESS BY INDEX ROWID BATCHED in Zugriffsplänen auf.
• Postgres neigt zur Verknüpfung mehrerer Indizes über BitmapOr- und BitmapAnd-Verknüpfungen. Oracle kann das grundsätzlich auch (mit Hilfe einer BITMAP CONVERSION TO ROWID), neigt aber fast immer zur Verwendung des am besten geeigneten Index und zur anschließenden Filterung der zurückgelieferten Ergebnisse (für bitmap Indizes verwendet Oracle natürlich auch die entsprechenden Kombinationsverfahren, aber ich betrachte hier zunächst nur normale B*Tree-Indizes).

Das Costing für den "Index Scan" basiert, so weit ich sehen kann, auf folgender Formel:

(index pages read * random_page_cost * 2) 
+ (cpu_tuple_cost * rows scanned) 
+ (cpu_index_tuple_cost * scanned rows) 
+ (cpu_operator_cost * x)

-- im Beispiel für eine Query mit Einzelsatzzugriff:
(1 * 4 * 2) + (0.01 * 1) + (0.005 * 1) + (0.0025 * 100)
= 8 + 0.01 + 0.005 + 0.25

-- also:
create index t_idx0 on t(id);
create index t_idx1 on t(col1);

explain select * from t where id = 1;

                           QUERY PLAN
-----------------------------------------------------------------
 Index Scan using t_idx0 on t  (cost=0.00..8.27 rows=1 width=43)
   Index Cond: (id = 1)

So weit ist das ganz plausibel und vermutlich auch mehr oder minder zutreffend, aber die Frage ist: wie komme ich auf die 100 als Multiplikator für cpu_operator_cost? Die Antwort lautet: durch Einsetzen. Wenn ich für den Parameter cpu_operator_cost unterschiedliche Werte einsetze, dann liefert explain das passende Ergebnis zu meiner Formel. Für cpu_operator_cost = 0 ergibt sich ein Cost-Wert von 8.02. Allerdings bekomme ich für veränderte Einschränkungen auch einen veränderten Multiplikator:

set cpu_operator_cost = 0;

explain select * from t where id <= 100;

                            QUERY PLAN
-------------------------------------------------------------------
 Index Scan using t_idx0 on t  (cost=0.00..9.50 rows=100 width=43)
   Index Cond: (id <= 100)

--> (1 * 4 * 2) + (0.01 * 100) + (0.005 * 100) = 9.5

set cpu_operator_cost = 0.1;

explain select * from t where id <= 100;

                             QUERY PLAN
--------------------------------------------------------------------
 Index Scan using t_idx0 on t  (cost=0.00..29.50 rows=100 width=43)
   Index Cond: (id <= 100)

--> (1 * 4 * 2) + (0.01 * 100) + (0.005 * 100) + (0.1 * (100 + 100))

explain select * from t where id <= 200;

                             QUERY PLAN
--------------------------------------------------------------------
 Index Scan using t_idx0 on t  (cost=0.00..42.00 rows=200 width=43)
   Index Cond: (id <= 200)
--> (1 * 4 * 2) + (0.01 * 200) + (0.005 * 200) + (0.1 * (200 + 110))

Demnach scheint cpu_operator_cost immer mit (scanned rows + 100 + x) multipliziert zu werden, wobei das x vermutlich in einem bestimmten Verhältnis zu scanned rows steht. Vermutlich ändern sich die Details auch, wenn mehr als ein Index-Block gelesen werden muss, was bei 30 Index-Blocks und 10000 Datensätzen etwa nach 333 Sätzen erfolgen sollte (= 10000/30).

An dieser Stelle soll mir dieses Zwischenergebnis bis auf weiteres genügen. Klar ist, dass das Costing für postgres - wie im Fall von Oracle - relativ klaren und relativ einfachen Regeln unterliegt; wobei das "relativ einfach" vermutlich nur so lange gilt, wie man überschaubare Fälle untersucht. Mit der Kenntnis dieser Regeln sollte es dann auch möglich sein, die Schwächen des Modells in entsprechenden Fällen zu erkennen und auszugleichen - und muss sich nicht auf die eigene Kreativität im Umformulieren von SQL verlassen (wobei man dann so lange umbaut, bis sich etwas ergibt, was dem Optimizer gerade gefällt - was durchaus zu Ergebnissen führen kann, aber nicht unbedingt effektiv ist).

Zugriff über Index-Kombinationen

Jonathan Lewis hat in den letzten Tagen zwei Artikel veröffentlicht, die sich mit den Möglichkeiten der Kombination von Indizes beim Zugriff beschäftigen. Üblicherweise entscheidet sich der Optimizer bekanntlich für einen der existierenden Indizes, der ihm am besten geeignet erscheint, um einen selektiven Zugriff zu gewährleisten und verwendet weitere Bedingungen als Filter für die über den Index ermittelte Menge von Datensätzen:

• Conditional SQL – 4: beschäftigt sich mit einem besonderen Fall konditionaler Ausführungspläne, bei denen abhängig vom Vorliegen eines Bindewerts ein gefiltertes Ergebnis oder alle Datensätze geliefert werden sollen (eine Standardvariante dazu wäre z.B.: where t1.n1 = nvl(:n1,t1.n1); wenn ein Bindewert vorliegt, wird mit diesem verglichen, sonst erfolgt der - immer true liefernde - Vergleich der Spalte mit sich selbst). Im speziellen Fall wurden zwei über index concatenation verknüpfbare Bedingungen mit einer dritten Bedingung (LENGTH ( :b7) IS NULL) OR-verknüpft, was den Optimizer dann zum full table scan übergehen lässt. Dieses Verhalten ändert sich auch nicht, wenn man auf die dubiose LENGTH-Verwendung verzichtet. Insgesamt bleibt festzuhalten: "the optimizer’s ability to introduce concatenation is limited".
• Index Hash: zeigt, dass das costing für HASH JOINS, bei denen die Inhalte zweier Indizes einer Tabelle verknüpft werden (um auf den teureren Zugriff auf eine relativ breite Tabelle verzichten zu können), offenbar ein paar recht massive Inkonsistenzen - und Fehler - enthält: nicht immer wird der günstigste Plan verwendet und die Kosten der einzelnen Index-Zugriffe verändern sich deutlich, wenn sie im index join verwendet werden sollen (statt einzeln angesprochen zu werden). Plausibel sieht das Verhalten jedenfalls nicht aus.

NULL IS NOT NULL-Filter und Bindevariablen

Der folgende Test verdankt sich wieder einer Fragestellung im OTN-Forum, wobei ich die eigentliche Anfrage möglicherweise etwas frei interpretiert habe. Gegeben ist eine Query, in der in einer inline-View mehrere Subqueries über UNION ALL verknüpft sind, und in der äußeren Abfrage eine Einschränkung auf einen konstanten Wert erfolgt, der einige der Subqueries bedeutungslos macht, da er ihre Ergebnisse filtert. Aber wahrscheinlich erklärt ein Beispiel die Fragestellung sehr viel deutlicher:

drop table t1;
drop table t2;
drop table t3;
 
create table t1
as
select rownum col1
  from dual
connect by level <= 1000;
 
create table t2
as
select rownum col1
  from dual
connect by level <= 1000;
 
create table t3
as
select rownum col1
  from dual
connect by level <= 1000;

exec dbms_stats.gather_table_stats(user, 'T1')
exec dbms_stats.gather_table_stats(user, 'T2')
exec dbms_stats.gather_table_stats(user, 'T3') 

explain plan for
select coll, col1
  from (select 'AAA' coll, col1 from t1
          union all
        select 'BBB' coll, col1 from t2
          union all
        select 'CCC' coll, col1 from t3
       )
 where coll = 'AAA';

-----------------------------------------------------------------------------
| Id  | Operation            | Name | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------
|   0 | SELECT STATEMENT     |      |  1002 | 18036 |     4   (0)| 00:00:01 |
|   1 |  VIEW                |      |  1002 | 18036 |     4   (0)| 00:00:01 |
|   2 |   UNION-ALL          |      |       |       |            |          |
|   3 |    TABLE ACCESS FULL | T1   |  1000 |  4000 |     4   (0)| 00:00:01 |
|*  4 |    FILTER            |      |       |       |            |          |
|   5 |     TABLE ACCESS FULL| T2   |  1000 |  4000 |     4   (0)| 00:00:01 |
|*  6 |    FILTER            |      |       |       |            |          |
|   7 |     TABLE ACCESS FULL| T3   |  1000 |  4000 |     4   (0)| 00:00:01 |
-----------------------------------------------------------------------------

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

   4 - filter(NULL IS NOT NULL)
   6 - filter(NULL IS NOT NULL)

Der Plan zeigt deutlich, dass nur aus T1 Werte ausgelesen werden, während für T2 und T3 ein Filter-Prädikat "filter(NULL IS NOT NULL)" erscheint, das immer false liefern muss. Dazu passt (zumindest ungefähr) auch die Prognose der Größe der Ergebnismenge (rows = 1002). Aber was passiert, wenn statt des Literals ein Bindewert als Einschränkung verwendet wird?

var test varchar2(30);
exec :test := 'AAA';

explain plan for
select coll, col1
  from (select 'AAA' coll, col1 from t1
          union all
        select 'BBB' coll, col1 from t2
          union all
        select 'CCC' coll, col1 from t3
       )
 where coll = :test

-----------------------------------------------------------------------------
| Id  | Operation            | Name | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------
|   0 | SELECT STATEMENT     |      |  3000 | 54000 |    12   (0)| 00:00:01 |
|   1 |  VIEW                |      |  3000 | 54000 |    12   (0)| 00:00:01 |
|   2 |   UNION-ALL          |      |       |       |            |          |
|*  3 |    FILTER            |      |       |       |            |          |
|   4 |     TABLE ACCESS FULL| T1   |  1000 |  4000 |     4   (0)| 00:00:01 |
|*  5 |    FILTER            |      |       |       |            |          |
|   6 |     TABLE ACCESS FULL| T2   |  1000 |  4000 |     4   (0)| 00:00:01 |
|*  7 |    FILTER            |      |       |       |            |          |
|   8 |     TABLE ACCESS FULL| T3   |  1000 |  4000 |     4   (0)| 00:00:01 |
-----------------------------------------------------------------------------

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

   3 - filter('AAA'=:TEST)
   5 - filter('BBB'=:TEST)
   7 - filter('CCC'=:TEST)

Anstelle der "filter(NULL IS NOT NULL)" erscheinen hier ganz konventionelle Prädikate, die den Eindruck erwecken, als wäre hier eine frühzeitige Filterung ausgeschlossen - also ein Verzicht auf den Tabellenzugriff nicht möglich (was sich auch in der rows-Angabe 3000 widerspiegelt). Das ist insofern einleuchtend, als der Optimizer zum Zeitpunkt der Optimierung die Bindewerte nicht kennt und folglich auch keine Vorstellung von ihren Filtereigenschaften haben kann. Ein Blick auf die (hier nicht aufgeführten autotrace-) Statistiken der Ausführung macht aber deutlich, dass die Variante mit dem Bindewert die gleiche Anzahl an LIOs hervorruft wie die Variante mit Literal. Offenbar ist der Plan der Bindewert-Query ein wenig irreführend.

Dazu hat Randolf Geist im Thread die Erklärung geliefert:

the FILTER operation is always checked first if it can be fully evaluated without having to refer to the child operations of the FILTER - and in case of the expression :TEST = this is possible - so the underlying operations won't be started if the expression can be evaluated to FALSE. This could be confirmed by running the same test with rowsource statistics enabled (or via Real-Time SQL Monitoring) - the corresponding skipped child operations should be shown with STARTS = 0.

Auf die Idee der Verwendung von rowsource Statistiken hätte ich vielleicht auch kommen können - schließlich empfehle ich diese Technik im OTN-Forum regelmäßig selbst. In jedem Fall hat der Herr Geist recht, was die Vorhersage des Trace-Ergebnisses angeht:

---------------------------------------------------------------------------------------
| Id  | Operation            | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
---------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT     |      |      1 |        |   1000 |00:00:00.01 |      71 |
|   1 |  VIEW                |      |      1 |   3000 |   1000 |00:00:00.01 |      71 |
|   2 |   UNION-ALL          |      |      1 |        |   1000 |00:00:00.01 |      71 |
|*  3 |    FILTER            |      |      1 |        |   1000 |00:00:00.01 |      71 |
|   4 |     TABLE ACCESS FULL| T1   |      1 |   1000 |   1000 |00:00:00.01 |      71 |
|*  5 |    FILTER            |      |      1 |        |      0 |00:00:00.01 |       0 |
|   6 |     TABLE ACCESS FULL| T2   |      0 |   1000 |      0 |00:00:00.01 |       0 |
|*  7 |    FILTER            |      |      1 |        |      0 |00:00:00.01 |       0 |
|   8 |     TABLE ACCESS FULL| T3   |      0 |   1000 |      0 |00:00:00.01 |       0 |
---------------------------------------------------------------------------------------

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

   3 - filter('AAA'=:TEST)
   5 - filter('BBB'=:TEST)
   7 - filter('CCC'=:TEST)

Die Filter-Prädikate werden also zur Laufzeit tatsächlich vor dem Zugriff auf das zugehörige Segment ausgewertet und verhindern den Zugriff - was eine effektive Strategie darstellt. Das einzige kleine Problem dabei ist, dass man den Prädikaten dieses Verhalten nicht ansieht.

Bytes Angaben für View-Operatoren im Ausführungsplan

Manchmal stellt mich die Aufgabe der Wahl eines passenden Titels für einen Blog-Eintrag vor unlösbare Schwierigkeiten...

Vor knapp einem Monat hat Randolf Geist einen Artikel mit dem deutlich griffigeren Titel View Data Volume Estimates veröffentlicht, den ich an dieser Stelle kurz zusammenfasse, um die Chance zu erhöhen, mich bei Bedarf an das angesprochenen Verhalten zu erinnern. Worum es geht, ist Folgendes: normalerweise verwendet der Optimizer die column statistics zur Berechnung der bytes-Angabe im execution plan. Im Fall des Auftretens eines View-Operators im Plan für eine unmerged view ist dieses Vorgehen aber nicht möglich und der Optimizer muss stattdessen auf default-Werte ausweichen, die aus den Spaltendefinitionen abgeleitet werden - in der Regel scheint dabei ein Füllgrad von 50% angenommen zu werden (also z.B. 50 Byte für eine Spalte vom Typ VARCHAR2(100)). Im Fall der Verwendung von multi-byte-Zeichensätzen werden die Schätzung daher noch weiter erhöht.

Gefährlich können falsche Schätzungen des Datenvolumens bei allen Operationen sein, die sich auf diese Angabe beziehen, vor allem aber bei HASH JOINs, bei denen die Bestimmung von input und probe set davon abhängt. Im Artikel folgen einige Beispiele, die das Verhalten vorführen. Interessant ist dabei auch der Hinweis, dass in diesem Fall dynamic sampling keine Verbesserung bringt, da dabei ähnliche Kalkulationen ins Spiel kommen wie im Fall der Verwendung von Statistiken. Der Herr Geist schließt mit dem Hinweis, dass das Verhalten auch in 12c unverändert ist.

Systemstatistiken im Exadata Modus

Seit Release 11.2.0.4 gibt es die Systemstatistiken in einer neuen Geschmacksrichtung: dem "exadata mode". Das hört sich vielleicht dramatischer an als es ist, da die Ermittlung von "exadata mode" system statistics exakt der Ermittlung von noworkload system statistics entspricht - abgesehen davon, dass der MBRC auf den Wert des Parameters db_file_multiblock_read_count gesetzt wird. Daher ergeben sich nur dann Unterschiede zwischen dem "exadata mode" und den herkömmlichen noworkload system statistics, wenn der Initialisierungsparameter db_file_multiblock_read_count nicht explizit gesetzt wurde, denn in diesem Fall verwendet Oracle den Standardwert 8 (im dictionary als hidden parameter _db_file_optimizer_read_count hinterlegt). Diese Zusammenfassung basiert auf der Grundlage von:

• System Statistics – “Exadata” Mode von Kerry Osborne mit einer kurzen Vorstellung des neuen Modus.
• System Statistics Gathered in Exadata Mode – When Are They Relevant? von Christian Antognini, der nicht nur den Unterschied zwischen "exadata mode" und noworkload system statistics erläutert, sondern eine umfassende, aber trotzdem handliche Darstellung des Costings für Full Table Scans liefert.

Christian Antogninis Artikel ist ein hervorragender Einstieg zum Thema CBO-Kalkulationen - und wahrscheinlich werde ich darauf noch häufiger verweisen (so wie auf seine Anleitung zum Lesen von Ausführungsplänen).

Cardinality ohne Spaltenstatistiken

Ein Exkurs im Rahmen einer Anfrage im OTN Forum hat mir mal wieder gezeigt, wie viele Lücken mein Wissen über die Kalkulationsregeln des CBO hat. Die eigentliche Ausgangsfragestellung lasse ich dabei ausgeklammert, aber im Rahmen der Analyse wurde der Vorschlag gemacht, die column statistics einer Index-Spalte zu löschen. Die Frage ist jetzt, wie der CBO die Cardinality des Zugriffs bestimmt. Dazu das Beispiel, das ich auch im OTN-Thread beigesteuert habe, und in dem ich die cardinalities für IN-list-Zugriffe mit einem, zwei und zwanzig Elementen jeweils mit und ohne column statistics untersuche:

-- 11.1.0.7
drop table t;

create table t
as
select 'testtesttesttesttest' || rownum id
     , mod(rownum, 5) col2
     , lpad('*', 50, '*') padding
  from dual
connect by level <= 100000;

alter table t add constraint t_pk primary key (id, col2);

exec dbms_stats.gather_table_stats(user, 'T')

-- with column statistics
explain plan for
select *
  from t
where id in ('testtesttesttesttest1'
              );

select * from table(dbms_xplan.display);

------------------------------------------------------------------------------------
| Id  | Operation                   | Name | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |      |     1 |    80 |     4   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| T    |     1 |    80 |     4   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN          | T_PK |     1 |       |     3   (0)| 00:00:01 |
------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("ID"='testtesttesttesttest1')

explain plan for
select *
  from t
where id in ('testtesttesttesttest1'
            , 'testtesttesttesttest2'
              );

select * from table(dbms_xplan.display);

-------------------------------------------------------------------------------------
| Id  | Operation                    | Name | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |      |     2 |   160 |     5   (0)| 00:00:01 |
|   1 |  INLIST ITERATOR             |      |       |       |            |          |
|   2 |   TABLE ACCESS BY INDEX ROWID| T    |     2 |   160 |     5   (0)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN          | T_PK |     2 |       |     4   (0)| 00:00:01 |
-------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access("ID"='testtesttesttesttest1' OR "ID"='testtesttesttesttest2')


explain plan for
select *
  from t
where id in ('testtesttesttesttest1'
            , 'testtesttesttesttest2'
            , 'testtesttesttesttest3'
            , 'testtesttesttesttest4'
            , 'testtesttesttesttest5'
            , 'testtesttesttesttest6'
            , 'testtesttesttesttest7'
            , 'testtesttesttesttest8'
            , 'testtesttesttesttest9'
            , 'testtesttesttesttest10'
            , 'testtesttesttesttest11'
            , 'testtesttesttesttest12'
            , 'testtesttesttesttest13'
            , 'testtesttesttesttest14'
            , 'testtesttesttesttest15'
            , 'testtesttesttesttest16'
            , 'testtesttesttesttest17'
            , 'testtesttesttesttest18'
            , 'testtesttesttesttest19'
            , 'testtesttesttesttest20'
              );

select * from table(dbms_xplan.display);

-------------------------------------------------------------------------------------
| Id  | Operation                    | Name | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |      |    20 |  1600 |    26   (0)| 00:00:01 |
|   1 |  INLIST ITERATOR             |      |       |       |            |          |
|   2 |   TABLE ACCESS BY INDEX ROWID| T    |    20 |  1600 |    26   (0)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN          | T_PK |    20 |       |    21   (0)| 00:00:01 |
-------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access("ID"='testtesttesttesttest1' OR "ID"='testtesttesttesttest10'
              OR "ID"='testtesttesttesttest11' OR "ID"='testtesttesttesttest12' OR
              "ID"='testtesttesttesttest13' OR "ID"='testtesttesttesttest14' OR
              "ID"='testtesttesttesttest15' OR "ID"='testtesttesttesttest16' OR
              "ID"='testtesttesttesttest17' OR "ID"='testtesttesttesttest18' OR
              "ID"='testtesttesttesttest19' OR "ID"='testtesttesttesttest2' OR
              "ID"='testtesttesttesttest20' OR "ID"='testtesttesttesttest3' OR
              "ID"='testtesttesttesttest4' OR "ID"='testtesttesttesttest5' OR
              "ID"='testtesttesttesttest6' OR "ID"='testtesttesttesttest7' OR
              "ID"='testtesttesttesttest8' OR "ID"='testtesttesttesttest9')

-- without column statistics
exec dbms_stats.delete_column_stats(user, 'T', 'ID')

explain plan for
select *
  from t
where id in ('testtesttesttesttest1'
              );

select * from table(dbms_xplan.display);

------------------------------------------------------------------------------------
| Id  | Operation                   | Name | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |      |  1000 | 80000 |    86   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| T    |  1000 | 80000 |    86   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN          | T_PK |   400 |       |     5   (0)| 00:00:01 |
------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   2 - access("ID"='testtesttesttesttest1')

explain plan for
select *
  from t
where id in ('testtesttesttesttest1'
            , 'testtesttesttesttest2'
              );

select * from table(dbms_xplan.display);

-------------------------------------------------------------------------------------
| Id  | Operation                    | Name | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |      |  1000 | 80000 |    87   (0)| 00:00:01 |
|   1 |  INLIST ITERATOR             |      |       |       |            |          |
|   2 |   TABLE ACCESS BY INDEX ROWID| T    |  1000 | 80000 |    87   (0)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN          | T_PK |   400 |       |     6   (0)| 00:00:01 |
-------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access("ID"='testtesttesttesttest1' OR "ID"='testtesttesttesttest2')

explain plan for
select *
  from t
where id in ('testtesttesttesttest1'
            , 'testtesttesttesttest2'
            , 'testtesttesttesttest3'
            , 'testtesttesttesttest4'
            , 'testtesttesttesttest5'
            , 'testtesttesttesttest6'
            , 'testtesttesttesttest7'
            , 'testtesttesttesttest8'
            , 'testtesttesttesttest9'
            , 'testtesttesttesttest10'
            , 'testtesttesttesttest11'
            , 'testtesttesttesttest12'
            , 'testtesttesttesttest13'
            , 'testtesttesttesttest14'
            , 'testtesttesttesttest15'
            , 'testtesttesttesttest16'
            , 'testtesttesttesttest17'
            , 'testtesttesttesttest18'
            , 'testtesttesttesttest19'
            , 'testtesttesttesttest20'
              );

select * from table(dbms_xplan.display);

-------------------------------------------------------------------------------------
| Id  | Operation                    | Name | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |      |  1000 | 80000 |   102   (0)| 00:00:01 |
|   1 |  INLIST ITERATOR             |      |       |       |            |          |
|   2 |   TABLE ACCESS BY INDEX ROWID| T    |  1000 | 80000 |   102   (0)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN          | T_PK |   400 |       |    21   (0)| 00:00:01 |
-------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access("ID"='testtesttesttesttest1' OR "ID"='testtesttesttesttest10'
              OR "ID"='testtesttesttesttest11' OR "ID"='testtesttesttesttest12' OR
              "ID"='testtesttesttesttest13' OR "ID"='testtesttesttesttest14' OR
              "ID"='testtesttesttesttest15' OR "ID"='testtesttesttesttest16' OR
              "ID"='testtesttesttesttest17' OR "ID"='testtesttesttesttest18' OR
              "ID"='testtesttesttesttest19' OR "ID"='testtesttesttesttest2' OR
              "ID"='testtesttesttesttest20' OR "ID"='testtesttesttesttest3' OR
              "ID"='testtesttesttesttest4' OR "ID"='testtesttesttesttest5' OR
              "ID"='testtesttesttesttest6' OR "ID"='testtesttesttesttest7' OR
              "ID"='testtesttesttesttest8' OR "ID"='testtesttesttesttest9')

Meine vorläufige Interpretation dazu lautet:

• mit (akkuraten) column statistics kann der CBO die cardinalities in allen Fällen (1, 2, 20) exakt bestimmen.
• nach der Löschung der Statistiken der in der condition verwendeten Spalte wird in allen Fällen eine cardinality von 400 angenommen (wobei die cost Angaben sich sukzessive erhöhen, wenn sich die Länge der IN-list vergrößert).
• die 400 bleiben übrigens auch erhalten, wenn man auch die Statistiken der zweiten PK-Spalte löscht und sogar, wenn man die zweite Spalte nicht in den PK aufnimmt (die zugehörigen Tests habe ich hier unterschlagen, da sie mit geringfügigem Aufwand aus dem bestehenden Test erzeugt werden können). In diesem Fall wird allerdings aus dem range scan ein unique scan und die cardinality ist für die Variante mit einem Element korrekt mit 1 bestimmt - offenbar erkennt der CBO in diesem Fall, dass ein unique scan auf einen Wert auch nur (höchstens) einen Satz liefern kann.
• Anscheinend ist dieser Faktor 400/100000 = 0,004 ein fixierter Wert für diesen Fall.
• wenn man den Index komplett entfernt, kommt der CBO im Test stabil auf eine cardinality von 1000 also 0,001.

Ich vermute, dass diese Annahmen des CBO irgendwo dokumentiert und bekannt sind, aber den einzigen Hinweis, den ich auf Anhieb finden konnte, liefert Richard Foote, der einen 0,4% bzw. 1% guess des CBO erwähnt, aber nicht näher erläutert. Möglicherweise trage ich hier die Details noch nach, sollte ich sie irgendwo finden.

Adaptive Plans in 12c

Gestern habe ich im OTN Forum ein paar Fragen zum grundsätzlichen Verhalten der in 12c eingeführten Adaptive Plans gestellt, aber inzwischen denke ich, dass die Überlegungen hier besser aufgehoben wären. Falls der OTN Thread noch interessante Ergänzungen liefern sollte, werde ich sie auch hier hinzufügen. Aber nun zum Thema. Maria Colgan ("The Optimizer Lady" - wenn ich mich richtig erinnere, verdankt sie den Titel Doug Burns) nennt die Adaptive Plans in ihrem White Paper Optimizer with Oracle Database 12c "by far the biggest change to the optimizer in Oracle Database 12c". Zur Arbeitsweise des Features erklärt sie weiterhin:

Adaptive plans enable the optimizer to defer the final plan decision for a statement, until execution time. The optimizer instruments its chosen plan (the default plan), with statistics collectors so that at runtime, it can detect if its cardinality estimates, differ greatly from the actual number of rows seen by the operations in the plan. If there is a significant difference, then the plan or a portion of it can be automatically adapted to avoid suboptimal performance on the first execution of a SQL statement.

Der CBO entwickelt also nicht wie bisher einen vorab vollständig festgelegten Plan, den er dann zum Zeitpunkt der Ausführung durchführt, sondern er erzeugt einen Gesamtplan mit alternativen Sub-Plänen und behält sich vor, die Wahl des Sub-Plans erst zu treffen, wenn er die tatsächlichen Kardinalität der zugehörigen Input-Menge kennt. Wenn man bedenkt, wie viele suboptimale Pläne sich aus fehlerhaften Entscheidungen zwischen Nested Loops und Hash Joins ergeben, weil die Schätzung des CBO deutlich von den tatsächlichen Größen der Mengen abweichen, dann erscheint diese Strategie ausgesprochen plausibel. In meiner OTN-Frage hatte ich Frau Colgans Erläuterung zitiert, aber offenbar nicht bis zu Ende gelesen, denn der letzte Teil war mir offenbar entgangen: "on the first execution of a SQL statement". Die endgültige Entscheidung für einen Plan wird bei der ersten Ausführung der Query getroffen, wenn der statistics collector seine Zahlen liefert. Dazu ein Beispiel mit 12c auf meinem heimischen Windows 7-Rechner:

-- creation of test tables with indexes and statistics
drop table t1;
drop table t2;

create table t1
as
select rownum id
     , mod(rownum, 10) col1
     , lpad('*', 20, '*') col2
  from dual
connect by level <= 100000;

exec dbms_stats.gather_table_stats(user, 't1')

create index t1_id_idx on t1(col1, id);

create table t2
as
select mod(rownum, 100) id_t1
     , lpad('*', 20, '*') col2
     , rownum col3
  from dual
connect by level <= 100000;

exec dbms_stats.gather_table_stats(user, 't2')

create index t2_idx on t2(id_t1);

-- a significant change of the data distribution
-- without regathering of statistics
update t1 set col1 = 1000 where id > 1;
--> Update for 99999 rows
commit;

Für meine folgende Test-Query hätte die initiale Datenverteilung einen HASH JOIN nahe gelegt, aber durch das Update sollte ein NESTED LOOPS JOIN die bessere Wahl sein. Dazu zunächst die Einschätzung von Explain Plan:

explain plan for
select sum(t1.col1) sum_col3
  from t1
     , t2
 where t1.id = t2.id_t1
   and t1.col1 = 1;

select * from table(dbms_xplan.display);

PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------
Plan hash value: 1632433607

------------------------------------------------------------------------------------
| Id  | Operation              | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT       |           |     1 |    11 |    84   (2)| 00:00:01 |
|   1 |  SORT AGGREGATE        |           |     1 |    11 |            |          |
|*  2 |   HASH JOIN            |           |   100K|  1074K|    84   (2)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN    | T1_ID_IDX | 10000 | 80000 |    28   (0)| 00:00:01 |
|   4 |    INDEX FAST FULL SCAN| T2_IDX    |   100K|   292K|    55   (0)| 00:00:01 |
------------------------------------------------------------------------------------

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

   2 - access("T1"."ID"="T2"."ID_T1")
   3 - access("T1"."COL1"=1)

Note
-----
   - this is an adaptive plan

-- plan with adaptive parts
select * from table(dbms_xplan.display(format=>'+adaptive'));

PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------
Plan hash value: 1632433607

----------------------------------------------------------------------------------------
|   Id  | Operation                | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------------
|     0 | SELECT STATEMENT         |           |     1 |    11 |    84   (2)| 00:00:01 |
|     1 |  SORT AGGREGATE          |           |     1 |    11 |            |          |
|  *  2 |   HASH JOIN              |           |   100K|  1074K|    84   (2)| 00:00:01 |
|-    3 |    NESTED LOOPS          |           |   100K|  1074K|    84   (2)| 00:00:01 |
|-    4 |     STATISTICS COLLECTOR |           |       |       |            |          |
|  *  5 |      INDEX RANGE SCAN    | T1_ID_IDX | 10000 | 80000 |    28   (0)| 00:00:01 |
|- *  6 |     INDEX RANGE SCAN     | T2_IDX    |    10 |    30 |    55   (0)| 00:00:01 |
|     7 |    INDEX FAST FULL SCAN  | T2_IDX    |   100K|   292K|    55   (0)| 00:00:01 |
----------------------------------------------------------------------------------------

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

   2 - access("T1"."ID"="T2"."ID_T1")
   5 - access("T1"."COL1"=1)
   6 - access("T1"."ID"="T2"."ID_T1")

Note
-----
   - this is an adaptive plan (rows marked '-' are inactive)

Der Plan ist explizit als "adaptive plan" gekennzeichnet und enthält den HASH JOIN, mit dem bei der von den Statistiken beschriebenen Datenverteilung zu rechnen ist. Dass diese Datenverteilung nach dem Update nicht mehr vorliegt, kann der Optimizer zu diesem Zeitpunkt nicht wissen, weil er im Rahmen von Explain Plan keinen Blick auf die Daten wirft. Die mit dem Format '+adaptive' erzeugte Version des Plans zeigt die Subplan-Varianten: in diesem Fall die Möglichkeit, den Hash Join durch einen NL Join zu ersetzen, wobei die inaktiven Teilen durch das führende '-' gekennzeichnet sind. Besonders lesbar ist dieser gemischte Plan nicht, aber die parallele Darstellung solcher Varianten ist auch keine dankbare Aufgabe, wie diverse Diff-Tools bestätigen können.

Nun zur tatsächlichen Ausführung der Query:

select sum(t1.col1) sum_col3
  from t1
     , t2
 where t1.id = t2.id_t1
   and t1.col1 = 1;

  SUM_COL3
----------
      1000

select * from table( dbms_xplan.display_cursor('0g3mdd8b1pstt', 0));

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
SQL_ID  0g3mdd8b1pstt, child number 0
-------------------------------------
select sum(t1.col1) sum_col3   from t1      , t2  where t1.id =
t2.id_t1    and t1.col1 = 1

Plan hash value: 1261696607

--------------------------------------------------------------------------------
| Id  | Operation          | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           |       |       |    84 (100)|          |
|   1 |  SORT AGGREGATE    |           |     1 |    11 |            |          |
|   2 |   NESTED LOOPS     |           |   100K|  1074K|    84   (2)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN| T1_ID_IDX | 10000 | 80000 |    28   (0)| 00:00:01 |
|*  4 |    INDEX RANGE SCAN| T2_IDX    |    10 |    30 |    55   (0)| 00:00:01 |
--------------------------------------------------------------------------------

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

   3 - access("T1"."COL1"=1)
   4 - access("T1"."ID"="T2"."ID_T1")

Note
-----
   - this is an adaptive plan

Die tatsächliche Ausführung verwendet also den NL Join, wobei der Plan weiterhin die Cardinalities anzeigt, die aus den Tabellen- und Spalten-Statistiken des Dictionary ermittelt wurden. Dabei sind die Cost-Angaben die des HASH JOIN Planes: wenn man den ausgeführten Plan mit einem USE_NL Hint erzwingt, ergeben sich sehr viel höhere Cost-Werte, was wiederum keine Überraschung, sondern ganz folgerichtig ist.

explain plan for
select /*+ use_nl(t1 t2) */
       sum(t1.col1) sum_col3
  from t1
     , t2
 where t1.id = t2.id_t1
   and t1.col1 = 1;

PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 1261696607

--------------------------------------------------------------------------------
| Id  | Operation          | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           |     1 |    11 | 10081   (1)| 00:00:01 |
|   1 |  SORT AGGREGATE    |           |     1 |    11 |            |          |
|   2 |   NESTED LOOPS     |           |   100K|  1074K| 10081   (1)| 00:00:01 |
|*  3 |    INDEX RANGE SCAN| T1_ID_IDX | 10000 | 80000 |    28   (0)| 00:00:01 |
|*  4 |    INDEX RANGE SCAN| T2_IDX    |    10 |    30 |     1   (0)| 00:00:01 |
--------------------------------------------------------------------------------

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

   3 - access("T1"."COL1"=1)
   4 - access("T1"."ID"="T2"."ID_T1")

Letztlich steht alles, was ich hier ausführe, auch schon in Maria Colgans White Paper, und es zeigt sich wieder einmal, dass es Texte gibt, die eine gründliche Lektüre verdienen statt eines kursorischen Überfliegens. Hier noch einmal eine Zusammenfassung der Schritte:

• im Rahmen der Optimization entwickelt der CBO einen Plan mit adaptiven Komponenten, über deren Verwendung er erst zum Zeitpunkt der ersten Ausführung eine Entscheidung treffen will.
• während der ersten Ausführung prüft der statistics collector die tatsächliche Größe der Input-Mengen und trifft dann die endgültige Entscheidung für eine der im ursprünglichen Plan vorgesehenen potentiellen Varianten. Nachdem die Entscheidung getroffen ist, wird das Attribut IS_RESOLVED_ADAPTIVE_PLAN in v$sql auf 'Y' gesetzt (so dass ein Wert 'N' nur während der ersten Ausführung auftreten kann, wie man im White Paper erfährt)

Nützlich sind Adaptive Plans somit in Fällen, in denen die initialen Cardinality Schätzungen des CBO (aus welchen Gründen auch immer) nicht viel taugen. Für Fälle, in denen sich die Daten darüber hinaus rasch ändern, ist weiterhin dynamic sampling relevant (das in 12c das neue Label "dynamic statistics" bekommen hat).

Nachtrag 26.08.2013: ziemlich zeitgleich mit meiner Untersuchung hat Frau Colgan noch einen Artikel What's new in 12c: Adaptive joins veröffentlicht, der offenbar den Auftakt zu einer Serie zum Thema darstellt - und weitere wichtige Punkte anspricht (etwa den - im CBO Trace sichtbaren - 'inflection point', der definiert, wann eine Änderung der Join-Strategie aufgrund der Größe der ersten Input-Menge sinnvoll wird; Iordan Iotzow hat allerdings schon vor einigen Wochen darauf hingewiesen, dass die Statistiken hier immer noch relevant sind, nämlich bei der Größenbestimmung der zweiten Menge).

Nachtrag 25.04.2014: noch ein Artikel von Iordan Iotzow zum Thema: diesmal stellt er die Frage, wann adaptive Pläne verwendet werden und kommt zum Ergebnis:

• wenn eine Menge (laut Statistiken) erheblich kleiner ist als die andere und passende Indizes vorliegen, wählt der Optimizer einen NL Join und spart sich den Aufwand, einen adaptive plan zu erzeugen.
• wenn beide Mengen eine ähnliche Größe haben (für geeignete Werte von ähnlich), dann wählt der Optimizer den HJ.
• wenn die eine Menge "slightly smaller" als die andere, dann wird ein adaptive plan erzeugt - wobei "slightly smaller" in der illustrierenden Grafik deutlich kleiner ist.

Die Aussage ist also recht allgemein, dafür aber vermutlich zutreffend.

Nachtrag 29.07.2014: mit Release 12.1.0.2 ist auch der SQL Monitor dazu in der Lage, adaptive plans korrekt anzuzeigen, wie man bei Franck Pachot nachlesen kann.

Nachtrag 30.07.2014: noch mal Iordan Iotzow mit Überlegungen zum Inflection-Point. Im Titel erscheint ein geklammertes "part 1", so dass von Fortsetzungen auszugehen ist.

CBO: Cost für NVL-Prädikate

Jonathan Lewis zeigt, dass der Oracle Optimizer offenbar eine erstaunlich klare Vorstellung von der Wirkung von Prädikaten mit der NVL-Funktion besitzt und dabei die NULL-Werte der Spalte in seiner Kalkulation akkurat einbezieht (und das bereits seit Version 8i). Leider ist diese Einsicht des CBO offenbar auf NVL beschränkt und betrifft nicht COALESCE oder CASE, die stattdessen mit der Standard-Selektivität von 0.01 (also 1%) für Funktionen operieren. Besonders traurig ist das, weil diese beiden NVL-Alternativen im Gegensatz zu NVL eine short-circuit Optimierung verwenden, die dafür sorgt, dass überflüssige Auswertungen vermieden werden können. Schade: ich dachte, das wäre mal ein Fall, bei dem man eine eindeutige Antwort auf die Frage nach der am besten geeigneten Verfahrensweise geben könnte ...

CBO: Cardinality-Berechnung für Werte außerhalb des bekannten Wertebereichs

Jonathan Lewis gibt eine kurze Zusammenfassung des in Cost Based Oracle umfassender erläuterten Verfahrens zur Berechnung der Cardinality von Werten die außerhalb des durch LOW_VALUE und HIGH_VALUE (in DBA_TAB_COLS und entsprechenden Views) definierten Bereichs bekannter Werte liegen. Für Gleichheitsprüfungen gilt dabei folgende Formel:

base cardinality * (total range – distance outside ) / (total range)

Die Wahrscheinlichkeit nimmt dabei jenseits der bekannten Werte sukzessive ab und die Cardinality fällt spätestens auf 1, wenn die "distance outside" die "total range" erreicht. Für Range-Pädikate wird eine andere Berechnung verwendet - in diesem Fall gilt:

For the out-of-range range-based predicate, the cardinality is simply the base cardinality of an in-range “column = unknown constant”

Die Größe des Bereichs hat folglich keinen Einfluss auf die Cardinality. Für Ranges, die teilweise außerhalb des bekannten Wertebereichs liegen, wird dabei offenbar nur die Cardinality des bekannten Teilbereichs berücksichtigt:

-- basierend auf dem Beispiel von Jonathan Lewis
-- 12.1.0.1
select * from t1 where n1 between 90 and 200;

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   178 |  1958 |     4   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |   178 |  1958 |     4   (0)| 00:00:01 |
--------------------------------------------------------------------------

select * from t1 where n1 between 90 and 100;

--------------------------------------------------------------------------
| Id  | Operation         | Name | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |   178 |  1958 |     4   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS FULL| T1   |   178 |  1958 |     4   (0)| 00:00:01 |
--------------------------------------------------------------------------

Diese Berechnungsregeln sind in Oracle 12 offenbar unverändert.

Berechnungskorrektur für den CLUSTERING_FACTOR

Richard Foote weist in seinem Blog auf eine wichtige Errungenschaft von Release 12c hin, die es als Patch hinab in die Versionen 11.1.0.7, 11.2.0.2 und 11.2.0.3 geschafft hat: die lange erwartete Korrektur des CLUSTERING_FACTOR (CF) durch einen ergänzenden zweiten Parameter für die Funktion sys_op_countchg. Zur Erinnerung: der CF ist ein Maß für die Sortierung einer Tabelle hinsichtlich des zugehörigen Index: ist die Sortierung von Tabelle und Index identisch, dann ergibt sich ein günstiger CF, der der Anzahl der Tabellenblocks entspricht. Weicht die Sortierung deutlich voneinander ab, so dass ein Index Range Scan von einem Index Block aus in sehr viele Tabellenblocks springen muss, dann ergibt sich ein ungünstiger CF, der im Extremfall der Anzahl der Zeilen in der Tabelle entspricht. Neben der Anzahl der Leaf-Blocks ist der CF die entscheidende Komponente in der Kostenberechung für Index-Zugriffe (sofern sie einen Tabellenzugriff hervorrufen und nicht auf die Indexstruktur beschränkt bleiben).

Das größte Problem des CF war in der Vergangenheit, dass er keine Historie zuletzt betrachteter Blocks berücksichtigte: der Wechsel zwischen wenigen Tabellenblocks, auf die abwechselnd zugegriffen wurde, führte demnach zu einem sehr hohen CF, obwohl die Blocks in einem solchen Fall vermutlich im Cache gehalten wurden und einen sehr effizienten Zugriff gestatteten. Ein Fall, der sich ungünstig auf die CF-Berechnung auswirkt, ist ASSM, da dabei ja explizit mehrere Blocks parallel für eingehende Inserts verwendet werden. Mit Patch 15830250 (der die zutreffende Beschreibung "Index Clustering Factor Computation Is Pessimistic" trägt) wurde der Funktion sys_op_countchg, die für die CF-Berechnung verantwortlich ist, ein zweiter Parameter spendiert, der die Anzahl der zuletzt besuchten Blocks angibt, die bei der CF-Berechnung berücksichtigt werden sollen. Im Artikel des Herrn Foote gibt's neben einer etwas ausführlicheren Erläuterung auch noch ein schönes Testbeispiel. Der Vollständigkeit halber hier noch der Verweis auf Jonathan Lewis' Kommentar zum Thema und Martin Deckers Artikel, der die Auswirkung des Patches als erster angesprochen hatte.

Nachtrag 19.05.2013: in einem zweiten Artikel Clustering Factor Calculation Improvement Part II (Blocks On Blocks) zeigt Richard Foote, dass die TABLE_CACHED_BLOCKS Angabe in der Regel keine massiv ungünstigen Wirkungen auf die CF-Berechnung hat und gibt eine übersichtliche mathematische Erklärung dafür.

Optimizer Index Caching und IOTs

Timur Akhmadeev zeigt in seinem Blog, dass das Costing für secondary indexes bei Verwendung des (spätestens seit der Ankunft von system statistics ohnehin fragwürdigen) Parameters optimizer_index_caching (bzw. eines entsprechenden Hints) zu absurd niedrigen Ergebnissen führt: anscheinend wird der Zugriff auf den PK der IOT in solchen Fällen als kostenlos betrachtet. Schuld ist möglicherweise ein Bug-Fix, der in 10.2.0.4 eingeführt wurde, aber dem Herrn Akhmadeev fehlt (genau wie mir) ein ausreichend altes Release, um diese Annahme zu überprüfen.