viernes, 4 de diciembre de 2009

Una introducción a los histogramas. Para que se usan y como se interpretan

Si alguna vez se pusieron a buscar información sobre que son, como funcionan y para que sirven realmente los histogramas en Oracle se habrán percatado que no existe demasiada data al respecto. La mayoria de la información es solo de referencia y no se explica claramente la verdadera esencia. El tema es bastante extenso, en esta primera parte, mi idea es introducir los conceptos principales, como se guarda la información de histogramas en el catálogo y como se interpreta dicho contenido. En futuras notas voy a mostrarles mas detalle de como se calcula la cardinalidad y el costo de los planes en base a la información estadística y de histogramas y tambien en que casos no sirven.

Oracle utiliza los histogramas para mejorar los calculos de cardinalidad y selectividad cuando la distribución de los datos no es uniforme. Hay que pensar a los histogramas como una "dibujo" de los datos que representa la distribución del contenido en las columnas. Existen dos tipos de histogramas: "Frecuency Histograms" y "Height Balanced Histrograms". Los primeros se usan cuando los valores distintos de la columna son pocos, y los segundos cuando la columna tiene gran cantidad de valores diferentes.

En los histogramas por frecuencia cada valor de la columna se corresponde con una entrada del histograma. Cada entrada contiene en número de concurrencia para un valor. En los histogramas balanceados la columna es dividida en buckets (barras), cada barra tiene el mismo número de filas y cada valor puede ser representado por uno o mas buckets, según su popularidad (cantidad de ocurrencias).

La principal tarea de los histogramas es ayudar a obtener la cardinalidad correcta, como ya comenté en otras notas, el calculo de la cardinalidad es fundamental para que Oracle arme el plan mas adecuado, lo que implica elegir el método y el orden de los joins y la elección de los indices correctos, y asi garantizar la mejor performance posible.

La forma de almacenamiento sigue conceptos estadísticos como percentiles y cuartiles y los valores se agrupan en buckets (si se grafica un histogramas, los buckets son como las barras en un gráfico de barras común y corriente).

Ahora vamos a hacer un par de pruebas y asi tratar de entender un poco mas el concepto detrás de los histogramas.

Primero voy a crear una tabla que tendrá 11110 filas, con cuatro valores posibles (1,2,3 y 4) de forma tal de que cada valor tenga una cantidad redonda de registros (potencia de 10).



rop@DESA10G> create table t
2 as select case when (rownum between 1 and 10) then 1
3 when (rownum between 11 and 110) then 2
4 when (rownum between 111 and 1110) then 3
5 when (rownum between 1111 and 11110) then 4
6 end x
7 from dual
8 connect by rownum <= 11110;

Tabla creada.

rop@DESA10G> select x,count(1)
2 from t
3 group by x;

X COUNT(1)
---------- ----------
1 10
2 100
3 1000
4 10000


La tabla T nos quedó con la distribución que se muestra arriba. Voy a recolectar
estadísticas y ver en la tabla de catálogo USER_TAB_COL_STATISTICS los datos estadisticos de la columna X:


rop@DESA10G> begin
2 dbms_stats.gather_table_stats(ownname => user,tabname => 'T');
3 end;
4 /

Procedimiento PL/SQL terminado correctamente.

rop@DESA10G> exec print_table('select * from user_tab_col_statistics where table_name = ''T''');
TABLE_NAME : T
COLUMN_NAME : X
NUM_DISTINCT : 4
LOW_VALUE : C102
HIGH_VALUE : C105
DENSITY : .25
NUM_NULLS : 0
NUM_BUCKETS : 1

LAST_ANALYZED : 02-dic-2009 15:28:59
SAMPLE_SIZE : 11110
GLOBAL_STATS : YES
USER_STATS : NO
AVG_COL_LEN : 3
HISTOGRAM : NONE
-----------------

Procedimiento PL/SQL terminado correctamente.


De los datos mostrados arriba vemos que Oracle detectó 4 valores distintos, que no hay valores nulos, que la densidad es 0.25 (1/"cant. de valores distinto"=1/4),que hay un solo bucket y que no hay histogramas (NONE). Ya que en la recolección no explicitamos el parámetro method_opt, que da directivas de como armar los histogramas, se uso el default que es: "for all columns size auto". La unica información de distribución es la siguiente:


