Índice de mapa de bits vs. índice de árbol B: Cuándo usar cuál?

Por Vivek Sharma
Publicado en Diciembre 2014

Entender bien cómo usar cada índice puede influir mucho en el rendimiento.

Suele pensarse que los índices de mapas de bits son los más adecuados para columnas que pueden contener pocos valores distintos, como GENDER [género], MARITAL_STATUS [estado civil] y RELATION [relación]. Sin embargo, esa premisa no es del todo exacta. En realidad, siempre se recomienda usar índices de mapas de bits para sistemas en los que los datos no son actualizados por muchos sistemas simultáneos frecuentemente. De hecho, como demostraré aquí, usar un índice de mapa de bits asociado a una columna con 100% de valores únicos (que podrían usarse como clave principal) es un recurso tan eficiente como usar un índice de árbol B.
En este artículo, ofreceré algunos ejemplos, junto con decisiones del optimizador, comunes a ambos tipos de índices ya sea que se apliquen a columnas de baja cardinalidad o bien a columnas de alta cardinalidad. Esos ejemplos ayudarán a los administradores de bases de datos a entender que el uso de los índices de mapas de bits en realidad no depende de la cardinalidad, sino de la aplicación.

Comparación de los índices
Usar un índice de mapa de bits asociado a una columna única plantea varias desventajas, entre ellas la necesidad de espacio suficiente (y Oracle no recomienda ese uso). No obstante, el tamaño del índice de mapa de bits depende de la cardinalidad de la columna respecto de la cual se lo crea así como de la distribución de los datos. En consecuencia, un índice de mapa de bits para la columna GENDER será más pequeño que un índice de árbol B para la misma columna. Por su parte, un índice de mapa de bits para EMPNO [N° de empleado] (que podría usarse como clave principal) será mucho más grande que un índice de árbol B para esa columna. Pero como son menos los usuarios que acceden a sistemas de apoyo para la toma de decisiones (DSS) que los que accederían a sistemas de procesamiento de transacciones (OLTP), los recursos no son un problema para estas aplicaciones.
Para ilustrar lo anterior, creé dos tablas TEST_NORMAL [prueba normal] y TEST_RANDOM [prueba aleatoria]. Inserté un millón de filas en la tabla TEST_NORMALcon un bloque PL/SQL y, a continuación, inserté las filas que siguen en la tabla TEST_RANDOM en orden aleatorio:

Create  table test_normal (empno number(10), ename varchar2(30), sal number(10));
   
Begin
 For i in  1..1000000
 Loop
 Insert into test_normal 
 values(i, dbms_random.string('U',30), dbms_random.value(1000,7000));
 If mod(i, 10000) = 0 then
 Commit;
 End if;
 End loop;
 End;
 /
   
Create  table test_random 
as 
select  /*+ append */ * from test_normal order by dbms_random.random;

SQL>  select count(*) "Total Rows" from test_normal;

Total  Rows
----------
1000000

Elapsed:  00:00:01.09

SQL>  select count(distinct empno) "Distinct Values" from test_normal;

Distinct  Values
---------------
1000000

Elapsed:  00:00:06.09

SQL>  select count(*) "Total Rows" from test_random;

Total Rows
----------
1000000

Elapsed:  00:00:03.05

SQL>  select count(distinct empno) "Distinct Values" from test_random;

Distinct Values
---------------
1000000

Elapsed: 00:00:12.07
   

Nótese que la tabla TEST_NORMAL está organizada mientras que la tabla TEST_RANDOM fue creada de manera aleatoria, por lo que contiene datos desorganizados. En la tabla anterior, la columna EMPNO incluye valores 100% distintos entre sí, y sería adecuado usarla como clave principal. Si se define esa columna como clave principal, se creará un índice de árbol B y no uno de mapa de bits porque Oracle no admite índices de mapas de bits con claves principales.

Para analizar el comportamiento de los índices, realizaremos lo siguiente:

  1. En TEST_NORMAL:
    1. Crear un índice de mapa de bits a partir de la columna EMPNO y ejecutar consultas con predicados de igualdad.
    2. Crear un índice de árbol B a partir de la columna EMPNO, ejecutar consultas con predicados de igualdad, y comparar las E/S lógicas y físicas que emplearon las consultas para obtener los resultados correspondientes a los diferentes conjuntos de valores.
  2. En TEST_RANDOM:
    1. Ídem paso 1A.
    2. Ídem paso 1B.
  3. En TEST_NORMAL:
    1. Ídem paso 1A, a excepción de que las consultas se ejecutan dentro un rango de predicados.
    2. Ídem paso 1B, a excepción de que las consultas se ejecutan dentro un rango de predicados. Comparar las estadísticas.
  4. En TEST_RANDOM:
    1. Ídem paso 3A.
    2. Ídem paso 3B.
  5. En TEST_NORMAL:
    1. Crear un índice de mapa de bits a partir de la columna SAL y ejecutar algunas consultas con predicados de igualdad y otras con predicados de rango.
    2. Crear un índice de árbol B a partir de la columna SAL y ejecutar algunas consultas con predicados de igualdad y otras con predicados de rango (emplear el mismo conjunto de valores que en el paso 5A). Comparar las E/S que emplearon las consultas para obtener los resultados.
  6. Agregar una columna GENDER a ambas tablas y, a continuación, actualizar la columna con tres valores posibles: M para masculino, F para femenino y null para N/A. La columna se actualiza con los valores anteriores en respuesta a cierta condición.
  7. Crear un índice de mapa de bits a partir de la columna creada y ejecutar consultas con predicados de igualdad.
  8. Crear un índice de árbol B a partir de la columna GENDER y ejecutar consultas con predicados de igualdad. Comparar los resultados del paso 7.

