Birleştirme Eniyilemesi

Önceki derslerdeki bütün ölçümler tek tablo üzerindeydi ve karar tekti: dizin mi, tarama mı. Birden çok tablo birleştiğinde karar sayısı artar. Veritabanı üç şeye ayrı ayrı karar verir: tabloların hangi sırayla okunacağı, her tabloya hangi yolla erişileceği ve satırların hangi yöntemle eşleştirileceği.

Bu üç karar birbirine bağlıdır ve yanlış birleşimi, doğru birleşiminden yüzlerce kat pahalıya mal olur. Bu ders kararların plandaki karşılığını ve ölçülen etkisini ele alır.

Veri Kümesi

rm -f kutuphane.db
cat > kurulum.sql <<'SQL'
CREATE TABLE sube (
  sube_id INTEGER PRIMARY KEY,
  ad      TEXT NOT NULL,
  sehir   TEXT NOT NULL
);
CREATE TABLE uye (
  uye_id       INTEGER PRIMARY KEY,
  ad           TEXT NOT NULL,
  sehir        TEXT NOT NULL,
  kayit_tarihi TEXT NOT NULL
);
CREATE TABLE kitap (
  kitap_id INTEGER PRIMARY KEY,
  baslik   TEXT NOT NULL,
  yazar    TEXT NOT NULL,
  yil      INTEGER NOT NULL,
  sube_id  INTEGER NOT NULL
);
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 sube (sube_id, ad, sehir) VALUES
  (1,'Merkez','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul'),
  (4,'Beyoglu','Istanbul'),(5,'Konak','Izmir'),(6,'Nilufer','Bursa'),
  (7,'Selcuklu','Konya'),(8,'Cankaya','Ankara');

INSERT INTO uye (uye_id, ad, sehir, kayit_tarihi)
WITH RECURSIVE sayac(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM sayac WHERE n < 120000)
SELECT n, 'Uye ' || n,
       CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir'
                  WHEN 3 THEN 'Bursa' ELSE 'Konya' END,
       date('2015-01-01', '+' || (n % 3200) || ' days')
FROM sayac;

INSERT INTO kitap (kitap_id, baslik, yazar, yil, sube_id)
WITH RECURSIVE sayac(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM sayac WHERE n < 200000)
SELECT n, 'Kitap ' || n, 'Yazar ' || (n % 4000), 1950 + (n % 75), 1 + (n % 8)
FROM sayac;

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 kutuphane.db < kurulum.sql

İç İçe Döngü ve İçerideki Dizin

Birleştirmenin en temel yöntemi iç içe döngü birleştirmesidir (nested loop join): dış tablodan okunan her satır için iç tabloda eşleşen satırlar aranır. Maliyeti tek bir çarpım verir — dış satır sayısı çarpı bir iç aramanın maliyeti. İkinci çarpanı belirleyen şey, iç taraftaki birleştirme sütununda dizin olup olmadığıdır.

sqlite3 kutuphane.db <<'SQL'
CREATE INDEX kitap_yazar ON kitap(yazar);
EXPLAIN QUERY PLAN
SELECT count(*) FROM kitap k JOIN odunc o ON o.kitap_id = k.kitap_id
WHERE k.yazar = 'Yazar 7';
.timer on
.stats vmstep
SELECT count(*) FROM kitap k JOIN odunc o ON o.kitap_id = k.kitap_id
WHERE k.yazar = 'Yazar 7';
.timer off
.stats off
CREATE INDEX odunc_kitap ON odunc(kitap_id);
EXPLAIN QUERY PLAN
SELECT count(*) FROM kitap k JOIN odunc o ON o.kitap_id = k.kitap_id
WHERE k.yazar = 'Yazar 7';
.timer on
.stats vmstep
SELECT count(*) FROM kitap k JOIN odunc o ON o.kitap_id = k.kitap_id
WHERE k.yazar = 'Yazar 7';
SQL

QUERY PLAN
|--SCAN o
`--SEARCH k USING INTEGER PRIMARY KEY (rowid=?)
500
VM-steps: 10000512
Run Time: real 0.378 user 0.338558 sys 0.039777
QUERY PLAN
|--SEARCH k USING COVERING INDEX kitap_yazar (yazar=?)
`--SEARCH o USING COVERING INDEX odunc_kitap (kitap_id=?)
500
VM-steps: 1712
Run Time: real 0.000 user 0.000062 sys 0.000049

