Cost für Group By

Alexandr Antonov weist in seinem Blog auf eine Änderung des Costings für GROUP BY Operationen in 11g hin und nennt dafür folgende Formel:

GROUP BY CARD = JOIN CARD * SEL(t1.fil1) / SEL(t2.fil2) 

Ich habe daraufhin noch mal darüber nachgedacht, wie die Formel für das Costing von GROUP BY vorher ausgesehen haben könnte und, nachdem mir dazu nicht viel eingefallen war, noch mal in Jonathan Lewis' Cost Based Oracle (S. 388) nachgeschlagen und dort folgende Erklärung gefunden:

In general, the optimizer estimates the number of distinct combinations of N columns by multiplying the individual num_distinct values, and then dividing by the square root of 2 (N-1) times.

Dazu ein kleiner Test mit 11.1.0.7:

drop table t3;
create table t3
as
select mod(rownum, 10) col1
     , mod(rownum, 20) col2
  from dual
connect by level <= 10000;

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

ALTER SESSION SET EVENTS '10053 trace name context forever, level 1';

select col1, col2, count(*)
  from t3
 group by col1, col2;

ALTER SESSION SET EVENTS '10053 trace name context OFF';

Im erzeugten CBO-Trace sieht man dann unter anderem Folgendes:

Access path analysis for T3
***************************************
SINGLE TABLE ACCESS PATH 
  Single Table Cardinality Estimation for T3[T3] 
  Table: T3  Alias: T3
    Card: Original: 10000.000000  Rounded: 10000  Computed: 10000.00  Non Adjusted: 10000.00
  Access Path: TableScan
    Cost:  7.11  Resp: 7.11  Degree: 0
      Cost_io: 7.00  Cost_cpu: 1842429
      Resp_io: 7.00  Resp_cpu: 1842429
  Best:: AccessPath: TableScan
         Cost: 7.11  Degree: 1  Resp: 7.11  Card: 10000.00  Bytes: 0

Grouping column cardinality [      COL1]    10
Grouping column cardinality [      COL2]    20
***************************************

OPTIMIZER STATISTICS AND COMPUTATIONS
***************************************
GENERAL PLANS
***************************************
Considering cardinality-based initial join order.
Permutations for Starting Table :0
Join order[1]:  T3[T3]#0
GROUP BY sort

GROUP BY adjustment factor: 0.707107
GROUP BY cardinality:  142.000000, TABLE cardinality:  10000.000000

Diese Angaben deuten an, dass die Aussagen aus Cost-Based Oracle grundsätzlich noch zutreffen: die GROUP BY cardinality ergibt sich als: (10 * 20)/1,4142 = 141,42. Was einerseits zur 142 im Trace passt und andererseits zeigt, dass mein Beispiel etwas zu symmetrisch ausgefallen ist (weil 2 durch die square root von 2 natürlich wieder square root von 2 ergibt). Der GROUP BY adjustment factor ist dabei anscheinend einfach 1,4142/2 = 0,7071 - was wiederum zeigt, dass meine Beispielwerte eher unglücklich gewählt sind, denn der Wert hängt nicht von den distinkten Werten ab, sondern von der Anzahl der GROUP BY Spalten:

• 2 Spalten: GROUP BY adjustment factor: 0,7071 = 1,4142/2
• 3 Spalten: GROUP BY adjustment factor: 0,5 = 1,4142/1,4142/2
• 4 Spalten: GROUP BY adjustment factor: 0,3535 = 1,4142/1,4142/1,4142/2

Das ist nicht uninteressant, hat aber erst einmal noch nicht allzu viel mit den Ausführungen des Herrn Antonov zu tun. Daher noch ein Blick in die CBO-Traces für das Antonov'sche Beispiel. Dort findet man für den Fall der Verwendung des neuen Verfahrens eine andere GROUP BY cardinality als für den Fall der Verwendung des alten Verfahrens (_optimizer_improve_selectivity => false):

-- default Verhalten
GROUP BY adjustment factor: 1.000000
GROUP BY cardinality:  125.000000, TABLE cardinality:  500.000000
-- _optimizer_improve_selectivity => false
GROUP BY adjustment factor: 1.000000
GROUP BY cardinality:  500.000000, TABLE cardinality:  500.000000

Da nur eine Spalte im GROUP BY erscheint, überrascht der GROUP BY adjustment factor 1 nicht. Die unterschiedlichen GROUP BY cardinality-Angaben sind, so weit ich sehe, schon die einzigen (relevanten) Unterschiede der CBO-Traces für beide Versionen. Eine Erklärung für die innere Logik, die der durch _optimizer_improve_selectivity repräsentierten Berechnung zugrunde liegt, findet ich dort nicht (was allerdings auch nicht überrascht, da die Inhalte des CBO-Traces in aller Regel nicht unbedingt verbose erläutert sind). Dazu ein weiterer Test, der das Beispiel auf Alexandr Antonovs Blog behutsam erweitert:

drop table t1;
drop table t2;

CREATE TABLE t1 AS 
  SELECT LEVEL AS id1, 
         MOD(LEVEL, 10) fil1, 
         MOD(LEVEL, 5) fil3, 
         rpad('x', 1000) padding 
    FROM dual 
  CONNECT BY LEVEL < 10000 
;

CREATE TABLE t2 AS 
  SELECT LEVEL AS id2, 
         MOD(LEVEL, 20) fil2, 
         MOD(LEVEL, 15) fil4, 
         rpad('x', 1000) padding 
    FROM dual 
  CONNECT BY LEVEL < 10000 
;

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

-- Fall 1
explain plan for
SELECT t1.fil1
     , t2.fil2
  FROM t1,
       t2
 WHERE t2.id2 = t1.id1
   and t1.fil3 = 1
   AND t2.fil4 = 1
 GROUP BY t1.fil1
        , t2.fil2;

-- Fall 2
explain plan for
SELECT /*+ OPT_PARAM('_optimizer_improve_selectivity' 'false') */
       t1.fil1
     , t2.fil2
  FROM t1,
       t2
 WHERE t2.id2 = t1.id1
   and t1.fil3 = 1
   AND t2.fil4 = 1
 GROUP BY t1.fil1
        , t2.fil2;

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |   142 |  2840 |   797   (1)| 00:00:10 |
|   1 |  HASH GROUP BY      |      |   142 |  2840 |   797   (1)| 00:00:10 |
|*  2 |   HASH JOIN         |      |   667 | 13340 |   796   (1)| 00:00:10 |
|*  3 |    TABLE ACCESS FULL| T2   |   667 |  6670 |   398   (1)| 00:00:05 |
|*  4 |    TABLE ACCESS FULL| T1   |  2000 | 20000 |   398   (1)| 00:00:05 |
----------------------------------------------------------------------------

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

   2 - access("T2"."ID2"="T1"."ID1")
   3 - filter("T2"."FIL4"=1)
   4 - filter("T1"."FIL3"=1)

-- Fall 3
explain plan for
SELECT t1.fil1
     , t2.fil2
  FROM t1,
       t2
 WHERE t2.id2 = t1.id1
   and t1.fil3 = 1
   -- AND t2.fil4 = 1
 GROUP BY t1.fil1
        , t2.fil2;

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |   142 |  2414 |   797   (1)| 00:00:10 |
|   1 |  HASH GROUP BY      |      |   142 |  2414 |   797   (1)| 00:00:10 |
|*  2 |   HASH JOIN         |      |  2000 | 34000 |   796   (1)| 00:00:10 |
|*  3 |    TABLE ACCESS FULL| T1   |  2000 | 20000 |   398   (1)| 00:00:05 |
|   4 |    TABLE ACCESS FULL| T2   |  9999 | 69993 |   398   (1)| 00:00:05 |
----------------------------------------------------------------------------

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

   2 - access("T2"."ID2"="T1"."ID1")
   3 - filter("T1"."FIL3"=1)

Mit und ohne OPT_PARAM-Hint ergibt sich für diesen Fall jeweils der gleiche Plan, was ich als Indiz dafür nehme, dass hier keine "improved selectivity" wirksam wird: die Join-Cardinality (667) ist dabei absolut akkurat, aber das GROUP BY liefert tatsächlich nur 4 Sätze. Dabei ergibt sich die 142 - wie Fall 3 zeigt - unabhängig von allen Filter-Bedingungen und folglich auch unabhängig von der Größe der Ergebnismenge des HASH JOINs. Hier greift demnach die von Jonathan Lewis beschriebene Logik auf der Basis der Tabellenstatistiken. Über die Plausibilität der Annahme, dass eine Reduzierung der Satzanzahl nicht unmittelbar mit der Anzahl distinkter Wertkombinationen zu tun hat, kann man sicher diskutieren. Ohne behaupten zu wollen, ein völlig klares Bild der Zusammenhänge bekommen zu haben, ist mein Eindruck, dass die Logik der Bestimmung von cardinialities für GROUP BY Operationen insgesamt eine recht fehleranfällige ist. Außerdem frage ich mich, ob das Schlüsselwort "improved" bei Oracle ähnlich wie die Angabe "fast" etwas ist, das grundsätzlich Anlass zur Vorsicht geben sollte...