viernes, 14 de septiembre de 2007

Las columnas más selectivas deberían ir al comienzo del índice?

El mito dice lo siguiente: Cuando creamos un índice, las columnas más selectivas (las columnas con la mayor cantidad de valores distintos) deberían ir al comienzo del índice.
Nuestro sentido común nos dice que es lógico crear los índices de esa forma; pero lo que no nos dice nuestro sentido común, es si en realidad éste mito es verdadero o falso.

La mejor manera de comprobar la veracidad de éste mito, es realizando un ejemplo:

SQL_9iR2> CREATE TABLE test
2 (nombre, edad, sexo)
3 AS
4 SELECT 'nom_'||level,
5 to_number(round(dbms_random.value(1,5))||round(dbms_random.value(1,5))),
6 decode(mod(level,2),1,'M','F')
7 FROM dual
8 CONNECT BY level <= 10000 ;

Table created.

Veamos la cantidad de valores distintos de cada columna:

SQL_9iR2> SELECT COUNT(DISTINCT nombre) nombre,
2 COUNT(DISTINCT edad) edad,
3 COUNT(DISTINCT sexo) sexo
4 FROM test ;

NOMBRE EDAD SEXO
---------- ---------- ----------
10000 25 2

1 row selected.

Con los valores que estamos viendo, nuestro sentido común nos diría que si tenemos que crear un índice sobre esas 3 columnas, las coloquemos en orden de selectividad (de las columnas con mayor cantidad de valores distintos a las de menor cantidad).

SQL_9iR2> CREATE INDEX test_selectivo_idx ON test(nombre,edad,sexo) ;

Index created.

El índice "test_selectivo_idx" que acabamos de crear es el que la gente está más acostumbrada a crear. Colocando las columnas con mayor cantidad de valores distintos en la cabecera del índice hasta llegar a la columna con menor cantidad de valores distintos.
Pero no sólo vamos a crear ese índice. También vamos a crear otro índice invirtiendo el orden de las columnas del índice anterior:

SQL_9iR2> CREATE INDEX test_no_selectivo_idx ON test(sexo,edad,nombre) ;

Index created.

Ahora vamos a analizar la estructura de los 2 índices para ver si el espacio que ocupa cada uno es el mismo:

SQL_9iR2> ANALYZE INDEX test_selectivo_idx VALIDATE STRUCTURE ;

Index analyzed.

SQL_9iR2> exec print_table('SELECT * FROM index_stats') ;
-----------------
HEIGHT : 2
BLOCKS : 40
NAME : TEST_SELECTIVO_IDX
PARTITION_NAME :
LF_ROWS : 10000
LF_BLKS : 35
LF_ROWS_LEN : 248894
LF_BLK_LEN : 7996
BR_ROWS : 34
BR_BLKS : 1
BR_ROWS_LEN : 543
BR_BLK_LEN : 8028
DEL_LF_ROWS : 0
DEL_LF_ROWS_LEN : 0
DISTINCT_KEYS : 10000
MOST_REPEATED_KEY : 1
BTREE_SPACE : 287888
USED_SPACE : 249437
PCT_USED : 87
ROWS_PER_KEY : 1
BLKS_GETS_PER_ACCESS : 3
PRE_ROWS : 0
PRE_ROWS_LEN : 0
OPT_CMPR_COUNT : 0
OPT_CMPR_PCTSAVE : 0
-----------------

PL/SQL procedure successfully completed.

SQL_9iR2> ANALYZE INDEX test_no_selectivo_idx VALIDATE STRUCTURE ;

Index analyzed.

SQL_9iR2> exec print_table('SELECT * FROM index_stats') ;
-----------------
HEIGHT : 2
BLOCKS : 40
NAME : TEST_NO_SELECTIVO_IDX
PARTITION_NAME :
LF_ROWS : 10000
LF_BLKS : 35
LF_ROWS_LEN : 248894
LF_BLK_LEN : 7996
BR_ROWS : 34
BR_BLKS : 1
BR_ROWS_LEN : 673
BR_BLK_LEN : 8028
DEL_LF_ROWS : 0
DEL_LF_ROWS_LEN : 0
DISTINCT_KEYS : 10000
MOST_REPEATED_KEY : 1
BTREE_SPACE : 287888
USED_SPACE : 249567
PCT_USED : 87
ROWS_PER_KEY : 1
BLKS_GETS_PER_ACCESS : 3
PRE_ROWS : 0
PRE_ROWS_LEN : 0
OPT_CMPR_COUNT : 2
OPT_CMPR_PCTSAVE : 19
-----------------

PL/SQL procedure successfully completed.

Vemos que los índices usan la misma cantidad de espacio (hay alguna diferencia mínima en bytes, pero en general no hay diferencia en cuanto al espacio que ocupan). Por otro lado, el orden en el cual se encuentran las columnas en un índice, pueden ser o no, mejor candidatos para usar "Index Key Compression" (observando el valor OPT_CMPR_PCTSAVE de la vista index_stats).

Lo que vamos a realizar ahora es un TKPROF ejecutando las 2 consultas dentro de un bloque PL/SQL para ver la diferencia en cuanto a la performance de utilizar cada uno de los índices:

SQL_9iR2> EXEC dbms_stats.GATHER_TABLE_STATS(USER,'TEST',cascade => true) ;

PL/SQL procedure successfully completed.


SQL_9iR2> ALTER SESSION SET SQL_TRACE = TRUE ;

Session altered.

