SQL Server JOIN Türleri – II (LOOP, HASH, MERGE JOIN)

Önceki yazıda SQL Server’in desteklediği mantıksal tablo birleştirme işleminden (Table Join) bahsetmiştik. Bu yazıda da biraz işin mutafağına geçerek birleştirme işlemin hangi fiziksel yöntemlerle yapıldığını özetlemeye çalışacağız.
Diğer veritabanları gibi SQL Server’da bulunan query optimizer bir sorguyu etkin bir şekilde çalıştırmak için bir planlama sunar. Bu planlamanın en önemli parçası veri arama aşamasında hangi yöntemi kullanacağıdır. Bu süreçte farklı yol haritaları çıkarılır ve içlerinen maliyeti en düşük olan seçilir. SQL Server’in bir sorguyu çalıştırma yöntemini değiştirmek için hint denilen sorgu ipuçları mevcuttur. Bunları kullanarak o esnada SQL Server için yönlendirilme yapılabilir. Bu ipuçlarından biri de JOIN hint’leridir (LOOP | HASH | MERGE ). INNER ve OUTER join türleri sorguların mantıksal olarak operasyonuyla ilgili iken LOOP, HASH ve MERGE yöntemleri sorguların fiziksel operasyonuyla ilgilidir.

NESTED LOOPS JOIN : İki tabloyu birleştirirken döngüleme yöntemini kullanır. Bu esnada tablolardan birini iç(inner) diğerini dış(outer) olarak işleme alır. Aşağıdaki algoritmada gösterildiği gibi dış tablodaki herbir satır için iç tablodaki tüm satırlar okunur. Bu döngü işleminde dış ve iç tablolara ait satırlar eşleştikçe sonuç listesine eklenir. Bu yöntem kayıt sayısı az olan tablolarda iyi bir performans sunar. SQL Server bu yöntemi RIGHT ve FULL join türlerinde kullanmaz.
for each R1 in outer input set (T1)
for each R2 in inner input set (T2)
if R1 match with R2
Output (R1, R2)

Buradaki R1 ve R2, tablolardaki satır dizisini temsil etmektedir.
Danisman ve OgrenciDanisman tabloları arasında LOOP JOIN kullanılacak şekilde join işlemi kuralım.

SET STATISTICS PROFILE ON
GO
SELECT * FROM Danisman D
	INNER LOOP JOIN OgrenciDanisman OD
		ON D.DanismanId=OD.DanismanId
GO
SET STATISTICS PROFILE OFF

“SET STATISTICS PROFILE ON” aracılığıyla elde ettiğimiz yürütme adımları aşağıdaki gibi göründü.

Bu tabloya baktığımızda Danisman tablosunun Outer Table, OgrenciDanisman tablosunun da Inner Table olduğunu görmekteyiz. Bu seçimden sonra ilk adım olarak dış tablo(Danisman) taranmış. Birim zamanda bir “danışman” okunur ardından bu danışmanın OgrenciDanisman tablosundaki karşılığını bulmak için OgrenciDanisman tablosu “Table Scan” yöntemiyle taranır. Bu işlem Danisman tablosundaki tüm kayıtlar için tekrar edilmiş olur. Danisman tablosunda 4 kayıt olduğu için OgrenciDanisman tablosu 4 kere taranmış olacaktır. Sonuçta danisman tablosu 1 kere taranmış ve 4 satır elde edilmiş. OgrenciDanisman tablosu da 4 kere taranmış ve sonuçta 12 row elde edilmiştir. Oysa toplamda sorgunun sonucu 3 row döndürmektedir. Query Analyzer’de “Include Actual Execution Plan” seçeneğini aktifleştirip sorgumuzu çalıştırdığımızda aşağıdaki görüntüyü elde etmiş oluruz.

Metin tabanlı Exution Planda da görüldüğü gibi OgrenciDanisman tablosundan toplamda 12 satır okunmuş. Oysa sonuç listesinde sadece 3 row ancak eşleşmiş olarak gelebiliyor. Bu sorunu aşmak için OgrenciDanisman tablosu üzerinde bir index kurabiliriz. Böylece “Table Scan” yöntemi gibi kötü bir yöntem ile değil de doğrudan Index’i kullanarak sadece eşleşecek veriyi döndürür.

CREATE CLUSTERED INDEX IX on OgrenciDanisman(DanismanId)

Index’i oluşturduktan sonra sorgumuzu yeniden çalıştıralım. Bu durumda aşağıdaki görüntüleri elde etmiş oluruz.

Yine aynı şekilde OgrenciDanisman tablosu 4 defa taranmış ancak bu sefer “Index Seek” yöntemi kullanıldığı için her defasında tüm satırlar değil sadece DanismanId ile eşleşen satır döndürülmüştür.

SQL Optimizer aracının nested loops join yöntemini kullanmasını zorlamak için aşağıdaki gibi OPTION tümcesi de yazılabilir.

SELECT * FROM Danisman D
	INNER JOIN OgrenciDanisman OD
		ON D.DanismanId=OD.DanismanId
OPTION(LOOP JOIN)

