GoSuda

Vilkas bittikartta

By snowmerak
views ...

비트맵이란?

여기서 비트맵은 인덱스의 한 종류입니다. 그래픽스 생각하고 들어오셨다면 뒤로가기 누르시면 됩니다.

기본 개념

비트맵은 데이터베이스의 인덱싱 기술의 한 형태입니다. 특정 칼럼의 값을 비트 배열이나 벡터의 한 원소나 형태로 표현하여, 각 비트가 해당 칼럼의 특정 값이 존재하는지 여부를 나타냅니다. 그래서 가장 기본적인 형태는 각 row에 대해 비트 인덱스를 할당하고 존재 여부를 0과 1로 표현하는 것입니다.

예를 들어, 성별 칼럼이 있는 테이블이 있다고 가정해봅시다. 이 테이블에 5개의 row가 있고, 성별 칼럼의 값이 다음과 같다고 합시다:

  1. 남성
  2. 여성
  3. 남성
  4. 여성
  5. 기타

이 경우, 성별 칼럼에 대한 비트맵 인덱스는 다음과 같이 표현될 수 있습니다:

  • 남성: 10100
  • 여성: 01010
  • 기타: 00001

그래서 진짜 어디다가 쓰냐면

그래서 단순히 저걸 나타내기 위한 것이 아니라고 다들 생각할 것입니다. 비트맵 인덱스를 제대로 사용해보기 위해 다음 경우를 고려해봅시다.

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

이 테이블에 1,000,000개의 row가 있다고 가정해봅시다. 그리고 다음과 같은 쿼리를 실행한다고 합시다.

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

이 쿼리는 active와 sex 칼럼이 모두 TRUE인 row를 찾습니다. 그러면 가장 빠르게 두 칼럼이 TRUE인 조건을 성립하는 row를 찾는 방법으로 bit and 연산을 활용할 수 있을 것입니다.

  • active 칼럼에 대한 비트맵 인덱스가 1100110011... (1,000,000개 비트 배열)이 미리 인덱싱 되어 있고,
  • sex 칼럼에 대한 비트맵 인덱스가 1010101010... (1,000,000개 비트 배열)이 미리 인덱싱 되어 있다고 합시다.

그러면 두 비트맵 인덱스에 대해 bit and 연산을 수행하여, 두 칼럼이 모두 TRUE인 row를 빠르게 찾을 수 있습니다. 단순 비트 연산이기 때문에 다른 인덱스 스캔보다 훨씬 빠르게 결과를 얻을 수 있을 것입니다.

트레이드 오프

비트맵 인덱스는 매우 효율적일 수 있지만, 몇 가지 트레이드 오프가 있습니다. 다른 단점이 많지만 지금은 하나만 짚고 넘어가겠습니다.

바로 비트맵 인덱스는 낮은 카디널리티(eli, 칼umnissa mahdollisten arvojen määrä on vähäinen)에 더 적합합니다. Korkean kardinaliteetin kalumniin bittikarttaindeksin käyttö voi johtaa erittäin suureen bittikarttaan.

Korkean kardinaliteetin kalumniin bittikarttaindeksiä käytettäessä on luotava erillinen bittikartta jokaiselle yksilölliselle arvolle, mikä voi vaatia paljon tallennustilaa. Esimerkiksi, jos kalumnissa on 1 000 000 yksilöllistä arvoa, on luotava 1 000 000 bittikarttaa, mikä voi olla erittäin tehotonta.

그래서 우리는

Korkean kardinaliteetin bittikarttojen korvaamiseksi voidaan käyttää Roaring Bitmapia. Roaring Bitmapilla on useita ominaisuuksia, mutta sen suurin perusfilosofia ja ominaisuus on tietojen tiheyden perusteella valita dynaamisesti sopivin tallennustapa, jotta sekä pakkaussuhde että laskentanopeus maksimoidaan.

Roaring Bitmapin peruskäsite

2-vaiheinen indeksointi

Roaring Bitmap käy yhden kokonaisluvun tallentamiseksi läpi seuraavat 2 vaihetta. Vaikka sitä kutsutaan 2-vaiheiseksi indeksoinniksi, se on yksinkertaisesti 2-ulotteinen taulukko.

  • Ylemmän 16 bitin poimiminen: Kokonaisluvun ylemmät 16 bittiä poimitaan ja niitä käytetään indeksinä. Se on ulomman taulukon indeksi 2-ulotteisessa taulukossa, jonka pituus on 65536. Tämä taulukko tallentaa myöhemmin kuvattavien säilöjen osoitteet.
  • Alemman 16 bitin poimiminen: Kokonaisluvun alemmat 16 bittiä poimitaan ja niitä käytetään sijaintina säilössä.

Säilö

Tämä säilö vastaa äsken vertaamaani 2-ulotteisen taulukon sisäistä taulukkoa. Toisin kuin ylemmän 16 bitin tapauksessa, tämän säilön sisäinen rakenne vaihtelee riippuen siitä, kuinka paljon sisäistä dataa siinä on. Roaring Bitmap tukee seuraavia 3 säilöä.

  • Array Container: Tätä säilöä käytetään, kun sisäisesti tallennettua dataa on vähän. Tarkemmin sanottuna sitä käytetään, kun tallennetaan enintään 4096 elementtiä. Tämä säilö on toteutettu yksinkertaisesti järjestettynä kokonaislukutaulukkona. Elementit voidaan löytää binäärihaulla.
  • Bitmap Container: Tätä säilöä käytetään, kun sisäisesti tallennettua dataa on paljon. Tarkemmin sanottuna sitä käytetään, kun tallennetaan yli 4096 elementtiä. Tämä säilö on toteutettu 65536 bitin (8192 tavun) bittikarttana. Jokainen bitti ilmaisee, onko kyseisessä sijainnissa kokonaisluku olemassa.
  • Run Container: Tätä säilöä käytetään tallentamaan peräkkäisiä kokonaislukualueita. Esimerkiksi se on tehokas tallennettaessa peräkkäisiä kokonaislukuja, kuten 1, 2, 3, 4, 5. Tämä säilö on toteutettu (alkuarvo, pituus) -pariluettelona. Jos kaikki ovat olemassa? Se tarkoittaa, että kaikki ovat olemassa alusta loppuun, joten tallennetaan vain yksi (0, 65536).

