BD_W12

Bazy danych

Małgorzata Krętowska

Katedra Oprogramowania

e-mail: m.kretowska@pb.edu.pl

Wykład 12: Optymalizacja zapytań.

Język DDL, DML (cd)

Plan wykładu

• Etapy przetwarzania zapytania

• Implementacja wyrażeń algebry relacji

• Reguły heurystyczne optymalizacji zapytań

• Kosztowa optymalizacja zapytań

• Język DML, DDL (cd)

Przetwarzanie zapytań

Zapytanie wyrażone w wysokopoziomowym języku zapytań, takim jak

SQL, musi najpierw zostać odczytane, poddane analizie składniowej i
zweryfikowane.

•

Czytnik (ang. Scanner) - identyfikuje elementy języka (słowa kluczowe
SQL, nazwy atrybutów, nazwy relacji ) w tekście zapytania

•

Analizator składniowy (ang. Parser) - sprawdza składnię zapytania w
celu określenia czy sformułowano je zgodnie z regułami gramatyki
języka zapytań.

•

Drzewo zapytania - wewnętrzna reprezentacja zapytania, w postaci
drzewiastej struktury

•

Strategia wykonania zapytania - określana jest przez SZBD i określa
strategię pobrania wyników zapytania z plików bazy danych. Proces
wyboru najlepszej strategii określa się mianem optymalizacji zapytania.

Etapy przetwarzania zapytania

Zapytanie w języku wysokiego poziomu

Zapytanie w postaci pośredniej

Plan wykonania

Kod wykonania zapytania

Wynik zapytania

ODCZYT, ANALIZA
SKŁADNIOWA
I WERYFIKACJA

OPTYMALIZATOR ZAPYTAŃ

GENERATOR KODU ZAPYTAŃ

WYKONAWCZY PROCESOR
BAZY DANYCH

Strategie optymalizacji zapytań

• Reguły heurystyczne - sprawdzają się z większości sytuacji, ale

nie gwarantują poprawnego działania w każdym przypadku

• Reguły z systematycznym szacowaniem - szacowany jest koszt

różnych strategii wykonania zapytania. Wybierany jest plan o
najniższym szacowanym koszcie.

Translacja zapytań języka SQL do

postaci wyrażeń algebry relacji

•

Zapytanie języka SQL jest tłumaczone na równoważne mu wyrażenie
algebry relacji - reprezentowane jako struktura danych drzewa
zapytania - które podlega optymalizacji.

•

Zapytania SQL są rozkładane na bloki zapytania, które stanowią
podstawową jednostkę, jaka może być tłumaczona na operatory
algebraiczne i optymalizowana

•

Blok zapytania stanowi pojedyncze wyrażenie SELECT- FROM-
WHERE, jak również

klauzule GROUP BY I HAVING.

•

Wyrażenia algebry relacji:

- operacje teoriomnogościowe (suma, przecięcie, różnica, iloczyn kartezjański)

– rzutowanie (projekcja)

– selekcja

– złączenie

⇔

– agregacja (zastosowanie funkcji agregujących)

ℑ

Przykład

Select nazwisko, id_pracownika

from pracownik

where pensja >

(select max(pensja)

from pracownik

where nr_departamentu=5)

• Blok wewnętrzny ma postać:

select max(pensja) from pracownik where nr_departamentu=5

•

Zapis w postaci wyrażenia algebry relacji:

ℑ

max pensja

(σ

nr_departamentu=5

(pracownik))

• Blok zewnętrzny ma postać:

Select nazwisko, id_pracownika from pracownik where pensja > C

•

Zapis w postaci wyrażenia algebry relacji:

nazwisko, id_pracownika

(σ

pensja>C

(pracownik))

Algorytmy sortowania zewnętrznego

• Jedne z najważniejszych algorytmów używanych w czasie

przetwarzania zapytań, wykorzystywany wówczas gdy zapytanie
zawiera

– klauzulę order by
– opcję distinct w klauzuli select
– przy złączaniu tabel

• sortowanie można uniknąć, jeżeli istnieje odpowiedni indeks,