En los pasos 1 a 4 se trabaja con una columna de alta cardinalidad (valores 100% diferentes); en el paso 5 con una columna de cardinalidad normal, y en los pasos 7 y 8 con una columna de baja cardinalidad.

Paso 1A (con TEST_NORMAL)
En este paso, crearemos un índice de mapa de bits para la tabla TEST_NORMAL y, a continuación, verificaremos el tamaño del índice, su factor de agrupamiento [clustering factor] y el tamaño de la tabla. Luego ejecutaremos algunas consultas con predicados de igualdad y registraremos las E/S de las consultas empleando el índice de mapa de bits.

SQL> create bitmap index normal_empno_bmx on test_normal(empno);
Index created.

Elapsed:  00:00:29.06

SQL>  analyze table test_normal compute statistics for table for all indexes for all  indexed columns;
Table  analyzed.

Elapsed:  00:00:19.01

SQL>  select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in  MB"
      2  from  user_segments
      3* where segment_name in ('TEST_NORMAL','NORMAL_EMPNO_BMX');
      
SEGMENT_NAME                    Size in MB
------------------------------  ---------------
TEST_NORMAL                     50
NORMAL_EMPNO_BMX                28

Elapsed:  00:00:02.00

SQL>  select index_name, clustering_factor from user_indexes;
      
INDEX_NAME                      CLUSTERING_FACTOR
------------------------------  ---------------------------------
NORMAL_EMPNO_BMX                1000000

Elapsed:  00:00:00.00
      

Puede verse en la tabla anterior que el tamaño del índice es 28 MB y que el factor de agrupamiento es igual a la cantidad de filas de la tabla. Ahora ejecutaremos las consultas con predicados de igualdad para diferentes conjuntos de valores:

SQL>  set autotrace only

SQL>  select * from test_normal where empno=&empno;
 Enter  value for empno: 1000
 old   1: select * from test_normal where  empno=&empno
 new   1: select * from test_normal where  empno=1000
   
Elapsed:  00:00:00.01
   
Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=4 Card=1 Bytes=34)
1     0    TABLE ACCESS (BY INDEX ROWID)  OF 'TEST_NORMAL' (Cost=4 Card=1 Bytes=34)
2     1    BITMAP CONVERSION (TO  ROWIDS)
3     2    BITMAP INDEX (SINGLE  VALUE) OF 'NORMAL_EMPNO_BMX'
   
Statistics
----------------------------------------------------------
0   recursive calls
0   db block gets
5   consistent gets
0   physical reads
0   redo size
515   bytes sent via SQL*Net to client
499   bytes received via SQL*Net from client
2   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

1   rows processed
   

Paso 1B (con TEST_NORMAL)
Ahora quitaremos el índice de mapa de bits y crearemos un índice de árbol B asociado a la columna EMPNO. Como antes, verificaremos el tamaño del índice y el factor de agrupamiento, y ejecutaremos algunas consultas para el mismo conjunto de valores a fin de comparar las E/S.

SQL>  drop index NORMAL_EMPNO_BMX;
Index  dropped.

SQL>  create index normal_empno_idx on test_normal(empno);
Index  created.

SQL>  analyze table test_normal compute statistics for table for all indexes for all  indexed columns;
Table  analyzed.

SQL>  select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in  MB"
   2  from  user_segments
   3   where segment_name in ('TEST_NORMAL','NORMAL_EMPNO_IDX');
   
SEGMENT_NAME                        Size in MB
----------------------------------  ---------------
TEST_NORMAL                         50
NORMAL_EMPNO_IDX                    18
SQL>  select index_name, clustering_factor from user_indexes;
   
INDEX_NAME                          CLUSTERING_FACTOR
----------------------------------  ----------------------------------
NORMAL_EMPNO_IDX                    6210
   

En la tabla se ve claramente que el índice de árbol B es más pequeño que el de mapa de bits asociado a la columna EMPNO. El factor de agrupamiento del índice de árbol B se aproxima mucho más a la cantidad de bloques de una tabla; por ese motivo, el índice de árbol B resulta eficiente para consultas con predicados de rango.
Ahora ejecutaremos las mismas consultas para el mismo conjunto de valores empleando el índice de árbol B creado.

