J’ai toujours du mal à expliquer concrètement et à me souvenir des explications sur les méthodes utilisées par Oracle pour le calcul des histogrammes sur les colonnes. Voici donc une tentative de simplification et de synthèse qui sera j’espère compréhensible pour le plus grand nombre, nous ne rentrerons pas ici dans le débat de la  pertinence de ces histogrammes mais vous pourrez trouver plusieurs informations sur le sujet dans les références citées en fin d’article.
L’idée de départ est claire et simple, il faut que l’optimiseur puisse établir de la manière la plus précise possible la cardinalité (le nombre de valeur)  d’un critère sur une colonne. En français, ces informations  peuvent être écrites de la manière suivante : dans la colonne “Etat” de ma table des ventes composée de 100 000 lignes, il y en a 90 0000 avec le statut “Close”,  7500 en “En cours”   et  2500 en “Anomalie” et  c’est  parfaitement compréhensible. Pour du code , il a fallu trouver une représentation la plus juste possible tout en étant  performant. Particulièrement quand le nombre de possibilités devient important  et ou même pour nous avec notre intelligence et notre compréhension,  la répétition de l’information  va nous faire perdre le fil. Ainsi on imagine très bien que pour une colonne de type “date”, l’énumération du nombre de lignes par date deviendra vite insupportable pour tout auditeur, il faut donc une méthode efficace pour calculer et représenter cette information.  Entre l’apparition des histogrammes  et la version 12c  Oracle utilise maintenant quatre techniques pour répondre à ces problématiques, nous allons voir les principes fondamentaux pour chacune d’entre elle avec plus ou moins de détails. On peut retrouvé les types d’histogramme utilisés dans une des vues *_TAB_COL_STATISTICS (par exemple DBA_TAB_COL_STATISTICS) , la colonne HISTOGRAM de type VARCHAR2(15) peut prendre en version 12C, les valeurs NONE, FREQUENCY,  HEIGHT BALANCED,  TOP-FREQUENCY et HYBRID <more>.
1)  Frequency
Autrement dit par fréquence de valeur. C’est la plus simple à comprendre et sans doute à coder. Lors du calcul , le moteur tri toutes les lignes de la table par la colonne concernée puis compte et enregistre le nombre de lignes par valeur de la colonne.  Il le fait en parcourant la liste triée et en notant le numéro de la dernière ligne ou apparait une même valeur (ENDPOINT_NUMBER) . Le nombre d’élément (n) pour une valeur (ENDPOINT_VALUE) est obtenu par la différence entre les deux points de rupture :
n =  ENDPOINT_NUMBER (ENDPOINT_VALUE)  –  ENDPOINT_NUMBER (ENDPOINT_VALUE précédent) .
Les informations END_POINT_VALUE et ENDPOINT_VALUE collectées sont stockées dans le dictionnaire et accessibles au travers des vues *_TAB_HISTOGRAMS.
Voici un exemple pour concrétiser le tout  :
Création de la table T1  :

create table T1 tablespace USERS as select * from dba_objects ;

Obtention de la répartition et du nombre de valeurs distinctes avec l’ordre suivant :

select count(*), object_type from T1 group by OBJECT_TYPE order by OBJECT_TYPE  ;

Soit 44 types d’objets différents et une distribution bien déséquilibrée dont voici un extrait :

Calcul de l’histogramme par fréquence sur la colonne “OBJECT_TYPE” de la table “T1”  :

begin
	dbms_stats.gather_table_stats(
		'SYSTEM',
		'T1',
		method_opt => 'for columns object_type size 254',
                estimate_percent=>100
	);
end;
/

On retrouve alors dans le dictionnaire les informations suivantes (extrait des  neuf premières )  :

select ENDPOINT_NUMBER , ENDPOINT_VALUE, ENDPOINT_ACTUAL_VALUE
from user_tab_histograms where table_name='T1' and column_name='OBJECT_TYPE'  ;

le nombre de ligne par type d’objet n’est pas direct , il faut réaliser la différence entre  les deux “ENDPOINT_NUMBER” , ainsi le nombre d’index est de  (3460 – 204 ) soit 3256 , comme nous l’avions vu précédemment.
Noter que la colonne ENDPOINT_VALUE correspond au codage interne de la valeur (utilisé par le moteur) , ENDPOINT_ACTUAL_VALUE  est l’information lisible pour la valeur de la colonne.
Une petite fonction analytique dans une sous-requête permet d’obtenir le  résultat  directement avec la construction de la colonne “frequency” :