SQL_9iR2> DECLARE
2 l_count PLS_INTEGER ;
3 BEGIN
4 FOR i IN ( SELECT * FROM test ) LOOP
5
6 SELECT /*+ INDEX(test test_selectivo_idx) */ COUNT(*)
7 INTO l_count
8 FROM test
9 WHERE nombre = i.nombre
10 AND edad = i.edad
11 AND sexo = i.sexo ;
12
13 SELECT /*+ INDEX(test test_no_selectivo_idx) */ COUNT(*)
14 INTO l_count
15 FROM test
16 WHERE nombre = i.nombre
17 AND edad = i.edad
18 AND sexo = i.sexo ;
19
20 END LOOP ;
21 END ;
22 /

PL/SQL procedure successfully completed.

Elapsed: 00:00:02.08

SQL_9iR2> ALTER SESSION SET SQL_TRACE = FALSE ;

Session altered.

Veamos el reporte del TKPROF que generamos:

SELECT /*+ INDEX(test test_selectivo_idx) */ COUNT(*)
FROM
TEST WHERE NOMBRE = :B3 AND EDAD = :B2 AND SEXO = :B1

call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.00 0.00 0 0 0 0
Execute 10000 0.17 0.12 0 0 0 0
Fetch 10000 0.13 0.09 0 20034 0 10000
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 20001 0.30 0.22 0 20034 0 10000

Misses in library cache during parse: 1
Optimizer goal: CHOOSE
Parsing user id: 137 (recursive depth: 1)

Rows Row Source Operation
------- ---------------------------------------------------
10000 SORT AGGREGATE
10000 INDEX RANGE SCAN TEST_SELECTIVO_IDX (object id 82961)

SELECT /*+ INDEX(test test_no_selectivo_idx) */ COUNT(*)
FROM
TEST WHERE NOMBRE = :B3 AND EDAD = :B2 AND SEXO = :B1

call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.00 0.00 0 0 0 0
Execute 10000 0.19 0.12 0 0 0 0
Fetch 10000 0.12 0.09 0 20034 0 10000
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 20001 0.31 0.21 0 20034 0 10000

Misses in library cache during parse: 1
Optimizer goal: CHOOSE
Parsing user id: 137 (recursive depth: 1)

Rows Row Source Operation
------- ---------------------------------------------------
10000 SORT AGGREGATE
10000 INDEX RANGE SCAN TEST_NO_SELECTIVO_IDX (object id 82962)

Como podemos ver en el reporte, leen exactamente la misma cantidad de bloques de datos y se ejecutan aproximadamente en el mismo tiempo de CPU y elapsed. En conclusión, los 2 índices son exactamente iguales.

Este ejemplo nos sirve como prueba de que el mito no es cierto. No hay diferencias en cuanto a performance en colocar las columnas menos selectivas en la cabecera del índice o las más selectivas.

La realidad es que tenemos que decidir en qué orden colocar las columnas en el índice en base a cómo vamos a acceder a esas columnas en nuestras consultas. Si tenemos el índice compuesto por (sexo,edad,nombre) y accedemos sólo por la columna sexo, no tiene sentido crear un índice compuesto B*Tree y quizás nos convendría crear un índice Bitmap sólo por la columna sexo.

Por ejemplo, si tenemos estas 2 consultas ...

SELECT d FROM test WHERE a = :a AND b = :b ;

SELECT d FROM test WHERE b = :b ;

... lo más razonable es crear un índice en el siguiente orden: (b,a). De ésta manera, ese índice puede ser usado en las 2 consultas.

4 comentarios:

Hector Gabriel Ulloa Ligarius dijo...

Hola Leonardo...

Muy interesante tú post, pero podrías incluir el comentario de que si el ingreso a una tabla se hace por la columna menos selectiva, ese índice no debiese ser de B*Tree sino que debiese ser de Bitmap.

Cómo bien tú sabes , aunque tengas el índice (sexo , edad , nombre) y la consulta sólo ingresa por sexo , ese índice estará desbalanceado, será un índice "demasiado plano" , por ende no debiese ser un B*Tree , sino, que debiese ser un índice de Bitmap

Atte
Hector Gabriel Ulloa Ligarius
http://ligarius.wordpress.com

Leonardo Horikian dijo...

Hola Héctor, si tenemos el índice (sexo , edad , nombre) y se ingresa sólo por sexo, se debería crear un índice Bitmap por sexo solamente. El post habla sobre el orden de las columnas en índices compuestos. En caso de que tengamos el índice compuesto por (sexo , edad , nombre) y se ingresa sólo por sexo, no tiene sentido el índice que se creó ya que, como bien dije en el post, debemos crear los índices en base a cómo se los accede y no en base a la selectividad de las columnas.

Anónimo dijo...

Buen post. Sin embargo hay que tener mucho cuidado a la hora de recomendar bitmap. Si se trata de select bien pero, ¿y si sobre esa tabla o tablas se realizan modificaciones/inserciones masivamente?. A lo mejor se nota mejora en las select pero los bloqueos indirectos por temas de bitmap que se van a generar en las otras operaciones pueden penalizar demasiado.

Un saludo.

Leonardo Horikian dijo...

Si, la creación de bitmaps debe realizarse con mucho cuidado ya que especialmente las modificaciones/inserciones concurrentes pueden afectar en gran medida la performance ya que una modificación en un índice bitmap requiere involucrar loqueos y realiza mucho más trabajo en el sistema que en un índice b*tree. Esto hace que comiencen a aparecer muchos loqueos y por consiguiente, deadlocks.
Generalmente, los bitmap se utilizan en data warehouses donde no suele existir modificaciones/inserciones concurrentes. El costo de mantenimiento de los índices bitmap es enorme.

Saludos