GoSuda

Mapa de bits vibrante

By snowmerak views ...

O que é um Bitmap?

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

Conceito básico

Bitmap é uma forma de técnica de indexação de banco de dados. Ele representa os valores de uma coluna específica como um array de bits ou como um elemento ou forma de um vetor, de modo que cada bit indica se um valor específico dessa coluna existe. Portanto, a forma mais básica consiste em atribuir um índice de bit a cada row e representar a existência com 0 e 1.

Por exemplo, suponha que exista uma tabela com uma coluna de sexo. Digamos que essa tabela tenha 5 rows e que os valores da coluna de sexo sejam os seguintes:

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

Nesse caso, o índice bitmap para a coluna de sexo pode ser representado da seguinte forma:

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

Então, onde ele realmente é usado?

Muitos devem pensar que isso não serve apenas para representar esses dados. Para usar o índice bitmap de forma adequada, 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 essa tabela tenha 1.000.000 de rows. E vamos executar a seguinte consulta.

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

Essa consulta busca as rows em que as colunas active e sex são ambas TRUE. Nesse caso, a forma mais rápida de encontrar as rows que satisfazem a condição de que as duas colunas sejam TRUE é utilizar a operação bit and.

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

Assim, ao executar a operação bit and sobre os dois índices bitmap, é possível encontrar rapidamente as rows em que ambas as colunas são TRUE. Por se tratar de uma simples operação de bits, o resultado pode ser obtido muito mais rapidamente do que com outras varreduras de índice.

Trade-offs

Os índices bitmap podem ser muito eficientes, mas apresentam alguns trade-offs. Há muitas outras desvantagens, mas por ora vamos abordar apenas uma.

Trata-se de que os índices bitmap são mais adequados para cardinalidade baixa (ou seja, quando a coluna possui poucos valores possíveis). Ao usar um índice bitmap em uma coluna de alta cardinalidade, o bitmap pode crescer muito.

Ao usar um índice bitmap em uma coluna de alta cardinalidade, é necessário criar um bitmap separado para cada valor único, o que pode exigir muito espaço de armazenamento. Por exemplo, se a coluna tiver 1.000.000 de valores únicos, será preciso criar 1.000.000 de bitmaps, o que pode ser extremamente ineficiente.

Então, o que fazemos

Para substituir os bitmaps que surgem em alta cardinalidade, é possível usar algo chamado Roaring Bitmap. O Roaring Bitmap possui várias características, mas sua principal filosofia e propriedade fundamental é selecionar dinamicamente a forma de armazenamento mais adequada de acordo com a densidade dos dados, maximizando tanto a taxa de compressão quanto a velocidade das operações.

Conceitos básicos do Roaring Bitmap

Indexação em dois níveis

O Roaring Bitmap passa por as seguintes duas etapas para armazenar um inteiro. Embora se chame indexação em dois níveis, basta pensar nela como um array bidimensional.

  • Extração dos 16 bits superiores: extrai os 16 bits superiores do inteiro e os utiliza como índice. Trata-se do índice do array externo entre um array bidimensional com comprimento total de 65536. Esse array armazena o endereço do contêiner, descrito adiante.
  • Extração dos 16 bits inferiores: extrai os 16 bits inferiores do inteiro e os utiliza como posição dentro do contêiner.

Contêineres

