Índice de bitmap x índice de árvore B: Qual e quando usar?

Por Vivek Sharma
Postado em Dezembro 2014

Entender bem como usar cada índice pode ter grande influência no desempenho.

É comum pensar que os índices de bitmap são os mais adequados para colunas que podem conter poucos valores diferentes, como GENDER [gênero], MARITAL_STATUS [estado civil] e RELATION [relação]. Porém, essa premissa não totalmente exata. Na verdade, sempre é recomendável usar índices de bitmap para sistemas em que os dados não são frequentemente atualizados por muitos sistemas simultâneos. De fato, como demonstrarei aqui, usar um índice de bitmap associado a uma coluna com 100% de valores únicos (que poderiam ser usados como chave principal) é um recurso tão eficiente quanto usar um índice de árvore B.
Neste artigo, vou oferecer alguns exemplos, bem como decisões do otimizador, comuns a ambos os tipos de índices, quer que estes sejam aplicados a colunas de baixa cardinalidade ou a colunas de alta cardinalidade. Esses exemplos irão ajudar os gerentes de bases de dados a entenderem que o uso dos índices de bitmap não dependem, na verdade, da cardinalidade, mas do aplicativo.

Comparação dos índices
Usar um índice de bitmap associado a uma coluna única traz várias desvantagens, entre elas, a necessidade de espaço suficiente (e o Oracle não indica esse uso). Mesmo assim, o tamanho do índice de bitmap depende da cardinalidade da coluna em relação à qual é criado bem como da distribuição dos dados. Por conseguinte, um índice de bitmap para a coluna GENDER será menor que um índice de árvore B para a mesma coluna. Por sua vez, um índice de bitmap para EMPNO [N° de funcionário] (que poderia ser usado como chave principal) será muito maior do que um índice de árvore B para essa coluna. Mas como os usuários que acessam sistemas de apoio para a tomada de decisões (DSS) são menos do que os que acessariam sistemas de processamento de transações (OLTP), os recursos não são um problema para estes aplicativos.
Para ilustrar o anterior, criei duas tabelas TEST_NORMAL [teste normal] e TEST_RANDOM [teste aleatório]. Inseri um milhão de linhas na tabela TEST_NORMAL com um bloco PL/SQL e, a seguir, inseri as linhas que seguem na tabela TEST_RANDOM em ordem aleatória:

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
   

Note-se que a tabela TEST_NORMAL é organizada enquanto a tabela TEST_RANDOM foi criada de forma aleatória, portanto, esta contém dados desorganizados. Na tabela acima, a coluna EMPNO inclui valores 100% diferentes entre si, e seria adequado usá-la como chave principal. Caso essa coluna seja definida como chave principal, será criado um índice de árvore B e não um de bitmap, pois o Oracle não suporta índices de bitmap com chaves principais.

Para analisar o comportamento dos índices, faremos o seguinte:

  1. Em TEST_NORMAL:
    1. Criar um índice de bitmap a partir da coluna EMPNO e executar consultas com predicados de igualdade.
    2. Criar um índice de árvore B a partir da coluna EMPNO, executar consultas com predicados de igualdade, e comparar as E/S lógicas e físicas usadas pelas consultas para obter os resultados relacionadas aos diferentes conjuntos de valores.
  2. Em TEST_RANDOM:
    1. Idem passo 1A.
    2. Idem passo 1B.
  3. Em TEST_NORMAL:
    1. Idem passo 1A, exceto que as consultas são executadas dentro de uma série de predicados.
    2. Idem passo 1B, exceto que as consultas são executadas dentro de uma série de predicados. Comparar as estatísticas.
  4. Em TEST_RANDOM:
    1. Idem passo 3A.
    2. Idem passo 3B.
  5. Em TEST_NORMAL:
    1. Criar um índice de bitmap a partir da coluna SAL e executar consultas com predicados de igualdade e outras com predicados de intervalo.
    2. Criar um índice de árvore B a partir da coluna SAL e executar algumas consultas com predicados de igualdade e outras com predicados de intervalo (usar o mesmo conjunto de valores usado no passo 5A). Comparar as E/S usadas pelas consultas para obter os resultados.
  6. Adicionar uma coluna GENDER em ambas as tabelas e, em seguida, atualizar a coluna com três valores possíveis: M para masculino, F para feminino e null para N/A. A coluna é atualizada com os valores anteriores como resposta a certa condição.
  7. Criar um índice de bitmap a partir da coluna criada e executar consultas com predicados de igualdade.
  8. Criar um índice de árvore B a partir da coluna GENDER e executar consultas com predicados de igualdade. Comparar os resultados do passo 7.