SQL>  set autot trace  
SQL>  select * from test_normal where empno=&empno;
   Enter  value for empno: 1000
   old   1: select * from test_normal where  empno=&empno
   new   1: select * from test_normal where  empno=1000

Elapsed:  00:00:00.01
   
Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=4 Card=1 Bytes=34)
1     0    TABLE ACCESS (BY INDEX ROWID)  OF 'TEST_NORMAL' (Cost=4 Card=1 Bytes=34)
2     1    INDEX (RANGE SCAN) OF  'NORMAL_EMPNO_IDX' (NON-UNIQUE) (Cost=3 Card=1)
  
Statistics
----------------------------------------------------------
29   recursive calls
0   db block gets
5   consistent gets
0   physical reads
0   redo size
515   bytes sent via SQL*Net to client
499   bytes received via SQL*Net from client
2   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

1   rows processed
   

Como se puede ver, cuando las consultas se ejecutan para diferentes conjuntos de valores, las cantidades de lecturas coherentes [consistent get] y lecturas físicas [physical read] coinciden con relación a los índices de mapa de bits y de árbol B asociados a una columna con valores 100% únicos.

MAPA DE BITS

EMPNO

ÁRBOL B

Consistent reads

Physical reads

Consistent reads

Physical reads

5

0

1000

5

0

5

2

2398

5

2

5

2

8545

5

2

5

2

98008

5

2

5

2

85342

5

2

5

2

128444

5

2

5

2

858

5

2


Paso 2A (con TEST_RANDOM)
Ahora realizaremos el mismo experimento con TEST_RANDOM:

SQL>  create bitmap index random_empno_bmx on test_random(empno);
Index  created.

SQL>  analyze table test_random compute statistics for table for all indexes for all  indexed columns;
Table  analyzed.

SQL>  select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in  MB"
      2  from  user_segments
      3* where segment_name in  ('TEST_RANDOM','RANDOM_EMPNO_BMX');
   
SEGMENT_NAME                          Size in MB
-----------------------------------   ---------------
TEST_RANDOM                           50
RANDOM_EMPNO_BMX                      28
SQL>  select index_name, clustering_factor from user_indexes;
   
INDEX_NAME                         CLUSTERING_FACTOR
------------------------------     ---------------------------------
RANDOM_EMPNO_BMX                   1000000 


Nuevamente, las estadísticas (tamaño y factor de agrupamiento) son idénticas a las del índice creado para la tabla TEST_NORMAL:

SQL>  select * from test_random where empno=&empno;
   Enter  value for empno: 1000
   old   1: select * from test_random where  empno=&empno
   new   1: select * from test_random where  empno=1000

Elapsed:  00:00:00.01
   
Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=4 Card=1 Bytes=34)
1     0    TABLE ACCESS (BY INDEX ROWID)  OF 'TEST_RANDOM' (Cost=4 Card=1 Bytes=34)
2     1    BITMAP CONVERSION (TO  ROWIDS)
3     2    BITMAP INDEX (SINGLE  VALUE) OF 'RANDOM_EMPNO_BMX'
   
Statistics
----------------------------------------------------------
0   recursive calls
0   db block gets
5   consistent gets
0   physical reads
0   redo size
515   bytes sent via SQL*Net to client
499   bytes received via SQL*Net from client
2   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

1   rows processed
 

                   
Paso 2B (con TEST_RANDOM)
Ahora, como en el paso 1B, quitaremos el índice de mapa de bits y crearemos un índice de árbol B asociado a la columna EMPNO.

SQL>  drop index RANDOM_EMPNO_BMX;
Index  dropped.

SQL>  create index random_empno_idx on test_random(empno);
Index  created.

SQL>  analyze table test_random compute statistics for table for all indexes for all  indexed columns;
Table  analyzed.

SQL>  select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in  MB"
   2  from  user_segments
   3  where segment_name in ('TEST_RANDOM','RANDOM_EMPNO_IDX');
   
SEGMENT_NAME                        Size in MB
----------------------------------  ---------------
TEST_RANDOM                         50
RANDOM_EMPNO_IDX                    18
SQL>  select index_name, clustering_factor from user_indexes;
   
INDEX_NAME                          CLUSTERING_FACTOR
----------------------------------  ----------------------------------
RANDOM_EMPNO_IDX                    999830 
   

En la tabla se advierte que el tamaño del índice es igual al del correspondiente a la tabla TEST_NORMAL, pero el factor de agrupamiento se aproxima mucho más a la cantidad de filas, por lo cual este índice es ineficiente para consultas con predicados de rango (según veremos en el paso 4). El factor de agrupamiento mencionado no afectará las consultas con predicados de igualdad porque las filas tienen valores 100% distintos y hay una fila por clave.

