SQL Server Nested Loops – jak to działa

SQLServerNestedLoopsHowItWorks_00

Łącząc nasze tabele w SQL Server możemy myśleć o samych złączeniach w dwojaki sposób. Po pierwsze zastanawiamy się wysokopoziomowo czy potrzebujemy złączenia wewnętrznego (INNER) czy też zewnętrznego (OUTER) – ich użycie jest determinowane przez logikę jaką chcemy w danym zapytaniu zawrzeć. Z drugiej zaś strony możemy myśleć o tym przy użyciu jakiego algorytmu nasze złączenie jest realizowane. Poszczególne algorytmy możemy zobaczyć na planie zapytania pod postacią operatorów takich jak Nested Loops, Merge Jon czy też Hash Match – dziś chciałbym powiedzieć parę słów o pierwszym z nich – zapraszam do lektury.

Na wstępie wykonajmy poniższe zapytanie aby otrzymać plan wykonania z omawianym algorytmem złączenia i przedstawmy jego plan wykonania:

Nested Loop jest najprostszym algorytmem łączącym dostępnym w SQL Server. W przypadku gdy łączymy dwie tabele to jedna z nich nazywana jest Outer table (widoczna na planie w górnej części zapytania) oraz Inner Table (widoczna poniżej). Schemat działania algorytmu został przedstawiony na poniższej grafice. Pierwsza pętla “biegnie” po tabeli oznaczonej jako Outer table (nazwijmy ją pętlą zewnętrzną) i napotyka na wartość A. Wtedy też dla tej wartości uruchamiana jest druga pętla (wewnętrzna) i w tabeli oznaczonej jako Inner table wyszukuje wszystkie pasujące rekordy dla aktualnej wartości pętli zewnętrznej. Pętla wewnętrzna musi przeskanować całą tabelę gdyż nie ma pewności czy zbiory są posortowane i może znaleźć wiele pasujących rekordów lub też optymalnie użyć indeksu używając operacji Seek. Jak widać w pierwszym przebiegu (Look for A) znalezione zostały dwa pasujące rekordy. Kiedy już pętla wewnętrzna się wykona to pętla wewnętrzna przechodzi do kolejnej wartości czyli “B” i pętla wewnętrzna po raz kolejny przeszukuje całą tabelę w poszukiwaniu wartości B i tak aż do wyczerpania wartości.

Tabela zewnętrzna w całości czytana jest przez SQL Server natomiast tabela wewnętrzna jest odczytywana tyle razy ile jest rekordów w tabeli zewnętrznej. W najprostszej postaci fakt ten możemy w łatwy sposób zaobserwować na planie wykonania obserwując właściwość Actual Executions poszczególnych operatorów:

Powyższy przypadek dobrze opisuje również fakt, iż na kolumnach po których następuje złączenie powinny być założone odpowiednie indeksy dzięki czemu wykonywana jest operacja Index Seek zamiast kosztownego Indeks Scan.

Drugi przypadek kiedy możemy zobaczyć w planach zapytań Nested Loop to tzw. Bookmark Lookup (o którym pisałem już tutaj). Pojawia się on wtedy gdy mamy indeks nieklastrowany, który nie pokrywa wszystkich żądanych przez nas kolumn – spróbujmy zobrazować to na przykładzie. Poniższe zapytanie powoduje wykonanie Bookmark Lookup:

W tym przypadku nie są łączone poszczególne tabele, a jedynie do zbioru danych zwróconego przez indeks niezgrupowany dołączone są dodatkowo wymagane przez nas dane z indeksu zgrupowanego. To co warto w tym miejscu zauważyć to fakt, że w momencie gdy mamy w planie Bookmark Lookup to do połączenia danych z indeksu niezgrupowanego z danymi z indeksu zgrupowanego zawsze używany jest Nested Loop co przy większych zbiorach danych może być bardzo kosztowne.

