GoSuda

Eloisa bitmap

By snowmerak views ...

Mikä on bitmap?

Tässä bitmap tarkoittaa yhtä indeksityyppiä. Jos tulit etsimään grafiikkaan liittyvää asiaa, voit palata takaisin.

Peruskäsite

Bitmap on tietokannan indeksointitekniikan muoto. Se esittää tietyn sarakkeen arvot bittitaulukkona tai vektorin alkioina siten, että kukin bitti ilmaisee, onko kyseisen sarakkeen tietty arvo olemassa. Yksinkertaisin muoto on siis antaa jokaiselle riville bittiindeksi ja esittää olemassaolo arvoina 0 ja 1.

Oletetaan esimerkiksi taulu, jossa on sukupuolisarake. Taulussa on viisi riviä, ja sukupuolisarakkeen arvot ovat seuraavat:

  1. Mies
  2. Nainen
  3. Mies
  4. Nainen
  5. Muu

Tässä tapauksessa sukupuolisarakkeen bitmap-indeksi voidaan esittää seuraavasti:

  • Mies: 10100
  • Nainen: 01010
  • Muu: 00001

Mihin tätä oikeasti käytetään

Monet varmasti ajattelevat, ettei tällaista tarvitse esittää vain sen vuoksi. Tarkastellaan seuraavaa tapausta, jotta bitmap-indeksin käyttö tulee selväksi.

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

Oletetaan, että tässä taulussa on 1 000 000 riviä, ja suoritetaan seuraava kysely.

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

Tämä kysely hakee rivit, joilla sekä active- että sex-sarake ovat TRUE. Nopein tapa löytää rivit, jotka täyttävät molemmat ehdot, on käyttää bittien AND-operaatiota.

  • Active-sarakkeen bitmap-indeksi on ennalta indeksoitu muodossa 1100110011... (1 000 000 bitin taulukko).
  • Sex-sarakkeen bitmap-indeksi on ennalta indeksoitu muodossa 1010101010... (1 000 000 bitin taulukko).

Suorittamalla bittien AND-operaation näille kahdelle bitmap-indeksille voidaan nopeasti löytää rivit, joilla molemmat sarakkeet ovat TRUE. Koska kyseessä on yksinkertainen bittioperaatio, tulos saadaan huomattavasti nopeammin kuin muilla indeksiskannauksilla.

Kompromissit

Bitmap-indeksit voivat olla hyvin tehokkaita, mutta niihin liittyy useita kompromisseja. Niitä on paljon, mutta tässä käsitellään vain yhtä.

Se on se, että bitmap-indeksit soveltuvat paremmin matalalle cardinality-arvolle, eli tilanteisiin, joissa sarakkeen mahdollisten arvojen määrä on pieni. Jos bitmap-indeksiä käytetään sarakkeessa, jonka cardinality on korkea, bitmapista voi tulla hyvin suuri.

Korkean cardinality-arvon sarakkeessa jokaiselle yksilölliselle arvolle on luotava oma bitmap, joten tallennustilaa tarvitaan paljon. Jos esimerkiksi sarakkeessa on 1 000 000 yksilöllistä arvoa, on luotava 1 000 000 bitmapia, mikä voi olla erittäin tehotonta.

Joten mitä me teemme

Korkean cardinality-arvon ongelmaan voidaan vastata käyttämällä Roaring Bitmap -nimistä rakennetta. Roaring Bitmapilla on useita ominaisuuksia, mutta sen tärkein perusperiaate ja ominaisuus on seuraava: valitaan dynaamisesti datan tiheyden mukaan sopivin tallennusmenetelmä, jotta sekä pakkausaste että laskentanopeus saadaan mahdollisimman suuriksi.

Roaring Bitmapin peruskäsite

Kaksivaiheinen indeksointi

Roaring Bitmap tallentaa kokonaisluvun ensin seuraavien kahden vaiheen kautta. Vaikka kyseessä on kaksivaiheinen indeksointi, sitä voi ajatella yksinkertaisesti kaksiulotteisena taulukkona.

  • Ylempien 16 bitin erottaminen: Kokonaisluvun ylemmät 16 bittiä erotetaan ja käytetään indeksinä. Ne vastaavat ulomman taulukon indeksiä kaksiulotteisessa taulukossa, jonka pituus on yhteensä 65 536. Tämä taulukko tallentaa myöhemmin kuvattavan containerin osoitteen.
  • Alempien 16 bitin erottaminen: Kokonaisluvun alemmat 16 bittiä erotetaan ja käytetään paikkana containerin sisällä.

Container

Container vastaa edellä käytettyä vertauskuvaa kaksiulotteisen taulukon sisemmästä taulukosta. Toisin kuin ylempien 16 bitin taulukko, container muuttaa sisäistä rakennettaan sen mukaan, kuinka paljon dataa siinä on. Roaring Bitmap tukee seuraavia kolmea containeria.

  • Array Container: Tätä containeria käytetään, kun sen sisällä on vähän dataa. Tarkemmin sanottuna sitä käytetään, kun tallennettavia alkioita on enintään 4 096. Container on toteutettu yksinkertaisena lajiteltuna kokonaislukutaulukkona. Alkion voi etsiä binäärihaulla.
  • Bitmap Container: Tätä containeria käytetään, kun sen sisällä on paljon dataa. Tarkemmin sanottuna sitä käytetään, kun tallennettavia alkioita on yli 4 096. Container on toteutettu 65 536 bitin (8 192 tavun) bitmapina. Kukin bitti ilmaisee, onko kyseisessä kohdassa oleva kokonaisluku olemassa.
  • Run Container: Tätä containeria käytetään jatkuvien kokonaislukuvälien tallentamiseen. Esimerkiksi jatkuvat kokonaisluvut 1, 2, 3, 4 ja 5 tallennetaan tehokkaasti. Container on toteutettu (alkuarvo, pituus) -parien listana. Jos kaikki arvot ovat olemassa, eli koko väli alusta loppuun on täynnä, riittää tallentaa vain yksi pari (0, 65 536).

