Tablo Bölümleme

Dizin Bakımı dersi bir soruyu askıda bıraktı. Eski ödünç kayıtlarını silmek, dizin sırasıyla örtüşmediği her yerde ölü boşluk bıraktı ve o boşluğu geri almak tabloyu baştan yazmayı gerektirdi. Sorunun kaynağı silmenin kendisi değil, silinecek verinin canlı verinin arasına karışmış olmasıdır.

Bölümleme (partitioning), bu karışmayı baştan önler: mantıksal olarak tek bir tablo, fiziksel olarak birden çok parçada saklanır. Her parçaya bölüm (partition) denir ve bir satırın hangi bölüme düşeceğini bölüm anahtarı (partition key) belirler. Bu ders üç bölümleme biçimini kurar, kazancını ölçer ve kazancın nereden gelmediğini de gösterir.

Aralık Bölümlemesi

En yaygın biçim aralık bölümlemesidir (range partitioning): bölüm anahtarının değer aralıkları bölümlere karşılık gelir. Kütüphane kayıtlarında doğal anahtar alış tarihidir ve doğal aralık yıldır.

Bazı motorlar bölümlemeyi sözdizimiyle sunar; sunmayanlarda aynı yapı ayrı tablolar ve bir birleşim görünümüyle kurulur. Aşağıdaki koşum ikinci yolu izler. Her bölüm tablosu kendi aralığını bir değer denetimiyle bildirir ve bir görünüm bölümleri tek bir ad altında toplar.

rm -f bolumsuz.db bolumlu.db bolumle.sql
cat > kurulum.sql <<'SQL'
CREATE TABLE odunc (
  odunc_id    INTEGER PRIMARY KEY,
  kitap_id    INTEGER NOT NULL,
  uye_id      INTEGER NOT NULL,
  alis_tarihi TEXT NOT NULL,
  iade_tarihi TEXT
);
INSERT INTO odunc (odunc_id, kitap_id, uye_id, alis_tarihi, iade_tarihi)
WITH RECURSIVE sayac(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM sayac WHERE n < 2000000)
SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000),
       date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'),
       CASE WHEN n % 9 = 0 THEN NULL
            ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END
FROM sayac;
SQL
sqlite3 bolumsuz.db < kurulum.sql
sqlite3 bolumsuz.db 'CREATE INDEX odunc_alis ON odunc(alis_tarihi);'

# Yil basina bir bolum tablosu, deger denetimi ve bolumleri toplayan gorunum.
{
  echo "ATTACH 'bolumsuz.db' AS kaynak;"
  for y in 2018 2019 2020 2021 2022 2023 2024; do
    s=$((y + 1))
    cat <<EOF
CREATE TABLE odunc_$y (
  odunc_id    INTEGER PRIMARY KEY,
  kitap_id    INT NOT NULL,
  uye_id      INT NOT NULL,
  alis_tarihi TEXT NOT NULL CHECK (alis_tarihi >= '$y-01-01' AND alis_tarihi < '$s-01-01'),
  iade_tarihi TEXT);
INSERT INTO odunc_$y SELECT * FROM kaynak.odunc
  WHERE alis_tarihi >= '$y-01-01' AND alis_tarihi < '$s-01-01';
CREATE INDEX odunc_${y}_alis ON odunc_$y(alis_tarihi);
EOF
  done
  echo "CREATE VIEW odunc AS"
  echo "  SELECT * FROM odunc_2018 UNION ALL SELECT * FROM odunc_2019 UNION ALL"
  echo "  SELECT * FROM odunc_2020 UNION ALL SELECT * FROM odunc_2021 UNION ALL"
  echo "  SELECT * FROM odunc_2022 UNION ALL SELECT * FROM odunc_2023 UNION ALL"
  echo "  SELECT * FROM odunc_2024;"
} > bolumle.sql
sqlite3 bolumlu.db < bolumle.sql
sqlite3 bolumlu.db <<'SQL'
.mode column
.headers on
SELECT count(*) AS gorunum_satir FROM odunc;
SELECT name AS bolum, count(*) AS sayfa FROM dbstat
WHERE name LIKE 'odunc\_20__' ESCAPE '\' GROUP BY name ORDER BY name;
SQL

