Dans l’article précédent nous avions vu qu’avec un histogramme de type FREQUENCY on avait un bucket alloué pour chaque valeur distincte ce qui permettait au CBO d’estimer une cardinalité juste. Cependant, le nombre de buckets étant limité à 254 il n’est plus possible d’avoir un histogramme FREQUENCY pour les colonnes ayant un nombre de valeurs distinctes supérieur à cette limite. Oracle calcule à la place des histogrammes de type height-balanced (HB).
La colonne C_HB de ma table T1 contenant 829 valeurs distinctes est candidate pour un histogramme height-balanced.
Jetons un œil aux 10 valeurs les plus récurrentes dans la table :
Principe de calcul des histogrammes height-balanced :
La valeur 4 apparait au ENDPOINT_NUMBER de 114 après la valeur 2 qui apparait au endpoint 82. Cette ligne dans la vue USER_TAB_HISTOGRAMS nous permet de déduire 2 choses :
Pour afficher les fréquences de chaque valeur capturée on peut utiliser la requête suivante qui utilise notamment la fonction LAG:
Histogrammes Height-Balanced et cardinalités :
Dans l’article sur les histogrammes FREQUENCY j’avais écrit qu’à partir du moment où l’on avait autant de buckets que de valeurs distinctes, on pouvait considérer toutes les valeurs de l'histogramme comme populaires ce qui permettait au CBO d’estimer une bonne cardinalité. Malheureusement, il n’en va pas de même pour les histogrammes height-balanced car seules les valeurs ayant une fréquence supérieure à 1 sont considérées comme populaires. Les valeurs apparaissant une seule fois ou bien celles n’ayant pas été capturées lors du calcul de statistiques sont donc considérées comme non populaires. De plus, puisqu’il est nécessaire qu’une valeur apparaisse au moins 2 fois comme endpoint_value pour devenir populaire on peut en déduire qu’Oracle n’est capable de capturer au mieux que 127 valeurs populaires.
Voyons ce que donnent les estimations du CBO lorsqu’on requête une valeur populaire :
Regardons enfin ce qu’on obtient lorsqu’on utilise une valeur non populaire et n’ayant pas été capturée par le calcul de statistiques :
Pour ceux que ça intéresse je donne ci-dessous les formules appliquées par le CBO pour calculer les cardinalités selon les cas :
Cas d’une valeur populaire :
BUCKET_SIZE = SAMPLE_SIZE / NUM_BUCKETS
BUCKET_SIZE = 14739/254 = 58.027
Cardinalité estimée = FREQUENCY * BUCKET_SIZE
Cardinalité estimée = 99 * 58.027 = 5744.72 ~= 5745 => correspond bien à ce qu’on voit dans le plan pour la colonne E-Rows
Cas d’une valeur NON populaire (capturée ou pas) :
Cardinalité estimée = NUM_ROWS * NewDensity
NewDensity est une fonction interne à Oracle dont le nom apparait dans la 10053 et qui lui permet de faire une estimation en cas de valeurs non populaires pour les colonnes ayant un histogramme de type height-balanced.
CONCLUSION :
La notion d’histogrammes height-balanced est une notion plus complexe à assimiler que celle des histogrammes FREQUENCY néanmoins voici les points qu'il me semble essentiel de retenir :
Nous verrons dans un prochain article comment, avec la 12c et les histogrammes TOP-frequency et Hybrides, Oracle a tenté d’améliorer ses histogrammes.
La colonne C_HB de ma table T1 contenant 829 valeurs distinctes est candidate pour un histogramme height-balanced.
exec dbms_stats.gather_table_stats(user,'T1', method_opt=>'for columns C_HB size 829'); ERROR at line 1: ORA-20000: Cannot parse for clause: for columns C_HB size 829 ORA-06512: at "SYS.DBMS_STATS", line 24281 ORA-06512: at "SYS.DBMS_STATS", line 24332 ORA-06512: at line 1L’erreur précédente nous montre qu’en 11g, il est inutile de positionner un nombre de buckets égale au nombre de valeurs distinctes lorsque ce dernier est supérieur à 254. Il faut donc calculer les statistiques pour cette colonne avec 254 buckets :
exec dbms_stats.gather_table_stats(user,'T1', method_opt=>'for columns C_HB size 254');
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 ,000748974 0 254 14739 HEIGHT BALANCED
La colonne HISTOGRAM de la vue USER_TAB_COL_STATISTICS nous montre que c’est bel et bien un histogramme height-balanced qui a été calculé.Jetons un œil aux 10 valeurs les plus récurrentes dans la table :
select * from (
SELECT C_HB, count(*) AS frequency, trunc(ratio_to_report(count(*)) OVER ()*100,2) AS percent
FROM t1
GROUP BY C_HB
ORDER BY 3 desc
)
where rownum<=10
;
C_HB FREQUENCY PERCENT
--------- ---------- ----------
999 5710 38,74
0 4601 31,21
4 1853 12,57
5 237 1,6
8 195 1,32
19 169 1,14
1 152 1,03
16 84 ,56
13 70 ,47
6 47 ,31
On s’aperçoit que la valeur 999 qui est la valeur la plus présente apparait 5710 fois, la valeur 0 apparait 4601 fois et la valeur 4 apparait 1853 fois. A elles trois ces valeurs représentent plus de 80% des données.Principe de calcul des histogrammes height-balanced :
Pour calculer l’histogramme sur la colonne C_HB, Oracle commence par trier les valeurs de la colonne C_HB puis il divise ces données triées en buckets de 58 valeurs (num_rows/num_buckets=14739/254=58). Pour chaque bucket Oracle conserve la valeur la plus grande, c’est ce qu’on appelle le ENDPOINT_VALUE. La première valeur triée est la valeur 0 qui apparait 4601 fois. La taille du bucket étant de 58, la valeur 0 correspondra au ENDPOINT_VALUE de 79 buckets (4601/58=79). Ensuite, Oracle arrive à la valeur 1 qui apparait 152 fois dans la table et donc cette valeur apparaitra comme ENDPOINT_VALUE dans 2 buckets (152/58=2.6). En continuant avec ce mécanisme on aura dans notre histogramme 254 valeurs et on comprend qu’en fonction de l'évolution des données dans la table on peut avoir un ENDPOINT_VALUE qui diffère après chaque exécution du calcul de statistiques. Le fameux problème d’instabilité des histogrammes height-balanced vient de là.
Requêtons maintenant la vue USER_TAB_HISTOGRAMS pour la colonne C_HB et observons ce qu'on obtient dans notre histogramme :
La valeur 1 qui apparait au ENDPOINT_NUMBER 81 juste après le 79 a une fréquence de 2 (81-79), en d’autres termes on peut dire que la valeur 1 apparait à deux reprises comme endpoint_value d’un bucket. Requêtons maintenant la vue USER_TAB_HISTOGRAMS pour la colonne C_HB et observons ce qu'on obtient dans notre histogramme :
select ENDPOINT_NUMBER, ENDPOINT_VALUE
from USER_TAB_HISTOGRAMS
where table_name = 'T1' and column_name = 'C_HB'
order by ENDPOINT_NUMBER;
ENDPOINT_NUMBER ENDPOINT_VALUE
--------------- --------------
79 0
81 1
82 2
114 4
118 5
119 6
122 8
123 9
124 12
125 13
127 16
130 19
131 21
132 25
133 32
134 40
135 53
136 70
137 88
138 110
139 138
140 216
141 256
142 370
143 460
144 640
243 999
244 1414
245 2150
246 3333
247 5484
248 8038
249 14660
250 27455
251 64093
252 187520
253 986698
254 63681020
38 rows selected.
Là vous vous demandez peut-être pourquoi nous n’obtenons que 38 lignes dans notre histogramme au lieu de 254 ? Effectivement, bien que la règle consiste à avoir une valeur pour chaque bucket, la colonne ENDPOINT_NUMBER étant une valeur cumulative, Oracle ne conservera que le dernier ENDPOINT_NUMBER lorsque plusieurs ENDPOINT_VALUE se succèdent avec la même valeur. Ainsi, on peut déduire en regardant notre histogramme que la fréquence de la valeur 0 est de 79 car il n’existe pas de ENDPOINT_NUMBER avant ce nombre.La valeur 4 apparait au ENDPOINT_NUMBER de 114 après la valeur 2 qui apparait au endpoint 82. Cette ligne dans la vue USER_TAB_HISTOGRAMS nous permet de déduire 2 choses :
- La valeur 3 n’est pas présente dans l’histogramme (même si la valeur apparait 9 fois dans la table)
- La valeur 4 a une fréquence de 32 (114-82)
Pour afficher les fréquences de chaque valeur capturée on peut utiliser la requête suivante qui utilise notamment la fonction LAG:
select endpoint_value as column_value, endpoint_number as cummulative_frequency, endpoint_number - lag(endpoint_number,1,0) over (order by endpoint_number) as frequency from user_tab_histograms where table_name = 'T1' and column_name = 'C_HB'; COLUMN_VALUE CUMMULATIVE_FREQUENCY FREQUENCY ------------ --------------------- ---------- 0 79 79 1 81 2 2 82 1 4 114 32 5 118 4 6 119 1 8 122 3 9 123 1 12 124 1 13 125 1 16 127 2 19 130 3 21 131 1 25 132 1 32 133 1 40 134 1 53 135 1 70 136 1 88 137 1 110 138 1 138 139 1 216 140 1 256 141 1 370 142 1 460 143 1 640 144 1 999 243 99 1414 244 1 2150 245 1 3333 246 1 5484 247 1 8038 248 1 14660 249 1 27455 250 1 64093 251 1 187520 252 1 986698 253 1 63681020 254 1
Histogrammes Height-Balanced et cardinalités :
Dans l’article sur les histogrammes FREQUENCY j’avais écrit qu’à partir du moment où l’on avait autant de buckets que de valeurs distinctes, on pouvait considérer toutes les valeurs de l'histogramme comme populaires ce qui permettait au CBO d’estimer une bonne cardinalité. Malheureusement, il n’en va pas de même pour les histogrammes height-balanced car seules les valeurs ayant une fréquence supérieure à 1 sont considérées comme populaires. Les valeurs apparaissant une seule fois ou bien celles n’ayant pas été capturées lors du calcul de statistiques sont donc considérées comme non populaires. De plus, puisqu’il est nécessaire qu’une valeur apparaisse au moins 2 fois comme endpoint_value pour devenir populaire on peut en déduire qu’Oracle n’est capable de capturer au mieux que 127 valeurs populaires.
Voyons ce que donnent les estimations du CBO lorsqu’on requête une valeur populaire :
-- popular value alter system flush shared_pool; 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 | 415 | |* 1 | TABLE ACCESS FULL| T1 | 1 | 5745 | 5710 |00:00:00.01 | 415 | ------------------------------------------------------------------------------------On constate que la cardinalité estimée est très proche de la réalité et que le CBO a choisi de faire un Full Table Scan en ne générant que 415 logical reads. Pour rappel, voici le plan obtenu lorsque le CBO ne disposait d’aucun histogramme pour la colonne C_HB. L’optimiseur avait sous-estimé la cardinalité retournée et avait opté pour un accès indexé générant 806 logical I/Os :
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 | ------------------------------------------------------------------------------------------------Voyons maintenant ce que donnent les estimations du CBO pour une valeur non populaire mais présente dans l’histogramme:
-- Non popular presente dans l'histogramme select * from T1 where C_HB=256; ------------------------------------------------------------------------------------------------ | Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers | ------------------------------------------------------------------------------------------------ | 0 | SELECT STATEMENT | | 1 | | 24 |00:00:00.01 | 17 | | 1 | TABLE ACCESS BY INDEX ROWID| T1 | 1 | 2 | 24 |00:00:00.01 | 17 | |* 2 | INDEX RANGE SCAN | IDX_HB | 1 | 2 | 24 |00:00:00.01 | 4 | ------------------------------------------------------------------------------------------------Cette fois à l’inverse de la valeur popular le CBO se trompe dans son estimation : 2 lignes estimées contre 24 réellement.
Regardons enfin ce qu’on obtient lorsqu’on utilise une valeur non populaire et n’ayant pas été capturée par le calcul de statistiques :
-- Non popular non capturée select * from T1 where C_HB=3; ------------------------------------------------------------------------------------------------ | Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers | ------------------------------------------------------------------------------------------------ | 0 | SELECT STATEMENT | | 1 | | 9 |00:00:00.01 | 7 | | 1 | TABLE ACCESS BY INDEX ROWID| T1 | 1 | 2 | 9 |00:00:00.01 | 7 | |* 2 | INDEX RANGE SCAN | IDX_HB | 1 | 2 | 9 |00:00:00.01 | 3 | ------------------------------------------------------------------------------------------------Là encore le CBO ne peut estimer une cardinalité juste et c’est là où le bât blesse avec les histogrammes height-balanced : le CBO n’est capable d’estimer le bon nombre de lignes retournées si et seulement si la valeur requêtée est une valeur populaire, or comme nous l’avons dit précédemment Oracle n’est capable de capturer au mieux que 127 valeurs populaires. Imaginons une table contenant plusieurs millions de valeurs distinctes avec un histogramme height-balanced, le CBO ne sera capable d’estimer une cardinalité fiable que lorsqu’une valeur populaire sera requêtée (c’est-à-dire 0.001% des valeurs dans ce cas). Si cette table faisait l’objet d’une requête très complexe avec beaucoup de jointures le plan d’exécution choisi par le CBO pourrait s’avérer catastrophique.
Cas d’une valeur populaire :
BUCKET_SIZE = SAMPLE_SIZE / NUM_BUCKETS
BUCKET_SIZE = 14739/254 = 58.027
Cardinalité estimée = FREQUENCY * BUCKET_SIZE
Cardinalité estimée = 99 * 58.027 = 5744.72 ~= 5745 => correspond bien à ce qu’on voit dans le plan pour la colonne E-Rows
Cas d’une valeur NON populaire (capturée ou pas) :
Cardinalité estimée = NUM_ROWS * NewDensity
NewDensity est une fonction interne à Oracle dont le nom apparait dans la 10053 et qui lui permet de faire une estimation en cas de valeurs non populaires pour les colonnes ayant un histogramme de type height-balanced.
CONCLUSION :
La notion d’histogrammes height-balanced est une notion plus complexe à assimiler que celle des histogrammes FREQUENCY néanmoins voici les points qu'il me semble essentiel de retenir :
- Oracle est dans l’incapacité de calculer des histogrammes de type frequency et calcule donc des histogrammes height-balanced dès lors que le nombre de buckets est inférieur au nombre de valeurs distinctes ou dès lors que le nombre de valeurs distinctes est supérieur à 254 (car le nombre de buckets est limité à 254).
- Dans les histogrammes height-balanced la colonne ENDPOINT_NUMBER correspond à l’id du bucket et la colonne ENDPOINT_VALUE correspond à la plus grande valeur du bucket.
- Lorsque le ENDPOINT_VALUE est identique sur plusieurs buckets, Oracle ne stocke que le dernier bucket.
- Oracle n’est capable de capturer au mieux que 127 valeurs populaires
- Oracle est capable d’estimer une bonne cardinalité uniquement pour les valeurs populaires
- Puisque seule la plus grande valeur de chaque bucket est prise en compte une valeur peut devenir populaire un jour puis non populaire un autre jour en fonction du fait qu’elle ait été capturée par le processus de calcul de statistiques ou pas. C’est ce qui rend les histogrammes HB très versatiles et qui en font une des premières sources d’instabilité dans les plans d’exécution.
Nous verrons dans un prochain article comment, avec la 12c et les histogrammes TOP-frequency et Hybrides, Oracle a tenté d’améliorer ses histogrammes.