umożliwiający uzyskanie uporządkowanego dostępu do
rekordów

• Sortowanie zewnętrzne odnosi się do algorytmów sortowania

odpowiednich dla dużych plików rekordów składowanych na
dysku, które nie mieszczą się w pamięci głównej

Algorytmy sortowania zewnętrznego

•

Typowy algorytm sortowania zewnętrznego wykorzystuje strategię sortująco-
scalającą:

– Faza sortowania:

• jednostki pliku, które mieszczą się w dostępnej przestrzeni bufora, są

wczytywane do pamięci, sortowane przy użyciu algorytmu sortowania
wewnętrznego i zapisywane z powrotem na dysku jako tymczasowe
posortowane podpliki. Liczba jednostek początkowych n

zależy od liczby bloków

pliku (b) oraz dostępnej przestrzeni bufora n

=ceil (b/n

– Faza scalania:

• posortowane jednostki są scalane w czasie jednego lub większej liczby

przebiegów. Stopień scalenia d

jest liczbą jednostek, które można scalić w

każdym przebiegu.

• W każdym przebiegu potrzebny jest jest jeden blok bufora w celu

przechowywania jednego bloku z każdej ze scalanych jednostek i jeden blok do
przechowywania każdego bloku wyniku scalenia. d

jest mniejszą spośród

wartości (n

-1) i n

; liczba przebiegów wynosi ceil(log

)).

• Liczba operacji dostępu do bloków:

(2*b)+(2*(b*log

))

Implementacja operacji SELECT

• Metody wyszukiwania w przypadku prostych operacji wybierania

nr_departamentu=5

(pracownik) ; σ

id_pracownika>3

(pracownik)

•

algorytmy te można podzielić na tzw. przeglądy plików (przeglądają rekordy w
pliku w celu wyszukania i pobrania odpowiednich rekordów) oraz przeglądy
indeksu (wyszukiwania uwzględniające użycie indeksu).

– wyszukiwanie liniowe- pobieramy każdy rekord z pliku i sprawdzamy, czy

wartość jego atrybutu spełnia warunek wyboru

– wyszukiwanie binarne -

• warunek wyboru zawiera porównanie równowartościowe na atrybucie

klucza, względem którego uporządkowany jest plik

– użycie indeksu głównego (lub klucza haszującego)

• jeżeli warunek zawiera porównanie równowartościowe na atrybucie

klucza z indeksem głównym

• warunek ten powoduje wybranie najwyżej jednego rekordu

Implementacja operacji SELECT

– użycie indeksu głównego w celu pobrania wielu rekordów

• warunek porównania jest >,>=,< lub <= na polu klucza z indeksem

głównym

• używamy indeksu w celu znalezienia rekord spełniającego odpowiedni

warunek, a następnie pobieramy wszystkie kolejne rekordy z
uporządkowanego pliku

– użycie indeksu drugorzędnego (B

-drzewa) na porównaniu równościowym -

metoda może być użyta w celu pobrania pojedynczego rekordu, jeżeli pole
indeksujące jest kluczem lub w celu pobrania wielu rekordów, jeżeli pole
indeksujące nie jest kluczem. Można jej używać w przypadku porównań
uwzględniających relacje >; >=;<; <=.

Implementacja operacji SELECT

Metody wyszukiwania w przypadku złożonych operacji wyboru

nr_departamentu=5 and nazwisko=‘C%’

(pracownik)

– Wybór koniunktywny przy użyciu pojedynczego indeksu - jeżeli atrybut związany z

dowolnym pojedynczym warunkiem prostym jest kluczem,możemy użyć jednej z
metod dla prostych operacji wybierania, a następnie sprawdzamy, czy każdy pobrany
rekord spełnia pozostałe warunki proste.

– Wybór koniunktywny przy użyciu indeksu złożonego - jeżeli warunki równości dotyczą

dwóch lub więcej atrybutów i na połączonych polach istnieje indeks złożony możemy
bezpośrednio użyć takiego indeksu

