GoSuda

Élénk bitkép

By snowmerak views ...

Mi is az a bitmap?

Itt a bitmap az indexek egyik fajtája. Ha grafikai értelemben érkezett ide, kérjük, lépjen vissza.

Alapfogalmak

A bitmap az adatbázisok indexelési technikájának egyik formája. Egy adott oszlop értékeit bitvektor vagy bittömb egy elemeként vagy alakjában ábrázolja, ahol minden bit azt jelzi, hogy az adott oszlopban létezik-e a megadott érték. Ennek megfelelően a legegyszerűbb forma az, hogy minden sorhoz bitindexet rendelünk, és a létezést 0 és 1 értékekkel fejezzük ki.

Tegyük fel például, hogy van egy olyan tábla, amelyben szerepel a nem oszlop. Legyen a táblában 5 sor, a nem oszlop értékei pedig a következők:

  1. Férfi
  2. Nő
  3. Férfi
  4. Nő
  5. Egyéb

Ebben az esetben a nem oszlopra vonatkozó bitmap index például így ábrázolható:

  • Férfi: 10100
  • Nő: 01010
  • Egyéb: 00001

Valójában hol használjuk?

Valószínűleg sokan úgy gondolják, hogy a fenti ábrázolás nem pusztán erre szolgál. Ahhoz, hogy a bitmap indexet ténylegesen hasznosan alkalmazzuk, tekintsük a következő esetet.

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);

Tegyük fel, hogy ebben a táblában 1 000 000 sor található, és a következő lekérdezést futtatjuk.

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

Ez a lekérdezés azokat a sorokat keresi, amelyekben mind az active, mind a sex oszlop értéke TRUE. Ilyen esetben a két feltételt a leggyorsabban úgy elégíthetjük ki, ha bit AND műveletet alkalmazunk.

  • Az active oszlop bitmap indexe előre elkészítve tartalmazza a 1100110011... bittömböt (1 000 000 bit).
  • A sex oszlop bitmap indexe előre elkészítve tartalmazza a 1010101010... bittömböt (1 000 000 bit).

Ezután a két bitmap indexen bit AND műveletet végezve gyorsan megtalálhatjuk azokat a sorokat, amelyekben mindkét oszlop értéke TRUE. Mivel ez egyszerű bitművelet, az eredmény sokkal gyorsabban előáll, mint más indexbejárási módszerek esetén.

Kompromisszumok

A bitmap index rendkívül hatékony lehet, ugyanakkor több kompromisszummal jár. Számos hátránya van, de most csak egyet emelnék ki.

Ez pedig a kardinalitás kérdése: a bitmap index az alacsony cardinality (vagyis az oszlopban előforduló lehetséges értékek kis száma) esetén a legalkalmasabb. Magas cardinality oszlopon történő használat esetén a bitmap jelentősen megnőhet.

Magas cardinality oszlop esetén minden egyedi értékhez külön bitmapet kell létrehozni, ezért a tárigény jelentős lehet. Ha például egy oszlopnak 1 000 000 egyedi értéke van, akkor 1 000 000 bitmapet kell generálni, ami rendkívül nem hatékony lehet.

Megoldásunk

A magas cardinality okozta problémák kiküszöbölésére használhatjuk a Roaring Bitmap nevű szerkezetet. A Roaring Bitmap számos tulajdonsággal rendelkezik, de legfontosabb alapelve és jellemzője: az adatok sűrűségétől függően dinamikusan választja ki a legmegfelelőbb tárolási módot, így maximalizálja mind a tömörítési arányt, mind a műveletek sebességét.

A Roaring Bitmap alapfogalmai

Kétszintű indexelés

A Roaring Bitmap egy egész szám tárolásához először a következő két lépésen megy keresztül. Bár kétszintű indexelésről beszélünk, lényegében elegendő egy kétdimenziós tömbként gondolni rá.

  • Felső 16 bit kinyerése: Az egész szám felső 16 bitjét kinyerjük, és indexként használjuk. Ez a 65536 hosszúságú kétdimenziós tömb külső tömbjének indexe. Ez a tömb a később ismertetendő konténerek címeit tárolja.
  • Alsó 16 bit kinyerése: Az egész szám alsó 16 bitjét kinyerjük, és ezt használjuk a konténeren belüli pozícióként.

Konténerek

A konténer a fent említett kétdimenziós tömb belső tömbjének felel meg. Ellentétben a felső 16 bites tömbbel, a konténer belső szerkezete attól függ, hogy mennyi adat található benne. A Roaring Bitmap a következő 3 konténertípust támogatja.

  • Array Container: Ez a konténer akkor használatos, ha a benne tárolt adatok száma kicsi. Pontosabban, 4096 vagy kevesebb elem tárolása esetén alkalmazzuk. Egyszerűen rendezett egész számok tömbjeként valósul meg, és az elemek bináris kereséssel találhatók meg.
  • Bitmap Container: Ez a konténer akkor használatos, ha a benne tárolt adatok száma nagy. Pontosabban, 4096-nál több elem tárolása esetén alkalmazzuk. 65536 bites (8192 bájtos) bitmapként valósul meg. Minden bit azt jelzi, hogy az adott pozícióban szereplő egész szám létezik-e.
  • Run Container: Ez a konténer folytonos egész számtartományok tárolására szolgál. Például az 1, 2, 3, 4, 5 típusú egymást követő számok tárolása esetén hatékony. (Kezdőérték, hossz) párokat tartalmazó listaként valósul meg. Ha minden érték jelen van, vagyis a teljes tartomány megtelt, akkor elegendő egyetlen (0, 65536) párt tárolni.