Ahora ejecutaremos las consultas con predicados de igualdad y el mismo conjunto de valores:
SQL>  select * from test_random where empno=&empno;
      Enter  value for empno: 1000
      old   1: select * from test_random where  empno=&empno
      new   1: select * from test_random where  empno=1000

Elapsed:  00:00:00.01
  
Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=4 Card=1 Bytes=34)
1     0    TABLE ACCESS (BY INDEX ROWID)  OF 'TEST_RANDOM' (Cost=4 Card=1 Bytes=34)
2     1    INDEX (RANGE SCAN) OF  'RANDOM_EMPNO_IDX' (NON-UNIQUE) (Cost=3 Card=1)

Statistics
----------------------------------------------------------
0   recursive calls
0   db block gets
5   consistent gets
0   physical reads
0   redo size
515   bytes sent via SQL*Net to client
499   bytes received via SQL*Net from client
2   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

1   rows processed

                          
Nuevamente, los resultados son casi idénticos a los obtenidos en los pasos 1A y 1B. La distribución de datos no afectó la cantidad de lecturas coherentes ni lecturas físicas asociadas a una columna única.


Paso 3A (con TEST_NORMAL)
En este paso, crearemos el índice de mapa de bits (de manera similar a lo que hicimos en el paso 1A). Conocemos el tamaño del índice y el factor de agrupamiento del índice, que es igual a la cantidad de las filas de la tabla. Ahora ejecutaremos algunas consultas con predicados de rango.

SQL>  select * from test_normal where empno between &range1 and &range2;
      Enter  value for range1: 1
      Enter  value for range2: 2300
      old   1: select * from test_normal where empno  between &range1 and &range2
      new   1: select * from test_normal where empno  between 1 and 2300

2300 rows  selected.

Elapsed:  00:00:00.03

Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=451 Card=2299 Bytes=78166)
1     0    TABLE ACCESS (BY INDEX ROWID)  OF 'TEST_NORMAL' (Cost=451 Card=2299 Bytes=78166)
2     1    BITMAP CONVERSION (TO  ROWIDS)
3     2    BITMAP INDEX (RANGE SCAN)  OF 'NORMAL_EMPNO_BMX'

Statistics
----------------------------------------------------------
0   recursive calls
0   db block gets
331   consistent gets
0   physical reads
0   redo size
111416   bytes sent via SQL*Net to client
2182   bytes received via SQL*Net from client
155   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

2300   rows processed


Paso 3B (con TEST_NORMAL)
En este paso, ejecutaremos las consultas en la tabla TEST_NORMAL con un índice de árbol B asociado a esa tabla.

SQL>  select * from test_normal where empno between &range1 and &range2;
   Enter  value for range1: 1
   Enter  value for range2: 2300
   old   1: select * from test_normal where empno  between &range1 and &range2
   new   1: select * from test_normal where empno  between 1 and 2300

2300 rows  selected.

Elapsed:  00:00:00.02

Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=23 Card=2299 Bytes=78166)
1     0    TABLE ACCESS (BY INDEX ROWID)  OF 'TEST_NORMAL' (Cost=23 Card=2299 Bytes=78166)
2     1    INDEX (RANGE SCAN) OF  'NORMAL_EMPNO_IDX' (NON-UNIQUE) (Cost=8 Card=2299)

Statistics
----------------------------------------------------------
0   recursive calls
0   db block gets
329   consistent gets
15   physical reads
0   redo size
111416   bytes sent via SQL*Net to client
2182   bytes received via SQL*Net from client
155   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

2300   rows processed

Cuando las consultas se ejecutan para diferentes conjuntos de rangos, se muestran los siguientes resultados:

MAPA DE BITS

EMPNO (intervalo)

ÁRBOL B

Consistent reads

Physical reads

Consistent reads

Physical reads

331

0

1-2300

329

0

285

0

8-1980

283

0

346

19

1850-4250

344

16

427

31

28888-31850

424

28

371

27

82900-85478

367

23

2157

149

984888-1000000

2139

35


Como se puede ver, la cantidad de lecturas coherentes y lecturas físicas con ambos índices vuelve a ser casi idéntica. El último rango (984888-1000000) devolvió casi 15.000 filas, la cantidad máxima de filas obtenidas para todos los rangos anteriores. Así, cuando quisimos realizar una exploración completa de la tabla (agregando /*+ full(test_normal) */ ), los recuentos de lecturas coherentes y lecturas físicas fueron 7239 y 5663, respectivamente.

Paso 4A (con TEST_RANDOM) 
En este paso, ejecutaremos las consultas con predicados de rango en la tabla TEST_RANDOM con el índice de mapa de bits y verificaremos la cantidad de lecturas coherentes y lecturas físicas. En este ejemplo se verá el impacto del factor de agrupamiento.

