GoSuda

Levende Bitmaps

By snowmerak
views ...

Hva er Bitmap?

Her er bitmap en type indeks. Hvis du kom hit med grafikk i tankene, kan du trykke tilbake.

Grunnleggende konsept

Bitmap er en form for indekseringsteknologi i databaser. Den representerer verdien av en spesifikk kolonne som et bit-array eller et element eller en form for en vektor, der hver bit indikerer om en spesifikk verdi eksisterer i den aktuelle kolonnen. Derfor er den mest grunnleggende formen å tildele en bit-indeks til hver rad og representere eksistensen som 0 eller 1.

Anta for eksempel at vi har en tabell med en kjønnskolonne. Anta at denne 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 representeres som følger:

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

Så, hvor brukes det egentlig?

De fleste vil tenke at dette ikke bare er for å representere det. For å bruke bitmap-indekser riktig, 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 anta at vi utfø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. Da vil vi kunne bruke bitvise AND-operasjoner for å raskest finne rader som tilfredsstiller betingelsen at begge kolonnene er TRUE.

  • Anta at bitmap-indeksen for kolonnen active er forhåndsindeksert som 1100110011... (et bit-array på 1 000 000 biter), og
  • Anta at bitmap-indeksen for kolonnen sex er forhåndsindeksert som 1010101010... (et bit-array på 1 000 000 biter).

Da kan vi utføre en bitvis AND-operasjon på de to bitmap-indeksene for raskt å finne rader der begge kolonnene er TRUE. Siden dette er en enkel bitvis operasjon, vil vi sannsynligvis få resultater mye raskere enn med andre indeks-skanninger.

Avveininger

Bitmap-indekser kan være svært effektive, men det er noen avveininger. Det er mange andre ulemper, men vi vil bare nevne én for nå.

Bitmap-indekser er mer egnet for lav kardinalitet (dvs. når antallet mulige verdier i en kolonne er lite). Hvis bitmap-indekser brukes på kolonner med høy kardinalitet, kan bitmapen bli veldig stor.

Hvis bitmap-indekser brukes på kolonner med høy kardinalitet, kan det kreves mye lagringsplass, da en egen bitmap må genereres for hver unik verdi. For eksempel, hvis en kolonne har 1 000 000 unike verdier, må 1 000 000 biter genereres, noe som kan være svært ineffektivt.

Så, hva gjør vi?

Vi kan bruke Roaring Bitmap som et alternativ til bitmap i høy kardinalitet. Roaring Bitmap har flere egenskaper, men den største underliggende filosofien og egenskapen er å dynamisk velge den mest passende lagringsmetoden basert på datatetthet for å maksimere både kompresjonsforhold og operasjonshastighet.

Grunnleggende konsepter for Roaring Bitmap

To-trinns indeksering

For å lagre et enkelt heltall, går Roaring Bitmap først gjennom de to følgende trinnene. Det kalles to-trinns indeksering, men du kan bare tenke på det som et todimensjonalt array.

  • Ekstraksjon av de øverste 16 bitene: De øverste 16 bitene av heltallet ekstraheres og brukes som en indeks. Dette blir indeksen for det ytre arrayet i et todimensjonalt array med en total lengde på 65536. Dette arrayet lagrer adressene til containerne som vil bli omtalt senere.
  • Ekstraksjon av de nederste 16 bitene: De nederste 16 bitene av heltallet ekstraheres og brukes som posisjonen innenfor containeren.

Container