select
endpoint_number, endpoint_number - nvl(prev_endpoint,0)  frequency, endpoint_value, endpoint_actual_value
from    (
select
endpoint_number, lag(endpoint_number,1) over(order by endpoint_number)  prev_endpoint,
endpoint_value,endpoint_actual_value
from
user_tab_histograms
where
table_name = 'T1' and     column_name = 'OBJECT_TYPE'
)
order by
endpoint_number;

Ce type d’histogramme est très pertinent car il donne une image précise de la distribution d’une colonne à un instant t .
2)  Height Balanced
Traduction proposée:  histogramme de hauteur équilibrée.
Quand le nombre de valeur possible devient élevé, la méthode par fréquence n’est plus performante, il fallait donc trouver autre chose. Le seuil du changement est important à connaitre , c’est 254 valeurs distinctes pour les versions inférieures  a la 12C et 1024 ensuite. La première opération du moteur est toujours la même,  il va trier les lignes en fonction des valeurs de la colonne. Il subdivise ensuite le résultat en cellule, le nombre de cellules (la fameuse valeur du “Bucket” )  va déterminé l’intervalle des échantillons, car en parcourant  la liste, Oracle va considéré la première ligne puis toutes les n lignes suivantes avec
n = nombre de valeurs non nul de la colonne/ nombre de cellules voulues.
Chaque ligne scrutée est associée à une  cellule  avec un numéro de référence s’incrémentant (c’est l’information « end point value » qui contiendra la valeur contenue). De plus si la même valeur apparaît consécutivement dans plusieurs cellules, seul le numéro de la dernière sera enregistré, en voici un exemple concret :
Soit les 20 valeurs suivante à ranger dans 5 cellules :
5, 6, 6, 6, 9, 11, 11, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 16, 17, 17
On prend la première ligne et ensuite toutes les 20/5 , 4 lignes suivantes:
5, 6, 6, 6, 9, 11, 11, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 16, 17, 17.
La première valeur de la liste est enregistré dans la cellule 0 , la seconde dans le cellule 1 et ainsi de suite pour donné le tableau suivant

Éliminons ensuite les premières cellules ou l’on retrouve une valeur identique pour ne conserver que la dernière et voilà comment sont enregistrés les informations par le moteur:

Grâce à ces données , Oracle voit que la valeur 12 est une valeur populaire (elle revient dans plus d’une cellule).
On se rend vite compte de l’approximation faite:  la valeur 13 apparait autant de fois que la valeur 12 , mais n’est pas considérée comme populaire. Si on change l’un des 11 en 16 , le nouvel arrangement de la liste fait que la valeur 12 n’est plus populaire mais c’est la valeur 13 qui le devient, de même si on remplace le 16 en 11 aucune des valeurs ne sera vue comme populaire:
5, 6, 6, 6, 9, 11, 11,11,12, 12, 12, 12,12, 13, 13, 13, 13, 13, 17, 17.
Pour le calcul de la cardinalité Oracle prend en compte la taille de la cellule , ainsi dans notre exemple ,chaque cellule représente 4 lignes , sachant que la valeur 12 apparait deux fois , la cardinalité (le nombre de ligne avec la valeur 12)  est donc de 8 ( 4 *  2) .   Le calcul pour les valeurs non populaire a varié suivant les versions , pour la 11.2.0.3  c’est :
(nombre de ligne valeur non populaire /  nombre  des autres valeurs)
Les informations à disposition pour l’optimiseur serait pour notre petite liste :

• Valeur populaire :  1  (la valeur 12)
• Valeur non populaires :  7 (les valeurs 5,6,9,11,13,16 et 17)
• Cardinalité de la valeur populaire :  8  (nous l’avons vu,  2 casiers de 4)
• Nombre de ligne des autres valeurs :  20  (nombre total)  –  8  soit 12
• La cardinalité pour les valeurs non populaires est donc de 12 /  7  soit 1,714 (arrondi à  2)

