Kapsayan Dizinler

Önceki dersin son ölçümünde aynı dizin, aynı üye ve aynı sorgu biçimi iki ayrı sayı verdi: 62 adım ve 103 adım. Aradaki tek fark, planın birinde COVERING sözcüğünün bulunması, diğerinde bulunmamasıydı.

O sözcük tek bir işi anlatır. Dizin, sorgunun istediği sütunların hepsini taşıyorsa veritabanı yanıtı doğrudan dizinden üretir. Taşımıyorsa, dizinde bulunan her girdi için tabloya dönüp eksik sütunu okumak zorundadır. Bu ders o dönüşün ne kadar pahalı olduğunu ölçer — ve ölçünün hangi araçla yapılacağının kendisi de bir bulgu üretir.

Dönüşün İzi

Ölçümler kütüphane ödünç kayıtları üzerinde yapılır. Aylık bir rapor sorusu seçilmiştir: bir ay içinde ödünç alınan kaç ayrı kitap var? Sorgu iki sütuna dokunur — alis_tarihi süzme için, kitap_id sayım için.

rm -f temel.db dar.db kapsayan.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 temel.db < kurulum.sql
cp temel.db dar.db
cp temel.db kapsayan.db
sqlite3 dar.db      'CREATE INDEX odunc_alis       ON odunc(alis_tarihi);'
sqlite3 kapsayan.db 'CREATE INDEX odunc_alis_kitap ON odunc(alis_tarihi, kitap_id);'

echo "-- sayfa sayisi --"
for db in temel.db dar.db kapsayan.db; do
  printf '%-13s %s\n' "$db" "$(sqlite3 "$db" 'PRAGMA page_count;')"
done
for db in dar.db kapsayan.db; do
  printf '\n=== %s ===\n' "$db"
  sqlite3 "$db" <<'SQL'
EXPLAIN QUERY PLAN SELECT count(DISTINCT kitap_id) FROM odunc
  WHERE alis_tarihi BETWEEN '2021-03-01' AND '2021-03-31';
.stats vmstep
SELECT count(DISTINCT kitap_id) FROM odunc
  WHERE alis_tarihi BETWEEN '2021-03-01' AND '2021-03-31';
SQL
done

-- sayfa sayisi --
temel.db      19078
dar.db        28424
kapsayan.db   30311

=== dar.db ===
QUERY PLAN
|--USE TEMP B-TREE FOR count(DISTINCT)
`--SEARCH odunc USING INDEX odunc_alis (alis_tarihi>? AND alis_tarihi<?)
25441
VM-steps: 203543

=== kapsayan.db ===
QUERY PLAN
|--USE TEMP B-TREE FOR count(DISTINCT)
`--SEARCH odunc USING COVERING INDEX odunc_alis_kitap (alis_tarihi>? AND alis_tarihi<?)
25441
VM-steps: 178101

Plan farkı beklendiği gibi: ikinci dizin kitap_id sütununu da taşıdığı için plan COVERING INDEX diyor. Boyut farkı da beklendiği gibi: kapsayan dizin bir sütun fazla taşıdığı için veritabanına 1.887 sayfa daha ekledi.

Adım sayısı ise beklentiyi boşa çıkarıyor. 203.543’ten 178.101’e, yalnızca yüzde on iki. Yirmi beş bin satır için yirmi beş bin tablo dönüşünün maliyeti bu mudur?

Doğru Ölçü

Adım sayısı, sorgunun yürüttüğü sanal makine komutlarını sayar. Tablodan bir satır okumak tek bir komuttur — o komutun arkasında bir disk sayfasının bulunup okunması yatar ama sayaç bunu görmez. Bir başka deyişle: adım sayısı yapılan işlemleri sayar, dokunulan sayfaları değil.

İşlemci Önbelleği dersinde kurulan ayrım burada geri gelir. Aynı sayıda komut, verinin nerede olduğuna göre yüz kat farklı sürebilir. Ölçünün değiştirilmesi gerekir: sayfa ıskası sayısı. Aşağıdaki koşum aynı sorguyu üç ayrı genişlikte çalıştırır ve her koşum için hem sayfa ıskasını hem geçen süreyi yazar. Her sorgu ayrı bir süreçte çalışır, bu yüzden sayaçlar soğuk önbellekten başlar.

