Dizin Kavramı

İşlemler konusu, veritabanının doğru cevabı vermesi için gereken düzeni tamamladı: kesinleştirme sınırları, yalıtım düzeyleri, kilitler ve tetikleyicilerin örtük yan etkileri. O konunun sonunda elde kalan şey, doğru sonucu veren bir sorgudur.

Bu ders aynı sorguyu ikinci kez sormaz. Sorduğu şey şudur: veritabanı o doğru sonucu verirken kaç satıra baktı? İki milyon satırlık bir tabloda tek bir üyenin kayıtlarını isteyen sorgu, doğru cevabı iki milyon satırı okuyarak da verebilir, altmış kadar adımda da verebilir. İkisi arasındaki fark, sorgunun yazımında değil, verinin nasıl düzenlendiğindedir.

Ölçülebilir Bir Veri Kümesi

Başarım iddiaları küçük tablolarda görünmez: yüz satırlık bir tabloda her yol hızlıdır. Ölçümün gürültünün üstüne çıkması için tablo yeterince büyük olmalıdır. Aşağıdaki betik, kütüphane ödünç kayıtlarından oluşan bir veri kümesi kurar. Satırlar özyinelemeli bir ortak tablo ifadesiyle üretilir; dışarıdan hiçbir dosya gerekmez.

-- kurulum.sql — kutuphane veri kumesi
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;

Betik kurulum.sql adıyla kaydedilip çalıştırılır. Bu konudaki bütün ölçümler bu veri kümesi üzerinde yapılır.

rm -f kutuphane.db
sqlite3 kutuphane.db < kurulum.sql
sqlite3 kutuphane.db "SELECT 'uye', count(*) FROM uye
  UNION ALL SELECT 'kitap', count(*) FROM kitap
  UNION ALL SELECT 'odunc', count(*) FROM odunc;"

uye|120000
kitap|200000
odunc|2000000

Aramanın Varsayılan Maliyeti

Tek bir üyenin ödünç kayıtları soruluyor. Veritabanı bu sorguyu nasıl karşılıyor? Sorgu planı (query plan), sorgunun hangi adımlarla yürütüleceğini gösteren ağaçtır; komut satırından EXPLAIN QUERY PLAN ön ekiyle istenir. Ölçüm için iki araç daha kullanılır: .timer on geçen süreyi, .stats vmstep sorgunun harcadığı sanal makine adımı sayısını yazar.

sqlite3 kutuphane.db <<'SQL'
EXPLAIN QUERY PLAN SELECT odunc_id, alis_tarihi FROM odunc WHERE uye_id = 4242;
.timer on
.stats vmstep
SELECT count(*) FROM odunc WHERE uye_id = 4242;
SELECT count(*) FROM odunc WHERE uye_id = 4242;
SELECT count(*) FROM odunc WHERE uye_id = 4242;
SQL

