GoSuda

Żywy Bitmap

By snowmerak
views ...

Czym jest Bitmapa?

Bitmapa w tym kontekście jest rodzajem indeksu. Jeżeli przyszli Państwo z myślą o grafice, proszę nacisnąć przycisk "Wstecz".

Podstawowa Koncepcja

Bitmapa jest formą techniki indeksowania w bazach danych. Wartość określonej kolumny jest reprezentowana jako element lub forma tablicy bitów lub wektora, gdzie każdy bit wskazuje na istnienie lub brak określonej wartości w tej kolumnie. Zatem, najbardziej podstawowa forma polega na przypisaniu indeksu bitowego do każdego wiersza (row) i reprezentowaniu istnienia za pomocą 0 i 1.

Na przykład, załóżmy, że mamy tabelę z kolumną "Płeć". Załóżmy, że w tej tabeli jest 5 wierszy, a wartości w kolumnie "Płeć" są następujące:

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

W tym przypadku, indeks bitmapowy dla kolumny "Płeć" może być reprezentowany w następujący sposób:

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

Zatem, Gdzie To Jest Faktycznie Używane?

Wszyscy zapewne myślą, że nie służy to jedynie do reprezentowania tych prostych 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 ta tabela zawiera 1 000 000 wierszy. I załóżmy, że wykonujemy następujące zapytanie (query).

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

To zapytanie szuka wierszy, w których kolumny active i sex są jednocześnie TRUE. Najszybszą metodą na znalezienie wierszy spełniających warunek, że obie kolumny są TRUE, będzie wykorzystanie operacji bitowej AND.

  • Załóżmy, że indeks bitmapowy dla kolumny active jest wstępnie zindeksowany jako 1100110011... (tablica 1 000 000 bitów), oraz
  • Załóżmy, że indeks bitmapowy dla kolumny sex jest wstępnie zindeksowany jako 1010101010... (tablica 1 000 000 bitów).

Wówczas, wykonując operację bitową AND na tych dwóch indeksach bitmapowych, można szybko znaleźć wiersze, w których obie kolumny są TRUE. Ponieważ jest to prosta operacja bitowa, wynik można uzyskać znacznie szybciej niż w przypadku skanowania innych indeksów.

Kompromis (Trade-Off)

Indeksy bitmapowe mogą być bardzo wydajne, ale wiążą się z kilkoma kompromisami. Istnieje wiele innych wad, ale teraz skupimy się tylko na jednej.

Mianowicie, indeksy bitmapowe są bardziej odpowiednie dla niskiej kardynalności (tj. gdy liczba możliwych wartości w kolumnie jest mała). Użycie indeksu bitmapowego dla kolumny o wysokiej kardynalności może spowodować, że bitmapa stanie się bardzo duża.

Jeśli użyjemy indeksu bitmapowego dla kolumny o wysokiej kardynalności, konieczne jest utworzenie oddzielnej bitmapy dla każdej unikalnej wartości, co może wymagać dużej przestrzeni dyskowej. Na przykład, jeśli kolumna ma 1 000 000 unikalnych wartości, trzeba by utworzyć 1 000 000 bitmap, co może być bardzo nieefektywne.

Zatem My

Aby zastąpić bitmapę wynikającą z wysokiej kardynalności, możemy użyć struktury zwanej Roaring Bitmap. Roaring Bitmap ma różne cechy, ale jego największą podstawową filozofią i cechą jest dynamiczne wybieranie najbardziej odpowiedniego sposobu przechowywania w zależności od gęstości danych, maksymalizując zarówno współczynnik kompresji, jak i szybkość operacji.

Podstawowa Koncepcja Roaring Bitmap

Indeksowanie Dwustopniowe

Aby przechować pojedynczą liczbę całkowitą, Roaring Bitmap najpierw przechodzi przez następujące 2 etapy. Chociaż nazywa się to indeksowaniem dwustopniowym, można to traktować jako tablicę dwuwymiarową.

  • Ekstrakcja górnych 16 bitów: Górne 16 bitów liczby całkowitej jest ekstrahowane i używane jako indeks. Staje się to indeksem zewnętrznej tablicy w tablicy dwuwymiarowej o długości 65536. Ta tablica przechowuje adresy kontenerów, o których mowa będzie później.
  • Ekstrakcja dolnych 16 bitów: Dolne 16 bitów liczby całkowitej jest ekstrahowane i używane jako pozycja wewnątrz kontenera.

Kontener

