Column-Store, Bitmap ve RLE Üçlüsü

Veri tabanları, büyük veri ve veri ambarları gibi konularla uğraşırken karşıma çıkan teknik terimleri, kendi öğrendiğim süreçteki gibi sadeleştirerek blogda paylaşmaya karar verdim. Geçenlerde column-oriented (sütun bazlı) veri tabanı mimarilerini inceliyordum. ClickHouse, BigQuery, Snowflake gibi devlerin milyarlarca satırlık verileri saniyeler içinde nasıl analiz edebildiğini araştırırken karşıma iki büyüleyici kavram çıktı: Bitmap Encoding ve Run-Length Encoding (RLE).

Bu iki arkadaş bir araya geldiğinde disk alanından öyle bir tasarruf sağlıyor ve sorguları öyle bir uçuruyor ki, insan arka plandaki mühendislik zekasına hayran kalmadan edemiyor. Gelin, bu yapının arkasındaki sihirli mantığı birlikte çözelim.

1. Column-Store Neden Sıkıştırmaya Bu Kadar Aç?

Geleneksel veri tabanları (MySQL, PostgreSQL vb.) veriyi satır satır saklar. Yan yana duran veriler birbirinden tamamen farklı tiptedir: [1, "Ahmet", "1992-05-12", "İstanbul", "Gold"]. Bu kadar alakasız veriyi peş peşe koyduğunuzda optimize edip sıkıştırmak çok zordur.

Column-store ise her sütunu diskte ayrı birer dosya olarak tutar. Yani “Üyelik Tipi” sütununun dosyasını açtığınızda sadece şu veriyi görürsünüz: ["Gold", "Gold", "Gold", "Standart", "Premium", "Premium"]. İşte aynı veri tipinin ve tekrar eden değerlerin alt alta gelmesi, inanılmaz bir sıkıştırma potansiyeli doğurur.

2. İlk Adım: Bitmap Encoding (Bit Haritası Kodlaması)

Bitmap kodlaması, kategorik verileri bilgisayarın en iyi anladığı dile, yani 0 ve 1’lere (bit) dönüştürme işlemidir. Sistem, her bir kategori için ayrı bir bit haritası (vektör) oluşturur ve o satırdaki verinin o kategoriye ait olup olmadığını sadece 1 bit kullanarak işaretler.

Bir e-ticaret sitemiz olduğunu ve 5 müşterinin üyelik tipini tuttuğumuzu düşünelim:

Satır No	Orijinal Veri	Standart Haritası	Gold Haritası	Premium Haritası
1	Standart	1	0	0
2	Gold	0	1	0
3	Standart	1	0	0
4	Premium	0	0	1
5	Gold	0	1	0

Gün sonunda elimizde kalan saf bit dizileri şunlar oluyor:

• Standart: 10100
• Gold: 01010
• Premium: 00001

Neden Bu Kadar Hızlı? > Bilgisayar işlemcileri (CPU) bit düzeyindeki işlemleri (AND, OR, NOT) donanımsal olarak inanılmaz hızlı yapar. “Hem Gold üye olan hem de İstanbul’da yaşayanları getir” dediğinizde, işlemci iki bit haritasını üst üste koyup AND işlemine sokar. RAM’e milyonlarca satır yüklemek yerine sadece bitleri çarpar ve milisaniyeler içinde sonucu döner.

3. İkinci Adım: Run-Length Encoding (RLE)

Veri tabanında 10 milyon satır olduğunda bu 0 ve 1’lerin oluşturduğu kuyruklar da uzar. Ancak büyük veride veriler genellikle zamana, ID’ye veya belirli bir kritere göre sıralı tutulur. Bu da bit haritalarında arka arkaya binlerce, hatta milyonlarca 0 veya 1’in gelmesi demektir.

İşte Run-Length Encoding (RLE) tam bu noktada devreye girer. Tekrar eden veriyi tek tek yazmak yerine, “Veri + Tekrar Sayısı” formülüyle tutar.

Düz metin üzerinden mantığı çok basit:

• Sıkışmamış veri: AAAAABBBCCDDDD (14 karakter)
• RLE ile sıkışmış veri: 5A3B2C4D (8 karakter)

4. İki Teknolojinin Evliliği: “İnanılmaz Küçük Boyutlar”

Araştırırken beni en çok etkileyen kısım bu iki algoritmanın birleşimi oldu. 10 milyon satırlık veri tabanımızda “Ülke” sütunundaki verilerin sıralı kaydedildiğini hayal edelim. Türkiye’den gelen kullanıcılar peş peşe kayıt olmuşsa, “Türkiye” için oluşturulan bitmap haritası diskte şöyle görünecektir:

0000000000... (tam 10.000 tane sıfır) ...11110000...

Bunu ham haliyle saklarsanız diskte devasa bir yer kaplar. Ama RLE devreye girip sisteme şu komutu fısıldar:

“Burada arka arkaya on bin tane sıfır var, sonra dört tane bir var, sonra dört tane sıfır var.”

Diskte tutulan veri şuna dönüşür: (0, 10000), (1, 4), (0, 4). Megabaytlarca yer kaplayacak o devasa bit haritası, diskte sadece birkaç bayta indirgenir.

Özetle Ne Kazanıyoruz?

Sütun bazlı veri tabanlarını incelerken gördüğüm bu sıkıştırma yöntemleri, büyük veri dünyasının neden bu kadar hızlı çalıştığının en büyük kanıtı.

• Disk Tasarrufu: Aynı tür veriler alt alta geldiği için bu algoritmalarla %70 ila %90 arasında sıkıştırma oranları yakalanıyor. 1 TB’lık devasa bir veri ambarı diskte sadece 100 GB yer kaplayabiliyor.
• I/O (Giriş/Çıkış) Azalması: Bir sorgu attığınızda tüm satırlar değil, sadece ilgili sütunun zaten küçücük kalmış olan sıkıştırılmış dosyası diskten RAM’e taşınıyor. Disk daha az yoruluyor, sorgu saniyeler içinde ekrana düşüyor.

Veriyi akıllıca sıralayıp, bitlere indirgemek ve peş peşe gelenleri sayarak kaydetmek… Büyük veri dünyasında performansı uçuran bu akıllı çözümleri öğrenmek benim için ufuk açıcı oldu. Bir sonraki teknik keşfimde görüşmek üzere!