Wykład 12. Optymalizacja zapytań - część I.pdf - Kurs Bazy Danych - sliwak

Bazy danych

Optymalizacja zapytań

część I

Wykład przygotował:

Tadeusz Morzy

BD – wykład 12

Wykład jest poświęcony problemom wykonywania i optymalizacji zapytań w systemach

baz danych. Rozpoczniemy od krótkiego wprowadzenia do wykonywania zapytań.

Przedstawimy poszczególne fazy przetwarzania zapytań, takie jak analiza zapytań,

normalizacja zapytań, analiza semantyczna zapytań upraszczanie zapytań oraz

restrukturyzacja zapytań. Następnie, przejdziemy do omówienia problemów związanych z

optymalizacją zapytań. W kolejnej części wykładu, przedstawimy i omówimy algebraiczne

reguły transformacji zapytań. Na zakończenie wykładu powiemy o technice

przepisywania zapytań jako ważnym mechanizmie optymalizacji wykonywania zapytań.

Bazy danych

Fazy przetwarzania zapytania

zapytanie SQL

dekompozycja

zapytania

Katalog

systemowy

zapytania

wyrażenie algebry relacji

optymalizacja

zapytania

Statystyki

bazy danych

zapytania

plan wykonania zapytania

generacja

kodu

kod zapytania

wykonanie

zapytania

Baza danych

zapytania

Wynik zapytania

BD – wykład 12 (2)

Proces wykonywania zapytania składa się, najogólniej mówiąc, z kilku faz: fazy

dekompozycji, fazy optymalizacji zapytania, fazy generacji kodu, oraz fazy wykonania.

Zapytanie wyrażone w języku SQL, w fazie dekompozycji, jest transformowane do

postaci wyrażenia algebry relacji, umożliwiającej dalsze przetwarzania zapytania.

Transformacja zapytania do postaci wyrażenia algebraicznego wymaga dostępu do

katalogu bazy danych. W kolejnej fazie, wyrażenie reprezentujące zapytanie jest

optymalizowane za pomocą dwóch mechanizmów. Pierwszym jest mechanizm reguł

transformacji, który wykorzystując pewien zbiór reguł stara się uprościć zapytanie.

Drugim, jest mechanizm optymalizacji kosztowej, który, dla danego wyrażenia, stara się

określić optymalny plan wykonania zapytania (m.in. stara się określić optymalne drzewo

połączeń). Moduł optymalizatora wykorzystuje w procesie optymalizacji zapytania

statystyki, przechowywane w systemie bazy danych, dotyczące relacji, atrybutów i

indeksów (rozmiary relacji, liczba stron relacji, liczba różnych wartości atrybutu, itp.). W

kolejnym kroku, dla znalezionego planu wykonania zapytania, generowany jest kod

zapytania, który jest, następnie, uruchamiany przez tak zwany silnik zapytań (ang. query

engine).

dekompozycja

optymalizacja

generacja

wykonanie

Bazy danych

Dynamiczna vs statyczna

optymalizacja zapytań

Dynamiczna optymalizacja zapytań

Statyczna optymalizacja zapytań

Optymalizacja pojedynczego zapytania

Jednoczesna optymalizacja zbioru zapytań

BD – wykład 12 (3)

Zanim przejdziemy do przedstawienia i omówienia poszczególnych faz przetwarzania

zapytania, wprowadzimy i omówimy krótko klasyfikację metod optymalizacji zapytań.

Istnieje wiele klasyfikacji metod optymalizacji zapytań. Pierwsza z podanych klasyfikacji

wyróżnia optymalizację statyczną i optymalizację dynamiczną. Optymalizacja statyczna

polega na znalezieniu „najlepszego” planu wykonania zapytania, przed rozpoczęciem

wykonywania zapytania. W trakcie realizacji zapytania plan wykonania zapytania nie

ulega już zmianie – stąd nazwa optymalizacja statyczna. Optymalizacja dynamiczna

polega na znalezieniu „najlepszego” planu wykonania zapytania, przed rozpoczęciem

