Bileşik ve Kısmi Dizinler

Önceki ders dizin türlerini birbirinden ayırdı ve hepsinde tek sütunlu, tablonun tamamını kapsayan dizinler kullandı. İki kısıtlama da tasarım kararıdır, zorunluluk değil.

Bir dizin birden çok sütun taşıyabilir. Bu durumda ortaya yeni bir soru çıkar: sütunlar hangi sırayla yazılacak? Sorgu Planı Okuma dersinde bu sorunun tek bir sorgu üzerindeki karşılığı ölçülmüştü ve bir sıra kırk dört bin kat kazanmıştı. O ölçüm eksik bir izlenim bırakır: sanki sıralardan biri doğru, diğeri yanlıştır. Gerçekte her sıra bir sorgu kümesine hizmet eder ve başka bir kümeyi dışarıda bırakır. Bu ders üç sorguyla o dengeyi gösterir, sonra ikinci kısıtlamayı gevşetir: tablonun yalnız bir bölümünü kapsayan dizin.

Üç Sorgu, İki Sıra

Ölçümler kütüphane ödünç kayıtları üzerinde yapılır. Aşağıdaki kurulum bu ders için gereken iki tabloyu kurar.

rm -f kutuphane.db
cat > kurulum.sql <<'SQL'
CREATE TABLE uye (
  uye_id       INTEGER PRIMARY KEY,
  ad           TEXT NOT NULL,
  sehir        TEXT NOT NULL,
  kayit_tarihi TEXT 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 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 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

Üç sorgu, ödünç masasının gerçekten sorduğu üç sorudur. Birincisi bir üyenin ödünç geçmişini tarih sırasında ister. İkincisi belli bir günde alınan bütün kitapları sayar. Üçüncüsü bir üyenin belli bir tarihten sonraki kayıtlarını ister. Aynı iki sütun, iki ayrı sırayla dizinlenir ve üç sorgu her iki dizinle de çalıştırılır.

for sira in "uye_id, alis_tarihi" "alis_tarihi, uye_id"; do
  rm -f sira.db
  sqlite3 sira.db < kurulum.sql
  sqlite3 sira.db "CREATE INDEX odunc_bilesik ON odunc($sira);"
  printf '=== dizin: (%s) ===\n' "$sira"
  sqlite3 sira.db <<'SQL'
.print '-- S1: uye esitligi, tarihe gore sirali'
EXPLAIN QUERY PLAN SELECT odunc_id FROM odunc WHERE uye_id = 4 ORDER BY alis_tarihi;
.stats vmstep
SELECT count(*) FROM (SELECT odunc_id FROM odunc WHERE uye_id = 4 ORDER BY alis_tarihi);
.stats off
.print '-- S2: yalniz tarih esitligi'
EXPLAIN QUERY PLAN SELECT count(*) FROM odunc WHERE alis_tarihi = '2021-03-15';
.stats vmstep
SELECT count(*) FROM odunc WHERE alis_tarihi = '2021-03-15';
.stats off
.print '-- S3: uye esitligi + tarih araligi'
EXPLAIN QUERY PLAN SELECT count(*) FROM odunc WHERE uye_id = 4 AND alis_tarihi >= '2022-01-01';
.stats vmstep
SELECT count(*) FROM odunc WHERE uye_id = 4 AND alis_tarihi >= '2022-01-01';
SQL
done

=== dizin: (uye_id, alis_tarihi) ===
-- S1: uye esitligi, tarihe gore sirali
QUERY PLAN
`--SEARCH odunc USING COVERING INDEX odunc_bilesik (uye_id=?)
17
VM-steps: 135
-- S2: yalniz tarih esitligi
QUERY PLAN
`--SCAN odunc USING COVERING INDEX odunc_bilesik
820
VM-steps: 6000831
-- S3: uye esitligi + tarih araligi
QUERY PLAN
`--SEARCH odunc USING COVERING INDEX odunc_bilesik (uye_id=? AND alis_tarihi>?)
8
VM-steps: 37
=== dizin: (alis_tarihi, uye_id) ===
-- S1: uye esitligi, tarihe gore sirali
QUERY PLAN
`--SCAN odunc USING COVERING INDEX odunc_bilesik
17
VM-steps: 6000101
-- S2: yalniz tarih esitligi
QUERY PLAN
`--SEARCH odunc USING COVERING INDEX odunc_bilesik (alis_tarihi=?)
820
VM-steps: 2471
-- S3: uye esitligi + tarih araligi
QUERY PLAN
`--SEARCH odunc USING COVERING INDEX odunc_bilesik (alis_tarihi>?)
8
VM-steps: 2402957

Altı ölçüm bir tabloya sığar. Sütun sırası (uye_id, alis_tarihi) iken S1 135 adım, S2 6.000.831 adım, S3 37 adım harcadı. Ters sırayla S1 6.000.101, S2 2.471, S3 2.402.957 oldu. Hiçbir sıra üç sorgunun üçünde birden kazanmıyor.

Nedeni tek bir yapısal olgudur. Bileşik dizin, girdileri önce birinci sütuna, o eşitken ikinci sütuna göre sıralar. Böyle bir sıra ancak bir giriş noktası verirse işe yarar ve giriş noktası hep baştan başlar.

Sol Ön Ek Kuralı

Kuralın adı sol ön ek kuralıdır (leftmost prefix rule): bir bileşik dizin, sütun listesinin yalnız soldan başlayan bir parçasına giriş noktası verir. (a, b, c) dizini a koşuluna, a ve b koşuluna, a, b ve c koşuluna yanıt verir; yalnız b koşuluna ya da yalnız b ile c koşuluna yanıt vermez.

Ölçümler bunu üç kez doğruluyor. S2 yalnız tarihi süzüyor: (uye_id, alis_tarihi) dizininde tarih ikinci sütun olduğu için giriş noktası yok, plan SCAN diyor. Aynı sorgu (alis_tarihi, uye_id) dizininde birinci sütunu süzdüğü için 2.471 adımda bitiyor.

S3 kuralın ikinci yüzünü gösterir. (uye_id, alis_tarihi) dizininde iki koşul da anahtara giriyor — plan bunu (uye_id=? AND alis_tarihi>?) yazarak söylüyor — ve iş 37 adımda bitiyor. Ters sırada ise yalnız tarih aralığı anahtar oluyor; motor 2022 sonrasındaki bütün kayıtları dizinden okuyup üye koşulunu tek tek sınıyor. Sonuç aynı sekiz satır, bedel 2,4 milyon adım.

Buradan sütun sırasını seçme kuralı çıkar: eşitlikle süzülen sütunlar başa, aralık ve sıralama sütunları sona. Eşitlik dizindeki konumu tek bir noktaya sabitler ve sonraki sütunun sırasını korur; aralık ise bir kez girildiğinde sonraki sütunların sırasını dağıtır. (uye_id, alis_tarihi) dizininde tarih sırası her üye için ayrı ayrı korunduğu için S1’de sıralama düğümü hiç oluşmadı.

Bir sütunun iki dizinde birden yer alması yasak değildir. Yukarıdaki üç sorguyu birlikte hızlandırmanın yolu iki bileşik dizin kurmaktır; bedeli, iki ağacın da her yazmada güncellenmesidir. Bu bedelin ölçüsü Dizin Bakımı dersinin konusudur.

Kısmi Dizin

İkinci gevşetme kapsamla ilgilidir. Kısmi dizin (partial index), tablonun yalnız bir koşulu sağlayan satırlarını içeren dizindir. Kütüphanede bunun karşılığı doğrudandır: ödünç kayıtlarının çoğu kapanmıştır, günlük işin sorduğu ise açık ödünçlerdir.

rm -f temel.db tam.db kismi.db
sqlite3 temel.db < kurulum.sql
cp temel.db tam.db
cp temel.db kismi.db
sqlite3 tam.db   'CREATE INDEX odunc_uye  ON odunc(uye_id);'
sqlite3 kismi.db 'CREATE INDEX odunc_acik ON odunc(uye_id) WHERE iade_tarihi IS NULL;'

echo "-- kapsanan satir sayisi --"
sqlite3 temel.db "SELECT count(*) AS tumu FROM odunc;
                  SELECT count(*) AS acik FROM odunc WHERE iade_tarihi IS NULL;"
echo "-- sayfa sayisi --"
for db in temel.db tam.db kismi.db; do
  printf '%-10s %s\n' "$db" "$(sqlite3 "$db" 'PRAGMA page_count;')"
done
for db in tam.db kismi.db; do
  printf '\n=== %s ===\n' "$db"
  sqlite3 "$db" <<'SQL'
.print '-- bir uyenin acik oduncleri'
EXPLAIN QUERY PLAN SELECT count(*) FROM odunc WHERE uye_id = 4 AND iade_tarihi IS NULL;
.stats vmstep
SELECT count(*) FROM odunc WHERE uye_id = 4 AND iade_tarihi IS NULL;
.stats off
.print '-- ayni uyenin butun oduncleri'
EXPLAIN QUERY PLAN SELECT count(*) FROM odunc WHERE uye_id = 4;
.stats vmstep
SELECT count(*) FROM odunc WHERE uye_id = 4;
SQL
done

-- kapsanan satir sayisi --
2000000
222222
-- sayfa sayisi --
temel.db   19078
tam.db     24832
kismi.db   19719

=== tam.db ===
-- bir uyenin acik oduncleri
QUERY PLAN
`--SEARCH odunc USING INDEX odunc_uye (uye_id=?)
6
VM-steps: 103
-- ayni uyenin butun oduncleri
QUERY PLAN
`--SEARCH odunc USING COVERING INDEX odunc_uye (uye_id=?)
17
VM-steps: 62

=== kismi.db ===
-- bir uyenin acik oduncleri
QUERY PLAN
`--SEARCH odunc USING INDEX odunc_acik (uye_id=?)
6
VM-steps: 36
-- ayni uyenin butun oduncleri
QUERY PLAN
`--SCAN odunc
17
VM-steps: 6000028

Boyut farkı dizinin kapsadığı satır oranını birebir izliyor. Tam dizin veritabanına 5.754 sayfa ekledi (24.832 − 19.078), kısmi dizin ise 641 sayfa (19.719 − 19.078). Oran 5754 / 641 ≈ 9,0; kapsanan satır oranı da 2.000.000 / 222.222 = 9,0. Kısmi dizin küçüktür çünkü az satır tutar — başka bir hüner yoktur.

Plan tarafında da kazanıyor. Açık ödünç sorgusunda tam dizin 103, kısmi dizin 36 adım harcadı. Kazanç iki kaynaktan gelir: kısmi dizinin ağacı daha kısadır ve dizinden gelen her girdi zaten koşulu sağladığı için tabloya dönülüp iade_tarihi denetlenmesi gerekmez.

Kısmi Dizinin Sınırı

İkinci ölçüm bedeli gösterir. Aynı üyenin bütün ödünçleri sorulduğunda kısmi dizin kullanılamadı ve sorgu tam tablo taramasına düştü: 6.000.028 adım. Bunun bir eksiklik değil tanım gereği olduğunu görmek gerekir — kısmi dizinde kapalı ödünçlerin girdisi hiç yoktur; kullanılsaydı yanlış cevap verirdi.

Planlayıcı kısmi dizini ancak sorgunun koşulu dizinin koşulunu gerektiriyorsa kullanır. Bu, uygulama tarafında somut bir yazım disiplini demektir: kısmi dizinden yararlanacak sorgu, dizinin koşulunu kendi WHERE yan tümcesinde taşımalıdır. Açık ödünçleri getiren sorgu iade_tarihi IS NULL koşulunu yazmıyorsa dizin devrede olmaz.

Kazanç yazma tarafında da vardır ve aynı orandan gelir: kapsanmayan satırların eklenmesi dizine hiç dokunmaz.

rm -f y_tam.db y_kismi.db
sqlite3 y_tam.db < kurulum.sql
cp y_tam.db y_kismi.db
sqlite3 y_tam.db   'CREATE INDEX odunc_uye  ON odunc(uye_id);'
sqlite3 y_kismi.db 'CREATE INDEX odunc_acik ON odunc(uye_id) WHERE iade_tarihi IS NULL;'
for db in y_tam.db y_kismi.db; do
  printf '%-11s ' "$db"
  sqlite3 "$db" <<'SQL'
.timer on
INSERT INTO odunc (kitap_id, uye_id, alis_tarihi, iade_tarihi)
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 200000)
SELECT 1 + ((n*7) % 200000), 1 + ((n*13) % 120000),
       date('2024-01-01','+'||(n%300)||' days'),
       date('2024-01-15','+'||(n%300)||' days')
