Histogrammes en 11gR2

Les performances d’Oracle reposent sur l’analyse des requêtes SQL au travers du Cost Based Optimizer (CBO) qui s’appuie sur les statistiques sur les divers objets de la base. Toute le problématique des statistiques Oracle est d’avoir une représentation la plus fidèle possible des données en base en un minimum d’informations. La solution proposée par Oracle pour le faire est d’utiliser les histogrammes.

Au niveau des tables et sans s’occuper des problématiques de partitionnement les statistiques sont visibles dans des vues diverses qui vont donner des informations au niveau de la table (par exemple DBA_TABLES, ALL_TAB_STATISTICS, USER_TABLES …) puis pour les colonnes des tables (USER_TAB_COLUMNS, DBA_TAB_COL_STATISTICS …) et enfin pour certaines colonnes un histogramme est créé et visible dans des vues telles que DBA_COL_HISTOGRAMS. Reste à juger de leur pertinence afin de décider si oui ou non on en a besoin pour telle ou telle colonne.

Frequency Histograms

Un petit jeu de test ?

create table t0 ( c1 number );

insert into t0
select abs(ceil(dbms_random.normal*3))
from sys.dual
connect by rownum <= 1E5 ;

exec dbms_stats.gather_table_stats(user, 'T0', method_opt=>'FOR COLUMNS C1 SIZE 254', estimate_percent=>100)

On effectue un Explain plan pour toutes les requête dont le prédicat est C1=x où x varie de -2 à 15 que l’on compare au nombre effectif d’occurrence de chaque valeur ( count(*) group by C1 ).

Résultat

 

histo_freq

 

En bleu l’histogramme, en rouge le nombre effectif d’occurrences des valeurs données en abscisse … On a ici un histogramme qui représente parfaitement le contenu de la colonne C1, et qui contredit la documentation officielle du fait qu’il ne décroît pas progressivement au delà des valeurs minimales et maximales.

Pourquoi ?

L’histogramme a été calculé sur un échantillon de 100 %. Le CBO le considère comme “juste” en l’occurrence à raison, mais dans deux semaines ? Au bout de deux semaines aussi, et c’est nettement moins agréable.

Si on laisse Oracle choisir l’échantillon, ça donne quoi ?

exec dbms_stats.gather_table_stats(user, 'T0')

freq_auto

ATTENTION: L’échelle est logarithmique. Mais là on a bien ce que décrit la documentation. Et l’histogramme garde sa pertinence.

Height Balanced Histograms

En résumé: Les Frequency histograms c’est génial mais ça prend de la place donc si le nombre de valeur distinctes d’une colonne est trop important il faut trouver une autre solution pour rendre compte de la répartition non uniforme des données et ne pas trop encombrer le dictionnaire des données; c’est là qu’intervient le second type d’histogramme appelé height balanced histogram.

Oracle a décidé que le nombre maximal de valeurs distinctes qu’il allait stocker pour une colonne était de 254, au delà ou si on demande de calculer l’histogramme pour moins de valeurs qu’il n’en existe pour la colonne (non documenté) l’histogramme devient height balanced.

Un nouveau petit jeu de test ?

create table t1 ( c1 number );

insert /*+ APPEND */ into t1
select ceil(dbms_random.normal*35)
from sys.dual
connect by rownum 'FOR COLUMNS C1 SIZE 254', estimate_percent=>100)

create table t2 ( c1 number );

insert /*+ APPEND */ into t2
select (150-abs(c))*sign(c+0.1) 
from (select ceil(dbms_random.normal*35) c
      from sys.dual
      connect by rownum <=1E5 ) ;

On obtient les répartitions de données suivantes :

tables_loiNormale

Cardinalités sans histogramme

Si on calcule les statisitques sur la table en ne calculant pas l’histogramme on obtient la distribution de cardinalités suivantes (en vert):

no_histogram

Comme on pouvait s’y attendre, Oracle considère que chaque valeur est représentée autant que les autres. A noter tout de même: avant la valeur minimale et au delà de la valeur maximale détectée, le CBO estime une cardinalité progrssivement décroissante de la valeur moyenne calculée jusuq’à une valeur de 1. La raison en est que les statistiques n’ont pas vocation à être calculées en permanence et que donc, la table vivant, de nouvelles valeurs peuvent apparaitre.

Histogramme calculé sur un échantillon de 100% et pour 254 buckets

0n obtient la distribution de cardinalités suivantes (en bleu):

normal_h254_100

On constate :

  • Que l’histogramme fonctionne par palliers
  • Que dans chaque pallier chaque valeur n’est pas équitabement représentée.
  • Que l’estimation d’une cardinalité est au pire égale à l’estimation sans histogramme.

Histogramme calculé sur un échantillon de 100% et on laisse à Oracle le choix du nombre de buckets

normal_auto_e100

On constate :

  • Peu de différence avec la distribution précédente

Histogramme calculé sur un échantillon et pour un nombre du buckets nombre de buckets dont les choix sont laissés à Oracle

normal_auto_auto

On constate :

  • Cette fois ci, trois palliers
  • Une moins bonne correspodance des cardinalités estimées avec les cardinalités réelles

