Veritabanı yönetim sistemlerinde Cost-Based Optimization (CBO), sorgu planlarını değerlendirmek ve en verimli olanı seçmek için nicel bir temel sağlayan matematiksel bir çerçevedir. Bu modelin kalbinde, her bir olası sorgu yürütme planına (execution plan) sayısal bir “maliyet” değeri atama fikri yatar. Optimizatör, maliyeti minimize edecek planı seçer. Bu maliyet, disk I/O, CPU tüketimi, bellek kullanımı ve ağ band genişliği gibi kaynakların tahmini tüketimini sentezleyen soyut bir birimdir. Gerçek fiziksel birimlerle (örn. milisaniye) doğrudan ilişkili olmamasına rağmen, sistem mimaisinin göreceli performansını doğru bir şekilde modellemelidir.
Maliyet modeli, bir dönüştürme faktörü görevi görerek, farklı fiziksel operatörlerin ve algoritmaların çeşitli bağlamlardaki göreceli “ağırlığını” hesaplar. Örneğin, bir model, rastgele bir disk erişiminin sıralı bir disk erişiminden kat kat daha maliyetli olduğunu varsayabilir. Bu tür varsayımlar, temel donanım ve veri düzeninin anlaşılmasına dayanır. Modern sistemlerde, bu modeller genellikle donanım parametrelerine ve veritabanı yapılandırmasına göre kalibre edilebilir, böylece farklı ortamlara uyum sağlanır. Optimizatörün doğruluğu, bu modelin karmaşıklığı ile yakından ilişkilidir.
Bir maliyet fonksiyonu, genellikle bileşenlerin ağırlıklı toplamı şeklinde ifade edilir: C_total = w_io * N_io + w_cpu * N_cpu + w_mem * N_mem. Burada w ağırlık katsayılarını, N ise ilgili kaynak için tahmini işlem sayısını (örn. okunan sayfa sayısı) temsil eder. Ağırlıkların belirlenmesi, benchmarking ve sistem profilleme ile yapılır.
- CPU Maliyeti: Karşılaştırma, toplama, hash hesaplama gibi işlemler için tahmini CPU döngüsü.
- G/Ç Maliyeti: Diskten okunan veya diske yazılan veri sayfası (page) miktarı.
- Bellek Maliyeti: Ara sonuçlar için gereken geçici tampon alanı.
- Ağ Maliyeti (dağıtık sistemlerde): Düğümler arası aktarılan veri miktarı.
Bu modele dayalı optimizasyon, heuristik (kural tabanlı) yaklaşımların aksine, dinamik ve veriye bağlı bir karar sürecine olanak tanır. Sorgunun karmaşıklığı arttıkça, farklı planların maliyetleri arasındaki fark da büyüyebilir ve CBO'nun sistematik üstünlüğü belirginleşir.
İstatistikler ve Seçicilik
Maliyet modelinin doğru tahminlerde bulunabilmesi, veritabanı sistem kataloğunda saklanan istatistiksel meta-verilere bağımlıdır. Bu istatistikler, tabloların ve indekslerin mevcut durumuna dair nicel bir profil çıkarır. En temel istatistikler arasında kardinalite (satır sayısı), belirli bir sütundaki farklı değer sayısı (NDV - number of distinct values), ve sütun değerlerinin histogramları bulunur. Histogramlar, veri dağılımının düzgün olmadığı durumlarda seçiciliğin çok daha doğru hesaplanmasını sağlayan kritik veri yapılarıdır.
Bir sorgu yükleminin (predicate) seçiciliği (selectivity), yüklemi sağlayacak tahmini satır oranını ifade eder ve 0 ile 1 arasında bir değerdir. Seçicilik tahmini, maliyet modelinin en hassas ve en zorlu parçalarından biridir. Eşitlik yüklemleri (`sütun = değer`) için, genellikle 1/NDV basit varsayımı kullanılırken, aralık yüklemleri (`sütun > değer`) için histogramlara başvurulur. Yanlış bir seçicilik tahmini, operatör maliyetlerinin katlanarak yanlış hesaplanmasına ve dolayısıyla optimal olmayan bir plan seçimine yol açabilir.
Çoklu sütunlar üzerindeki yüklemler için seçicilik tahmini daha da karmaşıklaşır. Basit ve yaygın bir yaklaşım, sütunların bağımsız olduğu varsayımıyla seçicilikleri çarpmaktır. Ancak bu, gerçek verideki fonksiyonel bağımlılıklar veya korelasyonlar olduğunda ciddi hatalara sebep olur. Gelişmiş sistemler, çok değişkenli istatistikler veya sıkıştırılmış istatistikler (örneğin, en sık kullanılan değerlerin listesi) tutarak bu sorunu hafifletmeye çalışır.
İstatistiklerin zaman içinde geçersiz hale gelmesi (statistics staleness) büyük bir sorundur. Yoğun ekleme/silme/güncelleme aktivitesi olan tablolarda, eski istatistiklere dayanan tahminler güvenilmez olacaktır. Bu nedenle, veritabanı yöneticileri düzenli istatistik güncelleme (ANALYZE) işlemlerini planlamalı veya sistemin otomatik güncelleme özelliklerini kullanmalıdır. Modern veritabanları, örnekleme (sampling) teknikleriyle tam tablo taraması yapmadan hızlı ve yeterince doğru istatistikler üretebilmektedir.
Seçicilik, birleştirme (join) işlemlerinin çıktı büyüklüğünü tahmin etmede de merkezi bir role sahiptir. İki tablonun kartezyen çarpımının boyutu |R| * |S| iken, bir birleştirme yüklemi uygulandığında bu değer bir seçicilik faktörü ile çarpılır. Örneğin, eşitlik birleştirmesi (equijoin) için, birleştirme sütunlarındaki ortak değerlerin dağılımına bağlı olarak karmaşık formüller kullanılır. Bu tahminlerdeki hata, birleştirme sırasının (join order) yanlış belirlenmesine neden olarak performansı dramatik şekilde düşürebilir.
Fiziksel Operatörler ve Maliyetler
Maliyet modelinin uygulanması, her bir temel veri erişim ve işleme operatörü için ayrıntılı maliyet formüllerinin tanımlanmasını gerektirir. Bu fiziksel operatörler, sorgu plan ağacının yaprakları ve düğümleridir. Optimizatör, belirli bir mantıksal işlemi (örn., birleştirme) gerçekleştirmek için birden fazla fiziksel operatör arasından seçim yapabilir. Örneğin, bir birleştirme işlemi için Nested Loops, Hash Join veya Merge Join algoritmaları kullanılabilir. Her algoritmanın maliyet profili, girdi verisinin boyutu, bellek durumu ve indeks varlığı gibi faktörlere bağlı olarak radikal biçimde farklılık gösterir.
Temel tarama operatörlerinin maliyeti, erişim yoluna (access path) göre değişir. Tam tablo taraması (Table Scan), tablonun disk üzerindeki tüm sayfalarının sıralı okunması maliyetine sahiptir. Buna karşılık, bir indeks taraması (Index Scan) daha düşük bir I/O maliyeti taşır, ancak bu maliyet seçiciliğe ve indeksin fiziksel düzenine bağlıdır. Çok seçici bir yüklem için, yalnızca birkaç indeks yaprağı okunurken, seçiciliği düşük bir yüklemde indeksin önemli bir kısmı taranabilir. İndeksli erişimde ayrıca, indeksten alınan her RowID için tablo veri bloklarına yapılan ek rastgele erişimlerin (row lookups) maliyeti de hesaba katılmalıdır. Bu, optimizatörün indeks kullanımının ne zaman faydalı olacağına karar vermesinde kritik bir dengedir.
Sıralama (Sort) ve gruplama (Hash Aggregate) gibi operatörlerin maliyeti, ara sonuçların bellek sığmasına veya sığmamasına göre katlanarak artar. Belirtilen sıralama boyutu çalışma belleğini aşarsa, algoritma dış birleştirmeli sıralamaya (external merge sort) geçer ve bu da ek disk I/O'su anlamına gelir. Maliyet modeli, bu "dışa taşma" (spill) durumunu tahmin etmek için bellek boyutu ve veri dağılımı hakkında varsayımlarda bulunur.
| Fiziksel Operatör | Ana Maliyet Bileşenleri | Maliyetin Ölçeklenmesi |
|---|---|---|
| Nested Loops Join | Dış döngü tarama maliyeti + (Dış satır sayısı * İç tarama maliyeti) | O(N*M); iç taramada indeks varsa O(N*logM) |
| Hash Join | Build aşaması (küçük tabloyu hashle) + Probe aşaması tarama maliyeti. Bellek taşması durumunda ek I/O. | O(N+M); en iyi durumda doğrusal. |
| Merge Join | Her iki girdinin sıralanma maliyeti + birleştirilmiş sıralı listelerin birleştirilmesi. | O(N*logN + M*logM); girdiler sıralıysa O(N+M). |
| Index Scan | İndeks yaprakları tarama maliyeti + Tablo veri bloklarına yapılan RowID erişimleri (fetch) maliyeti. | Seçicilik ve indeks seçiciliği ile değişir. |
Operatör maliyetlerinin hesaplanması, derin bir sistem mühendisliği bilgisi gerektirir. Örneğin, bir Hash Join'de hash tablosunu oluşturmak (build phase) için gereken bellek, sütun genişliğine ve tahmini farklı değer sayısına bağlıdır. Maliyet fonksiyonu, bu bellek ihtiyacını çalışma belleği (work_mem) ile karşılaştırarak diske taşma ihtimalini ve bunun getireceği ek gecikmeyi tahmin etmeye çalışır. Bu tür detaylı modelleme, CBO'yu sezgisel yöntemlerden ayıran temel unsurdur.
- Tarama Maliyetleri: Seq Scan, Index Scan, Index Only Scan, Bitmap Heap Scan.
- Birleştirme Maliyetleri: Nested Loops, Hash Join, Merge Join. Her birinin tercih edildiği veri boyutu ve bellek koşulu farklıdır.
- Sıralama ve Gruplama Maliyetleri: Explicit Sort, Hash Aggregate, Group Aggregate. Bellek taşması durumunda performans düşüşü katlanır.
- Yardımcı Operatör Maliyetleri: Limit, Materialize, Unique. Bu operatörler genel plan maliyetini önemli ölçüde etkileyebilir.
Sonuç olarak, optimizatör bir plan ağacı oluştururken, her düğüm için alternatif fiziksel operatörleri değerlendirir ve bunların birleşik maliyetini toplayarak toplam plan maliyetini hesaplar. Bu süreçte, bir operatörün çıktısının boyutu (kardinalite), bir üstteki operatörün girdisi olur ve onun maliyetini doğrudan etkiler. Bu nedenle, maliyet modelinin en alt seviyedeki kardinalite tahminlerindeki hata, yukarı doğru katlanrak büyüyebilir.
Plan Uzayı ve Arama Stratejileri
Bir sorgu için, özellikle çok sayıda birleştirme içeren karmaşık sorgularda, potansiyel tüm yürütme planlarının oluşturduğu küme plan uzayı olarak adlandırılır. Bu uzayın boyutu, birleştirme sayısıyla birlikte kombinatorik olarak patlar; n tablo için teorik olarak n! farklı birleştirme sırası ve her bir birleştirme için birden fazla algoritma seçeneği vardır. Cost-Based Optimizer'ın temel görevi, bu devasa arama uzayında global maliyeti minimize eden planı pratik bir sürede bulmaktır. Saf bir kaba kuvvet (brute-force) araması mümkün olmadığından, optimizatörler akıllı arama stratejileri ve kırpma (pruning) teknikleri kullanır.
En yaygın arama stratejilerinden biri, dinamik programlama (DP) tabanlı yaklaşımlardır. Sistem tarafından desteklenen en iyi planlar, alt kümeler için özyinelemeli olarak hesaplanır ve saklanır. Örneğin, {A, B, C, D} tablo kümesi için en iyi plan, {A,B}, {A,C} gibi tüm alt kümelerin en iyi planları bilinerek bulunabilir. Bu yöntem, n tablo için O(3^n) karmaşıklığına sahip olduğundan, genellikle birleştirme sayısı 10-15 ile sınırlandırılmıştır. Daha büyük sorgular için, optimizatörler heuristic veya randomize arama algoritmalarına başvurur.
Greedy algoritmalar, her adımda yerel olarak en düşük maliyetli birleştirmeyi seçer. Bu yöntem hızlıdır ancak global optimumu garanti etmez, çünkü erken bir seçim daha sonraki pahalı birleştirmelere yol açabilir. Daha gelişmiş sistemler, genetik algoritmalar veya simulated annealing gibi randomize teknikler kullanarak daha geniş bir plan uzayını keşfeder. PostgreSQL gibi sistemlerde, genetik sorgu optimizasyonu (GEQO), belirli bir eşiğin üzerindeki birleştirme sayıları için varsayılan olarak devreye girer.
Arama sürecini hızlandırmak için kullanılan en etkili tekniklerden biri plan maliyeti için alt sınır (lower bound) hesaplamak ve kırpma yapmaktır. Bir alt planın mevcut maliyeti, daha önce bulunan tam bir planın maliyetini aşarsa, bu alt plandan türeyen tüm planlar elenebilir (branch-and-bound arama). Bu yöntemin etkinliği, iyi bir başlangıç planı (örn., greedy ile bulunan) bulunmasına ve maliyet tahminlerinin doğruluğuna bağlıdır. Yanlış maliyet tahminleri, optimal planın erken elenmesine neden olabilir.
Plan uzayını daraltan diğer bir faktör, sistemin desteklediği fiziksel operatörlerin ve özelliklerin (planning enablers) sınırlı olmasıdır. Örneğin, bazı sistemler yalnızca sol-derin (left-deep) plan ağaçlarını değerlendirir, bu da arama uzayını büyük ölçüde azaltır. Sol-derin ağaçlarda, birleştirmelerin her zaman bir tablo ile önceki birleştirmenin sonucu arasında yapıldığı doğrusal bir yapı vardır. Bushy plan ağaçları ise daha esnektir ve paralel yürütme için daha uygun olabilir, ancak değerlendirilmesi daha maliyetlidir.
- Dinamik Programlama: Optimal sonuç garantisi sunar ancak kombinatorik patlamaya maruz kalır. Küçük-orta ölçekli sorgular için idealdir.
- Genetik Algoritmalar (GEQO): Randomize arama. Büyük birleştirme sayılarında pratik bir çözüm sunar, ancak optimal olma garantisi yoktur.
- Greedy (Açgözlü) Algoritmalar: Hızlıdır, ancak yerel optimum tuzağına düşebilir. Genellikle DP veya randomize yöntemler için başlangıç noktası olarak kullanılır.
- Branch-and-Bound (Dal-Sınır): Mevcut en iyi maliyeti kullanarak arama ağacındaki dalları erkenden kırpar. Maliyet modelinin doğruluğu ile verimlidir.
Modern veritabanı sistemleri, çok aşamalı optimizasyon (multi-stage optimization) yaklaşımını benimser. İlk aşamada hızlı heuristic yöntemlerle bir plan oluşturulur ve maliyeti bir üst sınır olarak kaydedilir. Sonraki aşamalarda, daha kapsamlı arama teknikleri, bu üst sınırı kullanarak agresif kırpma yaparak daha iyi planlar arar. Ayrıca, adaptive query processing gibi yeni yaklaşımlar, yürütme sırasında toplanan gerçek kardinalite bilgilerine dayanarak planı dinamik olarak yeniden optimize etme yeteneğini araştırmaktadır.
Sonuç olarak, plan uzayı araması, veritabanı optimizasyonunun teorik bilgisayar bilimi ile en çok kesiştiği alandır. Optimizatör tasarımcısı, aramanın kapsamı (tam/optimal vs. hızlı/yaklaşık) ile hesaplama süresi arasında sürekli bir denge kurmak zorundadır. Bu denge, sistemin kullanım amacına (OLTP'de hızlı planlama, OLAP'de kapsamlı optimizasyon) göre ayarlanır ve CBO'nun gerçek dünyada başarısını belirleyen en önemli faktörlerden biridir.