Wykład 10

Wykonywanie zapytań

 

Streszczenie

Wykład składa się z dwóch części. Pierwsza część zaznajamia z metodami realizacji operatorów relacyjnych, z których składają się zapytania SQL.

W drugiej części są omówione zasady wykonywania zapytań. Przed wykonaniem zapytania przez SZBD włącza się moduł optymalizatora zapytań, którego zadaniem jest znaleźć możliwie najlepszy plan wykonania tego zapytania.

 

10.1 Operatory relacyjne

Każdą instrukcję SQL można rozłożyć na części przy czym każda z tych części jest związana z użyciem jednego operatora relacyjnego działającego na jednej lub więcej tabeli. Oto podstawowe operatory relacyjne:

  1. Selekcja - selekcja podzbioru wierszy (określona przez warunek w klauzuli WHERE).
  2. Projekcja - pominięcie z wyniku pewnych kolumn (klauzule SELECT i SELECT DISTINCT).
  3. Złączenie - złączenie tabel (relacji).
  4. Operatory algebraiczne UNION (DISTINCT) i EXCEPT na tabelach (relacjach).
  5. Agregacja - zastosowanie funkcji agregujących SUM, MIN, itd. i klauzuli GROUP BY.

Przypominamy, że na koszt realizacji operacji bazodanowych największy wpływ ma liczba stron dyskowych przesyłanych między dyskiem a pamięcią wewnętrzną.

Implementacja selekcji

Rozważmy przykład.

SELECT *
FROM Emp e
WHERE e.Ename < 'C' AND e.Sal > 1000;
 

Załóżmy, że warunek w klauzuli WHERE ma postać koniunkcji. (Wiadomo z wykładu z matematyki dyskretnej, że każdą formułę logiczną można sprowadzić do koniunkcji alternatyw prostych warunków – czyli do tzw. postaci normalnej.) Są dwie metody realizacji takiej selekcji:

  1. przejście sekwencyjne całego pliku rekordów (operacja scan),

  2. wybór najbardziej "selektywnego" pola, które występuje w prostym warunku koniunkcji i na którym jest założony indeks, po czym wyszukanie przez ten indeks (tzn. sprowadzamy warunek WHERE do postaci koniunkcji: p AND Reszta gdzie p jest prostym predykatem dotyczącym pojedynczego pola w tabeli). Najlepiej, gdy indeks jest haszowany dla selekcji równościowej oraz gdy indeks jest na B+ drzewie dla selekcji zakresowej.

Wybór drugiej metody jest wskazany w trzech przypadkach:

  1. gdy indeks jest główny lub jednoznaczny,

  2. gdy indeks jest pogrupowany oraz wyszukiwanie jest zakresowe,

  3. gdy oszacowanie rozmiaru zbioru wyszukiwanych przez indeks wierszy wskazuje na niewielką ich liczbę (to znaczy gdy wyszukiwanie przez indeks jest selektywne) - powiedzmy do 5-10%.

W przypadku zastosowania indeksu nie pogrupowanego wskazane jest, jeśli możliwe, posortowanie identyfikatorów zwracanych rekordów według adresów stron dyskowych i ściągnięcie każdej potrzebnej strony tylko jeden raz.

Implementacja projekcji

Rozważmy przykład:

      SELECT DISTINCT e.Job
    FROM Emp e;

Gdy nie ma operatora DISTINCT – wystarczy przejść cały plik (scan) i przepisać wartości wyrażeń na liście SELECT.

Problem stanowi tylko klauzula SELECT DISTINCT, która wymaga eliminacji powtórzeń co można uzyskać przez posortowanie zbioru wynikowego.

Do eliminacji powtórzeń można też użyć metody polegającej na rozrzuceniu wynikowych wartości do segmentów tablicy haszowanej  poprzez zastosowanie funkcji haszującej. Eliminacja powtórzeń odbywa się wtedy w ramach jednego segmentu dla znacznie mniejszej liczby rekordów – można wtedy użyć sortowania wewnętrznego albo kolejnego rozrzucenia do segmentów - jeśli rozmiar segmentu jest zbyt duży aby zmieścił się w pamięci wewnętrznej.

Implementacja operatorów zbiorowych