Ezek a módszerek biztosítják, hogy a Roaring Bitmap rendkívül hatékonyan használja a memóriát, és különböző adatsűrűségek mellett is optimális teljesítményt nyújtson.

A Roaring Bitmap funkciói

Alapvető funkciók

A Roaring Bitmap a következő alapvető funkciókat biztosítja:

  • Beszúrás: Új egész számot ad hozzá a bitmaphez. Ennek során megfelelő konténert választ, vagy szükség esetén konténert konvertál.
  • Törlés: Eltávolítja a meglévő egész számot a bitmapből. Ennek során is a konténerek állapotától függően történik a megfelelő kezelés.
  • Keresés: Ellenőrzi, hogy egy adott egész szám szerepel-e a bitmapben. Ez a művelet nagyon gyorsan végrehajtódik.

Halmazműveletek

A Roaring Bitmap emellett a következő halmazműveleteket támogatja:

  • Únió (Union): Új bitmapet hoz létre, amely mindkét bitmap összes elemét tartalmazza.
  • Metszet (Intersection): Új bitmapet hoz létre, amely csak azokat az elemeket tartalmazza, amelyek mindkét bitmapben megtalálhatók.
  • Szimmetrikus különbség (Symmetric Difference): Új bitmapet hoz létre, amely azokat az elemeket tartalmazza, amelyek a két bitmap közül pontosan az egyikben szerepelnek.

Ezek a műveletek a bitmap konténertípusától függően optimalizálva vannak, így rendkívül gyorsan végrehajthatók.

Go nyelv esetén

Go nyelven a github.com/RoaringBitmap/roaring csomag segítségével egyszerűen használhatjuk a Roaring Bitmapet. A csomag a Roaring Bitmap összes funkcióját biztosítja, és a Go nyelv sajátosságaihoz igazodva optimalizált.

Telepítés

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

Használati példa

 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álás az 1, 2, 3, 4 értékekkel
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inicializálás a 2, 4, 6, 8, 12 értékekkel
12
13	b1.Add(5)  // 5 hozzáadása
14	b2.Add(10) // 10 hozzáadása
15
16	b2.Remove(12) // 12 eltávolítása
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Mivel a bitmap műveletek módosítják az eredeti példányt, másolatot készítünk a használatukhoz
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]

A fenti példakódban nem szereplő főbb funkciók:

  • Contains(x uint32) bool: Ellenőrzi, hogy egy adott érték szerepel-e a bitmapben
  • GetCardinality() uint64: Visszaadja a bitmapben lévő elemek számát
  • Rank(x uint32) uint64: Visszaadja az x értéknél kisebb vagy egyenlő elemek számát
  • ToBytes() ([]byte, error): Bájtszeletté szerializálja a bitmapet
  • FromBytes(data []byte) error: Visszaállítja a bitmapet bájtszeletből
  • Clone() *Bitmap: Létrehozza a bitmap másolatát
  • Clear(): Inicializálja (üríti) a bitmapet
  • NextValue(x uint32) int64: Visszaadja az x-nél nagyobb vagy vele egyenlő következő elemet
  • PreviousValue(x uint32) int64: Visszaadja az x-nél kisebb vagy vele egyenlő előző elemet
  • Maximum() uint32: Visszaadja a bitmap legnagyobb elemét
  • Minimum() uint32: Visszaadja a bitmap legkisebb elemét

Ezek a funkciók állnak rendelkezésre. Részletekért tekintse meg a hivatalos dokumentációt.

Megjegyzendő, hogy a roaring csomag a uint32 mellett uint64 típust támogató csomagot is tartalmaz. Ez szinte azonos felülettel rendelkezik, ezért közvetlenül lecserélhető a használata.

 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álás az 1, 2, 3, 4 értékekkel
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inicializálás a 2, 4, 6, 8, 12 értékekkel
12
13	b1.Add(5)  // 5 hozzáadása
14	b2.Add(10) // 10 hozzáadása
15
16	b2.Remove(12) // 12 eltávolítása
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Mivel a bitmap műveletek módosítják az eredeti példányt, másolatot készítünk a használatukhoz
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}

Összegzés

A Roaring Bitmap nagy kardinalitású egész számhalmazok hatékony tárolására és kezelésére alkalmas erőteljes eszköz. Go nyelven a github.com/RoaringBitmap/roaring csomag használatával a Roaring Bitmap összes funkciója egyszerűen elérhetővé válik. A csomag különböző konténertípusai és optimalizált műveletei révén maximalizálja a memóriahasználat hatékonyságát és a teljesítményt. Adatbázis-indexelés, naplóelemzés, statisztikai számítások és más területeken is alkalmazható a Roaring Bitmap a hatékony adatfeldolgozás megvalósításához.

A Roaring Bitmap különösen nagy adathalmazok esetén nyújt magas teljesítményt, és számos alkalmazásban hasznos lehet. A Go nyelv tömör és hatékony szintaxisával párosítva a Roaring Bitmap erőteljes eszközt biztosít a fejlesztők számára. A Roaring Bitmap fejlődésével további funkciók és optimalizációk várhatók.

Miért csináltam ezt egyáltalán? Idősoros adatbázisokban az egyes címkék szerinti indexeléshez és a gyors únió műveletekhez.