Os passos 1 a 4 envolvem uma coluna de alta cardinalidade (valores 100% diferentes); no passo 5, uma coluna de cardinalidade normal e, nos passos 7 e 8, uma coluna de baixa cardinalidade.

Passo 1A (com TEST_NORMAL)
Neste passo, criaremos um índice de bitmap para a tabela TEST_NORMAL e, a seguir, verificaremos o tamanho do índice, seu fator de agrupamento [clustering factor] e o tamanho da tabela. Depois, executaremos algumas consultas com predicados de igualdade e registraremos as E/S das consultas usando o índice de bitmap.

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
      

Na tabela acima, observamos que o tamanho do índice é de 28 MB e que o fator de agrupamento é igual à quantidade de linhas da tabela. Agora, vamos executar as consultas com predicados de igualdade 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
   

Passo 1B (com TEST_NORMAL)
Agora, vamos remover o índice de bitmap e vamos criar um índice de árvore B associado à coluna EMPNO. Como antes, vamos conferir o tamanho do índice e o fator de agrupamento, e vamos executar algumas consultas para o mesmo conjunto de valores, a fim de comparar as 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
   

Observamos claramente na tabela que o índice de árvore B é menor do que o de bitmap associado à coluna EMPNO. O fator de agrupamento do índice de árvore B se aproxima muito mais da quantidade de blocos de uma tabela; por isso, o índice de árvore B é eficiente para consultas com predicados de intervalo.
Agora, vamos executar as mesmas consultas para o mesmo conjunto de valores usando o índice de árvore B criado.

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 é possível observar, quando as consultas são executadas para diferentes conjuntos de valores, as quantidades de leituras consistentes [consistent get] e leituras físicas [physical read] coincidem em relação aos índice de bitmap e de árvore B associados a uma coluna com valores 100% únicos.

BITMAP

EMPNO

ÁRVORE 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


Passo 2A (com TEST_RANDOM)

Agora, vamos fazer a mesma experiência com 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 


Mais uma vez, as estatísticas (tamanho e fator de agrupamento) são idênticas às do índice criado para a tabela 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
 

                   
Passo 2B (com TEST_RANDOM)
Agora, como no passo 1B, vamos remover o índice de bitmap e vamos criar um índice de árvore B associado à coluna 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 
   

Observamos que, na tabela, o tamanho do índice é igual ao do correspondente à tabela TEST_NORMAL, mas o fator de agrupamento se aproxima muito mais da quantidade de linhas, portanto, este índice é ineficiente para consultas com predicados de intervalo (conforme veremos no passo 4). O fator de agrupamento mencionado não vai afetar as consultas com predicados de igualdade pois as linhas têm valores 100% distintos e há uma linha por chave.
Agora, vamos executar as consultas com predicados de igualdade e o mesmo 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

                          
Novamente, os resultados são quase idênticos aos obtidos nos passos 1A e 1B. A distribuição de dados não afetou a quantidade de leituras consistentes nem leituras físicas associadas a uma coluna única.

Passo 3A (com TEST_NORMAL)
Neste passo, vamos criar o índice de bitmap (de forma similar a como fizemos no passo 1A). Conhecemos o tamanho do índice e o fator de agrupamento do índice, que é igual à quantidade das linhas da tabela. Agora, vamos executar algumas consultas com predicados de intervalo.

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


Passo 3B (com TEST_NORMAL)
Neste passo, vamos executar as consultas na tabela TEST_NORMAL com um índice de árvore B associado a essa tabela.

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

                           
Quando as consultas são executadas para diferentes conjuntos de intervalos, surgem os resultados a seguir:

BITMAP

EMPNO (intervalo)

ÁRVORE 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


Observamos que a quantidade de leituras consistentes e leituras físicas com ambos os índices é novamente quase idêntica. O último intervalo (984888-1000000) retornou quase 15.000 linhas, a quantidade máxima de linhas obtida para todos os intervalos anteriores. Assim, quando quisemos realizar uma varredura completa da tabela (adicionando /*+ full(test_normal) */ ), as contagens de leituras consistentes e de leituras físicas foram 7239 e 5663, respectivamente.

Passo 4A (com TEST_RANDOM) 
Neste passo, vamos executar as consultas com predicados de intervalo na tabela TEST_RANDOM com o índice de bitmap e vamos avaliar a quantidade de leituras consistentes e de leituras físicas. Neste exemplo, observaremos o impacto do fator de agrupamento.

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


Passo 4B (com TEST_RANDOM)
Neste passo, vamos executar as consultas com predicados de intervalo na tabela TEST_RANDOM com um índice de árvore B associado a essa tabela. É necessário lembrar que o fator de agrupamento deste índice se aproximava muito da quantidade de linhas da tabela (portanto, o índice resultava ineficiente). A seguir, incluímos o procedimento aplicado pelo otimizador:

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 
   

O otimizador optou por fazer uma varredura completa da tabela em vez de usar o índice por causa do fator de agrupamento:


BITMAP

EMPNO (intervalo)

ÁRVORE 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


O otimizador escolheu a varredura completa da tabela apenas para o último intervalo (984888-1000000) no caso do índice de bitmap, enquanto optou pela varredura completa da tabela para todos os intervalos no caso do índice de árvore B. A diferença no procedimento escolhido é devida ao fator de agrupamento: O otimizador não leva em conta o valor do fator de agrupamento quando gera planos de execução baseados em um índice de bitmap; mas leva em conta quando trabalha com um índice de árvore B. No cenário descrito, o índice de bitmap é mais eficiente do que o de árvore B.
Nos passos a seguir, revelamos outros dados interessantes sobre os dois índices.

Passo 5A (com TEST_NORMAL)
Criar um índice de bitmap associado à coluna SAL [salário] da tabela TEST_NORMAL. Essa coluna tem cardinalidade 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.
   


Agora, vamos obter o tamanho do índice e o fator de agrupamento.

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

                           
Agora, vamos trabalhar com as consultas. Primeiro, vamos executá-las com predicados de igualdade:

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

e depois, com predicados de intervalo:

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 
   

Agora, vamos remover o índice de bitmap e vamos criar um índice de árvore 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.

                           
Vamos observar o tamanho do índice e o fator de  agrupamento.

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


Na tabela acima, podemos ver que este índice é maior do que o de bitmap associado à mesma coluna. O fator de agrupamento também se aproxima da quantidade de linhas da tabela.
Em relação aos testes, primeiramente, vamos usar predicados de igualdade:

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

e depois, predicados de intervalo:

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 

                          
Quando as consultas foram executadas para conjuntos de valores diferentes, conforme mostrado nas tabelas anteriores, a saída obtida revelou quantidades idênticas de leituras consistentes e de leituras físicas.

BITMAP

SAL (igualdade)

ÁRVORE B

Linhas obtidas

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

 



BITMAP

SAL (intervalo)

ÁRVORE B

Linhas obtidas

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


No caso de predicados de intervalo, o otimizador optou pela varredura completa da tabela para todos os conjuntos de valores diferentes —diretamente, ele não usou os índices—; pelo contrário, no caso de predicados de igualdade, ele usou os índices. Mais uma vez, as quantidades de leituras consistentes e de leituras físicas são idênticas.
Por conseguinte, é possível concluir que quando o trabalho foi feito com uma coluna de cardinalidade normal, o otimizador tomou as mesmas decisões para ambos os índices e não houve diferenças importantes entre as E/S.

Passo 6 (adicionar uma coluna GENDER)
Antes de realizar o teste com uma coluna de baixa cardinalidade, vamos adicionar uma coluna GENDER na tabela e vamos atualizar para carregar os valores M, F e 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.
   

