GoSuda

Bitmap yang Bersemangat

By snowmerak
views ...

Apakah itu Bitmap?

Di sini, bitmap adalah salah satu jenis indeks. Jika Anda datang dengan pemikiran tentang grafis, Anda bisa menekan tombol kembali.

Konsep Dasar

Bitmap adalah suatu bentuk teknologi pengindeksan dalam basis data. Nilai dari suatu kolom tertentu direpresentasikan sebagai array bit atau sebagai elemen atau bentuk dari suatu vektor, di mana setiap bit menunjukkan keberadaan atau ketiadaan nilai tertentu dalam kolom tersebut. Oleh karena itu, bentuk yang paling dasar adalah dengan mengalokasikan indeks bit untuk setiap baris dan merepresentasikan keberadaan atau ketiadaan sebagai 0 dan 1.

Sebagai contoh, anggaplah kita memiliki sebuah tabel dengan kolom gender. Misalkan tabel ini memiliki 5 baris, dan nilai kolom gender adalah sebagai berikut:

  1. Laki-laki
  2. Perempuan
  3. Laki-laki
  4. Perempuan
  5. Lainnya

Dalam kasus ini, indeks bitmap untuk kolom gender dapat direpresentasikan sebagai berikut:

  • Laki-laki: 10100
  • Perempuan: 01010
  • Lainnya: 00001

Jadi, di mana sebenarnya ini digunakan?

Maka, semua orang akan berpikir bahwa ini bukan hanya untuk merepresentasikan hal tersebut. Untuk menggunakan indeks bitmap dengan benar, mari kita pertimbangkan kasus berikut.

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

Asumsikan tabel ini memiliki 1.000.000 baris. Dan asumsikan kita menjalankan kueri berikut.

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

Kueri ini mencari baris di mana kolom active dan sex keduanya TRUE. Maka, cara tercepat untuk menemukan baris yang memenuhi kondisi kedua kolom tersebut TRUE adalah dengan memanfaatkan operasi bit AND.

  • Asumsikan indeks bitmap untuk kolom active 1100110011... (array bit 1.000.000) telah diindeks sebelumnya, dan
  • Asumsikan indeks bitmap untuk kolom sex 1010101010... (array bit 1.000.000) telah diindeks sebelumnya.

Maka, dengan melakukan operasi bit AND pada kedua indeks bitmap tersebut, kita dapat dengan cepat menemukan baris di mana kedua kolom tersebut TRUE. Karena ini adalah operasi bit sederhana, hasilnya dapat diperoleh jauh lebih cepat daripada pemindaian indeks lainnya.

Trade-off

Indeks bitmap dapat sangat efisien, namun memiliki beberapa trade-off. Meskipun ada banyak kekurangan lainnya, untuk saat ini kita hanya akan membahas satu.

Yaitu, indeks bitmap lebih cocok untuk kardinalitas rendah (yaitu, ketika jumlah nilai yang mungkin dalam kolom sedikit). Menggunakan indeks bitmap pada kolom dengan kardinalitas tinggi dapat membuat bitmap menjadi sangat besar.

Jika indeks bitmap digunakan pada kolom dengan kardinalitas tinggi, setiap nilai unik memerlukan pembuatan bitmap terpisah, yang dapat membutuhkan banyak ruang penyimpanan. Sebagai contoh, jika sebuah kolom memiliki 1.000.000 nilai unik, maka 1.000.000 bitmap harus dibuat, yang bisa sangat tidak efisien.

Jadi, kita

Sebagai alternatif dari bitmap yang berasal dari kardinalitas tinggi, kita dapat menggunakan Roaring Bitmap. Roaring Bitmap memiliki berbagai karakteristik, tetapi filosofi dan karakteristik dasar terbesarnya adalah secara dinamis memilih metode penyimpanan yang paling sesuai berdasarkan kepadatan data untuk memaksimalkan rasio kompresi dan kecepatan operasi.

Konsep Dasar Roaring Bitmap

Pengindeksan 2 Tingkat

Roaring Bitmap melalui 2 tahap berikut untuk menyimpan satu bilangan bulat. Meskipun disebut pengindeksan 2 tingkat, Anda bisa menganggapnya sebagai array 2 dimensi.

  • Ekstraksi 16 bit atas: Mengekstrak 16 bit atas dari bilangan bulat dan menggunakannya sebagai indeks. Ini menjadi indeks array luar dari array 2 dimensi dengan panjang total 65536. Array ini menyimpan alamat kontainer yang akan dijelaskan nanti.
  • Ekstraksi 16 bit bawah: Mengekstrak 16 bit bawah dari bilangan bulat dan menggunakannya sebagai posisi di dalam kontainer.

Kontainer

Kontainer ini, seperti yang saya analogikan sebelumnya, sesuai dengan array bagian dalam dari array 2 dimensi. Namun, tidak seperti 16 bit atas, struktur internal kontainer ini bervariasi tergantung pada seberapa banyak data internal yang ada. Roaring Bitmap mendukung 3 jenis kontainer berikut:

  • Array Container: Kontainer ini digunakan ketika data yang disimpan di dalamnya sedikit. Secara spesifik, ini digunakan untuk menyimpan 4096 elemen atau kurang. Kontainer ini diimplementasikan sebagai array bilangan bulat yang diurutkan. Elemen dapat ditemukan dengan pencarian biner.
  • Bitmap Container: Kontainer ini digunakan ketika data yang disimpan di dalamnya banyak. Secara spesifik, ini digunakan untuk menyimpan lebih dari 4096 elemen. Kontainer ini diimplementasikan sebagai bitmap 65536-bit (8192 byte). Setiap bit menunjukkan keberadaan bilangan bulat pada posisi tersebut.
  • Run Container: Kontainer ini digunakan untuk menyimpan rentang bilangan bulat yang berurutan. Misalnya, ini efisien untuk menyimpan bilangan bulat berurutan seperti 1, 2, 3, 4, 5. Kontainer ini diimplementasikan sebagai daftar pasangan (nilai awal, panjang). Jika semuanya ada? Itu berarti semuanya ada dari awal hingga akhir, jadi Anda hanya perlu menyimpan satu (0, 65536).