– Wybór koniunktywny poprzez przecięcie zbiorów wskaźników na rekordy

• jeżeli na więcej niż jednym polu związanym z warunkami prostymi istnieją

indeksy drugorzędne oraz jeżeli indeksy zawierają wskaźniki na rekordy
wówczas każdy indeks może zostać użyty w celu pobrania zbioru wskaźników
rekordów, które spełniają pojedyncze warunki. Przecięcie tych zbiorów daje w
wyniku wskaźniki rekordów spełniające warunek koniunktywny. Jeżeli tylko
niektóre warunki posiadają odpowiednie indeksy, wówczas każdy pobrany rekord
jest dodatkowo sprawdzany w celu określenia czy spełnia pozostałe warunki.

Implementacja operacji SELECT

nr_departamentu=5 or nazwisko=‘C%’

(pracownik)

• alternatywy logiczne stanowią sumę teoriomnogościową

rekordów spełniających poszczególne warunki stąd niewielkie
pole manewru w zakresie optymalizacji

• jeżeli któryś z warunków nie posiada indeksu należy wykorzystać

wyszukiwanie liniowe

• tylko wówczas gdy indeks istnieje na każdym warunku można

zoptymalizować wybór, pobierając rekordy spełniające każdy z
warunków a następnie zastosować operację sumy
teoriomnogościowej w celu wyeliminowania duplikatów

Implementacja operacji NATURAL JOIN

R ⇔

A=B

S np. pracownik ⇔

nr_departamentu=nr_departamentu

departament

•

Złączenie pętli zagnieżdżonych - dla każdego rekordu t w pliku R (pętla
zewnętrzna) pobieramy każdy rekord s z pliku S (pętla wewnętrzna) i
sprawdzamy, czy oba rekordy spełniają warunek złączenia

•

Złączenie z pętlą pojedynczą - jeżeli na jednym z atrybutów podlegających
złączeniu - np. B w pliku S - istnieje indeks pobieramy każdy rekord t z pliku R,
po jednym naraz, a następnie używamy struktury dostępowej w celu
bezpośredniego pobrania wszystkich pasujących rekordów s z pliku S,
spełniających warunek złączenia.

•

Złączenie sortująco - scalające

– jeżeli rekordy plików R i S są uporządkowane według wartości atrybutów

złączenia -> implementacja złączenia najwydajniejsza; oba pliki są
przeglądane w kolejności atrybutów złączenia i dopasowujemy rekordy
mające odpowiednio takie same wartości atrybutów złączenia

– jeżeli rekordy nie są posortowane można tego dokonać przy użyciu

sortowania zewnętrznego.

Algorytmy operacji rzutowania

(R)

• Prosty do implementacji, jeżeli lista atrybutów zawiera klucz

relacji R -> wynik operacji ma tę samą liczbę krotek co relacji R,
ale zawiera w każdej krotce tylko wartości atrybutów należących
do listy.

• Jeżeli lista atrybutów nie zawiera klucza relacji R, należy

wyeliminować duplikaty -> dokonuje się tego zwykle przez
posortowanie wyniku operacji, a następnie usunięcie duplikatów
krotek, które występują teraz obok siebie

Algorytmy operacji teoriomnogościowych

• iloczyn kartezjański - operacja kosztowna, stąd istotną rzeczą

jest jej unikanie poprzez zastępowanie jest równoważnymi
operacjami w czasie optymalizacji

• suma, przecięcie, różnica

– technika sortująco-mieszająca - dwie relacje zostają posortowane

względem tych samych atrybutów i jednokrotne przejrzenie każdej z
nich wystarczy do utworzenia wyniku (np. przecięcie - zachowanie
w pliku scalonym tylko tych krotek, które występują w obu relacjach)

Implementacja operacji agregujących

•

Select max(pensja) from pracownik

– jeżeli na atrybucie pensja relacji pracownik istnieje indeks (rosnący),

optymalizator może zdecydować o jego użyciu w celu uzyskania największej
wartości. Największa wartość będzie to ostatni wpis indeksu.

•

Count, avg, sum