Nested Loop Join, doğrudan FULL OUTER JOIN yönteminde kullanılmaz. “T1 full outer join T2” şeklindeki sorgu “T1 left outer join T2 UNION T2 left anti-semi-join T1” şekline dönüştürerek çalıştırır Yani önce iki tablo arasında LEFT JOIN varmış gibi sorgu çalıştırılır ardından Anti-Semi Join yöntemi kullanılarak T2’nin satırları sonuç listesine eklenir.
Nested Loop Join yöntemi daha çok küçük kayıtlı tablolarda performans sergiler. Üzerinde index bulunan büyük tablolarda da iyi performans sergileyebilir. Özellikle iç tablonun çok satırlı olması durumunda veriye erişimi index yapısıyla hızlandırılabilir. Böylece Table Scan yükünden kurtulmuş olur.
MERGE JOIN : Bazı kaynaklarda “Merge Scan Join” veya “Sort Merge Join” olarak ta isimlendirilen Merge Join yöntemi Nested Loop Join’den farklı olarak herhangi bir Join yöntemiyle çalışmaktan ziyade koşul olarak verilmiş alanların sıralı olmasını şart koşar. Örneğin “T1.a = T2.b” şeklinde bir koşulda T1 tablosunun T1.a kolonuna göre, T2 tablosunun da T2.b kolonuna göre sıralı olması gerekmektedir. Merge Join, birim zamanda sıralı durumda olan “a” ve “b” kolonları okuyup karşılaştırır. Eğer iki alan eşit ise sözkonusu satırı sonuç listesine ekler. Eğer tablolar sıralı değilse ve sorguda Merge Join işlemi kullanılması isteniyorsa Query Optimizer tarafında öncelikle tablolar sıralı hale getirilir ardından karşılaştırma sürecine geçilir. İki kaynak arasında Merge Join algoritması aşağıdaki gibi işler;
get first row R1 from input 1
get first row R2 from input 2
while not at the end of either input
begin
if R1 joins with R2 (if R1 match R2)
begin
return (R1, R2)
get next row R2 from input 2
end
else if R1 <>
get next row R1 from input 1
else
get next row R2 from input 2
end

Algoritmadan da görüleceği gibi tablolardaki kayıt sayısı kadar maliyet oluşur. Nested Loop’ta iç tablonun tüm satırları her defasında yeniden okunuyordu. Merge join’de ise aynı anda iki tablonun birer satırı okunmaktadır. Tablolar aynı anda tarandığı gibi toplamda bir kere taranıyor. Bu yüzden büyük sıralı tablolarda iyi bir performans sunar. Eğer koşul olarak verilmiş alanlar arasında < ,>< =,>= operatörleri varsa bu yöntemin tercih edilmesi iyi sonuç verecektir.
Örnek tablolarımız için çalıştırma planı aşağıdaki gibi olacaktır;

SELECT * FROM Ogrenci O
	INNER JOIN OgrenciDanisman OD
	ON O.OgrenciId=OD.OgrenciId
	OPTION (MERGE JOIN)



Burada görüldüğü gibi tablolar sıralı olmadığı için o esnada SIRALAMA işlemi de yapılmaktadır. Örneğin Ogrenci tablosunu OgrenciId alanına göre sıralı yapalım.

CREATE CLUSTERED INDEX IX ON Ogrenci(OgrenciId)

Bu durumda plan aşağıdaki gibi değişecektir.

HASH JOIN :
Daha çok sıralı olmayan büyük tablolarda tercih edilen Hash Join yöntemi öncelikle iki tablodan küçük olanını kullanarak bellekte bir hash table oluşturur ardından büyük tabloyu tarayıp büyük tabloya ait hash değerini bellekteki tabloya ait hash değeriyle karşılaştırarak sonuç listesini oluşturur. Temelde her iki tarafta her satır için bir hash değeri oluşturup bu değer üzerinden ilişki kurar. Hash Join yönteminin algoritması aşağıdaki gibidir;
Create build table
For each R1
begin
generate hash value of R1 join key
insert into build table to appropriate hash bucket
end
for each R2
begin
generate hash value of R2 join key
for each R1 in corresponding hash bucket
if match R1 and R2
output (R1,R2)
end

Algoritmadaki “build table” ilk tablo kullanarak bellekte oluşturulmuş hash değerlerinin bulunduğu tabloyu temsil etmektedir.
Algoritmadan görüleceği Hash Join, diğer Join çalışma yöntemine göre daha maliyetlidir. Query Optimizer bu yöntemi sıralı olmayan büyük tablolar veya beklenilenden fazla dağılmış (big fraction) küçük tablolarda tercih eder.
Son olarak JOIN yöntemlerinin performansıyla ilgili şunu söyleyebiliriz; bu yöntemlerin hangisinin en iyisi olduğunu söylemek zor. Kullanılan tabloların büyüklüğüne ve üzerinde index yapısına bağlı olarak farklı performanslar sergileyebilir. Kısacası tek doğru JOIN yöntemi şudur şeklinde birşey söylemek yanıltıcı olacaktır. Tabloların birleştirilmesinde perfomansı iyileştirecek en önemli konu tabloların ilişkili alanlar üzerinden sıralı olmasıdır.

SQL Server JOIN Türleri – II (LOOP, HASH, MERGE JOIN)” üzerine 2 düşünce

  1. İbrahim Sezen

    Sql Server konusunda bu şekilde detaya inen çok sınırlı kaynak var. Çok başarılı bir çalışma olmuş. Paylaşım için teşekkür ederim.

    Cevapla

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Time limit is exhausted. Please reload CAPTCHA.