Join Cardinality

Zu Erinnerungszwecken die Formel aus Jonathan Lewis' Cost Based Oracle (Kapitel 10, S. 265ff.) zur Join Cardinality für einfache Joins mit zwei Tabellen:

-- 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)

Für die Tabellen des Lewis'schen Beispiels ergibt sich:

Join Selectivity
   = ((10000 - 0)/ 10000) *
     ((10000 - 0)/ 10000) /
     greater(30,40)
   = 1/40

Join Cardinality
   = 1/40 * (400 * 200)
   = 2000

Ich habe das Beispiel des Buchs mit 11.2.0.1 durchgespielt (die Scripts kann man übrigens hier downloaden) und bekomme die gleichen cardinalities wie der Herr Lewis, aber eine geringfügig andere cost-Angabe:

-----------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost  |
-----------------------------------------------------------
|   0 | SELECT STATEMENT   |      |  2000 | 68000 |    58 |
|*  1 |  HASH JOIN         |      |  2000 | 68000 |    58 |
|*  2 |   TABLE ACCESS FULL| T2   |   200 |  3400 |    28 |
|*  3 |   TABLE ACCESS FULL| T1   |   400 |  6800 |    28 |
-----------------------------------------------------------

Vermutlich ist die abweichende cost-Angabe mal wieder ein round/ceil-Effekt.

Nachtrag 15.02.2012: Für einen Join über mehrere Spalten wird durch die greater-Ausdrücke für alle Spalten dividiert, also:

Join Selectivity
   = ... 
/ greater (num_distinct(t1.col1),  num_distinct(t2.col1))
/ greater (num_distinct(t1.col2),  num_distinct(t2.col2))

Im Sinne einer doppelt verketteten Liste hier noch der Verweis auf einen jüngeren Eintrag zum gleichen Thema (und mit nahezu gleichem Titel).