Operatory UNION (DISTINCT) i EXCEPT są realizowane podobnie jak SELECT DISTINCT – wymagają usunięcia powtórzeń albo przez sortowanie zewnętrzne albo przez haszowanie.

Operator INTERSECT jest szczególnym przypadkiem złączenia. Na przykład, instrukcja:

SELECT Deptno FROM Dept
INTERSECT
SELECT Deptno FROM Emp;

jest równoważna:

SELECT d.Deptno
FROM Dept d, Emp e
WHERE d.Deptno=e.Deptno;

Metody realizacji operatora złączenia są omówione dalej na tym wykładzie.
 

Implementacja agregacji

Bez GROUP BY

Rozważmy przykład.

SELECT AVG(e.Sal)
FROM Emp e;

Wymagane jest albo przejście całego pliku rekordów.

Z GROUP BY

Rozważmy przykład.

SELECT e.Job, AVG(e.Sal)
FROM Emp e
GROUP BY e.Job;

Można posortować według wartości pól grupujących, przechodząc cały plik rekordów. Inną metodą realizacji grupowania może być użycie haszowania.
 

Implementacja złączenia tabel

W celu zaprezentowania metod złączania tabel rozważymy dla uproszczenia złączenie równościowe z jedną kolumną złączenia. Założymy mianowicie, że interesuje nas złączenie dowolnych tabel E i D względem i-tej kolumny w E oraz j-tej kolumny w D. To znaczy przyjmiemy, że warunkiem złączenia jest Ei=Dj.

Rozważmy przykład.

SELECT E.Ename, D.Loc
FROM Emp E, Dept D
WHERE E.Deptno = D.Deptno;

Przegląd metod złączania tabel zaczynamy od najprostszego algorytmu opartego na rozważeniu wszystkich możliwych kombinacji wierszy tabel E i D.

Algorytm Simple Nested Loops Join
foreach row e in E do
foreach row d in D do
if ei == dj then dodaj <e, d> do obliczanego wyniku;
Dla każdego wiersza tabeli E, przeglądamy wszystkie wiersze tabeli D.

Tabela E nazywa się tabelą zewnętrzną (złączenia), tabela D nazywa się tabelą wewnętrzną (złączenia).

Oczywiste ulepszenie polega na zastosowaniu postępowania:  dla każdej strony w E, sprowadź każdą stronę w D. Będziemy dalej używać metody Simple Nested Loops Join razem z tym ulepszeniem.

Algorytm Index Nested Loops Join
{E – tabela zewnętrzna złączenia, D – tabela wewnętrzna złączenia, na kolumnie złączenia Dj  jest założony indeks}
foreach row e in E do
{weź wartość  ei  kolumny złączenia Ei i poprzez indeks na Dj wyznacz wszystkie wiersze d mające tę samą wartość w kolumnie złączenia Dj (ei == dj) – połącz oba wiersze <e,d> i dodaj <e, d> do obliczanego wyniku}

Rys. 10.1 Ilustracja algorytmu Index Nested Loops Join
 

Dla każdego wiersza w E najpierw wyszukujemy pozycję danych w indeksie na kolumnie Dj . Mając pozycję danych w indeksie na kolumnie Dj, przechodzimy do wierszy w D.

Wydajność tej metody zależy od rodzaju indeksu. W przypadku indeksu głównego, jednoznacznego, pogrupowanego jej koszt jest względnie niewielki - liniowy względem liczby wierszy w tabeli zewnętrznej i nie zależy od liczby wierszy w tabeli wewnętrznej.

Natomiast w pozostałych przypadkach koszt istotnie zależy od selektywności wyszukiwania przez indeks i może być bardzo duży (nawet kwadratowy względem liczby wierszy w tabeli zewnętrznej i wewnętrznej).

Użycie klastra tabel

Można się lepiej przygotować do często występujących złączeń tabel przez umieszczenie ich w jednym klastrze z kluczem będącym kolumną złączenia obu tabel. Połączenie tabel w klaster powoduje, że złączenie odbywa się tak jakby to była pojedyncza operacja przejścia jednej tabeli. Realizacja naszego przykładowego zapytania zostanie przyśpieszona jeśli obie tabele Emp i Dept umieścimy w jednym klastrze tak jak to zrobliśmy na wykładzie 3.

