GoSuda

Živý Bitmap

By snowmerak
views ...

Čo je to Bitmapa?

Bitmapa je tu jedným z typov indexov. Ak ste sem prišli s myšlienkou na grafiku, stlačte tlačidlo späť.

Základný koncept

Bitmapa je forma indexovacej techniky databázy. Hodnota konkrétneho stĺpca je vyjadrená ako bitové pole alebo ako prvok či forma vektora, pričom každý bit indikuje, či daná hodnota existuje pre daný stĺpec. Preto je najzákladnejšou formou priradiť bitový index ku každému riadku a vyjadriť existenciu hodnotou 0 alebo 1.

Napríklad, predpokladajme tabuľku so stĺpcom pre pohlavie. Táto tabuľka má 5 riadkov 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

Takže, kde sa to naozaj používa

Všetci si asi myslíte, že to nie je len na reprezentáciu toho. Aby sme správne použili bitmapový index, 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 má 1 000 000 riadkov. A predpokladajme, že vykonáme nasledujúci dotaz.

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

Tento dotaz nájde riadky, kde sú stĺpce active aj sex TRUE. Najrýchlejší spôsob, ako nájsť riadky, ktoré spĺňajú podmienku, že oba stĺpce sú TRUE, by mohol byť s využitím bitovej operácie AND.

  • Predpokladajme, že bitmapový index pre stĺpec active je vopred indexovaný ako 1100110011... (bitové pole s 1 000 000 bitmi),
  • a bitmapový index pre stĺpec sex je vopred indexovaný ako 1010101010... (bitové pole s 1 000 000 bitmi).

Potom môžeme vykonať bitovú operáciu AND na týchto dvoch bitmapových indexoch, aby sme rýchlo našli riadky, kde sú oba stĺpce TRUE. Pretože ide o jednoduchú bitovú operáciu, výsledky sa získajú oveľa rýchlejšie ako pri iných indexových prehľadávaniach.

Kompromisy (Trade-offs)

Bitmapové indexy môžu byť veľmi efektívne, ale majú niekoľko kompromisov. Existuje mnoho iných nevýhod, ale teraz sa zameriame len na jednu.

A to, že bitmapové indexy sú vhodnejšie pre nízku kardinalitu (t. j. keď je počet možných hodnôt v stĺpci nízky). Použitie bitmapového indexu na stĺpci s vysokou kardinalitou môže spôsobiť, že bitmapa bude veľmi veľká.

Ak sa bitmapový index použije na stĺpec s vysokou kardinalitou, je potrebné vytvoriť samostatnú bitmapu pre každú jedinečnú hodnotu, čo môže vyžadovať veľa úložného priestoru. Napríklad, ak stĺpec obsahuje 1 000 000 jedinečných hodnôt, je potrebné vytvoriť 1 000 000 bitmap, čo môže byť veľmi neefektívne.

A preto my

Na nahradenie bitmapy pri vysokej kardinalite môžeme použiť Roaring Bitmap. Roaring Bitmap má rôzne vlastnosti, ale jeho najväčšou základnou filozofiou a vlastnosťou je dynamický výber najvhodnejšieho spôsobu ukladania v závislosti od hustoty dát, čím sa maximalizuje kompresný pomer aj rýchlosť operácií.

Základný koncept Roaring Bitmapu

Dvojstupňové indexovanie

Aby Roaring Bitmap uložil jedno celé číslo, prechádza najprv nasledujúcimi 2 fázami. Aj keď sa to nazýva dvojstupňové indexovanie, stačí si to predstaviť ako dvojrozmerné pole.

  • Extrakcia horných 16 bitov: Extrahujú sa horné 16 bitov celého čísla a použijú sa ako index. Toto sa stáva indexom vonkajšieho poľa z dvojrozmerného poľa s celkovou dĺžkou 65536. Toto pole ukladá adresy kontajnerov, ktoré budú popísané neskôr.
  • Extrakcia dolných 16 bitov: Extrahujú sa dolné 16 bitov celého čísla a použijú sa ako pozícia v rámci kontajnera.

Kontajner

