GoSuda

Élénk Bitmap

By snowmerak
views ...

Mi az a Bitmap?

Itt a bitmap egyfajta index. Ha grafikára gondolva érkezett, nyomja meg a vissza gombot.

Alapvető koncepció

A bitmap egyfajta adatbázis-indexelési technológia. Egy adott oszlop értékét bit tömbként vagy vektor elemeként vagy formájaként fejezi ki, ahol minden bit azt jelzi, hogy az adott oszlop adott értéke létezik-e. Ezért a legalapvetőbb forma az, hogy minden sornak hozzárendelünk egy bit indexet, és a létezést 0-val és 1-gyel fejezzük ki.

Tegyük fel például, hogy van egy táblánk egy nem oszloppal. Tegyük fel, hogy ebben a táblában 5 sor van, és a nem oszlop értékei a következők:

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

Ebben az esetben a nem oszlophoz tartozó bitmap index a következőképpen fejezhető ki:

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

Szóval, mire is használják valójában?

Mindenki azt gondolja majd, hogy ez nem csupán ennek a jelzésére szolgál. Ahhoz, hogy a bitmap indexet megfelelően használhassuk, vegyük figyelembe 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 ez a tábla 1 000 000 sort tartalmaz. Tegyük fel, hogy a következő lekérdezést hajtjuk végre.

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

Ez a lekérdezés azokat a sorokat keresi, ahol az active és a sex oszlop is TRUE. Ekkor a bitwise AND műveletet felhasználhatjuk arra, hogy a leggyorsabban megtaláljuk azokat a sorokat, amelyek mindkét oszlop TRUE feltételének megfelelnek.

  • Tegyük fel, hogy az active oszlophoz tartozó bitmap index 1100110011... (1 000 000 bites tömb) már indexelve van,
  • és a sex oszlophoz tartozó bitmap index 1010101010... (1 000 000 bites tömb) már indexelve van.

Ekkor a két bitmap indexen bitwise AND műveletet hajtva gyorsan megtalálhatjuk azokat a sorokat, ahol mindkét oszlop TRUE. Mivel ez egy egyszerű bitwise művelet, sokkal gyorsabban kaphatunk eredményt, mint más index szkennelésekkel.

Kompromisszumok

Bár a bitmap index nagyon hatékony lehet, vannak bizonyos kompromisszumai. Sok más hátránya is van, de most csak egyet fogunk megemlíteni.

A bitmap indexek jobban alkalmasak alacsony kardinalitású (azaz kevés lehetséges értékkel rendelkező oszlopok) oszlopokhoz. Magas kardinalitású oszlopokban a bitmap indexek használata nagyon naggyá teheti a bitmapot.

Ha magas kardinalitású oszlopokban használunk bitmap indexeket, minden egyedi értékhez külön bitmapot kell generálni, ami sok tárhelyet igényelhet. Például, ha egy oszlop 1 000 000 egyedi értéket tartalmaz, akkor 1 000 000 bitmapot kell generálni, ami nagyon ineffektív lehet.

Tehát mi

A magas kardinalitásból adódó bitmapok helyett használhatunk egy Roaring Bitmap nevű megoldást. A Roaring Bitmapnak számos jellemzője van, de a legnagyobb alapvető filozófia és jellemző az, hogy dinamikusan választja ki a legmegfelelőbb tárolási módszert az adatsűrűség alapján, maximalizálva mind a tömörítési arányt, mind a műveleti sebességet.

A Roaring Bitmap alapkoncepciója

Kétlépéses indexelés

A Roaring Bitmap egy egész szám tárolásához először a következő 2 lépésen megy keresztül. Ez nem más, mint egy 2D tömb.

  • Felső 16 bit kivonása: Az egész szám felső 16 bitjét kivonjuk, és ezt használjuk indexként. Ez lesz a külső tömb indexe egy 65536 hosszú 2D tömbben. Ez a tömb a későbbiekben tárgyalandó konténerek címét tárolja.
  • Alsó 16 bit kivonása: Az egész szám alsó 16 bitjét kivonjuk, és ezt használjuk a konténeren belüli pozícióként.

Konténerek

Ez a konténer, ahogy az imént hasonlítottuk, a 2D tömb belső tömbje. Azonban a felső 16 bitétől eltérően ennek a konténernek a belső szerkezete attól függően változik, hogy mennyi adat van benne. A Roaring Bitmap a következő 3 konténert támogatja.

  • Array Container: Ezt a konténert akkor használják, ha kevés adat van tárolva. Pontosabban, akkor használják, ha 4096 vagy kevesebb elemet tárolnak. Ez a konténer egyszerűen rendezett egész szám tömbként van implementálva. Bináris kereséssel találhatók meg az elemek.
  • Bitmap Container: Ezt a konténert akkor használják, ha sok adat van tárolva. Pontosabban, akkor használják, ha több mint 4096 elemet tárolnak. Ez a konténer 65536 bites (8192 bájtos) bitmapként van implementálva. Minden bit azt jelzi, hogy az adott pozíción lévő egész szám létezik-e.
  • Run Container: Ezt a konténert akkor használják, ha összefüggő egész szám tartományokat tárolnak. Például hatékonyan tárolja az olyan összefüggő egész számokat, mint az 1, 2, 3, 4, 5. Ez a konténer (kezdő érték, hossz) párok listájaként van implementálva. Ha minden megvan? Akkor csak egy (0, 65536) értéket kell tárolni, ami azt jelenti, hogy az elejétől a végéig minden megvan.