FROM s;
SQL
done

y_tam.db    Run Time: real 0.200 user 0.144343 sys 0.045784
y_kismi.db  Run Time: real 0.085 user 0.076838 sys 0.006395

Eklenen iki yüz bin satırın hepsi iade edilmiş kayıt olduğu için kısmi dizine tek girdi bile yazılmadı; ekleme bu ortamda 2,4 kat kısa sürdü. Süre değerleri ortama bağlıdır ve başka bir makinede değişir; kararlı olan, aynı ortamdaki iki koşumun oranıdır.

Kısmi dizinin doğal kullanım alanı buradan çıkar: dağılımı çok dengesiz olan ve yalnız küçük tarafı sorgulanan sütunlar. Açık ödünçler, iptal edilmemiş kayıtlar, işlenmemiş kuyruk satırları, boş olmayan alanlar. Bunların tersi de doğrudur: sorgular kapsamın her iki tarafını da soruyorsa kısmi dizin yanıltıcı bir tasarruftur, çünkü ikinci bir tam dizin gerekecektir.

Özet

• Bileşik dizin girdileri önce birinci sütuna göre sıralar; bu yüzden yalnız soldan başlayan sütun parçalarına giriş noktası verir — sol ön ek kuralı.
• Aynı iki sütunun iki sırası üç sorguda üç ayrı sonuç verdi: hiçbir sıra üçünde birden kazanmadı, sıra bir sorgu kümesi seçimidir.
• Sütun sırası seçiminde eşitlikle süzülen sütunlar başa, aralık ve sıralama sütunları sona konur; aralık koşulu kendisinden sonraki sütunların sırasını dağıtır.
• Kısmi dizin yalnız koşulu sağlayan satırları tutar; ölçümde tam dizin 5.754 sayfa eklerken kısmi dizin 641 sayfa ekledi ve oran kapsanan satır oranını birebir izledi.
• Kısmi dizin ancak sorgunun koşulu dizinin koşulunu gerektirdiğinde kullanılır; kapsam dışı sorgu tam tablo taramasına düşer ve kapsanmayan satırların yazımı dizine hiç dokunmaz.

Sonraki Adım

Bu derste bir plan satırı iki kez COVERING sözcüğüyle çıktı, bir kez çıkmadı. Fark sessiz görünüyordu ama sayıya yansıdı: aynı dizin, aynı üye, biri 62 diğeri 103 adım. Aradaki iş, dizinden bulunan her girdi için tabloya dönmektir. Sonraki ders bu dönüşü ölçer ve ortadan kaldırmanın yolunu kurar: dizine sorgunun istediği bütün sütunları koymak. Kazancın eşleşen satır sayısıyla nasıl büyüdüğü, hangi sütunların dizine eklenmeye değdiği ve bu yaklaşımın nerede kendi bedelini aştığı ölçümle görülecek.