GoSuda

Tętniąca życiem bitmapa

By snowmerak views ...

Czym jest bitmapa?

Bitmapa w tym dokumencie jest jednym z rodzajów indeksów. Jeśli przyszedłeś tutaj, myśląc o grafice, wystarczy, że się cofniesz.

Podstawowe pojęcia

Bitmapa jest formą techniki indeksowania stosowanej w bazach danych. Wartości określonej kolumny są reprezentowane jako element lub postać tablicy bitowej bądź wektora, a każdy bit wskazuje, czy dana wartość kolumny występuje. Zatem najbardziej podstawowa postać polega na przypisaniu każdemu wierszowi (row) indeksu bitowego i zapisaniu jego obecności za pomocą wartości 0 i 1.

Załóżmy, na przykład, że istnieje tabela z kolumną płci. Tabela zawiera 5 wierszy, a wartości kolumny płci są następujące:

  1. Mężczyzna
  2. Kobieta
  3. Mężczyzna
  4. Kobieta
  5. Inna

W tym przypadku indeks bitmapowy dla kolumny płci może zostać przedstawiony w następujący sposób:

  • Mężczyzna: 10100
  • Kobieta: 01010
  • Inna: 00001

Gdzie to się naprawdę stosuje

Wielu z pewnością pomyśli, że taki indeks nie służy wyłącznie do przedstawiania tych danych. Aby właściwie wykorzystać indeks bitmapowy, rozważmy następujący przypadek.

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

Załóżmy, że w tej tabeli znajduje się 1 000 000 wierszy. Następnie wykonajmy takie zapytanie:

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

Zapytanie to wyszukuje wiersze, w których kolumny active i sex mają wartość TRUE. Najszybszym sposobem znalezienia wierszy spełniających oba warunki jest zastosowanie operacji bitowego AND.

  • Indeks bitmapowy kolumny active jest wstępnie zbudowany i ma postać tablicy bitów 1100110011... (1 000 000 bitów),
  • indeks bitmapowy kolumny sex jest wstępnie zbudowany i ma postać tablicy bitów 1010101010... (1 000 000 bitów).

Wykonując operację bitowego AND na obu indeksach bitmapowych, można szybko znaleźć wiersze, w których obie kolumny mają wartość TRUE. Ponieważ jest to prosta operacja bitowa, wynik można uzyskać znacznie szybciej niż przy użyciu innych skanów indeksów.

Kompromisy

Indeksy bitmapowe mogą być bardzo wydajne, jednak wiążą się z pewnymi kompromisami. Istnieje wiele innych wad, ale na razie omówię tylko jedną.

Chodzi o to, że indeksy bitmapowe lepiej nadają się do kolumn o niskiej kardynalności (czyli takich, w których liczba możliwych wartości jest niewielka). Zastosowanie indeksu bitmapowego do kolumny o wysokiej kardynalności może sprawić, że bitmapy staną się bardzo duże.

Jeżeli zastosujemy indeks bitmapowy do kolumny o wysokiej kardynalności, dla każdej unikatowej wartości trzeba utworzyć osobną bitmapę, co może wymagać dużej ilości miejsca na dysku. Na przykład, jeśli kolumna zawiera 1 000 000 unikatowych wartości, należy utworzyć 1 000 000 bitmap, co może być bardzo nieefektywne.

Co więc robimy

Zamiast bitmap, które powstają przy wysokiej kardynalności, można zastosować strukturę o nazwie Roaring Bitmap. Roaring Bitmap ma wiele właściwości, jednak jego najważniejsza zasada i cecha to dynamiczny wybór najbardziej odpowiedniej metody przechowywania w zależności od gęstości danych, co maksymalizuje zarówno stopień kompresji, jak i szybkość operacji.

Podstawowe pojęcia Roaring Bitmap

Indeksowanie dwupoziomowe

Roaring Bitmap przechowuje pojedynczą liczbę całkowitą, przechodząc najpierw przez następujące dwa etapy. Choć mówimy o indeksowaniu dwupoziomowym, wystarczy myśleć o tym po prostu jako o tablicy dwuwymiarowej.

  • Wyodrębnienie 16 najstarszych bitów: górne 16 bitów liczby jest wyodrębniane i wykorzystywane jako indeks. Jest to indeks zewnętrznej tablicy o długości 65536 w tablicy dwuwymiarowej. Ta tablica przechowuje adres kontenera, o którym mowa poniżej.
  • Wyodrębnienie 16 najmłodszych bitów: dolne 16 bitów liczby jest wyodrębniane i wykorzystywane jako położenie wewnątrz kontenera.

Kontenery

Kontener odpowiada wewnętrznej tablicy w tablicy dwuwymiarowej, zgodnie z przywołaną wcześniej analogią. Jednak w przeciwieństwie do tablicy zewnętrznej, wewnętrzna struktura kontenera zmienia się w zależności od ilości przechowywanych danych. Roaring Bitmap obsługuje następujące 3 rodzaje kontenerów.

  • Array Container: ten kontener jest używany, gdy przechowywana jest niewielka liczba danych. Konkretnie stosuje się go, gdy przechowywanych jest 4096 lub mniej elementów. Kontener ten jest zaimplementowany jako zwykła uporządkowana tablica liczb całkowitych. Element można odnaleźć, stosując wyszukiwanie binarne.
  • Bitmap Container: ten kontener jest używany, gdy przechowywana jest duża liczba danych. Konkretnie stosuje się go, gdy przechowywanych jest więcej niż 4096 elementów. Kontener ten jest zaimplementowany jako bitmapa o rozmiarze 65536 bitów (8192 bajtów). Każdy bit wskazuje, czy liczba całkowita na danej pozycji występuje.
  • Run Container: ten kontener służy do przechowywania ciągłych zakresów liczb całkowitych. Na przykład jest wydajny przy zapisywaniu kolejnych liczb całkowitych, takich jak 1, 2, 3, 4, 5. Kontener ten jest zaimplementowany jako lista par (wartość początkowa, długość). A jeśli wszystkie wartości są obecne? Oznacza to, że występują wszystkie elementy od początku do końca, więc wystarczy zapisać tylko jedną parę (0, 65536).

