Wykład 10

Wykonywanie zapytań. Projektowanie fizycznej bazy danych i jej dostrajanie.

 

Streszczenie

Wykład składa się z trzech 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.

W trzeciej części są omówione zasady projektowania fizycznego schematu bazy danych i jego dostrajanie: jakie założyć indeksy, czy pogrupować tabele w klastry, jak poprawić schemat logiczny bazy danych z punktu widzenia szybkości działania zapytań.

 

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 (operator INNER JOIN).
  4. Operatory algebraiczne UNION ALL, UNION DISTINCT, INTERSECT i EXCEPT na tabelach.
  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ą.

Na tym i na następnym wykładzie mówiąc "indeks pogrupowany" będziemy mieć na myśli "indeks pogrupowany zbudowany na B+ drzewie".

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 pierwszy metody jest wskazany,

  1. gdy tabela jest mała,
  2. gdy nie ma odpowiedniego indeksu do zastosowania,
  3. gdy zachodzi potrzeba posortowania wyników według porządku określonego w klauzuli ORDER BY.

Wybór drugiej metody jest wskazany w czterech przypadkach:

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

  2. gdy indeks jest haszowany wewnętrzny oraz wyszukiwanie jest równościowe,

  3. gdy indeks jest pogrupowany oraz wyszukiwanie jest zakresowe (w tym oczywiście równościowe),

  4. 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 zewnętrznego (np. nie pogrupowanego) wskazane jest, jeśli możliwe, posortowanie wskaźników zwracanych rekordów według adresów stron dyskowych i ściągnięcie każdej potrzebnej strony tylko jeden raz.

W szczególnym przypadku gdy wszystkie elementy klauzul SELECT i WHERE należą do klucza wyszukiwania jednego indeksu – wystarczy przejść tylko indeks. Metoda ta nosi nazwę strategii tylko-indeks. Pewne jej ograniczenie stanowi sprawa obsługi pseudo-wartości NULL w indeksie - rozważymy ten problem w dalszej części wykładu.

Czasami warto do klucza wyszukiwania dodać jedno lub więcej pól aby umożliwić zastosowanie tej metody np. do indeksu opartego na nazwisku pracownika możemy rozważyć dodanie zarobków i/albo numeru działu.

Takie użycie indeksu przypomina użycie perspektywy zmaterializowanej. Zamiast indeksu można więc użyć perspektywy zmaterializowanej, szczególnie wtedy, gdy rozmiar wyniku jest większy.  Warto zauważyć, że w przeciwieństwie do indeksu stosując perspektywę zmaterializowaną zachowujemy w niej wszystkie pseudo-wartości NULL.

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ń. Oto możliwe metody jej realizacji:

  1. Eliminację powtórzeń można uzyskać przez posortowanie zbioru wyników zapytania.
  2. 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.
  3. Gdy wszystkie elementy klauzul SELECT i WHERE należą do klucza wyszukiwania jednego indeksu – wystarczy przejść tylko ten indeks nie sięgając w ogóle do pliku rekordów z danymi (strategia tylko-indeks ze zwróceniem uwagi na problem pseudo-wartości NULL).

Implementacja operatorów zbiorowych

Operator UNION ALL polega na przepisaniu wyników otrzymanych ze składowych zapytań.

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

Ponieważ dla operatora UNION domyślnie jest przyjmowana opcja UNION DISTINCT, system będzie się zawsze starał usunąć duplikaty z połączenia obu zbiorów wyników. W przypadku gdy projektant wie, że zbiory wyników są rozłączne, może użyć explicite operatora UNION ALL, co spowoduje że system pominie usuwanie duplikatów, które istotnie spowolniłoby wykonanie operatora UNION.

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

SELECT a.Deptno FROM Dept a
INTERSECT
SELECT b.Deptno FROM Emp b;

jest równoważna:

SELECT DISTINCT a.Deptno
FROM Dept a INNER JOIN Emp b ON a.Deptno=b.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 albo tylko indeksu jeśli zbiór kolumn w SELECT i WHERE jest podzbiorem klucza wyszukiwania indeksu (w tym przypadku nie ma problemu pseudo-wartości NULL, bo AVG nie bierze ich pod uwagę).

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 bądź tylko indeks jeśli elementy występujące w SELECT, WHERE i GROUP BY (i ewentualnie HAVING) są podzbiorem klucza wyszukiwania indeksu (strategia tylko-indeks). Inną metodą realizacji grupowania może być użycie haszowania.

Warto tutaj wspomnieć o jeszcze jednej metodzie implementacji agregacji, którą wykorzystuje się w sytuacjach, gdy wyliczenie agregacji wymaga dużego czasu i kiedy z wyników agregacji korzysta się w wielu zapytaniach. W takich sytuacjach wyniki agregacji są "materializowane" za pomocą perspektywy zmaterializowanej. Była o tym już mowa w wykładzie na temat hurtowni danych. Metodę tę można zresztą użyć w przypadku dowolnych obliczeń nie tylko agregacji.

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 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.

W celu porównania kosztu poszczególnych metod wprowadzimy następujące oznaczenia. Niech:

Koszt tak jak poprzednio będziemy mierzyć liczbą operacji We-Wy. Pomijamy koszt zapisu wyniku do pliku, bo jest on taki sam przy każdej metodzie.

Rozważmy przykład.

SELECT E.Ename, D.Loc
FROM Emp E INNER JOIN Dept D ON 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.  Koszt wynosi NE + (pE * NE) * ND.

Tabela E nazywa się tabelą zewnętrzną (złączenia), tabela D nazywa się tabelą wewnętrzną (złączenia). Jak widać wzór nie jest symetryczny względem NE i ND, jest więc istotne, którą tabelę wybierzemy za zewnętrzną a którą za wewnętrzną.

Oczywiste ulepszenie polega na zastosowaniu postępowania:  dla każdej strony w E, sprowadź każdą stronę w D. Koszt wynosi NE + NE*ND. 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

Koszt wynosi:

NE + ((NE*pE) * średni koszt wyznaczenia pasujących wierszy w D)

Dla każdego wiersza w E najpierw wyszukujemy pozycję danych w indeksie na kolumnie Dj . Koszt tego kroku, zgodnie z przyjętymi oszacowaniami, wynosi:

  1. ~ 1.2 - dla indeksu haszowanego;
  2. ~ 3    - dla B+ drzewa.

Niech pas oznacza średnią liczby wierszy w D pasujących do wiersza w E. Wielkość pas jest więc miarą selektywności wyszukiwania przez indeks na kolumnie Dj.

Mając pozycję danych w indeksie na kolumnie Dj, przechodzimy do wierszy w D. Koszt tego kroku zależy od rodzaju indeksu.

  1. Dla indeksu haszowanego wewnętrznego koszt jest 0. Co daje łączny koszt w przybliżeniu NE + 1.2NE*pE.
  2. Dla indeksu haszowanego zewnętrznego głównego lub jednoznacznego koszt wynosi 1. Co daje łączny koszt w przybliżeniu NE + 2.2NE*pE.
  3. Dla indeksu pogrupowanego (na B+ drzewie) koszt jest 0. Co daje łączny koszt w przybliżeniu NE + 3NE*pE.
  4. Dla indeksu zewnętrznego (na B+ drzewie) głównego lub jednoznacznego koszt jest 1. Co daje łączny koszt w przybliżeniu NE + 4NE*pE.
  5. Dla indeksu haszowanego zewnętrznego koszt wynosi pas gdzie, przypominamy, że pas jest średnią liczbą wierszy w D pasujących do wiersza w E.  Co daje łączny koszt w przybliżeniu NE + (1.2+pas)(NE*pE).
  6. Dla indeksu zewnętrznego (na B+ drzewie) koszt też wynosi pas. Co daje łączny koszt w przybliżeniu NE+ (3+pas)(NE*pE).

W przypadkach 1-4 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 przypadkach 5 i 6 koszt istotnie zależy od selektywności wyszukiwania przez indeks - wyrażonego we wzorze parametrem pas 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 zrobiliśmy na wykładzie 3.

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

Algorytm Sort Merge Join
Stosując algorytm wielofazowego sortowania zewnętrznego, posortuj wiersze obu tabel względem wartości kolumn złączenia. Dokonaj scalenia obu ciągów produkując wynikowy zbiór wierszy.