Globalement sur ces tests

Les histogrammes sont assez représentatifs des données (ouf !) mais peut-être que ça vient de la forme de la courbe, d’où l’idée d’essayer avec une courbe ‘inversée’.

On recrée le deuxième type d’histogramme (100% buckets auto)

normal_bol_h255_e100

On constate :

  • Une estimation aussi “bonne” ou “mauvaise” que l’estimation faite dans les mêmes conditions sur l’autre répartion de données.

Comment un histogramme est-il calculé ?

les données de la colonne sont ordonnées et le résultat découpé en autant de buckets que vous ou Oracle en avez décidé. A partir de là à chaque point de rupture entre deux buckets, la valeur est enregistrée.A chaque bucket correspond donc le nombre de lignes valuées de la table divisé par le nombre du buckets. A une valeur de la colonne qui est relevée correspond une cardinalité estimée au nombre de fois où elle a été relevée multiplié par le nombre de lignes que contient un bucket

Est-il possible de faire mieux ?

Oui mais c’est très coûteux: en effet, si on fait du dynamic sampling on obtient ça:

dynamic_sampling

Seulement, du coup, le temps de parsing est très fortement allongé et les lectures disques augmentées

Limites des histogrammes

Le calcul des histogrammes parait un bon compromis, cependant il est des cas où il s’avère inutile. Le graphe ci-après représente l’histogramme et les valeurs calculées sur une table de 10 millions de lignes sur une colonne présentant près de 1600 valeurs distinctes.

v1600_h254_100

On constate :

  • L’estimation faite est équivalente à celle qui serait survenue en l’absence d’histogramme. Si le calcul de l’histogramme n’est pas néfaste, il reste contre-productif.

Jusqu’à maintenant les histogrammes étaient calculés sur des colonnes de type numérique. Si on calcule un histogramme sur une colonne de type varchar2 on peut rencontrer un soucis dans le cas où un grand nombre de valeurs distinctes ont leur 32 premiers caractères en commun.

create table t6 ( c1 varchar2(64) );

insert /*+ APPEND */ into t6
select 'Foo Bar Baz Foo Bar Baz Foo Bar Baz '||to_char(ceil(dbms_random.normal*35))
from sys.dual
connect by rownum 'FOR COLUMNS C1 SIZE 254', estimate_percent=>100)

varchar

On constate :

  • L’estimation faite est égale au nombre de lignes de la table et donc totalement hors de propos.

Conclusion

Les histogrammes représentent un moyen intéressant d’avoir une estimation de la cardinalité réelle d’une occurrence de valeur pour une colonne donnée. Cependant, si les valeurs sont trop nombreuses ou pour certains types de données trop centrées autour d’une même valeur les statistiques calculées seront au mieux inutiles et au pire complètement erronées.

PS

Cet article est paru précédemment sur le site de mon ancien employeur.

Explain plan, Bind variables et Histogrammes (1/2)

Lors d’une discussion sur un forum j’ai lancé l’affirmation suivante qui a laissé un membre dubitatif :

Vous utilisez ici des bind variables. Lorsque vous utilisez ce type de variable dans un explain plan, Oracle ignore les éventuels histogrammes sur les colonnes alors que lors d’une exécution réelle il les prends en compte.

Je reprends ici les éclaircissements donnés à ce sujet sur ledit forum.

Mise en place d’un environnement de test

Je me suis créé une table de test de 100 000 lignes contenant une colonne qui suit une loi normale de la manière suivante :

set autot off

drop table t1;
create table t1 ( c1 number );

insert /*+ APPEND */ into t1
select abs(ceil(dbms_random.normal*3))
from sys.dual
connect by rownum 'FOR COLUMNS C1 SIZE 254', estimate_percent=>100)

J’ai donc la distribution suivante pour les valeurs de ma table

select c1, count(*)
from t1
group by c1
order by c1 ;

        C1   COUNT(*)
---------- ----------
         0      12917
         1      24741
         2      21291
         3      16074
         4      11194
         5       6775
         6       3840
         7       1778
         8        868
         9        346
        10        113
        11         51
        12         10
        13          2

Tests avec explain plan

Premier test avex une valeur fortement représentée :

variable s number

exec :s := 1 ;

explain plan for
select /* tst explain 1 */ * from t1
where c1=:s ;

@?/rdbms/admin/utlxplp

PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------
Plan hash value: 4291296153

-------------------------------------------------------------------------
| Id  | Operation        | Name | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------
|   0 | SELECT STATEMENT |      |  7143 | 21429 |    14   (0)| 00:00:01 |
|*  1 |  INDEX RANGE SCAN| I_T1 |  7143 | 21429 |    14   (0)| 00:00:01 |
-------------------------------------------------------------------------

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

   1 - access("C1"=TO_NUMBER(:S))

13 rows selected.

Le plan d’exécution m’indique que je vais remonter 7143 lignes. Je sais que c’est faux, la distribution des données me donne 24741 et l’histogramme ayant été calculé complètement, il donne les mêmes inforamtions à l’optimiseur.

Je fais un nouveau test avec une valeur très faiblement représentée