rop@DESA10G> select * from user_tab_histograms where table_name = 'T';

TABLE_NAME COLUMN_NAM ENDPOINT_NUMBER ENDPOINT_VALUE ENDPOINT_A
---------- ---------- --------------- -------------- ----------
T X 0 1
T X 1 4


Recolectando estadísticas diciendole a Oracle que use 4 buckets para representar la distribución obtenemos:

rop@DESA10G> begin
2 dbms_stats.gather_table_stats(ownname => user,
3 tabname => 'T',
4 method_opt=>'for all columns size 4');
5 end;
6 /

Procedimiento PL/SQL terminado correctamente.

rop@DESA10G> exec print_table('select * from user_tab_col_statistics where table_name = ''T''');
TABLE_NAME : T
COLUMN_NAME : X
NUM_DISTINCT : 4
LOW_VALUE : C102
HIGH_VALUE : C105
DENSITY : .000045004500450045
NUM_NULLS : 0
NUM_BUCKETS : 4
LAST_ANALYZED : 02-dic-2009 16:12:21
SAMPLE_SIZE : 11110
GLOBAL_STATS : YES
USER_STATS : NO
AVG_COL_LEN : 3
HISTOGRAM : FREQUENCY
-----------------

Procedimiento PL/SQL terminado correctamente.

rop@DESA10G> select * from user_tab_histograms where table_name = 'T';

TABLE_NAME COLUMN_NAM ENDPOINT_NUMBER ENDPOINT_VALUE ENDPOINT_A
---------- ---------- --------------- -------------- ----------
T X 10 1
T X 110 2
T X 1110 3
T X 11110 4
rop@DESA10G>

Notemos que ahora se creo un "Frecuency Histrogram", que la densidad es mucho menor y viendo la tabla USER_TAB_HISTOGRAMS ahora se representa exactamente la distribución. Para interpretar esa tabla pensemos que la columna ENDPOINT_VALUE es cada valor posible de la columna y el ENDPOINT_NUMBER es la cantidad de registros iguales. Para 1 tenemos 10, para 2 tenemos 110-10=100, para 3 tenemos 1110-110=1000 y asi siguiendo.

Ahora voy a armar una distribución distinta, con muchos valores distintos para mostrarles el otro tipo de histograma:

rop@DESA10G> drop table t;

Tabla borrada.

rop@DESA10G> ed
Escrito file afiedt.buf

1 create table t
2 as select rownum x
3 from dual
4* connect by rownum <= 11110
rop@DESA10G> /

Tabla creada.

rop@DESA10G> update t set x = 1 where rownum <= 5000;

5000 filas actualizadas.

rop@DESA10G> update t set x = 2 where rownum <= 3000 and x != 1;

3000 filas actualizadas.

rop@DESA10G> create index t_idx on t(x);

Índice creado.


Se creó una tabla con la misma cantidad de filas que el ejemplo anterior pero ahora tenemos una distribución muy diferente. Para X=1 tenemos 5000 valores, para x=2 hay 3000 filas y para las demas solo 1 ocurrencia. Como ahora tengo muchos valores distintos si recolecto sin especificar me va a crear el histograma. Para evitar que lo cree en el parametro method_opt le especifiqué "for columns size 1" para que no asocie ningun histograma.


rop@DESA10G> begin
2 dbms_stats.gather_table_stats(ownname => user,
3 tabname => 'T',
4 cascade => true,
5 method_opt => 'for columns size 1');
6 end;
7 /

Procedimiento PL/SQL terminado correctamente.

rop@DESA10G> exec print_table('select * from user_tab_col_statistics where table_name = ''T''');

Procedimiento PL/SQL terminado correctamente.

Como se ve, consultando la tabla USER_TAB_COL_STATISTICS no obtenemos ningua fila, es decir no tenemos información de histogramas.
Recordemos que para X=1 tenemos 5000 valores, es decir casi la mitad del total de filas, por lo tanto si filtramos en el predicado por dicho valor es de esperar que el optimizador use un full_scan, no?, veamos que pasa:


rop@DESA10G> explain plan for select count(1) from t where x = 1;

Explicado.

rop@DESA10G> select * from table(dbms_xplan.display);

PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------
Plan hash value: 3482591947

---------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 3 | 1 (0)| 00:00:01 |
| 1 | SORT AGGREGATE | | 1 | 3 | | |
|* 2 | INDEX RANGE SCAN| T_IDX | 111 | 333 | 1 (0)| 00:00:01 |
---------------------------------------------------------------------------

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

2 - access("X"=1)

14 filas seleccionadas.

Notar que el optimizador estimó (columna ROWS) 111 filas, lo cual dista mucho de la realidad, recordemos que tenemos 5000 filas que cumplen con X=1. Si recolectamos usando el método default:

rop@DESA10G> ed
Escrito file afiedt.buf

1 begin
2 dbms_stats.gather_table_stats(ownname => user,
3 tabname => 'T',
4 cascade => true);
5* end;
rop@DESA10G> /

Procedimiento PL/SQL terminado correctamente.

rop@DESA10G> exec print_table('select * from user_tab_col_statistics where table_name = ''T''');
TABLE_NAME : T
COLUMN_NAME : X
NUM_DISTINCT : 3112
LOW_VALUE : C102
HIGH_VALUE : C3020C0B
DENSITY : .00009000900090009
NUM_NULLS : 0
NUM_BUCKETS : 254
LAST_ANALYZED : 04-dic-2009 10:02:53
SAMPLE_SIZE : 11110
GLOBAL_STATS : YES
USER_STATS : NO
AVG_COL_LEN : 4
HISTOGRAM : HEIGHT BALANCED
-----------------

Procedimiento PL/SQL terminado correctamente.


El tipo de histograma ahora es: "HEIGHT BALANCED", la cantidad de filas distintas es 3312 y el nro de buckets es de 254 (el máximo posible)

La representación de los datos en la tabla T ahora es la siguiente:

rop@DESA10G> select * from user_tab_histograms where table_name = 'T';


TABLE_NAME COLUMN_NAM ENDPOINT_NUMBER ENDPOINT_VALUE ENDPOINT
------------------------------ ---------- --------------- -------------- --------
T X 113 1
T X 181 2

T X 182 8008
T X 183 8052
T X 184 8096
T X 185 8140
T X 186 8184
T X 187 8228
T X 188 8272
T X 189 8315
T X 190 8358
T X 191 8401
T X 192 8444
T X 193 8487
T X 194 8530
T X 195 8573
T X 196 8616
T X 197 8659
T X 198 8702
T X 199 8745
T X 200 8788
T X 201 8831
T X 202 8874
T X 203 8917
T X 204 8960
T X 205 9003
T X 206 9046
T X 207 9089
T X 208 9132
T X 209 9175
T X 210 9218
T X 211 9261
T X 212 9304
T X 213 9347
T X 214 9390
T X 215 9433
T X 216 9476
T X 217 9519
T X 218 9562
T X 219 9605
T X 220 9648
T X 221 9691
T X 222 9734
T X 223 9777
T X 224 9820
T X 225 9863
T X 226 9906
T X 227 9949
T X 228 9992
T X 229 10035
T X 230 10078
T X 231 10121
T X 232 10164
T X 233 10207
T X 234 10250
T X 235 10293
T X 236 10336
T X 237 10379
T X 238 10422
T X 239 10465
T X 240 10508
T X 241 10551
T X 242 10594
T X 243 10637
T X 244 10680
T X 245 10723
T X 246 10766
T X 247 10809
T X 248 10852
T X 249 10895
T X 250 10938
T X 251 10981
T X 252 11024
T X 253 11067
T X 254 11110

75 filas seleccionadas.

La tabla de arriba se lee diferente a la que info que guardaba el histograma del tipo "FRECUENCY" ya que hay muchos valores para representar Oracle uso el tipo de histograma "HEIGHT BALANCED". Analizando el histograma vemos que la columna ENDPOINT_VALUE tiene 254 valores (buckets). La primera fila:

TABLE_NAME COLUMN_NAM ENDPOINT_NUMBER ENDPOINT_VALUE ENDPOINT
------------------------------ ---------- --------------- -------------- --------
T X 113 1

Tiene 113 buckets asignados. De donde sale es valor?. Pensemeos que tenemos 11110 filas, de las cuales tenemos 5000 con valor 1. Hagamos un poco de aritmetica:

Si tenemos 11100 filas representadas con 254 buckets y para el valor 1 se asignaron 113 tenemos:

rop@DESA10G> select (11110/254)*113 from dual;

(11110/254)*113
---------------
4942.6378

Cercano a 5000, no?, veamos que pasa para el valor 2:

TABLE_NAME COLUMN_NAM ENDPOINT_NUMBER ENDPOINT_VALUE ENDPOINT
------------------------------ ---------- --------------- -------------- --------
T X 113 1
T X 181 2

Para sacar la cantidad de buckets del ENDPOINT_VALUE tenemos que hacer:

rop@DESA10G> select (11110/254)*(181-113) from dual;

(11110/254)*(181-113)
---------------------
2974.33071

Como se ve esta muy cercano a 3000 que es la cantidad real del filas del tipo 2.
La diferencia se da por lo siguiente: Ya que tenemos 11110 filas representadas por 254 barras a buckets entonces tenemos: 11110/254= 43.74 filas por bucket. Los dos valores obtenidos arriba para X=1 y X=2 no son exactos porque se calcula discretizando por bucket.

Una vez obtenido el histograma veamos el plan que se obtiene para la consulta:

rop@DESA10G> explain plan for select count(1) from t where x = 1;

Explicado.

rop@DESA10G> select * from table(dbms_xplan.display);

PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------
Plan hash value: 1842905362

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

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

2 - filter("X"=1)

14 filas seleccionadas.

Esta vez el optimizador eligió ir por un FULL_SCAN que es el mejor plan ya que tiene que recorrer casi la mitad de la tabla.

Si buscamos un valor con una sola ocurrencia:

rop@DESA10G> explain plan for select count(1) from t where x = 999999;

Explicado.

rop@DESA10G> select * from table(dbms_xplan.display);

PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------
Plan hash value: 3482591947

---------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
---------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | 3 | 1 (0)| 00:00:01 |
| 1 | SORT AGGREGATE | | 1 | 3 | | |
|* 2 | INDEX RANGE SCAN| T_IDX | 1 | 3 | 1 (0)| 00:00:01 |
---------------------------------------------------------------------------

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

2 - access("X"=999999)

14 filas seleccionadas.

rop@DESA10G>

Se observa que se usa el indice en el plan, que obviamente es el mejor acceso posible.
Por último, es importante prestar atención a la cardinalidad (columna ROWS del plan) para el caso de X=1 el calculo fue: 4943 que es el valor redondeado que obtuvimos mas arriba haciendo: (11110/254)*113. De esto podemos confirmar que el Optimizador consultó el histograma para obtener la cardinalidad mas cercana a la real y por lo tanto generó el plan mas adecuado.

5 comentarios:

  1. Qué buen artículo Pablo, es realmente muy claro.

    Estuve probando los ejemplos que ofrecés y de paso revisé como están los histogramas de las tablas de algunas bases 11g del trabajo, y resulta que encuentro que las tablas tienen algunas columnas con histogramas y otras que no, entonces aquí viene la pregunta:

    ¿Es posible que el paquete DBMS_STATS.GATHER_SCHEMA_STATS('usuario'); realice por sí solo los histogramas en las columnas que cree conveniente?

    Yo hice la prueba creando la primer tabla del ejemplo y no me creó los histogramas, pero me surge la duda si dicho paquete tiene esa capacidad.

    Muchas gracias.

    ResponderEliminar
  2. Los histogramas se crearan si la distribución no es uniforme, si es uniforme alcanza con la densidad. El parametro method_opt es el que determina como se obtendran los histogramas, el valor default es: for all columns size auto.

    ResponderEliminar