GoSuda

Canlı Bitmap

By snowmerak views ...

Bitmap Nedir?

Buradaki bitmap, bir indeks türüdür. Grafik işleme bağlamında geldiyseniz geri dönebilirsiniz.

Temel Kavram

Bitmap, veritabanlarında kullanılan bir indeksleme tekniği türüdür. Belirli bir sütunun değerlerini bit dizisi veya vektörün bir öğesi biçiminde temsil eder ve her bit, ilgili sütunda belirli bir değerin var olup olmadığını gösterir. Dolayısıyla en temel biçimi, her satıra bir bit indeksi atamak ve varlığını 0 ve 1 ile ifade etmektir.

Örneğin, cinsiyet sütunu bulunan bir tablo olduğunu varsayalım. Bu tabloda 5 satır bulunsun ve cinsiyet sütununun değerleri şöyle olsun:

  1. Erkek
  2. Kadın
  3. Erkek
  4. Kadın
  5. Diğer

Bu durumda, cinsiyet sütunu için bitmap indeksi şu şekilde gösterilebilir:

  • Erkek: 10100
  • Kadın: 01010
  • Diğer: 00001

Gerçekte Nerede Kullanılır

Elbette bunun yalnızca bu değerleri göstermek için olmadığını herkes düşünecektir. Bitmap indeksini düzgün biçimde kullanmak için aşağıdaki durumu ele alalım.

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

Bu tabloda 1.000.000 satır bulunduğunu varsayalım. Ayrıca aşağıdaki sorguyu çalıştırdığımızı düşünelim.

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

Bu sorgu, active ve sex sütunlarının her ikisinin de TRUE olduğu satırları bulur. Bu durumda, iki sütunun da TRUE olduğu satırları en hızlı şekilde bulmak için bit AND işlemi kullanılabilir.

  • active sütunu için bitmap indeksi önceden 1100110011... (1.000.000 bitlik bir dizi) olarak indekslenmiş olsun,
  • sex sütunu için bitmap indeksi önceden 1010101010... (1.000.000 bitlik bir dizi) olarak indekslenmiş olsun.

Bu durumda iki bitmap indeksi üzerinde bit AND işlemi gerçekleştirilerek, iki sütunun da TRUE olduğu satırlar hızlı biçimde bulunabilir. Basit bir bit işlemi olduğu için, diğer indeks taramalarına kıyasla sonucu çok daha hızlı elde edilebilir.

Ödünleşimler

Bitmap indeksi çok verimli olabilir, ancak bazı ödünleşimleri vardır. Birçok başka dezavantajı olmakla birlikte şimdilik yalnızca birini ele alacağım.

Bu da bitmap indeksinin düşük kardinalite (yani sütunda olası değerlerin sayısının az olduğu durumlar) için daha uygun olmasıdır. Yüksek kardinaliteli bir sütunda bitmap indeksi kullanılırsa, bitmap çok büyüyebilir.

Yüksek kardinaliteli bir sütunda bitmap indeksi kullanıldığında, her benzersiz değer için ayrı bir bitmap oluşturulmak zorunda olduğundan depolama alanına ihtiyaç duyulabilir. Örneğin, bir sütunda 1.000.000 benzersiz değer varsa, 1.000.000 bitmap oluşturulması gerekir ve bu da oldukça verimsiz olabilir.

Bu Noktada Biz

Yüksek kardinalitede ortaya çıkan bitmap sorununu gidermek için Roaring Bitmap adlı yapı kullanılabilir. Roaring Bitmap'in birçok özelliği vardır, ancak en temel felsefesi ve özelliği veri yoğunluğuna göre en uygun depolama yöntemini dinamik olarak seçerek hem sıkıştırma oranını hem de işlem hızını en üst düzeye çıkarmaktır.

Roaring Bitmap'in Temel Kavramı

İki Aşamalı İndeksleme

Roaring Bitmap, bir tam sayıyı saklamak için önce şu iki aşamayı izler. İki aşamalı indeksleme demesi de olsa, aslında bunu iki boyutlu bir dizi olarak düşünebilirsiniz.

  • Üst 16 bitin çıkarılması: Tam sayının üst 16 biti çıkarılır ve indeks olarak kullanılır. Uzunluğu toplam 65536 olan iki boyutlu dizinin dış dizisinin indeksi olur. Bu dizi, aşağıda açıklanacak konteynerin adresini saklar.
  • Alt 16 bitin çıkarılması: Tam sayının alt 16 biti çıkarılır ve konteyner içindeki konum olarak kullanılır.

Konteyner

Bu konteyner, az önce benzetmesini yaptığımız iki boyutlu dizinin iç dizisine karşılık gelir. Ancak üst 16 bitin tuttuğu diziden farklı olarak, bu konteynerin iç yapısı içinde bulunan veri miktarına göre değişir. Roaring Bitmap şu 3 konteyner türünü destekler.

  • Array Container: Bu konteyner, içinde az veri saklandığında kullanılır. Somut olarak, 4096 veya daha az öğe saklandığında kullanılır. Bu konteyner basitçe sıralanmış bir tam sayı dizisi olarak uygulanmıştır. Öğeyi bulmak için ikili arama yapılabilir.
  • Bitmap Container: Bu konteyner, içinde çok veri saklandığında kullanılır. Somut olarak, 4096'dan fazla öğe saklandığında kullanılır. Bu konteyner 65536 bitlik (8192 bayt) bir bitmap olarak uygulanmıştır. Her bit, ilgili konumdaki tam sayının var olup olmadığını gösterir.
  • Run Container: Bu konteyner, ardışık tam sayı aralıklarını saklamak için kullanılır. Örneğin 1, 2, 3, 4, 5 gibi ardışık tam sayıları saklarken verimlidir. Bu konteyner (başlangıç değeri, uzunluk) çiftlerinden oluşan bir liste olarak uygulanmıştır. Peki ya hepsi mevcutsa? Bu, baştan sona her şeyin mevcut olduğu anlamına gelir; bu durumda yalnızca (0, 65536) saklanması yeterlidir.