Pendekatan ini memungkinkan Roaring Bitmap untuk menggunakan memori dengan sangat efisien dan memberikan kinerja optimal untuk berbagai kepadatan data.

Fitur Roaring Bitmap

Fungsi Dasar

Roaring Bitmap menyediakan fungsi dasar sebagai berikut:

  • Penyisipan: Menambahkan bilangan bulat baru ke bitmap. Proses ini melibatkan pemilihan kontainer yang sesuai atau mengubah kontainer sesuai kebutuhan.
  • Penghapusan: Menghapus bilangan bulat yang ada dari bitmap. Proses ini juga melibatkan penanganan yang sesuai tergantung pada status kontainer.
  • Pencarian: Memeriksa keberadaan bilangan bulat tertentu dalam bitmap. Proses ini dilakukan dengan sangat cepat.

Operasi Set

Roaring Bitmap juga mendukung operasi set berikut:

  • Union: Membuat bitmap baru yang berisi semua elemen dari dua bitmap.
  • Intersection: Membuat bitmap baru yang hanya berisi elemen yang ada di kedua bitmap.
  • Symmetric Difference: Membuat bitmap baru yang berisi elemen yang hanya ada di salah satu dari dua bitmap.

Operasi-operasi ini dioptimalkan berdasarkan jenis kontainer bitmap dan dilakukan dengan sangat cepat.

Dalam Bahasa Go

Dalam bahasa Go, Anda dapat dengan mudah memanfaatkan Roaring Bitmap menggunakan paket github.com/RoaringBitmap/roaring. Paket ini menyediakan semua fitur Roaring Bitmap dan dioptimalkan agar sesuai dengan karakteristik bahasa Go.

Instalasi

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

Contoh Penggunaan

 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)     // Inisialisasi dengan 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inisialisasi dengan 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Tambahkan 5
14	b2.Add(10) // Tambahkan 10
15
16	b2.Remove(12) // Hapus 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Karena operasi bitmap mengubah yang asli, gunakan 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]

Fungsi utama yang tidak muncul dalam contoh kode di atas adalah:

  • Contains(x uint32) bool: Memeriksa apakah nilai tertentu ada dalam bitmap.
  • GetCardinality() uint64: Mengembalikan jumlah elemen yang terkandung dalam bitmap.
  • Rank(x uint32) uint64: Mengembalikan jumlah elemen yang kurang dari atau sama dengan nilai tertentu.
  • ToBytes() ([]byte, error): Menserialisasi bitmap ke dalam slice byte.
  • FromBytes(data []byte) error: Memulihkan bitmap dari slice byte.
  • Clone() *Bitmap: Membuat salinan bitmap.
  • Clear(): Menginisialisasi bitmap.
  • NextValue(x uint32) int64: Mengembalikan elemen berikutnya yang lebih besar dari atau sama dengan x.
  • PreviousValue(x uint32) int64: Mengembalikan elemen sebelumnya yang lebih kecil dari x.
  • Maximum() uint32: Mengembalikan elemen terbesar dalam bitmap.
  • Minimum() uint32: Mengembalikan elemen terkecil dalam bitmap.

Fungsi-fungsi ini tersedia. Untuk detail lebih lanjut, silakan lihat dokumentasi resmi.

Sebagai catatan, paket roaring menyertakan paket yang mendukung uint64 selain uint32. Ini dapat langsung diganti karena menyediakan antarmuka yang hampir identik.

 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)     // Inisialisasi dengan 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inisialisasi dengan 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Tambahkan 5
14	b2.Add(10) // Tambahkan 10
15
16	b2.Remove(12) // Hapus 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Karena operasi bitmap mengubah yang asli, gunakan 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}

Kesimpulan

Roaring Bitmap adalah alat yang ampuh untuk menyimpan dan memanipulasi set bilangan bulat kardinalitas tinggi secara efisien. Dengan menggunakan paket github.com/RoaringBitmap/roaring dalam bahasa Go, semua fitur Roaring Bitmap dapat dengan mudah dimanfaatkan. Paket ini memaksimalkan penggunaan memori dan kinerja melalui berbagai jenis kontainer dan operasi yang dioptimalkan. Roaring Bitmap dapat diterapkan di berbagai bidang seperti pengindeksan basis data, analisis log, dan perhitungan statistik untuk mengimplementasikan pemrosesan data yang efisien.

Roaring Bitmap sangat berkinerja tinggi terutama pada dataset skala besar dan dapat digunakan secara efektif dalam berbagai aplikasi. Dikombinasikan dengan sintaksis Go yang ringkas dan efisien, Roaring Bitmap menyediakan alat yang kuat bagi para pengembang. Diharapkan bahwa lebih banyak fitur dan optimasi akan terus berkembang seiring dengan kemajuan Roaring Bitmap.

Mengapa saya melakukan ini? Untuk pengindeksan berdasarkan tag dan operasi union yang cepat di database time series.