QUERY PLAN
`--SCAN odunc
17
VM-steps: 6000028
Run Time: real 0.036 user 0.028072 sys 0.007521
17
VM-steps: 6000028
Run Time: real 0.036 user 0.028525 sys 0.007273
17
VM-steps: 6000028
Run Time: real 0.036 user 0.028689 sys 0.007418

Planın tek düğümü var: SCAN odunc. Bu, tam tablo taraması (full table scan) demektir — tablodaki her satır okunur, koşul her satır için ayrı ayrı sınanır. On yedi satır döndürmek için iki milyon satır ziyaret edilmiştir.

İki ölçü birlikte okunmalıdır. Süre ortama bağlıdır: aynı sorgu daha hızlı bir diskte ya da daha yüklü bir makinede farklı çıkar; bu yüzden süreye mutlak bir değer olarak değil, aynı ortamdaki başka bir süreyle oranı üzerinden bakılır. Adım sayısı ise ortamdan bağımsızdır: aynı veri ve aynı plan her makinede aynı adım sayısını verir. Altı milyon adımın kaynağı da bellidir — iki milyon satırın her biri için ortalama üç sanal makine komutu.

Bu maliyet tablo büyüklüğüyle doğru orantılıdır. Ödünç sayısı ikiye katlanırsa tarama da ikiye katlanır: $O(n)$. Algoritmalar kursundaki Doğrusal Arama dersinin sonucudur bu; tek fark, dizinin diskte olmasıdır.

Dizin Nedir

Dizin (index), bir sütunun değerlerini sıralı tutan ve her değerin hangi satıra ait olduğunu kaydeden ayrı bir yapıdır. Tablo verisi yerinde kalır; dizin, o veriye ikinci bir erişim yolu açar.

Kütüphane benzetmesi doğrudan çalışır: raflardaki kitaplar bir düzene göre dizilidir, ancak kataloğu olmayan bir kütüphanede belli bir yazarın kitaplarını bulmanın yolu bütün rafları gezmektir. Katalog fişleri yazar adına göre sıralanmış ayrı bir kutuda durur ve her fiş bir raf numarası taşır. Fiş kutusunda arama, kutunun ortasını açıp yönü belirleyerek ilerler.

İlişkisel veritabanlarında bu kutunun karşılığı çoğunlukla bir B-ağacıdır (B-tree). Veri Yapıları kursunda B-Ağaçları dersinde kurulan yapı budur: her düğüm bir disk sayfasına sığacak kadar geniştir, ağaç dengelidir ve yüksekliği kayıt sayısının logaritmasıyla artar. Bir anahtarı bulmak için kökten yaprağa inmek gerekir; iki milyon kayıtlı bir dizide bu, birkaç sayfanın okunması demektir. Tablo on kat büyüdüğünde tarama on kat pahalılaşır, ağaçta inilen düzey sayısı ise bir artar.

Dizinin Ölçülen Etkisi

Aynı sorgu, uye_id üzerinde dizin varken tekrarlanır.

sqlite3 kutuphane.db <<'SQL'
.timer on
CREATE INDEX odunc_uye ON odunc(uye_id);
.timer off
EXPLAIN QUERY PLAN SELECT odunc_id, alis_tarihi FROM odunc WHERE uye_id = 4242;
.timer on
.stats vmstep
SELECT count(*) FROM odunc WHERE uye_id = 4242;
SELECT count(*) FROM odunc WHERE uye_id = 4242;
SELECT count(*) FROM odunc WHERE uye_id = 4242;
SQL

Run Time: real 0.263 user 0.219940 sys 0.036873
QUERY PLAN
`--SEARCH odunc USING INDEX odunc_uye (uye_id=?)
17
VM-steps: 62
Run Time: real 0.000 user 0.000016 sys 0.000012
17
VM-steps: 62
Run Time: real 0.000 user 0.000007 sys 0.000004
17
VM-steps: 62
Run Time: real 0.000 user 0.000005 sys 0.000004

Plan düğümü SCAN iken SEARCH ... USING INDEX oldu. Okunacak olan budur: veritabanı artık tabloyu baştan sona okumuyor, dizinden uye_id = 4242 anahtarına iniyor ve yalnız oradaki satırlara bakıyor.

Adım sayısı 6.000.028’den 62’ye indi — yaklaşık yüz bin kat. Süre ise ölçülemez oldu: 0.000 değeri “sıfır süre” demek değil, zamanlayıcının çözünürlüğünün altında kalmak demektir. Bu, ölçüm disiplininin ilk kuralını hatırlatır: bir yol yeterince ucuzladığında süre bilgi vermeyi bırakır, ölçülmesi gereken şey yapılan iştir. Dizinin oluşturulması da bedava değildir; iki milyon satırın sıralanması bu ortamda çeyrek saniye sürmüştür.

Dizinin Bedeli

Dizin, okumayı ucuzlatırken iki yerde pahalılaştırır: yer ve yazma. Aşağıdaki ölçüm aynı veri kümesinin iki kopyasına aynı iki yüz bin satırı ekler; kopyaların biri dizinsiz, diğeri odunc üzerinde üç dizinlidir.

rm -f dizinsiz.db dizinli.db
sqlite3 dizinsiz.db < kurulum.sql
cp dizinsiz.db dizinli.db
sqlite3 dizinli.db 'CREATE INDEX o_uye ON odunc(uye_id);
CREATE INDEX o_kitap ON odunc(kitap_id);
CREATE INDEX o_alis ON odunc(alis_tarihi);'

for db in dizinsiz.db dizinli.db; do
  printf '%s ' "$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'), NULL
FROM s;
SQL
done
ls -l dizinsiz.db dizinli.db | awk '{print $9, $5}'