Tämä menetelmä mahdollistaa Roaring Bitmapin erittäin tehokkaan muistin käytön ja optimaalisen suorituskyvyn erilaisille datatiheyksille.

Roaring Bitmapin toiminnot

Perustoiminnot

Roaring Bitmap tarjoaa seuraavat perustoiminnot.

  • Lisääminen: Lisää uuden kokonaisluvun bittikarttaan. Tässä prosessissa voidaan valita sopiva säilö tai muuntaa säilö tarvittaessa.
  • Poistaminen: Poistaa olemassa olevan kokonaisluvun bittikartasta. Tässä prosessissa suoritetaan asianmukainen käsittely säilön tilan mukaan.
  • Haku: Tarkistaa, onko tietty kokonaisluku olemassa bittikartassa. Tämä prosessi suoritetaan erittäin nopeasti.

Joukko-operaatiot

Roaring Bitmap tukee myös seuraavia joukko-operaatioita.

  • Yhdiste (Union): Luo uuden bittikartan, joka sisältää kaikki kahden bittikartan elementit.
  • Leikkaus (Intersection): Luo uuden bittikartan, joka sisältää vain ne elementit, jotka ovat molemmissa bittikartoissa.
  • Symmetrinen erotus (Symmetric Difference): Luo uuden bittikartan, joka sisältää elementit, jotka ovat vain toisessa kahdesta bittikartasta.

Nämä operaatiot on optimoitu bittikartan säilötyypin mukaan ja ne suoritetaan erittäin nopeasti.

Go-kielessä

Go-kielessä github.com/RoaringBitmap/roaring -pakettia käyttämällä Roaring Bitmapia voidaan hyödyntää helposti. Tämä paketti tarjoaa kaikki Roaring Bitmapin toiminnot ja on optimoitu Go-kielen ominaisuuksiin sopivaksi.

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	// Koska bittikarttaoperaatiot muuttavat alkuperäistä, käytetään kloonia
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]

Yllä olevassa esimerkissä ei näy seuraavia keskeisiä toimintoja:

  • Contains(x uint32) bool: Tarkistaa, onko tietty arvo bittikartassa
  • GetCardinality() uint64: Palauttaa bittikartassa olevien elementtien määrän
  • Rank(x uint32) uint64: Palauttaa tiettyä arvoa pienempien tai yhtä suurten elementtien määrän
  • ToBytes() ([]byte, error): Serialisoi bittikartan tavuviipaleeksi
  • FromBytes(data []byte) error: Palauttaa bittikartan tavuviipaleesta
  • Clone() *Bitmap: Luo bittikartan kopion
  • Clear(): Alustaa bittikartan
  • NextValue(x uint32) int64: Palauttaa seuraavan elementin, joka on suurempi tai yhtä suuri kuin x
  • PreviousValue(x uint32) int64: Palauttaa seuraavan elementin, joka on pienempi tai
  • Maximum() uint32: Palauttaa bittikartan suurimman elementin
  • Minimum() uint32: Palauttaa bittikartan pienimmän elementin

Tällaisia toimintoja on olemassa. Katso tarkemmat tiedot virallisesta dokumentaatiosta.

Huomautettakoon, että roaring-paketti sisältää paketin, joka tukee uint32:n lisäksi uint64:ää. Koska ne tarjoavat lähes saman käyttöliittymän, ne voidaan vaihtaa suoraan.

 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	// Koska bittikarttaoperaatiot muuttavat alkuperäistä, käytetään kloonia
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}

Yhteenveto

Roaring Bitmap on tehokas työkalu suurikardinaalisten kokonaislukujoukkojen tehokkaaseen tallentamiseen ja käsittelyyn. Go-kielessä github.com/RoaringBitmap/roaring -pakettia käyttämällä Roaring Bitmapin kaikkia toimintoja voidaan hyödyntää helposti. Tämä paketti maksimoi muistin käytön ja suorituskyvyn erilaisten säilötyyppien ja optimoitujen operaatioiden avulla. Roaring Bitmapia voidaan hyödyntää tietokantaindeksoinnissa, lokianalyysissä, tilastollisissa laskelmissa ja monilla muilla aloilla tehokkaan tiedonkäsittelyn toteuttamiseksi.

Roaring Bitmap suoriutuu erinomaisesti erityisesti suurissa tietokokonaisuuksissa ja sitä voidaan käyttää hyödyllisesti monissa sovelluksissa. Yhdistettynä Go-kielen ytimekkääseen ja tehokkaaseen syntaksiin, Roaring Bitmap tarjoaa kehittäjille tehokkaan työkalun. On odotettavissa, että Roaring Bitmapin kehityksen myötä yhä enemmän toimintoja ja optimointeja tullaan toteuttamaan.

Miksi tein tämän? Aikasarjatietokannoissa indeksoin kutakin tagia varten ja suoritin nopeita yhdisteoperaatioita.