Optymalizacja zapytan w SBQL 2004

Optymalizacja zapytań w SBQL: 

Optymalizacja zapytań w SBQL Kazimierz Subieta Polsko-Japońska Wyższa Szkoła Technik Komputerowych, Warszawa subieta@pjwstk.edu.pl Instytut Podstaw Informatyki PAN, Warszawa subieta@ipipan.waw.pl

Plan seminarium: 

Plan seminarium Wprowadzenie do problemu optymalizacji zapytań Metoda niezależnych pod-zapytań ..... Miało być o indeksach, ale nie zmieściło się....

Wprowadzenie do problemu optymalizacji zapytań: 

Wprowadzenie do problemu optymalizacji zapytań

Co to jest optymalizacja zapytań?: 

Co to jest optymalizacja zapytań? Radykalne skrócenie czasu wykonania zapytań, przerzucone w całości na maszynę - głównie na specjalny moduł oprogramowania zwany optymalizatorem zapytań. Ręczna optymalizacja przez programistę jest nieefektywna i prowadzi do skomplikowania programów oraz obniżenia ich pielęgnacyjności. Optymalizator zapytań, korzystający z gotowych algorytmów i dysponujący aktualną wiedzą dotyczącą stanu środowiska bazy danych, jest w stanie działać w sposób znacznie bardziej uniwersalny i skuteczny niż programista, nie zakłócając przy tym możliwości w zakresie pielęgnacyjności oprogramowania.

Historia optymalizacji zapytań: 

Historia optymalizacji zapytań Literatura dotycząca optymalizacji relacyjnych języków zapytań jest bardzo obszerna; tysiące artykułów. Często bardzo technicznych, przywiązanych do konkretnych systemów i detali fizycznych organizacji danych. Część metod proponowanych dla modelu relacyjnego została zaadoptowana dla obiektowych języków zapytań. Pojawiły się także nowe metody, takie jak pointer swizzling, specyficzne wyłącznie dla modeli obiektowych. Ograniczymy się do metod, które mogą być bezpośrednio wykorzystane w ramach SBA. Niektóre z nich, takie jak metoda niezależnych pod-zapytań, są wynalezione w związku z SBA i nie były rozpatrywane w innych kontekstach.

Kryteria optymalizacji: 

Kryteria optymalizacji Podstawowym kryterium optymalizacji zapytań jest łączny czas ich ewaluacji: czas samej optymalizacji, czas ewaluacji po optymalizacji. Zmniejszenie liczby transferów dyskowych. Inne kryteria, takie jak zużycie zasobów (dysku, pamięci operacyjnej, czasu procesora, sieci) są istotne, ale tylko w specyficznych sytuacjach, które występują rzadziej. Zasoby komputerowe są tanie i można je kupić Czas użytkownika może być bardzo cenny.

Optymalizacja czy usatysfakcjonowanie?: 

Optymalizacja czy usatysfakcjonowanie? Środowisko komputerowe, różnorodny charakter przetwarzanych struktur danych, konstrukcje językowe, itd. powodują, że istnieje ogromna ilość miejsc, w których można poszukiwać efektu skrócenia czasu ewaluacji zapytań. Optymalizacja zapytań nie nawiązuje do klasycznych zadań optymalizacyjnych, w których poszukuje się ekstremum pewnej funkcji kryterialnej. Jest poszukiwaniem rozwiązania, przy którym czas odpowiedzi na zapytanie niekoniecznie jest optymalny, lecz powinien być satysfakcjonujący dla użytkowników. Kryterium satysfakcji użytkowników jest oczywiście nieformalne, subiektywne i relatywne. Brak satysfakcji użytkownika  język zapytań nie ma sensu.

Gdzie szukać zysków w czasie?: 