Więcej informacji o implementacji i zastosowaniu klastra będzie podane na następnym wykładzie przy okazji omawiania struktur indeksowych w systemie Oracle.

W przypadku złączania gdy brak klastra albo odpowiedniego indeksu, SZBD stosuje jedną z dwóch poniższych metod.

Algorytm Sort Merge Join
Posortuj wiersze obu tabel względem wartości kolumn złączenia. Dokonaj scalenia obu ciągów produkując wynikowy zbiór wierszy.

 

Algorytm Hash Join
Rozrzuć wiersze tabel E i D do segmentów używając funkcji haszującej h1 określonej na wartościach kolumn złączenia. Powstające segmenty zapisz na dysku.

Rys. 10.2 Ilustracja algorytmu Hash Join
 

Rozpatruj kolejno odpowiadające sobie segmenty tabel E i D szukając par wierszy e i d dla których ei=dj. Nie trzeba już uzgadniać wierszy pochodzących z różnych segmentów – bo na takich wierszach wartość funkcji haszującej jest różna a więc i wartości w kolumnach złączenia też są różne. Dla każdej uzgodnionej pary wierszy, dodaj <e, d> do obliczanego wyniku.

Jeśli rozmiary jednej z par odpowiadających sobie segmentów są tak duże, że żaden z nich nie mieści się w pamięci wewnętrznej, należy do nich zastosować drugą funkcję haszującą h2 (istotnie inną niż h1) i powtórzyć postępowanie opisane powyżej.

 

Złączanie tabel obiektowo-relacyjnych

Przy złączaniu tabel obiektowo-relacyjnych możemy skorzystać z referencji i kolekcji referencji. Obie operacje zarówno przejście przez referencję jak i przejście przez kolekcję referencji są szybsze niż odpowiednie operacje przejścia przez indeksy zewnętrzne dla tabel relacyjnych. Wadą referencji i kolekcji referencji (oprócz utraty niezależności od wartości modelu fizycznego) jest dodatkowy narzut czasowy i miejsca na dysku związany z reprezentacją i przetwarzaniem kolekcji (rekord zawierający obszerną kolekcję referencji może wymagać więcej niż jednej strony do zapisu; przejście do rekordów wskazywanych przez referencje wymaga sprowadzenia tylu stron ile jest referencji w kolekcji.)
Porównanie metod złączania

Gdy SZBD chce wykonać złączenie tabel, rozważa możliwe metody w następującej kolejności:

  • Gdy jest zbudowany klaster, złączenie tabel sprowadza się do przejścia klastra tak jakby to była jedna tabela. Kluczem klastra powinna być kolumna złączania tabel.

  • W przypadku złączania tabel, których powiązanie jest określone nie przez związek klucz obcy-klucz główny ale bezpośrednio przez referencje, możemy zastosować przejścia przez te referencje. Przeciwskazaniem może być tylko przewidywana duża liczba referencji do przejścia (duża liczba stron do sprowadzenia do pamięci wewnętrznej).

  • Metoda Simple Nested Loops Join jest prosta i to jest jej podstawowa zaleta. Może być używana w sytuacji, gdy jedna ze złączanych tabel ma niewielki rozmiar.

  • Na koszt metody Index Nested Loops Join istotny wpływ mają własności indeksu np. czy jest pogrupowany, czy jest selektywny jak np. indeks główny, jednoznaczny. W połączeniu z selekcją na tabeli zewnętrznej złączenia bywa najszybszą metodą.

  • Metoda Hash Join  wypada lepiej w oszacowaniach średniej liczby operacji We/We niż metoda Sort-Merge ale w przypadku pesymistycznym może się okazać bardzo zła.

  • Metoda Hash Join wypada lepiej od Sort-Merge gdy rozmiary sortowanych plików zasadniczo się różnią. Jest łatwiejsza do zrównoleglenia niż Sort-Merge.

  • Metoda Sort Merge jest lepsza gdy rozmiary sortowanych plików są zbliżone. Jest mniej wrażliwa na mało losowe dane oraz rezultat złączenia jest posortowany.

 Strategia tylko-indeks