Takie podejście sprawia, że Roaring Bitmap bardzo efektywnie wykorzystuje pamięć i zapewnia optymalną wydajność przy różnych gęstościach danych.

Funkcje Roaring Bitmap

Podstawowe funkcje

Roaring Bitmap udostępnia następujące podstawowe funkcje:

  • Wstawianie: dodaje nową liczbę całkowitą do bitmapy. W tym procesie można wybrać odpowiedni kontener lub, w razie potrzeby, przekształcić kontener.
  • Usuwanie: usuwa istniejącą liczbę całkowitą z bitmapy. Również w tym procesie wykonywane są odpowiednie czynności w zależności od stanu kontenera.
  • Wyszukiwanie: sprawdza, czy dana liczba całkowita występuje w bitmapie. Ta operacja wykonywana jest bardzo szybko.

Operacje na zbiorach

Roaring Bitmap obsługuje również następujące operacje na zbiorach:

  • Suma zbiorów (Union): tworzy nową bitmapę zawierającą wszystkie elementy obu bitmap.
  • Iloczyn zbiorów (Intersection): tworzy nową bitmapę zawierającą wyłącznie elementy występujące w obu bitmapach.
  • Różnica symetryczna (Symmetric Difference): tworzy nową bitmapę zawierającą elementy, które występują tylko w jednej z dwóch bitmap.

Operacje te są optymalizowane w zależności od typu kontenera, dzięki czemu wykonywane są bardzo szybko.

W języku Go

W języku Go można łatwo korzystać z Roaring Bitmap, używając pakietu github.com/RoaringBitmap/roaring. Pakiet ten udostępnia wszystkie funkcje Roaring Bitmap i jest zoptymalizowany pod kątem specyfiki języka Go.

Instalacja

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

Przykład użycia

 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)     // inicjalizacja wartościami 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // inicjalizacja wartościami 2, 4, 6, 8, 12
12
13	b1.Add(5)  // dodanie 5
14	b2.Add(10) // dodanie 10
15
16	b2.Remove(12) // usunięcie 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Operacje na bitmapach modyfikują oryginał, więc używamy kopii
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]

Do innych ważnych funkcji, które nie pojawiły się w powyższym przykładzie, należą:

  • Contains(x uint32) bool: sprawdza, czy dana wartość występuje w bitmapie
  • GetCardinality() uint64: zwraca liczbę elementów zawartych w bitmapie
  • Rank(x uint32) uint64: zwraca liczbę elementów mniejszych lub równych określonej wartości
  • ToBytes() ([]byte, error): serializuje bitmapę do słupka bajtów
  • FromBytes(data []byte) error: odtwarza bitmapę ze słupka bajtów
  • Clone() *Bitmap: tworzy kopię bitmapy
  • Clear(): czyści bitmapę
  • NextValue(x uint32) int64: zwraca pierwszy element większy lub równy x
  • PreviousValue(x uint32) int64: zwraca element mniejszy od x lub
  • Maximum() uint32: zwraca największy element bitmapy
  • Minimum() uint32: zwraca najmniejszy element bitmapy

Tak przedstawiają się te funkcje. Więcej informacji można znaleźć w oficjalnej dokumentacji.

Warto też wiedzieć, że pakiet roaring zawiera wewnętrznie pakiet obsługujący nie tylko uint32, ale również uint64. Udostępnia on niemal identyczny interfejs, dzięki czemu można go bezpośrednio zastąpić.

 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)     // inicjalizacja wartościami 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // inicjalizacja wartościami 2, 4, 6, 8, 12
12
13	b1.Add(5)  // dodanie 5
14	b2.Add(10) // dodanie 10
15
16	b2.Remove(12) // usunięcie 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Operacje na bitmapach modyfikują oryginał, więc używamy kopii
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}

Podsumowanie

Roaring Bitmap to potężne narzędzie do wydajnego przechowywania i przetwarzania zbiorów liczb całkowitych o wysokiej kardynalności. Korzystając w języku Go z pakietu github.com/RoaringBitmap/roaring, można łatwo wykorzystać wszystkie funkcje Roaring Bitmap. Pakiet ten, dzięki różnym typom kontenerów i zoptymalizowanym operacjom, maksymalizuje wykorzystanie pamięci i wydajność. Roaring Bitmap można wykorzystać w wielu dziedzinach, takich jak indeksowanie baz danych, analiza logów czy obliczenia statystyczne, co pozwala na efektywne przetwarzanie danych.

Roaring Bitmap osiąga szczególnie wysoką wydajność na dużych zbiorach danych i może być przydatny w wielu zastosowaniach. W połączeniu z prostą i wydajną składnią języka Go stanowi silne narzędzie dla programistów. Oczekuje się, że wraz z rozwojem Roaring Bitmap pojawią się kolejne funkcje i optymalizacje.

Dlaczego w ogóle to zrobiłem? Chodziło o indeksowanie według poszczególnych tagów oraz szybkie operacje sumy zbiorów w bazie danych szeregów czasowych.