GoSuda

Živý bitmap

By snowmerak
views ...

Co je to Bitmapa?

Zde je bitmapa typem indexu. Pokud jste přišli s myšlenkou grafiky, můžete se vrátit zpět.

Základní koncept

Bitmapa je forma indexovací technologie v databázích. Vyjadřuje hodnoty konkrétního sloupce jako prvek nebo formu bitového pole nebo vektoru, přičemž každý bit indikuje existenci konkrétní hodnoty v daném sloupci. Proto je nejzákladnější formou přidělení bitového indexu každému řádku a vyjádření existence jako 0 a 1.

Předpokládejme například, že máme tabulku se sloupcem pohlaví. Tato tabulka má 5 řádků a hodnoty ve sloupci pohlaví jsou následující:

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

V tomto případě může být bitový index pro sloupec pohlaví vyjádřen takto:

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

Takže k čemu se to vlastně používá?

Všichni si tedy budou myslet, že to není jen k reprezentaci něčeho takového. Pro správné použití bitového indexu 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ů. A předpokládejme, že spustíme následující dotaz.

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

Tento dotaz vyhledá řádky, kde jsou sloupce active a sex oba TRUE. Nejrychlejší způsob, jak najít řádky splňující podmínku, že oba sloupce jsou TRUE, by bylo využít bitovou operaci AND.

  • Předpokládejme, že bitový index pro sloupec active je 1100110011... (bitové pole s 1 000 000 bity) již indexován, a
  • Předpokládejme, že bitový index pro sloupec sex je 1010101010... (bitové pole s 1 000 000 bity) již indexován.

Pak můžeme provést bitovou operaci AND na dvou bitových indexech, abychom rychle našli řádky, kde jsou oba sloupce TRUE. Vzhledem k tomu, že se jedná o jednoduchou bitovou operaci, lze výsledky získat mnohem rychleji než při skenování jiných indexů.

Kompromisy

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

Bitové indexy jsou vhodnější pro nízkou kardinalitu (tj. když je počet možných hodnot ve sloupci malý). Použití bitových indexů pro sloupce s vysokou kardinalitou může vést k velmi velkým bitmapám.

Použití bitových indexů pro sloupce s vysokou kardinalitou může vyžadovat značné množství úložného prostoru, protože pro každou jedinečnou hodnotu je třeba vytvořit samostatnou bitmapu. Například, pokud sloupec obsahuje 1 000 000 jedinečných hodnot, je třeba vytvořit 1 000 000 bitmap, což může být velmi neefektivní.

A proto my

Namísto bitmap, které trpí vysokou kardinalitou, můžeme použít Roaring Bitmap. Roaring Bitmap má několik vlastností, ale nejdůležitější základní filozofií a vlastností je dynamicky volit nejvhodnější způsob ukládání dat na základě hustoty dat, aby se maximalizovala komprese i rychlost operací.

Základní koncept Roaring Bitmap

Dvoufázové indexování

Roaring Bitmap nejprve prochází následujícími dvěma fázemi, aby uložil celé číslo. Ačkoli se mluví o dvoufázové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 se extrahuje a použije se jako index. To se stane indexem vnějšího pole z dvourozměrného pole o celkové délce 65536. Toto pole ukládá adresy kontejnerů, které budou popsány později.
  • Extrakce dolních 16 bitů: Dolních 16 bitů celého čísla se extrahuje a použije se jako pozice v 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 horních 16 bitů se vnitřní struktura tohoto kontejneru mění v závislosti na množství vnitřních dat. Roaring Bitmap podporuje následující 3 typy kontejnerů:

  • Array Container: Tento kontejner se používá, když je uvnitř uloženo málo dat. Konkrétně se používá pro ukládání 4096 nebo méně prvků. Tento kontejner je implementován jednoduše jako seřazené pole celých čísel. Prvky lze najít binárním vyhledáváním.
  • Bitmap Container: Tento kontejner se používá, když je uvnitř uloženo mnoho dat. Konkrétně se používá pro ukládání více než 4096 prvků. Tento kontejner je implementován jako 65536bitová (8192 bajtů) bitmapa. Každý bit indikuje existenci celého čísla na dané pozici.
  • Run Container: Tento kontejner se používá pro ukládání souvislých rozsahů celých čísel. Je efektivní například pro ukládání souvislých celých čísel jako 1, 2, 3, 4, 5. Tento kontejner je implementován jako seznam párů (počáteční hodnota, délka). Pokud je všechno přítomno? Pak to znamená, že je vše přítomno od začátku do konce, takže stačí uložit pouze (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í: 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.
  • Smazání: Odebere existující celé číslo z bitmapy. Během tohoto procesu se provede vhodná akce v závislosti na stavu kontejneru.
  • Vyhledávání: Zkontroluje, zda se určité celé číslo nachází v bitmapě. Tento proces se provádí velmi rychle.

Operace s množinami

Roaring Bitmap také podporuje následující operace s množinami:

  • Sjednocení (Union): Vytvoří novou bitmapu obsahující všechny prvky ze dvou 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é ze dvou bitmap.

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

V jazyce Go

V jazyce Go lze Roaring Bitmap snadno použí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) // Odebrání 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Operace s bitmapou mění originál, takže použijte 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: Zkontroluje, zda se určitá hodnota nachází v bitmapě
  • 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 určité hodnotě
  • ToBytes() ([]byte, error): Serializuje bitmapu do bajtového řezu
  • FromBytes(data []byte) error: Obnoví bitmapu z bajtového řezu
  • Clone() *Bitmap: Vytvoří klon bitmapy
  • Clear(): Inicializuje bitmapu
  • NextValue(x uint32) int64: Vrátí další prvek větší nebo roven x
  • PreviousValue(x uint32) int64: Vrátí předchozí prvek menší než
  • Maximum() uint32: Vrátí největší prvek v bitmapě
  • Minimum() uint32: Vrátí nejmenší prvek v bitmapě

Podrobnosti naleznete v oficiální dokumentaci.

Mimochodem, balíček roaring obsahuje balíček, který podporuje uint64 i uint32. Protože poskytují téměř identické rozhraní, lze je přímo nahradit.

 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) // Odebrání 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Operace s bitmapou mění originál, takže použijte 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ěr

Roaring Bitmap je výkonný nástroj, který umožňuje efektivně ukládat a manipulovat s množinami 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 díky různým typům kontejnerů a optimalizovaným operacím. Roaring Bitmap lze použít v různých oblastech, jako je databázové indexování, analýza logů a statistické výpočty, k implementaci efektivního zpracování dat.

Roaring Bitmap vyniká zejména vysokým výkonem u rozsáhlých datových sad a může být užitečný v různých aplikacích. V kombinaci s stručnou 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 bude dosaženo více funkcí a optimalizací.

A proč jsem to dělal? Kvůli indexování jednotlivých tagů v časoprostorové databázi a rychlým operacím sjednocení.