Przy realizacji operatorów selekcji, projekcji, agregowania i grupowania w przypadku gdy wszystkie elementy klauzul instrukcji SELECT należą do klucza wyszukiwania jednego indeksu – można ograniczyć się do przejścia tylko pliku indeksowego zamiast całego pliku rekordów. Metoda ta nosi nazwę strategii tylko-indeks. Jej zastosowanie wymaga aby wszystkie potrzebne do wyznaczenia wyniku zapytania wiersze tabeli były indeksowane.

Na przykład, jeśli mamy indeks założony na kolumnach Ename i Comm tabeli Emp oraz w kolumnie Ename nie występuje pseudo-wartość NULL (np. z powodu użycia więzów spójności NOT NULL na kolumnie Ename w tabeli Emp), to możemy strategię tylko-indeks zastosować do obliczenia wyniku instrukcji:

SELECT e.Ename, e.Comm
FROM Emp e;
jak również w przypadku indeksu założonego tylko na kolumnie Comm w przypadku instrukcji:

SELECT Avg(e.Comm)
FROM Emp e;

ponieważ to czy w kolumnie Comm występuje NULL nie ma tu znaczenia, bowiem operator Avg nie bierze w ogóle pod uwagę pseudo-wartości NULL.

 
 

10.2 Optymalizacja zapytań

Zapytanie SQL ma charakter deklaratywny: określa co ma być wyznaczone w bazie danych, a nie jak to ma być znalezione. Dla każdego zapytania istnieje wiele sposobów jego realizacji. Który sposób jest najlepszy, zależy od dodatkowych okoliczności. SZBD rozważa różne alternatywy, szacuje ich koszt oraz wybiera możliwie najlepszy, "optymalny" plan. Proces ten nazywa się optymalizacją zapytania a moduł go realizujący optymalizatorem zapytań.

  1. W SZBD zapytaniem najpierw zajmuje się parser, dokonujący analizy składniowej zapytania.
  2. Po analizie składniowej włącza się optymalizator zapytań w skład którego wchodzą dwa główne moduły:
  3. Przy szacowaniu kosztu planu estymator korzysta z informacji statystycznych zapisanych w słowniku danych (katalogu systemowym) takich jak: liczba rekordów w pliku, liczba stron na których są zapisane rekordy w pliku, liczba różnych wartości w kolumnie, rozkład wartości w kolumnie (histogram).
  4. Optymalizator wybiera plan o najniższym koszcie i przekazuje go do ewaluatora planu - modułu wykonującego zapytanie.
  5. Gdy zapytanie zostało wcześniej przeanalizowane i kontekst jego użycia się nie zmienił, system może użyć wyliczony wcześniej plan.

Rys. 10.3 Schemat optymalizatora zapytań
 

Plan wykonania zapytania obejmuje:

Niektóre plany wykonania zapytania nie korzystają z tymczasowych tabel - działając w miejscu.  Ich działanie polega na tym, że przy określonym sposobie dostępu do rekordów każdej tabeli utrzymuje się tylko kursory przebiegające rekordy w plikach (ewentualnie pozycje danych w pliku indeksowym) bez zapisywania pomocniczych tabel. Unikamy w ten sposób zapisywania tymczasowych wyników na dysk aby je potem sprowadzać powtórnie do pamięci RAM.

Plany mające postać drzewa skierowanego w lewo (omawiane dalej) w powiązaniu z metodami Simple Nested Loops Join i Index Nested Loops Join umożliwiają działanie w miejscu. Natomiast metody Sort-Merge Join i Hash Join wymagają użycia pomocniczych plików na dysku, więc nie działają w miejscu. Zastosowanie klastra lub kolekcji referencji zamiast operatora złączenia też umożliwia działanie w miejscu.

Jeśli chodzi o połączenie ze sobą operatorów w planie wykonania zapytania, to jest używana zasada przetwarzania potokowego. Wynik jednego operatora jest przekazywany na wejście drugiego operatora. Oznacza to, że nie jest potrzebna tymczasowa tabela, więc też mamy do czynienia z działaniem w miejscu.

W przykładach będziemy używać oznaczeń na operatory SQL zebranych w Tabeli 10.1.

Operator Symbol
Selekcja
Projekcja
Złączenie

Tab. 10.1 Oznaczenia operatorów relacyjnych
 

Zapytanie jest przedstawiane w postaci drzewa operatorów SQL. Na przykład, zapytanie

SELECT E.Ename
FROM Emp E, Dept D
WHERE E.Deptno=D.Deptno AND
    E.Mgr=100 AND D.Loc='Oz';

jest reprezentowane przez drzewo:

Rys. 10.4 Drzewo operatorów instrukcji SQL
 

Plan 1

Najprostszy plan wykonania tego zapytania to:

Rys. 10.5 Najprostszy plan wykonania zapytania
 

Plan ten działa w miejscu (bez tymczasowych tabel) i nie wykorzystuje indeksów. Nie jest zbyt dobry.

Plan 2

Rozważmy następujący alternatywny plan:

Rys. 10.6 Plan stosujący ograniczanie przed złączeniem
 

Główna różnica z poprzednim planem polega na tym, że zanim rozpocznie się złączanie rekordów - najpierw są wykonywane selekcje. Jest nadzieja, że istotnie ograniczą one liczbę złączanych rekordów w porównaniu z poprzednim planem. Przed złączaniem, oprócz selekcji, można byłoby jeszcze dokonywać eliminacji nie używanych dalej kolumn czyli, inaczej mówiąc, moglibyśmy zastosować projekcje Ename,Deptno dla Emp oraz Deptno dla Dept. W ten sposób zmniejszylibyśmy rozmiar tabel tymczasowych T1 i T2 a co za tym idzie również liczbę operacji We/Wy.

Drobna zmiana w powyższym planie polegałaby na zastąpieniu operacji scan wyszukiwaniem przez indeksy odpowiednio na kolumnach E.Mgr i D.Loc. W przypadku indeksów: pogrupowanego na B+ drzewie lub o dobrej selektywności zmiana istotnie przyśpieszyłaby cały proces obliczeniowy.

Plan 3

Rozważmy jeszcze jeden alternatywny plan tym razem taki, w którym złączenie jest oparte na indeksie (czyli jest stosowana metoda Index Nested Loops Join). Dodatkowo na tabeli zewnętrznej złączenia stosujemy selekcję przez indeks, która może istotnie ograniczyć liczbę wierszy rozpatrywanych jako kandydaci do złączenia.

Rys. 10.7 Plan zorientowany na stosowanie indeksów i przetwarzanie potokowe
 

Zauważmy, że:

Generowanie przez optymalizator planów wykonania zapytania

Jest dużo możliwych planów wykonania jednego zapytania, ponieważ kolejność wykonywania złączeń jest dowolna na podstawie praw przemienności i łączności operatora złączenia.

Ze względu na dużą liczbę możliwości optymalizator ogranicza się do pewnej klasy wszystkich drzew tzw. drzew skierowanych w lewo.

Drzewo skierowane w lewo zawiera "rdzeń" w postaci gałęzi węzłów, na której każdy kolejny węzeł jest lewym następnikiem poprzedniego i tylko węzły leżące na tej gałęzi mogą mieć stopień dwa odpowiadający operatorowi złączenia (pozostałe węzły w drzewie mają stopień 0 lub 1).

Z trzech drzew na rysunku 10.8 tylko środkowe jest skierowane w lewo. Drzewa skierowane w lewo dają plany umożliwiające "potokowe" wykonywanie zapytania "w miejscu" tj. bez tymczasowych plików.

Oczywiście złączanie metodą Sort Merge Join czy Hash Join wymaga zapisywania pomocniczych plików, więc nawet jeśli zastosujemy plan oparty o drzewo skierowane w lewo, to wykonanie zapytania nie będzie działać potokowo „w miejscu”.

Rys. 10.8 Tylko środkowe drzewo jest skierowane w lewo
 

Zauważmy, że dla zapytania zawierającego n-1 operatorów złączenia jest co najmniej n! drzew skierowanych w lewo odpowiadających n! permutacjom operatorów złączenia.

Przykład

Faza 1: Generujemy drzewo planu wykonania zapytania: Emp - tabela zewnętrzna, Dept - tabela wewnętrzna. (Drugie możliwe drzewo to wariant pierwszego drzewa, w którym z lewej strony znajduje się tabela Dept a z prawej Emp.)