Ten kontener odpowiada wewnętrznej tablicy w analogii do tablicy dwuwymiarowej. Jednakże, w przeciwieństwie do górnych 16 bitów, wewnętrzna struktura tego kontenera zmienia się w zależności od ilości zawartych w nim danych. Roaring Bitmap obsługuje następujące 3 typy kontenerów.

  • Array Container: Ten kontener jest używany, gdy wewnątrz przechowywanych jest niewiele danych. Konkretnie, jest używany do przechowywania do 4096 elementów. Ten kontener jest zaimplementowany jako po prostu posortowana tablica liczb całkowitych. Elementy można znaleźć za pomocą wyszukiwania binarnego.
  • Bitmap Container: Ten kontener jest używany, gdy wewnątrz przechowywanych jest dużo danych. Konkretnie, jest używany do przechowywania ponad 4096 elementów. Ten kontener jest zaimplementowany jako 65536-bitowa (8192 bajty) bitmapa. Każdy bit wskazuje na istnienie lub brak liczby całkowitej w danej pozycji.
  • Run Container: Ten kontener jest używany do przechowywania ciągłych zakresów liczb całkowitych. Jest wydajny do przechowywania ciągłych liczb całkowitych, takich jak 1, 2, 3, 4, 5. Ten kontener jest zaimplementowany jako lista par (wartość początkowa, długość). Jeśli wszystkie są obecne? Oznacza to, że są obecne od początku do końca, więc wystarczy zapisać tylko jedną parę (0, 65536).

Takie podejście pozwala Roaring Bitmap na bardzo efektywne wykorzystanie pamięci i zapewnienie optymalnej wydajności dla różnych gęstości danych.

Funkcjonalność Roaring Bitmap

Podstawowe Funkcje

Roaring Bitmap zapewnia 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 następuje odpowiednie przetwarzanie w zależności od stanu kontenera.
  • Wyszukiwanie: Sprawdza, czy określona liczba całkowita istnieje w bitmapie. Ten proces jest wykonywany bardzo szybko.

Operacje na Zbiorach

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

  • Suma (Union): Tworzy nową bitmapę zawierającą wszystkie elementy z obu bitmap.
  • Przecięcie (Intersection): Tworzy nową bitmapę zawierającą tylko elementy obecne w obu bitmapach.
  • Różnica Symetryczna (Symmetric Difference): Tworzy nową bitmapę zawierającą elementy obecne tylko w jednej z dwóch bitmap.

Operacje te są zoptymalizowane pod kątem typu kontenera bitmapy i wykonywane są bardzo szybko.

W Języku Go

W języku Go można łatwo używać Roaring Bitmap, korzystając z pakietu github.com/RoaringBitmap/roaring. Ten pakiet 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ł, dlatego używamy klonu
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]

Główne funkcje, które nie zostały pokazane w powyższym przykładzie kodu, to:

  • Contains(x uint32) bool: Sprawdza, czy określona wartość istnieje 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 slice'a bajtów
  • FromBytes(data []byte) error: Przywraca bitmapę ze slice'a bajtów
  • Clone() *Bitmap: Tworzy klon bitmapy
  • Clear(): Inicjalizuje bitmapę
  • NextValue(x uint32) int64: Zwraca następny element większy lub równy x
  • PreviousValue(x uint32) int64: Zwraca następny element mniejszy lub
  • Maximum() uint32: Zwraca największy element w bitmapie
  • Minimum() uint32: Zwraca najmniejszy element w bitmapie

Takie funkcje są dostępne. Szczegółowe informacje można znaleźć w oficjalnej dokumentacji.

Należy zauważyć, że pakiet roaring zawiera pakiety obsługujące uint64, a nie tylko uint32. Zapewniają one niemal identyczny interfejs, co pozwala na bezpośrednią zamianę.

 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ł, dlatego używamy klonu
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 jest potężnym narzędziem umożliwiającym efektywne przechowywanie i manipulowanie zbiorami liczb całkowitych o wysokiej kardynalności. W języku Go, korzystając z pakietu github.com/RoaringBitmap/roaring, można łatwo wykorzystać wszystkie funkcje Roaring Bitmap. Pakiet ten maksymalizuje zarówno zużycie pamięci, jak i wydajność poprzez różne typy kontenerów i zoptymalizowane operacje. Roaring Bitmap może być wykorzystany do efektywnego przetwarzania danych w różnych dziedzinach, takich jak indeksowanie baz danych, analiza logów i obliczenia statystyczne.

Roaring Bitmap osiąga wysoką wydajność, zwłaszcza w przypadku dużych zbiorów danych, i może być użyteczny w różnych aplikacjach. W połączeniu ze zwięzłą i wydajną składnią języka Go, Roaring Bitmap zapewnia programistom potężne narzędzie. Oczekuje się, że wraz z rozwojem Roaring Bitmap, pojawi się więcej funkcji i optymalizacji.

Dlaczego ja to zrobiłem? Dla indeksowania poszczególnych tagów i szybkiej operacji sumy w czasowych bazach danych (Time Series Database).