SQL Server Merge Join operator – jak to działa

Stosunkowo niedawno opisałem najprostszy z dostępnych algorytmów/operatorów złączenia wbudowanych w SQL Server – chodzi mianowicie o Nested Loops. dziś chciałbym kontynuować temat i przejść do kolejnego operatora tego typu, którym jest Merge Join – jego znajomość może okazać się kluczowa jeśli chodzi o poprawne zrozumienie planów wykonania i performance tuning.

Najważniejszą charakterystyką opisywanego algorytmu jest fakt, iż wymaga on aby oba wejścia do algorytmu były posortowane. Wymóg ten może być osiągnięty na dwojaki sposób – pierwszym z nich jest jawne posortowanie zestawu danych operatorem Sort (który prawie zawsze daje nam pole do optymalizacji), drugim z kolei jest istnieje odpowiedniego indeksu na kluczu złączenia, który zapewnia sortowanie danych. Oczywiście w momencie gdy zobaczymy operator Sort przed Merge Join powinniśmy na to zwrócić szczególną uwagę bo zapewne będzie on kosztowny, a łatwo go zastąpić odpowiednim indeksem. Ponadto Merge Join wymaga aby przynajmniej jeden warunek złączenia był połączony operatorem równości, tak więc gdy nasze zapytanie będzie działało na warunku podobnym do poniższego to nie ma możliwości wykorzystania Merge Join:

FROM
	[dbo].[PurchaseOrders] AS PO
INNER JOIN 
	[Purchasing].[PurchaseOrderLines] AS POL
	ON POL.PurchaseOrderID>=PO.PurchaseOrderID

Nawet próba wymuszania tego algorytmu zakończy się błędem:

Msg 8622, Level 16, State 1, Line 4
Query processor could not produce a query plan because of the hints defined in this query. 
Resubmit the query without specifying any hints and without using SET FORCEPLAN.

Schemat działania Merge Join przedstawmy na przykładzie – przypuśćmy, że mamy do dyspozycji dwa posortowane wejścia (tabele). Na naszej grafice Input A jest tak zwanym OUTER INPUT natomiast Input B to INNER INPUT. Algorytm bierze pierwszy wiersz z OUTER INPUT i skanuje INNER INPUT w poszukiwaniu pasujących wartości. Tak więc dla wartości 1 algorytm znalazł dwie wartości i je zwrócił – przechodząc dalej w momencie gdy natrafił na wartość 2 w INNER INPUT nie musi dalej jej skanować ze względu na fakt, iż dane są posortowane tj. nie  ma fizycznej możliwości, że znalezione zostaną wartości równe 1. Następnie poszukiwana jest wartość 2 w INNER TABLE i zwraca pasujące rekordy itd.

Sprawdźmy działanie operatora na konkretnym przykładzie zapytania – zanim jednak rozpoczniemy usuńmy indeks z naszej tabeli:

DROP INDEX [FK_Purchasing_PurchaseOrderLines_PurchaseOrderID] ON 
[Purchasing].[PurchaseOrderLines]

Następnie wykonajmy poniższe proste złączenie tabel bazy WideWorldImporters:

SELECT 
	PO.PurchaseOrderID,
	POL.PurchaseOrderLineID,
	PO.IsOrderFinalized,
	POL.IsOrderLineFinalized,
	POL.OrderedOuters 
FROM
	[Purchasing].[PurchaseOrders] AS PO
JOIN 
	[Purchasing].[PurchaseOrderLines] AS POL
	ON POL.PurchaseOrderID=PO.PurchaseOrderID

w rezultacie otrzymaliśmy następujący plan wykonania:

Jak możecie zauważyć optymalizator wybrał tutaj złączenie Hash Match ze względu na fakt, iż w tabeli Purchasing.PurchaseOrderLines nie ma żadnego indeksu, który zapewnił by posortowany zestaw danych po kolumnie PurchaseOrderID. Oczywiście możemy wymusić wykorzystanie operatora Merge Join odpowiednim hintem OPTION(MERGE JOIN) lub też wpisując w składnię INNER MERGE JOIN (uwaga! ten drugi zapis jest jednoznaczny z hintem FORCE ORDER wymuszającym kolejność OUTER INPUT i INNER INPUT na takie jak wskazaliśmy w zapytaniu):

SELECT 
	PO.PurchaseOrderID,
	POL.PurchaseOrderLineID,
	PO.IsOrderFinalized,
	POL.IsOrderLineFinalized,
	POL.OrderedOuters 
FROM
	[Purchasing].[PurchaseOrders] AS PO
JOIN 
	[Purchasing].[PurchaseOrderLines] AS POL
	ON POL.PurchaseOrderID=PO.PurchaseOrderID
OPTION (MERGE JOIN)

Tym razem w naszym planie pojawił się pożądany operator – jednakże pojawił się również kosztowny operator Sort:

Jednakże koszt takiego zapytania jest dużo wyższy niż tego z Hash Match i wymuszanie operatora złączenia nie jest najlepszym pomysłem. Stwórzmy zatem indeks, który posortuje nam dane po kluczu złączenia i dodatkowo będzie indeksem pokrywającym dla naszego zapytania (czyli będzie zawierał pożądane kolumny):

