Índices bitmap têm sido usados há um bom tempo em bancos de dados convencionais como uma alternativa mais rápida aos tradicionais índices baseados em árvore por prover processamento em nível bit-a-bit, que é mais próximo das arquiteturas de hardware. Sua desvantagem em ambientes transacionais é que sua manutenção é cara frente ao grande número de inserções, atualizações e exclusões de registros. Entretanto, ambientes OLAP já têm como característica o baixo nível de operações de atualização (normalmente restritas ao processo de ETL) tornando viável a escolha deste tipo de índice para apoiar o processamento das consultas.
Em um DW, a junção dos registros da tabela de fatos com suas descrições nas tabelas de dimensão é uma das operações mais comuns encontradas e, pensando nesse fato, alguns pesquisadores criaram uma especialização dos índices bitmap já levando em conta tal junção. Tal tipo de índice foi chamado de Índice Bitmap de Junção (IBJ).
A Figura 6 representa um esquema de construção dos IBJs para a coluna
s_address da tabela dimensão Supplier contra a tabela fato Lineorder. Nela
podemos notar que são formados n vetores com m posições cada, onde n é o número de diferentes valores do domínio da coluna sendo mapeada na tabela de dimensão e m é o número de linhas da tabela de fatos. A construção segue num laço onde cada registro da tabela de fatos (setas horizontais saindo da tabela de fatos para os IBJs) é avaliado contra o registro da tabela de dimensão sendo considerado (setas saindo da tabela dimensão para os IBJs). Caso a linha da tabela de fatos corresponda a uma das chaves mapeadas pela coluna sendo avaliada na tabela de dimensão, o valor “1” é escolhido para a sua posição correspondente no IBJ. Caso contrário, o valor “0” é atribuído. Para o vetor “A”, pode-se notar que somente as duas primeiras posições do vetor possuem o valor “1”, pois somente estas duas linhas da tabela de fatos correspondem às chaves da tabela de dimensão mapeadas pelo valor “A” na coluna s_address. As outras posições do vetor não dizem respeito a esta linha da tabela de dimensão e, portanto, recebem o valor “0”.
CAPÍTULO 3 - Processamento de Consultas Análiticas 39
O processamento de uma consulta envolvendo tais índices envolve a execução de operações lógicas bit-a-bit nos índices pertinentes para posterior cálculo da resposta utilizando os valores da tabela de fatos correspondendo aos registros cujo resultado final foi ‘1’ nos cálculos bit-a-bit. No exemplo da Figura 6, a consulta “qual o total de vendas para os endereços C e E” seria respondida fazendo- se uma operação OR bit-a-bit entre os vetores C e E. O resultado desta operação indicaria que a soma dos valores de lo_revenue nas linhas 4,5,6 e 8 da tabela de fatos corresponde à resposta desejada.
Apesar da facilidade de representação com zeros e uns, até índices bitmap apresentaram dificuldades de escalabilidade ao enfrentar o grande número de registros encontrados em um DW. As três técnicas apresentadas a seguir foram idealizadas pelos pesquisadores para enfrentar tais problemas.
Binning
A técnica de Binning apresentada por Wu, Stockinger e Shoshani (2008) consiste no agrupamento de várias chaves das tabelas de dimensão em estruturas
Figura 6: Exemplo de construção de IBJs – adaptado de Siqueira (2009) e O’Neil e Graefe (1995)
CAPÍTULO 3 - Processamento de Consultas Análiticas 40
de bitmap semelhantes chamadas “bins” (compartimentos, em tradução livre) e, assim, requerer menos sequências de bitmap para codificar uma certa coluna.
Como exemplo, observa-se na Figura 7 como uma coluna numérica com valores entre 0 e 100 pode ser dividida em intervalos de 20 e mapeada em cinco compartimentos distintos. Apesar da economia de espaço, a técnica envolve a adição de uma fase de refinamento da solução, uma vez que falsos candidatos podem ser incluídos. Para consultas de valores fixos (“quais os registros onde 𝑋 = 26,9”, por exemplo), o compartimento B1 é retornado, mas há a necessidade de
refinamento da resposta, uma vez que o registro 1 também faria parte da solução erroneamente. O grande ganho vem com as consultas por intervalos onde os compartimentos totalmente contidos nos intervalos da consulta podem ser retornados sem processamento adicional. O exemplo da figura mostra que, para uma consulta onde 35 ≤ 𝑋 ≤ 65, o compartimento B2 pode ser incluído sem
refinamento enquanto os compartimentos B1 e B3 irão precisar deste para retornar a
solução correta.
Apesar da possível introdução de uma fase de refinamento, os ganhos obtidos com a exclusão de compartimentos são maiores fazendo compensar a utilização da técnica.
Figura 7: Exemplo da técnica de binning – adaptada de Wu, Stockinger e Shoshani (2008)
CAPÍTULO 3 - Processamento de Consultas Análiticas 41
Compressão
A compressão em IBJs foi introduzida por Wu, Otoo e Arie (2006) através de um algoritmo especializado de compressão de dados bitmap chamado WAH (Word Aligned Hybrid code).
Devido à própria natureza de um DW de conter um grande número de registros a serem mapeados entre a tabela de fatos e suas tabelas de dimensão, os vetores de bits são muitas vezes “esparsos” significando que contêm grandes sequências de ‘0’s e ‘1’s consecutivos. O algoritmo WAH se vale dessa propriedade separando o vetor de bits em partes iguais (de tamanho 31 ou 63 – de acordo com a arquitetura do processador) e criando dois tipos de interpretação dos dados chamados ‘cauda’ e ‘preenchimento’. Caudas possuem ‘0’ como bit inicial indicando que as posições de bits restantes precisam ser respeitadas da maneira como estão. Preenchimentos começam com o bit ‘1’, têm o segundo bit indicando o qual valor deve ser repetido (‘0’ ou ‘1’) naquele bloco e o restante dos bits indicando a quantidade de blocos a serem repetidos com o mesmo valor.
No exemplo dado pelo artigo (Figura 8), um vetor contendo 5456 bits (e separado por blocos de 31 posições) pôde ser representado utilizando-se 96 bits (uma cauda inicial seguida por um bloco de preenchimento indicando 174*31 bits com valor ‘0’ e finalizado por um último bloco de cauda).
CAPÍTULO 3 - Processamento de Consultas Análiticas 42
A exemplo da técnica de binning, a compressão também adiciona processamento dos registros para leitura e escrita dos seus valores, mas os ganhos com economia de espaço fazem compensar a utilização da técnica.
Codificação
A técnica de codificação foi apresentada por Wu e Buchmann (1998) e tem seu ponto central na utilização de códigos binários representando os valores do domínio de dados encontrado na coluna a ser codificada com os vetores de bits sendo criados no número de bits usado em tal codificação (ao invés de um vetor de bits para cada valor do domínio).
A Figura 9 mostra o exemplo do artigo onde uma coluna com 5 valores caractere (‘a’ a ‘e’) – que requereriam 5 vetores de bits para o mapeamento (item ‘a’ da figura) – pôde ser codificada usando-se 3 bits (000 para ‘a’, 001 para ‘b’, e assim por diante) e o mesmo mapeamento pôde ser feito utilizando-se os 3 vetores codificados (ao invés dos 5 iniciais), como mostrado no item ‘b’ da figura. Extrapolando a ideia, poder-se-ia ter um domínio de dados com 1 milhão de valores podendo ser codificados em apenas 20 vetores (ao invés dos 1 milhão de vetores iniciais). A contrapartida é que os valores do resultado precisam ser decodificados antes de serem retornados, mas, mais uma vez, tal custo é aceitável quando se leva
Figura 9: Exemplo de codificação de índices binários – adaptado de Wu e Buchmann (1998)
CAPÍTULO 3 - Processamento de Consultas Análiticas 43
em consideração a economia no número de vetores e nos cálculos que podem ser feitos ao utilizá-los.