Maliyet Tabanlı Sorgu Optimizasyonu
Maliyet tabanlı sorgu optimizasyonu, bir sorgu için eşdeğer yürütme planları alanını araştırır ve veri istatistikleri ile bir yürütme maliyeti modeli kullanarak tahmini maliyeti en düşük olanı seçer.
Tanım
Maliyet tabanlı sorgu optimizasyonu, veri istatistikleri ve bir maliyet modelinden yola çıkarak, bir sorgu için alternatif eşdeğer planların yürütme maliyetini tahmin etme ve genellikle dinamik programlama ile seçilen birleştirme sırasına sahip, tahmini maliyeti en düşük olan planı seçme sürecidir.
Kapsam
Bu konu, bir optimize edicinin bir planı nasıl seçtiğini kapsamaktadır: ilişkisel cebir eşdeğerlikleri ve alternatif fiziksel operatörler tarafından oluşturulan plan arama alanı, planları puanlayan maliyet modeli (başlıca G/Ç ve CPU cinsinden), istatistiklerden ve histogramlardan kardinalite ve seçicilik tahmini ve System R tarafından tanıtılan birleştirme sırası numaralandırmasına yönelik dinamik programlama yaklaşımı. Operatörlerin kendilerinin uygulanması ve plan üretimine katkıda bulunanın ötesindeki kural tabanlı mantıksal yeniden yazma bu kapsamın dışındadır.
Temel sorular
- Eşdeğer yürütme planları alanı nasıl oluşturulur ve budanır?
- Optimize edici, işlemlerin kardinalitesini ve seçiciliğini nasıl tahmin eder?
- Dinamik programlama, birleştirme sıralarını verimli bir şekilde nasıl numaralandırır?
- Maliyet modeli neleri hesaba katar ve G/Ç ile CPU maliyetleri nasıl birleştirilir?
- Kardinalite tahmin hataları neden kötü plan seçimlerine yol açar?
Anahtar kavramlar
- plan arama alanı
- maliyet modeli (G/Ç ve CPU)
- seçicilik ve kardinalite tahmini
- histogramlar ve istatistikler
- birleştirme sırası numaralandırması
- dinamik programlama
- ilginç sıralamalar
- dönüşüm tabanlı optimizasyon
Temel kuramlar
- System R dinamik programlama optimizasyonu
- Selinger'ın optimize edicisi, ilişkilerin her bir alt kümesi (ve her ilginç sıralama düzeni) için en ucuz planı tutarak, birleştirme sıralarını dinamik programlama ile aşağıdan yukarıya doğru numaralandırır, bu da geniş birleştirme sırası alanını aranabilir hale getirir.
- Kardinalite ve seçicilik tahmini
- Optimize edici, her işlemin ürettiği demet sayısını tablo istatistikleri, histogramlar ve seçicilik formülleri kullanarak tahmin eder; bu tahminler maliyet modelini yönlendirir ve optimizasyon hatasının ana kaynağıdır.
- Maliyet modelleri ve arama stratejileri
- Planlar, G/Ç, CPU ve bellek etkilerini birleştiren bir maliyet modeli tarafından puanlanır; System R'ın dinamik programlamasının ötesinde, dönüşüm tabanlı optimize ediciler, optimizasyonu daha zengin operatörlere ve dağıtılmış ayarlara genişletmek için yeniden yazma kuralları aracılığıyla planları keşfeder.
Klinik önem
Optimize edici, kullanıcıların SQL'i nasıl yürüteceklerini belirtmeksizin bildirimsel SQL yazmalarına olanak tanıyan bileşendir; maliyet tahminlerinin ve aramasının kalitesi, büyük veritabanlarındaki sorguların hızlı olup olmadığını doğrudan belirler, bu nedenle maliyet tabanlı optimizasyon, veritabanı sistemlerinin en çok incelenen ve ticari olarak en önemli kısımlarından biridir.
Tarihçe
Selinger ve meslektaşları tarafından geliştirilen 1979 tarihli System R optimize edicisi, dinamik programlama ile birleştirme sırası ve seçicilik tabanlı maliyet tahmini ile maliyet tabanlı optimizasyonu tanıtmış ve bu alanı tanımlamıştır. Daha sonra Volcano ve Cascades gibi dönüşüm tabanlı optimize ediciler aramayı genelleştirmiş ve öğrenilmiş modeller de dahil olmak üzere kardinalite tahmini üzerine devam eden çalışmalar, çerçevenin (framework) temel zayıflığını ele almaktadır.
Tartışmalar
- Kardinalite tahmini ve uyarlanabilir yürütme
- Maliyet tabanlı optimizasyon, yalnızca boyut tahminleri kadar iyi olduğundan ve bu tahminler genellikle ilişkili veriler için yanlış olduğundan, araştırmacılar daha iyi istatistiklere ve makine öğrenimi tabanlı tahmin edicilere yatırım yapıp yapmama veya yürütme sırasında kötü planları düzelten uyarlanabilir, çalışma zamanı yeniden optimizasyonuna daha fazla güvenip güvenmeme konusunda tartışmaktadır.
Öne çıkan isimler
- Patricia Selinger
- Goetz Graefe
- Surajit Chaudhuri
İlgili konular
Temel eserler
- selinger1979
- graefe1993
Sıkça sorulan sorular
- Bir optimize edici neden bazen kötü bir plan seçer?
- Maliyet tabanlı optimize ediciler, her işlemin kaç satır üreteceğine dair tahminlere dayanır. Veriler çarpık olduğunda veya sütunlar ilişkili olduğunda, bu tahminler büyük ölçüde yanlış olabilir ve hata birleştirmeler boyunca birikir. Yanlış bir tahmin, plan kağıt üzerinde ucuz görünse bile, optimize edicinin kötü bir birleştirme sırası veya erişim yolu seçmesine neden olabilir.
- Birleştirme sıralaması için neden dinamik programlama kullanılır?
- Olası birleştirme sıralarının sayısı, tablo sayısıyla kombinatoryal olarak artar, bu nedenle kapsamlı arama uygulanamaz. Dinamik programlama, daha küçük alt kümeler için optimal planlardan daha büyük ilişkiler kümeleri için optimal planlar oluşturur, bu da iş yükünü önemli ölçüde azaltırken, tipik sorgu boyutları için iyi (genellikle optimal) bir birleştirme sırası bulmayı sağlar.