GoSuda

Lebhafte Bitmap

By snowmerak
views ...

Was ist eine Bitmap?

Eine Bitmap ist hier eine Art von Index. Falls Sie an Grafiken gedacht haben, können Sie jetzt zurückgehen.

Grundlegendes Konzept

Eine Bitmap ist eine Form der Indizierungstechnologie in Datenbanken. Sie stellt die Werte einer bestimmten Spalte als ein Bit-Array oder als ein Element bzw. eine Form eines Vektors dar, wobei jedes Bit angibt, ob ein bestimmter Wert in der entsprechenden Spalte vorhanden ist. Die grundlegendste Form besteht daher darin, jeder Zeile einen Bit-Index zuzuweisen und das Vorhandensein als 0 oder 1 darzustellen.

Nehmen wir zum Beispiel an, wir haben eine Tabelle mit einer Geschlechtsspalte. Diese Tabelle hat 5 Zeilen, und die Werte der Geschlechtsspalte sind wie folgt:

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

In diesem Fall könnte der Bitmap-Index für die Geschlechtsspalte wie folgt dargestellt werden:

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

Wo wird sie wirklich eingesetzt?

Man wird wohl denken, dass dies nicht nur zur Darstellung dient. Um den Bitmap-Index richtig zu nutzen, betrachten wir den 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);

Nehmen wir an, diese Tabelle enthält 1.000.000 Zeilen. Und wir führen die folgende Abfrage aus:

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

Diese Abfrage sucht nach Zeilen, bei denen die Spalten active und sex beide TRUE sind. Die schnellste Methode, Zeilen zu finden, die die Bedingung erfüllen, dass beide Spalten TRUE sind, wäre die Verwendung einer bitweisen AND-Operation.

  • Angenommen, der Bitmap-Index für die active-Spalte ist 1100110011... (ein Bit-Array von 1.000.000 Bits) und wurde bereits indiziert,
  • und der Bitmap-Index für die sex-Spalte ist 1010101010... (ein Bit-Array von 1.000.000 Bits) und wurde bereits indiziert.

Dann kann durch Ausführen einer bitweisen AND-Operation auf die beiden Bitmap-Indizes schnell die Zeile gefunden werden, bei der beide Spalten TRUE sind. Da es sich um eine einfache Bit-Operation handelt, wird das Ergebnis viel schneller erzielt als bei anderen Index-Scans.

Kompromisse

Bitmap-Indizes können sehr effizient sein, aber es gibt einige Kompromisse. Es gibt viele andere Nachteile, aber wir werden uns jetzt nur auf einen konzentrieren.

Bitmap-Indizes sind besser für niedrige Kardinalität geeignet (d.h. wenn die Anzahl der möglichen Werte in einer Spalte gering ist). Wenn Bitmap-Indizes für Spalten mit hoher Kardinalität verwendet werden, kann die Bitmap sehr groß werden.

Die Verwendung eines Bitmap-Indexes für Spalten mit hoher Kardinalität erfordert die Erzeugung einer separaten Bitmap für jeden eindeutigen Wert, was einen erheblichen Speicherplatzbedarf mit sich bringen kann. Wenn eine Spalte beispielsweise 1.000.000 eindeutige Werte enthält, müssten 1.000.000 Bitmaps generiert werden, was äußerst ineffizient sein kann.

Deswegen verwenden wir

Um Bitmaps bei hoher Kardinalität zu ersetzen, kann eine sogenannte Roaring Bitmap verwendet werden. Eine Roaring Bitmap weist verschiedene Eigenschaften auf, doch die größte zugrundeliegende Philosophie und Eigenschaft ist die dynamische Auswahl der am besten geeigneten Speicherart je nach Datendichte, um sowohl die Kompressionsrate als auch die Verarbeitungsgeschwindigkeit zu maximieren.

Grundlegendes Konzept der Roaring Bitmap

Zweistufige Indizierung

Um eine einzelne Ganzzahl zu speichern, durchläuft eine Roaring Bitmap zunächst die folgenden zwei Schritte. Obwohl es sich um eine zweistufige Indizierung handelt, kann man es sich einfach als ein zweidimensionales Array vorstellen.

  • Extrahieren der oberen 16 Bit: Die oberen 16 Bit der Ganzzahl werden extrahiert und als Index verwendet. Dies wird der Index des äußeren Arrays in einem zweidimensionalen Array mit einer Gesamtlänge von 65536. Dieses Array speichert die Adressen der Container, die später beschrieben werden.
  • Extrahieren der unteren 16 Bit: Die unteren 16 Bit der Ganzzahl werden extrahiert und als Position innerhalb des Containers verwendet.

Container

