GoSuda

Livlig bitmap

By snowmerak views ...

Hvad er en bitmap?

Her er bitmap en type indeks. Hvis du kom hertil med tanke på grafik, kan du bare gå tilbage.

Grundlæggende begreber

En bitmap er en form for indekseringsteknik i databaser. Værdierne i en bestemt kolonne repræsenteres som et element i et bitarray eller en vektor, hvor hver bit angiver, om en bestemt værdi i kolonnen findes. Den mest grundlæggende form tildeler derfor hver row et bitindeks og udtrykker dens tilstedeværelse med 0 og 1.

Lad os for eksempel antage, at der findes en tabel med en kønskolonne. Denne tabel har 5 rows, og værdierne i kønskolonnen er som følger:

  1. Mand
  2. Kvinde
  3. Mand
  4. Kvinde
  5. Andet

I dette tilfælde kan bitmap-indekset for kønskolonnen udtrykkes således:

  • Mand: 10100
  • Kvinde: 01010
  • Andet: 00001

Så hvad bruger man det egentlig til

Mange vil sikkert tænke, at det ikke blot handler om at repræsentere noget sådant. For at se, hvordan man rigtigt bruger et bitmap-indeks, lad os overveje følgende tilfælde.

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

Lad os antage, at denne tabel har 1.000.000 rows, og at vi udfører følgende forespørgsel.

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

Denne forespørgsel finder de rows, hvor både active- og sex-kolonnerne er TRUE. Den hurtigste måde at finde de rows, der opfylder betingelsen om, at begge kolonner er TRUE, er at anvende bitvis AND-operation.

  • Bitmap-indekset for active-kolonnen er forudberegnet som 1100110011... (et bitarray med 1.000.000 bits),
  • og bitmap-indekset for sex-kolonnen er forudberegnet som 1010101010... (et bitarray med 1.000.000 bits).

Ved at udføre en bitvis AND-operation på de to bitmap-indekser kan vi hurtigt finde de rows, hvor begge kolonner er TRUE. Da det blot er en simpel bitoperation, kan resultatet opnås langt hurtigere end med andre indeksscanninger.

Afvejninger

Bitmap-indekser kan være meget effektive, men de har nogle afvejninger. Der findes mange andre ulemper, men lad os kun se på én her.

Nemlig at bitmap-indekser er bedst egnede til lav cardinality (det vil sige, når en kolonne har få mulige værdier). Hvis man bruger et bitmap-indeks på en kolonne med høj cardinality, kan bitmap'et blive meget stort.

Når man bruger et bitmap-indeks på en kolonne med høj cardinality, skal der oprettes en separat bitmap for hver unik værdi. Dette kan kræve megen lagerplads. Hvis en kolonne for eksempel har 1.000.000 unikke værdier, skal der oprettes 1.000.000 bitmaps, hvilket kan være yderst ineffektivt.

Så hvad gør vi?

Man kan erstatte bitmaps, der opstår ved høj cardinality, med noget, der kaldes Roaring Bitmap. Roaring Bitmap har mange egenskaber, men dets vigtigste grundlag og kendetegn er at vælge den bedst egnede lagringsmetode dynamisk ud fra datatætheden for at maksimere både komprimeringsgrad og beregningshastighed.

Grundlæggende begreber i Roaring Bitmap

Toniveau-indeksering

Roaring Bitmap gennemgår følgende to trin for at gemme et heltal. Selvom det kaldes toniveau-indeksering, kan man blot tænke på det som et todimensionelt array.

  • Udtræk de øverste 16 bits: De øverste 16 bits af heltallet udtrækkes og bruges som indeks. Det er indekset i det ydre array af et todimensionelt array med en længde på i alt 65536. Dette array gemmer adressen på den container, der beskrives nedenfor.
  • Udtræk de nederste 16 bits: De nederste 16 bits af heltallet udtrækkes og bruges som position inde i containeren.

Container

Denne container svarer til det indre array i det todimensionelle array, som vi lige har brugt som analogi. I modsætning til det ydre array med de øverste 16 bits har denne container dog en intern struktur, der varierer afhængigt af, hvor mange data den indeholder. Roaring Bitmap understøtter følgende tre typer containere.

  • Array Container: Denne container bruges, når den indeholder få data. Helt præcist bruges den, når den gemmer 4096 elementer eller færre. Den er implementeret som et simpelt sorteret heltalsarray. Elementerne kan findes ved binær søgning.
  • Bitmap Container: Denne container bruges, når den indeholder mange data. Helt præcist bruges den, når den gemmer mere end 4096 elementer. Den er implementeret som en bitmap på 65536 bits (8192 bytes). Hver bit angiver, om det heltal, der svarer til positionen, findes.
  • Run Container: Denne container bruges til at gemme sammenhængende intervaller af heltal. For eksempel er den effektiv til at gemme sammenhængende heltal som 1, 2, 3, 4 og 5. Den er implementeret som en liste af par (startværdi, længde). Hvis alle værdier er til stede? Så betyder det blot, at alt fra start til slut er til stede, og det er derfor nok kun at gemme (0, 65536).

