GoSuda

Levendige Bitmap

By snowmerak
views ...

Wat is een Bitmap?

Een Bitmap is hier een type Index. Indien u aan Grafische weergave dacht, kunt u teruggaan.

Basisconcept

Een Bitmap is een vorm van Indexeringstechnologie in databases. Het representeert de waarden van een specifieke kolom als een Bit Array of als een element of vorm van een Vector, waarbij elke Bit aangeeft of een specifieke waarde van die kolom aanwezig is. De meest basale vorm is dus het toewijzen van een Bit Index aan elke rij en het uitdrukken van de aanwezigheid als 0 of 1.

Stel bijvoorbeeld dat er een tabel is met een geslachtskolom. Stel dat deze tabel 5 rijen bevat en de waarden van de geslachtskolom als volgt zijn:

  1. Man
  2. Vrouw
  3. Man
  4. Vrouw
  5. Overig

In dit geval kan de Bitmap Index voor de geslachtskolom als volgt worden weergegeven:

  • Man: 10100
  • Vrouw: 01010
  • Overig: 00001

Dus waar wordt het echt voor gebruikt?

U zult waarschijnlijk denken dat dit niet alleen is om dat weer te geven. Laten we de volgende situatie overwegen om de Bitmap Index correct te gebruiken.

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

Stel dat deze tabel 1.000.000 rijen bevat. En stel dat we de volgende Query uitvoeren.

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

Deze Query zoekt naar rijen waar zowel de active als de sex kolom TRUE zijn. De snelste manier om rijen te vinden die voldoen aan de voorwaarde dat beide kolommen TRUE zijn, is door gebruik te maken van een Bitwise AND-operatie.

  • Stel dat de Bitmap Index voor de active kolom al is geïndexeerd als 1100110011... (een Bit Array van 1.000.000 Bits), en
  • Stel dat de Bitmap Index voor de sex kolom al is geïndexeerd als 1010101010... (een Bit Array van 1.000.000 Bits).

Dan kunnen we door een Bitwise AND-operatie uit te voeren op de twee Bitmap Indexen, snel de rijen vinden waar beide kolommen TRUE zijn. Aangezien het een eenvoudige Bitwise operatie is, zullen we veel sneller resultaten verkrijgen dan bij andere Index Scans.

Afwegingen

Hoewel Bitmap Indexen zeer efficiënt kunnen zijn, zijn er enkele afwegingen. Er zijn veel andere nadelen, maar we zullen er nu slechts één bespreken.

Bitmap Indexen zijn geschikter voor lage Cardinaliteit (d.w.z. wanneer het aantal mogelijke waarden in een kolom klein is). Het gebruik van een Bitmap Index op een kolom met hoge Cardinaliteit kan de Bitmap erg groot maken.

Als een Bitmap Index wordt gebruikt op een kolom met hoge Cardinaliteit, moet voor elke unieke waarde een afzonderlijke Bitmap worden gegenereerd, wat veel opslagruimte kan vereisen. Als een kolom bijvoorbeeld 1.000.000 unieke waarden bevat, moeten 1.000.000 Bitmaps worden gegenereerd, wat zeer inefficiënt kan zijn.

Dus wij

Ter vervanging van Bitmaps die voortkomen uit hoge Cardinaliteit, kunnen we Roaring Bitmap gebruiken. Roaring Bitmap heeft verschillende kenmerken, maar de grootste onderliggende filosofie en kenmerk is het dynamisch selecteren van de meest geschikte opslagmethode op basis van de dichtheid van de gegevens om zowel compressie als bewerkingssnelheid te maximaliseren.

Basisconcept van Roaring Bitmap

Indexering in 2 stappen

Om één integer op te slaan, doorloopt Roaring Bitmap eerst de volgende 2 stappen. Hoewel het 2-staps indexering wordt genoemd, kunt u het gewoon zien als een tweedimensionale Array.

  • Extractie van de bovenste 16 Bits: De bovenste 16 Bits van de integer worden geëxtraheerd en gebruikt als Index. Dit wordt de Index van de buitenste Array in een tweedimensionale Array met een totale lengte van 65536. Deze Array slaat de adressen van de Containers op, die later worden besproken.
  • Extractie van de onderste 16 Bits: De onderste 16 Bits van de integer worden geëxtraheerd en gebruikt als de positie binnen de Container.

Container

Deze Container komt overeen met de binnenste Array van de tweedimensionale Array, zoals zojuist geïllustreerd. Echter, in tegenstelling tot die van de bovenste 16 Bits, varieert de interne structuur van deze Container afhankelijk van de hoeveelheid interne gegevens. Roaring Bitmap ondersteunt de volgende 3 typen Containers.

  • Array Container: Deze Container wordt gebruikt wanneer er weinig gegevens intern zijn opgeslagen. Specifiek wordt deze gebruikt voor het opslaan van 4096 of minder elementen. Deze Container is eenvoudig geïmplementeerd als een gesorteerde Array van integers. Elementen kunnen worden gevonden door middel van Binaire Zoekopdrachten.
  • Bitmap Container: Deze Container wordt gebruikt wanneer er veel gegevens intern zijn opgeslagen. Specifiek wordt deze gebruikt voor het opslaan van meer dan 4096 elementen. Deze Container is geïmplementeerd als een Bitmap van 65536 Bits (8192 Bytes). Elke Bit geeft aan of de integer op die positie aanwezig is.
  • Run Container: Deze Container wordt gebruikt voor het opslaan van aaneengesloten reeksen integers. Bijvoorbeeld, het is efficiënt voor het opslaan van aaneengesloten integers zoals 1, 2, 3, 4, 5. Deze Container is geïmplementeerd als een lijst van (startwaarde, lengte) paren. Als alles aanwezig is? Dan betekent het dat alles van begin tot eind aanwezig is, dus hoeft u slechts (0, 65536) op te slaan.

