GoSuda

Lebendige Bitmap

By snowmerak views ...

Was ist eine Bitmap?

Bitmap bezeichnet hier eine Art von Index. Falls Sie mit dem Begriff Grafik gekommen sind, können Sie einfach zurückgehen.

Grundkonzept

Eine Bitmap ist eine Form der Indexierungstechnik in Datenbanken. Die Werte einer bestimmten Spalte werden als Bitarray oder als ein Element bzw. eine Form eines Vektors dargestellt, wobei jedes Bit angibt, ob ein bestimmter Wert dieser Spalte vorhanden ist. Die grundlegendste Form besteht daher darin, jeder Zeile einen Bitindex zuzuweisen und das Vorhandensein durch 0 und 1 darzustellen.

Angenommen, es gibt eine Tabelle mit einer Spalte für das Geschlecht. Diese Tabelle enthält 5 Zeilen, und die Werte der Geschlechtsspalte lauten wie folgt:

  1. Männlich
  2. Weiblich
  3. Männlich
  4. Weiblich
  5. Divers

In diesem Fall kann der Bitmap-Index für die Geschlechtsspalte folgendermaßen dargestellt werden:

  • Männlich: 10100
  • Weiblich: 01010
  • Divers: 00001

Wofür wird er tatsächlich verwendet?

Sicherlich denken nun viele, dass er nicht nur zur bloßen Darstellung dieser Werte dient. Um den Bitmap-Index sinnvoll einzusetzen, betrachten wir folgenden Fall.

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);

Angenommen, diese Tabelle enthält 1.000.000 Zeilen. Außerdem werde folgende Abfrage ausgeführt.

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

Diese Abfrage sucht Zeilen, in denen sowohl die Spalte active als auch die Spalte sex TRUE sind. Der schnellste Weg, Zeilen zu finden, die beide Bedingungen erfüllen, ist die Verwendung einer bitweisen UND-Operation.

  • Für die Spalte active ist ein Bitmap-Index 1100110011... (ein Bitarray mit 1.000.000 Bits) bereits vorab indexiert.
  • Für die Spalte sex ist ein Bitmap-Index 1010101010... (ein Bitarray mit 1.000.000 Bits) bereits vorab indexiert.

Durch die bitweise UND-Operation auf beiden Bitmap-Indizes lassen sich die Zeilen, in denen beide Spalten TRUE sind, schnell finden. Da es sich um eine einfache Bitoperation handelt, lässt sich das Ergebnis deutlich schneller ermitteln als mit anderen Indexscans.

Kompromisse

Bitmap-Indizes können sehr effizient sein, bringen jedoch einige Kompromisse mit sich. Es gibt viele weitere Nachteile, doch hier soll nur einer besprochen werden.

Bitmap-Indizes eignen sich besonders für eine niedrige Kardinalität (also Spalten, deren Anzahl möglicher Werte gering ist). Werden Bitmap-Indizes auf Spalten mit hoher Kardinalität angewendet, kann die Bitmap sehr groß werden.

Bei einer Spalte mit hoher Kardinalität muss für jeden eindeutigen Wert eine eigene Bitmap erzeugt werden, weshalb viel Speicherplatz benötigt werden kann. Enthält eine Spalte beispielsweise 1.000.000 eindeutige Werte, müssen 1.000.000 Bitmaps erzeugt werden, was sehr ineffizient sein kann.

Was wir stattdessen nutzen

Die Bitmaps, die bei hoher Kardinalität entstehen, können durch Roaring Bitmap ersetzt werden. Roaring Bitmap besitzt viele Eigenschaften, doch sein wichtigstes Grundprinzip und Merkmal ist, die jeweils am besten geeignete Speichermethode dynamisch in Abhängigkeit von der Datendichte auszuwählen, um sowohl die Kompressionsrate als auch die Rechengeschwindigkeit zu maximieren.

Grundkonzept der Roaring Bitmap

Zweistufige Indexierung

Um eine ganze Zahl zu speichern, durchläuft Roaring Bitmap zunächst die folgenden zwei Stufen. Auch wenn es sich um eine zweistufige Indexierung handelt, kann man sie einfach als zweidimensionales Array betrachten.

  • Extraktion der oberen 16 Bit: Die oberen 16 Bit der ganzen Zahl werden extrahiert und als Index verwendet. Es handelt sich dabei um den Index des äußeren Arrays eines zweidimensionalen Arrays mit einer Länge von insgesamt 65536. Dieses Array speichert die Adressen der weiter unten beschriebenen Container.
  • Extraktion der unteren 16 Bit: Die unteren 16 Bit der ganzen Zahl werden extrahiert und als Position innerhalb des Containers verwendet.

Container

Dieser Container entspricht, wie zuvor verglichen, dem inneren Array des zweidimensionalen Arrays. Anders als beim äußeren Array der oberen 16 Bit hängt die innere Struktur dieses Containers jedoch von der Menge der enthaltenen Daten ab. Roaring Bitmap unterstützt die folgenden 3 Container:

  • Array Container: Dieser Container wird verwendet, wenn wenige Daten gespeichert sind. Konkret wird er bei höchstens 4096 Elementen verwendet. Er ist als einfaches, sortiertes Integer-Array implementiert. Elemente können durch binäre Suche gefunden werden.
  • Bitmap Container: Dieser Container wird verwendet, wenn viele Daten gespeichert sind. Konkret wird er bei mehr als 4096 Elementen verwendet. Er ist als Bitmap mit 65536 Bit (8192 Byte) implementiert. Jedes Bit gibt an, ob die ganze Zahl an der entsprechenden Position vorhanden ist.
  • Run Container: Dieser Container wird verwendet, um zusammenhängende Bereiche von ganzen Zahlen zu speichern. Beispielsweise ist er effizient beim Speichern zusammenhängender Zahlen wie 1, 2, 3, 4, 5. Er ist als Liste von (Startwert, Länge)-Paaren implementiert. Sind alle Werte vorhanden? Dann bedeutet das, dass der gesamte Bereich vom Anfang bis zum Ende belegt ist, sodass es genügt, nur (0, 65536) zu speichern.