SQL>  select  * from test_random where empno between &range1 and &range2;
      Enter  value for range1: 1
      Enter  value for range2: 2300
      old  1: select * from test_random where empno  between &range1 and &range2
      new  1: select * from test_random where empno  between 1 and 2300

2300 rows  selected.

Elapsed:  00:00:08.01

Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=453 Card=2299 Bytes=78166)
1     0    TABLE ACCESS (BY INDEX ROWID)  OF 'TEST_RANDOM' (Cost=453 Card=2299 Bytes=78166)
2     1    BITMAP CONVERSION (TO  ROWIDS)
3     2    BITMAP INDEX (RANGE SCAN)  OF 'RANDOM_EMPNO_BMX'

Statistics
----------------------------------------------------------
0   recursive calls
0   db block gets
2463   consistent gets
1200   physical reads
0   redo size
111416   bytes sent via SQL*Net to client
2182   bytes received via SQL*Net from client
155   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

2300   rows processed


Paso 4B (con TEST_RANDOM)
En este paso, ejecutaremos las consultas con predicados de rango en la tabla TEST_RANDOM con un índice de árbol B asociado a esa tabla. Recuérdese que el factor de agrupamiento de este índice se aproximaba mucho a la cantidad de filas de la tabla (por lo que el índice resultaba ineficiente). A continuación se incluye el procedimiento aplicado por el optimizador:

SQL> select * from test_random where empno between &range1 and &range2;
     Enter  value for range1: 1
     Enter  value for range2: 2300
     old   1: select * from test_random where empno  between &range1 and &range2
     new   1: select * from test_random where empno  between 1 and 2300

2300 rows  selected.

Elapsed:  00:00:03.04

Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=613 Card=2299 Bytes=78166)
1     0    TABLE ACCESS (FULL) OF  'TEST_RANDOM' (Cost=613 Card=2299 Bytes=78166)

Statistics
----------------------------------------------------------
0   recursive calls
0   db block gets
6415   consistent gets
4910   physical reads
0   redo size
111416   bytes sent via SQL*Net to client
2182   bytes received via SQL*Net from client
155   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

2300   rows processed 
   

El optimizador optó por hacer una exploración de la tabla completa en lugar de emplear el índice a causa del factor de agrupamiento:


MAPA DE BITS

EMPNO (rango)

ÁRBOL B

Consistent reads

Physical reads

Consistent reads

Physical reads

2463

1200

1-2300

6415

4910

2114

31

8-1980

6389

4910

2572

1135

1850-4250

6418

4909

3173

1620

28888-31850

6456

4909

2762

1358

82900-85478

6431

4909

7254

3329

984888-1000000

7254

4909


El optimizador eligió la exploración completa de la tabla solo para el último rango (984888-1000000) en el caso del índice de mapa de bits, mientras que optó por la exploración de la tabla completa para todos los rangos en el caso del índice de árbol B. La diferencia en el procedimiento elegido se debe al factor de agrupamiento: El optimizador no tiene en cuenta el valor del factor de agrupamiento cuando genera planes de ejecución basados en un índice de mapa de bits; pero sí lo tiene en cuenta cuando trabaja con un índice de árbol B. En el escenario descripto, el índice de mapa de bits es más eficiente que el de árbol B.

En los pasos que siguen se revelan otros datos interesantes sobre ambos índices.

Paso 5A (con TEST_NORMAL)
Crear un índice de mapa de bits asociado a la columna SAL [salario] de la tabla TEST_NORMAL. Esa columna tiene cardinalidad normal.

SQL>  create bitmap index normal_sal_bmx on test_normal(sal);
Index  created.

SQL>  analyze table test_normal compute statistics for table for all indexes for all  indexed columns;
Table analyzed.
   

Ahora obtengamos el tamaño del índice y el factor de agrupamiento.

SQL> select  substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in MB"
     2* from user_segments
     3* where segment_name in  ('TEST_NORMAL','NORMAL_SAL_BMX');

SEGMENT_NAME                    Size in MB
-----------------------------   --------------
TEST_NORMAL                     50
NORMAL_SAL_BMX                  4

SQL>  select index_name, clustering_factor from user_indexes;

INDEX_NAME                      CLUSTERING_FACTOR
------------------------------  ----------------------------------
NORMAL_SAL_BMX                  6001

Ahora trabajemos con las consultas. Primero ejecutémoslas con predicados de igualdad:

SQL>  set autot trace
SQL>  select * from test_normal where sal=&sal;
      Enter  value for sal: 1869
      old   1: select * from test_normal where  sal=&sal
      new   1: select * from test_normal where sal=1869

164 rows  selected.

Elapsed:  00:00:00.08

Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=39 Card=168 Bytes=4032)
1     0    TABLE ACCESS (BY INDEX ROWID)  OF 'TEST_NORMAL' (Cost=39 Card=168 Bytes=4032)
2     1    BITMAP CONVERSION (TO  ROWIDS)
3     2    BITMAP INDEX (SINGLE  VALUE) OF 'NORMAL_SAL_BMX'