Denne tilgang gør det muligt for Roaring Bitmap at bruge hukommelsen meget effektivt og at levere optimal ydelse for en bred vifte af datatætheder.

Funktioner i Roaring Bitmap

Grundlæggende funktioner

Roaring Bitmap tilbyder følgende grundlæggende funktioner.

  • Indsættelse: Tilføjer et nyt heltal til bitmap'et. Under denne proces kan den passende container vælges, eller containere kan konverteres efter behov.
  • Sletning: Fjerner et eksisterende heltal fra bitmap'et. Også under denne proces udføres passende håndtering afhængigt af containerens tilstand.
  • Søgning: Kontrollerer, om et bestemt heltal findes i bitmap'et. Denne proces udføres meget hurtigt.

Mængdeoperationer

Roaring Bitmap understøtter desuden følgende mængdeoperationer.

  • Forening (Union): Opretter et nyt bitmap, der indeholder alle elementer fra de to bitmaps.
  • Snit (Intersection): Opretter et nyt bitmap, der kun indeholder elementer, som findes i begge bitmaps.
  • Symmetrisk differens (Symmetric Difference): Opretter et nyt bitmap, der indeholder elementer, som kun findes i ét af de to bitmaps.

Disse operationer er optimeret efter containertypen i bitmap'et og udføres derfor meget hurtigt.

I Go-sproget

I Go-sproget kan man nemt bruge Roaring Bitmap ved hjælp af pakken github.com/RoaringBitmap/roaring. Denne pakke leverer alle funktionerne i Roaring Bitmap og er optimeret til Go-sprogets egenskaber.

Installation

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

Eksempel på brug

 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)     // Initialiseret med 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialiseret med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Tilføj 5
14	b2.Add(10) // Tilføj 10
15
16	b2.Remove(12) // Fjern 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Bitmap-operationer ændrer originalen, så en kopi oprettes og bruges
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]

Her er nogle vigtige funktioner, der ikke fremgår af eksemplet ovenfor:

  • Contains(x uint32) bool: Kontrollerer, om en bestemt værdi findes i bitmap'et
  • GetCardinality() uint64: Returnerer antallet af elementer i bitmap'et
  • Rank(x uint32) uint64: Returnerer antallet af elementer, der er mindre end eller lig med en bestemt værdi
  • ToBytes() ([]byte, error): Serialiserer bitmap'et til en byte-slice
  • FromBytes(data []byte) error: Genskaber bitmap'et fra en byte-slice
  • Clone() *Bitmap: Opretter en kopi af bitmap'et
  • Clear(): Nulstiller bitmap'et
  • NextValue(x uint32) int64: Returnerer det næste element, der er større end eller lig med x
  • PreviousValue(x uint32) int64: Returnerer det forrige element, der er mindre end eller
  • Maximum() uint32: Returnerer det største element i bitmap'et
  • Minimum() uint32: Returnerer det mindste element i bitmap'et

Disse er nogle af de tilgængelige funktioner. For flere detaljer kan du se den officielle dokumentation.

Pakken roaring indeholder desuden en pakke, der understøtter uint64 ud over uint32. Den tilbyder næsten den samme grænseflade, så den kan bruges direkte som erstatning.

 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)     // Initialiseret med 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialiseret med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Tilføj 5
14	b2.Add(10) // Tilføj 10
15
16	b2.Remove(12) // Fjern 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Bitmap-operationer ændrer originalen, så en kopi oprettes og bruges
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}

Afslutning

Roaring Bitmap er et kraftfuldt værktøj til effektivt at gemme og manipulere mængder af heltal med høj cardinality. Ved at bruge pakken github.com/RoaringBitmap/roaring i Go kan man nemt udnytte alle funktionerne i Roaring Bitmap. Denne pakke maksimerer hukommelsesforbrug og ydelse gennem forskellige containertyper og optimerede operationer. Roaring Bitmap kan bruges til at implementere effektiv databehandling inden for mange områder, såsom databaseindeksering, loganalyse og statistiske beregninger.

Roaring Bitmap yder især godt på store datasæt og kan bruges med fordel i mange forskellige applikationer. Kombineret med Go-sprogets enkle og effektive syntaks giver Roaring Bitmap udviklere et kraftfuldt værktøj. Det forventes, at Roaring Bitmap vil blive yderligere udviklet med flere funktioner og optimeringer i fremtiden.

Hvorfor gjorde jeg dette overhovedet? For at lave indeksering af hvert tag og hurtige foreningsoperationer i en tidsserie-database.