gorunum_satir
-------------
2000000      
bolum       sayfa
----------  -----
odunc_2018  2966 
odunc_2019  2982 
odunc_2020  2970 
odunc_2021  2959 
odunc_2022  2964 
odunc_2023  2982 
odunc_2024  1994 

Görünüm iki milyon satırın hepsini veriyor: uygulama tarafından bakıldığında tablo hâlâ tektir. Altında yedi ayrı tablo, yedi ayrı dizin ve her biri yaklaşık üç bin sayfalık yedi ayrı ağaç vardır.

Yalnız İlgili Bölüme Dokunmak

Bölümlemenin ilk iddiası şudur: bölüm anahtarını süzen bir sorgu diğer bölümleri hiç okumaz. Bu iddia plan çıktısında görünmez — plan yedi bölümü de listeler.

sqlite3 bolumlu.db "EXPLAIN QUERY PLAN
SELECT count(*) FROM odunc WHERE alis_tarihi BETWEEN '2021-03-01' AND '2021-03-31';"

for hedef in "bolumlu.db|odunc|bolumlu gorunum" \
             "bolumlu.db|odunc_2021|dogrudan 2021 bolumu" \
             "bolumsuz.db|odunc|bolumsuz tek tablo"; do
  db=${hedef%%|*}; kalan=${hedef#*|}; tablo=${kalan%%|*}; ad=${kalan#*|}
  printf '%-22s ' "$ad"
  sqlite3 "$db" <<SQL 2>&1 | grep -E 'Page cache misses|Run Time' | tr '\n' ' '
.stats on
.timer on
SELECT count(*) FROM $tablo WHERE alis_tarihi BETWEEN '2021-03-01' AND '2021-03-31';
SQL
  echo
done

QUERY PLAN
|--CO-ROUTINE odunc
|  `--COMPOUND QUERY
|     |--LEFT-MOST SUBQUERY
|     |  `--SEARCH odunc_2018 USING INDEX odunc_2018_alis (alis_tarihi>? AND alis_tarihi<?)
|     |--UNION ALL
|     |  `--SEARCH odunc_2019 USING INDEX odunc_2019_alis (alis_tarihi>? AND alis_tarihi<?)
|     |--UNION ALL
|     |  `--SEARCH odunc_2020 USING INDEX odunc_2020_alis (alis_tarihi>? AND alis_tarihi<?)
|     |--UNION ALL
|     |  `--SEARCH odunc_2021 USING INDEX odunc_2021_alis (alis_tarihi>? AND alis_tarihi<?)
|     |--UNION ALL
|     |  `--SEARCH odunc_2022 USING INDEX odunc_2022_alis (alis_tarihi>? AND alis_tarihi<?)
|     |--UNION ALL
|     |  `--SEARCH odunc_2023 USING INDEX odunc_2023_alis (alis_tarihi>? AND alis_tarihi<?)
|     `--UNION ALL
|        `--SEARCH odunc_2024 USING INDEX odunc_2024_alis (alis_tarihi>? AND alis_tarihi<?)
`--SCAN odunc
bolumlu gorunum        Page cache misses:                   141 Run Time: real 0.002 user 0.002195 sys 0.000186 
dogrudan 2021 bolumu   Page cache misses:                   123 Run Time: real 0.001 user 0.000566 sys 0.000115 
bolumsuz tek tablo     Page cache misses:                   123 Run Time: real 0.000 user 0.000570 sys 0.000158

Sayfa ıskası sayıları iddiayı doğruluyor. Yalnız 2021 bölümüne doğrudan sorulan sorgu 123 sayfa okudu; görünüm üzerinden sorulan sorgu 141 sayfa. Aradaki 18 sayfa, altı bölümün dizinine yapılan altı boş yoklamadır — bölüm başına üç sayfa. Yedi bölümün altısı planda görünüyor ama verisi hiç okunmuyor.

Ayrımın adı bölüm ayıklamasıdır (partition pruning). Yerleşik bölümleme sunan motorlarda ayıklama plan kurulurken yapılır ve ilgisiz bölümler plana hiç girmez; buradaki modelde çalışma zamanında oluyor, çünkü her boş yoklama kendi dizininde hemen sonuçsuz kalıyor. İki yolun sonucu yakındır, maliyeti değil: bölüm sayısı yüzlere çıktığında yüzlerce boş yoklamanın toplamı ihmal edilemez olur.

Üçüncü satır ise beklentiyi düzeltir. Bölümsüz tek tablo aynı sorguyu aynı 123 sayfayla yanıtladı. Dizin varken bölümleme okuma başarımı kazandırmaz; dizin zaten aynı işi yapıyordu. Bölümlemenin kazancı başka yerdedir.

Eski Veriyi Silmek ve Bölümü Düşürmek

Asıl kazanç, verinin bütün olarak kaldırılabilmesidir. Aşağıdaki koşum aynı işi iki kurulumda yapar: 2018 yılının kayıtlarını sistemden çıkarmak.

rm -f s1.db s2.db
cp bolumsuz.db s1.db
cp bolumlu.db  s2.db
olc() { printf '%-8s dosya=%s  toplam_sayfa=%s  serbest=%s\n' "$2" "$(wc -c < "$1")" \
  "$(sqlite3 "$1" 'PRAGMA page_count;')" "$(sqlite3 "$1" 'PRAGMA freelist_count;')"; }

echo "=== bolumsuz: eski yili silme ==="
olc s1.db once
sqlite3 s1.db <<'SQL' | grep 'Run Time'
.timer on
DELETE FROM odunc WHERE alis_tarihi < '2019-01-01';
SQL
olc s1.db silme
sqlite3 s1.db <<'SQL' | grep 'Run Time'
.timer on
VACUUM;
SQL
olc s1.db vacuum

echo
echo "=== bolumlu: eski bolumu dusurme ==="
olc s2.db once
sqlite3 s2.db <<'SQL' | grep 'Run Time'
.timer on
DROP VIEW odunc;
DROP TABLE odunc_2018;
CREATE VIEW odunc AS
  SELECT * FROM odunc_2019 UNION ALL SELECT * FROM odunc_2020 UNION ALL
  SELECT * FROM odunc_2021 UNION ALL SELECT * FROM odunc_2022 UNION ALL
  SELECT * FROM odunc_2023 UNION ALL SELECT * FROM odunc_2024;
SQL
olc s2.db dusurme
sqlite3 s2.db "SELECT count(*) FROM odunc;"

=== bolumsuz: eski yili silme ===
once     dosya= 112066560  toplam_sayfa=27360  serbest=0
Run Time: real 0.674 user 0.165852 sys 0.203029
silme    dosya= 112066560  toplam_sayfa=27360  serbest=1398
Run Time: real 0.460 user 0.157747 sys 0.262727
vacuum   dosya= 95285248  toplam_sayfa=23263  serbest=0

=== bolumlu: eski bolumu dusurme ===
once     dosya= 119492608  toplam_sayfa=29173  serbest=0
Run Time: real 0.000 user 0.000095 sys 0.000291
Run Time: real 0.074 user 0.002629 sys 0.007488
Run Time: real 0.000 user 0.000063 sys 0.000187
dusurme  dosya= 119492608  toplam_sayfa=29173  serbest=4367
1700444

İki yol aynı 299.556 satırı sistemden çıkardı; maliyetleri karşılaştırılamaz. Silme yolu 0,674 saniye sürdü ve yalnızca 1.398 sayfayı serbest bırakabildi — kalan boşluk sayfaların içine dağılmıştı. Boşluğu geri almak için çalıştırılan tam yeniden yazma 0,460 saniye daha aldı ve bu süre boyunca tablo kilitliydi. Toplam bir saniyeyi aştı.

Bölümü düşürme yolu 0,074 saniye sürdü ve 4.367 sayfayı tek işlemde serbest bıraktı. Yapılan iş satır silmek değil, bir nesneyi kaldırmaktır: maliyet satır sayısıyla değil, sabit bir katalog işlemiyle ölçülür. Süreler ortama bağlıdır; kararlı olan, birinin veriyle orantılı, diğerinin veriden bağımsız olmasıdır.

Bu, saklama süresi kuralı olan her sistemde bölümlemenin ana gerekçesidir. Aynı gerekçe ters yönde de çalışır: yeni bir dönem başladığında boş bir bölüm eklemek de sabit maliyetlidir.

Liste ve Karma Bölümlemesi

İki biçim daha vardır. Liste bölümlemesinde (list partitioning) her bölüm, anahtarın belirli değerlerini alır — şehir, şube, ülke. Karma bölümlemesinde (hash partitioning) bölüm, anahtarın bir karma fonksiyonundan geçirilip bölüm sayısına bölünmesiyle bulunur; amaç anlamlı bir gruplama değil, dengeli bir dağıtımdır.

Seçim, bölümlerin ne kadar dengeli dolacağına bağlıdır ve bu hesaplanabilir. Aşağıdaki model üye başına ödünç sayısını güç yasasına yakın dağıtır — az sayıda üye çok ödünç alır, çoğu üye birkaç kayıt bırakır — ve bölüm doluluklarını üç anahtar seçimi için sayar.

cat > dagilim.mjs <<'JS'
// Model: odunc kayitlarinin bolumlere dagilimi. Gercek bir motorun bolumleyicisi degil;
// olculen sey anahtar secimi ile bolum dolulugu arasindaki iliskidir.
// Uye basina odunc sayisi guc yasasina yakin dagitilir: az sayida uye cok odunc alir.
const UYE = 120000, KAYIT = 2000000;
const sehirler = [['Istanbul', 0.42], ['Ankara', 0.24], ['Izmir', 0.16],
                  ['Bursa', 0.11], ['Konya', 0.07]];

function uyeler() {
  const agirlik = [];
  let toplam = 0;
  for (let i = 1; i <= UYE; i++) { const a = 1 / Math.pow(i, 0.8); agirlik.push(a); toplam += a; }
  return agirlik.map((a, i) => {
    let esik = ((i * 7919) % 100) / 100, k = 0, birikim = 0;
    while (k < sehirler.length - 1 && (birikim += sehirler[k][1]) <= esik) k++;
    return { uye_id: i + 1, odunc: Math.max(1, Math.round(a / toplam * KAYIT)), sehir: sehirler[k][0] };
  });
}
const M = 2654435761n;
const karmaDusuk  = (x) => Number((BigInt(x) * M) % 4294967296n);          // dusuk bitler
const karmaYuksek = (x) => Number(((BigInt(x) * M) % 4294967296n) >> 20n); // yuksek bitler

function rapor(ad, kova) {
  const enCok = Math.max(...kova), enAz = Math.min(...kova);
  const bos = kova.filter((s) => s === 0).length;
  const oran = enAz === 0 ? 'bölüm boş: ' + bos : (enCok / enAz).toFixed(2) + '×';
  console.log(ad.padEnd(24), 'bölüm', String(kova.length).padStart(2),
              '| en dolu', String(enCok).padStart(8), '| en boş', String(enAz).padStart(8),
              '| oran', oran);
}
function dagit(uye, P, anahtar) {
  const kova = new Array(P).fill(0);
  for (const u of uye) kova[anahtar(u.uye_id) % P] += u.odunc;
  return kova;
}
const uye = uyeler();
console.log('modeldeki toplam ödünç:', uye.reduce((t, u) => t + u.odunc, 0));
console.log('— karma bölümleme, güç yasasına yakın anahtar —');
for (const P of [8, 16, 64]) {
  rapor('uye_id % P', dagit(uye, P, (x) => x));
  rapor('karma_yuksek % P', dagit(uye, P, karmaYuksek));
}
console.log('— yapılı anahtar: üyelik numarası dörtün katı —');
const dortluk = uye.map((u) => ({ ...u, uye_id: u.uye_id * 4 }));
rapor('uye_id % 8',       dagit(dortluk, 8, (x) => x));
rapor('karma_dusuk % 8',  dagit(dortluk, 8, karmaDusuk));
rapor('karma_yuksek % 8', dagit(dortluk, 8, karmaYuksek));
console.log('— liste bölümleme: şehir —');
const listeKova = sehirler.map(([ad]) =>
  uye.filter((u) => u.sehir === ad).reduce((t, u) => t + u.odunc, 0));
rapor('şehir', listeKova);
console.log(sehirler.map(([ad], i) => `${ad}=${listeKova[i]}`).join('  '));
JS
node dagilim.mjs

modeldeki toplam ödünç: 2001046
— karma bölümleme, güç yasasına yakın anahtar —
uye_id % P               bölüm  8 | en dolu   278850 | en boş   238066 | oran 1.17×
karma_yuksek % P         bölüm  8 | en dolu   273855 | en boş   233420 | oran 1.17×
uye_id % P               bölüm 16 | en dolu   158156 | en boş   116396 | oran 1.36×
karma_yuksek % P         bölüm 16 | en dolu   154631 | en boş   114336 | oran 1.35×
uye_id % P               bölüm 64 | en dolu    69604 | en boş    27466 | oran 2.53×
karma_yuksek % P         bölüm 64 | en dolu    69318 | en boş    26434 | oran 2.62×
— yapılı anahtar: üyelik numarası dörtün katı —
uye_id % 8               bölüm  8 | en dolu  1014448 | en boş        0 | oran bölüm boş: 6
karma_dusuk % 8          bölüm  8 | en dolu  1014448 | en boş        0 | oran bölüm boş: 6
karma_yuksek % 8         bölüm  8 | en dolu   285482 | en boş   236957 | oran 1.20×
— liste bölümleme: şehir —
şehir                    bölüm  5 | en dolu   876922 | en boş   139966 | oran 6.27×
Istanbul=876922  Ankara=464332  Izmir=312596  Bursa=207230  Konya=139966

Üç bulgu çıkıyor.

Birincisi: karma bölümlemesi anahtarları dengeler, satırları değil. Sekiz bölümde dengesizlik oranı 1,17; altmış dört bölümde 2,53. Bölüm küçüldükçe tek bir çok etkin üyenin ağırlığı bölümün tamamına göre büyür ve karma fonksiyonunun kalitesi bunu değiştirmez — üstteki iki satırın hemen hemen aynı çıkması bunu gösteriyor.

İkincisi: karma fonksiyonunun kalitesi anahtarın yapılı olduğu durumda belirleyicidir. Üyelik numaraları dördün katı olduğunda doğrudan bölme sekiz bölümün altısını boş bıraktı. Çarpımsal karmanın düşük bitleri de aynı sonucu verdi; nedeni aritmetiktir — tek bir çarpanla çarpıp ikinin kuvvetine bölmek düşük bitleri korur. Yüksek bitler alındığında dağılım 1,20 oranına düzeldi. Kural: karma değerinin düşük bitleri bölüm seçmek için kullanılmaz.

Üçüncüsü: liste bölümlemesi dengeyi hiç hedeflemez. Şehre göre bölünen kayıtlarda oran 6,27 çıktı ve bu bir kusur değil, gerçekliğin kendisidir. Liste bölümlemesi bölümlerin ayrı yönetilmesi gerektiğinde seçilir — bir şehrin verisinin ayrı saklanması, ayrı yedeklenmesi ya da ayrı silinmesi gerekiyorsa dengesizlik kabul edilir.

Özet

• Bölümleme, mantıksal olarak tek bir tabloyu bölüm anahtarına göre birden çok fiziksel parçada saklar; aralık, liste ve karma biçimleri anahtarın bölüme nasıl çevrildiğiyle ayrılır.
• Bölüm anahtarını süzen sorgu ilgisiz bölümlerin verisini okumaz: görünüm üzerinden 141, doğrudan tek bölümden 123 sayfa okundu; aradaki fark altı boş dizin yoklamasıdır.
• Dizin varken bölümleme okuma başarımı kazandırmadı; bölümsüz tablo aynı sorguyu aynı 123 sayfayla yanıtladı.
• Asıl kazanç veriyi bütün olarak kaldırmaktır: bir yılın silinip boşluğun geri alınması 1,13 saniye sürdü ve 1.398 sayfa serbest bıraktı; bölümün düşürülmesi 0,07 saniyede 4.367 sayfa serbest bıraktı.
• Karma bölümlemesi anahtarları dengeler, satırları değil; bölüm sayısı arttıkça dengesizlik büyüdü (1,17 → 2,53). Yapılı anahtarlarda karma değerinin düşük bitleri bölüm seçmek için kullanılamaz.

Sonraki Adım

Bu dersteki bütün bölümler aynı veritabanının içindeydi. Bölümleri ayrı makinelere dağıtmak, aynı fikri bir adım ileri götürür ve nitelik değiştirir: bölümler arası bir sorgu artık ağ üzerinden yürür, bir işlem birden çok makineyi kapsar ve bölüm sayısı değiştiğinde veri taşınmak zorunda kalır. Sonraki ders bu kalıbı ele alır — parça anahtarının seçiminin uygulamaya ne dayattığı, çapraz parça sorgusunun maliyeti ve yeniden dengelemede taşınan veri miktarı sayılarak.