Alt Sorgu Azaltma

Birleştirme, tabloları yan yana getirmenin tek yolu değildir. Aynı soru çoğu zaman alt sorguyla da yazılabilir; iki yazım aynı sonucu verir ama aynı planı üretmez.

Ayrımın kaynağı tek bir sorudadır: alt sorgu bir kez mi, yoksa dış sorgunun her satırı için bir kez mi değerlendirilir? Dış sorguya bağlı olmayan bir alt sorgu bir kez çalışır ve sonucu kullanılır. Dış satırdan bir değer alan ilişkili alt sorgu (correlated subquery) ise her satır için yeniden çalışır — yani gizli bir döngüdür ve maliyeti önceki dersteki iç içe döngü formülüne uyar.

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

İlişkili Alt Sorgu Bir Döngüdür

Soru şu: her üyenin en son aldığı kitap hangisidir? Doğrudan yazımı, her ödünç kaydı için o üyenin en büyük tarihini hesaplayıp karşılaştırmaktır.

sqlite3 kutuphane.db <<'SQL'
CREATE INDEX odunc_uye   ON odunc(uye_id);
CREATE INDEX odunc_kitap ON odunc(kitap_id);
CREATE INDEX odunc_alis  ON odunc(alis_tarihi);
EXPLAIN QUERY PLAN
SELECT count(*) FROM odunc o
WHERE o.alis_tarihi = (SELECT max(o2.alis_tarihi) FROM odunc o2 WHERE o2.uye_id = o.uye_id);
.timer on
.stats vmstep
SELECT count(*) FROM odunc o
WHERE o.alis_tarihi = (SELECT max(o2.alis_tarihi) FROM odunc o2 WHERE o2.uye_id = o.uye_id);
.timer off
.stats off
EXPLAIN QUERY PLAN
SELECT count(*) FROM
  (SELECT alis_tarihi, max(alis_tarihi) OVER (PARTITION BY uye_id) AS son FROM odunc)
WHERE alis_tarihi = son;
.timer on
.stats vmstep
SELECT count(*) FROM
  (SELECT alis_tarihi, max(alis_tarihi) OVER (PARTITION BY uye_id) AS son FROM odunc)
WHERE alis_tarihi = son;
SQL

QUERY PLAN
|--SCAN o
`--CORRELATED SCALAR SUBQUERY 1
   `--SEARCH o2 USING INDEX odunc_uye (uye_id=?)