Ez a megközelítés lehetővé teszi a Roaring Bitmap számára, hogy rendkívül hatékonyan használja a memóriát, és optimális teljesítményt nyújtson a különböző adatsűrűségekhez.

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 bitmaphoz. Ebben a folyamatban kiválasztható a megfelelő konténer, vagy szükség esetén átalakítható a konténer.
  • Törlés: Egy meglévő egész számot távolít el a bitmapból. Ebben a folyamatban is megfelelő kezelés történik a konténer állapotától függően.
  • Keresés: Ellenőrzi, hogy egy adott egész szám létezik-e a bitmapban. Ez a folyamat rendkívül gyorsan végrehajtható.

Halmazműveletek

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

  • Egyesítés (Union): Létrehoz egy új bitmapot, amely mindkét bitmap összes elemét tartalmazza.
  • Metszet (Intersection): Létrehoz egy új bitmapot, amely csak azokat az elemeket tartalmazza, amelyek mindkét bitmapban megtalálhatók.
  • Szimmetrikus különbség (Symmetric Difference): Létrehoz egy új bitmapot, amely csak azokat az elemeket tartalmazza, amelyek csak az egyik bitmapban találhatók.

Ezek a műveletek a bitmap konténer típusától függően optimalizáltak, és rendkívül gyorsan végrehajthatók.

Go nyelvben

Go nyelven a github.com/RoaringBitmap/roaring csomag segítségével könnyedén használható a Roaring Bitmap. Ez a csomag a Roaring Bitmap összes funkcióját biztosítja, és optimalizálva van a Go nyelv sajátosságaihoz.

Telepítés

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

Példa használatra

 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)     // 1, 2, 3, 4-gyel inicializálva
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // 2, 4, 6, 8, 12-vel inicializálva
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 eredetit, használjunk klónt
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ő funkciók:

  • Contains(x uint32) bool: Ellenőrzi, hogy egy adott érték létezik-e a bitmapban.
  • GetCardinality() uint64: Visszaadja a bitmapban található elemek számát.
  • Rank(x uint32) uint64: Visszaadja az x-nél kisebb vagy egyenlő elemek számát.
  • ToBytes() ([]byte, error): Szerializálja a bitmapot egy bájtszeletre.
  • FromBytes(data []byte) error: Helyreállítja a bitmapot egy bájtszeletből.
  • Clone() *Bitmap: Létrehozza a bitmap másolatát.
  • Clear(): Inicializálja a bitmapot.
  • NextValue(x uint32) int64: Visszaadja a következő, x-nél nagyobb vagy egyenlő elemet.
  • PreviousValue(x uint32) int64: Visszaadja az x-nél kisebb vagy egyenlő előző elemet.
  • Maximum() uint32: Visszaadja a bitmap legnagyobb elemét.
  • Minimum() uint32: Visszaadja a bitmap legkisebb elemét.

További részletekért lásd a hivatalos dokumentációt.

Megjegyzendő, hogy a roaring csomag nem csak uint32, hanem uint64 típusokat is támogató csomagot tartalmaz. Mivel szinte azonos felületet biztosít, közvetlenül cserélhető.

 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)     // 1, 2, 3, 4-gyel inicializálva
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // 2, 4, 6, 8, 12-vel inicializálva
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 eredetit, használjunk klónt
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}

Befejezésül

A Roaring Bitmap egy hatékony eszköz a magas kardinalitású egész szám halmazok hatékony tárolására és kezelésére. Go nyelven a github.com/RoaringBitmap/roaring csomag segítségével könnyedén kihasználhatók a Roaring Bitmap összes funkciója. Ez a csomag különböző konténer típusokkal és optimalizált műveletekkel maximalizálja a memóriahasználatot és a teljesítményt. A Roaring Bitmap felhasználható adatbázis-indexelésben, logelemzésben, statisztikai számításokban és számos más területen a hatékony adatfeldolgozás megvalósítására.

A Roaring Bitmap különösen nagy adathalmazok esetén mutat magas teljesítményt, és számos alkalmazásban hasznosan alkalmazható. A Go nyelv tömör és hatékony szintaxisával kombinálva a Roaring Bitmap hatékony eszközt biztosít a fejlesztők számára. Várhatóan a Roaring Bitmap fejlődésével további funkciók és optimalizációk is megvalósulnak majd.

És miért csináltam ezt? Az idősoros adatbázisokban a címkék szerinti indexeléshez és a gyors egyesítési műveletekhez.