W większości przypadków optymalizator wybierze opisywany algorytm złączenia tylko w przypadku małych zbiorów danych i zawsze w przypadku Bookmark Lookup – w jaki sposób dokonuje tego wyboru? Po pierwsze tylko wtedy gdy nie wymusimy na nim konkretnych działań np. poprzez hint INNER LOOP JOIN jawnie wskazujemy Nested Loop jako pożądany algorytm:

Ponadto istnieje możliwość wymuszenia Nested Loop poprzez OPTION (LOOP JOIN). Czym zatem różni się od INNER LOOP JOIN? Kolega Krzysztof w komentarzu zamieścił informację, iż INNER LOOP JOIN wymusza kolejność złączania taką jak wskazaliśmy w zapytaniu, a OPTION (LOOP JOIN) – pozostawia ten wybór optymalizatorowi, który takową decyzję podejmie na podstawie estymacji liczebności. Sprawdźmy to na przykładzie – uruchommy zapytanie raz jeszcze wykorzystując oba hinty:

Jak można zauważyć na poniższym planie zapytania w zależności od użycia określonego hinta inna była tabela została wzięta jako OUTER TABLE co dosyć drastycznie wpłynęło na wydajność. Można zatem przyjąć, że INNER LOOP JOIN działa tak jakby niejawnie wywołany został hint FORCE ORDER wymuszający określoną kolejność tabel wchodzących do algorytmu łączącego.

Gdy nie używamy hintów znaczenie ma wiele czynników jak np. występowanie indeksów. Ogólnie rzecz biorąc Nested loop możemy podzielić na trzy różne typy:

  • naive nested loop – w momencie gdy przeszukiwana jest cała wewnętrzna tabela
  • index nested loop – w momencie gdy do przeszukania wewnętrznej tabeli używany jest indeks
  • temporary nested loop – w momencie gdy optymalizator stworzy na potrzeby planu indeks, który następnie zostanie usunięty

Jak możecie się domyślać algorytm ten nie jest w ogóle skalowalny i im większe tabele są łączone tym dłużej algorytm będzie się wykonywał. Można nawet powiedzieć, iż Nested Loop jest dobrym algorytmem do łączenia małych zbiorów danych – czasem jest to wręcz najlepszy algorytm dla takich zbiorów – szczególnie gdy widzimy go jako index nested loop. Tak jak wspomniałem istnieją również dwa inne algorytmy złączenia tj. Merge Join i Hash Match o których opowiemy sobie innym razem.

Adrian Chodkowski
Follow me

Adrian Chodkowski

SQL geek, Data enthusiast, Consultant & Developer
Adrian Chodkowski
Follow me

2 Comments

  1. Gość

    Kiedyś znalazłem informację, że hinty należy znać, ale nie należy ich stosować 😉
    Czy faktycznie jest tak jak opisano to w podlinkowanej (poniżej) dyskusji, że hint INNER LOOP JOIN wymusza kolejność łączenia kilku tabel, a hint OPTION(LOOP JOIN) pozostawia to do decyzji optymalizatorowi?
    https://social.msdn.microsoft.com/Forums/sqlserver/en-US/ae9ebe48-3610-43ee-a7dc-ec5ab21a8005/the-difference-between-optionloop-join-and-from-table-inner-loop-join-table?forum=transactsql

    Reply
  2. Adrian Chodkowski (Post author)

    Hinty bywają pomocne czasem podczas diagnostyki lub testów – produkcyjnie ich użycie jest raczej rzadko uzasadnione.
    Co do różnicy pomiędzy INNER LOOP JOIN a OPTION (LOOP JOIN) to przestestowałem i rzeczywiście tak jest – INNER LOOP JOIN działa tak jakbyśmy użyli dodatkowego HINTa o nazwie FORCE ORDER – bardzo trafna uwaga.

    Reply

Leave a Comment

Your email address will not be published. Required fields are marked *