Histogramme für Spalten mit extremer Ungleichverteilung

Mal wieder ein mäßig präziser Titel. Gemeint ist Folgendes: wenn in einer Spalte ein bestimmter Wert für nahezu sämtliche Sätze vorliegt und andere Werte extrem selten erscheinen, dann ist es nicht unwahrscheinlich, dass die seltenen Werte in einem mit auto_sample_size erzeugten Histogramm übersehen werden, was dann zur Folge hat, dass ihre Cardinality massiv überschätzt wird. Dazu ein Beispiel mit 11.2.0.1:

create table t_predominant
as
select rownum id
     , case when mod(rownum, 30000) = 10000 then 2
            when mod(rownum, 30000) = 20000 then 3
       else 1 end col_skew
     , lpad('*', 50, '*') padding
  from dual
connect by level <= 1000000;

select col_skew, count(*)
  from t_predominant
 group by col_skew;

COL_SKEW   COUNT(*)
-------- ----------
       1     999933
       2         34
       3         33

begin
  dbms_stats.gather_table_stats(
      user
    , 't_predominant'
    , estimate_percent=>dbms_stats.auto_sample_size
    , method_opt=>'for columns col_skew size 254'
  );
end;
/

Ich lege also eine Tabelle mit 1M rows an, von denen fast alle in der col_skew den Wert 1 enthalten. Nur in 33 bzw. 34 Fällen erscheinen die Werte 2 und 3. Anschließend erzeuge ich explizit Histogramme für die Spalte col_skew mit dem Standard-Wert für estimate_percent. Ein Blick auf die Cardinality-Schätzungen beim Zugriff, zeigt, dass sich der CBO für die seltenen Fälle massiv verkalkuliert:

explain plan for
select count(*) from T_PREDOMINANT where COL_SKEW = 1;

------------------------------------------------------------------------------------
| Id  | Operation          | Name          | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |               |     1 |     3 |  2453   (1)| 00:00:30 |
|   1 |  SORT AGGREGATE    |               |     1 |     3 |            |          |
|*  2 |   TABLE ACCESS FULL| T_PREDOMINANT |   999K|  2929K|  2453   (1)| 00:00:30 |
------------------------------------------------------------------------------------

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

   2 - filter("COL_SKEW"=1)

explain plan for
select count(*) from T_PREDOMINANT where COL_SKEW = 2;

------------------------------------------------------------------------------------
| Id  | Operation          | Name          | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |               |     1 |     3 |  2453   (1)| 00:00:30 |
|   1 |  SORT AGGREGATE    |               |     1 |     3 |            |          |
|*  2 |   TABLE ACCESS FULL| T_PREDOMINANT |   500K|  1464K|  2453   (1)| 00:00:30 |
------------------------------------------------------------------------------------

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

   2 - filter("COL_SKEW"=2)

Für den Fall mit "col_skew = 1" ist das Ergebnis präzise, aber woher kommen die abwegigen 500K für den Fall "col_skew = 2". Die Antwort findet man bei Jonathan Lewis: "If the value you supply does not appear in the histogram, but is inside the low/high range of the histogram then the cardinality will be half the cardinality of the least frequently occurring value that is in the histogram."

select column_name
     , num_distinct
     , low_value
     , high_value
     , histogram
     , num_buckets
     , sample_size
  from dba_tab_cols
 where table_name = 'T_PREDOMINANT'
   and column_name = 'COL_SKEW';

COLUMN_NAME     NUM_DISTINCT LOW_VALUE  HIGH_VALUE HISTOGRAM       NUM_BUCKETS SAMPLE_SIZE
--------------- ------------ ---------- ---------- --------------- ----------- -----------
COL_SKEW                   3 C102       C104       FREQUENCY                 1        5568