Birinci planda odunc sürücü tablo: iki milyon ödünç kaydı okunuyor, her biri için kitap tablosuna birincil anahtarla gidiliyor ve sonunda yazar koşulu süzüyor. Sorgu beş yüz satır döndürmek için on milyon adım harcıyor.

İkinci planda sıra tersine döndü. Fark, tek bir dizinin varlığıdır: odunc.kitap_id üzerinde dizin olduğu anda kitap tablosundan başlamak anlamlı hale geldi. Yazar koşulu elli kitap bırakıyor, her kitap için ödünç kayıtları dizinden aranıyor. On milyon adım 1.712 adıma indi.

Buradan çıkan kural, birleştirme başarımının en kısa özetidir: birleştirme sütunlarında dizin yoksa sıra seçilemez. Planlayıcının önündeki seçenek sayısı, dizinlerin açtığı erişim yollarıyla belirlenir.

Sıranın Ölçülen Etkisi

Sıranın etkisini yalıtmak için aynı sorgu, dizinler yerinde dururken ters sırada çalıştırılır. Bu motorda CROSS JOIN yazımı birleştirme sırasını sabitler: soldaki tablo dış döngü olur. Sıra sabitlemenin yazımı motora göre değişir; burada bir ölçüm aracı olarak kullanılıyor.

sqlite3 kutuphane.db <<'SQL'
EXPLAIN QUERY PLAN
SELECT count(*) FROM odunc o CROSS JOIN kitap k ON k.kitap_id = o.kitap_id
WHERE k.yazar = 'Yazar 7';
.timer on
.stats vmstep
SELECT count(*) FROM odunc o CROSS JOIN kitap k ON k.kitap_id = o.kitap_id
WHERE k.yazar = 'Yazar 7';
SQL