Ceci est une exemple simple et il existe beaucoup de cas différent traité par le code, imaginer par exemple que le calcul des statistiques soit fait sur un échantillon de 10% de la taille de la table , il faut que le moteur le prenne en compte et mette à l’échelle ses résultats.
Le résultat de cette technique est bien moins précis que la méthode par fréquence, et peut rendre très instable  le comportement de l’optimiseur, particulièrement si les valeurs populaires sont majoritaires dans les données,  les développeurs ont donc continué à travaillé pour l’améliorer.
3)  Top-Frequency
Histogramme de fréquence de niveau supérieur
Cet algorithme et cette méthode qui apparait à partir de la version 12c est une extension du premier,  il est choisi par le moteur lorsque le nombre de valeur distincte dépasse le seuil des 254 et les valeurs les plus populaires représentent la majorité des données. Ce serait le cas d’une table représentant les langues les plus parlés dans le monde , sur les près  de 6000 existantes, il ne doit y en avoir qu’une petite vingtaine de significatives. Dans ce cadre, seul les valeurs populaires sont traitées comme pour les histogrammes de fréquences classique, les informations pour les valeurs non populaires sont enregistrées dans deux cellules, une pour la valeur haute , l’autre pour la valeur basse.
Les critères de déclenchement sont :

• Le taux d’échantillonnage  est de type “AUTOMATIC”
• Le nombre de valeur distinctes est supérieur à 254 (ou au nombre de cellules (“bucket”) demandé)
• Le pourcentage de ligne contenant les valeurs les plus populaires est supérieur au seuil p, calculé de la manière suivante :  p = ( 1 – ( 1/nb)) * 100 . nb étant le nombre de cellules utilisées, le nombre de valeurs populaire étant nb –2.  Pour 10 cellules demandées (bucket de 10) , le nombre de lignes associé aux 8 valeurs les plus populaires doit être supérieur à 92% du nombre de ligne total .

Ainsi pour notre exemple de départ concernant la table T1 duplication de la vue  DBA_OBJECTS, on peut déclencher le calcul de type “TOP-FREQUENCY”  par la commande suivante :

begin
dbms_stats.gather_table_stats(
'SYSTEM',
'T1',
method_opt => 'FOR COLUMNS object_type size 7'
);
end;
/

Vérification du mode pris par le moteur :

select table_name , column_name, histogram from user_tab_col_statistics where table_name='T2' ;

TABLE_NAME COLUMN_NAME          HISTOGRAM
---------- -------------------- ---------------
T2         OBJECT_TYPE          TOP-FREQUENCY

Le mode d’échantillonnage est bien AUTOMATIC (le défaut de la procédure), le nombre de valeur distinctes (44) est bien supérieur au nombre de cellules demandé (7),  les 5 Tops valeurs représentent bien plus de 95% du nombre de lignes , la requête suivante et son résultat sur l’histogramme calculé nous le prouve :

select
endpoint_number, endpoint_number - nvl(prev_endpoint,0)  frequency,  endpoint_actual_value "ACTUAL_VALUE"
from    (
select  endpoint_number,  lag(endpoint_number,1) over( order by endpoint_number )   prev_endpoint,  endpoint_value,  endpoint_actual_value
from
user_tab_histograms
where
table_name = 'T2'
and     column_name = 'OBJECT_TYPE'
)
order by   endpoint_number ;

• Nombre de lignes associé aux valeurs populaires : 4427 + 31058 + 37199 + 2537 + 6212 =  81 433
• Pourcentage  de ligne total a dépassé :  (1 – (1/7))*100 soit 85,714 % de  91539 lignes = 78 462

