Birleştirme Algoritmaları: İç İçe Döngü, Karma, Birleştirme

INNER JOIN sözdizimini zaten biliyorsunuz. Kıdemli düzey mülakatlarda, veritabanının birleştirmeyi fiziksel olarak nasıl yürüttüğü sorulur. Üç algoritma vardır:

• İç İçe Döngü Birleştirmesi
• Karma Birleştirme
• Sıralı Birleştirme (sıralama-birleştirme)

Mantıksal birleştirme türü (INNER, LEFT) algoritmadan bağımsızdır. Planlayıcı algoritmayı tablo boyutlarına, dizinlere ve sıralama düzenine göre seçer. Her birinin hangi durumda avantajlı olduğunu bilmek bu dersin özüdür.

İç İçe Döngü en basit yöntemdir: dış tablodaki her satır için iç tablo taranarak eşleşmeler bulunur. Sözde kodda, biri diğerinin içinde olmak üzere iki döngü bulunur.

Saf hâliyle bu işlem O(dış * iç) maliyetine sahiptir ve büyük tablolar için çok kötüdür. Ancak iç tarafta birleştirme anahtarı üzerinde bir dizin varsa son derece verimli hâle gelir: her dış satır, iç tablonun tamamını taramak yerine ucuz bir dizin aramasını tetikler.

Dış tablo küçük ve iç birleştirme sütununda dizin bulunduğunda planlayıcının favorisi budur.

İç içe döngünün belirgin göstergesi, iç düğümdeki loops değeridir. Örnekte loops=3 görülmesinin nedeni, dış tarafın 3 satır üretmesi ve iç dizin taramasının 3 kez çalışmasıdır.

Dış taraf büyük olduğunda tehlike ortaya çıkar. Dış taraf 2 milyon satır üretirse iç taraf 2 milyon kez çalışır. Hızlı bir 0,01 ms'lik arama bile 20 saniyeye dönüşür.

Mülakatlarda, iyi bir dizin bulunmayan iç tabloda loops değeri yüksek olan her iç içe döngüyü belirtin; yavaş sorgu budur.

Karma Birleştirme, büyük ve sıralanmamış tabloları iyi işler. İki aşamada çalışır:

• Oluşturma: daha küçük tablo okunur ve birleştirme sütununa göre anahtarlanmış, bellekteki bir karma tablosuna yüklenir.
• Sorgulama: daha büyük tablo taranır; her satır için birleştirme anahtarı karmalanır ve karma tablosunda aranır.

Her tablo yalnızca bir kez okunduğu için maliyet yaklaşık olarak O(dış + iç) olur. Dizin veya sıralanmış girdi gerektirmez; eşitlik koşullarındaki büyük analitik birleştirmelerde üstün olmasının nedeni budur.

Karma birleştirmeler hakkında mutlaka belirtmeniz gereken iki nokta vardır:

• Yalnızca eşitlik birleştirme koşullarında çalışırlar (a.id = b.id). a.x < b.y gibi bir aralık koşulu karma birleştirmeyi kullanamaz.
• Oluşturma tarafı work_mem içine sığmalıdır. Sığmazsa Postgres paketleri diske taşır (Batches: > 1 ve disk kullanımı görülür); bu da birleştirmeyi ciddi biçimde yavaşlatır.

Bu nedenle, çok büyük oluşturma tarafı ve çok küçük work_mem ile yapılan karma birleştirme, gerçek dünyada belirtilmesi gereken bir performans hatasıdır.

Sıralı Birleştirme (sıralama-birleştirme), her iki girdinin de birleştirme anahtarına göre sıralanmış olmasını gerektirir. Ardından, sıralanmış iki listenin birleştirilmesine benzer şekilde, geride kalan işaretçiyi ilerleterek ikisini eşzamanlı biçimde tarar.

Girdiler, örneğin bir dizinden anahtar sırasıyla doğrudan geliyorsa ve zaten sıralanmışsa verimlidir; çünkü bu durumda sıralama adımına gerek kalmaz. Karma birleştirmenin aksine aralık ve eşitsizlik birleştirmelerini de destekler.

Girdiler önceden sıralanmamışsa planlayıcı açık Sort düğümleri ekler ve bu sıralama maliyeti karma birleştirmeyi daha ucuz hâle getirebilir.

Her algoritmanın hangi durumda avantajlı olduğunu ezberleyin:

