Donnerstag, Juli 24, 2014

Korrektur der Join Cardinality

Laut Randolf Geist ist es "one of the most obvious weak spots of the optimizer: A filter on a table that is joined to another table that has a skewed value distribution in the FK column(s)." Der Satz ist die Antwort auf eine Frage im OTN-Forum, die ein recht kompaktes Beispiel enthielt, bei dem der Optimizer sich hinsichtlich der Cardinality eines Joins massiv verschätzt. Hier eine vereinfachte Version des einfachen Beispiels:

-- 11.2.0.1
drop table t1;
drop table t2;

create table t1
as
select rownum id
     , 'val_' || rownum col1
  from dual
connect by level <= 20;

create table t2
as
select case when rownum > 1000 then 20
            else mod(rownum, 19) + 1
            end id
  from dual
connect by level <= 10000;  

exec dbms_stats.gather_table_stats(user, 't1')
exec dbms_stats.gather_table_stats(user, 't2')

set autot on explain
 
select count(*)
  from t1
     , t2
 where t1.id = t2.id
   and t1.col1 = 'val_19'; 
   
select count(*)
  from t1
     , t2
 where t1.id = t2.id
   and t1.col1 = 'val_20';    
   
set autot off  

Das Skript liefert folgende Ergebnisse:

SQL> select count(*)
  2    from t1
  3       , t2
  4   where t1.id = t2.id
  5     and t1.col1 = 'val_19';

  COUNT(*)
----------
        52

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

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |    13 |     5  (20)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |    13 |            |          |
|*  2 |   HASH JOIN         |      |   500 |  6500 |     5  (20)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL| T1   |     1 |    10 |     2   (0)| 00:00:01 |
|   4 |    TABLE ACCESS FULL| T2   | 10000 | 30000 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------

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

   2 - access("T1"."ID"="T2"."ID")
   3 - filter("T1"."COL1"='val_19')

SQL> select count(*)
  2    from t1
  3       , t2
  4   where t1.id = t2.id
  5     and t1.col1 = 'val_20';

  COUNT(*)
----------
      9000

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

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |    13 |     5  (20)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |    13 |            |          |
|*  2 |   HASH JOIN         |      |   500 |  6500 |     5  (20)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL| T1   |     1 |    10 |     2   (0)| 00:00:01 |
|   4 |    TABLE ACCESS FULL| T2   | 10000 | 30000 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------

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

   2 - access("T1"."ID"="T2"."ID")
   3 - filter("T1"."COL1"='val_20')

Obwohl sich die Anzahl der Ergebnissätze massiv unterscheidet (52 zu 9000) schätzt der Optimizer die Join-Cardinality in beiden Fällen auf 500. Dieser Wert ergibt sich aus der Verwendung der Standard-Formeln zur Berechung von Join-Selectivity und -Cardinality:

Join Selectivity = 1 / greater(num_distinct(t1.id), num_distinct(t2.id))
Join Cardinality = Join Selectivity * cardinality t1 * cardinality t2

Im Beispiel ergibt sich:

Join Selectivity = 1 / greater(20, 20) = 0,05
Join Cardinality = 0,05 * 1 * 10000 = 500

Im gegebenen Fall kann der menschliche Betrachter zwar unmittelbar erkennen, dass ein Wert für col1 einen entsprechenden Wert für id bedingt, aber der Optimizer ist in einer weniger günstigen Situation: er besitzt jeweils nur die Statistiken einer Tabelle: er weiß, dass der Zugriff auf t1 nur einen Satz liefern wird, aber zum Zeitpunkt der Optimierung kann er nicht bestimmen, welchem Satz der zweiten Tabelle diese Angabe entsprechen wird: dazu müsste er den Join bereits durchführen. Auch Histogramme helfen in diesem Fall nicht. Allerdings nennt Randolf Geist zwei Möglichkeiten mit deren Hilfe der Optimizer zu korrekten Cardinalities für den Join kommt - wobei beide Varianten wiederum recht massive Nachteile mit sich bringen. In 11.2 kann man den Hint precompute_subquery einsetzen, der zwar nicht offiziell dokumentiert ist, aber von Tanel Poder recht detailliert beschreiben wurde. Im Plan ergibt sich durch die Verwendung des Hints ein recht merkwürdiges Bild:

select count(*)
  from t2
 where t2.id in (select /*+ precompute_subquery */ t1.id
                   from t1
                  where t1.col1 = 'val_20');

  COUNT(*)
----------
      9000

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

---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |     3 |     2   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE    |      |     1 |     3 |            |          |
|*  2 |   TABLE ACCESS FULL| T2   |   500 |  1500 |     2   (0)| 00:00:01 |
---------------------------------------------------------------------------

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

   2 - filter("T2"."ID"=20)

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

--> erneute Ausführung

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

---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |     3 |     2   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE    |      |     1 |     3 |            |          |
|*  2 |   TABLE ACCESS FULL| T2   |  9000 | 27000 |     2   (0)| 00:00:01 |
---------------------------------------------------------------------------

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

   2 - filter("T2"."ID"=20)

