Hash Join

Hash Join to algorytm łączenia tabel wykorzystujący funkcję skrótu do dopasowania wierszy o wspólnej wartości klucza.

Na czym polega algorytm Hash Join

Hash Join to algorytm łączenia dwóch zbiorów danych na podstawie warunku równości wartości klucza. W najczęściej stosowanej odmianie silnik wybiera jeden ze zbiorów jako źródło budowy struktury haszującej, a następnie odczytuje drugi zbiór i wyszukuje w niej odpowiadające wpisy. Dzięki temu porównanie nie musi polegać na zestawianiu każdego wiersza pierwszej tabeli z każdym wierszem drugiej tabeli. Dla warunku takiego jak A.id = B.id funkcja skrótu przekształca wartość klucza w położenie w tablicy haszującej.

Przykładowe zapytanie może łączyć tabelę zamówień z tabelą klientów na podstawie identyfikatora klienta. Algorytm buduje tablicę dla jednej strony połączenia, zwykle tej mniejszej, a potem sprawdza kolejne identyfikatory z drugiej strony. Jeżeli wartość znajduje się w odpowiednim koszyku haszującym, silnik porównuje ją z zapisanymi tam kluczami i przekazuje pasujące pary do dalszego wykonania zapytania. Funkcja skrótu nie zastępuje końcowego porównania wartości, ponieważ różne klucze mogą trafić do tego samego koszyka, czyli spowodować kolizję.

Etapy budowy i wyszukiwania dopasowań

W klasycznym przebiegu Hash Join można wyróżnić fazę budowania oraz fazę sondowania. W fazie budowania silnik odczytuje wybrany zbiór, oblicza skrót dla klucza każdego wiersza i umieszcza wiersz w odpowiednim koszyku. W fazie sondowania odczytywane są wiersze drugiego zbioru. Dla każdego z nich obliczany jest skrót, a następnie sprawdzany jest odpowiadający koszyk w strukturze utworzonej wcześniej. Dopiero po znalezieniu kandydatów następuje dokładne sprawdzenie warunku łączenia.

Wybór strony budowanej ma znaczenie dla zużycia pamięci. Jeżeli cała tablica haszująca mieści się w przydzielonym obszarze roboczym, algorytm może działać bez dodatkowych operacji dyskowych. Gdy rozmiar danych przekracza dostępny budżet pamięci, wykonanie może zostać podzielone na partycje. Wiersze są wtedy grupowane według części wartości skrótu i tymczasowo zapisywane, aby kolejne fragmenty mogły być przetwarzane osobno. W praktyce zwiększa to liczbę operacji wejścia-wyjścia i może wydłużyć czas zapytania.

Warunki, w których Hash Join jest użyteczny

Hash Join jest szczególnie przydatny przy dużych zbiorach danych oraz przy łączeniach wykorzystujących równość kluczy. Jego działanie nie wymaga uporządkowania obu wejść według kolumny łączenia, dlatego może być korzystne wtedy, gdy sortowanie byłoby kosztowne albo gdy dane są odczytywane bez odpowiednich struktur indeksowych. Algorytm nie jest jednak uniwersalnym rozwiązaniem dla każdego rodzaju warunku. Klasyczna odmiana nie służy bezpośrednio do warunków zakresowych, takich jak A.data < B.data lub A.cena BETWEEN B.min_cena AND B.max_cena.

Na wybór Hash Join wpływa między innymi przewidywana liczba wierszy, rozkład wartości klucza, dostępna pamięć, selektywność filtrów oraz sposób dostarczenia danych przez pozostałe elementy planu wykonania. Nierównomierny rozkład wartości może powodować, że wiele wierszy trafi do tych samych koszyków. Zjawisko to nazywa się nierównowagą lub koncentracją kluczy i może zmniejszyć korzyść z wyszukiwania haszującego. Istotne są także wartości puste. W zależności od rodzaju połączenia i reguł porównywania NULL może nie zostać uznany za równy innemu NULL, dlatego wynik trzeba interpretować zgodnie z semantyką użytego warunku SQL.

Jak rozpoznać działanie Hash Join w planie zapytania

Informacji o zastosowanym algorytmie szuka się w planie wykonania zapytania. Nazwa operatora może być zapisana jako Hash Join albo jako bardziej szczegółowy wariant wskazujący rodzaj połączenia, na przykład inner, left lub full. W planie należy sprawdzić, który operator dostarcza dane do fazy budowania, a który do fazy sondowania. Warto porównać przewidywaną i rzeczywistą liczbę wierszy, zużycie pamięci, operacje zapisu do obszaru tymczasowego oraz liczbę odczytanych rekordów.

Jeżeli Hash Join wykonuje się wolno, sama obecność tego operatora nie dowodzi błędu. Przyczyną może być nieaktualna statystyka, zły szacunek liczby wierszy, brak selektywnego filtra, duża liczba kolizji, niedopasowany typ danych klucza albo niewystarczająca pamięć robocza. Diagnostyka powinna obejmować pełne zapytanie, plan wykonania oraz rzeczywisty rozmiar danych. Należy również sprawdzić, czy warunek łączenia nie powoduje niezamierzonego zwielokrotnienia wyników, na przykład przez połączenie relacji wiele-do-wielu. Hash Join jest mechanizmem optymalizacji wykonania, a nie gwarancją poprawności logicznej zapytania; poprawność wyniku nadal zależy od właściwego warunku, relacji między tabelami i oczekiwanego znaczenia danych.