SQL Server Nested Loops – jak to działa

Łą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:

SELECT * FROM dbo.FactCallCenter AS F
JOIN dbo.DimDate AS D
ON D.DateKey=F.DateKey

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:

SELECT ProductAlternateKey,StartDate,EndDate  FROM DimProduct
WHERE ProductAlternateKey='BA-8327'

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:

SELECT * FROM dbo.FactCallCenter AS F
INNER LOOP JOIN dbo.DimDate AS D
ON D.DateKey=F.DateKey

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:

SELECT * FROM 
dbo.DimDate AS D
INNER LOOP JOIN dbo.FactCallCenter AS F
ON D.DateKey=F.DateKey

SELECT * FROM 
dbo.DimDate AS D
INNER JOIN dbo.FactCallCenter AS F
ON D.DateKey=F.DateKey
OPTION (LOOP JOIN)

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.