GoSuda

Živá bitmapa

By snowmerak views ...

Čo je bitmapa?

Bitmapa tu predstavuje jeden druh indexu. Ak ste sem prišli s predstavou grafiky, stačí sa vrátiť späť.

Základný pojem

Bitmapa je forma indexovacej techniky databáz. Hodnoty konkrétneho stĺpca sa vyjadrujú ako prvok alebo podoba bitového poľa či vektora, pričom každý bit udáva, či sa daná konkrétna hodnota stĺpca v riadku vyskytuje. Najzákladnejšou podobou je preto priradenie bitového indexu ku každému riadku (row) a vyjadrenie prítomnosti pomocou 0 a 1.

Predstavme si napríklad tabuľku so stĺpcom pohlavia. Nech má táto tabuľka 5 riadkov (row) a hodnoty stĺpca pohlavia sú nasledovné:

  1. Muž
  2. Žena
  3. Muž
  4. Žena
  5. Iné

V tomto prípade môže byť bitmapový index pre stĺpec pohlavia vyjadrený takto:

  • Muž: 10100
  • Žena: 01010
  • Iné: 00001

Na čo sa to vlastne používa

Iste si mnohí myslia, že to slúži len na zobrazenie tohto stavu. Aby sme si však bitmapový index skutočne vyskúšali, zvážme nasledujúci prípad.

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

Predpokladajme, že táto tabuľka obsahuje 1 000 000 riadkov (row). Ďalej nech sa vykoná nasledujúci dopyt.

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

Tento dopyt vyhľadá riadky, v ktorých sú stĺpce active aj sex obidva TRUE. Najrýchlejším spôsobom, ako nájsť riadky spĺňajúce podmienku, že oba stĺpce sú TRUE, môže byť použitie bitovej operácie bit and.

  • bitmapový index stĺpca active 1100110011... (pole 1 000 000 bitov) je vopred indexovaný,
  • bitmapový index stĺpca sex 1010101010... (pole 1 000 000 bitov) je vopred indexovaný.

Potom možno nad oboma bitmapovými indexmi vykonať operáciu bit and a rýchlo nájsť riadky, v ktorých sú oba stĺpce TRUE. Keďže ide o jednoduchú bitovú operáciu, výsledok možno získať výrazne rýchlejšie než pri skenovaní iných indexov.

Kompromisy

Bitmapový index môže byť veľmi efektívny, no má niekoľko kompromisov. Nevýhod je veľa, ale teraz sa zameriam len na jednu.

Konkrétne, bitmapový index je vhodnejší pre nízku kardinalitu (t. j. prípad, keď stĺpec má malý počet možných hodnôt). Pri použití bitmapového indexu na stĺpec s vysokou kardinalitou môže byť bitmapa veľmi veľká.

Pri použití bitmapového indexu na stĺpec s vysokou kardinalitou sa pre každú jedinečnú hodnotu musí vytvoriť samostatná bitmapa, a preto môže byť potrebný veľký úložný priestor. Napríklad, ak stĺpec obsahuje 1 000 000 jedinečných hodnôt, treba vytvoriť 1 000 000 bitmáp, čo môže byť mimoriadne neefektívne.

Takže my

Namiesto bitmáp, ktoré vznikajú pri vysokej kardinalite, môžeme použiť takzvanú Roaring Bitmap. Roaring Bitmap má viacero vlastností, no jej najdôležitejšia základná filozofia a charakteristika spočíva v dynamickom výbere najvhodnejšieho spôsobu uloženia podľa hustoty dát, čím sa maximalizuje kompresný pomer aj rýchlosť operácií.

Základné pojmy Roaring Bitmap

Dvojstupňové indexovanie

Roaring Bitmap pri ukladaní jedného celého čísla najprv prechádza týmito dvoma stupňami. Hoci ide o dvojstupňové indexovanie, stačí si to predstaviť jednoducho ako dvojrozmerné pole.

  • Extrakcia horných 16 bitov: horných 16 bitov celého čísla sa extrahuje a použije ako index. Je to index vonkajšieho poľa z dvojrozmerného poľa s dĺžkou 65536. Toto pole ukladá adresy kontajnerov, o ktorých sa hovorí nižšie.
  • Extrakcia dolných 16 bitov: dolných 16 bitov celého čísla sa extrahuje a použije ako pozícia v rámci kontajnera.

Kontajnery

Tieto kontajnery zodpovedajú vnútornému poľu v dvojrozmernom poli, ako sme práve prirovnali. Na rozdiel od vonkajšej vrstvy, ktorú tvoria horné 16 bitov, sa však vnútorná štruktúra kontajnera mení podľa množstva dát, ktoré obsahuje. Roaring Bitmap podporuje tieto 3 typy kontajnerov.

  • Array Container: tento kontajner sa používa, keď je v ňom uložených málo dát. Konkrétne sa používa pri ukladaní 4096 alebo menej prvkov. Je implementovaný ako jednoduché zoradené pole celých čísel. Prvky je možné vyhľadať binárnym vyhľadávaním.
  • Bitmap Container: tento kontajner sa používa, keď je v ňom uložených veľa dát. Konkrétne sa používa pri ukladaní viac ako 4096 prvkov. Je implementovaný ako bitmapa o veľkosti 65536 bitov (8192 bajtov). Každý bit udáva, či sa celé číslo na danej pozícii nachádza v kontajneri.
  • Run Container: tento kontajner sa používa na ukladanie súvislých rozsahov celých čísel. Je efektívny napríklad pri ukladaní súvislých čísel ako 1, 2, 3, 4, 5. Je implementovaný ako zoznam dvojíc (počiatočná hodnota, dĺžka). A čo ak sú prítomné všetky hodnoty? Znamená to, že sú prítomné od začiatku až do konca, takže stačí uložiť jedinú dvojicu (0, 65536).

