GoSuda

Bitmap vivace

By snowmerak
views ...

Cos'è una Bitmap?

La Bitmap qui è un tipo di indice. Se siete venuti pensando alla grafica, potete premere il tasto indietro.

Concetto Fondamentale

La Bitmap è una forma di tecnologia di indicizzazione di database. Rappresenta il valore di una specifica colonna come un array di bit o come un elemento o una forma di un vettore, dove ogni bit indica se un determinato valore di quella colonna è presente. Pertanto, la forma più basilare consiste nell'assegnare un indice di bit a ogni row e rappresentare la presenza con 0 o 1.

Ad esempio, si supponga di avere una tabella con una colonna per il sesso. Si assuma che questa tabella abbia 5 row 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 espresso come segue:

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

Dunque, dove viene effettivamente utilizzata

Quindi, tutti penseranno che non sia semplicemente per rappresentare ciò. Per utilizzare correttamente l'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);

Si supponga che questa tabella contenga 1.000.000 di row. E si supponga di eseguire la seguente query.

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

Questa query cerca le row in cui le colonne active e sex sono entrambe TRUE. Allora, il modo più rapido per trovare le row che soddisfano la condizione in cui entrambe le colonne sono TRUE sarebbe quello di utilizzare l'operazione bit AND.

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

Quindi, eseguendo l'operazione bit AND sui due indici Bitmap, è possibile trovare rapidamente le row in cui entrambe le colonne sono TRUE. Poiché si tratta di una semplice operazione bit, si otterrà il risultato molto più velocemente rispetto ad altre scansioni di indici.

Trade-off

L'indice Bitmap può essere molto efficiente, ma presenta alcuni trade-off. Ci sono molti altri svantaggi, ma per ora ne menzioneremo solo uno.

L'indice Bitmap è più adatto per una bassa cardinalità (cioè, quando il numero di valori possibili nella colonna è piccolo). L'utilizzo di un indice Bitmap su una colonna ad alta cardinalità può rendere la Bitmap molto grande.

Se si utilizza un indice Bitmap su una colonna ad 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

In alternativa alla Bitmap derivante dall'alta cardinalità, possiamo utilizzare qualcosa chiamato Roaring Bitmap. La Roaring Bitmap ha varie proprietà, ma la filosofia e la proprietà di base più importanti sono: selezionare dinamicamente il metodo di archiviazione più appropriato in base alla densità dei dati, massimizzando sia il tasso di compressione che la velocità di calcolo.

Concetto Fondamentale della Roaring Bitmap

Indicizzazione a 2 Livelli

Per archiviare un singolo intero, la Roaring Bitmap procede prima attraverso i seguenti 2 livelli. Sebbene si parli di indicizzazione a 2 livelli, si può semplicemente pensare a un array bidimensionale.

  • Estrazione dei 16 bit superiori: I 16 bit superiori dell'intero vengono estratti e utilizzati come indice. Questo diventa l'indice dell'array esterno di un array bidimensionale con una lunghezza totale di 65536. Questo array memorizza l'indirizzo del container che verrà descritto più avanti.
  • Estrazione dei 16 bit inferiori: I 16 bit inferiori dell'intero vengono estratti e utilizzati come posizione all'interno del container.

Container

Questo container corrisponde all'array interno dell'array bidimensionale, come nell'analogia precedente. Tuttavia, a differenza di quello dei 16 bit superiori, la struttura interna di questo container varia a seconda della quantità di dati interni. La Roaring Bitmap supporta i seguenti 3 tipi di container:

  • Array Container: Questo container viene utilizzato quando i dati archiviati all'interno sono pochi. Specificamente, viene utilizzato per archiviare meno di 4096 elementi. Questo container è implementato semplicemente come un array di interi ordinati. Gli elementi possono essere trovati tramite ricerca binaria.
  • Bitmap Container: Questo container viene utilizzato quando i dati archiviati all'interno sono molti. Specificamente, viene utilizzato per archiviare più di 4096 elementi. Questo container è implementato come una Bitmap di 65536 bit (8192 byte). Ogni bit indica la presenza o l'assenza dell'intero in quella posizione.
  • Run Container: Questo container viene utilizzato per archiviare intervalli di interi consecutivi. Ad esempio, è efficiente per archiviare interi consecutivi come 1, 2, 3, 4, 5. Questo container è implementato come una lista di coppie (valore iniziale, lunghezza). Se sono presenti tutti? Significa che sono presenti tutti dall'inizio alla fine, quindi è necessario archiviare solo (0, 65536).

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

