Sorgu optimizasyonu

Sorgu optimizasyonu, birçok ilişkisel veritabanı yönetim sisteminin ve NoSQL ve grafik veritabanları gibi diğer veritabanlarının bir özelliğidir . Sorgu iyileştiricisi, olası sorgu planlarını göz önünde bulundurarak belirli bir sorguyu yürütmenin en verimli yolunu belirlemeye çalışır.

Kullanıcılar genellikle sorgu iyileştiriciye doğrudan erişemez; çünkü sorgular veritabanı sunucusuna gönderildikten sonra, ayrıştırıcı tarafından işlenir ve ardından iyileştirme işleminin yapıldığı sorgu iyileştiriciye iletilir. Ancak bazı veritabanı motorları, sorgu iyileştiricinin belirli ipuçlarıyla yönlendirilmesine olanak tanır.

Sorgu, bir veritabanından bilgi isteğidir. " Telefon numarası 555-123-4567 olan kişinin ismini sorgula." kadar basit veya "30 ila 39 yaş aralığındaki Erzurum'daki tüm çalışan evli erkeklerin eşlerinden daha az maaş almasının ortalama maaşını bul" kadar karmaşık olabilir. Bir sorgu sonucu, veritabanındaki satırların istenen bilgiyi verecek şekilde işlenmesiyle üretilir. Veritabanı yapıları karmaşık olduğundan, çoğu durumda ve özellikle çok basit olmayan sorgular için, bir sorgu için gereken veriler, veritabanına farklı yollarla, farklı Veri yapıları aracılığıyla ve farklı sıralarda erişilerek toplanabilir. Her farklı yol genellikle farklı işlem süreleri gerektirir. Aynı sorgunun işlem süreleri, seçilen yönteme bağlı olarak saniyenin bir kısmından saatlere kadar büyük farklılıklar gösterebilir. Otomatik bir süreç olan sorgu optimizasyonunun amacı, verilen sorguyu en kısa sürede işlemenin yolunu bulmaktır. Zaman içindeki olası büyük fark, sorgu optimizasyonunun gerçekleştirilmesini haklı çıkarır; ancak tüm olasılıklar arasında tam olarak optimum sorgu planını bulmak genellikle çok karmaşıktır, kendi başına zaman alıcıdır, çok maliyetli olabilir ve çoğu zaman pratik olarak imkansızdır. Bu nedenle sorgu optimizasyonu, makul bir sürede genellikle en iyi olası sonuçtan çok fazla sapmayan "yeterince iyi" bir plan sağlamak için genellikle birkaç sağduyulu alternatifi karşılaştırarak optimuma yaklaşmaya çalışır.

Genel hususlar

En uygun sorgu planını belirlemek için harcanan süre ile elde edilen planın kalitesi arasında bir denge bulunmaktadır; sorgu iyileştirici her zaman en ideal çözümü belirleyemeyebilir. Farklı veritabanı yönetim sistemleri, bu dengeyi sağlamak amacıyla farklı stratejiler ve yaklaşımlar benimsemektedir. Maliyet tabanlı sorgu iyileştiricileri, çeşitli sorgu planlarının kaynak ayak izini değerlendirir ve bunu plan seçimi için temel olarak kullanır. En uygun sorgu planını belirlemek için harcanan süre ile elde edilen planın kalitesi arasında bir denge bulunmaktadır; sorgu iyileştirici her zaman en ideal çözümü belirleyemeyebilir. Farklı veritabanı yönetim sistemleri, bu dengeyi sağlamak amacıyla farklı stratejiler ve yaklaşımlar benimsemektedir. Maliyet tabanlı sorgu iyileştiricileri, çeşitli sorgu planlarının kaynak ayak izini değerlendirir ve bunu plan seçimi için temel olarak kullanır. Sorgu iyileştiriciler, her olası sorgu planına tahmini bir "maliyet" atar ve en düşük maliyete sahip olan planı tercih eder. Bu maliyet tahminleri, bir sorgunun çalıştırılması sırasında ortaya çıkacak toplam çalışma zamanı giderlerini öngörmek amacıyla oluşturulur. Tahmin sürecinde; gerekli girdi/çıktı (G/Ç) işlemlerinin sayısı, işlemcideki yürütme adımlarının uzunluğu, ihtiyaç duyulan disk arabellek (buffer) miktarı, disk erişim süreleri, paralel işlem birimleri arasındaki veri iletim yoğunluğu ve veri sözlüğünden elde edilen diğer sistemsel bilgiler dikkate alınır. Sorgu planları, olası erişim yolları (örneğin, birincil dizin erişimi, ikincil dizin erişimi, tam tablo taraması) ile çeşitli ilişkisel birleştirme tekniklerinin (örneğinmerge join, hash join, product join) analiz edilmesiyle oluşturulan bir aday plan kümesi üzerinden değerlendirilir. SQL sorgusunun yapısal karmaşıklığı arttıkça, bu planların oluşturduğu arama uzayı da önemli ölçüde genişleyebilir. Sorgu optimizasyonu genel olarak iki aşamada gerçekleştirilir: Mantıksal optimizasyon, sorgunun ilişkisel cebir işlemlerine dönüştürülmesini sağlarken; fiziksel optimizasyon, bu işlemlerin nasıl ve hangi yollarla yürütüleceğini belirlemeye yönelik kararları kapsar.