120000
VM-steps: 232279993
Run Time: real 7.855 user 6.967326 sys 0.866287
QUERY PLAN
|--CO-ROUTINE (subquery-1)
|  |--CO-ROUTINE (subquery-3)
|  |  `--SCAN odunc USING INDEX odunc_uye
|  `--SCAN (subquery-3)
`--SCAN (subquery-1)
120000
VM-steps: 75200032
Run Time: real 1.050 user 1.027045 sys 0.022464

Birinci planda CORRELATED SCALAR SUBQUERY düğümü, alt sorgunun dış satıra bağlı olduğunu söyler. Dış tarafta iki milyon satır var; her biri için o üyenin bütün kayıtlarına bakılıp en büyük tarih bulunuyor. Dizinin varlığı iç maliyeti düşürüyor ama döngüyü ortadan kaldırmıyor: iki yüz otuz iki milyon adım.

İkinci yazım aynı hesabı pencere işleviyle (window function) yapıyor. Bileşik Sorgular konusunda tanıtılan bu yapı, her satıra kendi bölümünün toplu değerini iliştirir. Plandaki düğümler tek bir geçişi anlatıyor: dizin uye_id sırasında okunuyor, aynı üyenin satırları zaten yan yana olduğu için bölümün en büyüğü tek geçişte belirleniyor. Adım sayısı üçte birine, süre bu ortamda yedi buçukta birine indi.

Sonuç iki yazımda da aynı: 120.000. Kazancın kaynağı daha iyi bir dizin değil, aynı işin tekrarlanmamasıdır.

Aynı Sorunun Üç Yazımı

“2024 yılında en az bir kez ödünç alınmış kaç kitap var?” sorusu üç ayrı biçimde yazılabilir. Üçü de aynı sayıyı verir.

sqlite3 kutuphane.db <<'SQL'
EXPLAIN QUERY PLAN
SELECT count(*) FROM kitap k WHERE k.kitap_id IN
  (SELECT o.kitap_id FROM odunc o WHERE o.alis_tarihi >= '2024-01-01');
EXPLAIN QUERY PLAN
SELECT count(*) FROM kitap k WHERE EXISTS
  (SELECT 1 FROM odunc o WHERE o.kitap_id = k.kitap_id AND o.alis_tarihi >= '2024-01-01');
EXPLAIN QUERY PLAN
SELECT count(DISTINCT k.kitap_id) FROM kitap k JOIN odunc o ON o.kitap_id = k.kitap_id
WHERE o.alis_tarihi >= '2024-01-01';
.timer on
.stats vmstep
SELECT count(*) FROM kitap k WHERE k.kitap_id IN
  (SELECT o.kitap_id FROM odunc o WHERE o.alis_tarihi >= '2024-01-01');
SELECT count(*) FROM kitap k WHERE EXISTS
  (SELECT 1 FROM odunc o WHERE o.kitap_id = k.kitap_id AND o.alis_tarihi >= '2024-01-01');
SELECT count(DISTINCT k.kitap_id) FROM kitap k JOIN odunc o ON o.kitap_id = k.kitap_id
WHERE o.alis_tarihi >= '2024-01-01';
SQL

QUERY PLAN
|--SEARCH k USING INTEGER PRIMARY KEY (rowid=?)
`--LIST SUBQUERY 1
   |--SEARCH o USING INDEX odunc_alis (alis_tarihi>?)
   `--CREATE BLOOM FILTER
QUERY PLAN
|--SCAN k
`--CORRELATED SCALAR SUBQUERY 1
   `--SEARCH o USING INDEX odunc_kitap (kitap_id=?)
QUERY PLAN
|--USE TEMP B-TREE FOR count(DISTINCT)
|--SEARCH o USING INDEX odunc_alis (alis_tarihi>?)
`--SEARCH k USING INTEGER PRIMARY KEY (rowid=?)
105374
VM-steps: 1738206
Run Time: real 0.262 user 0.146818 sys 0.114816
105374
VM-steps: 9251955
Run Time: real 0.382 user 0.364876 sys 0.017004
105374
VM-steps: 1527452
Run Time: real 0.410 user 0.221352 sys 0.188635

Üç yazım, üç ayrı plan. IN yazımı alt sorguyu bir liste olarak üretip dış tarafa süzgeç kuruyor. EXISTS yazımı ilişkili: iki yüz bin kitabın her biri için odunc içinde arama yapıyor ve adım sayısı beş kat yüksek. Birleştirme yazımı en az adımı harcıyor, ancak DISTINCT için geçici bir yapı kurduğundan bu ortamda en uzun süreyi alıyor.

Çıkarılacak sonuç, bir yazımın diğerinden üstün olduğu değildir. Üç ölçüm üç ayrı sıralama veriyor ve adım sayısıyla süre aynı kazananı göstermiyor. EXISTS yazımı, aranan koşul çok seçici olduğunda ve ilk eşleşmede durabildiğinde öne geçer; IN yazımı alt sorgunun sonucu küçük olduğunda; birleştirme yazımı iki tarafın da büyük olduğu ve yinelemenin sorun olmadığı durumlarda. Karar ölçümle verilir.

Birleştirme yazımının bir yan etkisi de vardır: bir kitabın 2024 içinde birden çok ödüncü varsa birleştirme o kitabı birden çok satır olarak üretir. count(DISTINCT ...) yazımı bu yüzden zorunludur — eşdeğerlik, sonucun sayısında değil, satır çokluğunda bozulur.

NOT IN ve NULL

Yeniden yazımın eşdeğer olup olmadığı her zaman göründüğü kadar açık değildir. NOT IN ile NOT EXISTS arasındaki fark bunun en sert örneğidir.

