GoSuda

Živý bitmap

By snowmerak
views ...

Čo je Bitmapa?

Bitmapa je tu typom indexu. Ak ste sem prišli s myšlienkou grafiky, môžete sa vrátiť späť.

Základný koncept

Bitmapa je forma indexovacej techniky v databázach. Hodnoty konkrétneho stĺpca sú reprezentované ako bitové pole alebo ako prvok či forma vektora, pričom každý bit indikuje prítomnosť alebo neprítomnosť špecifickej hodnoty v danom stĺpci. Preto najzákladnejšou formou je priradenie bitového indexu ku každému riadku a reprezentácia prítomnosti ako 1 a neprítomnosti ako 0.

Predpokladajme napríklad, že máme tabuľku so stĺpcom pre pohlavie. Táto tabuľka má 5 riadkov a hodnoty stĺpca pohlavie sú nasledovné:

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

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

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

Na čo sa to skutočne používa

Každý si pravdepodobne myslí, že to nie je len na reprezentáciu niečoho takého. Aby sme správne využ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 hľadá riadky, kde sú oba stĺpce active a sex TRUE. Najrýchlejší spôsob, ako nájsť riadky, ktoré spĺňajú podmienku, že oba stĺpce sú TRUE, by bolo použiť operáciu bitového 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 vykonaním operácie bitového AND na týchto dvoch bitmapových indexoch môžeme rýchlo nájsť riadky, kde sú oba stĺpce TRUE. Keďže ide o jednoduchú bitovú operáciu, výsledky by sa získali oveľa rýchlejšie ako pri iných indexových skenoch.

Kompromisy

Bitmapové indexy môžu byť veľmi efektívne, ale existuje niekoľko kompromisov. Existuje mnoho ďalší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 malý). Použitie bitmapového indexu pre stĺpec s vysokou kardinalitou môže viesť k veľmi veľkej bitmape.

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

Preto my

Môžeme použiť Roaring Bitmap ako alternatívu k bitmapám s vysokou kardinalitou. Roaring Bitmap má niekoľko vlastností, ale 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ť výpočtu.

Základné koncepty Roaring Bitmap

Dvojstupňová indexácia

Roaring Bitmap pre uloženie jedného celého čísla najprv prechádza nasledujúcimi dvoma fázami. Hoci sa to nazýva dvojstupňová indexácia, môžete si to predstaviť ako dvojrozmerné pole.

  • Extrakcia horných 16 bitov: Horných 16 bitov celého čísla sa extrahuje a použije sa ako index. Toto sa stáva indexom vonkajšieho poľa v dvojrozmernom poli s celkovou dĺžkou 65536. Toto pole ukladá adresy kontajnerov, o ktorých sa bude hovoriť neskôr.
  • Extrakcia dolných 16 bitov: Dolných 16 bitov celého čísla sa extrahuje a použije 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 líši v závislosti od množstva interných dát. Roaring Bitmap podporuje nasledujúce 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 na uloženie 4096 alebo menej prvkov. Tento kontajner je jednoducho implementovaný ako usporiadané pole celých čísel. Prvky je možné nájsť pomocou binárneho vyhľadávania.
  • Bitmap Container: 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 prítomnosť alebo neprítomnosť celého čísla na danej pozícii.
  • Run Container: Tento kontajner sa používa na uloženie rozsahu súvislých 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 (počiatočná hodnota, dĺžka). Ak sú všetky prítomné? Znamená to, že sú prítomné všetky od začiatku do konca, takže stačí uložiť iba (0, 65536).

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

Funkcie Roaring Bitmap

Základné funkcie

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

  • Vloženie: Pridá nové celé číslo do bitmapy. Počas tohto procesu sa vyberie vhodný kontajner alebo sa kontajner podľa potreby transformuje.
  • Vymazanie: Odstráni existujúce celé číslo z bitmapy. Aj počas tohto procesu sa vykonáva vhodné spracovanie v závislosti od stavu kontajnera.
  • Vyhľadávanie: Skontroluje, či sa konkrétne celé číslo nachádza 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): Vytvorí novú bitmapu obsahujúcu všetky prvky z oboch bitmap.
  • Priesečník (Intersection): Vytvorí novú bitmapu obsahujúcu iba prvky, ktoré sú prítomné v oboch bitmapách.
  • Symetrický rozdiel (Symmetric Difference): Vytvorí novú bitmapu obsahujúcu prvky, ktoré sú prítomné iba v jednej z dvoch bitmap.

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

V jazyku Go

V jazyku Go môžete Roaring Bitmap ľahko použiť pomocou balíka github.com/RoaringBitmap/roaring. Tento balík poskytuje všetky funkcie Roaring Bitmap 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ácie s bitmapou menia originál, preto použite klon
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:

  • Contains(x uint32) bool: Skontroluje, či sa konkrétna hodnota nachádza v bitmape
  • GetCardinality() uint64: Vráti počet prvkov obsiahnutých v bitmape
  • Rank(x uint32) uint64: Vráti počet prvkov menších alebo rovných danej hodnote
  • ToBytes() ([]byte, error): Serializuje bitmapu do byte slice
  • FromBytes(data []byte) error: Obnoví bitmapu z byte slice
  • Clone() *Bitmap: Vytvorí klon bitmapy
  • Clear(): Inicializuje bitmapu
  • NextValue(x uint32) int64: Vráti ďalší prvok väčší alebo rovný x
  • PreviousValue(x uint32) int64: Vráti predchádzajúci prvok menší ako x
  • Maximum() uint32: Vráti najväčší prvok v bitmape
  • Minimum() uint32: Vráti najmenší prvok v bitmape

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

Pre informáciu, balík roaring obsahuje balík, ktorý podporuje nielen uint32, ale aj uint64. Poskytuje takmer identické rozhranie, takže ho možno priamo nahradiť.

 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ácie s bitmapou menia originál, preto použite klon
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 na efektívne ukladanie a manipuláciu so sadami celých čísel s vysokou kardinalitou. V jazyku Go môžete ľahko využívať všetky funkcie Roaring Bitmap pomocou balíka github.com/RoaringBitmap/roaring. Tento balík maximalizuje využitie pamäte a výkon vďaka rôznym typom kontajnerov a optimalizovaným operáciám. Roaring Bitmap možno 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á najmä pri rozsiahlych súboroch dát a môže byť užitočný v rôznych aplikáciách. V kombinácii s stručnou a efektívnou syntaxou jazyka Go poskytuje Roaring Bitmap vývojárom výkonný nástroj. Očakáva sa, že Roaring Bitmap sa bude naďalej vyvíjať s ďalšími funkciami a optimalizáciami.

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