Uygulama

Çoğu sorgu iyileştirici, sorgu planlarını "plan düğümleri"nden oluşan bir ağaç yapısı şeklinde temsil eder. Her plan düğümü, sorgunun yürütülmesi sırasında gerçekleştirilecek tek bir işlemi kapsar. Bu düğümler, hiyerarşik bir biçimde ağaç yapısında düzenlenir ve ara sonuçlar, genellikle yapının alt seviyelerinden üst seviyelerine doğru iletilir. Her düğüm, sıfır veya daha fazla alt düğüme sahip olabilir; bu alt düğümler, kendi çıktısını üst düğüme girdi olarak sağlayan işlemleri ifade eder. Örneğin, bir birleştirme (join) işlemi gerçekleştiren bir düğüm, iki alt düğümden veri alabilir ve bu alt düğümler katılma işleminin girdilerini oluşturur. Benzer şekilde, bir sıralama (sort) düğümü ise genellikle sıralanacak veriyi sağlayan tek bir alt düğüme sahiptir. Ağaç yapısının yaprak düğümleri ise genellikle diskte veri taraması yapan işlemleri temsil eder; bu işlemler örneğin sıralı tarama (sequential scan) ya da indeks taraması (index scan) gibi yöntemlerle veri kaynağından sonuç üretir.

Join ordering

R(A, B) ⋈ S(B, C) ⋈ T(A, C) şeklindeki üçlü (triangle) sorgusu için iki olası sorgu planı mevcuttur: İlk plan, öncelikle S(B, C) ile T(A, C) ilişkilerini birleştirir ve ardından elde edilen ara sonucu R(A, B) ile birleştirir. İkinci plan ise, önce R(A, B) ile S(B, C) ilişkilerini birleştirir, ardından bu ara sonucu T(A, C) ile birleştirerek nihai sonucu elde eder.

Bir sorgu planının performansı büyük ölçüde tabloların birleştirilme sırasına göre belirlenir. Örneğin, sırasıyla 10 satır, 10.000 satır ve 1.000.000 satır boyutundaki 3 tablo A, B, C birleştirildiğinde, önce B ve C'yi birleştiren bir sorgu planı, önce A ve C'yi birleştiren bir sorgu planından birkaç kat daha fazla zaman alabilir. Çoğu sorgu iyileştirici, katılma sırasını belirlemek için ilk olarak IBM'in System R veritabanı projesinde geliştirilen dinamik programlama tabanlı bir algoritmadan yararlanır. Bu algoritma iki aşamada çalışır:

1. Öncelikle sorgu içerisindeki her ilişkiye ulaşmanın tüm yolları hesaplanır. Sorgu içerisindeki her ilişkiye sıralı tarama yoluyla ulaşılabilir. Sorgu içindeki bir yordama yanıt vermek için kullanılabilecek bir ilişkide bir dizin varsa, bir dizin taraması da kullanılabilir. Her ilişki için, optimize edici ilişkiyi taramanın en ucuz yolunu ve belirli bir sıralı düzende kayıtlar üreten ilişkiyi taramanın en ucuz yolunu kaydeder.
2. Daha sonra, optimizatör, birleştirme koşulunun mevcut olduğu her ilişki çiftinin birleştirilmesini dikkate alır. Her çift için, optimize edici DBMS tarafından uygulanan mevcut birleştirme algoritmalarını dikkate alacaktır. Her ilişki çiftini birleştirmenin en ucuz yolunun yanı sıra, çıktısını belirli bir sıralama düzenine göre üreten her ilişki çiftini birleştirmenin en ucuz yolunu da koruyacaktır.
3. Daha sonra, önceki aşamada üretilen her iki ilişkisel plan, sorgu içindeki kalan ilişkilerle birleştirilerek üç ilişkisel sorgu planı hesaplanır.

Sıralama düzeni, sorguyu işlerken daha sonra gereksiz sıralama işlemlerinin yapılmasını önleyebilir. İkinci olarak, belirli bir sıralama düzeni, verileri belirli bir şekilde kümelediği için sonraki birleştirmeyi hızlandırabilir.