sqlite3 kutuphane.db <<'SQL'
SELECT count(*) FROM kitap WHERE kitap_id NOT IN (SELECT 1 UNION ALL SELECT 2);
SELECT count(*) FROM kitap WHERE kitap_id NOT IN (SELECT 1 UNION ALL SELECT NULL);
SELECT count(*) FROM kitap k WHERE NOT EXISTS
  (SELECT 1 FROM (SELECT 1 AS v UNION ALL SELECT NULL) t WHERE t.v = k.kitap_id);
SELECT count(*) FROM odunc WHERE iade_tarihi IS NULL;
SQL

199998
0
199999
222222

İkinci sorgu sıfır döndürüyor. Nedeni üç değerli mantıktır: kitap_id NOT IN (1, NULL) ifadesi, kitap_id <> 1 AND kitap_id <> NULL demektir; ikinci karşılaştırma hiçbir zaman doğru olmaz, bilinmeyen kalır. Bilinmeyen bir koşulu olan satır süzgeçten geçemez, bu yüzden sonuç kümesi boşalır.

NOT EXISTS aynı tuzağa düşmez: eşleşme arar, bulamazsa satırı geçirir. Üçüncü sorgu 199.999 döndürüyor — beklenen sayı.

Bu, akademik bir ayrıntı değildir. Dördüncü sorgu, odunc tablosunda iki yüz yirmi iki binden fazla kaydın iade_tarihi alanının boş olduğunu gösteriyor. Bu sütun üzerinden kurulmuş bir NOT IN alt sorgusu sessizce boş sonuç üretir; sorgu hata vermez, yalnız yanlış cevap verir. NOT EXISTS yazımı hem bu davranıştan bağımsızdır hem de çoğu planlayıcı tarafından daha iyi eniyilenir.

Yeniden Yazımın Kuralı

Bu derste dört yazım çifti karşılaştırıldı. Ortak yöntem üç adımdır.

Birinci adım, alt sorgunun dış satıra bağlı olup olmadığını görmektir. Bağlıysa plan düğümünde bunu söyleyen bir işaret bulunur ve maliyet dış satır sayısıyla çarpılır. İkinci adım, satır başına yapılan işi tek geçişe indirecek bir yapı aramaktır: pencere işlevi, gruplama, ortak tablo ifadesi ya da birleştirme. Üçüncü adım, yeniden yazımın gerçekten eşdeğer olduğunu denetlemektir — NULL davranışı, satır çokluğu ve boş sonuç durumları bu denetimin üç ayrı kalemidir.

Eşdeğerlik denetiminin en güvenilir biçimi, iki yazımı da çalıştırıp sonuçları karşılaştırmaktır. Bu derste her karşılaştırmada iki yazımın da aynı sayıyı döndürdüğü gösterildi; bu bir teyit değil, yeniden yazımın ön koşuludur.

Özet

• Dış satıra bağlı bir alt sorgu her satır için yeniden değerlendirilir; maliyeti iç içe döngü formülüne uyar ve planda ilişkili olduğunu söyleyen bir düğümle görünür.
• Satır başına yapılan bir toplama, pencere işleviyle tek geçişe indirildiğinde bu veri kümesinde 232.279.993 adımdan 75.200.032 adıma düştü.
• Aynı soru IN, EXISTS ve birleştirme ile yazıldığında üç ayrı plan çıktı; adım sayısı ve süre aynı yazımı işaret etmedi, karar ölçümle verilir.
• Birleştirmeye çevrilen bir alt sorgu satır çokluğunu değiştirebilir; eşdeğerlik için DISTINCT ya da gruplama gerekir.
• Alt sorgunun sonucunda tek bir NULL varsa NOT IN boş küme döndürür; NOT EXISTS bu davranıştan etkilenmez.

Sonraki Adım

Buraya kadar planlayıcının verdiği kararlar hep yerinde çıktı: doğru tabloyu sürdü, doğru dizini seçti. Bu kararları neye dayanarak verdiği ise henüz sorulmadı. Planlayıcı veriyi sorgu anında okumaz; tablolar ve dizinler hakkında önceden toplanmış istatistiklere bakar ve her adımda kaç satır döneceğini tahmin eder. Sonraki ders bu tahminin kaynağını, ne kadar isabetli olduğunun nasıl ölçüleceğini ve tahmin bozulduğunda planın nasıl değiştiğini ele alır.