Gdzie szukać zysków w czasie? Rozwiązania w zakresie optymalizacji zapytań mogą dotyczyć nie tylko samego języka zapytań, ale również: organizacji struktur danych (fizycznej lub logicznej), metod transmisji danych pomiędzy różnymi ich nośnikami, metod opartych na zapamiętywaniu rezultatów poprzednich zapytań (celem ich ponownego użycia), metod opartych na zrównolegleniu wykonania operacji, ..... Z tego względu optymalizacja zapytań jest w dużym stopniu zależna od środowiska bazy danych, środowiska implementacyjnego i konkretnych pomysłów. Optymalizacja ta jest bardziej „dostrajaniem” (tuning) przy użyciu dowolnych inżynierskich zabiegów.

Plan ewaluacji zapytania: 

Plan ewaluacji zapytania Możliwe jest wiele planów ewaluacji Wybór jednego z nich należy do optymalizatora Plan jest wykonywany przez interpreter zapytań Dowolny plan ewaluacji nie może doprowadzić z zmiany semantyki (rezultatu) zapytania, przy dowolnym stanie bazy danych i dowolnych stanach środowiska komputerowego Ten punkt podważa wiele metod inżynierskich. Wymaga opracowania mocnej teorii języków zapytań (mocnej i prawdziwej, bez luk koncepcyjnych) „Halloween problem” – nałożenie na siebie kilku metod optymalizacyjnych powoduje błędny wynik. Jest to skutek chaotycznego piętrzenia pomysłów optymalizacyjnych.

Rozwiązania dominujące: 

Rozwiązania dominujące Są to metody generowania nowego planu ewaluacji na podstawie poprzedniego planu, które nigdy nie doprowadzą do pogorszenia czasu. Dla wielu zastosowań wystarczają metody quasi-dominujące, czyli takie, gdzie pogorszenie czasu następuje tylko w skrajnych sytuacjach (np. dla bazy danych zawierającej mniej niż 100 obiektów) Metody oparte na przepisywaniu należą do rozwiązań quasi-dominujących. Jeżeli metoda nie jest (quasi-) dominująca, to trzeba w jakiś sposób ustalić, czy warto ją stosować.

Modele kosztów: 

Modele kosztów Zadaniem modelu kosztów oszacowanie czasu/kosztu ewaluacji wg danego planu. Model kosztów może wprowadzać ogromną liczbę czynników wpływających na czas ewaluacji. Budowanie modelu kosztów dla celów optymalizacji zapytań posiada zasadnicze wady: Skomplikowane środowisko powoduje trudności w uchwyceniu spraw ważnych i w pominięciu drugorzędnych. Prawo GIGO (Garbage In – Garbage Out): twórca modelu kosztów musi przyjąć pewne wzory lub dane „z sufitu” (np. wskaźnik selektywności predykatu), co może poważnie zniekształcić wynik. Modele kosztów są głównie wytwarzane przez akademię. W praktyce stosuje się raczej proste heurystyki.

3 popularne grupy metod optymalizacyjnych: 

3 popularne grupy metod optymalizacyjnych Metody ustalające fizyczne zasady przechowywania, buforowania i udostępniania danych. Np. hash coding jest często znacznie bardziej sprawny niż sekwencyjne ułożenie obiektów w pliku. Metody oparte na przepisywaniu, w których dokonuje się transformacji wewnętrznej reprezentacji zapytania na inną postać, rokującą lepszy czas wykonania. Metody oparte na pomocniczych, redundantnych strukturach danych zwanych zwykle indeksami. Istnieje wiele form indeksów, i w ślad za tym, różnych form optymalizacji zapytań bazujących na indeksach. Relacje wspomagające dostęp (access support relations), Zapamiętane zapytania (cached queries), Zmaterializowane perspektywy (materialized views).

Metody organizacji i udostępniania danych : 

Metody organizacji i udostępniania danych Kluczowa rola dla szybkości ewaluacji zapytań. Istotne są takie czynniki jak: Konstrukcja identyfikatora obiektu Alokacja obiektów i rejestrowanie nieużytków Fizyczna organizacja wnętrza obiektów Organizacja kolekcji obiektów Organizacja powiązań między obiektami Zarządzanie nazwami danych Organizacja wspierająca funkcję nested oraz funkcję wiązania na stosie środowiskowym (np. leniwe wiązanie, agregaty binderów) Metody te nie będą tu omawiane (można poczytać w książce).