Koszt algorytmu Sort Merge Join jest w przybliżeniu równy 8M + 8N + (M+N) = 9M+9N operacji We-Wy.

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.

Koszt algorytmu Hash Join mierzony liczbą operacji We/Wy jest w przybliżeniu równy (2M+2N)+ (2M+2N)+(M+N) = 5M+5N przy założeniu dwukrotnego rozrzucenia do segmentów. Przy jednokrotnym rozrzuceniu byłoby tylko 3M+3N.

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, bowiem rekord zawierający obszerną kolekcję referencji może wymagać więcej niż jednej strony do zapisu a 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 referencję, możemy zastosować przejścia przez te referencje. Przeciw-wskazaniem może być tylko przewidywana duża liczba referencji do przejścia (duża liczba stron do sprowadzenia do pamięci wewnętrznej - po jednej dla każdego rekordu).

  • Metoda Simple Nested Loops Join jest prosta i to jest jej podstawowa zaleta. Może być używana w sytuacjach, 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 lub wewnętrzny haszowany czy jest selektywny jak np. indeks główny czy jednoznaczny. W połączeniu z selekcją na tabeli zewnętrznej złączenia metoda ta bywa najszybszą metodą realizacji złączenia.

  • 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

Strategia tylko-indeks pozwala sprowadzić wykonanie zapytania do przejścia pliku indeksowego, co istotnie może przyśpieszyć wykonanie zapytania. Jest jednak jeden aspekt, który SZBD musi dodatkowo wziąć pod uwagę (a także osoba projektująca zapytanie), mianowicie obsługę pseudo-wartości NULL. Mianowicie, 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 lub z powodu posiadania przez optymalizator informacji, że w rozważanej kolumnie nie ma NULL), to możemy strategię tylko-indeks zastosować do obliczenia wyników instrukcji:

SELECT e.Ename, e.Comm
FROM Emp e
ORDER BY e.Ename;

i
SSELECT e.Ename
FROM Emp e
WHERE e.Comm IS NULL;

jak również w przypadku indeksu założonego tylko na kolumnie Comm w przypadku instrukcji:

SELECT e.Comm
FROM Emp e
WHERE e.Comm IS NOT NULL;

i

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 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:
    • generator planów - moduł generujący możliwe plany wykonania zapytania, i
    • estymator kosztu - moduł obliczający przybliżony koszt wykonania zapytania według danego planu.
  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:

Następujące dwie własności planu wykonania zapytania są pożądane:

  1. Działanie w miejscu.
  2. Przetwarzanie potokowe.

Działanie w miejscu

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.

Przetwarzanie potokowe

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 metoda ta umożliwia działanie 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 INNER JOIN Dept D ON E.Deptno=D.Deptno
WHERE  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. Jednak nie jest zbyt dobry, w przypadku gdy obie złączane tabele są duże.

Plan 2

Rozważmy następujący alternatywny plan:

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

Główna różnica z planem poprzednim 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: wewnętrznego haszowanego, 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. Wynika to w szczególności z faktu, że kolejność wykonywania złączeń może być dowolna na podstawie praw przemienności i łączności operatora złączenia.

Ze względu na dużą liczbę możliwych kolejności wykonania złączeń, 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 n argumentów operatorów złączenia.

Przykład

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

Rys. 10.9 Drzewo operatorów instrukcji SQL
 

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

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 (w tym perspektywy lokalne inline)

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.3 Projektowanie fizycznej bazy danych

Ulepszanie schematu tabel i postacie normalne