echo "-- eslesen satir sayilari --"
sqlite3 temel.db "SELECT '1 gun', count(*) FROM odunc WHERE alis_tarihi BETWEEN '2021-03-15' AND '2021-03-15'
UNION ALL SELECT '1 ay', count(*) FROM odunc WHERE alis_tarihi BETWEEN '2021-03-01' AND '2021-03-31'
UNION ALL SELECT '1 yil', count(*) FROM odunc WHERE alis_tarihi BETWEEN '2021-01-01' AND '2021-12-31';"

for aralik in "2021-03-15 2021-03-15" "2021-03-01 2021-03-31" "2021-01-01 2021-12-31"; do
  bas=${aralik% *}; bit=${aralik#* }
  printf '\n### %s .. %s\n' "$bas" "$bit"
  for db in dar.db kapsayan.db; do
    printf '%-13s ' "$db"
    sqlite3 "$db" <<SQL 2>&1 | grep -E 'Page cache misses|Run Time' | tr '\n' ' '
.stats on
.timer on
SELECT count(DISTINCT kitap_id) FROM odunc WHERE alis_tarihi BETWEEN '$bas' AND '$bit';
SQL
    echo
  done
done

-- eslesen satir sayilari --
1 gun|820
1 ay|25441
1 yil|299547

### 2021-03-15 .. 2021-03-15
dar.db        Page cache misses:                   874 Run Time: real 0.001 user 0.000626 sys 0.000896 
kapsayan.db   Page cache misses:                   8 Run Time: real 0.000 user 0.000136 sys 0.000042 

### 2021-03-01 .. 2021-03-31
dar.db        Page cache misses:                   26241 Run Time: real 0.034 user 0.017126 sys 0.016881 
kapsayan.db   Page cache misses:                   147 Run Time: real 0.005 user 0.005101 sys 0.000187 

### 2021-01-01 .. 2021-12-31
dar.db        Page cache misses:                   309414 Run Time: real 0.372 user 0.204850 sys 0.166556 
kapsayan.db   Page cache misses:                   1686 Run Time: real 0.060 user 0.057790 sys 0.002153 

Sayılar tek bir örüntüyü gösteriyor. Dar dizinde sayfa ıskası sayısı, eşleşen satır sayısını yaklaşık birebir izliyor: 820 satır için 874 sayfa, 25.441 satır için 26.241 sayfa, 299.547 satır için 309.414 sayfa. Kapsayan dizinde aynı üç sayı 8, 147 ve 1.686.

Oranın kaynağı fiziksel depolama düzenidir. Dizin, tarihe göre sıralı olduğu için eşleşen girdiler yan yanadır ve bir sayfa okuması yüzlerce girdi getirir. Tabloya dönüş ise odunc_id sırasına göre dizilmiş bir yapıda rastgele noktalara gitmektir; art arda gelen iki dizin girdisinin satırları tabloda birbirinden uzaktır. Her satır için ayrı bir sayfa okunur, aynı sayfa birden çok kez okunur ve tampon havuzu bu erişimi tutamaz.

Süre bunu doğruluyor: yıllık sorguda 0,372 saniyeye karşı 0,060 saniye, altı kat. Süreler ortama bağlıdır ve başka bir makinede değişir; kararlı olan, sayfa ıskası oranıdır — yıllık sorguda 309.414 / 1.686 ≈ 184.

Buradan ölçüm disiplininin bir kuralı çıkar: bir plan değişikliğinin etkisi değerlendirilirken, ölçünün değişen işi görüyor olması gerekir. Adım sayısı sorgunun mantığını iyi ölçer, disk erişimini ölçmez.

Kapsamanın Sınırı

Kapsayan dizin bedelsiz değildir. Dizine konan her sütun, iki milyon girdinin her birinde tekrarlanır. Aşağıdaki ölçüm aynı dizini dört ayrı genişlikte kurar ve her birinin kapladığı sayfa sayısını tablonun kendisiyle karşılaştırır.

rm -f genislik.db
sqlite3 genislik.db < kurulum.sql
sqlite3 genislik.db <<'SQL'
.mode column
.headers on
CREATE INDEX d1 ON odunc(alis_tarihi);
CREATE INDEX d2 ON odunc(alis_tarihi, kitap_id);
CREATE INDEX d3 ON odunc(alis_tarihi, kitap_id, uye_id);
CREATE INDEX d4 ON odunc(alis_tarihi, kitap_id, uye_id, iade_tarihi);
SELECT name AS nesne, count(*) AS sayfa FROM dbstat
WHERE name IN ('odunc','d1','d2','d3','d4') GROUP BY name ORDER BY sayfa;
SQL

nesne  sayfa
-----  -----
d1     9346 
d2     11233
d3     13089
d4     17968
odunc  18013

Dört sütunlu dizin 17.968 sayfa; tablonun kendisi 18.013 sayfa. Sorgunun istediği her sütun dizine eklendiğinde dizin, tablonun sıralanmış bir kopyası hâline gelir. O noktada kapsama artık bir eniyileme değil, verinin iki kez saklanmasıdır: yer iki katına çıkar, her yazma iki yapıya birden gider ve yedeğin boyutu büyür.

Karar ölçütü buradan çıkar. Kapsamaya değen sütunlar, sorgunun sonucunda geçen ama tablonun geri kalanına göre dar olan sütunlardır. Bir sayım için gereken tek bir kimlik sütununu eklemek 1.887 sayfa ödeyip 184 kat sayfa ıskası kazandırdı; uzun bir metin sütununu eklemek aynı hesabı ters çevirir.

İkinci ölçüt sorgunun genişliğidir. Bir gün süzen sorguda kazanç 874 sayfadan 8 sayfaya — mutlak değeri küçük bir tasarruf. Aynı dizin yıllık raporda üç yüz bin sayfa okumayı engelledi. Kapsayan dizin, çok satır eşleştiren ve az sütun isteyen sorgular için kurulur; tek satır getiren aramalarda kurulmasına gerek yoktur, çünkü orada dönüş zaten tek sayfadır.

Kapsama ve Sıra Birlikte

Kapsayan dizinin sütun listesi iki işi birden yapar ve bu iki iş çakışabilir. Önceki derste kurulan sol ön ek kuralı süzme ve sıralama için sütun sırasını belirliyordu; kapsama ise yalnız sütunun var olmasını ister, sırasını değil.

İki gereksinim bir listede toplanır: süzme ve sıralama sütunları sırası önemli olacak biçimde başa, yalnız sonuçta geçtiği için eklenen sütunlar sona. (alis_tarihi, kitap_id) dizini tam olarak budur — tarih giriş noktasını verir, kitap kimliği yalnız taşınır. Ters sıra, (kitap_id, alis_tarihi), aynı sütunları taşır ve aynı yeri kaplar ama tarih aralığına giriş noktası vermez.

Bazı motorlar bu ayrımı sözdizimine taşır ve yalnız taşınacak sütunları dizin anahtarının dışında tutan bir yazım sunar; böyle bir sütun benzersizlik denetimine katılmaz ve sıralamada yer tutmaz. Bu yazımın adı ve varlığı motora özgüdür; kavram aynıdır — anahtar olan sütunlarla yalnız taşınan sütunların ayrılması.

Özet

• Kapsayan dizin, sorgunun istediği bütün sütunları taşıyan dizindir; plan çıktısında COVERING sözcüğüyle görünür ve tabloya hiç dönülmediğini bildirir.
• Tabloya dönüşün maliyeti adım sayısında görünmez: aylık sorguda adım sayısı yüzde on iki düşerken sayfa ıskası 26.241’den 147’ye indi.
• Sayfa ıskası dar dizinde eşleşen satır sayısını birebir izler, çünkü tabloya dönüş rastgele erişimdir; kapsayan dizinde okuma dizin içinde sıralı ilerler.
• Kazanç eşleşen satır sayısıyla büyür: bir günlük sorguda 874 sayfaya karşı 8 sayfa, yıllık sorguda 309.414 sayfaya karşı 1.686 sayfa.
• Dizine sütun eklendikçe dizin tablonun kopyasına yaklaşır; dört sütunlu dizin 17.968 sayfa, tablonun kendisi 18.013 sayfa oldu.

Sonraki Adım

Buraya kadarki üç ders dizini bir kazanç olarak ele aldı ve bedelini yalnız kurulduğu andaki yerle ölçtü. Dizin kurulduğu anda kalmaz: satırlar silindikçe ve güncellendikçe dizin ağacında boşluklar birikir, dosya büyür, her yeni dizin yazma yolunu bir kat daha uzatır. Sonraki ders bu tarafı ölçer — silme sonrası dizinin ne kadar şiştiği, yeniden oluşturmanın neyi geri kazandırdığı ve tabloya eklenen her dizinin ekleme süresini ne kadar uzattığı.