Architektura środowiska ewaluacji zapytań: 

Architektura środowiska ewaluacji zapytań Parser zapytań/programów Środowisko rozwoju oprogramowania (edytor, kompilator, itd.) Klient Drzewo syntaktyczne zapytania/programu Optymalizacja poprzez przepisywanie Optymalizacja poprzez indeksy Interpreter zapytań/programów Lokalny skład danych Stos środowiskowy Stos rezultatów Statyczny stos środowiskowy Statyczny stos rezultatów Baza danych: metabaza, trwałe obiekty, abstrakcje, indeksy,... Zarządzanie obiektami Przetwarzanie trwałych abstrakcji bazujących na zapytaniach Rejestr indeksów Serwer

Metoda niezależnych podzapytań : 

Metoda niezależnych podzapytań

Przesuwanie selekcji przed złączenie i generalizacja tej metody: 

Przesuwanie selekcji przed złączenie i generalizacja tej metody Jedną z podstawowych metod optymalizacji relacyjnych zapytań jest tzw. przesuwanie selekcji przed złączenie. Redukuje wielkość złączanych relacji, przez co zapytanie jest wykonywane szybciej. Metodę tę dość często wiąże się z algebrą relacji, która pozwala na odpowiednie formalne przekształcenia. Ten związek jest jednak powierzchowny, metoda ta może być wyjaśniona na innym gruncie. Bardzo ogólne podstawy tej metody można wyrazić (jak dotąd) wyłącznie w SBA. Zostały odkryte w 1984 r. Istotą metody jest unikanie wielokrotnego liczenia tego samego podzapytania. Takie wielokrotne liczenie jest implikowane przez semantykę operatorów niealgebraicznych.

Przykład schematu bazy danych: 

Przykład schematu bazy danych

Motywujące przykłady: 

Motywujące przykłady Zapytanie zaznaczone na szaro będzie ewaluowane tyle razy, ilu jest pracowników, a wystarczyłoby je ewaluować tylko raz. Prac where Zar = ((Prac where Nazwisko = ”Nowak”).Zar) Prac where Zar = ((Dział where Nazwa = Nazwisko).( Budżet/1000)) Tym razem zapytanie zaznaczone na szaro musi być ewaluowane tyle razy, ilu jest pracowników – nie da się ewaluować go tylko raz. Jak odróżnić pierwszy i drugi przypadek?

Bardzo prosta obserwacja: 

Bardzo prosta obserwacja Podzapytanie jest niezależne od swojego najbliższego lewego operatora niealgebraicznego, jeżeli nie występuje w nim nazwa, która jest wiązana w sekcji (sekcjach) stosu otwieranej przez ten operator. Takie zapytanie można „wyłączyć przed nawias”. Dla każdego operatora niealgebraicznego przypisaliśmy numer sekcji (poczynając od dołu stosu), którą otwiera. Dla każdej nazwy przypisaliśmy dwie liczby: rozmiar stosu w momencie wiązania, oraz numer sekcji, w której dana nazwa zostanie związana. Widać wyraźnie, że zaznaczone podzapytanie nie ma nazwy wiązanej w sekcji otwieranej przez pierwszy operator where; dlatego jest niezależne. Prac where Zar = ((Prac where Nazwisko = ”Nowak”) . Zar) (1,1) 2 (2,2) (2,1) 3 (3,3) 3 (3,3)

Przepisanie zapytania zawierającego niezależne podzapytanie: 

Przepisanie zapytania zawierającego niezależne podzapytanie

Generalizacja: 

Generalizacja Widać wyraźnie, że w naszej metodzie może przesuwać nie tylko selekcję przed złączenie, ale „wszystko przed wszystko”: selekcję przed kwantyfikator selekcję przed selekcję kropkę przed złączenie ... Ważne jest tylko to, aby uniknąć wielokrotnego liczenia tego samego podzapytania. Nasza obserwacja to umożliwia. Ale co należy zrobić, aby ta obserwacja stała się metodą?

