GoSuda

Canlı Bitmap

By snowmerak
views ...

Bitmap Nedir?

Burada bahsedilen bitmap bir tür indextir. Grafikler hakkında olduğunu düşünerek geldiyseniz geri tuşuna basabilirsiniz.

Temel Kavramlar

Bitmap, veritabanı indeksleme teknolojisinin bir biçimidir. Belirli bir sütunun değerlerini bir bit dizisi veya vektörünün bir elemanı veya biçimi olarak temsil eder ve her bit, ilgili 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 indexi atamak ve varlığı 0 ve 1 ile ifade etmektir.

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

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

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

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

Peki Gerçekte Nerede Kullanılır?

Bu yüzden herkes bunun sadece yukarıdakini temsil etmek için olmadığını düşünecektir. Bitmap indexi 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ı düşünelim.

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

Bu sorgu, hem active hem de sex sütunlarının TRUE olduğu satırları bulur. Bu durumda, 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 indexinin 1100110011... (1.000.000 bitlik dizi) olarak önceden indekslendiğini ve,
  • sex sütunu için bitmap indexinin 1010101010... (1.000.000 bitlik dizi) olarak önceden indekslendiğini varsayalım.

Bu durumda, iki bitmap index üzerinde bit and işlemi gerçekleştirilerek, her iki sütunun da TRUE olduğu satırlar hızlı bir şekilde bulunabilir. Basit bir bit işlemi olduğu için, diğer index taramalarından çok daha hızlı sonuçlar elde edilebilir.

Trade-off

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

Bitmap indexler, düşük kardinaliteye (yani, bir sütunda olası değerlerin sayısının az olduğu durumlar) daha uygundur. Yüksek kardinaliteli bir sütunda bitmap index kullanıldığında, bitmap çok büyük olabilir.

Yüksek kardinaliteli bir sütunda bitmap index kullanıldığında, her benzersiz değer için ayrı bir bitmap oluşturulması gerektiğinden, çok fazla depolama alanı gerekebilir. Örneğin, bir sütunda 1.000.000 benzersiz değer varsa, 1.000.000 bitmap oluşturulması gerekecektir ki bu da oldukça verimsiz olabilir.

Biz Ne Yapıyoruz?

Yüksek kardinaliteden kaynaklanan bitmap sorununu aşmak için Roaring Bitmap adı verilen bir yapı kullanılabilir. Roaring Bitmap'in çeşitli özellikleri olmakla birlikte, 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 çıkarmasıdır.

Roaring Bitmap'in Temel Kavramı

2 Aşamalı İndeksleme

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

  • Üst 16 bitin çıkarılması: Tam sayının üst 16 biti çıkarılır ve index olarak kullanılır. Toplam 65536 uzunluğunda olan 2 boyutlu dizinin dış dizisinin indexi haline gelir. Bu dizi, daha sonra bahsedilecek olan container'ın adresini saklar.
  • Alt 16 bitin çıkarılması: Tam sayının alt 16 biti çıkarılır ve container içindeki konum olarak kullanılır.

Container

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

  • Array Container: Bu container, içinde az veri depolandığında kullanılır. Özellikle, 4096'dan az eleman depolandığında kullanılır. Bu container, basitçe sıralı bir tam sayı dizisi olarak uygulanır. Elemanlar ikili arama ile bulunabilir.
  • Bitmap Container: Bu container, içinde çok veri depolandığında kullanılır. Özellikle, 4096'dan fazla eleman depolandığında kullanılır. Bu container, 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 container, 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 container, (başlangıç değeri, uzunluk) çiftlerinin bir listesi olarak uygulanır. Eğer hepsi varsa? Bu, baştan sona her şeyin olduğu anlamına gelir, bu yüzden sadece (0, 65536) depolanır.

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

Roaring Bitmap'in Özellikleri

Temel İşlevler

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

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

Küme İşlemleri

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

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

Bu işlemler, bitmapin container türüne göre optimize edilmiş olup ç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 işlevlerini 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'yi 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şturun ve kullanın
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 bitmapte olup olmadığını kontrol eder.
  • GetCardinality() uint64: Bitmapte bulunan eleman sayısını döndürür.
  • Rank(x uint32) uint64: Belirli bir değerden küçük veya ona eşit eleman sayısını döndürür.
  • ToBytes() ([]byte, error): Bitmapi bir byte dilimine serileştirir.
  • FromBytes(data []byte) error: Bir byte diliminden bitmapi geri yükler.
  • Clone() *Bitmap: Bitmapin bir kopyasını oluşturur.
  • Clear(): Bitmapi sıfırlar.
  • 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: Bitmapteki en büyük elemanı döndürür.
  • Minimum() uint32: Bitmapteki en küçük elemanı döndürür.

Bu tür işlevler mevcuttur. Ayrıntılı bilgi için resmi belgeye bakınız.

Roaring paketi, yalnızca uint32'yi değil, uint64'ü de destekleyen bir paketi içerir. Neredeyse aynı arayüzü sağladığı 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'yi 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şturun ve kullanın
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 işlevlerini kolayca kullanabilirsiniz. Bu paket, çeşitli container 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ştirmek mümkündür.

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 gelecekte daha fazla özellik ve optimizasyonun gerçekleştirilmesi beklenmektedir.

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