İç içe SQL sorguları için sorgu planlaması (Query planning for nested SQL queries)

Modern bir ilişkisel DBMS'ye yönelik bir SQL sorgusu, seçim ve birleştirmelerden daha fazlasını yapar. Özellikle SQL sorguları, group by, exists ve not exists operatörleri aracılığıyla genellikle SPJ bloklarının (Select-Project-Join) birkaç katmanını iç içe yerleştirir. Bazı durumlarda bu tür iç içe geçmiş SQL sorguları select-project-join sorgusuna düzleştirilebilir, ancak her zaman değil. İç içe SQL sorguları için sorgu planları, birleştirme sıralamasında kullanılanla aynı dinamik programlama algoritması kullanılarak da seçilebilir; ancak bu, sorgu optimizasyon süresinde büyük bir artışa yol açabilir. Bu nedenle bazı veritabanı yönetim sistemleri, sorgu grafiği modeli kullanan alternatif bir kural tabanlı yaklaşım kullanır.

Maliyet tahmini (Cost estimation)

Sorgu optimizasyonundaki en zorlu problemlerden biri, alternatif sorgu planlarının maliyetlerini doğru biçimde tahmin edebilmektir. Optimizasyon araçları, bir sorgu planının yürütme maliyetini, plan üzerinde yer alan her kenardan (işlemden) geçen tahmini kardinalite (ya da tuple sayısı) üzerine kurulu matematiksel bir maliyet modeli aracılığıyla belirler. Kardinalite tahminleri ise, sorgudaki işleçlerin seçicilik değerlerine ilişkin öngörülere dayanır. Geleneksel veritabanı sistemleri, bu seçicilik tahminlerini üretmek amacıyla sütunlardaki veri dağılımını temsil eden histogram gibi ayrıntılı istatistiksel yapılardan faydalanır. Bu yöntem, tekil işleçlerin seçicilik tahminleri için genellikle başarılı sonuçlar verir.

Ancak birçok sorguda, örneğin SELECT COUNT(*) FROM R WHERE R.make = 'Honda' AND R.model = 'Accord' şeklindeki örnekte olduğu gibi, çoklu koşul bağlaçları (conjunctive predicates) yer alır. Bu tür durumlarda, tahminler çoğu zaman değişkenler arası güçlü korelasyon içerir (örneğin, model = 'Accord' koşulu genellikle make = 'Honda' koşulunu da ima eder). Bu gibi bağımlılıkları yakalamak güç olduğundan, bağlaçların birleşik seçiciliğini doğru şekilde tahmin etmek önemli ölçüde zordur. Hatalı kardinalite tahminleri ve gözden kaçan veri bağımlılıkları, sorgu iyileştiricilerinin düşük verimlilikte sorgu planları seçmesinin temel sebeplerindendir.

Bu nedenledir ki, veritabanı yöneticilerinin istatistikleri düzenli olarak güncellemeleri, özellikle büyük veri yükleme veya boşaltma işlemlerinden sonra bu güncellemeleri yapmaları kritik öneme sahiptir.

Uzantılar (Extensions)

Klasik sorgu optimizasyonu, sorgu planlarının genellikle yürütme süresi olan tek bir maliyet metriğine göre karşılaştırıldığını ve her sorgu planının maliyetinin belirsizlik olmaksızın hesaplanabileceğini varsayar. Her iki varsayım da bazen pratikte ihlal edilmektedir ve klasik sorgu optimizasyonunun bu sınırlamaları aşan çok sayıda uzantısı araştırma literatüründe incelenmiştir. Bu genişletilmiş sorun varyantları, tek sorgu planlarının maliyetini modelleme ve optimizasyon hedefleri açısından farklılık gösterir.

Parametreli sorgu optimizasyonu (Parametric query optimization)

Klasik sorgu optimizasyonu her sorgu planını bir skaler maliyet değeriyle ilişkilendirir. Parametreli sorgu optimizasyonu sorgu planı maliyetinin optimizasyon zamanında değerleri bilinmeyen parametrelere bağlı olduğunu varsayar. Bu tür parametreler örneğin optimizasyon zamanında tam olarak belirtilmeyen ancak yürütme zamanında sağlanacak sorgu tahminlerinin seçiciliğini temsil edebilir. Bu nedenle parametreli sorgu optimizasyonu her sorgu planını çok boyutlu bir parametre alanından tek boyutlu bir maliyet alanına eşlenen bir maliyet fonksiyonuyla ilişkilendirir. Optimizasyonun amacı genellikle olası parametre değer kombinasyonlarından herhangi biri için en uygun olabilecek tüm sorgu planlarını oluşturmaktır. Bu, ilgili sorgu planlarının bir kümesini oluşturur. Çalışma zamanında, gerçek parametre değerleri bilindiğinde, bu kümeden en iyi plan seçilir. Parametreli sorgu optimizasyonunun avantajı, optimizasyonun (genelde çok pahalı bir işlemdir) çalışma zamanında önlenmesidir.