Redundancja na poziomie logicznym (schematu tabel) pociąga za sobą redundancję zapisu na nośniku danych, bo wymagane jest więcej miejsca na dysku, oraz anomalie przy wstawianiu, usuwaniu i aktualizacji danych. Redundancje w schemacie tabel są eliminowane przy użyciu analizy zależności funkcyjnych i dekompozycji tabel na mniejsze. Jednak wówczas może się okazać, że do wykonania zapytania będzie potrzebne złączenie dwóch lub więcej tabel, co może istotnie zwiększyć czas realizacji zapytania.

  1. Jeśli wszystkie tabele są w postaci normalnej BCNF (Boyce'a-Codda), to są one wolne od redundancji związanych z zależnościami funkcyjnymi.
  2. Jeśli tabela nie jest w postaci BCNF, staramy się dokonać jej dekompozycji na zbiór tabel w postaci BCNF:
    • Jeśli przy dekompozycji nie daje się zachować zależności funkcyjnych – poprzestajemy na trzeciej postaci normalnej.
    • Jednocześnie z dekompozycjami bierzemy pod uwagę wymagania dotyczące szybkości działania zapytań na bazie danych; jeśli wymaganie szybkości działania ma charakter priorytetowy a dekompozycja istotnie spowalnia wykonanie zapytania – nie doprowadzamy procesu dekompozycji do końca, albo dokonujemy logicznej denormalizacji - połączenia dwóch rozdzielonych tabel w jedną. Aby przyśpieszyć złączanie tabel - alternatywą może być:
      • zbudowanie klastra tabel (fizyczna denormalizacja),
      • albo, jeśli zbudowanie klastra nie jest możliwe,  skorzystanie z kolumn typu referencji i kolekcji referencji (w miejscu odpowiednio kolumn klucza obcego i głównego).
  3. Gdy aplikacja przetwarza osobno dwa zbiory wierszy może opłacać się rozdzielić tabelę na dwie np. tabelę Osoby na tabele: Studenci i Pracownicy. Tutaj dekompozycja jest pozioma, przy normalizacji natomiast, dekompozycja jest pionowa.
  4. Sprawdzamy czy tabela jest wolna od zależności wielowartościowych. Jeśli nie, dokonujemy odpowiedniej dekompozycji.

Projektowanie indeksów

W pierwszej kolejności określamy pole działania (ang. workload) tworzonej aplikacji bazodanowej.

Pole działania aplikacji bazodanowej tworzą:

Dla każdego zidentyfikowanego zapytania:

Dla każdej zidentyfikowanej aktualizacji:

W oparciu o zebrane informacje projektant bazy danych podejmuje decyzje:

Jeszcze krótkie podsumowanie projektowania indeksów:

Rozważymy teraz na przykładach problem projektowania indeksów. Przypominamy, że potrzeba założenia indeksu ma swoje źródło w wymaganiu szybkiego wykonania jednego lub więcej zapytań na budowanej bazie danych.

Przykład 1

SELECT E.Ename, D.Loc
FROM Emp E INNER JOIN Dept D ON E.Deptno=D.Deptno
WHERE D.Dname='SALES';

Indeks na D.Dname wspomaga selekcję D.Dname='SALES' gdy D jest  tabelą zewnętrzną. Potrzebny jest indeks albo jednoznaczny albo selektywny albo pogrupowany albo haszowany wewnętrzny.

Indeks na kluczu obcym E.Deptno wspomaga złączenie (E – tabela wewnętrzna). Powinien być pogrupowany albo haszowany wewnętrzny, ponieważ spodziewamy się wybrania wielu wierszy z E.

Jeszcze lepszym rozwiązaniem byłby klaster obu tabel. Wtedy złączenie sprowadzilibyśmy do selekcji przez indeks na kolumnie D.Dname na klastrze tabel Dept i Emp zbudowanym na kolumnie D.Deptno. Przy odpowiednim zapisie klastra (jak w implementacji Oracle opisanej w w wykładzie 9) dla danego departamentu rekordy wszystkich pracowników pracujących w tym departamencie byłyby zapisane na tej samej stronie co rekord departamentu lub tylko na kilku. Zastosowanie klastra jest więc szczególnie istotne gdy selekcja dotyczy tabeli po stronie jeden związku między tabelami (to jest po stronie klucza głównego) a dołączane przy złączaniu rekordy pochodzą z tabeli po stronie klucza obcego.

W krytycznych zastosowaniach można byłoby pomyśleć o zaprojektowaniu perspektywy zmaterializowanej liczącej tę konkretną instrukcję SELECT. Wynik byłby dostępny natychmiast.

Można byłoby też pomyśleć o perspektywie zmaterializowanej liczącej całe złączenie tabel Dept i Emp:

SELECT D.Dname, E.Ename, D.Loc
FROM Emp E INNER JOIN Dept D ON E.Deptno=D.Deptno;

i założenie odpowiedniego indeksu na kolumnie D.Dname (pogrupowanego lub wewnętrznego haszowanego) w celu przyśpieszenia wyszukiwania po kolumnie D.Dname.

Przykład 2

SELECT E.Ename, D.Loc
FROM Emp E INNER JOIN Dept D ON E.Deptno=D.Deptno
WHERE E.Sal BETWEEN 10000 AND 20000 AND E.Job='SALESMAN';

Ze względu na warunki ograniczające dla tabeli E, wybieramy Emp E jako tabelę zewnętrzną złączenia. Wtedy Dept D będzie tabelą wewnętrzną złączenia.

Kolumna D.Deptno jest kluczem głównym, posiada zawsze indeks, który można użyć przy złączaniu.

Jaki indeks jest potrzebny na tabeli Emp E? Albo indeks na E.Sal albo na E.Job – wybór zależy od selektywności warunków wyszukiwania - przy złej selektywności potrzebny byłby indeks pogrupowany na E.Sal, ewentualnie indeks haszowany wewnętrzny na E.Job.

Alternatywnie system może zastosować przejście całego pliku rekordów (scan) tabeli E - wtedy ewentualne indeksy w E nie byłyby zastosowane.

Można byłoby rozważyć wariant, w którym tabelą zewnętrzną jest D, a wewnętrzną jest E - co mogłoby być korzystne pod warunkiem, że indeks na kolumnie klucza obcego E.Deptno miałby pożądane własności np. gdyby był pogrupowany lub haszowany wewnętrzny.

Klaster też mógłby być zastosowany do przyśpieszenia wykonania zapytania. Tym razem selekcja dotyczy tabeli po stronie wiele (to jest po stronie klucza obcego): dla rekordu pracownika obok na tej samej stronie moglibyśmy odczytać rekord departamentu.

Przykład 3

SELECT E.Deptno, COUNT(*)
FROM Emp E
WHERE E.Sal>2000
GROUP BY E.Deptno;

Potrzebny jest indeks pogrupowany albo haszowany wewnętrzny na kolumnie E.Deptno. Jeśli nie jest możliwe założenie takiego indeksu, system posortuje względem E.Deptno plik rekordów tabeli Emp E - biorąc pod uwagę tylko rekordy dla których E.Sal>2000. Następnie wykona zliczania COUNT(*).

Byłoby jeszcze lepiej, gdybyśmy dysponowali indeksem drzewowym na kolumnach <E.Deptno, E.Sal>. Wtedy moglibyśmy wykonać zapytanie przechodząc tylko indeks bez potrzeby przechodzenia do pliku rekordów – tzn. stosując strategię tylko-indeks.

Przykład 4

Pewne zapytania, jak ostatnie, można wykonać bezpośrednio przez indeks - bez przechodzenia do pliku rekordów. Tak jak wskazywaliśmy to już poprzednio w każdym konkretnym przypadku trzeba wziąć pod uwagę problem związany z pseudo-wartościami NULL. Oto kilka dodatkowych przykładów:
 
(a)

 

SELECT D.Dname
FROM Dept D INNER JOIN Emp E ON D.Deptno=E.Deptno;

W tym przypadku wystarczy dowolny indeks na E.Deptno, ponieważ w ogóle nie trzeba przechodzić do pliku rekordów tabeli E! Zapytanie jest realizowane przez przejście (scan) całego pliku rekordów tabeli D i za każdym razem sięgnięcie do indeksu na E.Deptno w celu sprawdzenia czy istnieje pozycja danych z wartością klucza wyszukiwania równą D.Deptno. W tym przypadku występowanie pseudo-wartości NULL nie jest istotne. Dlaczego?
 
(b)

 

SELECT E.Deptno, COUNT(*)
FROM Emp E
GROUP BY E.Deptno;

Wystarczy dowolny indeks na E.Deptno, ponieważ nie trzeba przechodzić do pliku rekordów tabeli E. W tym przypadku jest istotne, że w kolumnie E.Deptno nie ma pseudo-wartości NULL, inaczej strategii tylko-indeks nie można byłoby zastosować.
 
(c)

 

SELECT E.Deptno, MIN(E.sal)
FROM Emp E
GROUP BY E.Deptno;

Przydałby się indeks drzewowy na <E.Deptno, E.sal>. Wtedy nie trzeba byłoby przechodzić do pliku rekordów tabeli E.
 
(d)

 

SELECT AVG(E.Sal)
FROM Emp E
WHERE E.Deptno=25 AND E.Sal BETWEEN 3000 AND 5000;

Przydałby się indeks drzewowy na <E.Deptno,E.Sal> lub na <E.Sal, E.Deptno>. Wtedy nie trzeba by było przechodzić do pliku rekordów tabeli E. W tym przypadku występowanie pseudo-wartości NULL nie jest istotne. Dlaczego?

Heurystyki optymalizacyjne dotyczące zapytań i indeksów

 

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 zasady wykonywania zapytań w tym podstawowy problem optymalizacji zapytania.

Zostały też omówione zasady projektowania fizycznego schematu bazy danych i jego dostrajanie: jakie założyć indeksy, czy pogrupować tabele w klastry, jak poprawić schemat logiczny bazy danych z punktu widzenia szybkości działania zapytań.
 

10.5 Słownik pojęć

operator relacyjny - jeden z następujących: selekcja, projekcja, złączenie, suma i agregacja. Wykonanie 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 (przy założeniu tego samego schematu).

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.

pole działania - składa się z informacji o aplikacji bazy danych:

 

10.6 Sprawdzenie wiedzy

  1. Kiedy rekomendowane jest użycie indeksu przy realizacji selekcji:

    Gdy indeks jest główny.
    Gdy rozmiar zbioru wyników wynosi 50%
    Gdy rozmiar zbioru wyników wynosi co najwyżej 5%
    Gdy indeks jest pogrupowany oraz wyszukiwanie jest zakresowe

  2. Której metody używa algorytm Simple Nested Loops Join:

    indeksu dla tabeli wewnętrznej złączenia
    indeksu dla tabeli zewnętrznej złączenia
    sortowania
    haszowania

  3. Której metody używa algorytm Index Nested Loops Join:

    indeksu dla tabeli wewnętrznej złączenia
    indeksu dla tabeli zewnętrznej złączenia
    sortowania
    haszowania

  4. Której metody używa algorytm Sort Merge Join:

    indeksu dla tabeli wewnętrznej złączenia
    indeksu dla tabeli zewnętrznej złączenia
    sortowania
    haszowania

  5. Której metody używa algorytm Hash Join:

    indeksu dla tabeli wewnętrznej złączenia
    indeksu dla tabeli zewnętrznej złączenia
    sortowania
    haszowania

  6. Którego modułu SZBD jest częścią generator planów?

    zarządzania miejscem na dysku
    zarządzania buforami
    zarządzania transakcjami
    optymalizatora zapytań

 

10.7 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?

6. Zaimplementuj metody realizacji operatorów relacyjnych w tym strategie tylko-indeks.

7. Zaimplementuj moduł realizacji zapytania (a więc parser, optymalizator, ewaluator) przy uproszczonych założeniach co do składni zapytania, np. co najwyżej dwie tabele.

8. Omów wybór indeksów na tabelach Emp i Dept z punktu widzenia wykonania zapytania. Opisz przypuszczalny plan wykonania zapytania wybrany przez optymalizator zapytań.

  1. SELECT E.Mgr, COUNT(*)
    FROM Emp E
    GROUP BY E.Mgr;
  2. SELECT E.Ename
    FROM Emp E INNER JOIN Dept D ON E.Deptno=D.Deptno
    WHERE  D.Dname='SALES'
    ORDER BY E.Empno;
  3. SELECT e.Dname, COUNT(*)
    FROM Emp E INNER JOIN Dept D ON E.Deptno=D.Deptno
    WHERE E.Job = 'SALESMAN'
    GROUP BY E.Deptno, E.Dname;
  4. SELECT E.Ename, D.Dname
    FROM Emp E INNER JOIN Dept D ON E.Deptno=D.Deptno
    WHERE E.Job = 'SALESMAN'
    ORDER BY E.Empno;
  5. SELECT E.Ename, E.job, D.Dname
    FROM Emp E INNER JOIN Dept D ON E.Deptno=D.Deptno
    ORDER BY E.Ename;

 

Strona przygotowana przez Lecha Banachowskiego - 06/17/07 .