SQL Server Hash Match – jak to działa

Nadszedł czas opisać ostatni algorytm złączenia dostępny w SQL Server, którym po Nested Loops oraz Merge Join jest Hash Match. Pierwszy z nich sprawdza się doskonale przy małych zbiorach danych, drugi to świetny algorytm łączący posortowane zbiory danych, bohater niniejszego artykułu sprawdza się z kolei bardzo dobrze przy dużych, nieposortowanych zbiorach wejściowych. Jak to wszystko działa? Postaram się to wytłumaczyć w ramach niniejszego artykułu.

Operacja Hash match wewnętrznie składa się z dwóch faz tj. build oraz probe. Podczas fazy build Hash match skanuje jedno z wejść i każdą wartość zamienia na hash i na tej podstawie buduje tabele z wygenerowanymi właśnie hashami. Hash to wynik działania pewnej funkcji hashującej, która zamienia dane na hash. O tym jaka funkcja jest wykorzystywana w SQL Server nie wiemy gdyż nie została ona udokumentowana. Możemy o niej powiedzieć to co o innych funkcjach tego typu – że jej działanie jest jednokierunkowe tzn. nie ma możliwości odkodowania oryginalnej wartości z hasha. Ponadto można powiedzieć, że jest ona funkcją w pełni deterministyczną tzn. ta sama wartość poddana funkcji hashującej da zawsze ten sam hash. Dzięki tym właściwościom hashowanie świetnie sprawdza się jako jako część algorytmu złączenia.

Podczas przetwarzania fazy Build otrzymany z wartości hash definiuje do którego bucketu trafiają wiersze. Bucket to nic innego jak po prostu kontener, jeśli dwie wartości poddane funkcji hashującej dają ten sam hash to trafią do tego samego bucketu. Faza probe pobiera wiersze z drugiego wejścia i przyporządkowuje za pomocą tej samej funkcji hashującej poszczególne wiersze do konkretnych bucketów.

Na poniższym rysunku można zobaczyć dwie tabele, jedna z nich ze 100 wierszami została przyporządkowana jako Probe Input, druga z 50 wierszami  została zaklasyfikowana jako build input i na jej podstawie zbudowana została tabela hashy. W znakomitej większości przypadków jako build input będzie wybrana mniejsza tabela.

 

Zarówno w czasie budowania tabeli hashy jaki i porównywania wartości z wejścia probe każdy wiersz odczytywany jest tylko raz. Oczywiście Hash Join będzie operatorem częściowo blokującym ponieważ na moment budowania tabeli hashy musi oni zebrać wszystkie wartości nie przepuszczając przy tym żadnego z nich. Możliwe jest wykonanie dodatkowego porównania pomiędzy wejściami w ramach pojedynczego bucketu gdyż funkcja hashująca nie musi dawać unikalnej wartości hasha. W momencie gdy wiele wartości ląduje w tym samym buckecie mówimy o tzw. hash collision. Przypuśćmy, że w warunku WHERE wpiszemy a.KEY=b.KEY AND a.Id>b.Id w tym przypadku druga część warunku złączenia będzie wykonana właśnie jako dodatkowe porównanie w ramach bucketu. W tym miejscu warto zaznaczyć, że aby algorytm hash join mógł być użyty to musimy w warunku złączenia podać minimum jeden warunek równości w innym przypadku jedyną możliwością złączenia będzie nested loops.

Kolejnym bardzo istotnym aspektem związanym z Hash Match jest fakt, że tabela hashy budowana jest w pamięci i wymaga przyznania odpowiedniego grantu pamięci (memory grant). Wielkość tego grantu zależy oczywiście od estymacji ilości wierszy, w momencie gdy estymaty są nieprawidłowe i ilość przydzielonej pamięci jest za mała następuje zrzut danych do tempdb, co jak możecie się domyślać negatywnie wpływa na wydajność całego algorytmu. Oczywiście możemy monitorować zrzuty do tempdb używając np. Extended Events w poszukiwaniu zdarzania Hash Warning co postaram się zademonstrować w dalszej części artykułu.

Ogólnie rzecz biorąc wyróżniamy trzy rodzaje hash joinów:

• In-memory hash join – tabela hashy w całości przechowywana jest w zaalokowanej pamięci, a wiersze z probe input porównywane są z tabelą hashy wiersz po wierszu.
• Grace hash join – tabela hashy nie mieści się w całości w zaalokowanej pamięci. Hash join wykonywany w kilku krokach i każdy krok posiada własną fazę build i probe. Wejścia są niejako partycjonowane poprzez hash z hashy. Porównywanie następuje najpierw poprzez powstałe “partycje” następnie przez buckety, a potem wiersz po wierszu. Bieżąca “partycja” używana do porównania jest przechowywana w pamięci – pozostałe są przechowywane na dysku.
• Recursive hash join – powstaje w momencie gdy nawet “partycje” mimo, że są mniejsze od oryginalnego zbioru, to nadal nie mieszczą się w pamięci. W takiej sytuacji SQL Server próbuje tworzyć podpartycje i powtarza czynność. To dzielenie na mniejsze części może odbywać się wielokrotnie i każde kolejne jest kolejnym poziomem zagłębienia. Dzieje się tak aż partycje zmieszczą się w pamięci lub gdy osiągnięty został limit zagnieżdżania. W momencie osiągnięcia limitu następuje tzw. hash bailout czyli przełączenie na inny plan aby połączyć dane ( co można z wydajnościowego punktu widzenia traktować jako z jedno z najgorszych możliwych przypadków).

