GoSuda

Canlı Bitmap

By snowmerak
views ...

Bitmap Nedir?

Burada bitmap bir indeks türüdür. Grafik düşündüyseniz ve buraya geldiyseniz, geri tuşuna basabilirsiniz.

Temel Kavram

Bitmap, veritabanı indeksleme teknolojisinin bir biçimidir. Belirli bir sütunun değerini bir bit dizisi veya bir vektörün bir elemanı veya biçimi olarak ifade eder, öyle ki her bit, o sütunun belirli bir değerinin var olup olmadığını gösterir. Bu nedenle, en temel biçimi, her satır için bir bit indeksi atamak ve varlığı 0 ve 1 ile ifade etmektir.

Örneğin, cinsiyet sütunu olan bir tablomuz olduğunu varsayalım. Bu tabloda 5 satır olduğunu ve cinsiyet sütununun değerlerinin aşağıdaki gibi olduğunu varsayalım:

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

Bu durumda, cinsiyet sütunu için bitmap indeksi şu şekilde ifade edilebilir:

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

Peki Gerçekten Nerede Kullanılır?

Bu yüzden herkes bunun sadece bunu göstermek için olmadığını düşünecektir. Bitmap indeksini doğru bir şekilde kullanmak için aşağıdaki durumu göz önünde bulunduralı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 olduğunu varsayalım. Ve aşağıdaki sorguyu çalıştırdığımızı varsayalım.

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

Bu sorgu, active ve sex sütunlarının her ikisi de TRUE olan satırları bulur. O zaman, her iki sütunun da TRUE olduğu koşulu sağlayan satırları en hızlı şekilde bulmak için bit AND işlemi kullanılabilir.

  • active sütunu için bitmap indeksinin 1100110011... (1.000.000 bitlik dizi) olarak önceden indekslenmiş olduğunu ve,
  • sex sütunu için bitmap indeksinin 1010101010... (1.000.000 bitlik dizi) olarak önceden indekslenmiş olduğunu varsayalım.

O zaman, her iki bitmap indeksi üzerinde bit AND işlemi gerçekleştirerek, her iki sütunun da TRUE olduğu satırlar hızlı bir şekilde bulunabilir. Bu, basit bir bit işlemi olduğu için diğer indeks taramalarından çok daha hızlı sonuçlar elde edilebilir.

Trade-off'lar

Bitmap indeksleri çok verimli olabilir, ancak bazı trade-off'ları vardır. Başka birçok dezavantajı olsa da, şimdilik sadece bir tanesine odaklanacağız.

Bitmap indeksleri, düşük kardinaliteye (yani, sütunda mümkün olan değerlerin sayısının az olduğu durumlara) daha uygundur. Yüksek kardinaliteli bir sütunda bitmap indeksi kullanılırsa, bitmap çok büyük olabilir.

Yüksek kardinaliteli bir sütunda bitmap indeksi kullanılırsa, her benzersiz değer için ayrı bir bitmap oluşturmak gerekebilir, bu da çok fazla depolama alanı gerektirebilir. Örneğin, bir sütunda 1.000.000 benzersiz değer varsa, 1.000.000 bitmap oluşturmak gerekecektir ki bu çok verimsiz olabilir.

Bu yüzden biz

Yüksek kardinaliteden kaynaklanan bitmap'leri Roaring Bitmap adı verilen bir şeyle değiştirebiliriz. Roaring Bitmap'in çeşitli özellikleri olsa da, en büyük temel felsefesi ve özelliği verinin 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 Kavramları

2 Aşamalı İndeksleme

Roaring Bitmap, bir tam sayıyı depolamak için önce aşağıdaki 2 aşamadan geçer. Bu 2 aşamalı indeksleme denilse de, aslında 2 boyutlu bir dizi olarak düşünebilirsiniz.

  • Üst 16 bitin çıkarılması: Tam sayının üst 16 biti çıkarılır ve bu, indeks olarak kullanılır. Toplam 65536 uzunluğunda olan 2 boyutlu dizinin dış dizisinin indeksi olur. Bu dizi, daha sonra açıklanacak konteynerin adresini saklar.
  • Alt 16 bitin çıkarılması: Tam sayının alt 16 biti çıkarılır ve bu, konteyner içindeki konum olarak kullanılır.

