Merge Join

Merge Join to operator planu wykonania łączący dwa posortowane zbiory wierszy przez ich równoległe przeglądanie.

Jak działa operator Merge Join

Merge Join jest algorytmem łączenia dwóch zbiorów wierszy na podstawie warunku równości lub innego warunku porządkującego, gdy dane wejściowe są uporządkowane według używanych kolumn. Operator otrzymuje dwa strumienie, nazywane zwykle wejściem zewnętrznym i wewnętrznym, a następnie przesuwa się po nich w sposób sekwencyjny. Porównuje bieżącą wartość klucza z pierwszego strumienia z bieżącą wartością klucza z drugiego. Jeżeli wartości są różne, operator może odrzucić wiersze z mniejszym kluczem i przejść do kolejnej pozycji. Jeżeli wartości są takie same, tworzy wynikowe kombinacje pasujących wierszy.

Przykładowo, przy łączeniu tabel Klienci i Zamówienia po kolumnie id_klienta oba wejścia powinny być posortowane według tej kolumny. Gdy operator napotka identyczny identyfikator w obu strumieniach, może połączyć klienta z jednym lub wieloma zamówieniami. Jeśli identyfikator występuje wielokrotnie po obu stronach, wynik obejmuje wszystkie odpowiednie pary, więc liczba wygenerowanych wierszy może być większa niż liczba wierszy w tabelach źródłowych. Kolejność przeglądania nie wymaga wielokrotnego wyszukiwania całych tabel, ponieważ operator korzysta z istniejącego porządku.

Warunek uporządkowania danych wejściowych

Najważniejszym warunkiem efektywnego działania Merge Join jest zgodność kolejności sortowania obu wejść z kluczem łączenia. Porządek musi uwzględniać kolumnę lub zestaw kolumn użyty w predykacie, a także kierunek sortowania. Jeśli łączenie odbywa się po kilku kolumnach, kolejność kolumn w sortowaniu ma znaczenie: porządek po kraj, miasto i kod nie jest równoważny porządkowi po miasto, kraj i kod. Operator planu wykonania może otrzymać już posortowane dane z indeksu albo z wcześniejszej części planu.

Jeżeli żadne źródło nie dostarcza wymaganego porządku, plan może zawierać dodatkową operację sortowania. Sortowanie zwiększa koszt wykonania, ponieważ wymaga odczytania danych, porównania wartości i często wykorzystania pamięci operacyjnej lub przestrzeni tymczasowej. Przy dużych zbiorach koszt ten może dominować nad samym przejściem Merge Join. Z tego powodu analiza planu wykonania powinna rozdzielać koszt operatora łączenia od kosztu przygotowania jego wejść. Sam fakt użycia Merge Join nie oznacza automatycznie, że całe zapytanie jest szybkie.

Obsługa powtórzeń, wartości NULL i różnych typów złączeń

Powtarzające się wartości klucza wymagają od operatora zapamiętania albo ponownego odczytania zakresu wierszy o tej samej wartości. Dla złączenia wewnętrznego wynik zawiera tylko kombinacje, dla których warunek łączenia jest spełniony. W przypadku złączenia lewego operator musi dodatkowo zachować wiersze z lewego wejścia, nawet gdy po prawej stronie nie ma odpowiadającej wartości. Wtedy kolumny prawego źródła są uzupełniane wartościami pustymi zgodnie z semantyką danego silnika i zapytania.

Wartość NULL nie jest zwykłym kluczem równym innemu NULL w typowym warunku porównania SQL. Wynika to z trójwartościowej logiki, w której porównanie z NULL daje wynik nieznany, a nie prawdę. Dlatego wiersze z pustą wartością klucza nie są łączone tak samo jak wiersze z identycznymi wartościami liczbowymi lub tekstowymi. Znaczenie mają również typy danych, reguły porównywania tekstu, wielkość liter, sortowanie zależne od ustawień oraz sposób traktowania wartości równoważnych. Niezgodność tych zasad między wejściami może wymusić konwersję, zmianę porządku albo wybór innego operatora.

Rola Merge Join w analizie planu wykonania

Obecność Merge Join w planie wykonania wskazuje, że silnik uznał uporządkowane przeglądanie obu źródeł za korzystne dla danego zapytania. Ocena może zależeć od szacowanej liczby wierszy, dostępnych indeksów, selektywności filtrów, kosztu sortowania oraz rodzaju złączenia. W planie warto sprawdzić, czy estymacje liczby wierszy są zbliżone do rzeczywistych, czy przed operatorem występują kosztowne sortowania i czy nie jest wykonywana niepotrzebna konwersja typów. Różnica między estymowaną a rzeczywistą liczbą wierszy może powodować wybór nieoptymalnej strategii.

Diagnostyka problemu nie polega na mechanicznym zastępowaniu Merge Join innym algorytmem. Należy przeanalizować predykat łączenia, indeksy, kolejność sortowania, filtry oraz statystyki opisujące dane. Wąskim gardłem może być odczyt z dysku, sortowanie, nadmiarowy transfer wierszy albo błędne założenie dotyczące rozkładu wartości. W środowisku serwisowym analiza planu wykonania pomaga ustalić, czy spowolnienie pochodzi z samego zapytania, struktury tabel, konfiguracji silnika bazy danych czy ograniczeń sprzętowych komputera, na którym wykonywane są obliczenia.