GoSuda

Bitmap vibrante

By snowmerak
views ...

O que é um Bitmap?

Aqui, um bitmap é um tipo de índice. Se você veio pensando em gráficos, pode voltar.

Conceito Básico

Um bitmap é uma forma de tecnologia de indexação de banco de dados. Ele representa o valor de uma coluna específica como um elemento ou forma de um array de bits ou vetor, onde cada bit indica a presença ou ausência de um valor específico para essa coluna. Assim, a forma mais básica é atribuir um índice de bit a cada linha e representar a presença ou ausência com 0 e 1.

Por exemplo, suponha que temos uma tabela com uma coluna de gênero. Esta tabela tem 5 linhas, e os valores da coluna de gênero são os seguintes:

  1. Masculino
  2. Feminino
  3. Masculino
  4. Feminino
  5. Outro

Neste caso, o índice de bitmap para a coluna de gênero pode ser representado da seguinte forma:

  • Masculino: 10100
  • Feminino: 01010
  • Outro: 00001

Onde ele realmente é usado

Portanto, todos devem pensar que isso não serve apenas para representar aquilo. Para usar um índice de bitmap corretamente, vamos considerar o seguinte caso.

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

Suponha que esta tabela tenha 1.000.000 de linhas. E vamos supor que executamos a seguinte consulta.

1SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;

Esta consulta encontra linhas onde as colunas active e sex são ambas TRUE. Então, a maneira mais rápida de encontrar as linhas que satisfazem a condição de que ambas as colunas são TRUE seria usando a operação bitwise AND.

  • Suponha que o índice de bitmap para a coluna active já esteja indexado como 1100110011... (um array de bits de 1.000.000), e
  • Suponha que o índice de bitmap para a coluna sex já esteja indexado como 1010101010... (um array de bits de 1.000.000).

Então, podemos realizar uma operação bitwise AND nos dois índices de bitmap para encontrar rapidamente as linhas onde ambas as colunas são TRUE. Como é uma operação bitwise simples, podemos obter resultados muito mais rapidamente do que com outras varreduras de índice.

Trade-offs

Os índices de bitmap podem ser muito eficientes, mas há alguns trade-offs. Embora existam muitas outras desvantagens, abordaremos apenas uma agora.

Os índices de bitmap são mais adequados para baixa cardinalidade (ou seja, quando o número de valores possíveis em uma coluna é pequeno). Usar um índice de bitmap em uma coluna de alta cardinalidade pode fazer com que o bitmap se torne muito grande.

Se um índice de bitmap for usado em uma coluna de alta cardinalidade, pode ser necessário muito espaço de armazenamento, pois um bitmap separado deve ser criado para cada valor exclusivo. Por exemplo, se uma coluna tiver 1.000.000 de valores exclusivos, 1.000.000 de bitmaps teriam que ser criados, o que pode ser muito ineficiente.

Então, nós

Podemos usar o Roaring Bitmap como alternativa ao bitmap que surge da alta cardinalidade. O Roaring Bitmap tem várias características, mas sua maior filosofia e característica subjacente é selecionar dinamicamente o método de armazenamento mais adequado com base na densidade dos dados para maximizar tanto a taxa de compressão quanto a velocidade de operação.

Conceitos Básicos do Roaring Bitmap

Indexação em 2 Níveis

Para armazenar um único inteiro, o Roaring Bitmap primeiro passa pelas seguintes 2 etapas. Embora seja chamada de indexação em 2 níveis, você pode simplesmente pensar nela como um array bidimensional.

  • Extração dos 16 bits superiores: Os 16 bits superiores do inteiro são extraídos e usados como índice. Isso se torna o índice do array externo de um array bidimensional com um comprimento total de 65536. Este array armazena o endereço do contêiner que será descrito posteriormente.
  • Extração dos 16 bits inferiores: Os 16 bits inferiores do inteiro são extraídos e usados como a posição dentro do contêiner.

Contêiner

Este contêiner corresponde ao array interno do array bidimensional que acabamos de usar como analogia. No entanto, ao contrário dos 16 bits superiores, a estrutura interna deste contêiner varia dependendo da quantidade de dados internos. O Roaring Bitmap suporta os seguintes 3 tipos de contêineres:

  • Array Container: Este contêiner é usado quando há poucos dados armazenados internamente. Especificamente, é usado para armazenar 4096 ou menos elementos. Este contêiner é implementado simplesmente como um array de inteiros ordenados. Os elementos podem ser encontrados por busca binária.
  • Bitmap Container: Este contêiner é usado quando há muitos dados armazenados internamente. Especificamente, é usado para armazenar mais de 4096 elementos. Este contêiner é implementado como um bitmap de 65536 bits (8192 bytes). Cada bit indica a presença ou ausência de um inteiro na posição correspondente.
  • Run Container: Este contêiner é usado para armazenar intervalos contínuos de inteiros. Por exemplo, é eficiente para armazenar inteiros contínuos como 1, 2, 3, 4, 5. Este contêiner é implementado como uma lista de pares (valor inicial, comprimento). Se todos estiverem presentes? Isso significa que todos estão presentes do início ao fim, então apenas (0, 65536) precisa ser armazenado.

Este método permite que o Roaring Bitmap utilize a memória de forma muito eficiente e forneça desempenho otimizado para várias densidades de dados.

Funcionalidades do Roaring Bitmap

Funcionalidades Básicas

O Roaring Bitmap oferece as seguintes funcionalidades básicas:

  • Inserção: Adiciona um novo inteiro ao bitmap. Durante este processo, um contêiner apropriado pode ser selecionado ou convertido, se necessário.
  • Exclusão: Remove um inteiro existente do bitmap. Durante este processo, o tratamento apropriado é realizado de acordo com o estado do contêiner.
  • Busca: Verifica se um inteiro específico existe no bitmap. Este processo é executado muito rapidamente.

Operações de Conjunto

O Roaring Bitmap também suporta as seguintes operações de conjunto:

  • União (Union): Cria um novo bitmap que inclui todos os elementos de dois bitmaps.
  • Interseção (Intersection): Cria um novo bitmap que inclui apenas os elementos presentes em ambos os bitmaps.
  • Diferença Simétrica (Symmetric Difference): Cria um novo bitmap que inclui elementos presentes em apenas um dos dois bitmaps.

Essas operações são otimizadas com base no tipo de contêiner do bitmap e são executadas muito rapidamente.

Na linguagem Go

Na linguagem Go, o pacote github.com/RoaringBitmap/roaring pode ser usado para utilizar o Roaring Bitmap facilmente. Este pacote fornece todas as funcionalidades do Roaring Bitmap e é otimizado para as características da linguagem Go.

Instalação

1go get github.com/RoaringBitmap/roaring/v2

Exemplo de Uso

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // Inicializa com 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inicializa com 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Adiciona 5
14	b2.Add(10) // Adiciona 10
15
16	b2.Remove(12) // Remove 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Como a operação de bitmap modifica o original, use uma cópia
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/09/08 22:16:27 xor result: [1 3 5 6 8 10]

As principais funcionalidades não mostradas no código de exemplo acima incluem:

  • Contains(x uint32) bool: Verifica se um valor específico existe no bitmap
  • GetCardinality() uint64: Retorna o número de elementos contidos no bitmap
  • Rank(x uint32) uint64: Retorna o número de elementos menores ou iguais a um valor específico
  • ToBytes() ([]byte, error): Serializa o bitmap para um slice de bytes
  • FromBytes(data []byte) error: Restaura o bitmap de um slice de bytes
  • Clone() *Bitmap: Cria uma cópia do bitmap
  • Clear(): Inicializa o bitmap
  • NextValue(x uint32) int64: Retorna o próximo elemento maior ou igual a x
  • PreviousValue(x uint32) int64: Retorna o elemento menor ou igual a x
  • Maximum() uint32: Retorna o maior elemento no bitmap
  • Minimum() uint32: Retorna o menor elemento no bitmap

Essas funcionalidades estão disponíveis. Para obter detalhes, consulte a documentação oficial.

Observe que o pacote roaring inclui um pacote que suporta uint64, além de uint32. Ele oferece uma interface quase idêntica, permitindo a substituição direta.

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // Inicializa com 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inicializa com 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Adiciona 5
14	b2.Add(10) // Adiciona 10
15
16	b2.Remove(12) // Remove 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Como a operação de bitmap modifica o original, use uma cópia
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

Conclusão

O Roaring Bitmap é uma ferramenta poderosa para armazenar e manipular eficientemente conjuntos de inteiros de alta cardinalidade. Na linguagem Go, o pacote github.com/RoaringBitmap/roaring permite que todas as funcionalidades do Roaring Bitmap sejam facilmente utilizadas. Este pacote maximiza o uso da memória e o desempenho por meio de vários tipos de contêineres e operações otimizadas. O Roaring Bitmap pode ser utilizado em diversas áreas, como indexação de bancos de dados, análise de logs e cálculos estatísticos, para implementar processamento de dados eficiente.

O Roaring Bitmap demonstra alto desempenho, especialmente em grandes conjuntos de dados, e pode ser utilmente empregado em várias aplicações. Combinado com a sintaxe concisa e eficiente da linguagem Go, o Roaring Bitmap oferece uma ferramenta robusta para os desenvolvedores. Espera-se que, com o progresso do Roaring Bitmap, mais funcionalidades e otimizações sejam realizadas.

Por que eu fiz isso? Para indexação de tags e operações de união rápidas em bancos de dados de séries temporais.