– można użyć indeksu, jeżeli jest to indeks zagęszczony tzn występuje w nim

wpis dla każdego rekordu z pliku głównego. Indeksu niezagęszczonego
można użyć tylko dla operacji count distinct. Wówczas odpowiedni
obliczenia wykorzystują tylko wartości w indeksie.

•

Klauzula GROUP BY

– operator agregujący musi być zastosowany oddzielnie dla każdej grupy

krotek

– najpierw tabela musi być podzielona na podgrupy względem atrybutu

grupującego

– często stosowane jest najpierw albo sortowanie albo haszowanie na

atrybutach grupujących.

Implementacja złączenia zewnętrznego

Select id_pracownika, nazwisko, nazwa

from pracownik left join departament on nr_departamentu;

• złączenie zewnętrzne można określić modyfikując jeden z

algorytmów złączeniowych, takich jak złączenie pętli
zagnieżdżonych lub złączenie z pętlą pojedynczą:

– w przypadku operacji left join relacja występująca po lewej stronie

musi się znaleźć w pętli zewnętrznej (lub pojedynczej), ponieważ
każda krotka z tej relacji musi się znaleźć w wyniku

– jeżeli w relacji po prawej stronie nie ma odpowiednich krotek to

wartości uzupełnia się wartościami null.

Implementacja złączenia zewnętrznego

Rozwiązanie alternatywne polega na wykonaniu kombinacji algebry relacji:

1. Określamy złączenie wewnętrzne tabel pracownik i departament

temp1 ← Π

id_pracownika, nazwisko, nazwa

(pracownik⇔

nr_departamentu=nr_departamentu

departament)

2. Znajdujemy w tabeli pracownik krotki, które nie występują w

wyniku złączenia wewnętrznego

temp2 ← Π

id_pracownika, nazwisko

(pracownik)− Π

id_pracownika, nazwisko

(temp1)

3. Uzupełniamy każdą krotkę polem nazwa o wartości null

temp2 ← temp2×’NULL’

4. Wykonujemy operację sumy na temp1 i temp2

wynik←temp1∪temp2

Mechanizm potokowy

• Zapytanie w języku SQL jest przekształcane na wyrażenia

algebry relacji, które jest sekwencją operacji relacyjnych

• wykonywanie po jednej operacji generuje pliki tymczasowe na

dysku, co jest czasochłonne i może być niepotrzebne, ponieważ
pliki te są natychmiast wykorzystywane jako dane wejściowe do
kolejnej operacji

• w celu zredukowania liczby plików tymczasowych często

generuje się kod zapytania, który odpowiada algorytmom
łączenia operacji w zapytaniu.

• Jest to tzw. przetwarzanie potokowe.

Reguły heurystyczne optymalizacji

zapytań

• Heurystyczna technika optymalizacji wykorzystuje reguły

heurystyczne w celu modyfikowania wewnętrznej reprezentacji
zapytania (drzewa zapytania) w celu zwiększenia oczekiwanej
wydajności działania

• Analizator składniowy najpierw generuje początkową

reprezentację wewnętrzną, która jest optymalizowana zgodnie z
regułami heurystycznymi (np. stosowanie operacji selekcji i
projekcji przed operacją złączenia)

• Otrzymujemy końcowe drzewo zapytania a następnie generuje

się plan wykonania zapytania w celu wykonania grup operacji

Przykład

Select nazwisko from pracownik, projekt, zlecenie

where nazwa=‘wodnik’ and pracownik.id_pracownika=zlecenie.id_pracownika and

projekt.nr_projektu=zlecenie.nr_projektu and data_zatrudnienia>’1998-12-31’;

Początkowe drzewo zapytań:

pracownik

zlecenie

projekt

nazwa=‘wodnik’ and pracownik.id_pracownika=zlecenie.id_pracownika and

projekt.nr_projektu=zlecenie.nr_projektu and data_zatrudnienia>’1998-12-31’

nazwisko

Przykład cd

pracownik

zlecenie

projekt

nr_projektu=nr_projektu

nazwisko

data_zatrudniena>’1998-12-31’