W momencie optymalizacji nie jest możliwe przewidzenie, który rodzaj hash join będzie wykonywany. Zawsze przetwarzanie rozpoczyna się od In-memory hash join i w razie potrzeby przechodzi się do Grace i Recursive. W sam algorytm wbudowana jest pewna optymalizacja nazwana role reversal, która odwraca wejścia build i probe jeśli do build na początku błędnie został wybrany większy zestaw danych ( zadziała ona wtedy gdy wystąpi minimum jeden zrzut na dysk).

Zobaczmy Hash Join w akcji – wykonajmy poniższe zapytanie na WideWorldImportersDW:

SELECT * FROM Fact.Sale AS F
JOIN Dimension.Customer AS DC
ON DC.[Customer Key]=F.[Customer Key]

Plan wykonania powyższego zapytania przedstawia się następująco:

Ze względu na fakt, iż tabela faktów zawiera dosyć dużo wierszy to optymalizator wybrał Hash Match jako algorytm złączenia. Wspomniałem wcześniej, że oba zestawy danych będą odczytane tylko raz – możemy to udowodnić sprawdzając właściwości obu operatorów Index Scan:

Skąd wiemy, która zestaw został wybrany do której fazy? Sprawdźmy właściwości operatora Hash match:

Teraz już wiemy, że do budowania tabeli hashy wybrany został [Customer Key] z tabeli Dimension.Customer, a klucz złączenia z tabeli Fact.Sale będzie w fazie Probe porównywany z tabelą hashy. Aby móc przeprowadzić operacje złączenia opisywanym algorytmem musi zostać nadany grant pamięci, który możemy sprawdzić we właściwościach operatora SELECT:

W porządku, wiemy już jak znaleźć podstawowe informacje na temat Hash joina. Zamieszajmy teraz nieco i zmieńmy statystyki naszej tabeli Dimension.Customer – zróbmy tak aby SQL myślał, że znajduje się tam tylko jeden wiersz:

UPDATE STATISTICS Dimension.Customer 
WITH ROWCOUNT = 1, 
PAGECOUNT = 1
GO

Po wykonaniu zapytania otrzymaliśmy następujący plan:

Statystyki mają ogromny wpływ na wydajność i powyższy plan to potwierdza. SQL myśląc, że ma do czynienia z jednym wierszem w tabeli wymiaru wolał wykonać serię Nested Loops i Key Lookup niż budować tabele hashy co w rzeczywistości było dużo wolniejszym algorytmem wykonania zapytania, jednakże najmniej kosztownym z punktu widzenia estymacji. Zaktualizujmy teraz statystyki zawyżając liczbę wierszy w tabeli klientów:

UPDATE STATISTICS Dimension.Customer 
WITH ROWCOUNT = 1000, 
PAGECOUNT = 10000
GO

Zwiększona ilość wierszy powiększyła memory grant niemal o połowę:

Zbyt duży memory grant nie jest może tak “zabójczy” jak zbyt mały grant jednakże marnotrawstwo pamięci nigdy nie jest mile widziane. Oczywiście nie jest tak, że grant będzie rósł w nieskończoność – możemy kontrolować maksymalną ilość pamięci jaką można przydzielić do pojedynczego zapytania, ale o tym powiemy sobie innym razem.

Do tej pory mieliśmy do czynienia z Hash joinami typu in-memory – mimo nieprecyzyjnych estymatów tabela hashy mieściła się w pamięci. Spróbujmy teraz wywołać mniej korzystną sytuację tj. wywołajmy zrzuty do tempdb. Aby to zrobić stwórzmy sobie tabelę tymczasową, która będzie przechowywała 30 kopii oryginalnej tabeli Dimension.Customer i użyjmy jej w złączeniu z tabelą faktów:

drop table #tmp

select * into #tmp FROM Dimension.Customer
GO
INSERT INTO #tmp 
SELECT * FROM Dimension.Customer
GO 29

UPDATE STATISTICS #tmp
WITH ROWCOUNT = 50, 
PAGECOUNT = 1000
GO

SELECT * FROM Fact.Sale AS F
JOIN #tmp AS DC
ON DC.[Customer Key]=F.[Customer Key]
OPTION (RECOMPILE)