Funzionalità della Roaring Bitmap

Funzionalità di Base

La Roaring Bitmap offre le seguenti funzionalità di base.

  • Inserimento: Aggiunge un nuovo intero alla Bitmap. Durante questo processo, può selezionare il container appropriato o convertire il container se necessario.
  • Eliminazione: Rimuove un intero esistente dalla Bitmap. Anche in questo processo, viene eseguito un trattamento appropriato a seconda dello stato del container.
  • Ricerca: Verifica se un intero specifico è presente nella Bitmap. Questo processo viene eseguito molto rapidamente.

Operazioni sugli Insiemi

La Roaring Bitmap supporta anche le seguenti operazioni sugli insiemi.

  • Unione (Union): Crea una nuova Bitmap che include tutti gli elementi di entrambe le Bitmap.
  • Intersezione (Intersection): Crea una nuova Bitmap che include solo gli elementi presenti in entrambe le Bitmap.
  • Differenza Simmetrica (Symmetric Difference): Crea una nuova Bitmap che include gli elementi presenti solo in una delle due Bitmap.

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

Nel Linguaggio Go

Nel linguaggio Go, è possibile utilizzare facilmente la Roaring Bitmap utilizzando il pacchetto github.com/RoaringBitmap/roaring. Questo pacchetto fornisce tutte le funzionalità della 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)     // Inizializzato con 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inizializzato 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	// L'operazione bitmap modifica l'originale, quindi si 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 principali funzionalità non mostrate nel codice di esempio sopra sono:

  • Contains(x uint32) bool: Verifica se un valore specifico è presente 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 una slice di byte
  • FromBytes(data []byte) error: Ripristina la Bitmap da una slice di byte
  • Clone() *Bitmap: Crea una copia della Bitmap
  • Clear(): Inizializza la Bitmap
  • NextValue(x uint32) int64: Restituisce il prossimo elemento maggiore o uguale a x
  • PreviousValue(x uint32) int64: Restituisce il prossimo elemento minore di x
  • Maximum() uint32: Restituisce l'elemento più grande nella Bitmap
  • Minimum() uint32: Restituisce l'elemento più piccolo nella Bitmap

Queste funzionalità sono disponibili. Per maggiori dettagli, si prega di fare riferimento alla documentazione ufficiale.

Si noti che il pacchetto roaring include un pacchetto che supporta uint64 oltre a uint32. Poiché fornisce quasi la stessa interfaccia, è possibile sostituirlo 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)     // Inizializzato con 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inizializzato 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	// L'operazione bitmap modifica l'originale, quindi si 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

La Roaring Bitmap è uno strumento potente per archiviare e manipolare in modo efficiente insiemi di interi ad alta cardinalità. Nel linguaggio Go, utilizzando il pacchetto github.com/RoaringBitmap/roaring, è possibile sfruttare facilmente tutte le funzionalità della Roaring Bitmap. Questo pacchetto massimizza l'utilizzo della memoria e le prestazioni attraverso vari tipi di container e operazioni ottimizzate. È possibile utilizzare la Roaring Bitmap in diversi ambiti come l'indicizzazione di database, l'analisi di log e i calcoli statistici per implementare un'elaborazione efficiente dei dati.

La Roaring Bitmap eccelle in termini di prestazioni, in particolare con dataset di grandi dimensioni, e può essere utilizzata utilmente in una varietà di applicazioni. In combinazione con la sintassi concisa ed efficiente del linguaggio Go, la Roaring Bitmap offre uno strumento potente agli sviluppatori. Si prevede che lo sviluppo della Roaring Bitmap continuerà, portando a ulteriori funzionalità e ottimizzazioni.

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