GoSuda

Živé bitmapy

By snowmerak views ...

Co je bitmapa?

Zde je bitmapa jedním druhem indexu. Pokud jste sem přišli s představou grafiky, stačí se vrátit zpět.

Základní pojmy

Bitmapa je jednou z forem indexovacích technik databází. Hodnoty konkrétního sloupce vyjadřuje jako prvek bitového pole nebo vektoru, přičemž každý bit udává, zda se daná hodnota ve sloupci vyskytuje. Nejzákladnější podoba tedy přiřazuje každému řádku bitový index a existenci hodnoty vyjadřuje pomocí 0 a 1.

Představme si například tabulku se sloupcem pohlaví. Tabulka obsahuje 5 řádků a hodnoty sloupce pohlaví jsou následující:

  1. muž
  2. žena
  3. muž
  4. žena
  5. jiné

V tomto případě lze bitmapový index sloupce pohlaví vyjádřit takto:

  • muž: 10100
  • žena: 01010
  • jiné: 00001

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

Většina čtenářů si jistě pomyslí, že se bitmapy nepoužívají pouze k vyjádření těchto hodnot. Abychom ukázali, jak se bitmapový index správně využívá, uvažujme 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 obsahuje 1 000 000 řádků. Dále spusťme následující dotaz.

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

Tento dotaz vyhledá řádky, v nichž jsou sloupce active i sex nastaveny na TRUE. Nejrychlejším způsobem, jak najít řádky splňující podmínku, že oba sloupce jsou TRUE, je pravděpodobně využití bitové operace AND.

  • Bitmapový index sloupce active je předem indexován jako 1100110011... (bitové pole o 1 000 000 bitech) a
  • bitmapový index sloupce sex je předem indexován jako 1010101010... (bitové pole o 1 000 000 bitech).

Provedením operace bitové AND nad oběma bitmapovými indexy lze rychle najít řádky, v nichž jsou oba sloupce TRUE. Jelikož jde o jednoduchou bitovou operaci, výsledek bude pravděpodobně získán výrazně rychleji než při použití jiných způsobů průchodu indexem.

Kompromisy

Bitmapové indexy mohou být velmi efektivní, ale mají určité kompromisy. Existuje mnoho dalších nevýhod, nyní se však zaměřme pouze na jednu z nich.

Bitmapové indexy se hodí spíše pro nízkou kardinalitu (tedy případy, kdy sloupec má malý počet možných hodnot). Použití bitmapového indexu u sloupce s vysokou kardinalitou může vést k velmi velkým bitmapám.

Při použití bitmapového indexu u sloupce s vysokou kardinalitou je nutné vytvořit samostatnou bitmapu pro každou jedinečnou hodnotu, a proto může být vyžadováno značné úložiště. Pokud má například sloupec 1 000 000 jedinečných hodnot, je třeba vytvořit 1 000 000 bitmap, což může být velmi neefektivní.

Co tedy použijeme

Problémy bitmap při vysoké kardinalitě lze nahradit použitím struktury nazvané Roaring Bitmap. Roaring Bitmap má řadu vlastností, avšak jeho nejdůležitější principiální myšlenkou a vlastností je dynamicky vybírat nejvhodnější způsob uložení podle hustoty dat, čímž se maximalizuje jak míra komprese, tak rychlost operací.

Základní pojmy Roaring Bitmap

Dvoustupňové indexování

Roaring Bitmap ukládá celé číslo nejprve prostřednictvím těchto dvou kroků. Ačkoli se jedná o dvoustupňové indexování, lze si ho jednoduše představit jako dvourozměrné pole.

  • Extrakce horních 16 bitů: horních 16 bitů celého čísla se extrahuje a použije jako index. Jde o index vnějšího pole z dvourozměrného pole o délce 65536. Toto pole ukládá adresu kontejneru, který je popsán níže.
  • Extrakce dolních 16 bitů: dolních 16 bitů celého čísla se extrahuje a použije jako pozice uvnitř kontejneru.

Kontejnery

