Faz sentido de “falsos” índices de bitmap?

Question

Estou planejando software que é uma aplicação OLAP em seu coração (que ajuda a analisar dados de medição) e vai ter algum tipo de esquema em estrela para seu banco de dados, porque os valores armazenados serão olhou para a partir de ângulos diferentes (tempo, fonte, tipo, etc.) e os pedidos será pedir dados agregados ao longo destas dimensões. As consultas tendem a oferecer uma grande quantidade de linhas (até cerca de 100 000).

A minha investigação sobre este tema (ver também minha pergunta aqui ) parece indicar que os índices de bitmap são uma boa maneira de procurar os dados do jeito que eu estou planejando. No entanto, eu quero suportar vários motores db, alguns dos quais não oferecem índices bitmap em suas mesas (em particular, MySQL).

Agora, eu certamente pode construir e manter meu próprio índice de bitmap e usá-lo para procurar IDs de linha apontando para a tabela de fatos. No entanto, eu suspeito que isso vai derrotar todo o propósito do índice, porque o banco de dados ainda está indo para procurar IDs de linha em um B-Tree. Poderia alguém com formação teórica mais profunda ou mais experiência me dizer se eu ainda ganhar qualquer coisa, como não ter que fazer lenta JOINs em tabelas de dimensão?

Eu também gostaria de receber dicas sobre o que eu tenho para avaliar se a resposta não é simples.

Answer 1

Alguns motores DB que não suportam diretamente índices de bitmap ainda tem optimizações estrelas que podem fazer este tipo de consulta sem bater a tabela de fatos. SQL Server, por exemplo, tem um recurso chamado Index Intersection que faz algo semelhante com a construção de bitmaps em tempo real para fazer a resolução. Microsoft reivindicações que o desempenho é comparável a índices de bitmap. Consulte Esta postagem para um pouco de fan-out sobre este tema.

Eu não tenho certeza fora do topo da minha cabeça se o MySQL faz isso, mas o PostgreSQL certamente faz. IIRC algumas das variantes (Greenplum, eu acho) também diretamente índices de bitmap de apoio e houve alguma conversa de incorporá-lo no motor DB principal. Não me lembro se isso foi feito ainda.

Eu acho que você vai descobrir que a maioria das plataformas modernas DBMS oferecer otimizações de consulta estrela de um tipo ou outro, então você provavelmente não precisa se re-inventar a roda. Você pode encontrar um ou dois que não pode fazer isso, mas você sempre tem a opção de simplesmente não apoiá-los.

Answer 2

Eu tive sorte com os índices bitmap ao manipular uma grande quantidade de dados na memória usando estruturas de dados personalizados, mas eles são uma espécie de estranho para implementar ao longo de um banco de dados de terceiros que não tem um bom (postgresql-like ) API para estender as suas estruturas de índice.

Em geral, uma vez que você vai estar procurando através de um índice B-Tree de qualquer maneira você não vai ganhar nada se minha experiência é qualquer guia.

Assim, não.

Se o seu aplicativo é inerentemente OLAP na natureza e você tem um pequeno número de dimensões que naturalmente grupo em intervalos ordenados, e você realmente precisa para mudar as asymptotics de seu problema, você pode considerar a construção de uma 'mesa soma' como a estrutura, em seguida, você pode consultá-lo para qualquer resposta hierárquica com 2 operações ^ d, e você pode amortizar que, se você está fazendo uma série de consultas relacionadas.

Um exemplo em 2D com coordenadas X e Y, em que você está interessado na soma sobre uma gama de (x1, y1) para (x2, y2).

armazenados separadamente você teria que somar um número de entradas proporcional à área.

Usando um sumtable, para cada posição (x, y) não armazenar o valor dessa posição, mas em vez armazenar a soma da região a partir de (0,0) para (x, y).

Depois, você pode responder a qualquer consulta gama perguntando:

sum (x2, y2) - soma (x1, y2) - soma (x2, y1) + soma (x1, y1)

uma quantidade constante de sobrecarga (bem, logarítmica no tamanho do conjunto de dados, assumindo que tem um índice em x e y e são armazenando-o no SQL)

Isto, obviamente, pausas para baixo se você tem complicado atributos que não quebram em intervalos, mas podem lidar com índices lexicográficas simples, datas, etc.