Statistics
----------------------------------------------------------
0   recursive calls
0   db block gets
165   consistent gets
0   physical reads
0   redo size
8461   bytes sent via SQL*Net to client
609   bytes received via SQL*Net from client
12   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

164   rows processed

y luego con los predicados de rango:

SQL> select * from test_normal where sal between &sal1 and &sal2;
     Enter  value for sal1: 1500
     Enter  value for sal2: 2000
     old   1: select * from test_normal where sal  between &sal1 and &sal2
     new   1: select * from test_normal where sal  between 1500 and 2000

83743  rows selected.

Elapsed:  00:00:05.00

Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=83376 Bytes=2001024)
1     0    TABLE ACCESS (FULL) OF  'TEST_NORMAL' (Cost=601 Card=83376 Bytes=2001024)

Statistics
----------------------------------------------------------
0   recursive calls
0   db block gets
11778   consistent gets
5850   physical reads
0   redo size
4123553   bytes sent via SQL*Net to client
61901   bytes received via SQL*Net from client
5584   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

83743   rows processed 
   

Ahora quitaremos el índice de mapa de bits y crearemos un índice de árbol B para TEST_NORMAL.

SQL>  create index normal_sal_idx on test_normal(sal);
Index  created.

SQL>  analyze table test_normal compute statistics for table for all indexes for all  indexed columns;
Table  analyzed.

Observemos el tamaño del índice y el factor de agrupamiento.

SQL> select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in  MB"
     2  from  user_segments
     3   where segment_name in ('TEST_NORMAL','NORMAL_SAL_IDX');

SEGMENT_NAME                    Size in MB
------------------------------  ---------------
TEST_NORMAL                     50
NORMAL_SAL_IDX                  17

SQL>  select index_name, clustering_factor from user_indexes;

INDEX_NAME                      CLUSTERING_FACTOR
------------------------------  ----------------------------------
NORMAL_SAL_IDX                  986778

En la tabla anterior, se puede ver que este índice es más grande que el de mapa de bits asociado a la misma columna. El factor de agrupamiento también se aproxima a la cantidad de filas de la tabla.
Con relación a las pruebas, usaremos primero predicados de igualdad:

SQL>  set autot trace
SQL>  select * from test_normal where sal=&sal;
      Enter  value for sal: 1869
      old   1: select * from test_normal where  sal=&sal
      new   1: select * from test_normal where sal=1869

164 rows  selected.

Elapsed:  00:00:00.01

Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=169 Card=168 Bytes=4032)
1     0    TABLE ACCESS (BY INDEX ROWID)  OF 'TEST_NORMAL' (Cost=169 Card=168 Bytes=4032)
2     1    INDEX (RANGE SCAN) OF  'NORMAL_SAL_IDX' (NON-UNIQUE) (Cost=3 Card=168)

Statistics
----------------------------------------------------------
0   recursive calls
0   db block gets
177   consistent gets
0   physical reads
0   redo size
8461   bytes sent via SQL*Net to client
609   bytes received via SQL*Net from client
12   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

164   rows processed

y luego, predicados de rango:

SQL> select * from test_normal where sal between &sal1 and &sal2;
     Enter  value for sal1: 1500
     Enter  value for sal2: 2000
     old  1: select * from test_normal where sal  between &sal1 and &sal2
     new  1: select * from test_normal where sal  between 1500 and 2000

83743  rows selected.

Elapsed:  00:00:04.03

Execution  Plan
---------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=83376 Bytes=2001024)
1     0    TABLE ACCESS (FULL) OF  'TEST_NORMAL' (Cost=601 Card=83376 Bytes=2001024)

Statistics
----------------------------------------------------------
0   recursive calls
0   db block gets
11778   consistent gets
3891   physical reads
0   redo size
4123553   bytes sent via SQL*Net to client
61901   bytes received via SQL*Net from client
5584   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

83743   rows processed 

                          
Cuando se ejecutaron las consultas para conjuntos de valores diferentes, según se muestra en las tablas anteriores la salida obtenida reveló cantidades idénticas de lecturas coherentes y lecturas físicas.

MAPA DE BITS

SAL (igualdad)

ÁRBOL B

Filas obtenidas

Consistent reads

Physical reads

Consistent reads

Physical reads

165

0

1869

177

164

 

169

163

3548

181

167

 

174

166

6500

187

172

 

75

69

7000

81

73

 

177

163

2500

190

175

 



MAPA DE BITS

SAL (rango)

ÁRBOL B

Filas obtenidas

Consistent reads

Physical reads

Consistent reads

Physical reads

11778

5850

1500-2000

11778

3891

83743

11765

5468

2000-2500

11765

3879

83328

11753

5471

2500-3000

11753

3884

83318

17309

5472

3000-4000

17309

3892

166999

39398

5454

4000-7000

39398

3973

500520