Tento kontejner odpovídá vnitřnímu poli ve dvourozměrném poli, jak jsme přirovnali. Na rozdíl od pole horních 16 bitů se však jeho vnitřní struktura mění podle množství uložených dat. Roaring Bitmap podporuje tyto 3 typy kontejnerů.

  • Array Container: tento kontejner se používá, když je v něm uloženo málo dat. Konkrétně se používá pro uložení 4096 nebo méně prvků. Je implementován jako jednoduché seřazené pole celých čísel. Prvek lze vyhledat binárním vyhledáváním.
  • Bitmap Container: tento kontejner se používá, když je v něm uloženo mnoho dat. Konkrétně se používá pro uložení více než 4096 prvků. Je implementován jako bitmapa o 65536 bitech (8192 bajtů). Každý bit udává, zda se celé číslo na dané pozici vyskytuje.
  • Run Container: tento kontejner se používá k ukládání souvislých rozsahů celých čísel. Je efektivní například pro souvislé hodnoty jako 1, 2, 3, 4, 5. Je implementován jako seznam dvojic (počáteční hodnota, délka). Pokud jsou přítomna všechna čísla? Znamená to, že jsou přítomna od začátku až do konce, a stačí tedy uložit pouze jednu dvojici (0, 65536).

Tento přístup umožňuje, aby Roaring Bitmap velmi efektivně využívala paměť a poskytovala 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í: přidá nové celé číslo do bitmapy. Během tohoto procesu lze vybrat vhodný kontejner nebo v případě potřeby kontejner převést.
  • Odstranění: odebere existující celé číslo z bitmapy. I zde se podle stavu kontejneru provádí příslušné zpracování.
  • Vyhledávání: ověří, zda se dané celé číslo v bitmapě nachází. Tento proces probíhá velmi rychle.

Operace nad množinami

Roaring Bitmap dále podporuje následující operace nad množinami.

  • Sjednocení (Union): vytvoří novou bitmapu obsahující všechny prvky obou bitmap.
  • Průnik (Intersection): vytvoří novou bitmapu obsahující pouze prvky, které se nacházejí v obou bitmapách.
  • Symetrický rozdíl (Symmetric Difference): vytvoří novou bitmapu obsahující prvky, které se nacházejí pouze v jedné z obou bitmap.

Tyto operace jsou optimalizovány podle typu kontejneru a provádějí se velmi rychle.

V jazyce Go

V jazyce Go lze Roaring Bitmap snadno používat pomocí balíčku github.com/RoaringBitmap/roaring. Tento balíček poskytuje všechny funkce Roaring Bitmap a je optimalizován podle specifik 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 hodnotami 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // inicializace hodnotami 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) // odebrání 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// operace nad bitmapou mění originál, proto se použije 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]

Mezi hlavní funkce, které nejsou uvedeny v předchozím příkladu, patří:

  • Contains(x uint32) bool: ověří, zda se daná hodnota v bitmapě nachází
  • GetCardinality() uint64: vrátí počet prvků obsažených v bitmapě
  • Rank(x uint32) uint64: vrátí počet prvků menších nebo rovných dané hodnotě
  • ToBytes() ([]byte, error): serializuje bitmapu do bajtového řezu
  • FromBytes(data []byte) error: obnoví bitmapu z bajtového řezu
  • Clone() *Bitmap: vytvoří kopii bitmapy
  • Clear(): inicializuje bitmapu
  • NextValue(x uint32) int64: vrátí další prvek větší nebo rovný x
  • PreviousValue(x uint32) int64: vrátí předchozí prvek menší než x nebo
  • Maximum() uint32: vrátí největší prvek bitmapy
  • Minimum() uint32: vrátí nejmenší prvek bitmapy

Existují tyto funkce. Podrobnosti naleznete v oficiální dokumentaci.

Pro informaci, balíček roaring obsahuje také balíček podporující nejen uint32, ale i uint64. Poskytuje téměř stejné rozhraní, takže jej lze použít přímou záměnou.

 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 hodnotami 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // inicializace hodnotami 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) // odebrání 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// operace nad bitmapou mění originál, proto se použije 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}

Závěr

Roaring Bitmap je silný nástroj pro efektivní ukládání a manipulaci s množinami celých čísel s vysokou kardinalitou. V jazyce Go lze pomocí balíčku github.com/RoaringBitmap/roaring snadno využít všechny funkce Roaring Bitmap. Tento balíček díky různým typům kontejnerů a optimalizovaným operacím maximalizuje využití paměti a výkon. Roaring Bitmap lze využít v mnoha oblastech, například při indexování databází, analýze logů nebo výpočtech statistik, k efektivnímu zpracování dat.

Roaring Bitmap vyniká zejména na velkých datových sadách a lze jej použít v mnoha aplikacích. V kombinaci se stručnou a efektivní syntaxí jazyka Go poskytuje vývojářům silný nástroj. Do budoucna lze očekávat další vývoj Roaring Bitmap, s novými funkcemi a optimalizacemi.

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