dizinsiz.db Run Time: real 0.060 user 0.055046 sys 0.003094
dizinli.db Run Time: real 0.397 user 0.289750 sys 0.095673
dizinli.db 191856640
dizinsiz.db 91119616

Aynı ekleme üç dizin varken bu ortamda altı buçuk kat uzun sürdü ve dosya iki katından fazla büyüdü. Nedeni doğrudan: eklenen her satır için üç ayrı ağaca da bir anahtar yazılır ve o ağaçların dengesi korunur. Silme ve anahtar sütunu güncelleyen UPDATE için de aynı bedel geçerlidir. Dizin bu yüzden “eklenince iyi olur” türü bir seçenek değil, okuma ile yazma arasında bilinçli bir ödünleşimdir.

Seçicilik

Her sütuna dizin açmak, bedeli çoğaltmanın yanı sıra çoğu zaman kazandırmaz da. Belirleyen ölçü seçiciliktir (selectivity): bir koşulun tablonun ne kadar küçük bir bölümünü seçtiği. kitap tablosunda sube_id sekiz farklı değer alır, yazar ise dört bin. Aşağıdaki ölçüm aynı sorgu biçimini iki sütun için, dizinsiz ve dizinli olarak çalıştırır.

rm -f secicilik.db
sqlite3 secicilik.db < kurulum.sql

echo "dizinsiz:"
sqlite3 secicilik.db <<'SQL'
.stats vmstep
SELECT sum(yil) FROM kitap WHERE sube_id = 3;
SELECT sum(yil) FROM kitap WHERE yazar = 'Yazar 7';
SQL

sqlite3 secicilik.db 'CREATE INDEX kitap_sube ON kitap(sube_id);
CREATE INDEX kitap_yazar ON kitap(yazar);'

echo "dizinli:"
sqlite3 secicilik.db <<'SQL'
.stats vmstep
SELECT sum(yil) FROM kitap WHERE sube_id = 3;
SELECT sum(yil) FROM kitap WHERE yazar = 'Yazar 7';
SQL

dizinsiz:
49674950
VM-steps: 650011
99075
VM-steps: 600111
dizinli:
49674950
VM-steps: 125012
99075
VM-steps: 262

Yazar koşulu iki bin üç yüz kat ucuzladı; şube koşulu yalnızca beş kat. Ayrım seçicilikten geliyor: yazar = 'Yazar 7' iki yüz bin kitabın ellisini, sube_id = 3 ise yirmi beş binini seçiyor. İkinci durumda veritabanı yirmi beş bin dizin girdisini okuduktan sonra yirmi beş bin satırı ayrıca tablodan almak zorunda; bu iş, tabloyu sırayla okumaktan çok da ucuz değil. Seçiciliği düşük bir sütuna açılan dizin, yazma bedelini öder ama okuma tarafında karşılığını vermez.

Özet

• Dizinsiz bir sütun üzerindeki koşul tam tablo taramasıyla karşılanır; maliyet satır sayısıyla doğru orantılıdır.
• Dizin, sütun değerlerini sıralı tutan ayrı bir yapıdır; B-ağacı biçimindeki bir dizinde arama maliyeti satır sayısının logaritmasıyla artar.
• Aynı sorgu bu veri kümesinde 6.000.028 adımdan 62 adıma indi; süre zamanlayıcının çözünürlüğünün altına düştüğü için ölçü olarak adım sayısı kullanıldı.
• Dizin yer kaplar ve her ekleme, silme ve anahtar güncellemesini pahalılaştırır; üç dizinli tabloya ekleme bu ortamda altı buçuk kat uzun sürdü.
• Kazanç seçicilikle belirlenir: az sayıda satır seçen koşullarda dizin büyük kazandırır, tablonun büyük bölümünü seçen koşullarda kazanç kaybolur.

Sonraki Adım

Bu derste plan çıktısına iki kez bakıldı ve iki kelime ayırt edildi: SCAN ve SEARCH. Gerçek sorgular tek düğümlü değildir — birleştirmeler, sıralamalar, gruplamalar ve alt sorgular planı çok satırlı bir ağaca dönüştürür. Sonraki ders bu ağacı okumayı ele alır: düğümlerin hangi sırada çalıştığı, hangi düğümün hangi tabloyu sürdüğü ve sıralamanın plana nasıl yansıdığı. Plan çıktısının biçimi motordan motora değişir; okunacak olan biçim değil, plandaki karardır.