4)  Hybrid
Histogramme de type hybride, dernier apparu, lui aussi avec la version 12c, il combine les caractéristiques des histogrammes de fréquences et des histogrammes basés sur la hauteur.  La première opération est toujours l’ordonnancement des lignes en fonction des valeurs de la colonne. Ensuite on parcours la liste pour remplir nos cellules, le nombre et le pas initial  n de la cellule suivent toujours la règle :
n = nombre de valeurs non nul de la colonne/ nombre de cellules voulues.
Par contre la taille de la cellule va pouvoir varier dynamiquement:  si le moteur ce rend compte que la dernière valeur de la cellule s’étend sur la cellule suivante, il va agrandir la cellule pour englober complètement la valeur, il en profite au passage pour compter et stocker le nombre de répétition de la valeur la plus haute de la cellule.
Ainsi en reprenant notre exemple des histogrammes basés sur la hauteur et notre série de  20 valeurs à ranger dans 5 cellules :
5, 6, 6, 6, 9, 11, 11, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 16, 17, 17
Le pas pour se déplacer de cellule en cellule est de 4 lignes, pour la première cellule la valeur est 5 , pour la suivante , la valeur est 6  , pour la troisième, la valeur est 12 (valeur entre parenthèse) mais la valeur suivante est aussi 12 ,  le moteur agrandit alors la troisième cellule pour qu’elle se termine sur la dernière occurrence de la valeur 12 (celle entre crochet) . la scrutation continue avec le pas de 4 pour la quatrième cellule contenant la valeur 13 (valeur entre parenthèse) , la valeur suivante étant aussi un 13  le moteur agrandit la quatrième cellule jusqu’à la dernière valeur 13 (celle entre crochet) et termine par une dernière cellule contenant la valeur 17.
5, 6, 6, 6, 9, 11, 11, (12) , 12, 12, 12, [12], 13, 13, 13, (13),[13], 16, 17, 17.
Ce qui donne comme information pour notre liste et les valeurs associées aux cellules :

En utilisant cette stratégie, on obtient beaucoup plus d’information que précédemment :

• Les valeurs populaires sont obtenues directement et aucune n’est oubliée via un tri sur le nombre de répétition (repeat_count).
• Pour chaque cellule on détermine le nombre de ligne de l’intervalle en soustrayant le “end_point_number” de la cellule précédente :  la cellule 3 est un intervalle de 12 – 4 , 8 lignes
• La valeur la plus haute de l’intervalle  correspond à  “endpoint_value”  (valeur 12 pour  la cellule 3)
• La cardinalité de la valeur la plus haute de l’intervalle considéré est immédiate via la valeur de “repeat_count”  (le nombre de fois ou apparait la valeur 12 dans la cellule 3 est 5) .

les conditions de déclenchement de cette stratégie de calcul par le moteur sont :

• Le taux d’échantillonnage  est de type “AUTOMATIC”
• Le nombre de valeurs distinctes est supérieur à 254 (ou au nombre de cellules (“bucket”) demandé)
• Les conditions du mode “Top frequency” ne s’applique pas (les valeurs populaires ne représente pas la majorité des lignes)

C’est la fin de la présentation de ces quatre méthodes,  j’espère que c’est maintenant plus clair pour vous avec ces explications et exemples.  Bien sur pour couvrir tous les cas et revoir les avantages des uns par rapport aux autres ou leurs manques il faudrait développer beaucoup plus et s’appuyer sur les lois mathématiques utilisées par Oracle (voir Mr Bernoulli entre autres)   mais ce n’était pas le sujet de cet article qui ce veut être seulement un premier pas dans ce domaine.
Remerciements et références:  Je n’aurais pas pu comprendre aussi bien les mécanismes en jeux sans les articles pertinents de jonhatan Lewis, particulièrement ceux-ci  : http://allthingsoracle.com/histograms-part-1-why/, http://allthingsoracle.com/histograms-pt-2, http://jonathanlewis.wordpress.com/2013/07/30/12c-histograms-pt-2/, http://jonathanlewis.wordpress.com/2013/10/09/12c-histograms-pt-3/  ; Il faut cependant aussi reconnaitre les efforts de l’éditeur dans sa documentation sur le sujet, chapitre 11 de “Oracle Database Tuning Guide” de la version 12c  http://docs.oracle.com/cd/E16655_01/server.121/e15858/tgsql_histo.htm#TGSQL366   et si vous souhaitez compléter votre connaissance du sujet, mes collègues ont déjà travaillé le sujet ici http://arkzoyddev.com/2012/10/29/oracle-database-comprendre-les-histogrammes-en-11gr2/?lang=fr  ou la :  http://arkzoyddev.com/2008/03/25/supprimer-un-histogramme-sur-une-colonne-ou-modifier-des-statistiques-manuellement/?lang=fr