GoSuda

Vibrant Bitmap

By snowmerak
views ...

Vad är en Bitmap?

Här är bitmap en typ av index. Om du kom hit för grafik kan du trycka på bakåtknappen.

Grundläggande koncept

En bitmap är en form av indexeringsteknik i databaser. Den representerar värdena för en specifik kolumn som en bitarray eller ett element i en vektor, där varje bit indikerar om ett specifikt värde för den kolumnen existerar. Den mest grundläggande formen tilldelar alltså ett bitindex till varje rad och representerar existensen som 0 eller 1.

Låt oss till exempel anta att vi har en tabell med en kolumn för kön. Denna tabell har 5 rader, och värdena i könskolumnen är följande:

  1. Man
  2. Kvinna
  3. Man
  4. Kvinna
  5. Övrigt

I detta fall kan ett bitmap-index för könskolumnen representeras enligt följande:

  • Man: 10100
  • Kvinna: 01010
  • Övrigt: 00001

Så, var används det egentligen?

Alla kommer nog att tänka att detta inte bara är för att representera det. För att kunna använda bitmap-index korrekt, låt oss överväga följande fall.

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

Låt oss anta att denna tabell har 1 000 000 rader. Och låt oss anta att vi kör följande fråga.

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

Denna fråga hittar rader där både kolumnerna active och sex är TRUE. Det snabbaste sättet att hitta rader som uppfyller villkoret att båda kolumnerna är TRUE skulle då vara att använda en bitmässig AND-operation.

  • Låt oss anta att ett bitmap-index för kolumnen active är förindexerat som 1100110011... (en bitarray med 1 000 000 bitar), och
  • Låt oss anta att ett bitmap-index för kolumnen sex är förindexerat som 1010101010... (en bitarray med 1 000 000 bitar).

Då kan vi utföra en bitmässig AND-operation på de två bitmap-indexen för att snabbt hitta rader där båda kolumnerna är TRUE. Eftersom det är en enkel bitoperation, kommer resultatet att erhållas mycket snabbare än med andra indexskanningar.

Kompromisser

Bitmap-index kan vara mycket effektiva, men det finns vissa kompromisser. Det finns många andra nackdelar, men för närvarande kommer vi bara att ta upp en.

Det är att bitmap-index är mer lämpliga för låg kardinalitet (det vill säga när antalet möjliga värden i en kolumn är litet). Att använda bitmap-index för kolumner med hög kardinalitet kan göra bitmapen mycket stor.

Om man använder bitmap-index för kolumner med hög kardinalitet, kan det krävas mycket lagringsutrymme eftersom en separat bitmap måste skapas för varje unikt värde. Om en kolumn till exempel har 1 000 000 unika värden, måste 1 000 000 bitmaps skapas, vilket kan vara mycket ineffektivt.

Därför använder vi

Vi kan använda något som kallas Roaring Bitmap för att ersätta bitmaps som kommer från hög kardinalitet. Roaring Bitmap har flera egenskaper, men den största grundläggande filosofin och egenskapen är att dynamiskt välja den mest lämpliga lagringsmetoden beroende på datatätheten för att maximera både komprimeringsgraden och beräkningshastigheten.

Grundläggande koncept för Roaring Bitmap

Tvåstegsindexering

Roaring Bitmap genomgår först följande två steg för att lagra ett heltal. Det är inte riktigt tvåstegsindexering, utan snarare en tvådimensionell array.

  • Extrahera de övre 16 bitarna: De övre 16 bitarna av heltalet extraheras och används som index. Detta blir indexet för den yttre arrayen i en tvådimensionell array med en total längd på 65536. Denna array lagrar adressen till den container som beskrivs nedan.
  • Extrahera de nedre 16 bitarna: De nedre 16 bitarna av heltalet extraheras och används som position inom containern.

Container

Denna container motsvarar den inre arrayen i den tvådimensionella arrayen som just nämndes. Men till skillnad från de övre 16 bitarna varierar den interna strukturen för denna container beroende på hur mycket intern data det finns. Roaring Bitmap stöder följande 3 containertyper.

  • Array Container: Denna container används när det finns lite data lagrad internt. Specifikt används den när färre än 4096 element lagras. Denna container är helt enkelt implementerad som en sorterad array av heltal. Element kan hittas genom binärsökning.
  • Bitmap Container: Denna container används när det finns mycket data lagrad internt. Specifikt används den när fler än 4096 element lagras. Denna container är implementerad som en 65536-bitars (8192 byte) bitmap. Varje bit indikerar om heltalet på den positionen existerar.
  • Run Container: Denna container används för att lagra kontinuerliga intervall av heltal. Till exempel är den effektiv för att lagra kontinuerliga heltal som 1, 2, 3, 4, 5. Denna container är implementerad som en lista med (startvärde, längd)-par. Om allt finns? Det betyder bara att allt finns från början till slut, så bara (0, 65536) behöver lagras.

