Birleştirme Algoritmaları
Birleştirme algoritmaları, iki veya daha fazla ilişkiden gelen demetleri (tuple) bir birleştirme koşuluna göre birleştiren fiziksel yöntemlerdir — iç içe döngü (nested-loop), sıralama-birleştirme (sort-merge) ve karma birleştirme (hash join) gibi. Bu algoritmalar genellikle bir sorgu planındaki en performans-kritik operatörlerdir.
Tanım
Bir birleştirme algoritması, iki ilişkinin bir koşul (predicate) üzerindeki birleştirmesini hesaplayan fiziksel bir operatördür. Bu algoritma, koşulu sağlayan demetleri sistematik olarak eşleştirerek, eşleşen demetleri verimli bir şekilde bulmak için iç içe yineleme (nested iteration), sıralı birleştirme (sorted merging) veya karma (hashing) yöntemlerini kullanmaktadır.
Kapsam
Bu konu, birleştirmeleri değerlendirmek için kullanılan başlıca algoritmaları kapsamaktadır: basit, blok ve indeks iç içe döngü birleştirmeleri; sıralama-birleştirme ve önceden sıralanmış girdilerle olan sinerjisi; ve bellekten daha büyük girdileri işleyen grace ve hibrit varyantlarını içeren karma birleştirme. Algoritmaların G/Ç maliyetleri ve bellek gereksinimleri ile her birinin hangi koşullar altında tercih edildiği analiz edilmektedir. Konu, maliyet tabanlı sorgu optimizasyonu altında ele alınan, optimize edicinin birleştirme sıralarının numaralandırılmasını içermemektedir.
Temel sorular
- İç içe döngü, sıralama-birleştirme ve karma birleştirme yaklaşımları ve maliyetleri açısından nasıl farklılık göstermektedir?
- Bir indeks iç içe döngü birleştirme, alternatiflerinden ne zaman daha iyi performans göstermektedir?
- Grace ve hibrit karma birleştirmeler, bellekten daha büyük girdileri nasıl işlemektedir?
- Her bir birleştirme yönteminin G/Ç maliyeti, sayfalar ve geçişler açısından nasıl analiz edilmektedir?
- Her bir algoritma hangi birleştirme koşulunu (eşitlik ve eşitsizlik) gerektirmektedir?
Anahtar kavramlar
- iç içe döngü birleştirme
- blok iç içe döngü birleştirme
- indeks iç içe döngü birleştirme
- sıralama-birleştirme
- karma birleştirme
- grace ve hibrit karma birleştirme
- eş-birleştirme (equijoin) ve teta birleştirme (theta join)
- G/Ç maliyet analizi
Temel kuramlar
- İç içe döngü birleştirmeleri
- Algoritma, bir ilişkinin her bir demeti için diğerini eşleşmeler açısından taramaktadır; blok iç içe döngü, sayfaları arabelleğe alarak G/Ç'yi azaltırken, indeks iç içe döngü, bir indeks mevcut olduğunda iç taramayı bir indeks aramasıyla değiştirmekte ve bu da onu seçici birleştirmeler için verimli hale getirmektedir.
- Sıralama-birleştirme
- Her iki girdi de birleştirme özniteliği üzerinde sıralanır ve ardından tek bir koordineli geçişte birleştirilir; girdiler zaten sıralanmış olduğunda veya çıktının sıralanması gerektiğinde özellikle caziptir ve eşitlik birleştirmelerini verimli bir şekilde işlemektedir.
- Karma birleştirme
- Bir eşitlik birleştirmesi, daha küçük ilişki üzerinde bellekte bir karma tablo oluşturularak ve daha büyük ilişki ile sorgulanarak hesaplanmaktadır; grace ve hibrit varyantları, bellek sınırını aştıklarında her iki girdiyi de diske bölümlere ayırarak büyük eş-birleştirmeler için güçlü performans sağlamaktadır.
Klinik önem
Birleştirmeler, birden çok tabloyu birleştiren analitik ve raporlama sorgularının maliyetine hakimdir. Bu nedenle, birleştirme algoritması seçimi — genellikle bir plandaki en önemli tek karar — bu tür sorguların etkileşimli olup olmadığını veya saatler sürüp sürmediğini belirlemektedir; bu da bu algoritmaları veritabanı performansı için merkezi hale getirmektedir.
Tarihçe
Sıralama-birleştirme ve iç içe döngü birleştirmeleri en eski ilişkisel sistemlere dayanmaktadır. Karma birleştirme ile grace ve hibrit varyantları 1980'lerde, özellikle paralel veritabanı araştırmalarında geliştirilmiştir ve birçok büyük eş-birleştirme (equijoin) için sıralama-birleştirmeden daha iyi performans gösterdiği kanıtlanmıştır. Graefe'nin 1993 tarihli araştırması, veritabanı metinlerinin hala takip ettiği bu algoritmaların analizini pekiştirmiştir.
Öne çıkan isimler
- Goetz Graefe
- David DeWitt
İlgili konular
Temel eserler
- graefe1993
- garciamolina2008
Sıkça sorulan sorular
- Hangi birleştirme algoritması en hızlıdır?
- Girdilere bağlıdır. Karma birleştirme, genellikle her iki girdi de sıralanmamışken büyük eş-birleştirmeler için en iyisidir; sıralama-birleştirme, girdiler zaten sıralanmış olduğunda veya çıktının sıralı olması gerektiğinde avantajlıdır; ve indeks iç içe döngü, bir girdi küçük olduğunda ve diğerinde birleştirme sütununda seçici bir indeks bulunduğunda en iyi performansı gösterir. Optimize edici, tahmini maliyete göre seçim yapmaktadır.
- Karma birleştirme neden eşitsizlik koşullarını işleyemez?
- Karma birleştirme, demetleri birleştirme anahtarının karmasına göre gruplandırır, böylece yalnızca eşit anahtarlara sahip demetler aynı kovaya düşer. Bu, eşitlik (eş-birleştirme) koşulları için işe yarar ancak kovalar arasında demetleri karşılaştırmayı gerektiren küçüktür gibi eşitsizlikler için geçerli değildir — bu tür durumlar bunun yerine iç içe döngü veya sıralama-birleştirme tarzı yöntemlerle ele alınmaktadır.