id_pracownika=id_pracownika

nazwa=‘wodnik’

Przeniesienie operacji select w dół drzewa

Przykład cd

pracownik

zlecenie

projekt

nr_projektu=nr_projektu

nazwisko

data_zatrudnienia>’1998-12-31’

id_pracownika=id_pracownika

nazwa=‘wodnik’

Zastosowanie bardziej restrykcyjnej operacji select jako pierwszej

Przykład cd

pracownik

zlecenie

projekt

⇔

nr_projektu=nr_projektu

nazwisko

data_zatrudnienia>’1998-12-31’

⇔

id_pracownika=id_pracownika

nazwa=‘wodnik’

Zastąpienie iloczynu kartezjańskiego i select operacją join

Przykład cd

Redukcja liczby atrybutów

pracownik

projekt

⇔

nr_projektu=nr_projektu

nazwisko

data_zatrudnienia>’1998-12-31’

⇔

id_pracownika=id_pracownika

nazwa=‘wodnik’

zlecenie

id_pracownika

nr_projektu, id_pracownika

id_pracownika, nazwisko

nr_projekru

Wykorzystanie oszacowań kosztu w

optymalizacji zapytań

• Optymalizator zapytań nie powinien polegać wyłącznie na

regułach heurystycznych, ale również uwzględniać oszacowania
i porównywać koszty wykonania zapytania przy użyciu różnych
strategii wykonania, wybierając strategię o najniższym
oszacowanym koszcie.

• Takie podejście określa się mianem kosztowej optymalizacji

zapytań i wykorzystuje ono tradycyjne techniki optymalizacji
przeszukujące przestrzeń rozwiązania problemu w celu
znalezienia rozwiązania, które będzie minimalizować funkcję
kosztu.

Składowe kosztu wykonania zapytań

•

Składowe kosztu wykonania zapytań:

– koszt dostępu do drugorzędnych mechanizmów składowania danych

• koszt wyszukania, odczytania i zapisania bloków danych

przechowywanych na dysku

• koszt zależy od struktur dostępu utworzonych dla danego pliku:

uporządkowanie, haszowanie, indeksy

– koszt składowania - koszt przechowywania wszelkich plików pośrednich

generowanych w ramach strategii wykonania zapytania

– Koszt obliczeniowy - koszt dokonywania obliczeń w pamięci na buforach

danych w czasie wykonywania zapytania np. wyszukiwanie, sortowanie,
scalanie rekordów, obliczenia na wartościach pól

– koszt zużycia pamięci - koszt zależny od liczby buforów pamięci

potrzebnych w czasie wykonywania zapytania

– koszt komunikacji - koszt zawiązany z przesłaniem zapytania i jego wyników

z bazy danych do węzła lub terminalu, z którego zostało przesłane żądanie

Wstawianie wierszy

•

Polecenie wstawiania nowych wierszy do tabeli:

INSERT INTO nazwa_tabeli [(lista_kolumn)]

VALUES (lista_wartości);)

•

Wstawianie wierszy wybieranych w zapytaniu:

INSERT INTO nazwa_tabeli [(lista_kolumn)]

SELECT lista_wyrażeń FROM....;

•

Parametryzowane polecenie INSERT

INSERT INTO nazwa_tabeli [(lista_kolumn)]

VALUES(&wartość1, &wartość2,...)

Przykład:

INSERT INTO dept (deptno, dname, loc)

VALUES (&d_numer, &d_nazwa, &d_miasto)

UPDATE

• Polecenie UPDATE służy do zmiany wartości w istniejących

wierszach:

UPDATE tabela [alias]
SET kolumna= {wyrażenie | podzapytanie }
[, kolumna= {wyrażenie | podzapytanie }]...
[WHERE warunek]

Przykład:
Zmienić dane w wierszu pracownika Nazwisko2:

UPDATE pracownik

SET job=‘SPRZEDAWCA’, data_zatrudnienia=TRUNC(SYSDATE),

pensja=pensja*1.1

WHERE nazwisko=‘Nazwisko2’;