GoSuda

Bitmap vivace

By snowmerak
views ...

Che cos'è una Bitmap?

Qui, la bitmap è un tipo di indice. Se siete arrivati pensando alla grafica, potete tornare indietro.

Concetto Base

Una bitmap è una forma di tecnologia di indicizzazione di database. Essa rappresenta il valore di una colonna specifica come un array di bit o un elemento o una forma di un vettore, dove ogni bit indica se un valore specifico di quella colonna è presente o meno. Pertanto, la forma più elementare consiste nell'assegnare un indice di bit a ogni riga e rappresentare la presenza o assenza con 0 e 1.

Ad esempio, supponiamo di avere una tabella con una colonna "sesso". Supponiamo che questa tabella abbia 5 righe e che i valori della colonna "sesso" siano i seguenti:

  1. Maschio
  2. Femmina
  3. Maschio
  4. Femmina
  5. Altro

In questo caso, l'indice bitmap per la colonna "sesso" può essere rappresentato come segue:

  • Maschio: 10100
  • Femmina: 01010
  • Altro: 00001

Quindi, dove viene effettivamente utilizzata?

Pertanto, tutti penseranno che non sia semplicemente per rappresentare ciò. Per utilizzare correttamente un indice bitmap, consideriamo il seguente 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);

Supponiamo che questa tabella abbia 1.000.000 di righe. E supponiamo di eseguire la seguente query.

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

Questa query cerca le righe in cui le colonne active e sex sono entrambe TRUE. Il modo più rapido per trovare le righe che soddisfano la condizione in cui entrambe le colonne sono TRUE sarà utilizzare l'operazione bitwise AND.

  • Supponiamo che l'indice bitmap per la colonna active sia già indicizzato come 1100110011... (un array di bit di 1.000.000 di bit), e
  • Supponiamo che l'indice bitmap per la colonna sex sia già indicizzato come 1010101010... (un array di bit di 1.000.000 di bit).

Allora, eseguendo un'operazione bitwise AND sui due indici bitmap, possiamo trovare rapidamente le righe in cui entrambe le colonne sono TRUE. Poiché si tratta di una semplice operazione bitwise, si potranno ottenere risultati molto più velocemente rispetto ad altre scansioni di indice.

Trade-off

Gli indici bitmap possono essere molto efficienti, ma presentano alcuni trade-off. Ci sono molti altri svantaggi, ma per ora ci concentreremo solo su uno.

Gli indici bitmap sono più adatti per bassa cardinalità (cioè, quando il numero di valori possibili in una colonna è piccolo). L'utilizzo di indici bitmap su colonne con alta cardinalità può portare a bitmap molto grandi.

Se si utilizza un indice bitmap su una colonna con alta cardinalità, è necessario creare una bitmap separata per ogni valore univoco, il che può richiedere molto spazio di archiviazione. Ad esempio, se una colonna ha 1.000.000 di valori univoci, è necessario creare 1.000.000 di bitmap, il che può essere molto inefficiente.

Quindi, noi

Possiamo utilizzare qualcosa chiamato Roaring Bitmap per sostituire le bitmap che derivano da un'alta cardinalità. Roaring Bitmap ha diverse caratteristiche, ma la sua filosofia e caratteristica principale è quella di massimizzare sia il tasso di compressione che la velocità di calcolo selezionando dinamicamente il metodo di archiviazione più adatto in base alla densità dei dati.

Concetto Base di Roaring Bitmap

Indicizzazione a 2 livelli

Per archiviare un singolo intero, Roaring Bitmap segue prima i seguenti 2 passaggi. Anche se si parla di indicizzazione a 2 livelli, si può semplicemente pensarla come un array bidimensionale.

  • Estrazione dei 16 bit superiori: I 16 bit superiori dell'intero vengono estratti e usati come indice. Questo diventa l'indice dell'array esterno di un array bidimensionale con una lunghezza totale di 65536. Questo array memorizza gli indirizzi dei container, di cui si parlerà più avanti.
  • Estrazione dei 16 bit inferiori: I 16 bit inferiori dell'intero vengono estratti e usati come posizione all'interno del container.

Contenitori

Questo contenitore corrisponde all'array interno dell'array bidimensionale, come illustrato in precedenza. Tuttavia, a differenza dei 16 bit superiori, la struttura interna di questo contenitore cambia a seconda della quantità di dati al suo interno. Roaring Bitmap supporta i seguenti 3 tipi di contenitori.

  • Array Container: Questo contenitore viene utilizzato quando ci sono pochi dati memorizzati al suo interno. Nello specifico, viene utilizzato per memorizzare fino a 4096 elementi. Questo contenitore è semplicemente implementato come un array ordinato di interi. Gli elementi possono essere trovati tramite ricerca binaria.
  • Bitmap Container: Questo contenitore viene utilizzato quando ci sono molti dati memorizzati al suo interno. Nello specifico, viene utilizzato per memorizzare più di 4096 elementi. Questo contenitore è implementato come una bitmap di 65536 bit (8192 byte). Ogni bit indica se l'intero in quella posizione è presente o meno.
  • Run Container: Questo contenitore viene utilizzato per memorizzare intervalli di interi consecutivi. Ad esempio, è efficiente per memorizzare interi consecutivi come 1, 2, 3, 4, 5. Questo contenitore è implementato come una lista di coppie (valore iniziale, lunghezza). Se ci sono tutti? Significa semplicemente che ci sono tutti dall'inizio alla fine, quindi è necessario memorizzare solo (0, 65536).