Architektura optymalizacji przez przepisywanie: 

Architektura optymalizacji przez przepisywanie Celem jest wyznaczenie numerów przypisanych do operatorów i nazw w zapytaniu. Statyczne stosy oraz metabaza dokładnie symulują (w czasie analizy zapytania) operacje na rzeczywistych stosach i składzie danych.

Drzewo syntaktyczne zapytania: 

Drzewo syntaktyczne zapytania Start Lewe podzapytanie Prawe podzapytanie Operator deref 2,2 Operator niealg where Lewe podzapytanie Prawe podzapytanie Nazwa Zar Operator = Nazwa Prac 1,1 2,2 Operator deref Operator koercji bag  1 Operator niealg . 3,3 Prawe podzapytanie Lewe podzapytanie Prawe podzapytanie Lewe podzapytanie Literał ”Nowak” Operator deref Nazwa Nazwisko 3.3 Prawe podzapytanie Lewe podzapytanie Operator = Nazwa Prac 2,1 Nazwa Zar 3.3 Operator niealg where 3.3 Prac where Zar = ((Prac where Nazwisko = ”Nowak”).Zar) Odwzorowuje składnię abstrakcyjną. Dostawia ukryte operatory. Ma dodatkowe pola umożliwiające zapis różnych informacji. Umożliwia łatwe manipulowanie jego fragmentami (przesuwanie, usuwanie, dostawianie).

Drzewo po modyfikacji: 

Drzewo po modyfikacji (((Prac where Nazwisko = ”Nowak”) . Zar) group as z) . (Prac where Zar = z) Operator deref Operator koercji bag  1 Operator niealg . info Prawe podzapytanie Lewe podzapytanie Prawe podzapytanie Lewe podzapytanie Literał ”Nowak” Operator deref Nazwa Nazwisko info Prawe podzapytanie Lewe podzapytanie Operator = Nazwa Prac info Nazwa Zar info Operator niealg where info Start Lewe podzapytanie Prawe podzapytanie Operator deref info Operator niealg where Lewe podzapytanie Prawe podzapytanie Nazwa Zar info Operator = Nazwa Prac info info Operator niealg . Lewe podzapytanie Prawe podzapytanie Nazwa z info Operator group as z

Metabaza – graf schematu bazy danych: 

Metabaza – graf schematu bazy danych Odwzorowuje schemat bazy danych w postaci strukturalnej Węzły – definicje bytów zapisanych w bazie danych Krawędzie – powiązania między bytami: is_owner_of (ciągła linia), pomiędzy bytem nadrzędnym oraz podrzędnym points_to (przerywana linia), pomiędzy definicją pointera a definicją obiektu, do którego prowadzi; inherits_from (podwójna linia), pomiędzy definicją klasy obiektu oraz definicją jego nad-klasy. Informacje wewnątrz węzła: id węzła nazwa bytu czy startowy? ograniczenie liczności typ wartości danego bytu

Przykład grafu schematu: 

Przykład grafu schematu

Stosy statyczne S_ENVS i S_QRES: 

Stosy statyczne S_ENVS i S_QRES Zadaniem stosów statycznych jest zasymulowanie ewaluacji zapytań podczas czasu ich kompilacji. Zawierają sygnatury. Sygnatura jest opisem bytu przechowywanego na stosach w czasie wykonania.

Definicja sygnatur: 

