Jak wiadomo SQL Serwer wykonuje zapytanie używając zestawu operatorów fizycznych. Ponieważ operatory iterują na zbiorach wierszy są nazywane iteratorami. W tej lekcji omówione zostaną najważniejsze iteratory używane w dostępie do danych, wykonywania złączeń i innych czynności mających na celu pobranie żądanych wyników.

Metody dostępu

W tabeli zorganizowanej jako sterta jedyną metodą dostępu jest skanowanie tabeli. Skanowanie jest wykonywany w określonej kolejności logicznej. SQL Serwer używa stron IAM do skanowania w kolejności fizycznej. SQL Serwer może użyć uporządkowanego skanowania (ang. allocation order scan) również kiedy tabela jest zorganizowana jako klastrowana. Uporządkowane skanowanie jest szybsze jeżeli tabela jest mniej rozdrobniona fizycznie. Fragmentacja logiczna nie ma wpływu na skanowanie uporządkowane. Poniższy kod tworzy stertę poprzez pobranie wszystkich wierszy z tabeli Sales.OrderDetails z bazy danych TSQL2012 i umieszczenie ich w nowej tabeli:

SELECT orderid, productid, unitprice, qty, discount
INTO Sales.OrderDetailsHeap
FROM Sales.OrderDetails;

Nieważne czy użyjemy  bardzo selektywnego predykatu w klauzuli WHERE który ograniczy wynik do kilku wierszy czy też pobierzemy tylko kilka kolumn SQL Serwer użyje operatora skanowania tabeli do pobrania danych, np:

SELECT orderid, productid
FROM Sales.OrderDetailsHeap
WHERE orderid = 10248
AND productid = 11;

Plan wykonania: ep222 SQL Serwer używa skanowania uporządkowanego dla tabel klastrowanych tylko jeżeli zapytanie nie wymaga konkretnej kolejności, jeżeli poziom izolacji to Read Uncommitted lub kiedy pracujemy w środowisku tylko do odczytu. Kiedy SQL Serwer skanuje indeks klastrowany to może również skanować w kolejności logicznej używając skanowania uporządkowanego indeksu (ang. index order scan). W każdym z tych przypadków używany jest iterator Clustered Index Scan. SQL Serwer używa listy powiązanej poziomu liści indeksu do wykonania skanowania uporządkowanego indeksu. Na skanowanie uporządkowane indeksu negatywny wpływ mają zarówno fizyczna i logiczna fragmentacja. Poniższe zapytanie nie wymaga uporządkowanego wyniku. Można zauważyć, że właściwość Ordered operatora Clustered Index Scan jest ustawiona na FALSE:

SELECT orderid, productid, unitprice
FROM Sales.OrderDetails;

Plan wykonania: ep223 Indeks nieklastrowany może pokryć zapytanie. Oznacza to, że SQL Serwer może znaleźć wszystkie dane potrzebne do otrzymania wyniku zapytania w indeksie nieklastrowanym i nie musi robić żadnych odwołań do tabeli bazowej. SQL Serwer używa iteratora Index Scan do przeskanowania indeksu nieklastrowanego. Tak jak z iteratorem Clustered Index Scan, SQL Serwer może wykonać alokację lub uporządkowane skanowanie kiedy skanuje indeks nieklastrowany. Poniższe zapytanie używa skanowania indeksu nieklastrowanego i zwraca dane w kolejności indeksu:

SELECT orderid, productid
FROM Sales.OrderDetails
ORDER BY productid;

