GoSuda

Élénk Bitmap

By snowmerak
views ...

Mi az a Bitmap?

Itt a bitmap az indexek egyik típusa. Ha grafikára gondolva érkezett, nyomja meg a Vissza gombot.

Alapvető koncepció

A bitmap az adatbázisok indexelési technológiájának egy formája. Egy adott oszlop értékét bit tömbként vagy vektor egyik elemeként vagy formájaként fejezi ki, ahol minden bit azt jelzi, hogy az adott oszlop egy specifikus értéke létezik-e. Ezért a legalapvetőbb formája az, hogy minden row-hoz egy bit indexet rendel, és a létezést 0-val vagy 1-gyel fejezi ki.

Például, tegyük fel, hogy van egy táblánk, amely tartalmaz egy nem oszlopot. Tegyük fel, hogy a táblában 5 row található, és a nem oszlop értékei a következők:

  1. Férfi
  2. Férfi
  3. Egyéb

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

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

Tehát valójában mire használják

Mindenki azt gondolná, hogy ez nem csak az értékek megjelenítésére szolgál. Nézzük meg a következő esetet, hogy megfelelően használhassuk a bitmap indexet.

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 row-t 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 row-kat keresi, ahol az active és a sex oszlop is TRUE. Ekkor a bit AND műveletet használhatjuk a leggyorsabb módszerként a feltételt kielégítő row-k megtalálására, ahol mindkét oszlop TRUE.

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

Ekkor a két bitmap indexen bit AND műveletet hajtva gyorsan megtalálhatjuk azokat a row-kat, ahol mindkét oszlop TRUE. Mivel ez egy egyszerű bitművelet, sokkal gyorsabban kaphatjuk meg az eredményt, mint más index szkennelésekkel.

Kompromisszumok (Trade-offs)

A bitmap index nagyon hatékony lehet, de van néhány kompromisszuma. Sok más hátránya is van, de most csak egyet említünk.

A bitmap index jobban megfelel alacsony kardinalitású (azaz kevés lehetséges értékkel rendelkező oszlopok) esetében. Magas kardinalitású oszlopokra alkalmazva a bitmap index nagyon naggyá válhat.

Ha magas kardinalitású oszlopra használunk bitmap indexet, minden egyedi értékhez külön bitmapot kell létrehozni, ami sok tárhelyet igényelhet. Például, ha egy oszlopban 1 000 000 egyedi érték van, 1 000 000 bitmapot kell létrehozni, ami rendkívül ineffektív lehet.

Ezért mi

A magas kardinalitásból adódó bitmap helyett a Roaring Bitmap nevű megoldást használhatjuk. A Roaring Bitmapnak számos tulajdonsága van, de a legnagyobb alapvető filozófia és jellemző az, hogy dinamikusan kiválasztja a legmegfelelőbb tárolási módot 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épcsős indexelés

Egy egész szám tárolásához a Roaring Bitmap először a következő két lépésen megy keresztül. Bár kétlépcsős indexelésnek hívjuk, gondolhatunk rá egyszerűen kétdimenziós tömbként.

  • 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 a 65536 hosszúságú kétdimenziós tömbben. Ez a tömb tárolja a későbbiekben részletezendő konténerek címeit.
  • 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éner

Ez a konténer felel meg a kétdimenziós tömb belső tömbjének, ahogy az előző hasonlatban említettük. Azonban a felső 16 bithez képest ez a konténer a benne lévő adatok mennyiségétől függően változó belső struktúrával rendelkezik. 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árol. Ez a konténer egyszerűen egy rendezett egész szám tömbként van megvalósítva. Az elemek bináris kereséssel találhatók meg.
  • 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árol. Ez a konténer 65536 bit (8192 byte) bitmapként van megvalósítva. 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 összefüggő egész szám tartományok tárolására használják. Például hatékony, ha összefüggő egész számokat tárol, mint az 1, 2, 3, 4, 5. Ez a konténer (kezdő érték, hossz) párok listájaként van megvalósítva. Ha minden érték benne van? Akkor csak egyetlen (0, 65536) párt kell tárolni, ami azt jelenti, hogy az elejétől a végéig minden benne van.

Ez a módszer lehetővé teszi, hogy a Roaring Bitmap 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égek esetén.

A Roaring Bitmap funkciói

Alapfunkciók

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

  • Beszúrás: Új egész szám hozzáadása a bitmaphoz. E folyamat során kiválasztható a megfelelő konténer, vagy szükség esetén a konténer átalakítható.
  • Törlés: Meglévő egész szám eltávolítása a bitmappból. E folyamat során is a konténer állapotának megfelelő kezelés történik.
  • Keresés: Annak ellenőrzése, hogy egy adott egész szám létezik-e a bitmappban. 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 tartalmazza mindkét bitmap összes elemét.
  • Metszet (Intersection): Létrehoz egy új bitmapot, amely csak azokat az elemeket tartalmazza, amelyek mindkét bitmappban megtalálhatók.
  • Szimmetrikus különbség (Symmetric Difference): Létrehoz egy új bitmapot, amely azokat az elemeket tartalmazza, amelyek csak az egyik bitmappban vannak jelen.

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 nyelven

Go nyelven a github.com/RoaringBitmap/roaring csomag használható a Roaring Bitmap egyszerű alkalmazásához. 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

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 1, 2, 3, 4 értékekkel
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inicializálás 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 eredetit, klónt kell használni
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]

Az alábbiakban felsorolt fő funkciók nem szerepelnek a fenti példakódban:

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

Ezek a funkciók elérhetők. További részletekért lásd a hivatalos dokumentációt.

Megjegyzendő, hogy a roaring csomag tartalmaz egy olyan csomagot is, amely az uint32 mellett az uint64-et is támogatja. Mivel szinte azonos interfészt 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)     // Inicializálás 1, 2, 3, 4 értékekkel
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inicializálás 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 eredetit, klónt kell használni
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 egy hatékony eszköz, amellyel hatékonyan tárolhatók és manipulálhatók a magas kardinalitású egész szám halmazok. A Go nyelven a github.com/RoaringBitmap/roaring csomag használatával a Roaring Bitmap összes funkciója könnyen alkalmazható. Ez a csomag különböző konténer típusokkal és optimalizált műveletekkel maximalizálja a memória kihasználását és a teljesítményt. A Roaring Bitmap felhasználható hatékony adatfeldolgozás megvalósítására különböző területeken, mint például adatbázis indexelés, naplóelemzés és statisztikai számítások.

A Roaring Bitmap különösen nagy teljesítményt nyújt nagyméretű adathalmazok esetén, és hasznos lehet különböző alkalmazásokban. A Go nyelv tömör és hatékony szintaxisával kombinálva a Roaring Bitmap erős eszközt biztosít a fejlesztők számára. Várható, hogy a Roaring Bitmap fejlődésével a jövőben még több funkció és optimalizáció valósul meg.

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