GoSuda

Levendige Bitmap

By snowmerak
views ...

Wat is een Bitmap?

Hier verwijst 'bitmap' naar een type index. Als u dacht aan computergraphics, kunt u teruggaan.

Basisconcepten

Een bitmap is een vorm van indexeringstechnologie in databases. De waarde van een specifieke kolom wordt weergegeven als een bitarray of een element of vorm van een vector, waarbij elke bit aangeeft of een specifieke waarde van die kolom aanwezig is. De meest elementaire vorm is daarom het toewijzen van een bitindex aan elke rij en het uitdrukken van de aanwezigheid als 0 of 1.

Stel bijvoorbeeld dat we een tabel hebben met een geslachtskolom. Stel dat deze tabel 5 rijen bevat en de waarden in de geslachtskolom als volgt zijn:

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

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

  • Man: 10100
  • Vrouw: 01010
  • Anders: 00001

Dus waar wordt het echt voor gebruikt?

Men zou verwachten dat dit niet alleen is om dat weer te geven. Laten we de volgende situatie overwegen om de bitmapindex 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 rijen waar zowel de kolommen active als sex TRUE zijn. De snelste manier om rijen te vinden die voldoen aan de voorwaarde dat beide kolommen TRUE zijn, zou het gebruik van een bitwise AND-bewerking zijn.

  • Stel dat een bitmapindex voor de kolom active 1100110011... (een bitarray van 1.000.000 bits) vooraf is geïndexeerd, en
  • Stel dat een bitmapindex voor de kolom sex 1010101010... (een bitarray van 1.000.000 bits) vooraf is geïndexeerd.

Dan kunnen we door een bitwise AND-bewerking uit te voeren op de twee bitmapindexen snel rijen vinden waar beide kolommen TRUE zijn. Aangezien het een eenvoudige bitbewerking is, zou het resultaat veel sneller worden verkregen dan bij andere indexscans.

Afwegingen

Bitmapindexen kunnen zeer efficiënt zijn, maar er zijn enkele afwegingen. Hoewel er veel andere nadelen zijn, zullen we ons nu concentreren op één daarvan.

Bitmapindexen zijn namelijk geschikter voor lage cardinaliteit (d.w.z. wanneer het aantal mogelijke waarden in een kolom klein is). Het gebruik van een bitmapindex op een kolom met hoge cardinaliteit kan de bitmap erg groot maken.

Als een bitmapindex 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 heeft, moeten 1.000.000 bitmaps worden gegenereerd, wat zeer inefficiënt kan zijn.

Wat wij dan doen

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

Basisconcept van Roaring Bitmap

2-fasen indexering

Roaring Bitmap doorloopt de volgende 2 fasen om één geheel getal op te slaan. Hoewel het 2-fasen indexering heet, kunt u het gewoon zien als een 2D-array.

  • Extractie van de bovenste 16 bits: De bovenste 16 bits van het geheel getal worden geëxtraheerd en als index gebruikt. Dit wordt de index van de buitenste array in een 2D-array met een lengte van 65536. Deze array slaat de adressen van de containers op, die later zullen worden beschreven.
  • Extractie van de onderste 16 bits: De onderste 16 bits van het geheel getal worden geëxtraheerd en als positie binnen de container gebruikt.

Container

Deze container komt overeen met de binnenste array van de 2D-array, zoals zojuist geanalogiseerd. 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 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 gehele getallen. 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 het gehele getal op die positie aanwezig is.
  • Run Container: Deze container wordt gebruikt voor het opslaan van aaneengesloten bereiken van gehele getallen. Bijvoorbeeld, het is efficiënt voor het opslaan van aaneengesloten gehele getallen zoals 1, 2, 3, 4, 5. Deze container is geïmplementeerd als een lijst van (startwaarde, lengte) paren. Wat als ze er allemaal zijn? Dan betekent het gewoon dat alles van het begin tot het einde aanwezig is, dus hoeft slechts één (0, 65536) te worden opgeslagen.

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

Functionaliteit van Roaring Bitmap

Basisfuncties

Roaring Bitmap biedt de volgende basisfuncties.

  • Invoegen: Voegt een nieuw geheel getal toe aan de bitmap. Tijdens dit proces kan een geschikte container worden geselecteerd of kan de container indien nodig worden geconverteerd.
  • Verwijderen: Verwijdert een bestaand geheel getal uit de bitmap. Ook tijdens dit proces wordt passende verwerking uitgevoerd afhankelijk van de staat van de container.
  • Zoeken: Controleert of een specifiek geheel getal aanwezig is in de bitmap. Dit proces wordt zeer snel uitgevoerd.

Setbewerkingen

Roaring Bitmap ondersteunt ook de volgende setbewerkingen.

  • Unie (Union): Genereert een nieuwe bitmap die alle elementen van twee bitmaps bevat.
  • Doorsnede (Intersection): Genereert een nieuwe bitmap die alleen elementen bevat die in beide bitmaps aanwezig zijn.
  • Symmetrisch verschil (Symmetric Difference): Genereert een nieuwe bitmap die elementen bevat die slechts in één van de twee bitmaps aanwezig zijn.

Deze bewerkingen zijn geoptimaliseerd op basis van het containertype van de bitmap en worden zeer snel uitgevoerd.

In Go-taal

In de Go-taal kan men gemakkelijk gebruikmaken van Roaring Bitmap door het github.com/RoaringBitmap/roaring pakket te gebruiken. Dit pakket biedt alle functionaliteit van 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)     // Initialiseer met 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialiseer 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 bitmap-bewerkingen het origineel wijzigen, gebruikt u 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]

De volgende belangrijke functies, die niet in de bovenstaande voorbeeldcode voorkomen, 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 dat groter is dan of gelijk is aan x
  • PreviousValue(x uint32) int64: Retourneert het vorige element dat kleiner is dan x
  • 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 niet alleen ondersteuning voor uint32, maar ook voor uint64. Ze bieden bijna dezelfde interface, dus u kunt ze direct uitwisselen.

 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)     // Initialiseer met 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialiseer 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 bitmap-bewerkingen het origineel wijzigen, gebruikt u 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}

Conclusie

Roaring Bitmap is een krachtig hulpmiddel voor het efficiënt opslaan en manipuleren van verzamelingen van gehele getallen met hoge cardinaliteit. In de Go-taal kan men gemakkelijk alle functionaliteit van Roaring Bitmap benutten met behulp van het github.com/RoaringBitmap/roaring pakket. Dit pakket maximaliseert het geheugengebruik en de prestaties door middel van diverse containertypen en geoptimaliseerde bewerkingen. Roaring Bitmap kan worden toegepast in diverse domeinen zoals database-indexering, loganalyse en statistische berekeningen om efficiënte gegevensverwerking te realiseren.

Roaring Bitmap presteert met name goed bij grote datasets en kan nuttig worden gebruikt in een verscheidenheid aan toepassingen. Gecombineerd met de beknopte en efficiënte syntaxis van de Go-taal, biedt Roaring Bitmap ontwikkelaars een krachtig hulpmiddel. Verdere vooruitgang en optimalisatie van Roaring Bitmap worden in de toekomst verwacht.

Waarom heb ik dit gedaan? Voor indexering per tag en snelle unie-bewerkingen in tijdreeksdatabases.