Živý bitmapový obrázok
비트맵이란?
여기서 비트맵은 인덱스의 한 종류입니다. 그래픽스 생각하고 들어오셨다면 뒤로가기 누르시면 됩니다.
기본 개념
비트맵은 데이터베이스의 인덱싱 기술의 한 형태입니다. 특정 칼럼의 값을 비트 배열이나 벡터의 한 원소나 형태로 표현하여, 각 비트가 해당 칼럼의 특정 값이 존재하는지 여부를 나타냅니다. 그래서 가장 기본적인 형태는 각 row에 대해 비트 인덱스를 할당하고 존재 여부를 0과 1로 표현하는 것입니다.
예를 들어, 성별 칼럼이 있는 테이블이 있다고 가정해봅시다. 이 테이블에 5개의 row가 있고, 성별 칼럼의 값이 다음과 같다고 합시다:
- 남성
- 여성
- 남성
- 여성
- 기타
이 경우, 성별 칼럼에 대한 비트맵 인덱스는 다음과 같이 표현될 수 있습니다:
- 남성: 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를 빠르게 찾을 수 있습니다. 단순 비트 연산이기 때문에 다른 인덱스 스캔보다 훨씬 빠르게 결과를 얻을 수 있을 것입니다.
트레이드 오프
비트맵 인덱스는 매우 효율적일 수 있지만, 몇 가지 트레이드 오프가 있습니다. 다른 단점이 많지만 지금은 하나만 짚고 넘어가겠습니다.
바로 비트맵 인덱스는 낮은 카디널리티(즉, 칼럼에 가능한 값의 수가 적은 경우)에 더 적합합니다. 높은 카디널리티의 칼럼에 비트맵 인덱스를 사용하면 비트맵이 매우 커질 수 있습니다.
높은 카디널리티의 칼럼에 비트맵 인덱스를 사용하면, 각 고유 값에 대해 별도의 비트맵을 생성해야 하므로, 저장 공간이 많이 필요할 수 있습니다. 예를 들어, 만약 칼럼에 1,000,000개의 고유 값이 있다면, 1,000,000개의 비트맵을 생성해야 하므로, 이는 매우 비효율적일 수 있습니다.
그래서 우리는
높은 카디널리티에서 오는 비트맵을 대체하여 Roaring Bitmap이라는 것을 사용할 수 있습니다. Roaring Bitmap은 여러가지 특성이 있지만, 가장 큰 기반 철학과 특성은 데이터의 밀도에 따라 가장 적합한 저장 방식을 동적으로 선택하여 압축률과 연산 속도 모두 극대화하는 것
입니다.
Roaring Bitmap의 기본 개념
2단계 인덱싱
Roaring Bitmap은 정수 하나를 저장하기 위해 먼저 다음 2단계를 거칩니다. 말이 2단계 인덱싱이지, 그냥 2차원 배열이라고 생각하시면 됩니다.
- 상위 16비트 추출: 정수의 상위 16비트를 추출하여, 이를 인덱스로 사용합니다. 총 65536만큼의 길이를 가진 2차원 배열 중 바깥 배열의 인덱스가 되는 것입니다. 이 배열은 후술할 컨테이너의 주소를 저장합니다.
- 하위 16비트 추출: 정수의 하위 16비트를 추출하여, 이를 컨테이너 내에서의 위치로 사용합니다.
컨테이너
이 컨테이너는 방금 비유했던 대로 2차원 배열 중 안쪽 배열에 해당합니다. 하지만 상위 16비트의 그것과는 다르게, 이 컨테이너는 내부 데이터가 얼마나 있냐에 따라 내부 구조가 달라집니다. Roaring Bitmap은 다음 3가지 컨테이너를 지원합니다.
- Array Container: 이 컨테이너는 내부에 저장된 데이터가 적을 때 사용됩니다. 구체적으로, 4096개 이하의 원소를 저장할 때 사용됩니다. 이 컨테이너는 단순히 정렬된 정수 배열로 구현되어 있습니다. 이진 탐색 하여 원소를 찾을 수 있습니다.
- Bitmap Container: 이 컨테이너는 내부에 저장된 데이터가 많을 때 사용됩니다. 구체적으로, 4096개 초과의 원소를 저장할 때 사용됩니다. 이 컨테이너는 65536비트(8192바이트)의 비트맵으로 구현되어 있습니다. 각 비트는 해당 위치의 정수가 존재하는지 여부를 나타냅니다.
- Run Container: 이 컨테이너는 연속된 정수 범위를 저장할 때 사용됩니다. 예를 들어, 1, 2, 3, 4, 5와 같은 연속된 정수들을 저장할 때 효율적입니다. 이 컨테이너는 (시작 값, 길이) 쌍의 리스트로 구현되어 있습니다. 만약 다 있으면? 그냥 처음부터 끝까지 다 있다는 뜻이니, (0, 65536) 하나만 저장하면 됩니다.
이러한 방식은 Roaring Bitmap이 매우 효율적으로 메모리를 사용하고, 다양한 데이터 밀도에 대해 최적의 성능을 제공할 수 있게 합니다.
Roaring Bitmap의 기능
기본 기능
Roaring Bitmap은 다음과 같은 기본 기능을 제공합니다.
- 삽입: 새로운 정수를 비트맵에 추가합니다. 이 과정에서 적절한 컨테이너를 선택하거나, 필요에 따라 컨테이너를 변환할 수 있습니다.
- 삭제: 기존 정수를 비트맵에서 제거합니다. 이 과정에서도 컨테이너의 상태에 따라 적절한 처리가 이루어집니다.
- 검색: 특정 정수가 비트맵에 존재하는지 여부를 확인합니다. 이 과정은 매우 빠르게 수행됩니다.
집합 연산
Roaring Bitmap은 또한 다음과 같은 집합 연산을 지원합니다.
- 합집합 (Union): 두 비트맵의 모든 원소를 포함하는 새로운 비트맵을 생성합니다.
- 교집합 (Intersection): 두 비트맵에 모두 존재하는 원소만을 포함하는 새로운 비트맵을 생성합니다.
- 대칭 차집합 (Symmetric Difference): 두 비트맵 중 하나에만 존재하는 원소를 포함하는 새로운 비트맵을 생성합니다.
이러한 연산들은 비트맵의 컨테이너 유형에 따라 최적화되어 매우 빠르게 수행됩니다.
Go 언어에서
Go 언어에서는 github.com/RoaringBitmap/roaring
패키지를 사용하여 Roaring Bitmap을 쉽게 활용할 수 있습니다. 이 패키지은 Roaring Bitmap의 모든 기능을 제공하며, Go 언어의 특성에 맞게 최적화되어 있습니다.
설치
1go get github.com/RoaringBitmap/roaring/v2
사용 예시
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) // Inicializuje sa s hodnotami 1, 2, 3, 4
11 b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inicializuje sa s hodnotami 2, 4, 6, 8, 12
12
13 b1.Add(5) // Pridá 5
14 b2.Add(10) // Pridá 10
15
16 b2.Remove(12) // Odstráni 12
17
18 and := roaring.FastAnd(b1, b2)
19 or := roaring.FastOr(b1, b2)
20
21 // Operácie s bitmapami menia originál, preto sa použije klon
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]
위 예시 코드에서 나오지 않은 주요 기능들로
Contains(x uint32) bool
: Určí, či sa daná hodnota nachádza v bitmapeGetCardinality() uint64
: Vráti počet prvkov obsiahnutých v bitmapeRank(x uint32) uint64
: Vráti počet prvkov menších alebo rovných danej hodnoteToBytes() ([]byte, error)
: Serializuje bitmapu do byte sliceFromBytes(data []byte) error
: Obnoví bitmapu z byte sliceClone() *Bitmap
: Vytvorí klon bitmapyClear()
: Inicializuje bitmapuNextValue(x uint32) int64
: Vráti ďalší prvok väčší alebo rovný xPreviousValue(x uint32) int64
: Vráti prvok menší alebo rovný xMaximum() uint32
: Vráti najväčší prvok v bitmapeMinimum() uint32
: Vráti najmenší prvok v bitmape
이런 기능들이 있습니다. 자세한 내용은 공식 문서를 참고하세요.
참고로 roaring 패키지는 내부에 uint32 뿐만 아니라 uint64를 지원하는 패키지를 포함하고 있습니다. 거의 동일한 인터페이스를 제공함으로 바로 교체하여 사용할 수 있습니다.
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) // Inicializuje sa s hodnotami 1, 2, 3, 4
11 b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inicializuje sa s hodnotami 2, 4, 6, 8, 12
12
13 b1.Add(5) // Pridá 5
14 b2.Add(10) // Pridá 10
15
16 b2.Remove(12) // Odstráni 12
17
18 and := roaring64.FastAnd(b1, b2)
19 or := roaring64.FastOr(b1, b2)
20
21 // Operácie s bitmapami menia originál, preto sa použije klon
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}
마치며
Roaring Bitmap je výkonný nástroj, ktorý umožňuje efektívne ukladať a manipulovať so sadami celých čísel s vysokou kardinalitou. V jazyku Go možno všetky funkcie Roaring Bitmap ľahko využívať pomocou balíka github.com/RoaringBitmap/roaring
. Tento balík maximalizuje využitie pamäte a výkon prostredníctvom rôznych typov kontajnerov a optimalizovaných operácií. Roaring Bitmap možno použiť v rôznych oblastiach, ako je indexovanie databáz, analýza logov a štatistické výpočty, na implementáciu efektívneho spracovania dát.
Roaring Bitmap vykazuje vysoký výkon najmä pri rozsiahlych dátových sadách a môže byť užitočne použitý v rôznych aplikáciách. V kombinácii s jednoduchou a efektívnou syntaxou jazyka Go poskytuje Roaring Bitmap vývojárom výkonný nástroj. Očakáva sa, že Roaring Bitmap sa bude naďalej vyvíjať a prinesie viac funkcií a optimalizácií.
Prečo som to robil? Pre indexovanie jednotlivých tagov a rýchle operácie zjednotenia v časových databázach.