wykonywania zapytania, ale później, w trakcie wykonywania zapytania jego plan

wykonania może ulęgać zmianie. Aktualnie, komercyjne systemy baz danych zapewniają

jedynie optymalizację statyczna, choć efektywność takiej optymalizacji jest najczęściej

niższa aniżeli efektywność optymalizacji dynamicznej. Optymalizacja dynamiczna jest

jednak znacznie bardziej kosztowna.

Druga z podanych klasyfikacji wyróżnia optymalizację pojedynczego zapytania oraz

jednoczesną optymalizację wielu zapytań. W przypadku optymalizacji pojedynczego

zapytania, optymalizacji podlega tylko jedno zapytanie. W przypadku jednoczesnej

optymalizacji wielu zapytań, częściowe wyniki wykonania jednego zapytania mogą być

wykorzystane przez wiele innych zapytań, co prowadzi do minimalizacji czasu wykonania

zbioru zapytań. W chwili obecnej systemy komercyjnych baz danych zapewniają jedynie

optymalizację pojedynczego zapytania.

Dynamiczna optymalizacja zapyta

Statyczna optymalizacja zapyta

Jednoczesna optymalizacja zbioru zapyta

Bazy danych

Proces optymalizacji zapytań

• Transformacja zapytania SQL do postaci drzewa

wyrażenia logicznego:

– Identyfikacja bloków zapytania (odpowiadających

zagnieżdżonym zapytaniom lub perspektywom)

• Faza przepisywania zapytania:

– Zastosowania transformacji algebraicznych

BD – wykład 12 (4)

transformacji algebraicznych w celu uzyskania tańszego planu wykonania

zapytania. W konsekwencji uzyskujemy zbiór najlepszych planów wykonania

pojedynczych bloków zapytania. Pozostaje jeszcze problem połączenia bloków, w

szczególności, problem zdefiniowania porządku wykonywania operacji połączenia. Wybór

kolejności wykonywania operacji połączenia, tzn. wybór uszeregowania operacji

połączenia, kończy proces optymalizacji zapytania. Obecnie, przejdziemy do

przedstawienia poszczególnych faz przetwarzania zapytań.

transformacji algebraicznych w celu

uzyskania tańszego planu wykonania zapytania

• Optymalizacja bloku: zdefiniowania porządku

wykonywania operacji połączenia

•Zakończenie optymalizacji: wybór uszeregowania

Jak już wspomnieliśmy, pierwszą fazą przetwarzania zapytań jest faza transformacji

zapytania SQL do postaci drzewa wyrażenia logicznego: Celem tej fazy jest również

identyfikacja bloków zapytania (odpowiadających zagnieżdżonym zapytaniom lub

perspektywom). W kolejnym kroku realizowana jest faza przepisywania zapytania za

pomocą transformacji algebraicznych

Bazy danych

Dekompozycja zapytania

Dekompozycja zapytania: celem procesu dekompozycji

zapytania jest transformacja zapytania wyrażonego w

języku wysokiego poziomu na wyrażenie algebry relacji i

weryfikacja syntaktycznej i semantycznej poprawności

zapytania

• Etapy procesu dekompozycji zapytania:

– Analiza zapytań

– normalizacja zapytań

– analiza semantyczna zapytań

– upraszczanie zapytań

– restrukturyzacja zapytania

BD – wykład 12 (5)

Pierwszą fazą przetwarzania zapytania jest faza dekompozycji zapytania. Celem procesu

dekompozycji zapytania jest transformacja zapytania wyrażonego w języku wysokiego

poziomu na wyrażenie algebry relacji i weryfikacja syntaktycznej i semantycznej

poprawności zapytania. Proces dekompozycji składa się z następujących etapów:

–analiza zapytania,

–normalizacja zapytania,

–analiza semantyczna zapytania,

–upraszczanie zapytania,

–restrukturyzacja zapytania.

• Dekompozycja zapytania

Wykład 12. Optymalizacja zapytań - część I.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: