JOIN: NESTED LOOPS - OracleDev

Pierwszą i podstawową metodą złączenia jest NESTED LOOPS JOIN. W skrócie metoda ta polega na przyrównywaniu kolejnych wartości do siebie w pętlach i zwracaniu ich w rezultacie wykonania zapytania. W bazie danych Oracle występują 3 podstawowe metody złączeń rekordów między tabelami.

Ten kurs jest częścią Kurs Oracle SQL

Łączenie tabel NESTED LOOPS jest jednym z oryginalnych metod łączenia tabel i pozostaje najczęstszym w szczególności dla małych zbiorów danych i przy możliwości wykorzystania indexów.

Jak JOIN NESTED LOOPS działa?

Koncepcyjnie JOIN NESTED LOOPS działa jako dwie zagnieżdżone pętle po jednej i drugiej tabeli zgodnie z poniższym pseudokodem:

FOR foo_row IN (select * from foo_table where X=Y) LOOP
  FOR bar_row IN (select * from bar_table where foo_row is matched) LOOP
    output values from foo_row and bar_row
  END LOOP
END LOOP

Pętla wewnętrzna (ang. inner) jest wykonywana dla każdego rekordu pętli zewnętrzne (ang. outer)j. Tabela foo_table jest tabelą zewnętrzną/OUTER, ponieważ znajduje się na zewnątrz pętli. Tabela zewnętrzna nosi często nazwę tabeli “DRIVING“. Tabela bar_table jest tabelą wewnętrzną/INNER, ponieważ znajduje się we wnętrzu pętli.

Algorytm działania NESTED LOOPS JOIN:

Optymalizator wybiera tebelę DRIVING/OUTER i umieszcza ją w pętli zewnętrznej.
- Zewnętrzna pętla tworzy zestaw rekordów do sterowania warunkiem łączenia. Źródłem wierszy może być tabela z dostępem do danych z indexu lub bezpośrednio z tabeli. Liczba iteracji pętli wewnętrznej jest równa liczbie rekordów pobranych z pętli zewnętrznej. Oznacza to, że jeżeli pętla zewnętrzna (select * from foo_table where X=Y) zwróci 100 rekordów to pętla wewnętrzna zostanie wykonana 100 razy.

Optymalizator wyznacza tabelę WEWNĘTRZNĄ/INNER i umieszcza ją w pętli wewnętrznej

Wykonaj pętle i wyszukaj rekordoów wynikowych:
- Pobierz rekordy z tabeli zewnętrznej
- Pobierz rekordy z tabel wewnętrznej
  - Wybierz pierwszy rekord tabeli zewnętrznej
  - Porównaj rekord z tabeli zewnętrznej z rekordami tabeli wewnętrznej
  - Zwróć wynik iteracji
  - Powtarzaj powyższą iterację aż, wszystkie rekordy zostaną porównane

Powyższy algorytm pokazuje, że wyszukiwanie rekordów poprzez NESTED LOOPS JOIN działa szybko dla wyszukiwania:

Małych zbiorów danych przy czym mały tłumaczyć należy jako niewielka część danych z tabeli np. 1% wszystkich danych. Gdy w tabeli zewnętrznej wyszukujemy tylko jednego rekordu
Gdy użyjemy klauzuli FIRST_ROW/ROWNUM
Gdy warunek łączenia jest w indexie

Przykład działania NESTED LOOPS w SQL

Aby pokazać działanie NESTED LOOPS JOIN stwórzmy w SQL dwie tabele testowe FOO_TABLE i BAR_TABLE. Tabela FOO_TABLE posiada dwie kolumny, ID który jest jednocześnie Primary Key oraz klumna FOO która wypełniona jest prostym tekstem. Pamiętać należy, że nałożenie Primary Key na kolumnę powoduje powstanie indexu unikalnego którego skanowanie opisałem w kursie INDEX UNIQUE SCAN. Tabela BAR_TABLE posiada dwie kolumny FOO_ID która jest “luźnym” połąceniem do tabeli FOO_TABLE oraz kolumnę BAR która jest prostą kolumną z tekstem.

CREATE TABLE FOO_TABLE (
    ID NUMBER
  , FOO VARCHAR2(255 CHAR)
  , CONSTRAINT ID_FOO_TABLE_PK PRIMARY KEY (ID)
);

CREATE TABLE BAR_TABLE (
    FOO_ID NUMBER
  , BAR VARCHAR2(255 CHAR)
);

Następnie wypełnijmy je danymi w liczbie po 10000 rekordów tak, że pasują jeden do jednego przy pomocy poniższego skryptu PL/SQL:

BEGIN
  FOR I IN 0 .. 10000
  LOOP
    INSERT INTO FOO_TABLE (
        ID
      , FOO
    ) VALUES (
        I
      , 'FOO ' || I
    );
  END LOOP;
END;
/

BEGIN
  FOR I IN 0 .. 10000
  LOOP
    INSERT INTO BAR_TABLE (
        FOO_ID
      , BAR
    ) VALUES (
        I
      , 'BAR ' || I
    );
  END LOOP;
END;
/

COMMIT;

Oraz przeliczmy statystyki dla obu tabel:

EXEC DBMS_STATS.GATHER_TABLE_STATS('SYSTEM','FOO_TABLE');
EXEC DBMS_STATS.GATHER_TABLE_STATS('SYSTEM','BAR_TABLE');

Skoro mamy już przygotowaną strukturę bazy oraz dane możemy poćwiczyć joinowanie NESTED LOOPS. Napiszmy więc najpierw proste zapytanie SQL łączące obie tabele:

SELECT
  *
FROM FOO_TABLE FOO
JOIN BAR_TABLE BAR ON BAR.FOO_ID = FOO.ID
WHERE 1=1;