Çok amaçlı sorgu optimizasyonu (Multi-objective query optimization)

Sorgu planlarını karşılaştırmak için yürütme süresine ek olarak genellikle başka maliyet ölçümleri de bulunur. Örneğin bir bulut bilişim senaryosunda, sorgu planları yalnızca yürütülmesinin ne kadar zaman aldığı açısından değil, aynı zamanda yürütülmesinin ne kadar paraya mal olduğu açısından da karşılaştırılmalıdır. Veya yaklaşık sorgu optimizasyonu bağlamında, yürütme yükünü azaltarak yaklaşık sonuçlar elde etmek amacıyla, girdi verilerinin rastgele seçilmiş örnekleri üzerinde sorgu planları yürütmek mümkündür. Bu gibi durumlarda alternatif sorgu planlarının, yürütme süreleri açısından olduğu kadar ürettikleri verilerin kesinliği veya güvenilirliği açısından da karşılaştırılması gerekir. Çok amaçlı sorgu optimizasyonu bir sorgu planının maliyetini, her vektör bileşeninin farklı bir maliyet metriğine göre maliyeti temsil ettiği bir maliyet vektörü olarak modeller. Klasik sorgu optimizasyonu, maliyet alanının boyutunun (yani maliyet vektörü bileşenlerinin sayısının) bir olduğu çok amaçlı sorgu optimizasyonunun özel bir durumu olarak düşünülebilir. Farklı maliyet ölçütleri birbirleriyle çelişebilir (örneğin, bulut bilişim senaryosunda asgari yürütme süresine sahip bir plan ve asgari parasal yürütme ücretlerine sahip farklı bir plan olabilir). Bu nedenle, Optimizasyonun amacı, tüm maliyet metriklerini aynı anda en aza indirmek değildir. Bunun yerine, farklı maliyet metrikleri arasında en iyi dengeyi sağlayan sorgu planını bulmaktır. En iyi uzlaşmanın hangisi olduğu kullanıcı tercihlerine bağlıdır (örneğin, bulut senaryosunda bazı kullanıcılar daha ucuz bir planı tercih ederken diğerleri daha hızlı bir planı tercih edebilir). Dolayısıyla optimizasyonun amacı, optimize ediciye girdi olarak sağlanan kullanıcı tercihlerinin bazı özelliklerine dayalı olarak en iyi sorgu planını bulmak (örneğin, kullanıcılar göreceli önemi ifade etmek veya belirli metrikler üzerinde kesin maliyet sınırları tanımlamak için farklı maliyet metrikleri arasında ağırlıklar tanımlayabilir) veya Pareto-optimal sorgu planları kümesinin bir yaklaşımını üretmektir (yani, tüm metriklere göre başka hiçbir planın daha iyi maliyete sahip olmadığı planlar) böylece kullanıcı bu plan kümesinden tercih edilen maliyet dengelemesini seçebilir.

Çok amaçlı parametreli sorgu optimizasyonu (Multi-objective parametric query optimization)

Çok amaçlı parametreli sorgu optimizasyonu parametreli ve çok amaçlı sorgu optimizasyonunu genelleştirir. Planlar birden fazla maliyet metriğine göre karşılaştırılır ve plan maliyetleri optimizasyon zamanında değerleri bilinmeyen parametrelere bağlı olabilir. Bu nedenle bir sorgu planının maliyeti, çok boyutlu bir parametre alanından çok boyutlu bir maliyet alanına doğru bir fonksiyon olarak modellenmiştir. Optimizasyonun amacı, her olası parametre değeri ve kullanıcı tercihi kombinasyonu için en uygun olabilecek sorgu planları kümesini oluşturmaktır. Birçok araç, hangi işlemlerin en yüksek işlem maliyetine sahip olduğunu göstermek için sorgu yürütme planlarını görüntüler. Microsoft SMS, ApexSQLPlan, Hana ve Tableau bunlara örnek olarak verilebilir. Bu planlarda bulunan sorunların düzeltilmesi, yürütme süresini yüzde on oranında kısaltabilir ve bazı durumlarda iki boyutlu aramaları doğrusal olanlara indirebilir. Birincil ve en basit optimizasyon kontrol listelerinden biri, çoğu RDMS'nin verimli bir şekilde yürütmek üzere tasarlandığı işlemleri kullanmaktır.