Definicja sygnatur Każdy typ elementarny należy do zbioru Sygnatura. Każda referencja do węzła grafu schematu należy do zbioru Sygnatura. Jeżeli x  Sygnatura, zaś n  N, wówczas para n(x)  Sygnatura. Taki rezultat (nazwaną sygnaturę) będziemy nazywać statyczny binder. Jeżeli x1, x2, ...  Sygnatura, wówczas struct{ x1, x2, ...}  Sygnatura. Jeżeli x1, x2, ...  Sygnatura, wówczas variant{ x1, x2, ...}  Sygnatura. Opcja ta jest potrzebna w przypadku, gdy opisywany byt czasu wykonania może mieć wiele sygnatur, zaś podczas kompilacji nie jesteśmy w stanie ustalić, która z nich będzie właściwa. Przykładem takiej sytuacji są kolekcje z heterogenicznymi elementami. Jeżeli x  Sygnatura, wówczas bag{x}  Sygnatura. Jeżeli x  Sygnatura, wówczas sequence{x}  Sygnatura. Zbiór Sygnatura nie ma innych elementów.

Byty czasu wykonania i ich sygnatury: 

Byty czasu wykonania i ich sygnatury struct{i1, i56} sequence{ i1, i6, i11} bag{ struct{i1, i56}, struct{i6, i72}, struct{i11, i72}} bag{struct{n("Kowalski"), Zarobek(2500), d(i56)}} bag{struct{ Dział(i56), Prac( bag{ struct{ n("Nowak"), s(i9 ) }, struct{ n("Stec" ), s(i14) }})} struct{iPrac, iDział} sequence{ iPrac } bag{ struct{ iPrac, iDział } } bag{struct{n(string) Zarobek(int), d(iDział)}} bag{struct{Dział(iDział), Prac( bag{ struct{n(string),s(iZar )}})}}

Statyczna funkcja nested : 

Statyczna funkcja nested Zachowuje się tak samo jak funkcja nested, ale działa na sygnaturach i zwraca statyczne bindery static_nested(iPrac) = { NrP(iNrp), Stan(iStan), Zar(iZar), PracujeW(iPracujeW), Kieruje(iKieruje), ZmieńZar(iZmieńZar), ZarNetto(iZarNetto) } static_nested(iSzef) = { Prac(iPrac) }

Procedura static_eval: 

Procedura static_eval Zachowuje się tak samo jak eval, ale działa na drzewie syntaktycznym, statycznych stosach (sygnaturach) i grafie schematu. Ustala wynikowe sygnatury dla nazw (na podstawie grafu schematu) i literali Ustala wynikowe sygnatury dla operatorów algebraicznych Ustala wynikowe sygnatury dla operatorów niealgebraicznych Zapisuje odpowiednie numery sekcji stosów w drzewie syntaktycznym.

Kroki statycznej ewaluacji zapytania : 

Kroki statycznej ewaluacji zapytania (Prac join (PracujeW.Dział)).(Nazwisko, Nazwa)

Dalsze kroki optymalizacji: 

Dalsze kroki optymalizacji static_eval ustali numery dla operatorów niealgebraicznych i nazw w drzewie syntaktycznym Mając te numery możemy dokonać przekształcenia drzewa, na podstawie procedur rekurencyjnych: void OptymalizujDrzewo(Węzeł Drzewo) – poszukuje od góry operatora niealg.; jeżeli go znajdzie - uruchamia JestNiezależne. Węzeł JestNiezależne(Węzeł OperNiealg) – analizuje numery i ustala id największego podzapytania, które jest niezależne; void PrzenieśPoddrzewo(Węzeł OperNiealg, Węzeł Poddrzewo) –przenosi niezależne poddrzewo w właściwe miejsce, dostawia operator group as i nazwę, wstawia tę nazwę. Po przekształceniu drzewa optymalizację należy zakończyć, następnie wywołać static_eval i optymalizację jeszcze raz. Czynności powtarzamy, aż nie da się już zmienić drzewa.

..........: 

.......... Wyjaśnienie dalszych metod nie zmieściło się. Wszystko jest do poczytania w najnowszym rozdziale książki (50 stron, dużo przykładów) Dalsze tematy: Wykorzystanie dystrybucyjności operatorów Wykorzystanie indeksów gęstych i zakresowych Usuwanie martwych podzapytań c.d.n. Pytania, uwagi, deklaracje?