exec :s := 13 ;

explain plan for
select /* tst explain 13 */ * from t1
where c1=:s ;

@?/rdbms/admin/utlxplp
 
PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------
Plan hash value: 4291296153

-------------------------------------------------------------------------
| Id  | Operation        | Name | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------
|   0 | SELECT STATEMENT |      |  7143 | 21429 |    14   (0)| 00:00:01 |
|*  1 |  INDEX RANGE SCAN| I_T1 |  7143 | 21429 |    14   (0)| 00:00:01 |
-------------------------------------------------------------------------

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

   1 - access("C1"=TO_NUMBER(:S))

13 rows selected.

Là encore le plan m’annonce que je vais remonter 7143 lignes, hors je sais que j’en remonterai deux

Tests d’exécution

Je refais mon test pour la valeur 13 qui doit remonter deux lignes

select /* tst exec 13 */ * from t1
where c1=:s ;

        C1
----------
        13
        13

Formidable, elle remonte bien deux lignes, l’explain plan m’avait donc bien donné une information erronée. Que dit le plan choisi par le CBO ?

select * from table( dbms_xplan.display_cursor() ) ;

------------------------------------------------------------------------------------
SQL_ID  31j5tck2g6gd2, child number 0
-------------------------------------
select /* tst exec 13 */ * from t1 where c1=:s

Plan hash value: 4291296153

-------------------------------------------------------------------------
| Id  | Operation        | Name | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------
|   0 | SELECT STATEMENT |      |       |       |     1 (100)|          |
|*  1 |  INDEX RANGE SCAN| I_T1 |     2 |     6 |     1   (0)| 00:00:01 |
-------------------------------------------------------------------------

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

   1 - access("C1"=:S)


18 rows selected.

Vous me direz qu’à postériori il est simple de donner le nombre de lignes qui ont été ramenées … Ok, je refais la même requête en lui demandant de me mémoriser les lignes estimées par le CBO (E-ROWS) et les lignes effectivement remontées (A-ROWS) et je refais afficher le plan.

select /*+ GATHER_PLAN_STATISTICS */ * from t1
where c1=:s ;

        C1
----------
        13
        13


select * from table( dbms_xplan.display_cursor(FORMAT=>'ALLSTATS LAST'));SQL>

PLAN_TABLE_OUTPUT
------------------------------------------------------------------------------------
SQL_ID  5av85qaqqqynu, child number 0
-------------------------------------
select /*+ GATHER_PLAN_STATISTICS */ * from t1 where c1=:s

Plan hash value: 838529891

------------------------------------------------------------------------------------
| Id  | Operation         | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |      |      1 |        |      2 |00:00:00.01 |     156 |
|*  1 |  TABLE ACCESS FULL| T1   |      1 |      2 |      2 |00:00:00.01 |     156 |
------------------------------------------------------------------------------------

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

   1 - filter("C1"=:S)


18 rows selected.

Ok, il estme donc bien deux lignes et en retourne 2 … ça parait logique et ça rassure

Pourquoi 7143 ?

On a vu qu’un explain plan produisait systématiquement la valeur erronée 7143, d’où la tire-t-il ? Je suppose qu’il utilise la formule de cardinalité générale sans tenir compte des histogrammes :

cardialité=nombre de lignes non nulles / nombre de valeurs distinctes ce qui dans notre cas donne : 100 000 lignes non nulles pour 14 valeurs distinctes … Je vous laisse compter le temps de taper la requête :

select round(100000/14) est from dual;

       EST
----------
      7143

Donc l’explain plan ne s’est pas donné la peine de parcourir l’histogramme.

Une question reste en suspens : Pourquoi la variable n’est pas interprétée ? … Suite au prochain épisode, ça se complexifie …

Les statistiques épisode: 1: où les trouver

Depuis … Poulala, oracle s’appuie sur des statistiques plutôt que sur l’heuristique1 pour optimiser ses plans d’exécution. De version en version, les statistiques dont dispose Oracle s’étoffent offrant ainsi à oracle de plus en plus d’informations sur les données stockées en base.

Les statistiques sont essentiellement stockées au niveau du dictionnaire de donnée dans les tables décrivant les divers segments qu’oracle est capable de manipuler mais elles peuvent aussi être calculées à la volée et sur échantillonnage. Elles sont utilisée entre autre par l’optimiseur de requête d’Oracle lorsqu’il analyse une requête dans le but de produire un2 plan d’exécution efficace dans un temps raisonnable3.

A partir de ces statistiques, oracle associe un coût à un texte SQL par un algorithme complexe et amélioré à chaque nouvelle version d’Oracle qui a été décortiqué pour certaines d’entre elles par l’éminent Jonatan Lewis dans le très vendu et encore plus lu Cost Based Oracle fundamentals lui même rédigé en langue de Shakespeare et malheureusement resté jusqu’à ce jour sans traduction française. Cet ouvrage donne une formule qui permet de calculer certains coûts à partir des statistiques Oracle, reste encore à savoir où les trouver et sur ce dernier point c’est aux table de la liste suivante (et plus particulièrement les vertes qu’il conviendra de s’intéresser. (suite…)