GoSuda

Levende Bitmap

By snowmerak
views ...

Hva er Bitmap?

Et bitmap er her en type indeks. Hvis du kom hit med grafikk i tankene, kan du trykke tilbake-knappen.

Grunnleggende konsept

Et bitmap er en form for indekseringsteknologi i databaser. Det 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 kolonnen. Den mest grunnleggende formen er derfor å tildele en bit-indeks til hver row og representere eksistensen med 0 og 1.

La oss for eksempel anta at vi har en tabell med en kjønnskolonne. La oss si at denne tabellen har 5 rows, 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

Hvor det faktisk brukes

Alle vil nok 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 rows. Og la oss si at vi utfører følgende spørring.

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

Denne spørringen finner rows der både active- og sex-kolonnene er TRUE. Den raskeste måten å finne rows som oppfyller betingelsen om at begge kolonnene er TRUE, vil være å bruke bit and-operasjonen.

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

Da kan vi utføre en bit and-operasjon på de to bitmap-indeksene for raskt å finne rows der begge kolonnene er TRUE. Siden det er en enkel bit-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 for nå vil vi bare nevne én.

Bitmap-indekser er mer egnet for lav kardinalitet (det vil si når antallet mulige verdier i kolonnen er lite). Bruk av bitmap-indekser på kolonner med høy kardinalitet kan føre til svært store bitmaps.

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

Hva vi gjør

I stedet for bitmaps som kommer fra høy kardinalitet, kan vi bruke noe som kalles Roaring Bitmap. Roaring Bitmap har flere egenskaper, men den største underliggende filosofien og egenskapen er dynamisk å velge den mest passende lagringsmetoden basert på datatettheten, for å maksimere både kompresjonsforhold og operasjonshastighet.

Grunnleggende konsepter for Roaring Bitmap

2-trinns indeksering

For å lagre et heltall går Roaring Bitmap først gjennom følgende 2 trinn. Det er egentlig ikke 2-trinns indeksering, men heller et 2-dimensjonalt array.

  • Ekstraher de øvre 16 bitene: De øvre 16 bitene av heltallet ekstraheres og brukes som en indeks. Dette blir indeksen for det ytre arrayet i et 2-dimensjonalt array med en total lengde på 65536. Dette arrayet lagrer adressene til containerne som vil bli beskrevet senere.
  • Ekstraher de nedre 16 bitene: De nedre 16 bitene av heltallet ekstraheres og brukes som posisjonen innenfor containeren.

Container

Denne containeren tilsvarer det indre arrayet i det 2-dimensjonale arrayet jeg nettopp sammenlignet det med. Men i motsetning til de øvre 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. Spesifikt brukes den når det lagres 4096 eller færre elementer. Denne containeren er implementert som et enkelt sortert heltallsarray. Elementer kan finnes ved binærsøk.
  • Bitmap Container: Denne containeren brukes når det er mye data lagret internt. Spesifikt brukes den når det lagres mer enn 4096 elementer. Denne containeren er implementert som et bitmap på 65536 bits (8192 bytes). Hver bit indikerer om heltallet på den posisjonen eksisterer.
  • Run Container: Denne containeren brukes til å lagre sammenhengende heltallsområder. For eksempel er den effektiv for å lagre 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å bare (0, 65536) lagres.

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

Funksjonalitet til Roaring Bitmap

Grunnleggende funksjonalitet

Roaring Bitmap tilbyr følgende grunnleggende funksjonalitet:

  • Innsetting: Legger til et nytt heltall i bitmapet. I denne prosessen kan en passende container velges, eller containere kan konverteres om nødvendig.
  • Sletting: Fjerner et eksisterende heltall fra bitmapet. I denne prosessen utføres passende behandling i henhold til containerens tilstand.
  • Søk: Kontrollerer om et spesifikt heltall eksisterer i bitmapet. Denne prosessen utføres svært raskt.

Mengdeoperasjoner

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

  • Union: Oppretter et nytt bitmap som inneholder alle elementene fra to bitmaps.
  • Snitt: Oppretter et nytt bitmap som bare inneholder elementene som finnes i begge bitmaps.
  • Symmetrisk differanse: Oppretter et nytt bitmap som inneholder elementene som bare finnes i ett av de to bitmaps.

Disse operasjonene er optimalisert i henhold til bitmapets containertype og utføres svært raskt.

I Go-språket

I Go-språket kan github.com/RoaringBitmap/roaring-pakken enkelt brukes til å utnytte Roaring Bitmap. Denne pakken tilbyr all funksjonalitet for 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	// Ettersom 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: Kontrollerer om en spesifikk verdi eksisterer i bitmapet
  • GetCardinality() uint64: Returnerer antall elementer i bitmapet
  • Rank(x uint32) uint64: Returnerer antall elementer mindre enn eller lik en spesifikk verdi
  • ToBytes() ([]byte, error): Serialiserer bitmapet til en byte-slice
  • FromBytes(data []byte) error: Gjenoppretter bitmapet fra en byte-slice
  • Clone() *Bitmap: Oppretter en klone av bitmapet
  • Clear(): Initialiserer bitmapet
  • NextValue(x uint32) int64: Returnerer neste element større enn eller lik x
  • PreviousValue(x uint32) int64: Returnerer elementet mindre enn eller lik x
  • Maximum() uint32: Returnerer det største elementet i bitmapet
  • Minimum() uint32: Returnerer det minste elementet i bitmapet

For mer informasjon, se offisiell dokumentasjon.

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

 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	// Ettersom 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 effektivt å lagre og manipulere sett med heltall 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 statistiske beregninger for å implementere effektiv databehandling.

Roaring Bitmap utmerker seg spesielt i 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. Videre utvikling av Roaring Bitmap forventes å bringe flere funksjoner og optimaliseringer.

Hvorfor gjorde jeg dette? For indeksering av hver tag og raske union-operasjoner i tidsbaserte databaser.