Plan wykonania: ep224 W niektórych przypadkach optymalizator może zdecydować do pokrycia zapytania wieloma indeksami nieklastrowanymi. SQL Serwer potrafi łączyć indeksy nieklastrowane. Wszystkie indeksy nieklastrowane tabeli zawsze mają pewne dane wspólne które mogą służyć do złączenia. Jeżeli tabela jest stertą to tymi danymi jest identyfikator wiersza (RID). Jeżeli tabela jest klastrowana to jest nim klucz klastrujący. Można również poprawić pokrycie zapytania poprzez uwzględnienie kolumn w indeksie nieklastrowanym. Uporządkowane skanowanie przydziału może być niebezpieczne. SQL Serwer może pominąć pewne wiersze lub odczytać inne kilka razy. Może tak się stać jeżeli używany jest poziom izolacji Read Uncommitted. W czasie kiedy jedno zapytanie używa skanowania uporządkowanego przydziału, drugie może aktualizować dane i spowodować przemieszczenie jednego lub wielu wierszy. Zapytanie skanujące mogło przeczytać już wiersze aktualizowane i przeczytać je jeszcze raz po przemieszczeniu.  Może być tak, że pewne strony zostały już przeczytane i wiersze ze stron nieprzeczytanych do nich trafią po przemieszczeniu to nie zostaną one wcale przeczytane. Wiersze mogą być przeniesione z wielu powodów. Przykładowo komenda może aktualizować kolumnę o zmiennej długości i zamienić krótką wartość przez długą. Strona może być pełna i aktualizowane wiersze muszą być przeniesione do innej strony. jeżeli do tabeli klastrowanej są dodawane wiersze to moze nastąpić podział strony w którym połowa wierszy jest przeniesiona do nowej strony. Trzeba być ostrożnym używając poziomu izolacji Read Uncommitted. SQL Serwer nie musi wykonywać pełnego skanowania. Jeżeli zwracany zbiór wynikowy jest ograniczony a skanowanie jest uporządkowane to SQL Serwer może wyszukać pierwszą wartość wyszukiwanego zbioru i wykonać skanowanie częściowe w kolejności logicznej indeksu. SQL Serwer może użyć wyszukania i skanowania częściowego dla indeksów klastrowanych i pokrywających indeksów nieklastrowanych, np:

SELECT orderid, productid, unitprice
FROM Sales.OrderDetails
WHERE orderid BETWEEN 10250 AND 10390
ORDER BY orderid, productid;

Plan wykonania: ep225 Operator użyty w planie wykonania to Clustered Index Seek. We właściwościach można zauważyć, że aktualna liczba wierszy to 377. Dlatego kiedy pierwszy wiersz został odnaleziony to SQL Serwer nie wyszukiwał pozostałych wierszy tylko wykonał częściowe skanowanie. SQL Serwer może użyć tych samych metod dostępu, wyszukania w indeksie po czy częściowego skanowania dla pokrywającego indeksu nieklastrowanego, np:

SELECT orderid, productid
FROM Sales.OrderDetails
WHERE productid BETWEEN 10 AND 30
ORDER BY productid;

Plan zapytania: ep226 Prawdopodobnie najczęstszą metodą dostępu używaną przez SQL Serwer w przetwarzaniu OLTP jest wyszukiwanie indeksu nieklastrowanego z uporządkowanym częściowym skanowaniem po czym odwołanie do tabeli bazowej dla każdego wiersza w indeksie nieklastrowanym. Takie plany są typowe dla selektywnych zapytań. Tabela bazowa może być stertą lub drzewem zrównoważonym. Gdy tabela jest stertą to SQL Serwer używa operatora RID Lookup do otrzymania wierszy z tabeli bazowej. Poniższy kod tworzy indeks nieklastrowany na stercie i wykonuje zapytanie używające wyszukiwania indeksu nieklastrowanego z uporządkowanym skanowaniem i RID Lookup:

CREATE NONCLUSTERED INDEX idx_nc_qtyheap ON Sales.OrderDetailsHeap(qty);
SELECT orderid, productid, unitprice, qty
FROM Sales.OrderDetailsHeap
WHERE qty = 52;

Plan wykonania: ep227 Jeżeli tabela jest klastrowana to SQL Serwer używa operatora Key Lookup. Poniższy kod tworzy indeks nieklastrowany na tabeli klastrowanej i wykonuje zapytanie używające wyszukiwania indeksu nieklastrowanego ze skanowaniem uporządkowanym i Key Lookup:

CREATE NONCLUSTERED INDEX idx_nc_qty ON Sales.OrderDetails(qty);
SELECT orderid, productid, unitprice, qty
FROM Sales.OrderDetails
WHERE qty = 52;

Plan wykonania: ep228 W bardzo rzadkich przypadkach SQL Serwer może zdecydować się na użycie nieuporządkowanego skanowania indeksu po czym na wykonanie odniesienia do klucza lub RID w tabeli bazowej. W celu uzyskania takiego planu, zapytanie musi być odpowiednio selektywne, nie może istnieć optymalny niekklastrowany indeks pokrywający a używany indeks nie musi utrzymywać wyszukanych kluczy w uporządkowanej kolejności. Poniższy kod czyści bazę TSQL2012:

DROP INDEX idx_nc_qtyheap ON Sales.OrderDetailsHeap;
DROP INDEX idx_nc_qty ON Sales.OrderDetails;
DROP TABLE Sales.OrderDetailsHeap;

Algorytmy złączeń

Łącząc tabele SQL Serwer używa różnych algorytmów. Trzy podstawowe algorytmy to nested loop, merge join i hash join. hash join może być zoptymalizowany używając filtrowania mapy bitowej (ang. bitmap filtering). Bitmap filtered hash join może być traktowany jako osobny algorytm lub ulepszenie algorytmu hash join. Algorytm nested loops jest bardzo prosty i wydajny w wielu przypadkach. SQL Serwer używa jednej tabeli dla zewnętrznej pętli, zwykle tabeli która ma mniej wierszy. Dla każdego wiersza w tej zewnętrznej pętli SQL Serwer wyszukuje pasujące wiersze w drugiej tabeli która jest tabelą wewnętrzną. SQL Serwer używa predykatu złączenia do odnalezienia pasujących wierszy. jeżeli wewnętrzna tabela nie ma indeksu wspierającego wyszukiwanie to SQL Serwer skanuje wewnętrzną tabelę dla każdego wiersza tabeli zewnętrznej. taki scenariusz jest niewydajny. Algorytm nested loops jest wydajny kiedy SQL Serwer może wykonać wyszukiwanie indeksu (ang. index seek) na tabeli wewnętrznej. Poniższe zapytanie używa iteratora nested loops do złączenia tabel Sales.Orders i Sales.OrderDetail. Zapytanie ogranicza zamówienia aby otrzymać mniej wierszy, bez klauzuli WHERE, SQL Serwer użyłby algorytmu merge join:

SELECT O.custid, O.orderdate, OD.orderid, OD.productid, OD.qty
FROM Sales.Orders AS O
INNER JOIN Sales.OrderDetails AS OD
ON O.orderid = OD.orderid
WHERE O.orderid < 10250;

Plan wykonania: ep229 Algorytm merge join jest bardzo wydajnym algorytmem jednakże ma swoje ograniczenia. Wymaga przynajmniej jednego predykatu equijoin (predykat ze znakiem równości) i posortowanych wejść z obu stron złączenia. Oznacza to, że ten algorytm musi być wspierany przez indeksy w dwóch łączonych tabelach. Dodatkowo jeżeli jedno wejście jest dużo mniejsze od drugiego to algorytm nested loops może być wydajniejszy. W scenariuszu jeden do jednego lub jeden do wielu iterator merge join skanuje oba wejścia tylko raz. Startuje od znalezienia pierwszego wiersza z obu stron. Jeżeli koniec wejścia nie został osiągnięty to algorytm sprawdza predykat złączenia aby określić czy wiersze są zgodne. Jeżeli wiersze są zgodne to zostają dodane do zbioru wyjściowego. Następnie algorytm sprawdza następny wiersz z drugiej strony i dodaje go do wyjścia jeżeli pasuje do predykatu. Jeżeli wiersze z obu wejść do siebie nie pasują to algorytm czyta następny wiersz ze strony z niższą wartością. Czyta z tej strony i porównuje do wiersza z drugiej strony dopóki wartość nie jest wyższa niż wartość z drugiej strony. Wtedy zaczyna czytać z drugiej strony itd. W scenariuszu wiele do wielu algorytm używa tabeli roboczej do wstawienia wierszy z jednego wejścia przeznaczonych do ponownego użycia kiedy istnieją zduplikowane wiersze z drugiego wejścia. Poniższe zapytanie używa iteratora merge join do złączenia tabel Sales.Ordeers i Sales.OrderDetails. Zapytanie używa equijoin a oba wejścia są wspierane przez indeks:

SELECT O.custid, O.orderdate, OD.orderid, OD.productid, OD.qty
FROM Sales.Orders AS O
INNER JOIN Sales.OrderDetails AS OD
ON O.orderid = OD.orderid;

