Les histogrammes (1): Introduction

J’ai remarqué que le sujet des histogrammes était souvent très mal assimilé même chez les DBAs et les développeurs les plus expérimentés alors qu’ils constituent un concept fondamental en matière de Tuning SQL.

Je vais tenter à travers une série d’articles de vous présenter ce qu’il est nécessaire de savoir sur le sujet : à quoi servent les histogrammes ? Comment on les calcule ? Quels sont les différents types d’histogrammes ? Comment sont-ils stockés en base ? Quels sont leurs avantages et inconvénients ?

Dans un premier temps je vais me limiter à la version 11g puis nous verrons dans un futur article que la 12c a apporté pas mal de changements. 

 Exemple:

create table T1 as  
select rownum id, decode(mod(rownum,10),0,2,1) c_freq, nvl(blocks,999) c_hb  
from dba_tables ; 
 
update T1 set c_freq=3 where rownum<=10; 
commit; 
 
create index idx_freq on T1(C_FREQ); 
create index idx_hb on T1(C_HB); 
 
select c_freq,count(*) from T1 group by c_freq order by 2 desc; 
 
    C_FREQ   COUNT(*) 
---------- ---------- 
         1      13257 
         2       1472 
         3         10 
 
          
select c_hb,count(*) from T1 group by c_hb order by 2 desc; 
 
      C_HB   COUNT(*) 
---------- ---------- 
       999       5710 
         0       4601 
         4       1853 
         5        237 
         8        195 
        19        169 
         1        152 
        16         84 
        13         70 
         6         47 
        32         34 
         7         29 
        20         26 
       256         24 
         9         23 
     .......................... 
      5046          1 
       
829 rows selected.

Notre exemple est basé sur une table de 14 739 lignes ayant 3 colonnes : une colonne ID qui est unique, une colonne C_FREQ possédant 3 valeurs distinctes et une colonne C_HB contenant 829 valeurs distinctes. On a également un index sur la colonne C_FREQ et un autre sur la colonne C_HB. Les deux requêtes de comptage mettent en évidence que la distribution des données des deux colonnes n’est pas répartie de manière uniforme, c’est-à-dire que certaines valeurs se répètent beaucoup plus que d’autres. Ainsi, selon la popularité de la valeur de la colonne utilisée dans la requête on utilisera soit un accès indexé soit un Full Scan de la table.

 

Estimations du CBO sans histogrammes

Dans un premier temps on collecte des statistiques pour la table T1 et ses colonnes mais sans calculer d’histogrammes :

exec dbms_stats.gather_table_stats (user, 'T1', method_opt=>'for all columns size 1'); 
 
select num_rows from user_tables where table_name='T1'; 
 
  NUM_ROWS 
---------- 
     14739 
 
select column_name,num_distinct,density,num_nulls,num_buckets,sample_size,histogram  
from user_tab_col_statistics  
where table_name='T1' and column_name='C_FREQ'; 
 
COLUMN_NAME                    NUM_DISTINCT    DENSITY  NUM_NULLS NUM_BUCKETS SAMPLE_SIZE HISTOGRAM 
------------------------------ ------------ ---------- ---------- ----------- ----------- ----------- 
C_FREQ                                    3 ,333333333          0           1       14739 NONE

Le fait d’avoir écrit « FOR ALL COLUMNS SIZE 1 » pour le paramètre METHOD_OPT indique qu’on veut calculer des statistiques pour toutes les colonnes mais sans histogrammes (c’est ce que signifie le SIZE 1). La colonne HISTOGRAM de la vue USER_TAB_COL_STATISTICS est à NONE ce qui confirme bien qu’aucun histogramme n’a été calculé pour la colonne C_FREQ de la table T1.

Voyons maintenant ce qu’estime le CBO lorsqu’on requête les lignes de la table T1 avec C_FREQ = 3 :

select * from T1 where C_FREQ=3; 
 
------------------------------------------------------------------------------------ 
| Id  | Operation         | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers | 
------------------------------------------------------------------------------------ 
|   0 | SELECT STATEMENT  |      |      1 |        |     10 |00:00:00.01 |      35 | 
|*  1 |  TABLE ACCESS FULL| T1   |      1 |   4913 |     10 |00:00:00.01 |      35 | 
------------------------------------------------------------------------------------

En comparant les colonnes E-Rows et A-Rows du plan on s’aperçoit que le CBO s'est trompé puisqu’il a estimé une cardinalité de 4913 lignes au lieu de 10 réellement retournées. Cette erreur (qui n’en est pas vraiment une) s’explique par le fait qu’en l'absence d'histogrammes le CBO suppose que les lignes sont uniformément réparties dans la table et il applique donc la formule suivante pour estimer la cardinalité retournée:

NUM_ROWS/NUM_DISTINCT = 14739/3 = 4913

A cause du nombre important de lignes estimées, le CBO a opté pour un FULL TABLE SCAN alors qu’un accès via l’index aurait été plus efficace.

Voyons maintenant ce qu’estime le CBO lorsqu’on filtre sur la colonne C_HB qui contient un nombre bien plus important de valeurs distinctes que la colonne C_FREQ :

select column_name,num_distinct,density,num_nulls,num_buckets,sample_size,histogram  
from user_tab_col_statistics  
where table_name='T1' and column_name='C_HB'; 
 
COLUMN_NAME                    NUM_DISTINCT    DENSITY  NUM_NULLS NUM_BUCKETS SAMPLE_SIZE HISTOGRAM 
------------------------------ ------------ ---------- ---------- ----------- ----------- ---------- 
C_HB                                    829 ,001206273          0           1       14739 NONE 
 
select * from T1 where C_HB=999; 
 
------------------------------------------------------------------------------------------------ 
| Id  | Operation                   | Name   | Starts | E-Rows | A-Rows |   A-Time   | Buffers | 
------------------------------------------------------------------------------------------------ 
|   0 | SELECT STATEMENT            |        |      1 |        |   5710 |00:00:00.01 |     806 | 
|   1 |  TABLE ACCESS BY INDEX ROWID| T1     |      1 |     18 |   5710 |00:00:00.01 |     806 | 
|*  2 |   INDEX RANGE SCAN          | IDX_HB |      1 |     18 |   5710 |00:00:00.01 |     394 | 
------------------------------------------------------------------------------------------------

Là aussi le nombre de lignes estimées est loin de la réalité (18 vs 5710). Le nombre 18 a été obtenu en divisant le nombre de lignes de la table par le nombre de valeurs distinctes de la colonne (E-Rows = 14739/829 = 17.79 = 18). Du coup le CBO a choisi un accès indexé alors qu’un Full Table Scan aurait sûrement été plus judicieux.

On se rend donc compte avec ces exemples que lorsque les données sont biaisées en termes de distribution de valeurs, les statistiques classiques ne suffisent plus à l’optimiseur pour estimer des cardinalités proches de la réalité. C’est là que les histogrammes rentrent en jeu.

Nous allons voir dans les prochains articles comment calculer des histogrammes sur les deux colonnes en question et analyser ce que donnent les estimations du CBO grâce à ces nouvelles données.