GoSuda

Levendige bitmap

By snowmerak views ...

Wat is een bitmap?

Hier is een bitmap een soort index. Als u hier met grafische verwerking in gedachten bent gekomen, kunt u nu teruggaan.

Basisconcept

Een bitmap is een indexeringstechniek in databases. De waarden van een bepaalde kolom worden weergegeven als een bitarray of als een element of vorm van een vector, waarbij elke bit aangeeft of een specifieke waarde van die kolom aanwezig is. De meest elementaire vorm wijst aan elke row een bitindex toe en geeft het bestaan weer met 0 en 1.

Stel dat er bijvoorbeeld een tabel is met een kolom voor geslacht. Deze tabel bevat 5 rows, en de waarden in de kolom geslacht zijn als volgt:

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

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

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

Waar wordt het eigenlijk voor gebruikt

Ongetwijfeld denkt iedereen nu dat het niet alleen dient om dit weer te geven. Om bitmapindexen goed te kunnen gebruiken, beschouwen we het volgende geval.

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 rows bevat. Stel verder dat de volgende query wordt uitgevoerd.

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

Deze query zoekt de rows waarin zowel active als sex TRUE is. In dat geval is het de snelste methode om de rows te vinden waarvoor beide kolommen TRUE zijn, om een bitsgewijze AND-bewerking te gebruiken.

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

Door een bitsgewijze AND-bewerking uit te voeren op de twee bitmapindexen, kunnen de rows waarin beide kolommen TRUE zijn snel worden gevonden. Omdat het om een eenvoudige bitbewerking gaat, kan het resultaat veel sneller worden verkregen dan met andere indexscans.

Afwegingen

Bitmapindexen kunnen zeer efficiënt zijn, maar ze hebben enkele afwegingen. Er zijn veel andere nadelen, maar nu bespreken we er slechts één.

Dat is dat bitmapindexen beter geschikt zijn voor een lage cardinaliteit (dat wil zeggen, wanneer het aantal mogelijke waarden in een kolom klein is). Bij gebruik van een bitmapindex op een kolom met een hoge cardinaliteit kan de bitmap zeer groot worden.

Bij gebruik van een bitmapindex op een kolom met een hoge cardinaliteit moet voor elke unieke waarde een afzonderlijke bitmap worden gemaakt, waardoor veel opslagruimte nodig kan zijn. Als een kolom bijvoorbeeld 1.000.000 unieke waarden heeft, moeten 1.000.000 bitmaps worden gemaakt, wat zeer inefficiënt kan zijn.

Dus wat doen we nu

Om de bitmap die voortkomt uit een hoge cardinaliteit te vervangen, kan men Roaring Bitmap gebruiken. Roaring Bitmap heeft verschillende kenmerken, maar de belangrijkste onderliggende filosofie en eigenschap is: het dynamisch kiezen van de meest geschikte opslagmethode op basis van de dichtheid van de data, om zowel de compressieverhouding als de bewerkingssnelheid te maximaliseren.

Basisconcept van Roaring Bitmap

Tweeledige indexering

Roaring Bitmap doorloopt om één geheel getal op te slaan eerst de volgende twee stappen. Hoewel het tweeledige indexering heet, kunt u het gewoon als een tweedimensionale array beschouwen.

  • Extractie van de bovenste 16 bits: De bovenste 16 bits van het gehele getal worden geëxtraheerd en als index gebruikt. Dit is de index van de buitenste array van een tweedimensionale array met een lengte van in totaal 65536. Deze array slaat het adres op van de container die hierna wordt beschreven.
  • Extractie van de onderste 16 bits: De onderste 16 bits van het gehele getal worden geëxtraheerd en gebruikt als positie binnen de container.

Container

Deze container komt overeen met de binnenste array van de tweedimensionale array uit de zojuist gegeven vergelijking. In tegenstelling tot die van de bovenste 16 bits verandert de interne structuur van deze container naargelang de hoeveelheid data erin. Roaring Bitmap ondersteunt de volgende 3 containers.

  • Array Container: Deze container wordt gebruikt wanneer er weinig data in is opgeslagen. Concreet wordt hij gebruikt bij het opslaan van 4096 elementen of minder. Deze container is geïmplementeerd als een eenvoudige gesorteerde array van gehele getallen. Elementen kunnen worden gevonden door binaire zoekopdrachten.
  • Bitmap Container: Deze container wordt gebruikt wanneer er veel data in is opgeslagen. Concreet wordt hij gebruikt bij 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. Hij is bijvoorbeeld efficiënt bij het opslaan van opeenvolgende gehele getallen zoals 1, 2, 3, 4, 5. Deze container is geïmplementeerd als een lijst van paren (startwaarde, lengte). Als alles aanwezig is? Dan betekent dat gewoon dat alles van begin tot eind aanwezig is, dus hoeft alleen (0, 65536) te worden opgeslagen.