W wyniku działania powyższego zapytania otrzymaliśmy następujący plan zapytania z pięknym wykrzyknikiem przy Hash Match ( w tym miejscu warto wspomnieć o tym, że informacja tego typu jest dostępna na planie zapytania stosunkowo niedawno – wcześniej mogliśmy śledzić zrzuty do tempdb za pomocą Extended Events czy też SQL Profilera):

Szczegóły na temat ostrzeżenia, które otrzymaliśmy możemy znaleźć oczywiście we właściwościach. Dowiadujemy się tam, że nastąpił zrzut do tempdb o poziomie 1:

Co to oznacza? Przekonajmy się zakładając sesję Extended Events gdzie powinniśmy otrzymać nieco więcej informacji:

CREATE EVENT SESSION [Hash] ON SERVER 
ADD EVENT sqlserver.hash_warning(
    ACTION(package0.event_sequence,sqlserver.database_id,
sqlserver.database_name,sqlserver.nt_username,sqlserver.sql_text))
WITH (MAX_MEMORY=4096 KB,EVENT_RETENTION_MODE=ALLOW_SINGLE_EVENT_LOSS,
MAX_DISPATCH_LATENCY=30 SECONDS,MAX_EVENT_SIZE=0 KB,
MEMORY_PARTITION_MODE=NONE,TRACK_CAUSALITY=OFF,STARTUP_STATE=OFF)
GO

Po wykonaniu tego zapytania raz jeszcze otrzymaliśmy następujące informacje z naszej sesji:

Level, który mieliśmy wcześniej oznaczał recursion_level czyli ile razy podczas fazy build nasz zestaw musiał być dzielony na partycje aby wykonać operację hash join.Oczywiście poziomów może być bardzo wiele, ale nie więcej niż maksymalny dostępny poziom. Kolumna hash_warning_type wskaże nam czy nastąpił podział na partycje czy hash bailout. Ponadto możemy zobaczyć kilka dodatkowych, użytecznych informacji jak np. ilość zapisów do tempdb.

Z tego co widać powyżej można powiedzieć, że zrzuty na dysk mogą całkowicie zabić wydajność zapytania. Dlatego też warto monitorować tego typu rzeczy, a jak już się na nie natkniemy to możemy przedsięwziąć konkretne kroki np.:

• sprawdzić czy grant pamięci był zbyt mały ze względu na złe statystyki czy też na memory pressure
• upewnić się, że istnieją statystyki na kolumnach złączenia
• upewnić się, że statystyki na tych kolumnach są aktualne
• jeżeli nie ma możliwości zwiększenia grantu pamięci spróbować dostosować strukturę aby można było użyć np. Merge Join jeśli to możliwe

Oczywiście to jeszcze nie wszystko! Jakiś czas temu opisywałem Residual Predicates – w Hash Match też mogą one wystąpić jako tzw. Probe Residual. Cały mechanizm polega to na tym, że następuje dodatkowa filtracja występująca zaraz po złączeniu, która może wpłynąć na wydajność naszego zapytania. Aby zobrazować ten mechanizm wykonamy poniższe zapytanie – przy okazji możecie zauważyć w jaki sposób można wymusić złączenie tego typu można użyć słowa kluczowego HASH:

SELECT DP.* FROM Fact.Sale AS F 
INNER HASH JOIN Dimension.[Stock Item] AS DP
ON DP.[Stock Item Key]=F.[Stock Item Key]
AND DP.[Unit Price]-F.[Unit Price]=0

Złączenie nastąpiło po dwóch kolumnach z czego Stock Item Key został użyty jako hash, a Unit Price występuje właśnie jako Probe Residual:

Predykaty rezydualne w tym wypadku pojawią się wtedy gdy nasz warunek filtrujący jest non-SARG czyli nie jest napisany w sposób optymalny i dodatkowo angażuję kolumny z obu tabel  (jeżeli filtrował by tylko jedną tabelę to z dużym prawdopodobieństwem trafił by na wcześniejszą część planu). Naprawa powyższego zapytania powinna być stosunkowo prosta i wygląda tak:

SELECT DP.* FROM Fact.Sale AS F 
INNER HASH JOIN Dimension.[Stock Item] AS DP 
ON DP.[Stock Item Key]=F.[Stock Item Key] 
AND DP.[Unit Price]=F.[Unit Price]

W bardzo wielu przypadkach probe residual nie będzie problemem bo ilość wierszy do przeskanowania po złączeniu nie będzie duża ale czasem może to być wąskie gardło naszego zapytania.

Jak widać nawet prosty z pozoru join może nieść ze sobą wiele komplikacji i pułapek szczególnie jeśli optymalizator wybierze  do wykonania tego zadania operator Hash Match. Na szczęście problem niedopasowanych grantów pamięci oraz algorytmów złączenia został w dużej mierze zniwelowany w SQL Server 2017, które przynosi ze sobą znaczne zmiany w tym zakresie – być może w przyszłości pokuszę się o opisanie tych mechanizmów. Na ten moment dziękuję za zapoznanie się z tekstem i mam nadzieję, że był przydatny w zrozumieniu tego niezwykle ważnego algorytmu.