QUERY PLAN
|--SCAN o USING COVERING INDEX odunc_kitap
`--SEARCH k USING INTEGER PRIMARY KEY (rowid=?)
500
VM-steps: 10000512
Run Time: real 0.067 user 0.063345 sys 0.004211

Aynı veri, aynı dizinler, aynı sonuç: 500. Yalnız sıra değişti ve adım sayısı 1.712’den 10.000.512’ye çıktı — beş bin sekiz yüz kat. Dış döngüde iki milyon satır olduğunda içeride ne kadar ucuz bir arama yapıldığının pek önemi kalmıyor.

Bu çıktı ikinci bir şey daha gösteriyor. Adım sayısı, dizinsiz durumdaki ölçümle birebir aynı: 10.000.512. Süre ise beş kat kısa. İki ölçünün farklı şeyleri saydığı buradan görülür: adım sayısı sanal makinenin çalıştırdığı komutları sayar, süre ise okunan baytları da hesaba katar. Kapsayan dizin üzerinden tarama, tablo üzerinden taramayla aynı sayıda komut çalıştırır ama çok daha az veri okur.

Döngü Nasıl Ölçekleniyor

İç içe döngünün maliyeti dış satır sayısıyla doğru orantılıdır. Aşağıdaki ölçüm iki farklı süzme koşuluyla dış tarafı büyütür.

sqlite3 kutuphane.db <<'SQL'
CREATE INDEX kitap_yil ON kitap(yil);
.stats vmstep
SELECT count(*) FROM kitap WHERE yazar = 'Yazar 7';
SELECT count(*) FROM kitap k JOIN odunc o ON o.kitap_id = k.kitap_id
WHERE k.yazar = 'Yazar 7';
SELECT count(*) FROM kitap WHERE yil = 1990;
SELECT count(*) FROM kitap k JOIN odunc o ON o.kitap_id = k.kitap_id
WHERE k.yil = 1990;
SQL

50
VM-steps: 161
500
VM-steps: 1712
2667
VM-steps: 8012
26670
VM-steps: 90690

Dış taraf elli satırdan 2.667 satıra çıktığında (53,3 kat), birleştirmenin adım sayısı 1.712’den 90.690’a çıkıyor (53,0 kat). Oran neredeyse birebir: döngü, dış satır sayısında $O(n)$ davranıyor ve iç aramanın maliyeti sabit kalıyor.

Bu doğrusallık, iç içe döngünün hem gücü hem sınırıdır. Dış taraf küçükse yöntem yenilmezdir: hiçbir hazırlık yapılmaz, yalnız gereken satırlara dokunulur. Dış taraf büyüdükçe her satır için ayrı bir ağaç inişi yapılır ve bu inişlerin toplamı, iki tabloyu bir kez baştan sona okumaktan pahalı hale gelir.

İki Küme Yöntemi

Dış taraf büyüdüğünde satır satır arama yerine küme temelli iki yöntem kullanılır. İkisi de standart ilişkisel eniyilemenin parçasıdır; hangi motorun hangisini gerçekleştirdiği değişir.

Karma birleştirme (hash join) küçük tarafı bir kez okuyup birleştirme sütunundan bir karma tablosu kurar, sonra büyük tarafı bir kez okuyup her satırın eşleşmesini bu tablodan arar. Maliyeti iki girdinin toplamıdır, çarpımı değil. Koşulu vardır: eşitlik karşılaştırması gerekir ve karma tablosunun belleğe sığması beklenir; sığmazsa tablo parçalara bölünüp diske taşınır. Veri Yapıları kursundaki Karma Tabloları dersinde kurulan yapı budur.

Sıralı birleştirme (merge join) iki girdiyi de birleştirme sütununa göre sıralı okur ve iki imleci birlikte ilerleterek tek geçişte eşleştirir. Girdiler zaten sıralıysa — örneğin her iki tarafta da o sütunda dizin varsa — hazırlık maliyeti yoktur ve bellek kullanımı düşüktür. Sıralı değilse önce sıralama gerekir; o zaman maliyeti sıralama belirler.

Seçim üç ölçüye bakar: girdilerin büyüklüğü, birleştirme koşulunun eşitlik olup olmaması ve girdilerin hazır sıralı gelip gelmediği. Küçük dış taraf ve dizinli iç taraf iç içe döngüyü, iki büyük tablo karma birleştirmeyi, iki sıralı büyük girdi sıralı birleştirmeyi işaret eder.

Bu ders boyunca ölçülen planların hepsi iç içe döngüdür; kullanılan motorun birleştirme yöntemi budur. Plan çıktısında hangi ailenin göründüğü motora bağlıdır, ancak okunacak karar aynıdır: hangi taraf sürüyor, iç tarafa nasıl erişiliyor ve eşleştirme satır satır mı yoksa küme olarak mı yapılıyor.

Özet

• İç içe döngü birleştirmesinin maliyeti, dış satır sayısı ile bir iç aramanın maliyetinin çarpımıdır; iç taraftaki dizin ikinci çarpanı belirler.
• Birleştirme sütununda dizin olmadığında planlayıcının sıra seçeneği kalmaz; dizin eklendiğinde aynı sorgu 10.000.512 adımdan 1.712 adıma indi.
• Sıra tek başına belirleyicidir: dizinler yerinde dururken sıranın tersine çevrilmesi aynı sorgunun adım sayısını beş bin sekiz yüz kat artırdı.
• Aynı adım sayısı aynı süre demek değildir; kapsayan dizin üzerinden tarama, tablo taramasıyla aynı komut sayısında beş kat kısa sürdü.
• Dış taraf büyüdükçe iç içe döngü doğrusal büyür; bu noktadan sonra karma birleştirme ya da sıralı birleştirme gibi küme temelli yöntemler tercih edilir.

Sonraki Adım

Birleştirme, tabloları yan yana getirmenin tek yolu değildir. Aynı soru çoğu zaman alt sorguyla da yazılabilir ve iki yazım aynı sonucu verirken çok farklı planlar üretebilir — özellikle alt sorgu dış satıra bağlıysa. Sonraki ders bu yazımları karşılaştırır: hangi alt sorgu bir kez, hangisi satır başına değerlendirilir ve hangi eşdeğer yeniden yazım aradaki farkı kapatır.