Optymalizacja zapytań - metoda niezależnych podzapytań.
- Przesuwanie selekcji przed złączenie
- Relatywizm stosu ENVS
- Istota metody niezależnych podzapytań
- Architektura optymalizatora
- Metabaza
- Stosy statyczne
- Drzewo syntaktyczne
- Algorytm statycznej analizy zapytania
- Przesuwanie selekcji przed złączenie
- Operacja złączenia jest czasochłonna i bezpośrednio zależy od wielkości złączanych relacji.
- Zamiast wykonywać najpierw złączenie a później selekcję, wykonuje się wcześniej selekcję na jednej ze złączanych relacji, a później złączenie.
- Metoda przesuwania selekcji przed złączenie redukuje wielkość relacji, przez co złączenie jest wykonywane znacznie szybciej.
- Metoda należy do klasy metod opartych na przepisywaniu, gdyż oparta jest na przepisaniu zapytania do innej postaci według reguły, która zapewnia ten sam wynik zapytania przy skróceniu czasu ewaluacji.
- Metodę tę wiąże się z algebrą relacji, gdyż zdaniem niektórych autorów, tylko algebra relacji pozwala na formalne jej potraktowanie.
- W konsekwencji, metoda ta jest wiązana z obiektowymi algebrami i jest jedną z przyczyn rozkwitu tego nurtu w obiektowych językach zapytań.
- Pokażemy, że związek tej metody z algebrą relacji jest powierzchowny, gdyż metoda ta może być również wyjaśniona na innym gruncie formalnym.
- W istocie, własności algebry relacji są tylko ilustracją metody, która w przypadku podejścia stosowego ma nieporównywalnie bardziej ogólne sformułowanie.
- Obserwacje motywujące metodę
- W podejściu stosowym niektóre podzapytania są obliczane wielokrotnie, gdyż uczestniczą w pętlach implikowanych przez operatory niealgebraiczne.
- Takie podzapytania mogą być obliczone wcześniej, tylko raz, zaś ich wynik może być podstawiany w każdym obrocie pętli iteracyjnej.
- To spostrzeżenie jest podstawą metody niezależnych podzapytań, której idea polega na zmodyfikowaniu tekstowej postaci danego zapytania w taki sposób, aby wszystkie jego podzapytania były ewaluowane najwcześniej jak to możliwe.
- Alternatywnie można obliczyć niezależne podzapytanie tylko w pierwszym obrocie pętli, a następnie odczytać wynik za każdym następnym razem.
- Ta technika ma jednak wadę: utrudnia ewentualne dalsze przepisywanie zapytania w celu jego dalszej optymalizacji.
- 1-szy problem polega na tym, jak ustalić, że dane podzapytanie jest niezależne od danej pętli.
- 2-gi problem polega na tym jak zmodyfikować zapytanie (drzewo syntaktyczne) aby niezależne podzapytanie było liczone tylko raz.
- Relatywizm stosu ENVS
- Zgodnie z semantyką podejścia stosowego, każdy operator niealgebraiczny otwiera na ENVS własną sekcję (w M1-M3 -kilka sekcji)
- Każda występująca w zapytaniu nazwa jest wiązana w pewnej sekcji tego stosu.
- Ponieważ zapytanie może być wywołane w dowolnym środowisku, nie jest możliwe określenie w sposób bezwzględny, w których dokładnie sekcjach zostaną związane poszczególne nazwy przy każdym ewaluowaniu tego zapytania.
- W ogólnym przypadku nie jest znany stan stosu ENVS, przy którym rozpocznie się ewaluacja danego zapytania
- Ponieważ jednak w czasie każdej ewaluacji danego zapytania wszystkie modyfikacje stosu ENVS są takie same, można więc wyznaczyć relatywnie, w których sekcjach nazwy zostaną związane przy każdym obliczeniu tego zapytania, jeżeli za punkt odniesienia zostanie przyjęta pierwsza sekcja położona na stosie podczas ewaluacji tego zapytania.
- W tym celu wszystkie sekcje, które są już na stosie w momencie rozpoczęcia ewaluacji zapytania, należy potraktować jako jedną sekcję o numerze 1.
- Dzięki temu każdemu operatorowi niealgebraicznemu można przypisać liczbę oznaczającą numer otwieranej przez niego sekcji (dla M1-M3 jest to przedział liczb), zaś każdej nazwie można przypisać wysokość stosu w chwili, gdy jest ona wiązana, oraz numer sekcji, w której ta nazwa jest wiązana.
- Istota metody niezależnych podzapytań
- Metoda niezależnych podzapytań polega na badaniu, w której sekcji stosu środowisk są wiązane poszczególne nazwy wchodzące w skład podzapytań tego zapytania.
- Jeżeli wszystkie nazwy danego podzapytania są wiązane w sekcji innej niż ta, która na stos kładzie aktualnie ewaluowany operator niealgebraiczny, to może ono być obliczone zanim operator otworzy tę sekcję, czyli wcześniej, niż to wynika z tekstowego umieszczenia tego podzapytania w zapytaniu (dla M1-M3 należy to zdanie rozszerzyć na wiele sekcji wkładanych przez operator niealgebraiczny).
- Zatem analiza numerów sekcji, w których są wiązane poszczególne nazwy w zapytaniu, staje się podstawą optymalizacji polegającej na unikaniu wielokrotnego liczenia tego samego podzapytania.
- Prosty przykład
- Rozważmy zapytanie dające w wyniku tych pracowników, którzy zarabiają tyle samo co Nowak
(zakładamy tutaj, że w bazie danych jest tylko jeden pracownik o takim nazwisku):
- Prac where Zar = ((Prac where Nazwisko = "Nowak").Zar)
- Zauważmy, że podzapytanie zwracające zarobek Nowaka :
- (Prac where Nazwisko = "Nowak").Zar
- jest ewaluowane tyle razy, ile w bazie danych jest obiektów Prac (potencjalnie bardzo wiele), podczas gdy wystarczyłoby policzyć je tylko raz, gdyż za każdym razem jego ewaluacja da dokładnie taki sam wynik.
-
- Gdy wynik ten jest już znany, to za każdym razem, gdy podzapytanie ma być ewaluowane, wystarczy odczytać obliczoną już wartość.
- O podzapytaniu tego rodzaju będziemy mówić, że jest niezależne od najbliższego operatora niealgebraicznego, którym tutaj jest pierwszy operator where.
- Rozstawianie numerów sekcji stosu
- Zbadajmy wysokości stosu i poziomy wiązania dla nazw oraz numery sekcji, które otwierają operatory niealgebraiczne występujące w tym zapytaniu (przypominamy, że wszystkie sekcje dolne są traktowane jako jedna sekcja).
- Żadna z nazw występujących w podzapytaniu obliczającym zarobek Nowaka nie jest wiązana w sekcji, którą otwiera na stosie operator where:
- nazwy tego podzapytania są wiązane w sekcjach 1 i 3,
- operator otwiera sekcję 2.
- To jest powodem niezależności podzapytania od tego operatora.
- Można je więc obliczyć, zanim operator where otworzy swoją sekcję, czyli przed rozpoczęciem ewaluacji początkowego podzapytania Prac.
- Jak przepisać to zapytanie?
- Należy wyciągnąć niezależne podzapytanie przed pętlę iteracyjną implikowaną przez pierwszy
operator where.
- W tym celu trzeba wprowadzić unikalną nazwę pomocniczą, nazwać nią wynik ewaluacji tego podzapytania i wstawić ją w jego miejsce.
- W tym celu stosujemy operator group as.
- Zapytanie po optymalizacji przyjmie następującą postać:
- Po modyfikacji każde podzapytanie, z wyjątkiem podzapytania z, jest zależne od swojego najbliższego operatora niealgebraicznego, więc dla nich metody niezależnych podzapytań nie można już zastosować.
- Podzapytanie z składa się z jednej nazwy, nie podlega więc dalszej optymalizacji.
- Inny przykład
- Podaj działy wraz z liczbą tych pracowników w nich zatrudnionych, którzy zarabiają więcej od kierowników tych działów:
- Podzapytanie Szef.Prac.Zar jest niezależne od operatora where: wszystkie nazwy są wiązane w sekcjach 2 i 4, podczas gdy operator where otwiera sekcję numer 3.
- Podzapytanie to jest również niezależne od operatora kropki po Zatrudnia.
- Jest zależne od operatora join, który otwiera sekcję numer 2
- Inny przykład cd.
- W tym przypadku można wyciągnąć niezależne podzapytanie przed where, kropkę i count, przepisując całość zapytania do postaci:
- Dział join (((Szef.Prac.Zar ) group as z) . count(Zatrudnia.Prac where Zar > z))
- Po modyfikacji każde podzapytanie, za wyjątkiem podzapytania z, jest zależne od swojego najbliższego operatora niealgebraicznego, więc dla nich metody niezależnych podzapytań nie można już zastosować.
- Zwrócimy uwagę, że podane przekształcenie zilustrowane jest niewyrażalne w algebrze relacji, gdyż w tej algebrze niewyrażalny jest operator count.
- Jest to pierwszy sygnał świadczący o tym, że nasza metoda jest nieporównywalnie bardziej ogólna niż metody znane z systemów relacyjnych.
- Czy zawsze można wyciągnąć podzapytanie przed pętlę?
- Oczywiście nie zawsze. Przykład:
- Zapytanie zwraca pracowników (nazwanych nazwą pomocniczą p) mających najwyższe pensje w swoich działach (model relacyjny):
- Podzapytanie max((Prac where NrD = p.NrD).Zar) nie jest niezależne od zewnętrznego
operatora where, gdyż występująca w nim nazwa p jest wiązana w drugiej sekcji stosu, którą na stos kładzie ten operator.
- Nie można więc zastosować tutaj żadnego z opisanych wyżej wariantów metody niezależnych podzapytań.
- Architektura optymalizatora
-
pokaż animację
- Szare prostokąty - elementy wykonawcze. Białe figury - struktury danych, które one tworzą lub wykorzystują.
- Wejściem jest zapytanie w postaci źródłowej, wyjściem zapytanie skompilowane w postaci drzewa syntaktycznego.
- Optymalizator przepisujący dokonuje zmian drzewa syntaktycznego.
- Działa na trzech strukturach: statycznym stosie środowiskowym S_ENVS (odpowiednik ENVS), statycznym stosie rezultatów S_QRES (odpowiednik QRES) oraz metabazie.
- Statyczna symulacja procesu ewaluacji
- Optymalizator przepisujący podczas optymalizacji symuluje ewaluację zapytania na bazie tej informacji, która jest znana podczas jego parsingu (bez korzystania z informacji zapisanych w bazie danych).
- W związku z tym statyczne stosy zawierają sygnatury obiektów z bazy danych i operują na tych sygnaturach w sposób analogiczny do tego, w jaki później interpreter będzie działał na konkretnych obiektach z bazy danych.
- Operacje na statycznych stosach i sygnaturach są odpowiednikami rzeczywistych operacji na rzeczywistych stosach i składzie danych z pewną dokładnością,
- w szczególności nie są istotne pętle implikowane przez operatory niealgebraiczne, a wyłącznie sygnatura wyniku działania operatora niealgebraicznego.
- Metabaza
- Głównym składnikiem metabazy jest graf schematu bazy danych.
- Metabaza może także zawierać inne dane, np. statystyki dostępu, itd.
- Graf schematu jest wewnętrznym katalogiem danych powstałym jako skutek kompilacji schematu danych.
- Węzły grafu zawierają definicje bytów znajdujących się w bazie danych (obiektów, atrybutów, pointerów, klas, asocjacji itd.) oraz interfejsy metod przechowywanych w bazie danych.
- Nazwane krawędzie grafu modelują powiązania pomiędzy definicjami. Generalnie, może być wiele rodzajów tych powiązań.
- Dla celów metody niezależnych podzapytań wyróżnimy spośród nich trzy:
- is_owner_of (ciągła linia), pomiędzy bytem nadrzędnym (np. definicją obiektu) a bytem w stosunku do niego podrzędnym (np. definicją atrybutu, pointera lub metody);
- points_to (przerywana linia), pomiędzy definicją pointera a definicją obiektu, do którego taki pointer prowadzi;
- inherits_from (podwójna linia), pomiędzy definicją klasy obiektu a definicją jego nadklasy.
- Graf schematu bazy danych (metabaza)
- Informacje w węzłach grafu schematu
- Pozostałe informacje o schemacie przechowywane są w węzłach. Każdy węzeł zawiera pięć informacji:
- Wewnętrzny identyfikator węzła grafu, który będzie służył jako jednoznaczna referencja do tego węzła we wszystkich innych miejscach mechanizmu optymalizacji (w szczególności na stosach S_ENVS i S_QRES);
- Informację, czy dany byt jest obiektem z identyfikatorem startowym (korzeniowym), od nazwy którego może rozpocząć się zapytanie;
- Zewnętrzną nazwę danego bytu (używaną w zapytaniach);
- Ograniczenie liczności definiowanego bytu w bazie danych;
- Typ wartości danego bytu. Typem może być typ elementarny (int, string itd.), specyfikacja wejścia i wyjścia (sygnatura) procedury lub metody, referencje do definicji obiektów podrzędnych w grafie schematu lub referencja do definicji obiektu, do którego prowadzi definicja pointera.
- Dalej referencje do węzłów grafu będziemy je oznaczać i nazwaWęzła, gdzie nazwaWęzła jest nazwą umieszczoną w pierwszym polu na tym rysunku.
- Drugie pole zawiera liczność definiowanego bytu w składzie danych.
- Trzecie (dolne) pole zawiera typ, zestaw referencji do podobiektów, a dla procedur lub metod zawiera parę t1 -> t2, gdzie t1 jest ciągiem nazw i typów parametrów wejściowych, zaś t2 jest typem wyjściowym.
- Stosy statyczne
- Zadaniem stosów statycznych jest dokładne zasymulowanie działania ewaluacji zapytań podczas czasu ich kompilacji.
- Wprowadzamy dwa takie stosy statyczne: S_ENVS i S_QRES (dla symulacji ENVS i QRES odpowiednio).
- Stosy statyczne zawierają sygnatury.
- Sygnatury są opisami odpowiednich bytów przechowywanych na stosach podczas ewaluacji zapytań.
- Zwrócimy uwagę że podana dalej definicja sygnatury jest rekurencyjna.
- Stos S_ENVS zawiera statyczne bindery, tj. pary o postaci
n(sygnatura)
- Definicja sygnatury
- Każdy typ elementarny należy do zbioru Sygnatura.
- Każda referencja do węzła grafu schematu należy do zbioru Sygnatura.
- Każdy literał należy do zbioru Sygnatura. Opcja ta jest potrzebna dla typów wyliczeniowych (enumeration) (określanych niżej jako variant).
- 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.
- Przykładowe sygnatury
- Statyczna funkcja nested
- Analogicznie do funkcji nested, zdefiniujemy static_nested, której zadaniem będzie przygotowanie sekcji na stosie S_ENVS w postaci zbioru statycznych binderów. Funkcja static_nested działa na dowolnej sygnaturze, ale jej wynik jest niepusty dla następujących przypadków:
- Dla sygnatury będącej referencją i Nazwa do węzła grafu schematu opisującego obiekt Nazwa rezultat static_nested zawiera wszystkie statyczne bindery bytów podrzędnych. Np.
- static_nested(iPrac) = { NrP(iNrp), Stan(iStan), Zar(iZar), PracujeW(iPracujeW), Kieruje(iKieruje),ZmieńZar(iZmieńZar), ZarNetto(iZarNetto) }
- Dla sygnatury będącej referencją iNazwa do węzła grafu schematu opisującego pointer Nazwa rezultat static_nested zawiera statyczny binder opisu obiektu, do którego prowadzi ten pointer.
- Dla sygnatury będącej statycznym binderem static_nested zwraca zbiór zawierający ten sam binder.
- Dla statycznych struktur:
- static_nested(struct{s1, ... , sk}) = static_nested(s1) ...
static_nested(sk)
- Drzewo syntaktyczne
- Drzewo syntaktyczne jest strukturą danych powstałą w wyniku rozbioru gramatycznego (parsingu) zapytania.
- Zawiera węzły odpowiadające wszystkim semantycznie istotnym elementom zapytania, powiązanym w taki sposób, aby całkowicie oddać budowę zapytania, z pominięciem syntaktycznego lukru.
- Drzewo syntaktyczne może być bezpośrednio wejściem do interpretera zapytań.
- Wszelkie optymalizacje przez przepisywanie polegają na zmianie drzewa syntaktycznego. Musi ono mieć strukturę ułatwiającą jego przekształcanie.
- Przepisywanie polega na przesuwaniu całych poddrzew w inne miejsce, zmianie poddrzew, usuwaniu poddrzew lub uzupełnianiu drzewa o nowe elementy.
- Na następnym slajdzie zaznaczyliśmy przy niektórych węzłach pole, które będzie służyć do przechowywania informacji o wysokości stosu oraz numerach sekcji wiązania nazw.
- Drzewo syntaktyczne przykładowego zapytania
- Prac where Zar =
((Prac where Nazwisko = "Nowak").Zar)
- Na drzewie tym zaznaczyliśmy operatory
- Drzewo syntaktyczne po przepisaniu
- Algorytm statycznej analizy zapytania
- Podstawą analizy jest graf schematu, traktowany w podobny sposób jak skład danych.
- Wynikiem statycznej ewaluacji zapytania (podzapytania) jest jego sygnatura.
- Celem tej ewaluacji jest przypisanie numerów będących rozmiarem stosu do wszystkich operatorów niealgebraicznych oraz przypisanie par numerów <wysokość stosu, nr sekcji wiązania> do tych nazw występujących w zapytaniu, które będą przedmiotem wiązania na stosie ENVS.
- Analiza tych numerów jest podstawą ustalenia, że dane podzapytanie jest niezależne od najbliższego operatora niealgebraicznego i w konsekwencji, wyciągnięcie takiego podzapytania "przed nawias", czyli przed ten operator niealgebraiczny.
- Szczegółowy algorytm statycznej analizy zapytania znajduje się w książce, w pracy magisterskiej T.Łazarczyka oraz w opisie implementacji platformy Odra.
- Procedura statycznej ewaluacji
- Procedura wyznaczania niezależnych podzapytań
- W rezultacie opisanego wyżej procesu dodatkowe pola informacyjne w węzłach drzewa syntaktycznego zostaną zapełnione następującą informacją:
- Dla węzłów reprezentujących operatory niealgebraiczne - przedział <a,b> numerów sekcji otwieranych przez dany operator,
- Dla węzłów reprezentujących wiązane nazwy - para <c,d>, gdzie c jest wysokością stosu w momencie wiązania nazwy, zaś d - numerem sekcji stosu, w której ta nazwa będzie związana.
- Całość procesu optymalizacji według tej metody można zrealizować za pomocą trzech procedur:
- void OptymalizujDrzewo(Węzeł Drzewo)
- Węzeł JestNiezależne(Węzeł OperNiealg)
- void PrzenieśPoddrzewo(Węzeł OperNiealg, Węzeł Poddrzewo)
- Procedura OptymalizujDrzewo
- Procedura OptymalizujDrzewo rekurencyjnie obiega drzewo syntaktyczne od góry w dół, poszukując operatora niealgebraicznego.
- Po wykryciu takiego węzła uruchamiana jest procedura JestNiezależne, której parametrem jest węzeł tego operatora niealgebraicznego, zaś wynikiem - węzeł największego poddrzewa będącego w obszarze działania tego operatora, lecz od niego niezależnego.
- Jeżeli takie poddrzewo jest znalezione, wówczas uruchamiana jest procedura PrzenieśPoddrzewo, która fizycznie przenosi to poddrzewo przed operator niealgebraiczny, zgodnie z regułą:
- q1 q2(q3) (q3 group as nowaNazwa) . (q1 q2(nowaNazwa))
- gdzie jest operatorem niealgebraicznym, q2(q3) jest zapytaniem, którego składową jest podzapytanie q3, przy czym q3 znajduje się bezpośrednio pod działaniem operatora ; nowaNazwa jest nową, unikalną nazwą nadaną w sposób automatyczny.
- Procedura JestNiezależne
- Procedura wyznaczania niezależnego zapytania JestNiezależne korzysta z przedziału numerów <a,b> charakteryzującego dany operator niealgebraiczny i wyznacza zbiór wszystkich numerów d przypisanych do wiązanych nazw dla danego poddrzewa, poczynając od największego poddrzewa z prawej strony operatora niealgebraicznego i następnie schodząc rekurencyjnie w dół drzewa.
- Jeżeli w wyznaczonym przez nią zbiorze numerów nie ma liczby znajdującej się w przedziale <a,b>, to dane podzapytanie jest niezależne od operatora niealgebraicznego.
- W takim przypadku procedura zwraca węzeł takiego poddrzewa.
- Nie podlegają analizie poddrzewa składające się z jednego literału lub z jednej nazwy (bo nie można ich zoptymalizować), z wyjątkiem, gdy nazwa oznacza wywołanie funkcji lub perspektywy.
- Procedura PrzenieśPoddrzewo
- Procedura fizycznie przenosi podrzewo niezależnego podzapytania poprzez zmianę powiązań pointerowych w drzewie syntaktycznym.
- Dokłada przy tym operator group as oraz unikalną nazwę.
- W stare miejsce poddrzewa wstawia tę nazwę.
- Po zadziałaniu procedury PrzenieśPoddrzewo drzewo syntaktyczne zmienia się, zatem kontynuowanie działania rekurencyjnych procedur na takim drzewie może prowadzić do niespójności.
- W takim przypadku najlepiej powrócić do głównego programu optymalizatora.
- Następnie należy kolejny raz wywołać procedury static_eval i OptymalizujDrzewo.
- Procedury te będą wywoływane aż do momentu, gdy po wywołaniu OptymalizujDrzewo nie nastąpi wywołanie procedury PrzenieśPoddrzewo.
- Wielokrotne wykonanie procedur static_eval i OptymalizujDrzewo zapewni to, że dane podzapytanie zostanie przesunięte przed wszystkie operatory niealgebraiczne, od których jest niezależne.
- Wykorzystanie rozdzielności operatorów
- Dotychczasowe metody optymalizacyjne nie czyniły żadnych dodatkowych założeń odnośnie do własności operatorów niealgebraicznych, zatem obowiązują dla nich wszystkich.
- To oznacza, że nie tylko możemy wyłączać pewne niezależne podzapytanie przed operator złączania, lecz równie dobrze przed kwantyfikatory, operator order by, tranzytywne domknięcia itd.
- Niektóre z wprowadzonych operatorów mają bardzo korzystną własność rozdzielności, która pozwala dodatkowo usprawnić metody optymalizacyjne.
- Operator będziemy określać jako rozdzielny (distributive), jeżeli dla dowolnego stanu składu danych, stanu ENVS oraz zapytań q1, q2, q3 zapytanie
- (q1 q2) q3
- jest semantycznie równoważne zapytaniu
- (q1 q3) (q2 q3)
- Operatory rozdzielne
- Można łatwo stwierdzić, że operatory where, kropka i join są rozdzielne. Wynika to stąd, że wszystkie są oparte na sumie cząstkowych rezultatów zwracanych przez q2.
- Rozdzielność może być podstawą kilku dalszych reguł przekształcania zapytań, które mogą być podstawą pewnej metody optymalizacyjnej. Przykładem jest reguła mówiąca, że dla dowolnych zapytań q1, q2, q3 zachodzi równoważność semantyczna:
- (q1 join q2) where q3 <=> q1 join (q2 where q3)
- Poprzez zmianę kolejności wykonywania operatorów reguła ta może prowadzić do optymalizacji, która polegałaby na analizie kosztu wykonania przedstawionych zapytań i wyborze zapytania z mniejszym kosztem.
- Rozdzielność operatorów prowadzi do dalszych możliwości metod optymalizacyjnych (są opisane w książce).