Sorgu Değerlendirmeye Genel Bakış

Database Management Systems —Overview of Query Evaluation konusundaki notlarım

Özet videom:

https://www.youtube.com/watch?v=h0vjkDdvuHQ

Plan: İlişkisel Cebir işlemi ağacı, her işlem için algoritma seçimi

Her operatör tipik olarak bir “çekme” arabirimi kullanılarak uygulanır. Bir operatör sonraki çıktı demetleri için “çekildiğinde”, operatör kendi girdilerini “çeker” ve bunları hesaplar.

SELECT S.Sname

FROM Sailors S, Reserves R

WHERE S.sid = R.sid AND B.bid = 100 AND S.rating > 5

Sorgu optimizasyonunda iki ana sorun vardır:

Belirli bir sorgu için hangi plan uygulanır?

En ucuz plan için plan aranı arayan algoritma.

Bir planın maliyeti nasıl tahmin edilir?

İdeal olarak: En iyi planı bul.

Pratik olarak: En kötü plandan kaçının!

System R yaklaşımını inceleyeceğiz.

Bazı Yaygın Teknikler

İlişkisel operatörleri değerlendirmeye yönelik algoritmalar, bazı basit fikirleri kapsamlı bir şekilde kullanır:

İndeksleme: Küçük demet kümelerini (seçimler, birleştirmeler) almak için “WHERE” koşullarını kullanabilir.

Yineleme(iteration): Bazen, işaretçi(index) olsa bile tüm demetleri taramak daha hızlı olabilir. (Ve bazen, tablonun kendisi yerine bir dizindeki veri işretçilerini tarayabiliriz.)

Bölümleme(partitioning): Sıralama veya heşleme kullanarak, girdi gruplarını bölümlere ayırabilir ve pahalı bir işlemi daha küçük girdilerde benzer işlemlerle değiştirebiliriz.

* Sorguları değerlendirmeyi tartışırken bu tekniklerin varlığının farkında olun!

İstatistikler ve Kataloglar

İlgili ilişkiler ve indeksler hakkında bilgiye ihtiyacınız var.

Kataloglar tipik olarak en az şunları içerir:

Her ilişki için demet sayısı (NTuples) ve sayfa sayısı (NPages).

Her dizin için farklı anahtar değerlerinin (NKey’ler) ve N Sayfalarının sayısı.

Her ağaç dizini için dizin yüksekliği ve düşük/yüksek anahtar değerleri (Düşük/Yüksek).

Kataloglar periyodik olarak güncellenmektedir.

Veri değişiklikleri çok pahalı olduğunda günceller. Zaten bir çok yaklaşık değer kullanılmaktadır bu yüzden hafif tutarsızlık sorun olmaz.

Daha ayrıntılı bir örnek verecek olursak bazı alanlardaki değerlerin histogramları bazen saklanmaktadır.

Erişim Yolları

Erişim yolu, demetleri alma yöntemidir:

Dosya taraması veya bir dosyada seçimle eşleşen dizin. Bir ağaç dizini, yalnızca arama anahtarının bir önekindeki öznitelikleri içeren terimlerle eşleşir (birleşim). Örneğin, <a, b, c> üzerindeki Ağaç dizini, a=5 AND b=3 ve a=5 AND b>6 seçimiyle eşleşir, ancak b=3 ile eşleşmez.

Bir karma dizini, dizinin arama anahtarındaki her öznitelik için bir terim özniteliği değerine eşit olan terimlerle (birleşim) eşleşir.

Örneğin, <a, b, c> üzerindeki heş indeksi a=5 AND b=3 AND c=5 ile eşleşir; ancak b=3 veya a=5 AND b=3 veya a>5 AND b=3 AND c=5 ile eşleşmez.

Karmaşık Seçimler Üzerine Bir Not

(day<8/9/94 AND rname=’Paul’) OR bid=5 OR sid=3

Seçim koşulları ilk önce birleşik normal biçime (CNF) dönüştürülür:

(day<8/9/94 OR bid=5 OR sid=3) AND (rname=’Paul’ OR bid=5 OR sid=3)

Sadece OR olmayan durumları tartışıyoruz; genel durumu merak ediyorsanız metne bakın.

Seçimlere Tek Yaklaşım

En seçici erişim yolunu bulun, onu kullanarak tanımlama gruplarını alın ve dizine uymayan kalan tüm terimleri uygulayın:

En seçici erişim yolu: Tahmin ettiğimiz bir dizin veya dosya taraması, en az sayfa G/Ç’sini gerektirecektir.

Bu dizinle eşleşen terimler, alınan demet sayısını azaltır; diğer terimler, alınan bazı demetleri atmak için kullanılır, ancak getirilen demetlerin/sayfaların sayısını etkilemez.

