GoSuda

Levende bitmap

By snowmerak
views ...

Hvad er Bitmap?

Her er bitmap en type indeks. Hvis du kom her og tænkte på grafik, kan du trykke på tilbageknappen.

Grundlæggende koncept

Bitmap er en form for indekseringsteknologi i databaser. Den repræsenterer værdierne i en specifik kolonne som et bitarray eller et element eller en form for en vektor, hvor hver bit angiver, om en bestemt værdi eksisterer i den pågældende kolonne. Den mest grundlæggende form er derfor at tildele et bitindeks til hver række og repræsentere eksistensen som 0 eller 1.

Lad os for eksempel antage, at vi har en tabel med en kønkolonne. Lad os antage, at denne tabel har 5 rækker, og værdierne i kønkolonnen er som følger:

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

I dette tilfælde kan bitmapindekset for kønkolonnen udtrykkes som følger:

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

Så, hvor bruges det egentlig?

Derfor vil alle nok tænke, at dette ikke blot er til at repræsentere det. For at kunne anvende bitmapindekset korrekt, 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 rækker. Og lad os antage, at vi udfører følgende forespørgsel.

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

Denne forespørgsel finder rækker, hvor både 'active' og 'sex' kolonnen er TRUE. Så den hurtigste måde at finde rækker, der opfylder betingelsen om, at begge kolonner er TRUE, ville være at bruge en bit-AND-operation.

  • Lad os antage, at bitmapindekset for 'active'-kolonnen 1100110011... (1.000.000 bitarray) er forindekseret, og
  • bitmapindekset for 'sex'-kolonnen 1010101010... (1.000.000 bitarray) er forindekseret.

Derefter kan man ved at udføre en bit-AND-operation på de to bitmapindekser hurtigt finde de rækker, hvor begge kolonner er TRUE. Da det er en simpel bitoperation, vil man kunne opnå resultater meget hurtigere end med andre indeksscanninger.

Trade-offs

Bitmapindekser kan være meget effektive, men der er nogle trade-offs. Selvom der er mange andre ulemper, vil vi nu kun fokusere på én.

Det er, at bitmapindekser er mere velegnede til lav kardinalitet (dvs. hvor antallet af mulige værdier i kolonnen er lille). Brug af bitmapindekser på kolonner med høj kardinalitet kan resultere i meget store bitmaps.

Hvis bitmapindekser bruges på kolonner med høj kardinalitet, kan der være behov for meget lagerplads, da et separat bitmap skal genereres for hver unik værdi. For eksempel, hvis en kolonne har 1.000.000 unikke værdier, skal der genereres 1.000.000 bitmaps, hvilket kan være meget ineffektivt.

Så vi

Vi kan bruge noget, der hedder Roaring Bitmap, som en erstatning for bitmaps, der kommer fra høj kardinalitet. Roaring Bitmap har forskellige egenskaber, men den største grundlæggende filosofi og egenskab er at dynamisk vælge den mest passende lagringsmetode baseret på datatætheden for at maksimere både kompressionsforhold og driftshastighed.

Grundlæggende koncept for Roaring Bitmap

2-trins indeksering

For at gemme et enkelt heltal gennemgår Roaring Bitmap først følgende 2 trin. Selvom det kaldes 2-trins indeksering, kan du blot betragte det som et 2D-array.

  • Udpakning af de øverste 16 bit: De øverste 16 bit af heltallet udpakkes og bruges som indeks. Dette bliver indekset for det ydre array i et 2D-array med en total længde på 65536. Dette array gemmer adresserne på de containere, der vil blive diskuteret senere.
  • Udpakning af de nederste 16 bit: De nederste 16 bit af heltallet udpakkes og bruges som position inden for containeren.

Container

Denne container svarer til det indre array i det 2D-array, som jeg netop har brugt som analogi. Men i modsætning til de øverste 16 bit ændrer denne container sin interne struktur afhængigt af, hvor meget intern data den indeholder. Roaring Bitmap understøtter følgende 3 containere.

  • Array Container: Denne container bruges, når der er få data gemt internt. Specifikt bruges den til at gemme 4096 eller færre elementer. Denne container er simpelthen implementeret som et sorteret array af heltal. Elementer kan findes ved binær søgning.
  • Bitmap Container: Denne container bruges, når der er mange data gemt internt. Specifikt bruges den til at gemme mere end 4096 elementer. Denne container er implementeret som et 65536-bit (8192-byte) bitmap. Hver bit angiver, om heltallet på den pågældende position eksisterer.
  • Run Container: Denne container bruges til at gemme et kontinuerligt interval af heltal. Den er for eksempel effektiv til at gemme kontinuerlige heltal som 1, 2, 3, 4, 5. Denne container er implementeret som en liste af (startværdi, længde) par. Hvis alle er der? Det betyder bare, at alt fra start til slut er der, så man behøver kun at gemme (0, 65536).

