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.
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:
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ą.
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:
przejście sekwencyjne całego pliku rekordów (operacja scan),
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:
gdy indeks jest główny lub jednoznaczny,
gdy indeks jest pogrupowany oraz wyszukiwanie jest zakresowe,
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.
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.
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.
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.
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.
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.
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).
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.
Posortuj wiersze obu tabel względem wartości kolumn złączenia. Dokonaj scalenia obu ciągów produkując wynikowy zbiór wierszy. |
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. |
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:
|
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.
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ń.
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:
E.Mgr=100 AND D.Loc='Oz'
;
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:
E.Mgr=100
oraz
odpowiednio D.Loc='Oz'
; wyniki selekcji zapisujemy w dwóch tymczasowych
tabelach;
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.
E.Mgr=100
. D.Deptno=E.Deptno
)
do niego wiersze z tabeli D.D.Loc='Oz'
a na koniec dokonujemy
projekcji na kolumnę E.Ename.
Rys. 10.7 Plan zorientowany na stosowanie indeksów i przetwarzanie potokowe
Zauważmy, że:
E.Mgr=100
oznaczająca, że liczba pracowników
mających kierownika o numerze 100 jest niewielka.
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 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.
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.
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.
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?