En el caso de predicados de rango, el optimizador optó por la exploración de la tabla completa para todos los conjuntos de valores diferentes —directamente no usó los índices—; en cambio, en el caso de predicados de igualdad empleó los índices. Nuevamente, las cantidades de lecturas coherentes y lecturas físicas son idénticas.
En consecuencia, es posible concluir que cuando se trabajó con una columna de cardinalidad normal, el optimizador tomó las mismas decisiones respecto de ambos índices y no hubo diferencias importantes entre las E/S.

Paso 6 (agregar una columna GENDER)
Antes de realizar la prueba con una columna de baja cardinalidad, agregaremos una columna GENDER a la tabla y la actualizaremos para cargarle los valores M, F y null.

SQL>  alter table test_normal add GENDER varchar2(1);
Table  altered.

SQL>  select GENDER, count(*) from test_normal group by GENDER;

S     COUNT(*)
--    ----------
F     333769
M     499921
      166310

3 rows  selected.
   

El tamaño del índice de mapa de bits asociado a esta columna es de alrededor de 570 KB, como se indica en la tabla que sigue:

SQL>  create bitmap index normal_GENDER_bmx on test_normal(GENDER);
Index created.

Elapsed:  00:00:02.08

SQL>  select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in  MB"
      2  from  user_segments
      3   where segment_name in ('TEST_NORMAL','NORMAL_GENDER_BMX');

SEGMENT_NAME                    Size in MB
------------------------------  ---------------
TEST_NORMAL                     50
NORMAL_GENDER_BMX               .5625

2 rows selected.

En cambio, el tamaño del índice de árbol B asociado a esta columna es 13 MB, mucho mayor que el de mapa de bits para la misma columna.

SQL>  create index normal_GENDER_idx on test_normal(GENDER);
Index  created.

SQL>  select substr(segment_name,1,30) segment_name, bytes/1024/1024 "Size in  MB"
      2  from  user_segments
      3   where segment_name in ('TEST_NORMAL','NORMAL_GENDER_IDX');

SEGMENT_NAME                    Size in MB
------------------------------  ---------------
TEST_NORMAL                     50
NORMAL_GENDER_IDX               13

2 rows selected.

Ahora bien, si ejecutamos una consulta con predicados de igualdad, el optimizador no utilizará los índices, sean de mapa de bits o de árbol B. En cambio, optará por la exploración de la tabla completa.                           

SQL>  select * from test_normal where GENDER is null;
 
166310 rows selected.

Elapsed:  00:00:06.08

Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=166310 Bytes=4157750)
1     0    TABLE ACCESS (FULL) OF  'TEST_NORMAL' (Cost=601 Card=166310 Bytes=4157750)

SQL>  select * from test_normal where GENDER='M';

499921  rows selected.

Elapsed:  00:00:16.07

Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=499921 Bytes=12498025)
1     0    TABLE ACCESS (FULL) OF  'TEST_NORMAL' (Cost=601 Card=499921Bytes=12498025)

SQL>select  * from test_normal where GENDER='F'
/

333769  rows selected.

Elapsed:  00:00:12.02

Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=333769 Bytes=8344225)
1     0    TABLE ACCESS (FULL) OF  'TEST_NORMAL' (Cost=601 Card=333769 Bytes=8344225)

Conclusiones
Ahora que comprendemos cómo reacciona el optimizador ante las técnicas descriptas, analicemos un escenario en el que se muestran claramente las aplicaciones respectivas de los índices de mapas de bits y de los de árbol B.
Habiendo creado un índice de mapa de bits para la columna GENDER, creemos otro del mismo tipo asociado a la columna SAL y, a continuación, ejecutemos algunas consultas. Las consultas volverán a ejecutarse con índices de árbol B asociados a esas columnas.
De la tabla TEST_NORMAL, necesitamos obtener el número de empleado de todos los empleados hombres con salarios mensuales iguales a alguno de los siguientes valores:

1000 
1500 
2000 
2500 
3000 
3500 
4000 
4500 
   
  

Entonces:

SQL> select  * from test_normal 
     where sal  in (1000,1500,2000,2500,3000,3500,4000,4500,5000) and GENDER='M';
  

Esta es una consulta de almacenes de datos típica que de ninguna manera debería ejecutarse en un sistema OLTP. A continuación se muestran los resultados con un índice de mapa de bits asociado a ambas columnas:

SQL> select  * from test_normal 
     where sal  in (1000,1500,2000,2500,3000,3500,4000,4500,5000) and GENDER='M';    

1453 rows  selected.