Auf diese Weise nutzt Roaring Bitmap den Speicher sehr effizient und kann über verschiedene Datendichten hinweg eine optimale Leistung bieten.

Funktionen der Roaring Bitmap

Grundfunktionen

Roaring Bitmap bietet die folgenden grundlegenden Funktionen:

  • Einfügen: Fügt der Bitmap eine neue ganze Zahl hinzu. Dabei kann ein geeigneter Container ausgewählt oder bei Bedarf ein Container umgewandelt werden.
  • Löschen: Entfernt eine vorhandene ganze Zahl aus der Bitmap. Auch dabei erfolgt je nach Zustand des Containers eine geeignete Verarbeitung.
  • Suche: Prüft, ob eine bestimmte ganze Zahl in der Bitmap vorhanden ist. Dieser Vorgang wird sehr schnell ausgeführt.

Mengenoperationen

Roaring Bitmap unterstützt außerdem die folgenden Mengenoperationen:

  • Vereinigung (Union): Erzeugt eine neue Bitmap, die alle Elemente beider Bitmaps enthält.
  • Schnittmenge (Intersection): Erzeugt eine neue Bitmap, die nur Elemente enthält, die in beiden Bitmaps vorhanden sind.
  • Symmetrische Differenz (Symmetric Difference): Erzeugt eine neue Bitmap, die Elemente enthält, die nur in einer der beiden Bitmaps vorhanden sind.

Diese Operationen sind abhängig vom Containertyp der Bitmaps optimiert und werden daher sehr schnell ausgeführt.

In der Programmiersprache Go

In Go lässt sich Roaring Bitmap mit dem Paket github.com/RoaringBitmap/roaring einfach nutzen. Dieses Paket stellt alle Funktionen der Roaring Bitmap bereit und ist an die Eigenheiten von Go angepasst.

Installation

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

Anwendungsbeispiel

 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)     // mit 1, 2, 3, 4 initialisieren
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // mit 2, 4, 6, 8, 12 initialisieren
12
13	b1.Add(5)  // 5 hinzufügen
14	b2.Add(10) // 10 hinzufügen
15
16	b2.Remove(12) // 12 entfernen
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Bitmap-Operationen verändern das Original, daher ein Duplikat erstellen und verwenden
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]

Zu den wichtigen Funktionen, die im obigen Beispielcode nicht vorkommen, gehören:

  • Contains(x uint32) bool: Prüft, ob ein bestimmter Wert in der Bitmap vorhanden ist
  • GetCardinality() uint64: Gibt die Anzahl der in der Bitmap enthaltenen Elemente zurück
  • Rank(x uint32) uint64: Gibt die Anzahl der Elemente kleiner oder gleich einem bestimmten Wert zurück
  • ToBytes() ([]byte, error): Serialisiert die Bitmap in einen Byte-Slice
  • FromBytes(data []byte) error: Stellt die Bitmap aus einem Byte-Slice wieder her
  • Clone() *Bitmap: Erzeugt eine Kopie der Bitmap
  • Clear(): Setzt die Bitmap zurück
  • NextValue(x uint32) int64: Gibt das nächste Element zurück, das größer oder gleich x ist
  • PreviousValue(x uint32) int64: Gibt das vorherige Element zurück, das kleiner oder gleich x ist
  • Maximum() uint32: Gibt das größte Element der Bitmap zurück
  • Minimum() uint32: Gibt das kleinste Element der Bitmap zurück

Diese Funktionen stehen zur Verfügung. Weitere Details finden Sie in der offiziellen Dokumentation.

Das roaring-Paket enthält zudem ein Paket, das neben uint32 auch uint64 unterstützt. Es bietet nahezu dieselbe Schnittstelle und kann daher direkt ersetzt werden.

 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)     // mit 1, 2, 3, 4 initialisieren
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // mit 2, 4, 6, 8, 12 initialisieren
12
13	b1.Add(5)  // 5 hinzufügen
14	b2.Add(10) // 10 hinzufügen
15
16	b2.Remove(12) // 12 entfernen
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Bitmap-Operationen verändern das Original, daher ein Duplikat erstellen und verwenden
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}

Schlussbemerkung

Roaring Bitmap ist ein leistungsstarkes Werkzeug, um Mengen ganzer Zahlen mit hoher Kardinalität effizient zu speichern und zu bearbeiten. Mit dem Paket github.com/RoaringBitmap/roaring in Go lassen sich alle Funktionen der Roaring Bitmap einfach nutzen. Das Paket maximiert durch verschiedene Containertypen und optimierte Operationen Speicherverbrauch und Leistung. Roaring Bitmap kann in vielen Bereichen wie Datenbankindexierung, Log-Analyse und Statistikberechnung eingesetzt werden, um eine effiziente Datenverarbeitung zu realisieren.

Roaring Bitmap ist besonders bei großen Datensätzen leistungsstark und lässt sich vielfältig einsetzen. In Kombination mit der einfachen und effizienten Syntax von Go stellt Roaring Bitmap Entwicklern ein leistungsfähiges Werkzeug zur Verfügung. Es ist zu erwarten, dass sich mit der Weiterentwicklung der Roaring Bitmap weitere Funktionen und Optimierungen ergeben werden.

Warum habe ich das überhaupt gemacht? Für die Indexierung einzelner Tags und schnelle Vereinigungsoperationen in einer Zeitreihendatenbank.