In diesem Fall wird die Subquery vor der Optimierung der Haupt-Query ausgewertet und das Ergebnis des ersten Schritts bei der Planung des zweiten Schritts zugrunde gelegt. Für die id-Spalte in t2 müssen allerdings Histogramme vorliegen, damit die ungleiche Verteilung der Werte berücksichtigt werden kann. Allerdings stellt Randolf Geist fest: "However the PRECOMPUTE_SUBQUERY is undocumented (and comes with some odd behaviour for more complex queries), hence no good solution." In Oracle 12 gibt es als Alternative dazu noch das dynamic_sampling auf Level 11, das die Join-Cardinalities durch explizite Prüfung der Datengrundlage korrrigiert:

-- 12.1.0.1
select /*+ dynamic_sampling (11) */count(*)
  from t1
     , t2
 where t1.id = t2.id
   and t1.col1 = 'val_20';

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

----------------------------------------------------------------------------
| Id  | Operation           | Name | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |     1 |    13 |    10   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE     |      |     1 |    13 |            |          |
|*  2 |   HASH JOIN         |      |  9000 |   114K|    10   (0)| 00:00:01 |
|*  3 |    TABLE ACCESS FULL| T1   |     1 |    10 |     3   (0)| 00:00:01 |
|   4 |    TABLE ACCESS FULL| T2   | 10000 | 30000 |     7   (0)| 00:00:01 |
----------------------------------------------------------------------------

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

   2 - access("T1"."ID"="T2"."ID")
   3 - filter("T1"."COL1"='val_20')

Note
-----
   - dynamic statistics used: dynamic sampling (level=0)

Aber auch hier gilt:
However, this feature, too, comes at a price. At present I think one of the two row sources joined will be processed in its entirety during the sampling, so I don't think it's a viable option for large tables being joined, but I haven't done any exhaustive tests with this new feature. Since Oracle themselves don't enable it by default it looks like a bit experimental anyway.
Zu dieser Aussage passt die Beobachtung, dass ein zugehöriges SQL Trace (Event 10046) unter anderem Folgendes enthält:

SELECT /* DS_SVC */ /*+ cursor_sharing_exact dynamic_sampling(0) no_sql_tune 
  no_monitoring optimizer_features_enable(default) result_cache */ SUM(C1) 
FROM
 (SELECT /*+ qb_name("innerQuery") NO_INDEX_FFS( "T2#0")  */ 1 AS C1 FROM 
  "T2" "T2#0", "T1" "T1#1" WHERE ("T1#1"."COL1"='val_20') AND ("T1#1"."ID"=
  "T2#0"."ID")) innerQuery


call     count       cpu    elapsed       disk      query    current        rows
------- ------  -------- ---------- ---------- ---------- ----------  ----------
Parse        1      0.00       0.00          0          0          0           0
Execute      1      0.00       0.00          0          0          0           0
Fetch        1      0.00       0.00          0         22          0           1
------- ------  -------- ---------- ---------- ---------- ----------  ----------
total        3      0.00       0.00          0         22          0           1

Misses in library cache during parse: 0
Optimizer mode: ALL_ROWS
Parsing user id: 110     (recursive depth: 1)
Number of plan statistics captured: 1

Rows (1st) Rows (avg) Rows (max)  Row Source Operation
---------- ---------- ----------  ---------------------------------------------------
         1          1          1  RESULT CACHE  7cy3yc33w1z8m0wa5xpc39wqcb (cr=22 pr=0 pw=0 time=4854 us)
         1          1          1   SORT AGGREGATE (cr=22 pr=0 pw=0 time=4824 us)
      9000       9000       9000    HASH JOIN  (cr=22 pr=0 pw=0 time=5399 us cost=10 size=6500 card=500)
         1          1          1     TABLE ACCESS FULL T1 (cr=3 pr=0 pw=0 time=34 us cost=3 size=10 card=1)
     10000      10000      10000     TABLE ACCESS FULL T2 (cr=19 pr=0 pw=0 time=1922 us cost=7 size=30000 card=10000)

Unter den Row Source Operation-Angaben findet sich also noch die card=500 des ursprünglichen Plans - und das Ergebnis dieser Query wird dann zur Bestimmung der korrekten Cardinality verwendet: das scheint noch nicht unbedingt eine besonders effiziente Lösung zu sein.

Da der Artikel etwas länger geworden ist, spendiere ich ausnahmsweise ein Fazit: der Optimizer hat seine Probleme mit der Bestimmung von Join Kardinalitäten, wenn ein Filter auf einer Tabelle eingesetzt wird, die mit einer zweiten Tabelle gejoint wird, bei der für die Spalten des Foreign Key eine Ungleichverteilung vorliegt. Es gibt zwei mögliche Workarounds zur Korrektur dieser Fehleinschätzungen, aber diese Workarounds schaffen möglicherweise mehr Probleme als sie lösen. Ein expliziter Dank noch mal an Randolf Geist, der an dieser Stelle mal wieder erstaunliche Details geliefert hat.

Nachtrag 28.08.2014: Sayan Malakshinov weist darauf hin, dass der PRECOMPUTE_SUBQUERY-Hint für query blocks angegeben und somit im Zusammenspiel mit SQL Profiles, Baselines und Patches eingesetzt werden kann.

Keine Kommentare:

Kommentar veröffentlichen