Konteyner

Bu konteyner, az önce bahsettiğimiz gibi 2 boyutlu dizinin iç dizisine karşılık gelir. Ancak üst 16 bitin aksine, bu konteynerin iç yapısı, içinde ne kadar veri olduğuna bağlı olarak değişir. Roaring Bitmap aşağıdaki 3 konteyner türünü destekler.

  • Array Container: Bu konteyner, içinde az veri depolandığında kullanılır. Özellikle 4096'dan az eleman depolandığında kullanılır. Bu konteyner sadece sıralı bir tam sayı dizisi olarak uygulanır. Elemanları ikili arama ile bulmak mümkündür.
  • Bitmap Container: Bu konteyner, içinde çok veri depolandığında kullanılır. Özellikle 4096'dan fazla eleman depolandığında kullanılır. Bu konteyner, 65536 bitlik (8192 bayt) bir bitmap olarak uygulanı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ı depolamak için kullanılır. Örneğin, 1, 2, 3, 4, 5 gibi ardışık tam sayıları depolarken verimlidir. Bu konteyner, (başlangıç değeri, uzunluk) çiftlerinin bir listesi olarak uygulanır. Eğer hepsi varsa? Sadece baştan sona kadar her şeyin var olduğu anlamına gelir, bu yüzden sadece (0, 65536) kaydedilir.

Bu yöntem, Roaring Bitmap'in belleği çok verimli kullanmasını ve çeşitli veri yoğunlukları için en uygun performansı sağlamasını mümkün kılar.

Roaring Bitmap'in Özellikleri

Temel Özellikler

Roaring Bitmap aşağıdaki temel özellikleri sağlar.

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

Küme İşlemleri

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

  • Birleşim (Union): İki bitmap'in tüm elemanlarını içeren yeni bir bitmap oluşturur.
  • Kesişim (Intersection): Yalnızca her iki bitmap'te de bulunan elemanları içeren yeni bir bitmap oluşturur.
  • Simetrik Fark (Symmetric Difference): Yalnızca iki bitmap'ten birinde bulunan elemanları içeren yeni bir bitmap oluşturur.

Bu işlemler, bitmap'in konteyner türüne göre optimize edilerek çok hızlı bir şekilde 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 özelliklerini sağlar ve Go dilinin özelliklerine göre 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 bir kopya oluşturularak kullanılır
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 özellikler şunlardır:

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

Bu tür özellikler mevcuttur. Ayrıntılı bilgi için resmi belgelere bakınız.

Roaring paketi sadece uint32'yi değil, uint64'ü de destekleyen bir paket içerir. Neredeyse aynı arayüzü sağladığından 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 bir kopya oluşturularak kullanılır
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 bir şekilde depolamak ve işlemek için güçlü bir araçtır. Go dilinde github.com/RoaringBitmap/roaring paketini kullanarak, Roaring Bitmap'in tüm özelliklerinden kolayca yararlanılabilir. Bu paket, çeşitli konteyner türleri ve optimize edilmiş işlemler aracılığıyla bellek kullanımını ve performansı en üst düzeye çıkarır. Veritabanı indeksleme, günlük analizi, istatistiksel hesaplamalar gibi çeşitli alanlarda Roaring Bitmap'i kullanarak verimli veri işleme uygulamaları geliştirilebilir.

Roaring Bitmap özellikle büyük veri kümelerinde yüksek performans gösterir ve çeşitli uygulamalarda faydalı bir şekilde kullanılabilir. Go dilinin özlü ve verimli sözdizimi ile birleştiğinde, Roaring Bitmap geliştiricilere güçlü bir araç sunar. Roaring Bitmap'in gelişimiyle birlikte, daha fazla özellik ve optimizasyonun gerçekleşmesi beklenmektedir.

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