Der Wert 2 liegt zwischen LOW_VALUE und HIGH_VALUE, erscheint aber offensichtlich nicht im Histogramm und deshalb berechnet sich seine Cardinality als ("cardinality of the least frequently occurring value")/2: im gegebenen Fall ist die "cardinality of the least frequently occurring value" die des einzigen im Histogramm enthaltenen Wertes - also 1000K, so dass sich die 500K für die Werte 2 und 3 ergeben. Die sample_size von 5568 ist dabei ein besonderer Effekt der auto_sample_size, auf den Randolf Geist gelegentlich hingewiesen hat (der verlinkte Kommentar weist auch explizit auf den hier angesprochenen Fall der Nichtberücksichtigung seltener Werte im Histogramm hin).

Allerdings ergibt sich in meinem Test-Fall die gleiche Cardinality von 500K auch für Werte jenseits der LOW_VALUE, HIGH_VALUE-Grenzen:

explain plan for
select count(*) from T_PREDOMINANT where COL_SKEW = 4;

------------------------------------------------------------------------------------
| Id  | Operation          | Name          | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |               |     1 |     3 |  2453   (1)| 00:00:30 |
|   1 |  SORT AGGREGATE    |               |     1 |     3 |            |          |
|*  2 |   TABLE ACCESS FULL| T_PREDOMINANT |   500K|  1464K|  2453   (1)| 00:00:30 |
------------------------------------------------------------------------------------

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

   2 - filter("COL_SKEW"=4)

explain plan for
select count(*) from T_PREDOMINANT where COL_SKEW = 10000000000000;

------------------------------------------------------------------------------------
| Id  | Operation          | Name          | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |               |     1 |     3 |  2453   (1)| 00:00:30 |
|   1 |  SORT AGGREGATE    |               |     1 |     3 |            |          |
|*  2 |   TABLE ACCESS FULL| T_PREDOMINANT |   500K|  1464K|  2453   (1)| 00:00:30 |
------------------------------------------------------------------------------------

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

   2 - filter("COL_SKEW"=10000000000000)

Jonathan Lewis schreibt dazu: "If the value you supply is outside the low/high range of the histogram Oracle starts with the “half the least popular” value, then applies the normal (for 10g) linear decay estimate so that the cardinality drops the further outside the known range your requested value falls." Das scheint hier nicht einzutreten, aber möglicherweise liegt hier ein ähnlicher Fall vor, wie der von Randolf Geist im Zusammenhang mit column groups beschriebene: "If there is only a single distinct value in the statistics then the "out-of-range" detection of the optimizer is not working correctly."

Um ein brauchbares Histogramm zu erhalten, ändere ich in meinem Testfall die estimate_percent auf 100:

begin
  dbms_stats.gather_table_stats(
      user
    , 't_predominant'
    , estimate_percent=>100
    , method_opt=>'for columns col_skew size 254'
  );
end;
/

explain plan for
select count(*) from T_PREDOMINANT where COL_SKEW = 2;

------------------------------------------------------------------------------------
| Id  | Operation          | Name          | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |               |     1 |     3 |  2453   (1)| 00:00:30 |
|   1 |  SORT AGGREGATE    |               |     1 |     3 |            |          |
|*  2 |   TABLE ACCESS FULL| T_PREDOMINANT |    34 |   102 |  2453   (1)| 00:00:30 |
------------------------------------------------------------------------------------

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

   2 - filter("COL_SKEW"=2)

Ein paar alternative Lösungen zum Problem findet man bei Nikolay Savvinov, der sich dabei wiederum auf Vorschläge von Jonathan Lewis bezieht, nämlich die Anlage eines FBI (und eine Anpassung der zugehörigen Queries) bzw. die manuelle Erzeugung geeigneter Histogramme.

Beim Herrn Savvinov habe ich dann noch einen Link auf einen weiteren Artikel von Randolf Geist entdeckt, der so ziemlich alles, was ich hier gerade aufgeschrieben habe, ausführlich ausführt und erläutert - sogar das Beispiel ist nahezu identisch mit dem, das ich mir gebastelt habe - und noch allerlei zusätzliche Informationen liefert. Vielleicht hätte ich dort erst mal suchen sollen ...