Tento kontajner zodpovedá vnútornému poľu v dvojrozmernom poli, ako sme už spomenuli. Avšak, na rozdiel od horných 16 bitov, vnútorná štruktúra tohto kontajnera sa mení v závislosti od toho, koľko dát je v ňom uložených. Roaring Bitmap podporuje nasledujúce 3 typy kontajnerov.

  • Array Container (Kontajner Pole): Tento kontajner sa používa, keď je v ňom uložených málo dát. Konkrétne sa používa na uloženie 4096 alebo menej prvkov. Tento kontajner je implementovaný jednoducho ako zoradené pole celých čísel. Prvok je možné nájsť pomocou binárneho vyhľadávania.
  • Bitmap Container (Kontajner Bitmapa): Tento kontajner sa používa, keď je v ňom uložených veľa dát. Konkrétne sa používa na uloženie viac ako 4096 prvkov. Tento kontajner je implementovaný ako 65536-bitová (8192-bajtová) bitmapa. Každý bit indikuje, či celé číslo na danej pozícii existuje.
  • Run Container (Kontajner Sekvencia): Tento kontajner sa používa na uloženie súvislých rozsahov celých čísel. Je efektívny napríklad pri ukladaní súvislých celých čísel ako 1, 2, 3, 4, 5. Tento kontajner je implementovaný ako zoznam párov (začiatočná hodnota, dĺžka). Ak sú tam všetky? Znamená to, že sú tam všetky od začiatku do konca, takže stačí uložiť len jeden pár (0, 65536).

Tento prístup umožňuje Roaring Bitmapu veľmi efektívne využívať pamäť a poskytovať optimálny výkon pre rôzne hustoty dát.

Funkcie Roaring Bitmapu

Základné funkcie

Roaring Bitmap poskytuje nasledujúce základné funkcie.

  • Vloženie: Pridanie nového celého čísla do bitmapy. Počas tohto procesu je možné vybrať vhodný kontajner alebo v prípade potreby kontajner transformovať.
  • Odstránenie: Odstránenie existujúceho celého čísla z bitmapy. Počas tohto procesu sa vykoná vhodné spracovanie v závislosti od stavu kontajnera.
  • Vyhľadávanie: Kontrola, či konkrétne celé číslo existuje v bitmape. Tento proces sa vykonáva veľmi rýchlo.

Množinové operácie

Roaring Bitmap tiež podporuje nasledujúce množinové operácie.

  • Zjednotenie (Union): Vytvorenie novej bitmapy, ktorá obsahuje všetky prvky z oboch bitmáp.
  • Priesečník (Intersection): Vytvorenie novej bitmapy, ktorá obsahuje iba prvky prítomné v oboch bitmapách.
  • Symetrický rozdiel (Symmetric Difference): Vytvorenie novej bitmapy, ktorá obsahuje prvky prítomné iba v jednej z dvoch bitmáp.

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

V jazyku Go

V jazyku Go sa dá Roaring Bitmap jednoducho použiť pomocou balíka github.com/RoaringBitmap/roaring. Tento balík poskytuje všetky funkcie Roaring Bitmapu a je optimalizovaný pre špecifiká 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 s 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inicializácia s 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 bitmapy mení originál, takže 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]

Kľúčové funkcie, ktoré nie sú uvedené v príklade kódu vyššie, sú:

  • Contains(x uint32) bool: Kontrola, či daná hodnota existuje 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 byte slice
  • FromBytes(data []byte) error: Obnovenie bitmapy z byte slice
  • Clone() *Bitmap: Vytvorenie kópie bitmapy
  • Clear(): 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 rovného x
  • Maximum() uint32: Vrátenie najväčšieho prvku v bitmape
  • Minimum() uint32: Vrátenie najmenšieho prvku v bitmape

Tieto funkcie sú dostupné. Podrobné informácie nájdete v oficiálnej dokumentácii.

Pre informáciu, balík roaring obsahuje balík, ktorý podporuje uint64 okrem uint32. Poskytuje takmer identické rozhranie, takže ho môžete priamo zameniť.

 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 s 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inicializácia s 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 bitmapy mení originál, takže 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}

Na záver

Roaring Bitmap je výkonný nástroj, ktorý dokáže efektívne ukladať a manipulovať so súbormi celých čísel s vysokou kardinalitou. V jazyku Go, použitím balíka github.com/RoaringBitmap/roaring, môžete ľahko využiť všetky funkcie Roaring Bitmapu. Tento balík maximalizuje využitie pamäte a výkon prostredníctvom rôznych typov kontajnerov a optimalizovaných operácií. Roaring Bitmap sa dá použiť v rôznych oblastiach, ako je indexovanie databáz, analýza logov a štatistické výpočty, na implementáciu efektívneho spracovania dát.

Roaring Bitmap vyniká vysokým výkonom najmä pri rozsiahlych súboroch dát a je užitočný v rôznych aplikáciách. V kombinácii s jednoduchou a efektívnou syntaxou jazyka Go poskytuje Roaring Bitmap vývojárom výkonný nástroj. Očakáva sa, že s rozvojom Roaring Bitmapu príde aj viac funkcií a optimalizácií.

Prečo som to robil? Pre indexovanie jednotlivých tagov a rýchlu operáciu zjednotenia v časových databázach.