Denne metode gør Roaring Bitmap i stand til at bruge hukommelse meget effektivt og give optimal ydeevne for forskellige datatætheder.

Roaring Bitmaps funktioner

Grundlæggende funktioner

Roaring Bitmap tilbyder følgende grundlæggende funktioner:

  • Indsæt: Tilføjer et nyt heltal til bitmap'en. Under denne proces kan en passende container vælges eller en container kan transformeres, hvis nødvendigt.
  • Slet: Fjerner et eksisterende heltal fra bitmap'en. Også under denne proces udføres passende behandling afhængigt af containerens tilstand.
  • Søg: Kontrollerer, om et specifikt heltal eksisterer i bitmap'en. Denne proces udføres meget hurtigt.

Mængdeoperationer

Roaring Bitmap understøtter også følgende mængdeoperationer.

  • Union: Opretter et nyt bitmap, der indeholder alle elementer fra to bitmaps.
  • Intersection: Opretter et nyt bitmap, der kun indeholder elementer, der eksisterer i begge bitmaps.
  • Symmetric Difference: Opretter et nyt bitmap, der indeholder elementer, der kun eksisterer i den ene af de to bitmaps.

Disse operationer er optimeret til at udføres meget hurtigt, afhængigt af bitmapens containertype.

I Go-sproget

I Go-sproget kan man nemt bruge Roaring Bitmap ved at anvende github.com/RoaringBitmap/roaring pakken. Denne pakke leverer alle Roaring Bitmaps funktioner og er optimeret til Go-sprogets karakteristika.

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)     // Initialiseres med 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialiseres 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	// Da bitmap-operationer ændrer originalen, skal der bruges en klon
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]

Blandt de vigtigste funktioner, der ikke er vist i ovenstående eksempelkode, er:

  • Contains(x uint32) bool: Kontrollerer, om en bestemt værdi eksisterer i bitmap'en
  • GetCardinality() uint64: Returnerer antallet af elementer i bitmap'en
  • Rank(x uint32) uint64: Returnerer antallet af elementer, der er mindre end eller lig med en bestemt værdi
  • ToBytes() ([]byte, error): Serialiserer bitmap'en til en byte-slice
  • FromBytes(data []byte) error: Gendanner bitmap'en fra en byte-slice
  • Clone() *Bitmap: Opretter en klon af bitmap'en
  • Clear(): Nulstiller bitmap'en
  • 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'en
  • Minimum() uint32: Returnerer det mindste element i bitmap'en

Disse funktioner er tilgængelige. Se venligst den officielle dokumentation for flere detaljer.

Bemærk, at 'roaring'-pakken ikke kun indeholder uint32, men også en pakke, der understøtter uint64. Da den tilbyder næsten den samme interface, kan den udskiftes 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)     // Initialiseres med 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialiseres 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	// Da bitmap-operationer ændrer originalen, skal der bruges en klon
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, der effektivt kan lagre og manipulere høj-kardinalitets heltalssæt. I Go-sproget kan alle Roaring Bitmaps funktioner nemt udnyttes ved at bruge github.com/RoaringBitmap/roaring pakken. Denne pakke maksimerer hukommelsesforbrug og ydeevne gennem forskellige containertyper og optimerede operationer. Roaring Bitmap kan bruges i forskellige områder som databaseindeksering, loganalyse og statistisk beregning for at implementere effektiv databehandling.

Roaring Bitmap udmærker sig især ved høj ydeevne i store datasæt og kan bruges effektivt i forskellige applikationer. Kombineret med Go-sprogets koncise og effektive syntaks giver Roaring Bitmap udviklere et kraftfuldt værktøj. Det forventes, at Roaring Bitmap vil fortsætte med at udvikle sig med flere funktioner og optimeringer i fremtiden.

Hvorfor gjorde jeg dette? For at indeksere hver tag og hurtige union-operationer i tidsbaseret database.