1 Optymalizacja zapytańProces przetwarzania i obliczania wyniku zapytania (wyrażenia algebry relacji) w SZBD

2 Elementy optymalizacjiAnaliza zapytania i przekształcenie go do „lepszej” postaci. Oszacowanie kosztu różnych opcji wykonania zapytania: informacje (statystyki) służące do szacowania kosztu; metody wykonania selekcji; metody złączeń; metody eliminacji duplikatów i sortowania Analizowanie i modyfikowanie planu wykonania zapytania.

3 Przekształcanie wyrażeń algebry relacjiSELECT K.prow FROM Student S, Ocena O, Kurs K WHERE S.indeks=O.indeks AND O.przed=K.przed AND O.ocena>=K.ocenaKwal AND S.nazwisko="Abacki”

4 Przekształcanie wyrażeń algebry relacjiS1 = πindeks(σnazwisko="Abacki”(S)) O1 = πindeks,ocena,przed(Ocena) K1 = πprow,ocenaKwal,przed(Kurs) SO = πocena,przed(S1 |><| O1) SOK = πprow(σocena>=ocenaKwal (SO |><| K))

5 Przekształcanie wyrażeń algebry relacjiWykonaj jak najwcześniej operacje selekcji (przemienność selekcji z innymi operacjami). Połącz iloczyn kartezjański z następującą po nim selekcją w złączenie (o ile to możliwe). Zastosuj łączność operacji złączenia tak, by wykonać złączenia w jak najbardziej ekonomicznej kolejności (algorytm dynamiczny wyznaczania optymalnej kolejności rozstawienia nawiasów). Wykonaj jak najwcześniej operacje rzutu. Wydziel wspólne podwyrażenia i obliczaj je tylko raz.

6 Statystyki i szacowanie kosztuStatystyki dla relacji R: nTuples(R) – liczba krotek relacji R, bFactor(R) – liczba krotek relacji mieszczących się w jednym bloku dyskowym, nBlocks(R) – liczba bloków, w których jest przechowywana relacja R. Statystyki dla atrybutu A relacji R: nDistinctA(R) – liczba różnych wartości A w R, minA(R), maxA(R) – minimalna i maksymalna wartość A w R, SCA(R) – selektywność A w R, czyli średnia liczba krotek spełniających warunek równości dla A. Statystyki dla indeksu I według atrybutu A: nLevelsA(I) - liczba poziomów I (jeśli jest drzewem), nLfBlocksA(I) - liczba bloków-liści w drzewie.

7 Statystyki i szacowanie kosztuPrzyjmuje się SCA(R) = { 1 iff A klucz; nTuples(R)/nDistinctA(R) wpp } Dla innych warunków także można określić selektywność: nTuples(R)* ((maxA(R)-c)/(maxA(R)-minA(R))) dla warunku A>c nTuples(R)* ((c-minA(R))/(maxA(R)-minA(R))) dla warunku A nTuples(R)*n/nDistinctA(R) dla warunku A in {c1,c2,...,cn} SCA(R)*SCB(R) dla warunku (A AND B) SCA(R)+SCB(R)- SCA(R)*SCB(R) dla warunku (A OR B) W przypadku gdy w systemie znajdują się histogramy dla wartości atrybutu, powyższe szacowania mogą być dokładniejsze

8 Sposoby wykonania selekcjiσw(A)(R), w(A) - warunek na A skanowanie całej relacji - nBlocks(R), wybranie wszystkich krotek relacji za pomocą indeksu (np. dla relacji pamiętanej w klastrze)- nTuples(R)+nLevelsA(I) wykorzystanie indeksu grupującego dla A - SCw(A)(R)/bFactor(R)+nLevelsA(I), wykorzystanie indeksu niegrupującego dla A - SCw(A)(R)+nLevelsA(I)

9 Wybór warunku do selekcjiσF1 AND ... AND Fn(R), F1,...,Fn - proste warunki Dla każdego Fi (1 <= i <= n) szacujemy koszt ci wykonania selekcji σFi. Wybieramy i, dla którego szacunkowy koszt był minimalny, i wybieramy (za pomocą indeksu lub bez) krotki spełniające warunek Fi, przy okazji sprawdzając, czy spełniają pozostałe warunki selekcji Fj (j<>i).

10 Wybór warunku do selekcji - przykładσA=2 AND B>950 AND C=5(R), dla R=ABCD R jest zapisana samodzielnie w nBlocks(R)=1000 blokach dyskowych, ma krotek, po 50 w jednym bloku; koszt skanowania = 1000; R ma indeks niegrupujący dla A i nDistinctA(R)=10; koszt wyszukania wg A = 50000/10 = 5000; R ma indeks grupujący dla B i nDistinctB(R)=1000, minB(R)=1, maxB(R)=1000; koszt wyszukania wg B = 50000*(50/1000)*(1/50) = 50; Dla C i D nie ma indeksów.

11 Obliczanie złączeń Szacunkowy rozmiar złączenia:R |><| S, dla R = AB i S = BC wynosi: nDistinctB(?)* (nTuples(R)/nDistinctB(R)*nTuples(S)/nDistinctB(S)) = = nTuples(R)*nTuples(S)/nDistinctB(R), przy założeniu, że rozkład wartości B w R i S jest jednostajny.

12 Zagnieżdżone pętle po blokachfor next M-2 blocks br1,br2,...,brM-2 in R do for each block bs in S do for i=1,..,M-1 return bri |><| bs; Szacunkowy koszt czytania: nBlocks(R) + (nBlocks(R)/(M-2))*nBlocks(S) zapisu wyniku (zawsze taki sam): nBlocks(R)*nBlocks(S)/nDistinctB(R)

13 Złączenia z wykorzystaniem indeksu:// 1. S ma indeks grupujący I wg. B for each t in R do search sx={s in S: s.B = t.B by I}; return sx |><| {t}; // nBlocks(R)+ nTuples(R)*(nLevelsB(S)+nBlocks(S)/nDistinctB(S)) // 2. S ma ind. grup.(I1), R ma ind. niegrup. I1, I2 wg. B for each value x in I1 do search sx = {s in S: s.B = x by I1}; search tx = {t in R: t.B = x by I2}; return sx |><| tx; // nDistinctB(S)*(nLevelsB(I1)+nBlocks(S)/nDistinctB(S)+ nLevelsB(I2)*nTuples(R)/nDistinctB(R))

14 Sort-Merge Join Sortowanie:Sort(R wg B) // 2*nBlocks(R)* (logM-1(nBlocks(R)/(M-1)+1) Sort(S wg B) // 2*Blocks(S)* (logM-1(nBlocks(S)/(M-1)+1) Merge(R,S wg B) // nBlocks(R)+nBlocks(S) Sortowanie: w pierwszym przebiegu sortujemy serie złożone z M-1 bloków; potem logM-1(nBlocks(R)/(M-1) razy scalamy po M-1 uporządkowanych serii najpierw długości M-1, potem (M-1)2, potem (M-1)3 itd.

15 Hash-join // h - funkcja haszująca dla B przyjmująca wartości 1,...,M-1 Hash(R wg h(B)) into R1,R2,...,RM-1// 2*nBlocks(R) Hash(S wg h(B)) into S1,S2,...,SM-1 // 2*nBlocks(S) // h' - funkcja haszująca dla B niezależna od h przyjmująca także wartości 1,...,M-1 for i=1,...,M-1 do Hash(Ri wg h'(B)) into A1,A2,...,AM-1// nBlocks(Ri)+M-1 Hash(Si wg h'(B)) into B1,B2,...,BM-1// nBlocks(Si) for j=1,...,M-1 return Aj |><| Bj; // M-1 // razem koszt: 3*(nBlocks(R)+nBlocks(S))+(2..4)*M

16 Sortowanie, grupowanie i eliminacja powtórzeńOperacje grupowania i eliminacji powtórzeń można wykonać poprzez sortowanie (M-1-krotny merge-sort, czyli multiway Merge-Sort) lub poprzez haszowanie połączone z sortowanie kubełków w pamięci.

17 Porównanie metod złączenia - przykładZ - zlecenie (zawiera id pracownika) nTuples(Z) = bFactor(Z) = 50 nBlocks(Z) = 2000 nDistinctid(Z) = 16 M = 100 P - pracownik (klucz: id) nTuples(P) = 6000 bFactor(P) = 30 nBlocks(P) = 200 nDistinctid(P) = 6000 ma indeks niegrupujący po id wys.3 Pętle po blokach (P zewnętrzna): 200+(200/98)*2000=4281 Pętle po blokach (Z - zewnętrzna): 2000+(2000/98)*200=6081 Pętla z indeksem niegrupującym: *3=8000 Sort-Join: 2*200*(log99(200/99)+1) + 2*2000*((log99(2000/99)+1)) 2*200*2+2*2000* =( )=11000 Hash-Join: 3*( )+3*100=6900

18 Statystyki w SZBD Statystyki tabel, atrybutów i indeksów są najczęściej aktualizowane: co pewien czas lub przy okazji operacji przeglądających relację (np. budowa indeksu) lub na wyraźne życzenie użytkownika (np. polecenia z pakietu DBMS_STATS w Oracle). Oprócz podanych wcześniej, system może budować histogramy wartości atrybutów pozwalające trafnie oceniać koszt operacji nawet przy niejednostajnym rozkładzie wartości.

19 EXPLAIN [ANALYZE] Plan wykonania EXPLAIN [ANALYZE] kolejność i metody wykonywania złączeń (NESTED LOOPS, HASH-JOIN, SORT-JOIN, INDEX NESTED LOOPS), warunek selekcji i ewentualnie użyty dla niego indeks (np. INDEX SCAN USING ON lub FULL SCAN) końcowe sortowanie, grupowanie lub haszowanie w celu uporządkowania lub pogrupowania wyniku. szacunkowy czas wykonania poszczególnych operacji (jeżeli użyto ANALYZE, to zapytanie jest wykonywane) szacunkowy rozmiar wyniku operacji

20 Wskazówki (hints) Specjalne komentarze zamieszczane przy zapytaniu wskazujące, jakiej metody obliczania ma użyć system. W komentarzu tym można zapisać: jakiego optymalizatora ma użyć system (np. w Oracle można wybrać oparty na kosztach lub rankingu operacji), jakiego indeksu użyć przy obliczaniu selekcji, w jakiej kolejności wykonać złączenia, jakiego algorytmu złączenia użyć. Np. SELECT /*+ INDEX(wgMiasta)*/ nazwisko FROM Student WHERE miasto="Chełm"