Questo approccio consente a Roaring Bitmap di utilizzare la memoria in modo molto efficiente e di fornire prestazioni ottimali per varie densità di dati.

Funzionalità di Roaring Bitmap

Funzionalità Base

Roaring Bitmap offre le seguenti funzionalità di base:

  • Inserimento: Aggiunge un nuovo intero alla bitmap. Durante questo processo, è possibile selezionare un contenitore appropriato o convertire un contenitore se necessario.
  • Eliminazione: Rimuove un intero esistente dalla bitmap. Anche in questo processo, viene eseguita un'elaborazione appropriata in base allo stato del contenitore.
  • Ricerca: Controlla se un intero specifico esiste nella bitmap. Questo processo viene eseguito molto rapidamente.

Operazioni sugli Insiemi

Roaring Bitmap supporta anche le seguenti operazioni sugli insiemi:

  • Unione (Union): Crea una nuova bitmap contenente tutti gli elementi di due bitmap.
  • Intersezione (Intersection): Crea una nuova bitmap contenente solo gli elementi presenti in entrambe le bitmap.
  • Differenza simmetrica (Symmetric Difference): Crea una nuova bitmap contenente gli elementi presenti solo in una delle due bitmap.

Queste operazioni sono ottimizzate in base al tipo di contenitore della bitmap e vengono eseguite molto rapidamente.

Nel linguaggio Go

Nel linguaggio Go, è possibile utilizzare facilmente Roaring Bitmap utilizzando il pacchetto github.com/RoaringBitmap/roaring. Questo pacchetto fornisce tutte le funzionalità di Roaring Bitmap ed è ottimizzato per le caratteristiche del linguaggio Go.

Installazione

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

Esempio di utilizzo

 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)     // Inizializza con 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inizializza con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Aggiunge 5
14	b2.Add(10) // Aggiunge 10
15
16	b2.Remove(12) // Rimuove 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Poiché le operazioni bitmap modificano l'originale, usa una copia
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]

Le funzionalità principali non presenti nel codice di esempio precedente includono:

  • Contains(x uint32) bool: Verifica se un valore specifico esiste nella bitmap.
  • GetCardinality() uint64: Restituisce il numero di elementi contenuti nella bitmap.
  • Rank(x uint32) uint64: Restituisce il numero di elementi minori o uguali a un valore specifico.
  • ToBytes() ([]byte, error): Serializza la bitmap in uno slice di byte.
  • FromBytes(data []byte) error: Ripristina la bitmap da uno slice di byte.
  • Clone() *Bitmap: Crea una copia della bitmap.
  • Clear(): Inizializza la bitmap.
  • NextValue(x uint32) int64: Restituisce l'elemento successivo maggiore o uguale a x.
  • PreviousValue(x uint32) int64: Restituisce l'elemento precedente minore o uguale a x.
  • Maximum() uint32: Restituisce l'elemento più grande nella bitmap.
  • Minimum() uint32: Restituisce l'elemento più piccolo nella bitmap.

Queste sono le funzionalità disponibili. Per maggiori dettagli, si prega di consultare la documentazione ufficiale.

Si noti che il pacchetto roaring include pacchetti che supportano uint64 oltre a uint32. Poiché forniscono un'interfaccia quasi identica, possono essere sostituiti direttamente.

 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)     // Inizializza con 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inizializza con 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Aggiunge 5
14	b2.Add(10) // Aggiunge 10
15
16	b2.Remove(12) // Rimuove 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Poiché le operazioni bitmap modificano l'originale, usa una copia
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}

Conclusione

Roaring Bitmap è uno strumento potente che può archiviare e manipolare in modo efficiente insiemi di interi con alta cardinalità. Nel linguaggio Go, utilizzando il pacchetto github.com/RoaringBitmap/roaring, è possibile sfruttare facilmente tutte le funzionalità di Roaring Bitmap. Questo pacchetto massimizza l'utilizzo della memoria e le prestazioni attraverso vari tipi di contenitori e operazioni ottimizzate. Roaring Bitmap può essere utilizzato in diversi campi come l'indicizzazione di database, l'analisi di log e il calcolo statistico per implementare un'elaborazione efficiente dei dati.

Roaring Bitmap eccelle in particolare nelle prestazioni con dataset di grandi dimensioni e può essere utile in varie applicazioni. Combinato con la sintassi concisa ed efficiente del linguaggio Go, Roaring Bitmap offre agli sviluppatori uno strumento potente. Ci si aspetta che Roaring Bitmap continui a evolversi con ulteriori funzionalità e ottimizzazioni in futuro.

Perché ho fatto questo? Per l'indicizzazione per tag e le operazioni di unione veloci nei database di serie temporali.