Denna metod gör att Roaring Bitmap kan använda minne mycket effektivt och ge optimal prestanda för olika datatätheter.

Roaring Bitmaps funktioner

Grundläggande funktioner

Roaring Bitmap tillhandahåller följande grundläggande funktioner.

  • Infoga: Lägger till ett nytt heltal i bitmapen. Under denna process kan en lämplig container väljas eller en container omvandlas vid behov.
  • Radera: Tar bort ett befintligt heltal från bitmapen. Även under denna process utförs lämplig bearbetning beroende på containerns tillstånd.
  • Sök: Kontrollerar om ett specifikt heltal finns i bitmapen. Denna process utförs mycket snabbt.

Mängdoperationer

Roaring Bitmap stöder även följande mängdoperationer.

  • Union: Skapar en ny bitmap som innehåller alla element från två bitmaps.
  • Skärningspunkt (Intersection): Skapar en ny bitmap som endast innehåller element som finns i båda bitmaps.
  • Symmetrisk skillnad (Symmetric Difference): Skapar en ny bitmap som innehåller element som endast finns i en av de två bitmaps.

Dessa operationer är optimerade beroende på bitmapens containertyp och utförs mycket snabbt.

I Go-språket

I Go-språket kan Roaring Bitmap enkelt användas med paketet github.com/RoaringBitmap/roaring. Detta paket tillhandahåller alla funktioner i Roaring Bitmap och är optimerat för Go-språkets egenskaper.

Installation

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

Användningsexempel

 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)     // Initiera med 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initiera med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Lägg till 5
14	b2.Add(10) // Lägg till 10
15
16	b2.Remove(12) // Ta bort 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Eftersom bitmap-operationer ändrar originalet, använd 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]

Viktiga funktioner som inte visas i ovanstående exempelkod är:

  • Contains(x uint32) bool: Kontrollerar om ett specifikt värde finns i bitmapen
  • GetCardinality() uint64: Returnerar antalet element i bitmapen
  • Rank(x uint32) uint64: Returnerar antalet element mindre än eller lika med ett specifikt värde
  • ToBytes() ([]byte, error): Serialiserar bitmapen till en byte-slice
  • FromBytes(data []byte) error: Återställer bitmapen från en byte-slice
  • Clone() *Bitmap: Skapar en klon av bitmapen
  • Clear(): Initierar bitmapen
  • NextValue(x uint32) int64: Returnerar nästa element som är större än eller lika med x
  • PreviousValue(x uint32) int64: Returnerar nästa element som är mindre än x
  • Maximum() uint32: Returnerar det största elementet i bitmapen
  • Minimum() uint32: Returnerar det minsta elementet i bitmapen

Dessa funktioner finns tillgängliga. För mer information, se den officiella dokumentationen.

Observera att roaring-paketet internt innehåller ett paket som stöder uint64 utöver uint32. Eftersom de tillhandahåller nästan samma gränssnitt, kan de bytas ut direkt.

 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)     // Initiera med 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initiera med 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Lägg till 5
14	b2.Add(10) // Lägg till 10
15
16	b2.Remove(12) // Ta bort 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Eftersom bitmap-operationer ändrar originalet, använd 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}

Avslutning

Roaring Bitmap är ett kraftfullt verktyg för att effektivt lagra och manipulera uppsättningar av heltal med hög kardinalitet. Med paketet github.com/RoaringBitmap/roaring i Go-språket kan alla funktioner i Roaring Bitmap enkelt utnyttjas. Detta paket maximerar minnesanvändning och prestanda genom olika containertyper och optimerade operationer. Roaring Bitmap kan användas inom olika områden som databasindexering, logganalys och statistikberäkning för att implementera effektiv databehandling.

Roaring Bitmap presterar särskilt bra med stora datamängder och kan användas i en mängd olika applikationer. I kombination med Go-språkets koncisa och effektiva syntax ger Roaring Bitmap utvecklare ett kraftfullt verktyg. Vi förväntar oss ytterligare utveckling och optimering av Roaring Bitmap i framtiden.

Varför gjorde jag detta? För indexering av varje tagg och snabb union-operation i tidsseriedatabaser.