O tamanho do índice de bitmap associado a esta coluna é de aproximadamente 570 KB, como mostrado na tabela a seguir:

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.

Já o tamanho do índice de árvore B associado a esta coluna é de 13 MB, muito maior do que o bitmap para a mesma coluna.

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.

Ora, se executarmos uma consulta com predicados de igualdade, o otimizador não vai usar os índices, quer os de bitmap ou os de árvore B. Pelo contrário, ele vai optar pela varredura completa da tabela.

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)

                              
Conclusões
Agora que entendemos como o otimizador reage ante as técnicas descritas, vamos analisar um cenário no qual são claramente mostrados as aplicações respectivas dos índice de bitmap e dos de árvore B.
Tendo criado um índice de bitmap para a coluna GENDER, vamos criar um outro do mesmo tipo associado à coluna SAL, e, a seguir, vamos executar algumas consultas. As consultas serão novamente executadas com índice de árvore B associados a essas colunas.
Da tabela TEST_NORMAL, precisamos obter o número de funcionário de todos os funcionários homens com salários mensais igual a algum dos seguintes valores:

1000 
1500 
2000 
2500 
3000 
3500 
4000 
4500 
   
  

Então:

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

Esta é uma consulta de armazém de dados típica que nunca deveria ser executada em um sistema OLTP. A seguir, mostramos os resultados com um índice de bitmap associado a ambas as colunas:

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

E com um índice de árvore 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 podemos observar, no caso da tabela com o índice de árvore B, o otimizador optou pela varredura completa da tabela; já no índice de bitmap, usou o índice para resolver a consulta. É possível deduzir o desempenho a partir da quantidade de E/S requeridas para obter o resultado.
Resumindo, os índices de bitmap são mais adequados para os sistemas DSS, independentemente da cardinalidade, pelos seguintes motivos:

  • trabalhando com índices de bitmap, o otimizador pode responder eficientemente a consultas que incluam operadores AND, OR ou XOR (o Oracle suporta a conversão dinâmica de árvore B para bitmap, mas isto pode ser ineficiente);
  • com índices de bitmap, o otimizador pode resolver as consultas quando procura ou conta os valores nulos; os valores nulos também são indexados nos índices de bitmap (não sendo assim nos índices de árvore B);
  • e, mais importante ainda, os índices de bitmap dos sistemas DSS suportam consultas ad hoc, enquanto os índices de árvore B não; concretamente, quando trabalhamos com uma tabela de 50 colunas e os usuários fazem consultas frequentes para dez dessas colunas, é muito complicado trabalhar com a combinação das dez colunas ou, às vezes, criar um índice de árvore B para uma única coluna; caso sejam criados 10 índices de bitmap para as dez colunas, todas as consultas podem ser solucionadas recorrendo a eles, tanto se as consultas abrangem as dez colunas, ou quatro ou seis das dez, ou até apenas uma. A indicação AND_EQUAL fornece essa funcionalidade quando trabalhamos com índice de árvore B, mas não permite usar mais de cinco índices por consulta; esse limite não é aplicado aos índices de bitmap.

Pelo contrário, os índices de árvore B são muito mais adequados para as aplicações OLTP nas quais as consultas dos usuários são relativamente repetitivas (e estão bem depuradas antes da implantação do ambiente de produção), diferentemente do que acontece com as consultas ad hoc, muito menos frequentes e frequentemente executadas em horários de baixa atividade. Como os dados são atualizados e eliminados das aplicações OLTP com frequência, os índices de bitmap podem criar importantes bloqueios nessas situações.

Os dados são bastante claros. Ambos os índices servem para finalidades similares: retornar resultados o quanto antes. Mas a escolha sobre qual usar vai depender exclusivamente da classe de aplicação e não do nível de cardinalidade.


Vivek Sharma é Administrador sênior de bases de dados Oracle na Accenture Índia, Bombaim. Trabalhou durante seis anos com as tecnologias Oracle e é Profissional certificado da Oracle. Vivek é especializado em otimização de desempenho e de SQL-PL/SQL.