Welcome Guest Search | Active Topics | Members | Log In

Optymalizacja zapytan: factoring out slabo zaleznych podzapytan Options · View
subieta
Posted: Wednesday, April 23, 2008 6:27:37 PM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
Problem factoring out independent subqueries zostal rozwiazany i zaimplementowany w systemie ODRA. Drazac ten temat wymyslilem jeszcze inny temat doktoratu: wyciaganie przed petle slabo zaleznych podzapytan. Temat ten juz zapodalem panu M.Bleja z Lodzi, ale sadze, ze warto go upublicznic, aby inni tez sie z tym tematem zapoznali. Zalozmy, ze mamy zapytanie:

Code:
Prac where zar > ((Prac where nazwisko = Nowak).zar)


W tym przypadku podzapytanie ((Prac where nazwisko = Nowak).zar) jest niezalezne od pierwszego where i mozna je wyciagnac przed petle. Ale moze sie trafic nieco bardziej zlozona sytuacja. Zalozmy, ze mamy atrybut plec i poszukujemy mezczyzn zarabiajacych wiecej od Nowaka i kobiet zarabiajacych wiecej niz 1000. W takim razie mmy bardziej zlozone zapytanie:

Code:
Prac as p where p.zar > ((Prac where p.sex = "M" and nazwisko = Nowak).zar) union (1000 where p.sex = "K"))


W tym przypadku wewnetrzne podzapytanie nie jest niezalezne, bo zalezy od zmiennej p, ktora ustawia operator where. Ale jest zalezne bardzo slabo: zalezy wylacznie od atrybutu sex, ktory ma dwie wartosci przeliczeniowe: "M" i "K". Zatem to podzapytanie mozna policzyc tez przed petla where dla tych dwoch wartosci, a pod petla juz tylko wstawic odpowiedni if:

Code:
((((Prac where "M" = "M" and nazwisko = Nowak).zar) union (1000 where "M" = "K")) as zM,
         (((Prac where "K" = "M" and nazwisko = Nowak).zar) union (1000 where "K" = "K")) as zK)).
(Prac as p where p.zar > (if p.sex = "M" then zM else zK))


W pierwszej linii liczymy prog dla mezczyzn nazywajac go zM, w drugiej prog dla kobiet nazywajac go zK, nastepniew trzeciej mamy juz wlasciwe nasze zapytanie, gdzie pod ifem wykorzystujemy te zmienne. Zapytanie to mozna oczywiscie dalej optymalizowac poprzez usuniecie oczywistych warunkow:

Code:
((((Prac where nazwisko = Nowak).zar) ) as zM,
         (1000 as zK)).
(Prac as p where p.zar > (if p.sex = "M" then zM else zK))


(Byc moze zle policzylem nawiasy, ale mam nadzieje, ze nie skopalem idei.)

Problem scisle wiaze sie z typami wyliczeniowymi. Jezeli podzapytanie jest zalezne od nazwy, ktora wiaze sie do wartosci z typem wyliczeniowym (takim jak typ {"M", "K"}, to bedziemy mowic ze jest slabo zalezne. W takim przypadku liczymy to podzapytanie dla wszystkich wartosci tego typu wyliczeniowego, odpowiednio nazywajac wyniki, nastepnie wyniki te wykorzystujemy za operatorem niealgebraiczy przez odpwiedni switch (w powyzszym przykladzie if).

Zatem implementacja tej metody wiazalaby sie scisle z implementacja typu wyliczeniowego, a tutaj mamy sporo roznych mozliwosci. Moim zdaniem, ten pomysl jest bardzo prosty, ale moze byc bardzo skuteczny. Przykladowo, zamiast liczyc pewne podzapytanie milion razy, liczymy je tyle razy ile wartosci przyjmuje typ wyliczeniowy, a zwykle to jest liczba dosc ograniczona (ktora zreszta algorytm moze jeszcze dodatkowo ograniczyc).
Users browsing this topic
Guest


Forum Jump
You cannot post new topics in this forum.
You cannot reply to topics in this forum.
You cannot delete your posts in this forum.
You cannot edit your posts in this forum.
You cannot create polls in this forum.
You cannot vote in polls in this forum.

Main Forum RSS : RSS

Powered by Yet Another Forum.net version 1.9.1.6 (NET v2.0) - 11/14/2007
Copyright © 2003-2006 Yet Another Forum.net. All rights reserved.
This page was generated in 0.042 seconds.