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)
2
Plan wykładu
• Etapy przetwarzania zapytania
• Implementacja wyrażeń algebry relacji
• Reguły heurystyczne optymalizacji zapytań
• Kosztowa optymalizacja zapytań
• Język DML, DDL (cd)
3
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.
4
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
5
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.
6
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)
ℑ
7
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))
8
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
9
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
r
zależy od liczby bloków
pliku (b) oraz dostępnej przestrzeni bufora n
B
:
n
R
=ceil (b/n
B
).
– Faza scalania:
• posortowane jednostki są scalane w czasie jednego lub większej liczby
przebiegów. Stopień scalenia d
M
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
M
jest mniejszą spośród
wartości (n
B
-1) i n
R
; liczba przebiegów wynosi ceil(log
dM
(n
R
)).
• Liczba operacji dostępu do bloków:
(2*b)+(2*(b*log
dM
n
R
))
10
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
11
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 >; >=;<; <=.
12
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.
13
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
14
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.
15
Algorytmy operacji rzutowania
Π
<lista atrybutów>
(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
16
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)
17
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.
18
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.
19
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
20
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.
21
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
22
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
x
x
nazwa=‘wodnik’ and pracownik.id_pracownika=zlecenie.id_pracownika and
projekt.nr_projektu=zlecenie.nr_projektu and data_zatrudnienia>’1998-12-31’
Π
nazwisko
23
Przykład cd
pracownik
zlecenie
projekt
x
x
σ
nr_projektu=nr_projektu
Π
nazwisko
σ
data_zatrudniena>’1998-12-31’
σ
id_pracownika=id_pracownika
σ
nazwa=‘wodnik’
Przeniesienie operacji select w dół drzewa
24
Przykład cd
pracownik
zlecenie
projekt
x
x
σ
nr_projektu=nr_projektu
Π
nazwisko
σ
data_zatrudnienia>’1998-12-31’
σ
id_pracownika=id_pracownika
σ
nazwa=‘wodnik’
Zastosowanie bardziej restrykcyjnej operacji select jako pierwszej
25
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
26
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
27
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.
28
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
29
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)
30
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’;
31
Przykład
• Załóżmy, że mamy informacje o dodatkowych prowizjach dla
części pracowników. Są one umieszczone w tabeli
prowizje(id_pracownika, prowizja). Dokonać aktualizacji tabeli
Pracownik na podstawie informacji zawartej w tabeli prowizje.
•
UPDATE pracownik p
SET prowizja=(select c.prowizja+p.prowizja
from prowizje c
where c.id_pracownika = p.id_pracownika)
WHERE id_pracownika in (select id_pracownika from prowizje);
32
DELETE
• Polecenie DELETE służy do usuwania jednego lub wielu wierszy
z tabeli.
DELETE [FROM] tabela
[WHERE warunek];
• warunek WHERE określa, które wiersze należy usunąć
• jeżeli pominiemy klauzulę WHERE wszystkie wiersze zostaną
pominięte.