Vďaka tomuto prístupu Roaring Bitmap využíva pamäť veľmi efektívne a dokáže poskytovať optimálny výkon pri rôznej hustote dát.

Funkcie Roaring Bitmap

Základné funkcie

Roaring Bitmap poskytuje tieto základné funkcie.

  • Vloženie: pridá nové celé číslo do bitmapy. Pri tomto procese sa môže vybrať vhodný kontajner alebo sa podľa potreby môže kontajner previesť na iný typ.
  • Odstránenie: odstráni existujúce celé číslo z bitmapy. Aj v tomto procese sa primerané spracovanie uskutočňuje podľa stavu kontajnera.
  • Vyhľadávanie: overí, či sa dané celé číslo nachádza v bitmape. Tento proces sa vykonáva mimoriadne rýchlo.

Operácie nad množinami

Roaring Bitmap okrem toho podporuje tieto operácie nad množinami.

  • Zjednotenie (Union): vytvorí novú bitmapu obsahujúcu všetky prvky oboch bitmáp.
  • Prienik (Intersection): vytvorí novú bitmapu obsahujúcu iba prvky, ktoré sa nachádzajú v oboch bitmapách.
  • Symetrický rozdiel (Symmetric Difference): vytvorí novú bitmapu obsahujúcu prvky, ktoré sa nachádzajú iba v jednej z oboch bitmáp.

Tieto operácie sú optimalizované podľa typu kontajnera bitmapy a vykonávajú sa mimoriadne rýchlo.

V jazyku Go

V jazyku Go možno Roaring Bitmap jednoducho využiť pomocou balíka github.com/RoaringBitmap/roaring. Tento balík poskytuje všetky funkcie Roaring Bitmap a je optimalizovaný podľa charakteristík jazyka Go.

Inštalácia

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

Príklad použitia

 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)     // inicializácia hodnotami 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // inicializácia hodnotami 2, 4, 6, 8, 12
12
13	b1.Add(5)  // pridanie 5
14	b2.Add(10) // pridanie 10
15
16	b2.Remove(12) // odstránenie 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// operácia nad bitmapou mení pôvodný objekt, preto sa použije kópia
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]

Okrem funkcií uvedených v príklade kódu existujú aj tieto dôležité funkcie:

  • Contains(x uint32) bool: overenie, či sa daná hodnota nachádza v bitmape
  • GetCardinality() uint64: vrátenie počtu prvkov obsiahnutých v bitmape
  • Rank(x uint32) uint64: vrátenie počtu prvkov menších alebo rovných danej hodnote
  • ToBytes() ([]byte, error): serializácia bitmapy do bajtového slice
  • FromBytes(data []byte) error: obnovenie bitmapy z bajtového slice
  • Clone() *Bitmap: vytvorenie kópie bitmapy
  • Clear(): vymazanie (inicializácia) bitmapy
  • NextValue(x uint32) int64: vrátenie nasledujúceho prvku väčšieho alebo rovného x
  • PreviousValue(x uint32) int64: vrátenie predchádzajúceho prvku menšieho alebo
  • Maximum() uint32: vrátenie najväčšieho prvku v bitmape
  • Minimum() uint32: vrátenie najmenšieho prvku v bitmape

Existujú aj ďalšie funkcie. Podrobnosti nájdete v oficiálnej dokumentácii.

Pre úplnosť, balík roaring obsahuje aj vnútorný balík podporujúci uint64, nielen uint32. Keďže poskytuje takmer rovnaké rozhranie, možno ho použiť priamo ako náhradu.

 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)     // inicializácia hodnotami 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // inicializácia hodnotami 2, 4, 6, 8, 12
12
13	b1.Add(5)  // pridanie 5
14	b2.Add(10) // pridanie 10
15
16	b2.Remove(12) // odstránenie 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// operácia nad bitmapou mení pôvodný objekt, preto sa použije kópia
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}

Záver

Roaring Bitmap je silný nástroj na efektívne ukladanie a spracovanie množín celých čísel s vysokou kardinalitou. V jazyku Go možno pomocou balíka github.com/RoaringBitmap/roaring ľahko využiť všetky funkcie Roaring Bitmap. Tento balík prostredníctvom rôznych typov kontajnerov a optimalizovaných operácií maximalizuje využitie pamäte aj výkon. Roaring Bitmap možno použiť na efektívne spracovanie dát v rôznych oblastiach, ako sú indexovanie databáz, analýza logov alebo štatistické výpočty.

Roaring Bitmap dosahuje vysoký výkon najmä pri rozsiahlych dátových množinách a môže byť užitočný v rôznych aplikáciách. V spojení s jednoduchou a efektívnou syntaxou jazyka Go poskytuje Roaring Bitmap vývojárom silný nástroj. Očakáva sa, že s ďalším vývojom Roaring Bitmap pribudnú ďalšie funkcie a optimalizácie.

Prečo som to robil? Kvôli indexovaniu jednotlivých tagov a rýchlym operáciám zjednotenia v časovej databáze.