GoSuda

Čilý Bitmap

By snowmerak
views ...

Co je to Bitmapa?

Bitmapa je zde jedním z typů indexů. Pokud jste sem přišli s myšlenkou na grafiku, můžete stisknout tlačítko zpět.

Základní koncept

Bitmapa je forma indexační techniky v databázích. Hodnota specifického sloupce je reprezentována jako bitové pole nebo jako prvek či forma vektoru, kde každý bit indikuje existenci dané specifické hodnoty sloupce. Proto je nejzákladnější formou přidělení bitového indexu každému řádku (row) a vyjádření existence pomocí 0 a 1.

Předpokládejme například tabulku se sloupcem pro pohlaví. Tato tabulka má 5 řádků (row) a hodnoty sloupce pohlaví jsou následující:

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

V tomto případě může být bitová mapa (bitmap) indexu pro sloupec pohlaví vyjádřena takto:

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

Takže, kde se skutečně používá

Všichni si jistě myslí, že se nejedná pouze o reprezentaci těchto hodnot. Abychom řádně využili bitmapový index, zvažme následující pří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);

Předpokládejme, že tato tabulka má 1 000 000 řádků (row). A předpokládejme, že spustíme následující dotaz (query).

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

Tento dotaz vyhledává řádky, kde jsou sloupce active i sex oba TRUE. Nejrychlejší způsob, jak najít řádky splňující podmínku, že jsou oba sloupce TRUE, by bylo využití operace bitového AND.

  • Předpokládejme, že bitová mapa indexu pro sloupec active je předem indexována jako 1100110011... (bitové pole o 1 000 000 bitech), a
  • předpokládejme, že bitová mapa indexu pro sloupec sex je předem indexována jako 1010101010... (bitové pole o 1 000 000 bitech).

Poté můžeme provést operaci bitového AND na těchto dvou bitmapových indexech a rychle najít řádky, kde jsou oba sloupce TRUE. Jelikož se jedná o jednoduchou bitovou operaci, výsledky budou získány mnohem rychleji než při skenování jiných indexů.

Kompromisy (Trade-offs)

Bitmapové indexy mohou být velmi efektivní, ale mají několik kompromisů. Existuje mnoho dalších nevýhod, ale nyní se zaměříme pouze na jednu.

A to, že bitmapové indexy jsou vhodnější pro nízkou kardinalitu (tj. když je počet možných hodnot ve sloupci malý). Použití bitmapového indexu na sloupci s vysokou kardinalitou může vést k tomu, že se bitmapa stane velmi velkou.

Pokud použijeme bitmapový index na sloupci s vysokou kardinalitou, musíme vytvořit samostatnou bitovou mapu pro každou jedinečnou hodnotu, což může vyžadovat značné množství úložného prostoru. Například, pokud má sloupec 1 000 000 jedinečných hodnot, musíme vytvořit 1 000 000 bitmap, což může být velmi neefektivní.

A proto my

Můžeme použít Roaring Bitmap jako náhradu za bitmapu, která vzniká při vysoké kardinalitě. Roaring Bitmap má několik charakteristik, ale jeho největší základní filozofie a vlastnost spočívá v tom, že dynamicky volí nejvhodnější způsob ukládání dat na základě jejich hustoty, čímž maximalizuje jak kompresní poměr, tak rychlost operací.

Základní koncept Roaring Bitmap

Dvoustupňové indexování

Roaring Bitmap nejprve projde následujícími 2 fázemi pro uložení celého čísla. I když se mluví o dvoustupňovém indexování, můžete si to představit jako dvourozměrné pole.

  • Extrakce horních 16 bitů: Horních 16 bitů celého čísla je extrahováno a použito jako index. Stává se indexem vnějšího pole dvourozměrného pole o celkové délce 65536. Toto pole ukládá adresy kontejnerů, které budou popsány dále.
  • Extrakce dolních 16 bitů: Dolních 16 bitů celého čísla je extrahováno a použito jako pozice uvnitř kontejneru.

Kontejner

Tento kontejner odpovídá vnitřnímu poli dvourozměrného pole, jak bylo právě přirovnáváno. Avšak na rozdíl od kontejneru horních 16 bitů se vnitřní struktura tohoto kontejneru mění v závislosti na tom, kolik dat obsahuje. Roaring Bitmap podporuje následující 3 typy kontejnerů.

  • Array Container (Kontejner Pole): Tento kontejner se používá, když je uvnitř uloženo málo dat. Konkrétně se používá pro uložení 4096 nebo méně prvků. Tento kontejner je implementován jednoduše jako seřazené pole celých čísel. Prvky lze najít pomocí binárního vyhledávání.
  • Bitmap Container (Kontejner Bitové Mapy): Tento kontejner se používá, když je uvnitř uloženo mnoho dat. Konkrétně se používá pro uložení více než 4096 prvků. Tento kontejner je implementován jako bitová mapa o velikosti 65536 bitů (8192 bajtů). Každý bit indikuje existenci celého čísla na dané pozici.
  • Run Container (Kontejner Sekvence): Tento kontejner se používá pro ukládání souvislých rozsahů celých čísel. Je efektivní pro ukládání souvislých celých čísel, jako jsou například 1, 2, 3, 4, 5. Tento kontejner je implementován jako seznam párů (počáteční hodnota, délka). A co když jsou tam všechny? To znamená, že jsou tam všechny od začátku do konce, takže se uloží pouze jeden pár (0, 65536).

