GoSuda

Livlig bitmap

By snowmerak views ...

Hva er en bitmap?

Her er bitmap en type indeks. Hvis du kom hit med tanke på grafikk, kan du gå tilbake.

Grunnleggende begrep

En bitmap er en indekseringsteknikk i databaser. Verdiene i en bestemt kolonne representeres som et bitarray eller som ett element i en vektor, og hver bit angir om en bestemt verdi i kolonnen finnes. Den enkleste formen tildeler derfor en bitindeks til hver rad og representerer forekomst med 0 og 1.

For eksempel, anta at det finnes en tabell med en kjønnskolonne. Tabellen har 5 rader, og verdiene i kjønnskolonnen er som følger:

  1. Mann
  2. Kvinne
  3. Mann
  4. Kvinne
  5. Annet

I dette tilfellet kan bitmap-indeksen for kjønnskolonnen uttrykkes slik:

  • Mann: 10100
  • Kvinne: 01010
  • Annet: 00001

Så hvor brukes det egentlig

Man vil sikkert tenke at dette ikke bare er ment for å representere data. For å bruke bitmap-indekser skikkelig, la oss vurdere følgende tilfelle.

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

Anta at denne tabellen har 1 000 000 rader, og at man kjører følgende spørring.

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

Denne spørringen finner rader der både kolonnene active og sex er TRUE. Den raskeste måten å finne radene der begge kolonnene er TRUE på er å bruke bitvis AND-operasjon.

  • Bitmap-indeksen for active-kolonnen 1100110011... (bitarray med 1 000 000 bit) er forhåndsindeksert, og
  • bitmap-indeksen for sex-kolonnen 1010101010... (bitarray med 1 000 000 bit) er forhåndsindeksert.

Deretter kan man utføre bitvis AND på de to bitmap-indeksene og raskt finne radene der begge kolonnene er TRUE. Fordi dette er en enkel bitoperasjon, kan resultatet oppnås mye raskere enn med andre indeksskanninger.

Avveininger

Bitmap-indekser kan være svært effektive, men de har noen avveininger. Det finnes mange andre ulemper, men her tar vi bare én.

Bitmap-indekser egner seg best for lav kardinalitet, det vil si når antallet mulige verdier i kolonnen er lite. Hvis man bruker bitmap-indekser på en kolonne med høy kardinalitet, kan bitmapene bli svært store.

Når man bruker bitmap-indekser på en kolonne med høy kardinalitet, må det lages en egen bitmap for hver unik verdi, og det kan kreve mye lagringsplass. For eksempel, hvis en kolonne har 1 000 000 unike verdier, må det lages 1 000 000 bitmaper, og dette kan være svært ineffektivt.

Så hva gjør vi

Bitmapene som oppstår ved høy kardinalitet kan erstattes med en struktur som kalles Roaring Bitmap. Roaring Bitmap har mange egenskaper, men det viktigste grunnprinsippet og den viktigste egenskapen er å dynamisk velge den lagringsmetoden som passer best til datatettheten, for å maksimere både komprimeringsgrad og beregningshastighet.

Grunnleggende begreper i Roaring Bitmap

Tonivå-indeksering

For å lagre ett heltall går Roaring Bitmap gjennom følgende to trinn. Selv om det kalles tonivå-indeksering, kan man tenke på det som en todimensjonal matrise.

  • Uttrekk av de øvre 16 bitene: De øvre 16 bitene i heltallet trekkes ut og brukes som indeks. Dette er indeksen i den ytre matrisen, som har en lengde på 65536. Matrisen lagrer adressen til containeren som omtales senere.
  • Uttrekk av de nedre 16 bitene: De nedre 16 bitene i heltallet trekkes ut og brukes som posisjon innenfor containeren.

Container

Containeren tilsvarer den indre matrisen i den todimensjonale matrisen. I motsetning til matrisen for de øvre 16 bitene varierer den interne strukturen til containeren etter hvor mye data den inneholder. Roaring Bitmap støtter følgende tre typer containere.

  • Array Container: Denne containeren brukes når den lagrer lite data. Mer presist brukes den når den lagrer 4096 elementer eller færre. Den er implementert som en sortert heltallsmatrise, og elementer kan finnes med binærsøk.
  • Bitmap Container: Denne containeren brukes når den lagrer mye data. Mer presist brukes den når den lagrer mer enn 4096 elementer. Den er implementert som en bitmap på 65536 bit (8192 byte). Hver bit angir om det tilsvarende heltallet finnes.
  • Run Container: Denne containeren brukes når den lagrer sammenhengende heltallsområder. For eksempel er den effektiv når man lagrer sammenhengende heltall som 1, 2, 3, 4 og 5. Den er implementert som en liste med par (startverdi, lengde). Hva hvis alle verdiene finnes? Da betyr det at hele området fra start til slutt er til stede, så det er nok å lagre ett par: (0, 65536).