• İç İçe Döngü, küçük dış tablo ve dizinlenmiş iç birleştirme anahtarı için; ayrıca sıralanmış girdi olmadan yapılan eşitlik dışı birleştirmelerde tek seçenektir.
• Karma Birleştirme, eşitlik üzerinden birleştirilen büyük ve sıralanmamış tablolar için; dizin gerekmez.
• Sıralı Birleştirme, her iki girdi de anahtara göre zaten sıralanmışsa (çoğunlukla dizinler aracılığıyla) veya aralık birleştirmelerinde; önceden sıralanmış çok büyük kümeler için idealdir.

Planlayıcı her birinin maliyetini tahmin eder ve satır tahminlerine göre en ucuz olanı seçer.

Kaynak kullanımı yöntemlere göre büyük ölçüde değişir ve mülakat yapanlar bunu özellikle sorgular:

• İç İçe Döngü, çok az bellek kullanır; maliyete tekrarlanan iç aramalar hâkimdir.
• Karma Birleştirme, karma tablosu için bellek gerektirir; tablo çok büyükse diske taşar.
• Sıralı Birleştirme, birleştirme işlemi ucuzdur; ancak önce sıralama yapılması gerekiyorsa pahalıdır. Sıralamalar da work_mem kullanır ve diske taşabilir.

Bu nedenle work_mem değerini artırmak, diske taşarak yavaşlayan bir karma işlemini veya sıralamayı bellekte çalışan bir işleme dönüştürebilir; bu, somut bir iyileştirme yanıtıdır.

Klasik senaryo şudur: bir sorgu geliştirme ortamında hızlı, üretim ortamında yavaştı. Planda loops=3000000 değerine sahip bir İç İçe Döngü görülür.

Planlayıcı dış satır sayısını olduğundan düşük tahmin etti (güncelliğini yitirmiş istatistikler 3 satır gösteriyordu, gerçek sayı 3 milyondu); bu nedenle iç içe döngüyü seçti. İstatistikler doğru olsaydı karma birleştirmeyi seçerdi.

Mülakatta vereceğiniz yanıt şudur: Tahminin doğru olması için ANALYZE çalıştırın; planlayıcı ardından karma birleştirmeye geçer ve sorgu büyük ölçüde hızlanır.

Genellikle algoritmaları zorlamamanız gerekir; ancak karşılaştırma yapmak için sınama sırasında bunu yapabilirsiniz. Postgres, yöntem başına açma-kapama seçenekleri sunar:

SET enable_nestloop = off; ve benzer şekilde enable_hashjoin ile enable_mergejoin. Birini kapatın, EXPLAIN ANALYZE komutunu yeniden çalıştırın ve alternatifin gerçekten daha hızlı olup olmadığını gözlemleyin.

Doğru çözümler yine şunlardır: güncel istatistikler, doğru dizinler, yeterli work_mem ve seçici yüklemler. Zorlama yalnızca tanı koymak içindir.

Bir kimlik üzerinden iki büyük olgu ve boyut tablosunu birleştiren bir analitik iş yükünü birlikte değerlendirelim:

• Boyut tablosu belleğe sığıyorsa genellikle en iyi seçenek olan bir Karma Birleştirme bekleyin.
• Her iki tablo da dizinlerden sıralanmış olarak geliyorsa Sıralı Birleştirme karma tablosu oluşturma adımını atlayabilir.
• Burada bir İç İçe Döngü görülmesi uyarı işaretidir; buna genellikle hatalı bir tahmin neden olur.

Planlayıcının hangisini seçtiğini okumak ve seçmesi gereken yöntemin bu olup olmadığını değerlendirmek, bu soruların ölçtüğü kıdemli düzey göstergesidir.

İki büyük ve sıralanmamış tabloyu a.id = b.id eşitlik koşuluyla birleştiriyorsunuz; hiçbirinde kullanışlı bir dizin yok ve istatistikler doğru. Planlayıcı büyük olasılıkla hangi birleştirme algoritmasını seçer?

Üç birleştirme algoritması:

• İç İçe Döngü, dış satır sayısı çarpı iç arama; küçük bir dış tablo ve dizinlenmiş bir iç anahtarla harikadır, loops çok büyük olduğunda ise tehlikelidir.
• Karma Birleştirme, oluşturma ve sorgulama aşamalarından oluşur; büyük ve sıralanmamış eşitlik birleştirmeleri için en iyisidir, eşitlikle sınırlıdır ve work_mem tarafından sınırlandırılır.
• Sıralı Birleştirme, sıralanmış girdiler üzerinde eşzamanlı ilerler; veriler zaten sıralanmışsa veya aralık birleştirmelerinde idealdir.

Planlayıcı seçimini maliyete ve istatistiklere göre yapar. Çok büyük loops değerine sahip şaşırtıcı bir iç içe döngü neredeyse her zaman hatalı bir satır tahmini anlamına gelir; istatistikleri düzeltin.