Met deze aanpak gebruikt Roaring Bitmap het geheugen zeer efficiënt en kan het optimale prestaties leveren bij uiteenlopende datadichtheden.

Functies van Roaring Bitmap

Basisfuncties

Roaring Bitmap biedt de volgende basisfuncties.

  • Invoegen: Voegt een nieuw geheel getal toe aan de bitmap. Daarbij kan een geschikte container worden gekozen, of kan de container indien nodig worden omgezet.
  • Verwijderen: Verwijdert een bestaand geheel getal uit de bitmap. Ook hierbij wordt afhankelijk van de toestand van de container een passende verwerking uitgevoerd.
  • Zoeken: Controleert of een specifiek geheel getal in de bitmap aanwezig is. Dit gebeurt zeer snel.

Verzamelingsbewerkingen

Roaring Bitmap ondersteunt bovendien de volgende verzamelingsbewerkingen.

  • Vereniging (Union): Maakt een nieuwe bitmap aan die alle elementen van beide bitmaps bevat.
  • Doorsnede (Intersection): Maakt een nieuwe bitmap aan die alleen de elementen bevat die in beide bitmaps voorkomen.
  • Symmetrisch verschil (Symmetric Difference): Maakt een nieuwe bitmap aan die de elementen bevat die in precies één van beide bitmaps voorkomen.

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

In de Go-taal

In de Go-taal kunt u Roaring Bitmap eenvoudig gebruiken met het pakket github.com/RoaringBitmap/roaring. Dit pakket biedt alle functies van Roaring Bitmap en is geoptimaliseerd voor de eigenschappen van Go.

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)     // Initialiseren met 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Initialiseren met 2, 4, 6, 8, 12
12
13	b1.Add(5)  // 5 toevoegen
14	b2.Add(10) // 10 toevoegen
15
16	b2.Remove(12) // 12 verwijderen
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Bitmapbewerkingen wijzigen het origineel, dus gebruik een kopie
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]

Andere belangrijke functies die niet in het bovenstaande voorbeeld zijn gebruikt, zijn onder meer:

  • Contains(x uint32) bool: Controleert of een specifieke waarde in de bitmap aanwezig is
  • GetCardinality() uint64: Geeft het aantal elementen in de bitmap terug
  • Rank(x uint32) uint64: Geeft het aantal elementen terug dat kleiner of gelijk is aan een bepaalde waarde
  • ToBytes() ([]byte, error): Serialiseert de bitmap naar een byteslice
  • FromBytes(data []byte) error: Herstelt de bitmap uit een byteslice
  • Clone() *Bitmap: Maakt een kopie van de bitmap
  • Clear(): Initialiseert de bitmap opnieuw
  • NextValue(x uint32) int64: Geeft het volgende element terug dat groter of gelijk is aan x
  • PreviousValue(x uint32) int64: Geeft het vorige element terug dat kleiner of gelijk is aan x
  • Maximum() uint32: Geeft het grootste element in de bitmap terug
  • Minimum() uint32: Geeft het kleinste element in de bitmap terug

Dit zijn enkele van de beschikbare functies. Raadpleeg voor meer informatie de officiële documentatie.

Het roaring-pakket bevat intern ook een pakket dat niet alleen uint32, maar ook uint64 ondersteunt. Omdat het vrijwel dezelfde interface biedt, kan het direct als vervanging worden gebruikt.

 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)     // Initialiseren met 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Initialiseren met 2, 4, 6, 8, 12
12
13	b1.Add(5)  // 5 toevoegen
14	b2.Add(10) // 10 toevoegen
15
16	b2.Remove(12) // 12 verwijderen
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Bitmapbewerkingen wijzigen het origineel, dus gebruik een kopie
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 om verzamelingen van gehele getallen met een hoge cardinaliteit efficiënt op te slaan en te bewerken. Met het pakket github.com/RoaringBitmap/roaring in de Go-taal kunt u alle functies van Roaring Bitmap eenvoudig gebruiken. Dit pakket maximaliseert het geheugengebruik en de prestaties dankzij verschillende containertypen en geoptimaliseerde bewerkingen. Met Roaring Bitmap kunt u efficiënte gegevensverwerking realiseren op uiteenlopende gebieden, zoals databaseindexering, loganalyse en statistische berekeningen.

Roaring Bitmap presteert vooral goed bij grootschalige datasets en kan in uiteenlopende toepassingen nuttig zijn. In combinatie met de beknopte en efficiënte syntaxis van Go biedt Roaring Bitmap ontwikkelaars een krachtig hulpmiddel. Naar verwachting zullen er in de toekomst met de ontwikkeling van Roaring Bitmap nog meer functies en optimalisaties komen.

Waarom heb ik dit eigenlijk gedaan? Voor de indexering per tag en snelle vereniging van bewerkingen in een tijdreeksdatabase.