W powyższym przykładzie pobieramy wszystkie dane z tabel. Warunek łączenia ustaliliśmy na BAR.FOO_ID = FOO.ID. Znając dane jakie umieściliśmy w tabelach wiemy, że na wyjściu oczekiwać możemy 10000 rekordów. Zobaczmy więc plan zapytania:

W powyższym przykładzie pjawił się HASH JOIN który nie jest tym czego się spodziewaliśmy na pierwszy rzut oka. Dzieje się tak, dlatego, że NESTED LOOPS dobrze działa, gdy wyszukujemy niewielką ilość danych. W powyższym zapytaniu chcemy porównać wszystkie rekordy z obu tabel i w tej sytuacji lepiej działa HASH JOIN. Istnieje możliwość wymuszenia na optymalizatorze wykorzystania NESTED LOOPS poprzez zastosowanie hintu USE_NL. Jednak jego zasotosowanie oraz zmianę kosztu można zobaczyć na dole kursu w części dotyczącej hintów.

Wykrzystanie ROWNUM

Zmodyfikujmy więc zapytanie dodając do niego klauzulę zwracającą 10 pierwszych rekordów:

SELECT
  *
FROM FOO_TABLE FOO
JOIN BAR_TABLE BAR ON BAR.FOO_ID = FOO.ID
WHERE 1=1
  AND ROWNUM < 10;

oraz plan:

UWAGA: na powyższym planie widzimy nawet dwa razy NESTED LOOPS jako metoda złącznia oraz wykorzystanie obiektu FOO_TABLE oraz INDEXU na nim nałożonego. Taka operacja jest zabiegiem optymalizacyjnym zastosowanym przez bazę przy wykorzystaniu NESTED LOOPS wraz z wykorzystaniem tabeli i indexu tego samego obiektu. Jest to zmiana wprowadzona wraz z wersją bazy Oracle 11g i pozwana na szybsze pobranie danych z tabeli dzięki odczytowi wieloblokowemu.

W powyższym przykładzie widzimy pojawienie się NESTED LOOPS jako metody złączenia BAR_TABLE oraz FOO_TABLE. Stało się tak, ponieważ baza wyszukuje tylko 10 pierwszych rekordów spełniających warunki zapytania. Stąd w planie pojawiła się adnotacja COUNT.

Gdybyśmy, w planie zmienili kaluzulę ROWNUM < 10 na ROWNUM < 100 baza powróci do metody HASH JOIN:

SELECT
  *
FROM FOO_TABLE FOO
JOIN BAR_TABLE BAR ON BAR.FOO_ID = FOO.ID
WHERE 1=1
  AND ROWNUM < 100;

oraz plan:

Na mojej bazi wartością graniczną jest ROWNUM < 50 czyli 5% rekordów z wyniku kiedy to NESTED LOOPS jest bardziej opłacalny od HASH JOIN.

Wykorzystanie INDEXU w warunku złączenia

Kolejnym przykładem zastosowania metody NESTET LOOPS JOIN jako metody złączenia dwóch tabel może być sytuacja gdy mocno ograniczymy liczbę rekordów z tabeli zewnętrznej oraz ją zaindeksujemy. W tabeli FOO_TABLE posiadamy index na kolumnie ID. W związku z tym, dodając warunek ograniczający na tą kolumnę baza powinna wykorzystać metodę NESTED LOOPS jako metodę złaczenia:

SELECT
  *
FROM FOO_TABLE FOO
JOIN BAR_TABLE BAR ON BAR.FOO_ID = FOO.ID
WHERE 1=1
  AND FOO.ID = 1000;

oraz plan:

W powyższym planie zapytania widzimy, wykorzystanie metody złączenia jaką jest NESTED LOOPS. Optymalizator wybrał w tej sytuacji NESTED LOOPS ponieważ z tabeli FOO_TABLE pobrany zostanie tylko jeden rekord. W związku z tym wystarczy następnie raz przeszukać tabelę BAR_TABLE w celu znalezienia odpowiadających rekordów. W tej sytuacji metoda ta jest szybsza od HASH JOIN.

Hint NESTED LOOPS

Istenieje możliwość wymuszenia na bazie wykorzystania złączenia metodą NESTED LOOPS poprzez zastosowanie hinta USE_NL wykorzytsanie którego może wyglądać jak w poniższym zapytaniu:

SELECT
  /*+ use_nl(FOO, BAR)*/
  *
FROM FOO_TABLE FOO
JOIN BAR_TABLE BAR ON BAR.FOO_ID = FOO.ID
WHERE 1=1;

Oraz plan:

Plan zapytania z wykorzystaniem nested loops

Powyższe zapytanie oryginalnie wykorzystywało do łączenia metodę HASH JON. Oryginalny koszt przed użyciem hintu był w okolicach 18, teraz ponad 10000. Dlatego też należy bardzo ostrożnie kożystać z hintów w zapytaniach ponieważ można przez przypadek mocno wydłużyć czas działania zapytania 🙂

Podsumowanie

NESTED LOOPS JOIN jest podstaowową metodą złączenia dwóch tabel
Wykorzystywany jest gdy operujemy na niewielkiej ilości danych. Przy czym niewielkiej tłumaczyć należy jako niewielka część danych z tabeli
NESTED LOOPS pozwala na szybki dostęp do danych gdy potrzebujemy ich ograniczoną ilość
USE_NL jest hinted pozwalającym wymusić na bazie metodę złączenia NESTED LOOPS

Jak JOIN NESTED LOOPS działa?

Przykład działania NESTED LOOPS w SQL

Wykrzystanie ROWNUM

Wykorzystanie INDEXU w warunku złączenia

Hint NESTED LOOPS

Podsumowanie

Dodaj komentarz Anuluj pisanie odpowiedzi