Denne måten gjør at Roaring Bitmap bruker minne svært effektivt og kan gi optimal ytelse for ulike datatettheter.

Funksjonene i Roaring Bitmap

Grunnleggende funksjoner

Roaring Bitmap tilbyr følgende grunnleggende funksjoner.

  • Innsetting: Legger til et nytt heltall i bitmapen. I denne prosessen kan den passende containeren velges, eller containere kan konverteres ved behov.
  • Sletting: Fjerner et eksisterende heltall fra bitmapen. Også i denne prosessen håndteres containerens tilstand på en passende måte.
  • Søk: Sjekker om et bestemt heltall finnes i bitmapen. Denne prosessen utføres svært raskt.

Mengdeoperasjoner

Roaring Bitmap støtter også følgende mengdeoperasjoner.

  • Union (forening): Lager en ny bitmap som inneholder alle elementene fra de to bitmapene.
  • Snitt (Intersection): Lager en ny bitmap som bare inneholder elementer som finnes i begge bitmapene.
  • Symmetrisk differanse (Symmetric Difference): Lager en ny bitmap som inneholder elementer som bare finnes i én av de to bitmapene.

Disse operasjonene er optimalisert for containertypene til bitmapene og utføres svært raskt.

I Go-språket

I Go kan man enkelt bruke Roaring Bitmap med pakken github.com/RoaringBitmap/roaring. Pakken tilbyr alle funksjonene i Roaring Bitmap og er optimalisert for Go.

Installasjon

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

Brukseksempel

 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)     // Initialiserer med 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialiserer med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Legger til 5
14	b2.Add(10) // Legger til 10
15
16	b2.Remove(12) // Fjerner 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Bitmap-operasjoner endrer originalen, så vi lager en kopi før bruk
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 noen viktige funksjoner som ikke vises i eksempelkoden over:

  • Contains(x uint32) bool: Sjekker om en bestemt verdi finnes i bitmapen
  • GetCardinality() uint64: Returnerer antall elementer i bitmapen
  • Rank(x uint32) uint64: Returnerer antall elementer som er mindre enn eller lik en bestemt verdi
  • ToBytes() ([]byte, error): Serialiserer bitmapen til en byte-slice
  • FromBytes(data []byte) error: Gjenoppretter bitmapen fra en byte-slice
  • Clone() *Bitmap: Lager en kopi av bitmapen
  • Clear(): Tilbakestiller bitmapen
  • NextValue(x uint32) int64: Returnerer neste element som er større enn eller lik x
  • PreviousValue(x uint32) int64: Returnerer forrige element som er mindre enn eller
  • Maximum() uint32: Returnerer det største elementet i bitmapen
  • Minimum() uint32: Returnerer det minste elementet i bitmapen

Disse funksjonene finnes. For mer informasjon, se den offisielle dokumentasjonen.

Pakken roaring inneholder også en undermodul som støtter uint64 i tillegg til uint32. Den tilbyr nesten samme grensesnitt, så den kan brukes 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)     // Initialiserer med 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialiserer med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Legger til 5
14	b2.Add(10) // Legger til 10
15
16	b2.Remove(12) // Fjerner 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Bitmap-operasjoner endrer originalen, så vi lager en kopi før bruk
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}

Avslutning

Roaring Bitmap er et kraftig verktøy for effektiv lagring og manipulering av mengder av heltall med høy kardinalitet. Hvis man bruker pakken github.com/RoaringBitmap/roaring i Go, kan man enkelt utnytte alle funksjonene i Roaring Bitmap. Pakken kombinerer ulike containertyper med optimaliserte operasjoner, og maksimerer dermed minnebruk og ytelse. Roaring Bitmap kan brukes i mange områder, som databaseindeksering, logganalyse og statistiske beregninger, for å oppnå effektiv databehandling.

Roaring Bitmap yter spesielt godt på store datasett og kan brukes i mange ulike applikasjoner. I kombinasjon med den enkle og effektive syntaksen i Go gir Roaring Bitmap utviklere et kraftig verktøy. Man kan forvente at Roaring Bitmap videreutvikles med flere funksjoner og optimaliseringer.

Hvorfor gjorde jeg dette? Det var for indeksering av hver tagg og raske unionsoperasjoner i en tidsseriedatabase.