Deze benadering stelt Roaring Bitmap in staat om geheugen zeer efficiënt te gebruiken en optimale prestaties te leveren voor diverse gegevensdichtheden.

Functionaliteit van Roaring Bitmap

Basisfuncties

Roaring Bitmap biedt de volgende basisfuncties.

  • Invoegen: Voegt een nieuwe integer toe aan de Bitmap. Tijdens dit proces kan een geschikte Container worden geselecteerd of kan de Container indien nodig worden geconverteerd.
  • Verwijderen: Verwijdert een bestaande integer uit de Bitmap. Ook tijdens dit proces wordt de juiste verwerking uitgevoerd op basis van de status van de Container.
  • Zoeken: Controleert of een specifieke integer aanwezig is in de Bitmap. Dit proces wordt zeer snel uitgevoerd.

Set-operaties

Roaring Bitmap ondersteunt ook de volgende Set-operaties.

  • Vereniging (Union): Genereert een nieuwe Bitmap die alle elementen van twee Bitmaps bevat.
  • Doorsnede (Intersection): Genereert een nieuwe Bitmap die alleen de elementen bevat die in beide Bitmaps aanwezig zijn.
  • Symmetrisch Verschil (Symmetric Difference): Genereert een nieuwe Bitmap die elementen bevat die in slechts één van de twee Bitmaps aanwezig zijn.

Deze operaties worden zeer snel uitgevoerd, geoptimaliseerd op basis van het Container type van de Bitmap.

In de Go-taal

In de Go-taal kan de Roaring Bitmap eenvoudig worden gebruikt met het github.com/RoaringBitmap/roaring pakket. Dit pakket biedt alle functionaliteiten van de Roaring Bitmap en is geoptimaliseerd voor de kenmerken van de Go-taal.

Installatie

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

Gebruiksvoorbeeld

 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)     // Geïnitialiseerd met 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Geïnitialiseerd met 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Voeg 5 toe
14	b2.Add(10) // Voeg 10 toe
15
16	b2.Remove(12) // Verwijder 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Omdat Bitwise operaties het origineel wijzigen, gebruik een kloon
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]

Belangrijke functies die niet in het bovenstaande voorbeeld zijn opgenomen, zijn:

  • Contains(x uint32) bool: Controleert of een specifieke waarde in de Bitmap aanwezig is.
  • GetCardinality() uint64: Retourneert het aantal elementen in de Bitmap.
  • Rank(x uint32) uint64: Retourneert het aantal elementen kleiner dan of gelijk aan een specifieke waarde.
  • ToBytes() ([]byte, error): Serialiseert de Bitmap naar een Byte Slice.
  • FromBytes(data []byte) error: Herstelt de Bitmap uit een Byte Slice.
  • Clone() *Bitmap: Creëert een kloon van de Bitmap.
  • Clear(): Initialiseert de Bitmap.
  • NextValue(x uint32) int64: Retourneert het volgende element groter dan of gelijk aan x.
  • PreviousValue(x uint32) int64: Retourneert het vorige element kleiner dan.
  • Maximum() uint32: Retourneert het grootste element in de Bitmap.
  • Minimum() uint32: Retourneert het kleinste element in de Bitmap.

Voor meer details, raadpleeg de officiële documentatie.

Ter info, het roaring-pakket bevat ook een pakket dat uint64 ondersteunt, naast uint32. Het biedt vrijwel dezelfde Interface, zodat u direct kunt wisselen.

 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)     // Geïnitialiseerd met 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Geïnitialiseerd met 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Voeg 5 toe
14	b2.Add(10) // Voeg 10 toe
15
16	b2.Remove(12) // Verwijder 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Omdat Bitwise operaties het origineel wijzigen, gebruik een kloon
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}

Tot slot

Roaring Bitmap is een krachtig hulpmiddel voor het efficiënt opslaan en manipuleren van verzamelingen integers met hoge Cardinaliteit. Door gebruik te maken van het github.com/RoaringBitmap/roaring-pakket in Go, kunt u eenvoudig alle functionaliteiten van Roaring Bitmap benutten. Dit pakket maximaliseert het geheugengebruik en de prestaties door diverse Container-typen en geoptimaliseerde operaties. Roaring Bitmap kan worden toegepast in diverse domeinen zoals database-indexering, loganalyse en statistische berekeningen om efficiënte gegevensverwerking te realiseren.

Roaring Bitmap presteert bijzonder goed met grootschalige Datasets en kan nuttig zijn in diverse applicaties. In combinatie met de beknopte en efficiënte syntaxis van de Go-taal, biedt Roaring Bitmap ontwikkelaars een krachtig hulpmiddel. Er wordt verwacht dat Roaring Bitmap zich verder zal ontwikkelen met meer functionaliteiten en optimalisaties in de toekomst.

Waarom ik dit deed? Voor Indexering per Tag en snelle Unie-operaties in een Time Series Database.