day<8/9/94 AND bid=5 AND sid=3’ı düşünün. “Day” işlemi için bir B+ ağaç indeksi kullanılabilir; daha sonra, alınan her demet için bid=5 ve sid=3 kontrol edilmelidir. Benzer şekilde, <bid, sid> üzerinde bir heş indeks kullanılabilir; day<8/9/94 sorgusu daha sonra kontrol edilmelidir.

Seçimler için Dizin Kullanma

Maliyet, nitelenen demetlerin sayısına ve kümelemeye bağlıdır.

Nitelikli veri girişlerini bulma maliyeti (genellikle küçük) artı kayıtları alma maliyeti (kümeleme olmadan büyük olabilir).

Örneğin, isimlerin tek tip dağılımını varsayarsak, demetlerin yaklaşık %10'u hak kazanır (100 sayfa, 10000 demet). Kümelenmiş bir dizinle, maliyet 100 I/O’dan biraz fazladır; kümelenmemişse, 10000 I/O’ya kadar!

SELECT * FROM Reserves R WHERE R.rname<’C%’

Yansıma(Projection)

SELECT DISTINCT R.sid, R.bid FROM Reserves R

Maaliyetli kısım, kopyaları kaldırmaktır.

SQL sistemleri, “DISTINCT anahtar kelimesi olmadığı sürece kopyaları kaldırmaz.

Sıralama Yaklaşımı: <sid, bid> üzerinde sıralayın ve kopyaları kaldırın. (Sıralama sırasında istenmeyen bilgileri bırakarak bunu optimize edebilir.)

Heşleme Yaklaşımı: Oluşturmak için <sid,bid> üzerinden heş edilir. Bölümleri birer birer belleğe yükleyin, bellek içi heş yapısı oluşturun ve yinelemeleri ortadan kaldırın.

Arama anahtarında hem R.sid hem de R.bid olan bir dizin varsa, veri girişlerini sıralamak daha ucuz olabilir!

Birleşim: İç İçe Döngüler

foreach tuple r in R do

foreach tuple s in S where ri == sj do

add <r, s> to result

Bir ilişkinin birleştirme sütununda bir dizin varsa (S diyelim), onu iç yapabilir ve işaretçiden yararlanabilir.

Maliyet: M + ( (M*pR) * S tane eşleşen demet bulma maliyeti)

M= R sayfa sayısı.

pR= sayfa başına R demet sayısı.

Her bir R demeti için, S işaretçisini arama maliyeti, heş işaretçi için yaklaşık 1.2, B+ ağacı için 2–4'tür.

O zaman demetleri bulmanın maliyeti kümelemeye bağlıdır.

Kümelenmiş dizin(clustered index): 1 G/Ç (tipik),

Kümelenmemiş: eşleşen demet başına 1 G/Ç’ye kadar.

Formüllerin özeti:

Birleşim: İç içe döngüler
Maliyet= M+((M*Pr)*Eşleşen demetler(satırlar) bulmanın maliyeti)
M= R sayfa sayısı(number of passes R)
Pr= number of R tuples per parse
Kümelenmiş dizin: 1 G/Ç.
Kümelenmemiş: S demeti başına 1 G/Ç’ya kadar tutuyor.
R: Dış tablo.
S: İç tablo.

Birleşim: Sıralama birleştirme
Cost:SortCost(M)+SortCost(N)+(M+N)
Sort Cost: 2*M*(pass sayısı)
Number of passes: [logB-1[M/B]]+1
Buradaki parantezler tavan sembolüdür!
B: arabellek sayfası(buffer page)

Sonuçların maliyetini de hesap etmeliyiz.

Özet

Her ilişkisel operatör için birkaç alternatif değerlendirme algoritması vardır.

Bir sorgu, bir operatör ağacına dönüştürülerek ve ağaçtaki operatörler değerlendirilerek değerlendirilir.

Belirli bir veritabanı tasarımının (ilişkilerve dizinler) bir iş yükü (sorgu kümesi) üzerindeki performans etkisini tam olarak anlamak için sorgu optimizasyonunu anlamanız gerekir.

Bir sorguyu optimize etmenin iki kısmı vardır:

Bir dizi alternatif plan düşünün.

• Arama alanını budamak gerekir; tipik olarak, yalnızca soldan derinlemesine tasarımlar.

Göz önünde bulundurulan her planın maliyeti tahmin edilmelidir.

• Her plan düğümü için sonuç boyutu ve maliyeti tahmin edilmelidir.

• Anahtar meseleler: İstatistikler, işaretçiler ve operatör uygulamaları.

Kaynak:

Database Management Systems -Overview of Query Evaluation