Tämän menetelmän ansiosta Roaring Bitmap käyttää muistia erittäin tehokkaasti ja tarjoaa optimaalisen suorituskyvyn erilaisilla datan tiheyksillä.

Roaring Bitmapin toiminnot

Perustoiminnot

Roaring Bitmap tarjoaa seuraavat perustoiminnot:

  • Lisäys: Lisää uuden kokonaisluvun bitmapiin. Tässä prosessissa valitaan sopiva container tai tarvittaessa muunnetaan container toiseksi.
  • Poisto: Poistaa olemassa olevan kokonaisluvun bitmapista. Tässäkin prosessissa käsitellään tilanne containerin tilan mukaan.
  • Haku: Tarkistaa, onko tietty kokonaisluku bitmapissa. Tämä toiminto suoritetaan erittäin nopeasti.

Joukko-operaatiot

Roaring Bitmap tukee lisäksi seuraavia joukko-operaatioita:

  • Yhdiste (Union): Luo uuden bitmapin, joka sisältää kaikki kahden bitmapin alkiot.
  • Leikkaus (Intersection): Luo uuden bitmapin, joka sisältää vain ne alkiot, jotka ovat molemmissa bitmapeissa.
  • Symmetrinen erotus (Symmetric Difference): Luo uuden bitmapin, joka sisältää alkiot, jotka ovat vain toisessa kahdesta bitmapista.

Nämä operaatiot on optimoitu bitmapin containerityypin mukaan, joten ne suoritetaan erittäin nopeasti.

Go-kieli

Go-kielessä Roaring Bitmapia voi käyttää helposti github.com/RoaringBitmap/roaring -paketilla. Paketti tarjoaa kaikki Roaring Bitmapin toiminnot, ja se on optimoitu Go-kielen ominaisuuksien mukaisesti.

Asennus

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

Käyttöesimerkki

 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)     // Alustetaan arvoilla 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Alustetaan arvoilla 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Lisätään 5
14	b2.Add(10) // Lisätään 10
15
16	b2.Remove(12) // Poistetaan 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Bitmap-operaatio muuttaa alkuperäistä, joten käytetään kopiota
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]

Muita tärkeitä toimintoja, joita ei ole yllä olevassa esimerkkikoodissa, ovat:

  • Contains(x uint32) bool: Tarkistaa, onko tietty arvo bitmapissa
  • GetCardinality() uint64: Palauttaa bitmapissa olevien alkioiden määrän
  • Rank(x uint32) uint64: Palauttaa alkioiden määrän, jotka ovat pienempiä tai yhtä suuria kuin annettu arvo
  • ToBytes() ([]byte, error): Sarjallistaa bitmapin tavuviipaleeksi
  • FromBytes(data []byte) error: Palauttaa bitmapin tavuviipaleesta
  • Clone() *Bitmap: Luo bitmapista kopion
  • Clear(): Tyhjentää bitmapin
  • NextValue(x uint32) int64: Palauttaa seuraavan alkion, joka on suurempi tai yhtä suuri kuin x
  • PreviousValue(x uint32) int64: Palauttaa edellisen alkion, joka on pienempi kuin x tai yhtä suuri
  • Maximum() uint32: Palauttaa bitmapin suurimman alkion
  • Minimum() uint32: Palauttaa bitmapin pienimmän alkion

Näitä toimintoja on saatavilla. Lisätietoja löytyy virallisesta dokumentaatiosta.

Roaring-paketti sisältää myös uint32-tyypin lisäksi uint64-tyyppiä tukevan paketin. Se tarjoaa lähes samat rajapinnat, joten sen voi vaihtaa suoraan käyttöön.

 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)     // Alustetaan arvoilla 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Alustetaan arvoilla 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Lisätään 5
14	b2.Add(10) // Lisätään 10
15
16	b2.Remove(12) // Poistetaan 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Bitmap-operaatio muuttaa alkuperäistä, joten käytetään kopiota
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}

Lopuksi

Roaring Bitmap on tehokas työkalu, jolla korkean cardinality-arvon kokonaislukujoukkoja voidaan tallentaa ja käsitellä tehokkaasti. Go-kielessä github.com/RoaringBitmap/roaring -paketin avulla Roaring Bitmapin kaikki toiminnot ovat helposti käytettävissä. Paketti tarjoaa useita containerityyppejä ja optimoituja operaatioita, jotka maksimoivat muistin käytön ja suorituskyvyn. Roaring Bitmapia voi hyödyntää tietokantojen indeksoinnissa, lokianalyysissä, tilastolaskennassa ja monilla muilla aloilla tehokkaan datankäsittelyn toteuttamiseksi.

Roaring Bitmap toimii erityisen hyvin suurilla tietoaineistoilla, ja sitä voi hyödyntää monissa eri sovelluksissa. Yhdistettynä Go-kielen selkeään ja tehokkaaseen syntaksiin se tarjoaa kehittäjille vahvan työkalun. Roaring Bitmapin kehityksen myötä on odotettavissa lisää ominaisuuksia ja optimointeja.

Miksi tein tämän? Syynä oli aikasarjatietokannan tarve indeksoida jokainen tagi erikseen ja suorittaa nopeita yhdiste-operaatioita.