Join Selectivity und Statistiken

Dieser Tage bin ich auf folgenden Effekt hereingefallen: gegeben war ein JOIN einer kleineren temporären Tabelle mit Bonpositionen und einer großen partitionierten Tabelle mit den zugehörigen Headern, der für ältere historische Daten ganz problemlos gelaufen war. Vor ein paar Tagen kippte dann der Plan beim Zugriff auf aktuellere Header und ich versuchte herauszubekommen, was passiert war (allerdings nicht, ehe ich erst mal einige Zeit damit verschwendete, ihn mit allerlei Hints wieder zurück zu biegen). Was ich sah, habe ich hier auf ein ganz simples Beispiel reduziert:

In meinem Beispiel sind die Tabellen gleichgroß und nicht partitioniert, da das eigentlich gar keine Rolle spielte. Die Inhalte sind auch alles andere als aufregend:

select col1
     , count(*)
  from t_2
 group by col1

 COL1   COUNT(*)
----- ----------
    1       5000
    0       5000

select col1
     , count(*)
  from t_4
 group by col1

 COL1   COUNT(*)
----- ----------
    1       2500
    2       2500
    3       2500
    0       2500

Zunächst die Query und der Plan:

set autot on

select count(*)
  from t_2
     , t_4
 where t_2.col1 = t_4.col1;

  COUNT(*)
----------
  25000000

Abgelaufen: 00:00:01.29

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

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     6 |    25   (4)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |     6 |            |          |
|*  2 |   HASH JOIN         |      |     1 |     6 |    25   (4)| 00:00:01 |
|   3 |    TABLE ACCESS FULL| T_2  | 10000 | 30000 |    12   (0)| 00:00:01 |
|   4 |    TABLE ACCESS FULL| T_4  | 10000 | 30000 |    12   (0)| 00:00:01 |
----------------------------------------------------------------------------

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

   2 - access("T_2"."COL1"="T_4"."COL1")

Laut Plan liefert der HASH JOIN in STEP 2 also nur einen Satz, tatsächlich aber sind es 25000000. Wenn ich die Standard-Formel zur Berechnung von Join-Cardinalities heranziehe, dann liefert sie:

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)

Ohne NULL-Werte ergibt sich für die Cardinality:

10000 * 10000 / greatest (2, 4) = 25000000

Das wäre also exakt richtig gewesen. Woher also die 1?

Dazu noch die Statistiken:

select table_name
     , num_rows
  from user_tables
 where table_name in ('T_2', 'T_4');

TABLE_NAME   NUM_ROWS
---------- ----------
T_2             10000
T_4             10000

select table_name
     , column_name
     , num_distinct
     , density
  from user_tab_cols
 where table_name in ('T_2', 'T_4')
   and column_name = 'COL1';

TABLE_NAME COLUMN_NAME NUM_DISTINCT    DENSITY
---------- ----------- ------------ ----------
T_2        COL1                   2         ,5
T_4        COL1                   4        ,25

Sieht erst mal ganz plausibel aus - ist es aber natürlich nicht. Deshalb hier noch das CREATE Script zum Fall:

drop table t_2;

-- initiale Füllung von T_2 mit Daten, die nicht zu T_4 passen
create table t_2
as
select rownum id
     , mod(rownum, 2) + 4 col1
  from dual
connect by level <= 10000;

exec dbms_stats.gather_table_stats(user, 'T_2')

delete from t_2;

-- erst jetzt kommen die Daten, die zu den Werten in T_4 passen
insert into t_2
select rownum id
     , mod(rownum, 2) col1
  from dual
connect by level <= 10000;

commit;

drop table t_4;

create table t_4
as
select rownum id
     , mod(rownum, 4) col1
  from dual
connect by level <= 10000;

exec dbms_stats.gather_table_stats(user, 'T_4')

select *
  from user_tables
 where table_name in ('T_2', 'T_4');

set autot on

select count(*)
  from t_2
     , t_4
 where t_2.col1 = t_4.col1;

Im praktischen Fall waren die Partitionsstatistiken akkurat, aber die globalen Statistiken mit den HIGH_VALUE und LOW_VALUE-Werten zu den Spalten der Header-Tabelle waren uralt, so dass die Überlappung mit den Spaltenwerten der Positionstabelle irgendwann aufhörte. Für die Positionstabelle hatte ich die Statistiken selbst erzeugt. Relevant waren also eher folgende Statistiken:

select table_name
     , column_name
     , last_analyzed
     , low_value
      , high_value
  from user_tab_cols
 where table_name in ('T_2', 'T_4')
   and column_name = 'COL1';

TABLE_NAME COLUMN_NAME LAST_ANALYZED       LOW_VALUE            HIGH_VALUE
---------- ----------- ------------------- -------------------- ----------
T_2        COL1        08.05.2012 18:42:40 C105                 C106
T_4        COL1        08.05.2012 18:42:41 80                   C104

Wobei das last_analyzed-Datum im Test nicht arg viel aussagt. Aber die Wertebereiche der Spalten sind überschneidungsfrei und das bringt den CBO unmittelbar zum - einleuchtenden - Schluss, dass der Join kein Ergebnis liefern wird (woraus er dann die 1 macht). Einmal mehr genügt es also, korrekte Statistiken zu liefern, um vom CBO korrekte Abschätzungen zu bekommen (wobei im gegebenen Fall aus der 1 dann allerlei unglückliche NL Operationen folgten):

exec dbms_stats.gather_table_stats(user, 'T_2')

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |     6 |    30   (4)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |     6 |            |          |
|*  2 |   HASH JOIN         |      |    25M|   143M|    30   (4)| 00:00:01 |
|   3 |    TABLE ACCESS FULL| T_2  | 10000 | 30000 |    17   (0)| 00:00:01 |
|   4 |    TABLE ACCESS FULL| T_4  | 10000 | 30000 |    12   (0)| 00:00:01 |
----------------------------------------------------------------------------

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

   2 - access("T_2"."COL1"="T_4"."COL1")

Da mir die Header-Tabelle nicht gehört, habe ich allerdings nicht ihre, sondern die Statistiken der Positionstabelle angepasst und dazu dbms_stats.set_column_stats verwendet, wie Tony Hasler es in seinem Blog vor einiger Zeit vorgeführt hat.

Eine Alternative wäre übrigens wahrscheinlich die Anlage von Histogrammen in der Positionstabelle gewesen, wie man (natürlich) bei Jonathan Lewis in Kapitel 10: Join Cardinality von Cost-Based Oracle nachlesen kann (S. 280ff.). In meinem Beispiel funktioniert das allerdings nur, wenn ich für beide Tabellen Histogramme erzeuge, dann allerdings unabhängig von der Überschneidung der Wertebereiche (was vermutlich so nicht beabsichtigt ist).