Como os índices de bitmap são úteis? - banco de dados, algoritmo, design de banco de dados, indexação, bitmap

Wikipedia dá este exemplo

Identifier    Gender         Bitmaps
F    M
1           Female            1    0
2           Male              0    1
3           Male              0    1
4           Unspecified       0    0
5           Female            1    0

Mas eu não entendo isso.

• Em primeiro lugar, como isso é um índice? Não é suposto um índice apontar para linhas (usando rowid) dada a chave?
• Quais seriam as consultas típicas em que esses índices seriam úteis? Como eles são melhores do que os índices de árvore B? Eu sei que se usarmos um índice de árvore B em Gender aqui, teremos muitos resultados se, por exemplo, procurarmos Gender = Male, que precisam ser filtrados posteriormente (portanto, não são muito úteis). Como um bitmap melhora a situação?

Respostas:

33 para resposta № 1

Uma representação melhor de um índice de bitmap é dada a amostra acima:

Identifier    Gender          RowID
1             Female          R1
2             Male            R2
3             Male            R3
4             Unspecified     R4
5             Female          R5

o índice de bitmap na coluna de gênero seria (conceitualmente) assim:

Gender       R1    R2   R3   R4   R5
Female       1     0    0    0    1
Male         0     1    1    0    0
Unspecified  0     0    0    1    0

Índices de bitmap são usados ​​quando o número de valores distintos em uma coluna é relativamente baixo (considere o oposto, onde todos os valores são únicos: o índice de bitmap seria tão largo quanto todas as linhas, e desde que seja como uma grande matriz de identidade.)

Portanto, com este índice implementado, uma consulta como

SELECT * FROM table1 WHERE gender = "Male"

o banco de dados procura uma correspondência nos valores de gênero no índice, encontra todos os rowids onde o bit foi definido como 1 e, em seguida, vai e obtém os resultados da tabela.

Uma consulta como:

SELECT * FROM table1 WHERE gender IN ("Male", "Unspecified")

obteria 1 bit para Male, 1 bit para Unspecified, faria um bit a bit-OR e depois obteria as linhas em que os bits resultantes fossem 1.

Portanto, as vantagens de usar um índice de bitmap sobre umO índice b * tree é o armazenamento (com baixa cardinalidade, os índices de bitmap são bastante compactos) e a capacidade de fazer operações bit a bit antes de resolver os rowids reais, o que pode ser bem rápido.

Observe que os índices de bitmap podem ter desempenhoimplicações com inserções / exclusões (conceitualmente, você adiciona / remove uma coluna de / para o bitmap e a reorganiza de acordo ...) e pode criar muita contenção, pois uma atualização em uma linha pode bloquear toda a entrada de bitmap correspondente e você não pode atualizar uma linha diferente (com o mesmo valor de bitmap) até que a primeira atualização seja confirmada / revertida.

---

12 para resposta № 2

O benefício vem ao filtrar em várioscolunas, os índices correspondentes podem ser mesclados com operações bit a bit antes de selecionar os dados. Se você tem gênero, cor dos olhos, cor do cabelo então a consulta

select * from persons where
gender = "male" and
(eye_colour = "blue" or hair_colour = "blonde")

faria primeiro um bit a bit ou entre oseye_colour ["blue"] index e hair_colour ["blonde"] index e finalmente bit a bit e entre o resultado e o gênero ["male"] index. Esta operação tem um desempenho muito rápido tanto computacionalmente quanto de E / S.
O fluxo de bits resultante seria usado para selecionar as linhas reais.

Os índices de bitmap são normalmente usados ​​em "star joins" em aplicativos de data warehouse.

---

4 para resposta № 3

Conforme indicado no artigo da Wikipedia, eles usam operações bit a bit, que podem ter um desempenho melhor do que comparar tipos de dados, como inteiros, portanto, a resposta curta é o aumento da velocidade das consultas.

Teoricamente, deve levar menos cálculos e menos tempo para selecionar todos os homens ou todas as mulheres de seu exemplo.

Só de pensar em como isso funciona nos bastidoresdeve tornar óbvio por que isso é mais rápido. Um bit é logicamente verdadeiro ou falso. Se você quiser fazer uma consulta usando uma cláusula WHERE, isso acabará avaliando como verdadeiro ou falso para os registros, a fim de determinar se deve incluí-los em seus resultados.

Prefácio - o resto deve ser usado para leigos e não-técnicos

Portanto, a próxima pergunta é o que é necessário para avaliar como verdadeiro? Mesmo a comparação de valores numéricos significa que o computador tem que ...

1. Aloque memória para o valor que deseja avaliar
2. Alocar memória para o valor de controle
3. Atribua o valor a cada um (conte como duas etapas)
4. Compare os dois - para um numérico isso deve ser rápido, mas para strings, há mais bytes para comparar.
5. Atribua os resultados a um valor 0 (falso) ou 1 (verdadeiro).

repetir se você estiver usando uma cláusula where de parte múltipla, como Onde "isto = isto E aquilo = aquilo"

6. realizar operações bit a bit nos resultados gerados na etapa 5
7. Encontre o valor final
8. desalocar a memória alocada nas etapas 1-3

Mas usando a lógica bit a bit, você está apenas olhando para os valores 0 (falso) e 1 (verdadeiro). 90% da sobrecarga para o trabalho de comparação é eliminada.

---