Plan wykonania: ep230 Jeżeli żadna strona złączenia nie jest wspierana przez indeks i predykat equijoin jest użyty to algorytm hash join wydaje się być najbardziej wydajnym. Algorytm ten używa struktury nazywanej hash table. Nie jest to struktura wyszukiwania którą można zbudować jak drzewo zrównoważone używane w indeksach. SQL Serwer buduje taką tabelę wewnętrznie. Używa funkcji skrótu do podziału wierszy z mniejszego wejścia. Faza ta jest nazywana fazą początkową (ang. build phase). SQL Serwer używa mniejszego wejścia do budowy tabeli hash table ponieważ dąży do tego aby zbudować ją w pamięci. Jeżeli musi zapisać ją na dysku to algorytm może być dużo wolniejszy. Funkcja skrótu dzieli wejście na części o przybliżonej wielkości które są nazywane wiadrami (ang. buckets). Kiedy table jest zbudowana, SQL Serwer używa funkcji skrótu do każdego wiersza drugiego wejścia. Sprawdza do którego wiadra pasuje wiersz. Następnie skanuje przez wszystkie wiersze z wiadra. Ta faza jest nazywana fazą sondowania (ang. probe phase). Algorytm hash join jest rodzajem kompromisu pomiędzy tworzeniem pełnego drzewa zrównoważonego i użyciem innego algorytmu złączenia a wykonaniem pełnego skanowania jednej strony dla każdego wiersza drugiej strony zapytania. można myśleć, że ten algorytm jest mało wydajny. Jest to częściowo prawda. W trybie jednowątkowym jest zazwyczaj wolniejszy niż pozostałe algorytmy. Jednakże SQL Serwer potrafi podzielić wiersze z wejścia sondy z góry i wykonać częściowe złączenia w wielu wątkach. Hash join jest bardzo skalowalny. ten rodzaj optymalizacji jest zwany bitmap filtered hash join. Jest on używany typowo w scenariuszach hurtowni danych gdzie występują złączenia z dużą ilością danych i mało konkurujących użytkowników, więc możliwe jest wykonanie wielowątkowe. poniższe zapytanie tworzy dwie sterty wstawiając dane z tabel Sales.Orders i Sales.OrderDetails do nowych tabel:

SELECT orderid, productid, unitprice, qty, discount
INTO Sales.OrderDetailsHeap
FROM Sales.OrderDetails;
SELECT orderid, custid, orderdate
INTO Sales.OrdersHeap
FROM Sales.Orders;

Poniższe zapytanie używa algorytmu hash join:

SELECT O.custid, O.orderdate, OD.orderid, OD.productid, OD.qty
FROM Sales.OrdersHeap AS O
INNER JOIN Sales.OrderDetailsHeap AS OD
ON O.orderid = OD.orderid;

Plan wykonania: ep231 Wykonaj poniższy kod aby wyczyścić zmiany w bazie danych TSQL2012:

DROP TABLE Sales.OrderDetailsHeap;
DROP TABLE Sales.OrdersHeap;

Tylko algorytm nested loops obsługuje non-equijoins!

Inne iteratory planu wykonania

Kompletną listę operatorów planu wykonania i ich graficzną reprezentację można zobaczyć na stronie Books Online. SQL Serwer używa operatora Sort zawsze kiedy wykonywane jest sortowanie wejścia. Może istnieć wiele powodów sortowania wejścia. Przykładowo SQL Serwer może zdecydować o sortowaniu wejścia aby móc zastosować algorytm merge join. Bardzo typowym przykładem wykorzystania operatora sort jest zapytanie które żąda posortowanego zbioru wynikowego którego kolejność nie jest wspierana przez indeks. Operacja sortowania może być bardzo kosztowna, powinna być wykonywana tylko dla małych zbiorów wejściowych. Poniższe zapytanie żąda uporządkowanego zbioru wynikowego. Zbiór wynikowy powinien być posortowany wg kolumny qty tabeli Sales.OrderDetails. Jednakże tabela nie posiada indeksu na tej kolumnie:

SELECT orderid, productid, qty
FROM Sales.OrderDetails
ORDER BY qty;

Plan wykonania: ep001 Koszt wykonania sortowania jest równy 80% całkowitego kosztu zapytania. SQL Serwer używa dwóch różnych algorytmów do obliczania agregacji. Jeżeli wejście jest uporządkowane wg kolumn użytych w klauzuli GROUP BY to SQL Serwer używa algorytmu stream aggregation. Algorytm ten jest bardzo wydajny, czasem SQL Serwer może zdecydować aby posortować wejście w celu użycia tego algorytmu. Poniższe zapytanie używa operatora Stream Aggregate. Grupowanie wierszy tabeli Sales.OrderDetails odbywa się wg kolumny productid dla której istnieje indeks nieklastrowany.  Ponieważ zapytanie nie potrzebuje żadnej więcej kolumny to indeks ten jest pokrywający:

SELECT productid, COUNT(*) AS num
FROM Sales.OrderDetails
GROUP BY productid;

Plan wykonania: ep002 Jeżeli wejście agregacji nie jest posortowane i jest za duże aby można było je wydajnie sortować to SQL Serwer używa algorytmu hash aggregation. Operator używany dla takich agregacji nazywa się Hash Match Aggregate. Algorytm ten buduje tabelę skrótów dla wejścia tak jak robi to dla algorytmu hash join, jednakże wiadra są używane do przechowywania grup. Algorytm ten jest również dobrze skalowalny. Poniższe zapytanie grupuje wiersze tabeli Sales.OrderDetails wg kolumny qty:

SELECT qty, COUNT(*) AS num
FROM Sales.OrderDetails
GROUP BY qty;

Plan wykonania: ep003 Jak widać operator hash aggregation jest dużo bardziej kosztowny od stream aggregation.

Ćwiczenia

I. Przewidywanie operatora planu wykonania

  1. Otwórz nowe okno SSMS i ustaw kontekst bazy danych na bazę danych TSQL2012.
    USE TSQL2012
    GO
    
  2. Przeanalizuj strukturę i indeksy tabel Sales.Customers i Sales.Orders. Spójrz na poniższe zapytanie i spróbuj odgadnąć jaki algorytm złączenia użyje SQL Serwer. czy w planie wykonania zobaczymy operator sortowania?
    SELECT C.custid, C.companyname, C.address, C.city,
    O.orderid, O.orderdate
    FROM Sales.Customers AS C
    INNER JOIN Sales.Orders AS O
    ON C.custid = O.custid;
    
  3. Włącz pokazywanie planu wykonania i wykonaj zapytanie. Zbadaj plan wykonania. ep004
  4. Poniższe zapytanie nie zawiera kolumny orderdate. Odgadnij operatory planu wykonania.
    SELECT C.custid, C.companyname, C.address, C.city,
    O.orderid
    FROM Sales.Customers AS C
    INNER JOIN Sales.Orders AS O
    ON C.custid = O.custid;
    
  5. Wykonaj zapytanie i sprawdź plan wykonania. ep005

II. Analiza różnych planów wykonania.

  1. Wykonaj poniższe zapytanie i sprawdź plan wykonania. Zauważ, że zapytanie jest dosyć selektywne.
    SELECT C.custid, C.companyname, C.address, C.city,
    O.orderid, O.orderdate
    FROM Sales.Customers AS C
    INNER JOIN Sales.Orders AS O
    ON C.custid = O.custid
    WHERE C.city = N'Berlin';
    
    Plan wykonania: ep006 Ponieważ zapytanie jest selektywne to SQL Serwer zdecydował, że operator Key Lookup nie będzie zbyt kosztowny. Zauważ, że dla 6 zwracanych wierszy z tylko 6 wyszukiwaniami klucza koszt operatora SQL Serwer to 74% całkowitego kosztu zapytania.
  2. Wykonaj poniższe zapytanie i sprawdź plan wykonania.
    SELECT C.city, MIN(O.orderid) AS minorderid
    FROM Sales.Customers AS C
    INNER JOIN Sales.Orders AS O
    ON C.custid = O.custid
    GROUP BY C.city;
    
    Plan wykonania: ep007 Zapytanie jest pokryte przez dwa indeksy nieklastrowane. Istnieje indeks na kolumnie city tabeli Sales.Customers który zawiera kolumnę custid z klucza głównego oraz nieklastrowany indeks na kolumnie custid tabeli Sales.Orders. Ponieważ wejście dla agregacji jest uporządkowane to SQL Serwer używa operatora Stream Aggregate.

Podsumowanie

  1. SQL Serwer używa wielu różnych metod dostępu do danych.
  2. SQL Serwer używa różnych operatorów złączeń i algorytmów agregujących.
  3. Nie ma złych ani dobrych operatorów. Każdy operator może być najlepszą metodą dla konkretnego zapytania i danych.