Sort Merge Join w Oracle

SORT MERGE JOIN jest typem łączenia posortowanych danych. Ten sposób łączenia tabel ma sporo wspólnego z nested loops join jednak w pewnych sytuacjach potrafi być znacznie szybszy. W tym kursie opiszę sposób działania sort merge join oraz pokażę kiedy optymalizator wybierze go jako optymalny sposób łączenia dwóch tabel.

Ten kurs jest częścią Kurs Oracle SQL

W tym kursie opiszę:

• Jak działa SORT MERGE JOIN
• Przykład działania SORT MERGE JOIN
• Przedstawię przykłady wywołania SORT MERGE JOIN wraz z planami
• Pokażę Hint do wymuszenia SORT MERGE JOIN
• Podsumowanie

Działanie SORT MERGE JOIN

SORT MERGE JOIN jest łączeniem dwóch posortowanych zestawów danych. Ten sposób łączenia tabel składa się z dwóch operacji które składają się na operację SORT MERGE JOIN:

• SORT JOIN jest to operacja w której baza danych sortuje zestawy danych. Jeśli istnieją indeksy, baza danych może uniknąć sortowania pierwszego zestawu danych jednak zawsze sortuje drugi zestaw danych, niezależnie od indeksów.
• MERGE JOIN gdy oba zestawy danych są już posortowane baza danych rozpoczyna ich łączenie. Operacja MERGE JOIN jest specyficznym i zoptymalizowanym sposobem nested loops join.

Operacja MERGE JOIN polega na porównywaniu dwóch posortowanych zestawów. Baza danych ustawia na obu z nich znacznik na pierwszym rekordzie. Jeżeli wartości są zgodne z warunkiem złączenia to rekord jest zwracany do wyniku. Następnie indeks jednej strony przesuwa się na kolejny rekord i porównuje wartości. Jeżeli nie są zgodne to albo porusza pierwszym znacznikiem albo drugim w zależności od warunku złączenia. Dokładny opis algorytmu przedstawiłem w kolejnym punkcie.

Baza danych wybierze SORT MERGE JOIN w sytuacji gdy:

• Warunek łączenia między dwiema tabelami nie jest warunkiem równoważnym, to znaczy stosuje warunek nierówności, taki jak <, <=, > lub> =.
• Wykonujemy operację sortowania na kolumnie z warunku złączenia
• Istnieją indeksy na kolumnach łączenia. Nie jest to warunek konieczny ale zwiększa szanse na jego wykorzystanie.

Przykład działania SORT MERGE JOIN

W skrócie SORT MERGE JOIN polega na posortowaniu zestawów danych a następnie ich porównaniu. Prześledzimy cały proces wykonania algorytmu połączenia dwóch nieposortowanych tabel. Rozpocznijmy od rozważenia poniższego przykładu:

Na powyższym schemacie mamy dwie tabele które nie są posortowane. Przy takim stanie tabel baza danych w pierwszej kolejności wykona operację SORT JOIN na obu z nich aby doprowadzić do sytuacji gdzie oba zestawy danych są posortowane w ten sam sposób. Wynik powinien wyglądać jak poniżej:

Po wykonaniu operacji SORT JOIN oba zestawy danych zostały posortowane w tej samej kolejności. W tym momencie baza danych może rozpocząć operację łączenia rekordów czyli do operacji MERGE JOIN. Pierwszym jej krokiem jest ustalenie wskaźników na obu zbiorach na pierwszym elemencie:

Po ustawieniu wskaźników z obu zestawów danych baza porównuje oba rekordy. Jeżeli wartości są zgodne z warunkiem złączenia (załóżmy, że naszym warunkiem jest = pomiędzy ID) to baza danych zwraca rekord do wyniku:

Jako, że pierwsze rekordy z obu tabel spełniają warunek złączenia to baza zwraca je do wyniku. W następnym kroku baza danych na lewym zestawie przesuwa wskaźnik na kolejny rekord:

W tym momencie baza znów porównuje rekordy. Jako, że 10 jest większe od 7 to baza wie, że kolejny do zmiany jest wskaźnik na TABELA2:

Następnie baza sprawdza rekordy i przesuwa wskaźnik na TABELA1 na 20. Kolejne kroki są powtarzane aż baza przeszuka do końca oba zestawy danych.

Przykłady wywołania SORT MERGE JOIN

Skoro wiemy jak działa SORT MERGE JOIN nadszedł czas na przyjrzenie się planom dla konkretnych zestawów danych. Przygotujmy więc prostą bazę danych z dwoma tabelami:

CREATE TABLE EMPLOYEE (
    ID      NUMBER
  , SALARY  NUMBER
  , NAME    VARCHAR2(255 CHAR)
  , BOSS_ID NUMBER
);

CREATE TABLE BOSS (
    ID     NUMBER
  , SALARY NUMBER
  , NAME   VARCHAR2(255 CHAR)
);

Powyższe tabele wypełnijmy danymi:

BEGIN
  FOR I IN 0 .. 10000
  LOOP
    INSERT INTO EMPLOYEE (
        ID
      , SALARY
      , NAME
      , BOSS_ID
    ) VALUES (
        I
      , MOD(I,100) * 1000
      , 'EMP ' || I
      , MOD(I,100)
    );
  END LOOP;