Elapsed:  00:00:02.03

Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=198 Card=754 Bytes=18850)
1     0    TABLE ACCESS (BY INDEX ROWID)  OF 'TEST_NORMAL' (Cost=198 Card=754 Bytes=18850)
2     1    BITMAP CONVERSION (TO  ROWIDS)
3     2    BITMAP AND
4     3    BITMAP OR
5     4    BITMAP INDEX (SINGLE  VALUE) OF 'NORMAL_SAL_BMX'
6     4    BITMAP INDEX (SINGLE  VALUE) OF 'NORMAL_SAL_BMX'
7     4    BITMAP INDEX (SINGLE  VALUE) OF 'NORMAL_SAL_BMX'
8     4    BITMAP INDEX (SINGLE  VALUE) OF 'NORMAL_SAL_BMX'
9     4    BITMAP INDEX (SINGLE  VALUE) OF 'NORMAL_SAL_BMX'
10    4    BITMAP INDEX (SINGLE  VALUE) OF 'NORMAL_SAL_BMX'
11    4    BITMAP INDEX (SINGLE  VALUE) OF 'NORMAL_SAL_BMX'
12    4    BITMAP INDEX (SINGLE  VALUE) OF 'NORMAL_SAL_BMX'
13    4    BITMAP INDEX (SINGLE  VALUE) OF 'NORMAL_SAL_BMX'
14    3    BITMAP INDEX (SINGLE  VALUE) OF 'NORMAL_GENDER_BMX'

Statistics
----------------------------------------------------------
0   recursive calls
0   db block gets
1353   consistent gets
920   physical reads
0   redo size
75604   bytes sent via SQL*Net to client
1555   bytes received via SQL*Net from client
98   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

1453   rows processed

Y con el índice de árbol B:

SQL> select  * from test_normal 
     where sal  in (1000,1500,2000,2500,3000,3500,4000,4500,5000) and GENDER='M'; 

1453 rows  selected.

Elapsed:  00:00:03.01

Execution  Plan
----------------------------------------------------------
0          SELECT STATEMENT Optimizer=CHOOSE (Cost=601 Card=754 Bytes=18850)
1     0    TABLE ACCESS (FULL) OF  'TEST_NORMAL' (Cost=601 Card=754 Bytes=18850)

Statistics
---------------------------------------------------------
0   recursive calls
0   db block gets
6333   consistent gets
4412   physical reads
0   redo size
75604   bytes sent via SQL*Net to client
1555   bytes received via SQL*Net from client
98   SQL*Net roundtrips to/from client
0   sorts (memory)
0   sorts (disk)

1453   rows processed

Como se puede ver, en el caso de la tabla con el índice de árbol B el optimizador optó por la exploración de la tabla completa, mientras que en el del índice de mapa de bits usó el índice para resolver la consulta. Es posible deducir el rendimiento a partir de la cantidad de E/S requeridas para obtener el resultado.
En resumen, los índices de mapas de bits son más adecuados para los sistemas DSS independientemente de la cardinalidad por los siguientes motivos:

  • cuando se trabaja con índices de mapas de bits, el optimizador puede responder eficientemente a consultas que incluyan operadores AND, OR o XOR (Oracle admite la conversión dinámica de árbol B a mapa de bits, pero puede ser ineficiente);
  • con los índices de mapas de bits, el optimizador puede resolver las consultas cuando busca o cuenta los valores nulos; los valores nulos también se indexan en los índices de mapas de bits (no así en los índices de árbol B);
  • y más importante aun, los índices de mapas de bits de los sistemas DSS admiten consultas ad hoc, mientras que los índices de árbol B no; concretamente, si se trabaja con una tabla de 50 columnas y los usuarios hacen consultas frecuentes para diez de esas columnas, es muy complicado trabajar con la combinación de las diez columnas o a veces crear un índice de árbol B para una sola columna; si se crean 10 índices de mapas de bits para las diez columnas, todas las consultas pueden solucionarse recurriendo a ellos, ya sea que las consultas comprendan las diez columnas, o cuatro o seis de las diez, o incluso solo una. La indicación AND_EQUAL proporciona esa funcionalidad cuando se trabaja con índices de árbol B, pero no permite usar más de cinco índices por consulta; ese límite no se aplica a los índices de mapas de bits.

En contraste, los índices de árbol B son muy adecuados para las aplicaciones OLTP en las que las consultas de los usuarios son relativamente repetitivas (y se encuentran bien depuradas antes de la implementación en el ambiente de producción), a diferencia de lo que ocurre con las consultas ad hoc, que son mucho menos frecuentes y suelen ejecutarse en horarios de baja actividad. Como los datos se actualizan y eliminan de las aplicaciones OLTP con frecuencia, los índices de mapas de bits pueden crear importantes bloqueos en esas situaciones.
Los datos son bastante claros. Ambos índices son para fines similares: devolver resultados lo antes posible. Pero la elección respecto de cuál usar dependerá exclusivamente de la clase de aplicación y no del nivel de cardinalidad.


Vivek Sharma es Administrador senior de bases de datos Oracle en Accenture India, Bombay. Ha trabajado seis años con las tecnologías Oracle y es Profesional certificado de Oracle. Vivek se especializa en optimización de rendimiento y de SQL-PL/SQL.