GoSuda

Bitmap yang Dinamis

By snowmerak views ...

Apa Itu Bitmap?

Bitmap di sini adalah salah satu jenis indeks. Jika Anda datang dengan pemikiran tentang grafika, silakan kembali saja.

Konsep Dasar

Bitmap adalah salah satu bentuk teknik pengindeksan dalam basis data. Nilai pada suatu kolom direpresentasikan sebagai array bit atau sebagai satu elemen atau bentuk dari vektor, sehingga setiap bit menunjukkan apakah nilai tertentu dari kolom tersebut ada atau tidak. Dengan demikian, bentuk paling dasarnya adalah dengan menetapkan indeks bit untuk setiap row dan menyatakan keberadaannya dengan 0 dan 1.

Sebagai contoh, misalkan terdapat sebuah tabel yang memiliki kolom jenis kelamin. Misalkan tabel ini memiliki 5 row dan nilai kolom jenis kelaminnya adalah sebagai berikut:

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

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

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

Lalu Sebenarnya Digunakan di Mana?

Tentu banyak yang berpikir bahwa tujuannya bukan sekadar untuk merepresentasikan hal tersebut. Untuk benar-benar memanfaatkan indeks bitmap, 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);

Misalkan tabel ini memiliki 1.000.000 row. Lalu, misalkan kita menjalankan query berikut.

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

Query ini mencari row yang kolom active dan sex keduanya bernilai TRUE. Dengan demikian, cara tercepat untuk menemukan row yang memenuhi kondisi kedua kolom bernilai TRUE adalah dengan memanfaatkan operasi bit and.

  • Misalkan indeks bitmap untuk kolom active sudah diindeks sebelumnya sebagai 1100110011... (array bit sepanjang 1.000.000 bit), dan
  • indeks bitmap untuk kolom sex sudah diindeks sebelumnya sebagai 1010101010... (array bit sepanjang 1.000.000 bit).

Maka, dengan melakukan operasi bit and pada kedua indeks bitmap tersebut, row yang kedua kolomnya bernilai TRUE dapat ditemukan dengan cepat. Karena merupakan operasi bit sederhana, hasilnya dapat diperoleh jauh lebih cepat dibandingkan pemindaian indeks lainnya.

Trade-off

Indeks bitmap dapat sangat efisien, tetapi terdapat beberapa trade-off. Terdapat banyak kekurangan lainnya, namun untuk saat ini hanya satu yang akan dibahas.

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

Jika indeks bitmap digunakan pada kolom dengan kardinalitas tinggi, karena diperlukan pembuatan bitmap terpisah untuk setiap nilai unik, kebutuhan ruang penyimpanan bisa menjadi sangat besar. Sebagai contoh, jika terdapat 1.000.000 nilai unik pada suatu kolom, maka harus dibuat 1.000.000 bitmap, sehingga hal ini bisa menjadi sangat tidak efisien.

Lalu Kita

Untuk mengatasi bitmap yang timbul dari kardinalitas tinggi, kita dapat menggunakan sesuatu yang disebut Roaring Bitmap sebagai pengganti. Roaring Bitmap memiliki berbagai karakteristik, tetapi filosofi dasar dan karakteristik terbesarnya adalah memilih secara dinamis metode penyimpanan yang paling sesuai berdasarkan kepadatan data untuk memaksimalkan rasio kompresi dan kecepatan operasi sekaligus.

Konsep Dasar Roaring Bitmap

Pengindeksan Dua Tingkat

Roaring Bitmap melalui dua tahap berikut terlebih dahulu untuk menyimpan sebuah integer. Meskipun disebut pengindeksan dua tingkat, pada dasarnya anggaplah ini sebagai array dua dimensi.

  • Ekstraksi 16 bit atas: 16 bit atas dari integer diekstraksi dan digunakan sebagai indeks. Ini menjadi indeks array luar dari array dua dimensi dengan panjang total 65536. Array ini menyimpan alamat container yang akan dijelaskan kemudian.
  • Ekstraksi 16 bit bawah: 16 bit bawah dari integer diekstraksi dan digunakan sebagai posisi di dalam container.

Container

Container ini sesuai dengan array bagian dalam dari array dua dimensi seperti yang telah diumpamakan sebelumnya. Namun, berbeda dengan 16 bit atas, struktur internal container ini berubah tergantung pada seberapa banyak data yang ada di dalamnya. Roaring Bitmap mendukung 3 jenis container berikut.

  • Array Container: Container ini digunakan ketika data yang tersimpan di dalamnya sedikit. Secara spesifik, digunakan saat menyimpan 4096 elemen atau kurang. Container ini diimplementasikan sebagai array integer yang terurut sederhana. Elemen dapat dicari dengan pencarian biner.
  • Bitmap Container: Container ini digunakan ketika data yang tersimpan di dalamnya banyak. Secara spesifik, digunakan saat menyimpan lebih dari 4096 elemen. Container ini diimplementasikan sebagai bitmap sebesar 65536 bit (8192 byte). Setiap bit menunjukkan apakah integer pada posisi tersebut ada atau tidak.
  • Run Container: Container ini digunakan untuk menyimpan rentang integer yang berurutan. Misalnya, sangat efisien untuk menyimpan integer berurutan seperti 1, 2, 3, 4, 5. Container ini diimplementasikan sebagai daftar pasangan (nilai awal, panjang). Lalu bagaimana jika semuanya terisi? Artinya seluruh rentang dari awal hingga akhir terisi, sehingga cukup menyimpan satu pasangan (0, 65536) saja.