CREATE NONCLUSTERED INDEX [FK_Purchasing_PurchaseOrderLines_PurchaseOrderID] 
ON [Purchasing].[PurchaseOrderLines]
(
	[PurchaseOrderID] ASC
)
INCLUDE (OrderedOuters,IsOrderLineFinalized )

wykonajmy nasze zapytanie ponownie, tym razem bez hinta i podejrzyjmy plan wykonania:

SELECT 
	PO.PurchaseOrderID,
	POL.PurchaseOrderLineID,
	PO.IsOrderFinalized,
	POL.IsOrderLineFinalized,
	POL.OrderedOuters 
FROM
	[Purchasing].[PurchaseOrders] AS PO
JOIN 
	[Purchasing].[PurchaseOrderLines] AS POL
	ON POL.PurchaseOrderID=PO.PurchaseOrderID

Wybrany został Merge Join gdyż zapewniliśmy to, że oba wejścia są posortowane. Technika zamiany operatorów złączenia na Merge Join bardzo często jest jedną z metod optymalizacyjnych dających bardzo dobre efekty. Oczywiście to nie wszystko na co powinniśmy zwrócić uwagę przy operatorze Merge Join – istnieje jeszcze jeden szczególny przypadek – aby go zobrazować stwórzmy sobie kopię jednej z naszej tabel:

SELECT * INTO dbo.PurchaseOrders FROM [Purchasing].[PurchaseOrders]

Powstała tabela jest stertą – stwórzmy sobie na niej CLUSTERED INDEX (zwróćcie uwagę na fakt, iż jest to indeks zgrupowany, a nie PRIMARY KEY – czyli może zawierać duplikaty):

CREATE CLUSTERED INDEX IX_PK_PurchaseOrders  ON dbo.PurchaseOrders
(PurchaseOrderID)

Następnie włączymy statystyki IO oraz wymuśmy MERGE JOIN do naszej nowopowstałej tabeli:

SET STATISTICS IO ON
GO

SELECT 
	PO.PurchaseOrderID,
	POL.PurchaseOrderLineID,
	PO.IsOrderFinalized,
	POL.IsOrderLineFinalized,
	POL.OrderedOuters 
FROM
	[dbo].[PurchaseOrders] AS PO
INNER JOIN 
	[Purchasing].[PurchaseOrderLines] AS POL
	ON POL.PurchaseOrderID=PO.PurchaseOrderID
OPTION (MERGE JOIN)

To co jest najciekawsze pojawia się w statystykach IO:

Mamy odczyty z naszych dwóch tabel… oraz z tworu o nazwie Worktable! Czym jest ten twór? Jest to tabela pomocnicza tworzona w bazie systemowej tempdb potrzebna przy złączeniu Merge Join obsługującym złączenia wiele do wielu. Możecie zadać pytanie skąd wziął się scenariusz wiele do wielu skoro pomiędzy dbo.PurchaseOrders a Purchasing.PurchaseOrderLines zachodzi relacja jeden do wielu? Odpowiedź jest prosta – optymalizator tego nie wie i nie jest w stanie wydedukować – nie ma zdefiniowanych pomiędzy tymi tabelami żadnych constraintów, a indeks który założyliśmy nie jest unikalny. Aby rozwiązać ten problem optymalizator musi posłużyć się właśnie tabelą roboczą (Worktable). O jej istnieniu możemy się dowiedzieć ze statystyk IO, ale również plan zapytania posiada pewną flagę pomocną w identyfikacji tego typu scenariuszy – po najechaniu myszą na operator Merge Join w menu kontekstowym zobaczymy flagę Many to Many – gdy jest ona zaznaczona na True to mamy pewność, że optymalizator nie ma powodów aby twierdzić, że pomiędzy tabelami zachodzi relacja jeden do wielu – być może jest to oznaka brakującego constraint’a lub też odpowiedniego indeksu unikalnego.

Warto ten przypadek mieć w tyle głowy ze względu na fakt, iż w niektórych przypadkach może on być problemem – szczególnie gdy tempdb jest mocno obciążona.

Jak podejść do implementacji złączenia MERGE JOIN w naszych zapytaniach? Pamiętajmy, że nie ma złych algorytmów złączenia – po prostu jedne zachowują się lepiej inne gorzej w konkretnych scenariuszach. Osobiście polecam podczas testowania użyć sobie hinta OPTION (MERGE JOIN) i sprawdzić w planie zapytania w którym miejscu brakuje nam posortowanego rezultatu – być może po stworzeniu indeksu optymalizator wybierze MERGE JOIN jako odpowiednią metodą złączenia. Oczywiście czasem mimo istniejących wydawałoby się idealnych warunków dla opisywanego algorytmu w planie wykonania zobaczymy HASH MATCH – warto upewnić się wtedy czy mamy do dyspozycji aktualne statystyki – jeśli tak to estymowany koszt algorytmu HASH MATCH może w rzeczywistości być lepszym wyborem dla naszego zapytania.