Este contêiner corresponde ao array interno do array bidimensional, conforme a analogia feita há pouco. No entanto, diferentemente do array dos 16 bits superiores, a estrutura interna deste contêiner varia de acordo com a quantidade de dados que ele contém. O Roaring Bitmap suporta os seguintes 3 tipos de contêineres.

  • Array Container: é utilizado quando a quantidade de dados armazenados internamente é pequena. Especificamente, é usado para armazenar até 4096 elementos. Esse contêiner é implementado simplesmente como um array de inteiros ordenado. É possível localizar um elemento por busca binária.
  • Bitmap Container: é utilizado quando a quantidade de dados armazenados internamente é grande. Especificamente, é usado para armazenar mais de 4096 elementos. Esse contêiner é implementado como um bitmap de 65536 bits (8192 bytes). Cada bit indica se o inteiro na posição correspondente existe.
  • Run Container: é utilizado para armazenar intervalos contínuos de inteiros. Por exemplo, é eficiente para armazenar inteiros contínuos como 1, 2, 3, 4, 5. Esse contêiner é implementado como uma lista de pares (valor inicial, comprimento). E se todos estiverem presentes? Isso significa que existem do início ao fim, então basta armazenar apenas (0, 65536).

Essa abordagem permite que o Roaring Bitmap utilize a memória de forma muito eficiente e forneça desempenho ótimo para diferentes 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. Nesse processo, é possível selecionar o contêiner adequado ou converter contêineres quando necessário.
  • Remoção: remove um inteiro existente do bitmap. Nesse processo também são realizados tratamentos adequados de acordo com o estado do contêiner.
  • Busca: verifica se um inteiro específico existe no bitmap. Esse processo é executado com muita rapidez.

Operações de conjunto

O Roaring Bitmap também oferece suporte às seguintes operações de conjunto.

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

Essas operações são otimizadas de acordo com o tipo de contêiner do bitmap e são executadas com muita rapidez.

Em Go

Na linguagem Go, é possível utilizar o Roaring Bitmap de forma simples por meio do pacote github.com/RoaringBitmap/roaring. Esse pacote oferece todas as funcionalidades do Roaring Bitmap e é otimizado de acordo com 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)     // inicializado com 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // inicializado 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	// As operações de bitmap alteram o original, então utilize 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]

Entre as principais funcionalidades que não aparecem no exemplo acima, temos:

  • Contains(x uint32) bool: verifica se um valor específico existe no bitmap
  • GetCardinality() uint64: retorna a quantidade de elementos contidos no bitmap
  • Rank(x uint32) uint64: retorna a quantidade de elementos menores ou iguais a um valor específico
  • ToBytes() ([]byte, error): serializa o bitmap em um slice de bytes
  • FromBytes(data []byte) error: restaura o bitmap a partir 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 anterior menor ou igual a x
  • Maximum() uint32: retorna o maior elemento do bitmap
  • Minimum() uint32: retorna o menor elemento do bitmap

Essas são algumas das funcionalidades disponíveis. Para mais detalhes, consulte a documentação oficial.

Além disso, o pacote roaring inclui um pacote que oferece suporte a uint64, além de uint32. Como ele fornece uma interface quase idêntica, pode ser substituído diretamente.

 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)     // inicializado com 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // inicializado 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	// As operações de bitmap alteram o original, então utilize 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}

Considerações finais

O Roaring Bitmap é uma ferramenta poderosa para armazenar e manipular de forma eficiente conjuntos de inteiros de alta cardinalidade. Na linguagem Go, ao utilizar o pacote github.com/RoaringBitmap/roaring, é possível aproveitar facilmente todas as funcionalidades do Roaring Bitmap. Esse pacote maximiza o uso de memória e o desempenho por meio de diversos tipos de contêineres e operações otimizadas. Em diversas áreas, como indexação de banco de dados, análise de logs e cálculo estatístico, é possível utilizar o Roaring Bitmap para implementar um processamento de dados eficiente.

O Roaring Bitmap apresenta desempenho especialmente elevado em conjuntos de dados em grande escala e pode ser útil em diversas aplicações. Combinado com a sintaxe concisa e eficiente da linguagem Go, o Roaring Bitmap oferece aos desenvolvedores uma ferramenta poderosa. Espera-se que, com o avanço do Roaring Bitmap, mais funcionalidades e otimizações sejam implementadas no futuro.

Por que eu fiz isso? Foi para a indexação de cada tag em um banco de dados de séries temporais e para operações de união rápidas.