END;
/

BEGIN
  FOR I IN 0 .. 100
  LOOP
    INSERT INTO BOSS (
        ID
      , SALARY
      , NAME
    ) VALUES (
        I
      , MOD(I,100) * 1100
      , 'BOSS ' || I
    );
  END LOOP;
END;
/

COMMIT;

A na końcu przeliczmy statystyki:

EXEC DBMS_STATS.GATHER_TABLE_STATS('SYS','EMPLOYEE');
EXEC DBMS_STATS.GATHER_TABLE_STATS('SYS','BOSS');

Skoro mamy już przygotowany zestaw danych wykonajmy pierwsze proste zapytanie:

SELECT
    *
FROM BOSS B
JOIN EMPLOYEE E ON E.BOSS_ID = B.ID
WHERE 1 = 1;

oraz zobaczmy plan:

Na planie zapytania sql widzimy hah join. Jest to wynik którego mogliśmy się spodziewać, ponieważ przeszukujemy duże zbiory danych a zgodnie z kursem hash join taki plan jest najbardziej prawdopodobny.

Zgodnie z opisem z wstępu aby optymalizator wybrał SORT MERGE JOIN w warunku złączenie powinien wystąpić operator > lub <. Wyobraźmy więc sobie sytuację gdy chcemy znaleźć którzy pracownicy zarabiają więcej od szefów. Możemy takie zadanie zrealizować poniższym zapytaniem:

SELECT
    E.ID
  , B.ID
  , E.SALARY
  , B.SALARY
FROM BOSS B
JOIN EMPLOYEE E ON E.SALARY > B.SALARY
WHERE 1 = 1;

Oraz plan dla powyższego zapytania:

W powyższym zapytaniu widzimy trzy operacje:

• SORT na tabeli EMPLOYEE
• SORT na tabeli BOSS
• MERGE JOIN na obu wynikach

Jest to przykład wykorzystania przez bazę danych operacji SORT MERGE JOIN do połączenia dwóch tabel. W planie zapytania widzimy dwie operacje sortowania ponieważ żadna z tabel nie jest posortowana po kolumnie SALARY. Zobaczmy więc co się stanie gdy dodamy na jeden z tabel index na kolumnie SALARY np.:

CREATE INDEX BOSS_SALARY_IDX ON BOSS(SALARY, ID);

I plan dla powyższego zapytania ale już z indexem:

Na powyższym planie widzimy już tylko jedną operację sortowania ponieważ baza danych skorzystała z indexu który jest posortowany po pierwszej kolumnie czyli SALARY. Od razu nasuwa się pytanie czy dodanie indexu na drugiej tabeli umożliwi uniknięcie w ogóle operacji sortowania? Baza zawsze sortuje jeden z źródłowych zestawów dlatego dodatkowy index nic nie zmieni.

Inną sytuacją gdy baza danych wykorzysta mechanizm SORT MERGE JOIN do złączenia dwóch wyników jest dodanie klauzuli ORDER BY po kolumnie użytej w warunku złączenia. Rozważmy więc poniższe zapytanie:

SELECT
    B.ID
FROM BOSS B
JOIN EMPLOYEE E ON E.BOSS_ID = B.ID
WHERE 1 = 1
ORDER BY B.ID;

Oraz plan:

Dla powyższego zapytania baza również wykorzysta SORT MERGE JOIN. Dzieje się tak dlatego, że w zapytaniu zadaliśmy warunek sortowania ORDER BY po kolumnie z warunku łączenia czyli B.ID. Przy użyciu SORT MERGE JOIN baza łączy dwa posortowane już zbiory dlatego nie musi wykonywać dodatkowej operacji sortowania na wyniku. Operacja taka jest szybsza niż operacja łączenia np. HASH JOIN + SORT wyniku.

Hint SORT MERGE JOIN

Aby wymusić na bazie wykorzystanie złączenia metodą SORT MERGE JOIN należy użyć hintu USE_MERGE(tabela1, tabela2). Zobaczmy więc przykład z pierwszego zapytania z użyciem hintu use_merge:

SELECT
    /*+ USE_MERGE(B, E)*/
    *
FROM BOSS B
JOIN EMPLOYEE E ON E.BOSS_ID = B.ID
WHERE 1 = 1;

oraz plan:

Na powyższym planie widzimy wykorzystanie SORT MERGE JOINa na zapytaniu z pierwszego przykładu. Dodać, należy że koszt wzrósł prawie 100 krotnie względem HASH_JOIN ponieważ obie tabele w całości musieliśmy posortować przez złączeniem.

PODSUMOWANIE

• SORT MERGE JOIN wpierw sortuje dane a następnie je porównuje
• SORT MERGE JOIN zwraca posortowany wynik dlatego wykorzystywany jest gdy w zapytaniu dodamy ORDER BY z kolumną z warunku złączenia
• Gdy w warunku złączenia użyjemy operatorów > lub < istnieje duża szansa na użycie tej metody złączenia
• USE_MERGE to hint to wymuszenia na bazie złączenia SORT MERGE JOIN
• Baza zawsze sortuje jeden z zestawów danych pomimo istnienia indexów