Dieser Container entspricht dem inneren Array des soeben erwähnten zweidimensionalen Arrays. Im Gegensatz zu den oberen 16 Bit variiert die interne Struktur dieses Containers jedoch je nach der Menge der enthaltenen Daten. Roaring Bitmap unterstützt die folgenden drei Containertypen:

  • Array Container: Dieser Container wird verwendet, wenn wenige Daten intern gespeichert werden. Konkret wird er für die Speicherung von bis zu 4096 Elementen verwendet. Dieser Container ist einfach als sortiertes Array von Ganzzahlen implementiert. Elemente können durch binäre Suche gefunden werden.
  • Bitmap Container: Dieser Container wird verwendet, wenn viele Daten intern gespeichert werden. Konkret wird er für die Speicherung von mehr als 4096 Elementen verwendet. Dieser Container ist als 65536 Bit (8192 Byte) Bitmap implementiert. Jedes Bit zeigt an, ob die Ganzzahl an der entsprechenden Position vorhanden ist oder nicht.
  • Run Container: Dieser Container wird verwendet, um eine Reihe von aufeinanderfolgenden Ganzzahlen zu speichern. Er ist beispielsweise effizient, um aufeinanderfolgende Ganzzahlen wie 1, 2, 3, 4, 5 zu speichern. Dieser Container ist als Liste von (Startwert, Länge)-Paaren implementiert. Wenn alle vorhanden sind? Dann bedeutet dies einfach, dass sie von Anfang bis Ende alle vorhanden sind, sodass nur (0, 65536) gespeichert werden muss.

Diese Methode ermöglicht es der Roaring Bitmap, den Speicher sehr effizient zu nutzen und eine optimale Leistung für verschiedene Datendichten zu bieten.

Funktionen der Roaring Bitmap

Grundlegende Funktionen

Die Roaring Bitmap bietet die folgenden grundlegenden Funktionen:

  • Einfügen: Fügt eine neue Ganzzahl zur Bitmap hinzu. Dabei wird der geeignete Container ausgewählt oder bei Bedarf konvertiert.
  • Löschen: Entfernt eine vorhandene Ganzzahl aus der Bitmap. Auch hier erfolgt eine entsprechende Verarbeitung je nach Zustand des Containers.
  • Suchen: Überprüft, ob eine bestimmte Ganzzahl in der Bitmap vorhanden ist. Dieser Vorgang wird sehr schnell ausgeführt.

Mengenoperationen

Die Roaring Bitmap unterstützt auch 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 für den Containertyp der Bitmap optimiert und werden sehr schnell ausgeführt.

In der Sprache Go

In der Sprache Go kann man das github.com/RoaringBitmap/roaring-Paket verwenden, um Roaring Bitmap einfach zu nutzen. Dieses Paket bietet alle Funktionen der Roaring Bitmap und ist an die Besonderheiten der Sprache Go angepasst und optimiert.

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)     // Initialisierung mit 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialisierung mit 2, 4, 6, 8, 12
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	// Da Bitmap-Operationen das Original ändern, wird eine Kopie verwendet
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]

Zusätzlich zu den im obigen Beispielcode nicht gezeigten Hauptfunktionen gibt es:

  • 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 zurück, die kleiner oder gleich einem bestimmten Wert sind.
  • ToBytes() ([]byte, error): Serialisiert die Bitmap in ein Byte-Slice.
  • FromBytes(data []byte) error: Stellt die Bitmap aus einem Byte-Slice wieder her.
  • Clone() *Bitmap: Erstellt eine Kopie der Bitmap.
  • Clear(): Initialisiert die Bitmap.
  • 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 in der Bitmap zurück.
  • Minimum() uint32: Gibt das kleinste Element in der Bitmap zurück.

Weitere Details finden Sie in der offiziellen Dokumentation.

Beachten Sie, dass das roaring-Paket nicht nur uint32, sondern auch uint64 unterstützende Pakete enthält. Da sie nahezu identische Schnittstellen bieten, können sie direkt ausgetauscht und verwendet 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)     // Initialisierung mit 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialisierung mit 2, 4, 6, 8, 12
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	// Da Bitmap-Operationen das Original ändern, wird eine Kopie verwendet
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}

Fazit

Die Roaring Bitmap ist ein leistungsstarkes Werkzeug zur effizienten Speicherung und Manipulation großer Mengen von Ganzzahlen mit hoher Kardinalität. Mit dem github.com/RoaringBitmap/roaring-Paket in Go können alle Funktionen der Roaring Bitmap einfach genutzt werden. Dieses Paket maximiert Speichernutzung und Leistung durch verschiedene Containertypen und optimierte Operationen. Durch den Einsatz von Roaring Bitmap in Bereichen wie Datenbankindizierung, Log-Analyse und statistischen Berechnungen kann eine effiziente Datenverarbeitung realisiert werden.

Die Roaring Bitmap erbringt insbesondere bei großen Datensätzen eine hohe Leistung und kann in verschiedenen Anwendungen nützlich eingesetzt werden. In Kombination mit der prägnanten und effizienten Syntax von Go bietet die Roaring Bitmap Entwicklern ein leistungsstarkes Werkzeug. Es wird erwartet, dass die Entwicklung der Roaring Bitmap weiterhin zu mehr Funktionen und Optimierungen führen wird.

Warum habe ich das gemacht? Für die Indizierung nach Tags und schnelle Vereinigung von Mengen in Zeitreihendatenbanken.