Tento přístup umožňuje Roaring Bitmap velmi efektivně využívat paměť a poskytovat optimální výkon pro různé hustoty dat.

Funkce Roaring Bitmap

Základní funkce

Roaring Bitmap poskytuje následující základní funkce.

  • Vložení (Insertion): Přidá nové celé číslo do bitové mapy. Během tohoto procesu je vybrán vhodný kontejner nebo je kontejner v případě potřeby transformován.
  • Smazání (Deletion): Odstraní existující celé číslo z bitové mapy. I v tomto procesu probíhá vhodné zpracování v závislosti na stavu kontejneru.
  • Vyhledávání (Search): Zjistí, zda se konkrétní celé číslo nachází v bitové mapě. Tento proces se provádí velmi rychle.

Množinové operace

Roaring Bitmap také podporuje následující množinové operace.

  • Sjednocení (Union): Vytvoří novou bitovou mapu, která obsahuje všechny prvky obou bitových map.
  • Průnik (Intersection): Vytvoří novou bitovou mapu, která obsahuje pouze prvky přítomné v obou bitových mapách.
  • Symetrická diference (Symmetric Difference): Vytvoří novou bitovou mapu, která obsahuje prvky přítomné pouze v jedné z obou bitových map.

Tyto operace jsou optimalizovány v závislosti na typu kontejneru bitové mapy a provádějí se velmi rychle.

V jazyce Go

V jazyce Go lze Roaring Bitmap snadno využít pomocí balíčku github.com/RoaringBitmap/roaring. Tento balíček poskytuje všechny funkce Roaring Bitmap a je optimalizován pro specifika jazyka Go.

Instalace

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

Příklad použití

 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)     // Inicializace s 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inicializace s 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Přidání 5
14	b2.Add(10) // Přidání 10
15
16	b2.Remove(12) // Odstranění 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Protože bitmapová operace mění originál, použijeme 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]

Mezi hlavní funkce, které nejsou uvedeny ve výše uvedeném příkladu kódu, patří:

  • Contains(x uint32) bool: Zjišťuje, zda se konkrétní hodnota nachází v bitové mapě
  • GetCardinality() uint64: Vrací počet prvků obsažených v bitové mapě
  • Rank(x uint32) uint64: Vrací počet prvků menších nebo rovných konkrétní hodnotě
  • ToBytes() ([]byte, error): Serializuje bitovou mapu do byte slice
  • FromBytes(data []byte) error: Obnovuje bitovou mapu z byte slice
  • Clone() *Bitmap: Vytváří kopii bitové mapy
  • Clear(): Inicializuje bitovou mapu
  • NextValue(x uint32) int64: Vrací další prvek větší nebo roven x
  • PreviousValue(x uint32) int64: Vrací prvek menší nebo roven x
  • Maximum() uint32: Vrací největší prvek v bitové mapě
  • Minimum() uint32: Vrací nejmenší prvek v bitové mapě

Tyto funkce jsou k dispozici. Podrobnosti naleznete v oficiální dokumentaci.

Pro informaci, balíček roaring obsahuje také balíček podporující uint64 kromě uint32. Poskytuje téměř identické rozhraní, takže jej lze přímo nahradit a použít.

 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)     // Inicializace s 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inicializace s 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Přidání 5
14	b2.Add(10) // Přidání 10
15
16	b2.Remove(12) // Odstranění 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Protože bitmapová operace mění originál, použijeme 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}

Závěrem

Roaring Bitmap je výkonný nástroj, který dokáže efektivně ukládat a manipulovat se sadami celých čísel s vysokou kardinalitou. V jazyce Go lze všechny funkce Roaring Bitmap snadno využít pomocí balíčku github.com/RoaringBitmap/roaring. Tento balíček maximalizuje využití paměti a výkon prostřednictvím různých typů kontejnerů a optimalizovaných operací. Roaring Bitmap lze využít pro efektivní zpracování dat v různých oblastech, jako je databázové indexování, analýza logů a statistické výpočty.

Roaring Bitmap vykazuje vysoký výkon zejména u velkých datových sad a může být užitečný v různých aplikacích. V kombinaci s jednoduchou a efektivní syntaxí jazyka Go poskytuje Roaring Bitmap vývojářům výkonný nástroj. Očekává se, že s dalším vývojem Roaring Bitmap budou přibývat další funkce a optimalizace.

Proč jsem to dělal já? Kvůli indexování jednotlivých tagů a rychlé operaci sjednocení v databázi časových řad.