Join Cardinality und Sanity Checks

In seinem heutigen Blog-Artikel Upgrades - bisweilen denke ich, der Autor könnte sich wiedererkennbarere Titel ausdenken - schreibt Jonathan Lewis über die Veränderungen der Join-Cardinality für unterschiedliche Oracle-Realases seit Version 9.2. In seinem Beispiel verbindet er zwei identische Tabellen, die jeweils 1.000.000 Datensätze enthalten, über unterschiedlich häufig auftretende Spaltenwerte und zeigt dabei, dass es mindestens drei unterschiedliche Ergebnisse für die Cardinality-Schätzungen gibt. Ich wiederhole hier nicht den Versuchsaufbau des Artikels, sondern ergänze nur meine Erklärungen/Interpretationen, denn die fehlen beim Herrn Lewis derzeit noch - obwohl er versprochen hat, sie in den nächsten Wochen nachzuliefern:

• in 9.2.0.8 ist anscheinend die alte Standardformel für die Berechnung der Join-Cardinality am Werk, also:
  

     -- für einen Join der Tabellen t1 und t2 über die Spalte c1 bzw. c2 gilt:
     Join Selectivity
        = ((num_rows(t1) - num_nulls(t1.c1))/num_rows(t1)) *
          ((num_rows(t2) - num_nulls(t2.c2))/num_rows(t2)) /
          greater (num_distinct(t1.c1),  num_distinct(t2.c2))

     Join Cardinality
         = Join Selectivity * filtered cardinality (t1) * filtered cardinality (t2)
     
     -- im Beispiel bei Jonathan Lewis:
     1/90 * 1/750 * 2500 * 2500 = 92,59
     -- das ist nicht der Wert 96, der im Plan des Scratchpad-Beispiels erscheint,
     -- aber eine ordentliche Annäherung

• in 10.2.0.4 wird die Formel offenbar insofern korrigiert, dass die beiden Selektivitäten der Join-Spalten von einer Seite des Joins genommen werden, um ein konsistentes Ergebnis zu erhalten. Für das Beispiel des Artikels ergibt sich:

     1/72 * 1/750 * 2500 * 2500 = 115,74
     -- das ist exakt das Ergebnis im Ausführungsplan des Artikels
     -- und relativ nah am Ergebnis aus 9.2.0.8

• in 11.2.0.4 und späteren Releases ergibt sich dann ein ganz anderes Resultat, nämlich 2554. Ein (in 12.1.0.2) über dbms_sqldiag.dump_trace (p_component => 'Compiler') erzeugtes CBO-Trace enthält folgende Angaben:

     ColGroup cardinality sanity check: ndv for  T1[T1] = 54000.000000  T2[T2] = 54000.000000
     Join selectivity using 1 ColGroups: 4.0866e-04 (sel1 = 0.000000, sel2 = 0.000000)
     Join Card:  2554.147936 = outer (2500.000000) * inner (2500.000000) * sel (4.0866e-04)
     Join Card - Rounded: 2554 Computed: 2554.147936

Vor einigen Jahren hat Randolf Geist zwei Artikel zum Thema "Multi-Column Joins" geschrieben und dabei erklärt:

It can be seen from a 10053 optimizer trace file that Oracle uses a "Multi-column cardinality sanity check" by default in cases where the calculated multi-column selectivity falls below a certain limit, obviously using the smaller selectivity available from the different 1/num_rows of the tables/row sources involved in the join, arriving at an estimate 30,000 rows in this particular case.

In den einfacheren Beispielen bei Randolf Geist entspricht die korrigierte Join-Cardinality dabei, so weit ich sehe, immer der Cardinality der kleineren Input-Menge (wobei Randolfs Artikel noch diverse komplexere Fälle untersuchen). Wie aber erklärt sich die 2554 in Jonathan Lewis' Fall, die von den 2500 Datensätzen beider Input-Mengen abweichen? Dazu ein - nicht übermäßig systematischer - Tests. Ausgangspunkt ist dabei die Query aus dem Scratchpad-Artikel, bei der ich unterschiedliche Join-Spalten einsetze:

select t1.*, t2.*
  from t1, t2
 where t1.n_400 = 0
   and t2.n_72 = t1.n_90
   and t2.n_750 = t1.n_600
   and t2.n_400 = 1;

Wenn ich an Stelle der 72, 90, 600, 750 andere Werte einsetze, ergeben sich folgende Muster:

• die Join-Cardinality sinkt bei veränderten Werten nicht unter 2500.
• sie werden offenbar wie schon in 10.2 nur von einer Seite des Joins bestimmt: statt 90 und 600 kann auf t1-Seite auch jede andere (weniger selektive) Kombination erscheinen, ohne dass sich die 2554 für die Kombination 750 + 72 ändern.
• ich vermute, dass die Selektivität der relevanten Seite des Joins die Differenz zu 2500 erklärt, denn für folgende Kombinationen erhalte ich folgende Werte:
• 1000 + 1000 => card: 2500
• 1000 + 750 => card: 2501
• 1000 + 600 => card: 2502
• 1000 + 90 => card: 2533
• 1000 + 72 => card: 2540
• 1000 + 40 => card: 2575
• 1000 + 3 => card: 3681
• 750 + 750 => card: 2502
• 750 + 600 => card: 2503
• 600 + 600 => card: 2505
• etc.
• Der Zusammenhang zwischen der im CBO-Trace erscheinenden NDV-Angabe (im Beispiel 54000) und der zusätzlichen cardinality oberhalb von 2500 (im Beispiel 54) ist rechnerisch relativ gut zu fassen, aber ich habe keine Ahnung, was er bedeutet:
• NDV: 54000 => card: 2554.147936 <=> (1/54000) * 2923988
• NDV: 66168 => card: 2543.752544 <=> (1/66168) * 2895018
• NDV: 72000 => card: 2539.618041 <=> (1/72000) * 2852498
• NDV: 82710 => card: 2534.468775 <=> (1/82710) * 2850912
• NDV: 90000 => card: 2531.389226 <=> (1/90000) * 2825030

Woher der Multiplikator von ca. 2.900.000 kommen könnte, weiß ich nicht - aber ich vermute, dass folgende Artikel bei Jonathan Lewis zeigen werden, was an den hier aufgestellten Behauptungen und Vermutungen dran ist.

Nachtrag 04.12.2014: Stefan Koehler hat in einem Kommentar zum Scratchpad-Artikel vermutlich die Antwort auf meine Frage geliefert. Die Basis dafür liefert ein Artikel von Alberto Dell'Era auf den mich Jonathan Lewis verwiesen hatte: dort wird eine (in verlinkten Artikeln genauer beschriebene) Funktion SWRU (select without replacement uniform) verwendet, mit deren Hilfe man die Wahrscheinlichkeit des Auftretens einer bestimmten Anzahl unterschiedlicher Werte beim Zugriff auf eine Menge mit einer bestimmten Anzahl von Elementen (unter der Annahme der Gleichverteilung) bestimmen kann. Stefan Koehler verwendet in seiner Rechnung folgende vereinfachte Version der Formel:

(input_num_of_distinct_values) * (1 - power(1 - sample_size/total_size, total_size/input_num_of_distinct_values))

-- im Beispiel:
54000 * (1 - power(1 - 2500/1000000, 1000000/54000)) = 2446,00097
-- die cardinality errechnet sich dann als:
(2500 * 2500)/2446,00097 = 2555,19114

Das Ergebnis entspricht in diesem und den anderen Testfällen ziemlich akkurat den Erwartungen. An dieser Stelle wird mir mal wieder klar, dass eine solide mathematische Grundlage manchmal ganz hilfreich wäre.