Pendekatan ini memungkinkan Roaring Bitmap menggunakan memori secara sangat efisien dan memberikan performa optimal untuk berbagai tingkat kepadatan data.

Fitur Roaring Bitmap

Fungsi Dasar

Roaring Bitmap menyediakan fungsi dasar berikut.

  • Penyisipan: Menambahkan integer baru ke dalam bitmap. Dalam proses ini, container yang sesuai dapat dipilih, atau container dapat dikonversi sesuai kebutuhan.
  • Penghapusan: Menghapus integer yang sudah ada dari bitmap. Dalam proses ini juga dilakukan penanganan yang sesuai bergantung pada kondisi container.
  • Pencarian: Memeriksa apakah suatu integer tertentu ada di dalam bitmap. Proses ini dilakukan dengan sangat cepat.

Operasi Himpunan

Roaring Bitmap juga mendukung operasi himpunan berikut.

  • Gabungan (Union): Membuat bitmap baru yang berisi seluruh elemen dari kedua bitmap.
  • Irisan (Intersection): Membuat bitmap baru yang hanya berisi elemen yang ada di kedua bitmap.
  • Selisih Simetris (Symmetric Difference): Membuat bitmap baru yang berisi elemen yang hanya ada di salah satu dari kedua bitmap.

Operasi-operasi ini dioptimalkan sesuai jenis container bitmap sehingga dapat dijalankan dengan sangat cepat.

Di Bahasa Go

Di Bahasa Go, Roaring Bitmap dapat digunakan dengan mudah melalui paket github.com/RoaringBitmap/roaring. Paket ini menyediakan seluruh fungsi Roaring Bitmap dan dioptimalkan sesuai 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)     // Diinisialisasi dengan 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Diinisialisasi dengan 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Menambahkan 5
14	b2.Add(10) // Menambahkan 10
15
16	b2.Remove(12) // Menghapus 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Operasi bitmap mengubah objek asli, sehingga gunakan salinan
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]

Selain fungsi-fungsi utama yang tidak muncul pada contoh kode di atas, terdapat fitur-fitur berikut:

  • Contains(x uint32) bool: Memeriksa apakah suatu nilai ada di dalam bitmap
  • GetCardinality() uint64: Mengembalikan jumlah elemen yang terdapat di dalam bitmap
  • Rank(x uint32) uint64: Mengembalikan jumlah elemen yang kurang dari atau sama dengan nilai tertentu
  • ToBytes() ([]byte, error): Melakukan serialisasi bitmap menjadi slice byte
  • FromBytes(data []byte) error: Memulihkan bitmap dari slice byte
  • Clone() *Bitmap: Membuat salinan bitmap
  • Clear(): Menginisialisasi ulang 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 atau sama dengan x
  • Maximum() uint32: Mengembalikan elemen terbesar di dalam bitmap
  • Minimum() uint32: Mengembalikan elemen terkecil di dalam bitmap

Demikianlah fitur-fitur yang tersedia. Untuk informasi lebih lanjut, silakan merujuk ke dokumentasi resmi.

Sebagai catatan, paket roaring juga memuat paket yang mendukung uint64 selain uint32. Karena antarmukanya hampir sama, paket tersebut dapat langsung digunakan sebagai pengganti.

 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)     // Diinisialisasi dengan 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Diinisialisasi dengan 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Menambahkan 5
14	b2.Add(10) // Menambahkan 10
15
16	b2.Remove(12) // Menghapus 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Operasi bitmap mengubah objek asli, sehingga gunakan salinan
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}

Penutup

Roaring Bitmap adalah alat yang kuat untuk menyimpan dan memanipulasi himpunan integer berkardinalitas tinggi secara efisien. Dengan menggunakan paket github.com/RoaringBitmap/roaring di Go, seluruh fungsi Roaring Bitmap dapat dimanfaatkan dengan mudah. Paket ini memaksimalkan penggunaan memori dan performa melalui berbagai jenis container serta operasi yang dioptimalkan. Roaring Bitmap dapat dimanfaatkan dalam berbagai bidang seperti pengindeksan basis data, analisis log, dan perhitungan statistik untuk mewujudkan pemrosesan data yang efisien.

Roaring Bitmap sangat unggul terutama pada kumpulan data berskala besar dan dapat digunakan secara bermanfaat dalam berbagai aplikasi. Dipadukan dengan sintaks Go yang ringkas dan efisien, Roaring Bitmap memberikan alat yang kuat bagi para pengembang. Ke depannya, diharapkan akan ada lebih banyak fitur dan optimisasi seiring perkembangan Roaring Bitmap.

Mengapa saya melakukan ini? Untuk pengindeksan setiap tag dan operasi gabungan yang cepat pada basis data time series.