Bu yöntem, Roaring Bitmap'in belleği çok verimli kullanmasını ve farklı veri yoğunlukları için en iyi performansı sunmasını sağlar.

Roaring Bitmap'in İşlevleri

Temel İşlevler

Roaring Bitmap aşağıdaki temel işlevleri sağlar.

  • Ekleme: Bitmap'e yeni bir tam sayı ekler. Bu süreçte uygun konteyner seçilebilir veya gerektiğinde konteyner dönüştürülebilir.
  • Silme: Bitmap'ten mevcut bir tam sayıyı kaldırır. Bu süreçte de konteynerin durumuna göre uygun işlem yapılır.
  • Arama: Belirli bir tam sayının bitmap içinde var olup olmadığını kontrol eder. Bu işlem çok hızlı gerçekleştirilir.

Küme İşlemleri

Roaring Bitmap ayrıca aşağıdaki küme işlemlerini destekler.

  • Birleşim (Union): İki bitmap'in tüm öğelerini içeren yeni bir bitmap oluşturur.
  • Kesişim (Intersection): Yalnızca iki bitmap'te birlikte bulunan öğeleri içeren yeni bir bitmap oluşturur.
  • Simetrik Fark (Symmetric Difference): İki bitmap'ten yalnızca birinde bulunan öğeleri içeren yeni bir bitmap oluşturur.

Bu işlemler, bitmap'in konteyner türüne göre optimize edildiği için çok hızlı gerçekleştirilir.

Go Dilinde

Go dilinde github.com/RoaringBitmap/roaring paketini kullanarak Roaring Bitmap'i kolayca kullanabilirsiniz. Bu paket, Roaring Bitmap'in tüm işlevlerini sağlar ve Go dilinin özelliklerine uygun şekilde optimize edilmiştir.

Kurulum

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

Kullanım Örneği

 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)     // 1, 2, 3, 4 ile başlat
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // 2, 4, 6, 8, 12 ile başlat
12
13	b1.Add(5)  // 5 ekle
14	b2.Add(10) // 10 ekle
15
16	b2.Remove(12) // 12 kaldır
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// bitmap işlemleri orijinali değiştirdiği için kopya oluşturup kullan
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]

Yukarıdaki örnek kodda yer almayan başlıca işlevler şunlardır:

  • Contains(x uint32) bool: Belirli bir değerin bitmap içinde var olup olmadığını kontrol eder
  • GetCardinality() uint64: Bitmap'te bulunan öğe sayısını döndürür
  • Rank(x uint32) uint64: Belirli bir değerden küçük veya eşit öğe sayısını döndürür
  • ToBytes() ([]byte, error): Bitmap'i bayt dilimine serileştirir
  • FromBytes(data []byte) error: Bitmap'i bayt diliminden geri yükler
  • Clone() *Bitmap: Bitmap'in kopyasını oluşturur
  • Clear(): Bitmap'i temizler
  • NextValue(x uint32) int64: x'ten büyük veya eşit bir sonraki öğeyi döndürür
  • PreviousValue(x uint32) int64: x'ten küçük veya
  • Maximum() uint32: Bitmap'teki en büyük öğeyi döndürür
  • Minimum() uint32: Bitmap'teki en küçük öğeyi döndürür

Bu işlevler de mevcuttur. Ayrıntılı bilgi için resmi dokümantasyona bakabilirsiniz.

Ayrıca roaring paketi, uint32'nin yanı sıra uint64'ü destekleyen bir paket de içermektedir. Hemen hemen aynı arayüzü sunduğu için doğrudan değiştirilerek kullanılabilir.

 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)     // 1, 2, 3, 4 ile başlat
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // 2, 4, 6, 8, 12 ile başlat
12
13	b1.Add(5)  // 5 ekle
14	b2.Add(10) // 10 ekle
15
16	b2.Remove(12) // 12 kaldır
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// bitmap işlemleri orijinali değiştirdiği için kopya oluşturup kullan
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}

Sonuç

Roaring Bitmap, yüksek kardinaliteli tam sayı kümelerini verimli biçimde saklamak ve işlemek için güçlü bir araçtır. github.com/RoaringBitmap/roaring paketini Go dilinde kullandığınızda, Roaring Bitmap'in tüm işlevlerinden kolayca yararlanabilirsiniz. Bu paket, çeşitli konteyner türleri ve optimize edilmiş işlemler sayesinde bellek kullanımını ve performansı en üst düzeye çıkarır. Veritabanı indeksleme, günlük analizi, istatistiksel hesaplama gibi birçok alanda Roaring Bitmap'ten yararlanarak verimli veri işleme gerçekleştirebilirsiniz.

Roaring Bitmap özellikle büyük ölçekli veri kümelerinde yüksek performans sergiler ve çeşitli uygulamalarda faydalı şekilde kullanılabilir. Go dilinin sade ve verimli sözdizimiyle birleştiğinde, Roaring Bitmap geliştiricilere güçlü bir araç sunar. Roaring Bitmap'in gelişimiyle birlikte daha fazla işlev ve optimizasyonun ortaya çıkması beklenmektedir.

Bunu neden yaptım derseniz? Zaman serisi veritabanlarında her etiket için indeksleme ve hızlı birleşim işlemleri yapabilmek için.