Algorytmy złączeń: Nested Loop, Hash, Merge

Znają już Państwo składnię INNER JOIN. Podczas rozmowy na poziomie senior rekruterzy pytają, w jaki sposób baza danych fizycznie wykonuje złączenie. Istnieją trzy algorytmy:

• Nested Loop Join
• Hash Join
• Merge Join (sortowanie i scalanie)

Logiczny typ złączenia (INNER, LEFT) jest niezależny od algorytmu. Planista wybiera algorytm na podstawie rozmiarów tabel, indeksów i kolejności sortowania. Zrozumienie, kiedy każdy z nich sprawdza się najlepiej, jest sednem tej lekcji.

Nested Loop to najprostszy algorytm: dla każdego wiersza tabeli zewnętrznej skanuje tabelę wewnętrzną w poszukiwaniu dopasowań. W pseudokodzie są to dwie pętle, jedna wewnątrz drugiej.

W naiwnym ujęciu ma złożoność O(outer * inner), co jest fatalne w przypadku dużych tabel. Staje się jednak bardzo wydajne, gdy po stronie wewnętrznej znajduje się indeks na kluczu złączenia: każdy wiersz zewnętrzny powoduje szybkie wyszukanie w indeksie zamiast pełnego skanowania tabeli wewnętrznej.

Planista najchętniej wybiera ten algorytm, gdy tabela zewnętrzna jest mała, a wewnętrzna kolumna złączenia ma indeks.

Charakterystyczną cechą złączenia z użyciem zagnieżdżonych pętli jest loops przy węźle wewnętrznym. Przykład pokazuje loops=3, ponieważ strona zewnętrzna zwróciła 3 wiersze, więc wewnętrzny skan indeksu uruchomiono 3 razy.

Problem pojawia się, gdy strona zewnętrzna jest duża. Jeśli zwróci 2 miliony wierszy, strona wewnętrzna zostanie uruchomiona 2 miliony razy. Nawet szybkie wyszukanie trwające 0.01ms zajmie wtedy 20 sekund.

Podczas rozmowy warto wskazać każde złączenie Nested Loop, w którym wartość loops jest duża, a tabela wewnętrzna nie ma dobrego indeksu — to właśnie oznacza wolne zapytanie.

Hash Join dobrze radzi sobie z dużymi, nieposortowanymi tabelami. Działa w dwóch fazach:

• Budowanie: odczytanie mniejszej tabeli i załadowanie jej do znajdującej się w pamięci tablicy haszującej, której kluczem jest kolumna złączenia.
• Sondowanie: skanowanie większej tabeli; dla każdego wiersza obliczany jest skrót klucza złączenia, a następnie wykonywane jest wyszukanie w tablicy haszującej.

Każda tabela jest odczytywana tylko raz, co daje w przybliżeniu O(outer + inner). Nie są potrzebne indeksy ani posortowane dane wejściowe, dlatego ten algorytm dominuje w dużych analitycznych złączeniach opartych na warunkach równości.

W przypadku złączeń haszujących należy wspomnieć o dwóch kwestiach:

• Działają one wyłącznie dla warunków złączenia opartych na równości (a.id = b.id). Warunek zakresowy, taki jak a.x < b.y, nie może zostać zrealizowany za pomocą Hash Join.
• Strona budowania musi zmieścić się w work_mem. Jeśli tak się nie stanie, Postgres zapisze partie na dysku (widoczne będą Batches: > 1 i wykorzystanie dysku), co znacznie spowolni złączenie.

Hash Join z ogromną stroną budowania i niewielką wartością work_mem to rzeczywisty problem wydajnościowy, który należy wskazać.

Merge Join (sortowanie i scalanie) wymaga, aby oba wejścia były posortowane według klucza złączenia. Następnie przechodzi przez oba wejścia równolegle, podobnie jak przy scalaniu dwóch posortowanych list, przesuwając ten wskaźnik, który znajduje się za drugim.

Jest wydajne, gdy dane wejściowe są już posortowane, na przykład pochodzą bezpośrednio z indeksu uporządkowanego według klucza, ponieważ nie trzeba wtedy wykonywać sortowania. Obsługuje także złączenia zakresowe i nierównościowe, w przeciwieństwie do Hash Join.

Jeśli dane wejściowe nie są wstępnie posortowane, planista dodaje jawne węzły Sort, a koszt sortowania może sprawić, że Hash Join będzie tańszy.

Warto zapamiętać, kiedy każdy algorytm sprawdza się najlepiej:

• Nested Loop — mała tabela zewnętrzna i indeksowany klucz złączenia po stronie wewnętrznej; to także jedyna opcja dla złączeń innych niż równościowe bez posortowanych danych wejściowych.
• Hash Join — duże, nieposortowane tabele połączone warunkiem równości; indeksy nie są potrzebne.
• Merge Join — oba wejścia są już posortowane według klucza (często dzięki indeksom) albo wykonywane jest złączenie zakresowe; świetnie sprawdza się w przypadku bardzo dużych, wstępnie posortowanych zbiorów.

Planista szacuje koszt każdego algorytmu i wybiera najtańszy na podstawie swoich szacunków liczby wierszy.

Zużycie zasobów znacznie się różni, a rekruterzy sprawdzają znajomość tych różnic:

• Nested Loop — minimalne zużycie pamięci; koszt jest zdominowany przez powtarzane wyszukania po stronie wewnętrznej.
• Hash Join — wymaga pamięci na tablicę haszującą; jeśli jest ona zbyt duża, dane są zapisywane na dysku.
• Merge Join — samo scalanie jest tanie, ale wcześniejsze sortowanie może być kosztowne; sortowanie również korzysta z work_mem i może zapisywać dane na dysku.

Zwiększenie wartości work_mem może więc zmienić wolne złączenie haszujące lub sortowanie, które zapisuje dane na dysku, w operację wykonywaną w pamięci — to konkretna odpowiedź dotycząca optymalizacji.

Klasyczny scenariusz: zapytanie działało szybko w środowisku deweloperskim, ale wolno w produkcji. Plan pokazuje złączenie Nested Loop z wartością loops=3000000.

Planista zaniżył liczbę wierszy po stronie zewnętrznej (nieaktualne statystyki wskazywały 3 wiersze, podczas gdy w rzeczywistości było ich 3 miliony), więc wybrał złączenie Nested Loop. Przy poprawnych statystykach wybrałby Hash Join.

Odpowiedź podczas rozmowy: należy uruchomić ANALYZE, aby estymacja była poprawna; planista przełączy się wtedy na Hash Join, a zapytanie znacznie przyspieszy.

Zwykle nie należy wymuszać algorytmów, ale podczas testów można je wymuszać w celu porównania. Postgres udostępnia przełączniki dla poszczególnych metod:

SET enable_nestloop = off; oraz analogiczne przełączniki enable_hashjoin i enable_mergejoin. Należy wyłączyć jeden z nich, ponownie uruchomić EXPLAIN ANALYZE i sprawdzić, czy alternatywa rzeczywiście działa szybciej.

Właściwe rozwiązania pozostają takie same: aktualne statystyki, odpowiednie indeksy, wystarczająca wartość work_mem i selektywne predykaty. Wymuszanie służy wyłącznie diagnostyce.

Zastosujmy te zasady do obciążenia analitycznego, w którym dwie duże tabele faktów i wymiarów są łączone po identyfikatorze:

• Jeśli tabela wymiarów mieści się w pamięci, należy oczekiwać Hash Join, często najlepszego rozwiązania.
• Jeśli oba wejścia pochodzą z indeksów już posortowane, Merge Join może uniknąć budowania tablicy haszującej.
• Nested Loop w takiej sytuacji byłby sygnałem ostrzegawczym, zwykle spowodowanym błędną estymacją.

Odczytanie, który algorytm wybrał planista, oraz ocena, czy powinien był wybrać właśnie ten algorytm, to dokładnie umiejętność na poziomie seniora sprawdzana w tych pytaniach.

Łączą Państwo dwie duże, nieposortowane tabele na podstawie warunku równości a.id = b.id; żadna z nich nie ma użytecznego indeksu, a statystyki są poprawne. Jaki algorytm złączenia najprawdopodobniej wybierze planista?

Trzy algorytmy złączeń:

• Nested Loop — dla każdego wiersza zewnętrznego wykonywane jest wyszukanie po stronie wewnętrznej; świetnie sprawdza się przy małej tabeli zewnętrznej i indeksowanym kluczu wewnętrznym, ale jest niebezpieczny, gdy wartość loops jest ogromna.
• Hash Join — budowanie i sondowanie; najlepszy w przypadku dużych, nieposortowanych złączeń równościowych, ograniczony do równości i limitowany przez work_mem.
• Merge Join — równoległe przechodzenie po posortowanych danych wejściowych; idealny, gdy dane są już posortowane, lub w przypadku złączeń zakresowych.

Planista dokonuje wyboru na podstawie kosztu i statystyk. Zaskakujące złączenie Nested Loop z ogromną liczbą iteracji niemal zawsze oznacza błędną estymację liczby wierszy — należy poprawić statystyki.