Denne containeren tilsvarer det indre arrayet i det todimensjonale arrayet, slik det ble analogisert. Men i motsetning til de øverste 16 bitene, varierer den interne strukturen til denne containeren avhengig av hvor mye intern data den inneholder. Roaring Bitmap støtter følgende 3 containere.

  • Array Container: Denne containeren brukes når det er lite data lagret internt. Mer spesifikt brukes den når det skal lagres 4096 eller færre elementer. Denne containeren er implementert som et enkelt sortert array av heltall. Elementer kan finnes ved binærsøk.
  • Bitmap Container: Denne containeren brukes når det er mye data lagret internt. Mer spesifikt brukes den når det skal lagres mer enn 4096 elementer. Denne containeren er implementert som en 65536-bit (8192-byte) bitmap. Hver bit indikerer om et heltall eksisterer på den aktuelle posisjonen.
  • Run Container: Denne containeren brukes til å lagre sammenhengende heltallsområder. For eksempel er den effektiv når man lagrer sammenhengende heltall som 1, 2, 3, 4, 5. Denne containeren er implementert som en liste med (startverdi, lengde)-par. Hvis alt er der? Det betyr bare at alt er der fra start til slutt, så du trenger bare å lagre én (0, 65536).

Denne tilnærmingen gjør at Roaring Bitmap kan bruke minne svært effektivt og gi optimal ytelse for ulike datatettheter.

Funksjoner i Roaring Bitmap

Grunnleggende funksjoner

Roaring Bitmap tilbyr følgende grunnleggende funksjoner.

  • Innsetting: Legger til et nytt heltall i bitmapen. Under denne prosessen kan en passende container velges, eller containeren kan konverteres om nødvendig.
  • Sletting: Fjerner et eksisterende heltall fra bitmapen. Under denne prosessen utføres også passende behandling avhengig av containerens tilstand.
  • Søk: Kontrollerer om et spesifikt heltall eksisterer i bitmapen. Denne prosessen utføres svært raskt.

Mengdeoperasjoner

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

  • Union: Genererer en ny bitmap som inneholder alle elementer fra to bitmapper.
  • Snitt: Genererer en ny bitmap som kun inneholder elementer som finnes i begge bitmappene.
  • Symmetrisk differanse: Genererer en ny bitmap som inneholder elementer som kun finnes i én av de to bitmappene.

Disse operasjonene er optimalisert avhengig av bitmapens containertype og utføres svært raskt.

I Go-språket

I Go-språket kan Roaring Bitmap enkelt brukes ved å benytte pakken github.com/RoaringBitmap/roaring. Denne pakken tilbyr alle funksjonene til Roaring Bitmap og er optimalisert for Go-språkets egenskaper.

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)     // Initialiser med 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialiser med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Legg til 5
14	b2.Add(10) // Legg til 10
15
16	b2.Remove(12) // Fjern 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Siden bitmap-operasjoner endrer originalen, bruk en klone
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]

Viktige funksjoner som ikke vises i eksempelet over inkluderer:

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

Disse funksjonene er tilgjengelige. For mer detaljer, se den offisielle dokumentasjonen.

Merk at roaring-pakken inkluderer en pakke som støtter uint64 i tillegg til uint32. Den tilbyr nesten det samme grensesnittet, slik at den umiddelbart kan byttes ut.

 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)     // Initialiser med 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialiser med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Legg til 5
14	b2.Add(10) // Legg til 10
15
16	b2.Remove(12) // Fjern 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Siden bitmap-operasjoner endrer originalen, bruk en klone
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 heltallsmengder med høy kardinalitet. Ved å bruke github.com/RoaringBitmap/roaring-pakken i Go-språket kan alle funksjonene til Roaring Bitmap enkelt utnyttes. Denne pakken maksimerer minnebruk og ytelse gjennom ulike containertyper og optimaliserte operasjoner. Roaring Bitmap kan brukes i ulike felt som databaseindeksering, logganalyse og statistisk beregning for å implementere effektiv databehandling.

Roaring Bitmap utviser spesielt høy ytelse med store datasett og kan brukes nyttig i en rekke applikasjoner. Kombinert med Go-språkets konsise og effektive syntaks gir Roaring Bitmap utviklere et kraftig verktøy. Det forventes at flere funksjoner og optimaliseringer vil bli realisert med Roaring Bitmaps videre utvikling.

Hvorfor gjorde jeg dette? For indeksering per tag og rask union-operasjon i tidsseriedatabaser.