Rys. 10.8 Drzewo operatorów instrukcji SQL
 

Faza 2: Analiza planów dostępu do wierszy tabel Emp i Dept:

Emp:

Dept:

Faza 3: Rozpatrujemy każdy plan dostępu, bierzemy pod uwagę możliwe dla tego planu dostępu metody złączenia (SNLJ, INLJ, SMJ, HJ) i liczymy orientacyjny koszt korzystając ze statystyk zebranych przez system takich jak liczba wierszy w tabeli, liczba stron w pliku z danymi i w pliku indeksu.
 

Podzapytania

Podzapytania są optymalizowane niezależnie od głównego zapytania. Główne zapytanie jest optymalizowane z branym pod uwagę kosztem „wywoływanych” podzapytań. Alternatywnie, podzapytanie jest sprowadzane do złączeń i optymalizowane łącznie z całym zapytaniem.
 

Ogólne strategie optymalizacyjne

 

10.4 Podsumowanie

W wykładzie 10 zostały omówione metody implementacji operatorów relacyjnych stanowiących cegiełki, z których składa się całe zapytanie SQL. Implementację tych operatorów można dokładnie dostroić. Zostały omówione podstawowe zasady wykonywania zapytań w tym podstawowy problem optymalizacji zapytania. 
 

10.5 Słownik pojęć

operator relacyjny - selekcja, projekcja, złączenie, suma i agregacja. Wykonywanie zapytania SQL sprowadza się do złożenia implementacji tych podstawowych operatorów.

selekcja - operator relacyjny polegający na ograniczeniu pliku rekordów do podzbioru.

projekcja - operator relacyjny polegający na ograniczeniu pliku rekordów do wybranych pól.

suma (union) - operator relacyjny polegający na zsumowaniu dwóch plików rekordów.

agregacja - operator relacyjny polegający na wyliczeniu statystyk na danym pliku rekordów według podziału na grupy rekordów.

złączenie - operator relacyjny polegający na połączeniu dwóch plików rekordów według wartości wspólnych pól.

Simple Nested Loops Join - metoda złączenia polegająca na rozpatrzeniu po kolei każdego rekordu z pierwszego pliku rekordów a z kolei dla niego przejrzenia wszystkich rekordów z drugiego pliku w poszukiwaniu wszystkich par rekordów, które dadzą się złączyć ze sobą.

Index Nested Loops Join - metoda złączenia polegająca na rozpatrzeniu po kolei każdego rekordu z pierwszego pliku rekordów a z kolei dla niego zastosowania wyszukiwania przez indeks w celu wyznaczenia wszystkich rekordów z drugiego pliku, które dadzą się z nim złączyć.

Sort Merge Join - metoda złączenia polegająca na posortowaniu plików rekordów według wartości w kolumnach złączenia a następnie dokonaniu ich scalenia.

Hash Join - metoda złączenia polegająca na rozrzuceniu rekordów w złączanych plikach rekordów według wartości funkcji haszującej na wartościach w kolumnach złączenia a następnie dokonaniu ich scalenia.

optymalizacja zapytań -  zadanie wykonywane przez SZBD polegające na analizie różnych planów wykonania zapytania SQL i wyboru "najoptymalniejszego".

optymalizator zapytań - moduł SZBD, którego zadaniem jest znaleźć możliwie najlepszy ("optymalny") plan wykonania zapytania SQL.
 

10.6 Zadania

1. Zastanów się nad implementacją złożonej selekcji F1 AND F2 gdzie F1 i F2 są prostymi predykatami równościowymi. Jakie widzisz możliwości?

2. Zastanów się nad implementacją złożonej selekcji F1 OR F2 gdzie F1 i F2 są prostymi predykatami równościowymi. Jakie widzisz możliwości?

3. Uzasadnij, że operator INTERSECT jest szczególnym przypadkiem operatora złączenia. Które algorytmy złączenia są odpowiednie dla INTERSECT?

4. Czy zastosowanie indeksu może przyśpieszyć realizację projekcji?

5. Czy zastosowanie indeksu może przyśpieszyć realizację klauzuli HAVING?

Strona przygotowana przez Lecha Banachowskiego - 12/04/05 .