Welcome Guest Search | Active Topics | Members | Log In

Optymalizacja - przesuwanie selekcji przed operator tworzenia struktur Options · View
subieta
Posted: Wednesday, June 03, 2009 10:32:23 AM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
W systemach relacyjnych nazywa sie to przesuwanie selekcji przed złączenie. Wydaje mi sie, że ta prosta optymalizacja nie zostala zaimplementowana w systemie ODRA. Np. weźmy zapytanie
Code:
(Emp as e join e.worksIn.Dept as d join d.manager.Emp as m) where e.sal > 2000 and d.location contains "Toruń" and e.sal > m.sal

Jest ono napisane w stylu relacyjnym, ale z użyciem operatora zależnego złaczenia. Można je przepisać do bardziej optymalnej postaci:
Code:
((Emp as e where e.sal > 2000) join (e.worksIn.Dept as d where d.location contains "Toruń") join d.manager.Emp as m) where e.sal > m.sal

Algorytm polegałby (jak zwykle) na analizie członów wyrażenia tworzącego struktury (przed where) i członów warunku (po where) połaczonych operatorem "and". Analiza poziomów wiazania nazw na stosie pozwałałaby (tak jak w metodzie niezaleznych podzapytań) na rozstrzygnięcie, który z członów warunków należy dopasować do człona operatora tworzenia struktur. Potem, trzeba odpowiednio zmodyfikować drzewo syntaktyczne.

W SBQL są dwa operatory tworzenia struktur: zależne złączenie i operator tworzenia struktur. Być może pewien zysk mogłaby dać normalizacja warunku po where (do dyzjunkcyjnej formy normalnej - np.warunek (a or b) and c byłby sprowadzony do (a and c) or (b and c)).

Optymalizacja ta jest relewantna takze w przypadku, gdy zamiast where mamy kwantyfikator. Np.
Code:
for some(Emp as e join e.worksIn.Dept as d join d.manager.Emp as m) (e.sal > 2000 and d.location contains "Toruń" and e.sal > m.sal)

można byłoby zapisać jako:
Code:
for some ((Emp as e where e.sal > 2000) join (e.worksIn.Dept as d where d.location contains "Toruń") join d.manager.Emp as m) (e.sal > m.sal)


Czy tego rodzaju optymalizację zrealizowano w Loxim?
stencel
Posted: Wednesday, June 03, 2009 10:45:38 AM

Rank: Advanced Member

Joined: 12/7/2004
Posts: 598
Points: 74
Location: Raszyn
subieta wrote:
Czy tego rodzaju optymalizację zrealizowano w Loxim?


Niestety nie. W ogole w tej chwili pracujemy na LoXiM zeby byl stabilny bardziej. W tej chwili niestety dosc czesto rzuca SEGFAULT, bo napisalismy go w C++, ktory na to nie daje odpornosci. Jest szansa jednak, ze wysilki te skoncza sie ustabilizowanym releasem w lutym 2010. Wtedy zaczniemy myslec o implementacji "wodotryskow". Na razie trudno byloby je docenic, gdy LoXiM czesto sie sypie.

Sama optymalizacja jest ciekawa i poprawna. Pewnie mozna by pomyslec o jakims uogolnieniu w postaci "pushing selections to the closest context where they apply". W SQL ten kontekst to bedzie zwykle JOIN, ale i przed GROUP BY z HAVINGA mozna przenosic do WHERE. W SBQL mozna to zrobic znacznie ogolniej ze wzgledu na jego piekna pelna kompozycjonalnosc. Moze jakis doktorat? Nie mam pewnosci.
stencel
Posted: Wednesday, June 03, 2009 10:51:20 AM

Rank: Advanced Member

Joined: 12/7/2004
Posts: 598
Points: 74
Location: Raszyn
subieta wrote:
Jakby tak jeszcze głebiej podrązyć, to mogłaby się z tego zrobić nawet niezla praca doktorska.


Tez mi sie tak wydawalo. Selekcja mozna przesuwac przed prawie kazdy operator SBQLa, jesli selekcje da sie sprowadzic do jego argumentow.
subieta
Posted: Wednesday, June 03, 2009 10:51:41 AM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
Zwrócę jeszcze uwagę, że można także poddać analizie wyrażenia złożone z dwóch, trzech itd. członow wyrażenia konstruujacego struktury. Np. w zapytaniu:
Code:
(Emp as e join e.worksIn.Dept as d join d.manager.Emp as m) where e.sal > 2000 and d.location contains "Toruń" and e.sal > m.sal
and d.budget > 100 * m.sal

ostatni skladnik warunku wiąze dwa człony skonstruowanych struktur. Można je przepisać do postaci:
Code:
((Emp as e where e.sal > 2000) join (((e.worksIn.Dept as d where d.location contains "Toruń") join d.manager.Emp as m))
where d.budget > 100 * m.sal ) where e.sal > m.sal


Jakby tak jeszcze głebiej podrązyć, to mogłaby się z tego zrobić nawet niezla praca doktorska.
subieta
Posted: Wednesday, June 03, 2009 11:04:35 AM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
To moze ktoś chcialby napisac na poczatek na ten temat artykuł? Wydaje się, ze ta metoda jest samograjem, który można złożyć z poprzednio uformowanych klocków.
stencel
Posted: Wednesday, June 03, 2009 11:11:19 AM

Rank: Advanced Member

Joined: 12/7/2004
Posts: 598
Points: 74
Location: Raszyn
subieta wrote:
To moze ktoś chcialby napisac na poczatek na ten temat artykuł? Wydaje się, ze ta metoda jest samograjem, który można złożyć z poprzednio uformowanych klocków.


Ja bardzo chetnie, ale moze ktos jeszcze by mnie wspomogl?
subieta
Posted: Wednesday, June 03, 2009 12:55:47 PM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
Ja oczywiście, ale nie chce byc glownym autorem. Powinien nim zostac ktos, kto chcialby to zaimplementowac w ODRA lub Loxim.
stencel
Posted: Wednesday, June 03, 2009 1:12:21 PM

Rank: Advanced Member

Joined: 12/7/2004
Posts: 598
Points: 74
Location: Raszyn
subieta wrote:
Ja oczywiście, ale nie chce byc glownym autorem. Powinien nim zostac ktos, kto chcialby to zaimplementowac w ODRA lub Loxim.


Wlasnie! LoXiM! A mam jednego doktoranta, ktory bedzie teraz na 1 roku i moze on chcialby. W zasadzie samograj, jak napisales.

No to sobie, profesorowie podyskutowali. Is there anybody out there? [ no moze ktos chociaz skojarzy z jakiego to utworu ]
stencel
Posted: Wednesday, June 03, 2009 1:14:15 PM

Rank: Advanced Member

Joined: 12/7/2004
Posts: 598
Points: 74
Location: Raszyn
subieta wrote:
Ja oczywiście, ale nie chce byc glownym autorem. Powinien nim zostac ktos, kto chcialby to zaimplementowac w ODRA lub Loxim.


W Lodzi mam jeszcze jednego podopiecznego doktoranta na UŁ (kolega pana Blei), ktory nie bardzo wie co z soba zrobic (jest po I roku). Jak bedziemy na obronie T.Kowalskiego, to sie z nim umowilem na jakas 16. Moze cos z tego wyjdzie?
subieta
Posted: Wednesday, June 03, 2009 1:18:08 PM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
stencel wrote:
[quote=subieta]Is there anybody out there? [ no moze ktos chociaz skojarzy z jakiego to utworu ]

Młodzi nie wiedzą, kto by tam pamietał Pink Floyd i ich The Wall. We don't need no education...
stencel
Posted: Wednesday, June 03, 2009 1:19:33 PM

Rank: Advanced Member

Joined: 12/7/2004
Posts: 598
Points: 74
Location: Raszyn
subieta wrote:
stencel wrote:
[quote=subieta]Is there anybody out there? [ no moze ktos chociaz skojarzy z jakiego to utworu ]

Młodzi nie wiedzą, kto by tam pamietał Pink Floyd i ich The Wall. We don't need no education...


Szacun! We certainly do not.
subieta
Posted: Thursday, June 04, 2009 9:20:04 PM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
Takie trzy wątki:

1. Co się dzieje z kwantyfikatorem ogólnym? Załóżmy, że mamy zapytanie:
Code:
forall (Emp as e join e.worksIn.Dept as d join d.manager.Emp as m) (e.sal > 2000 or d.location contains "Toruń" or e.sal > m.sal)

optymalizuje się jako:
Code:
forall ((Emp as e where not (e.sal > 2000)) join (e.worksIn.Dept as d where not(d.location contains "Toruń")) join d.manager.Emp as m) (e.sal > m.sal)

To wynika z praw deMorgana, ale dobrze by było sprawdzić. No i uogólnić.

2. Jezeli chcemy przesuwać warunki po where na dwa lub więcej człony konstruktora struktury, to warto zadbać o to, aby operatory były asocjacyjne. Z pewnością asocjacyjny jest konstruktur struktur:
Code:
struct(q1, q2, q3,...,qn) = struct(((q1, q2), q3),...,qn) = struct(q1, (q2, (q3,...,qn))) = ....dowolna kombinacja innych przypadków nawiasowania

Pytanie czy to samo dotyczy join: czy
Code:
(((q1 join q2) join q3) join ... join qn) = (q1 join ((q2 join q3) join ... join qn)) = ....dowolna kombinacja innych przypadków nawiasowania

Pewnie nie, ale jezeli nie, to jakie to są przypadki i czy mozna je wykluczyć? Taka asocjacyjność dałaby znacznie większe mozliwości przesuwania selekcji przed złączenia.

3. Czy są inne operatory algebraiczne lub niealgebraiczne (oprócz struct, join, forsome, for any), w ktory przesuwanie selekcji przed operator ma sens?
stencel
Posted: Friday, June 05, 2009 11:01:45 AM

Rank: Advanced Member

Joined: 12/7/2004
Posts: 598
Points: 74
Location: Raszyn
Code:
(((q1 join q2) join q3) join ... join qn) = (q1 join ((q2 join q3) join ... join qn)) = ....dowolna kombinacja innych przypadków nawiasowania


Chyba jednak jest! To co myslalem, ze nie jest, to byla kropka:

Code:
[ (1 as a).(1 as b) ] . a != (1 as a). [ (1 as b).a ]


Ale mozemy pewna sztuczka uzyskac łączność kropki. Zamieniany ja na join (wtedy jest) a potem rzutujemy na tylko to co potrzebne.

Code:
[ (1  a) join (1 as b) ] join a == (1 as a) join [ (1 as b) join a ]


a wiec takze:

Code:
{  [ (1  a) join (1 as b) ] join (a as OUTPUT) } . OUTPUT == { (1 as a) join [ (1 as b) join (a as OUTPUT) ] } . OUTPUT


subieta
Posted: Friday, June 05, 2009 1:53:12 PM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
Na oko (moje) brak asocjacyjnosci joina (kropka nie jest interesujaca, na razie) moze byc skutkiem tego, ze różne argumenty joina zwracają tę samą nazwę. Np:
Code:
((1 as x) join (x+1 as x)) join (x+1 as x)

daje
Code:
bag{struct{x(1), x(2), x(2)}, struct{x(1), x(2), x(3)}}

Natomiast
Code:
(1 as x) join ((x+1 as x) join (x+1 as x))

daje
Code:
struct{x(1), x(2), x(3)}

Wystarczy założyć, że każdy człon w wyrażeniu ścieżkowum z joinami daje na stosie bindery o różnych nazwach, aby taka ścieżka była asocjacyjna. Nie wykluczone, że ten warunek można troche osłabić, ale i tak pasuje do niego 90% zapytań ze ścieżką joinów.
stencel
Posted: Saturday, June 06, 2009 5:20:35 PM

Rank: Advanced Member

Joined: 12/7/2004
Posts: 598
Points: 74
Location: Raszyn
subieta wrote:
Na oko (moje) brak asocjacyjnosci joina


Oko Twoje się nie myli. Widać też w tym przykładzie "niealgebraiczność" joina. Ta niealgebraicznosc wynika z wlasciwosci stosu.
subieta
Posted: Saturday, July 11, 2009 4:02:05 PM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
Jeszcze jeden drobiazg, ktory warto poruszyć w planowanym artykule. Chodzi o o operator tworzenia struktur oraz warunki po where (czyli sytuację doskonale znaną z SQL). Oznaczmy skl(x) z indeksem jako składnik struktury wrzucający na stos zmienną x (x może oznaczać więcej zmiennych), zaś war(x) oznacza warunek, w ktorym występuje zmienna x (lub więcej takich zmiennych). Jezeli mamy:
Code:
(skl1(x), skl2(y), skl3(z)) where war(x, y) and coś_tam

to mozemy to przepisać do:
Code:
((skl1(x), skl2(y))where war(x,y), skl3(z)) where coś_tam

Nawiasem mówiąc, nie jestem pewien czy coś takiego jest możliwe w SQL, bo to dawałoby następujące coś:
Code:
select * from (select * from skl1, skl2 where war), skl3 where coś_tam

Nie wszystkie dialekty SQL umożliwiają select wewnatrz klauzuli from. Ale niech tam, nic to nas nie obchodzi.
Na pewno jest to możliwe możliwe w SBQL. Może być jednak inna sytuacja:
Code:
(skl1(x), skl2(y), skl3(z)) where war(x, z) and coś_tam

Teraz mamy gorzej, bo nie jesteśmy w stanie skleić ze sobą skl1(x) i skl3(z). Ale na oko widać, ze jest to tylko powodowane kolejnością operandów, która w istocie nie jest istotna (poza konstruowaniem ostatecznego wyniku). Zatem potrzebna jest funkcja swap(i,j), ktora zmieni kolejność elementów w strukturach: element i-ty przechodzi na element j-ty i odwrotnie. Wtedy naszą optymalizację można beztrudu zapisać w sposób następujący:
Code:
swap(2,3)(((skl1(x), skl3(z))where war(x,z), skl2(y)) where coś_tam)

W optymalizacji zmieniśmy kolejność drugiego i trzeciego elementu struktury, zoptymalizaowaliśmy jak poprzednio, a następnie uzyliśmy funkcji swap do odworzenia oryginalnej kolejności elementów w strukturach.

Wygląda prosto, ale generalny wariant może wymagać nie lada zabawy.
subieta
Posted: Monday, July 13, 2009 11:39:20 AM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
A jeszcze ciekawiej się robi jezeli różne warunki mają przecinające sie podzbiory zmiennych:
Code:
(skl1(x), skl2(y), skl3(z)) where war(x, y) and war (y, z) and coś_tam

Teraz możemy zgrupować pierwszy z drugim, albo drugi z trzecim, ale nie da się równocześnie zrobić tego i tego, trzeba wybrać. Oczywiście na podstawie modelu kosztów. Generalnie, problem dla ogólnego przypadku oznacza podział zbioru skladników konstruktora struktury na grupy, w ogólnym przypadku zagnieżdżone i przecinające się, zgodnie z warunkami połączonymi spójnikiem and po where. Następnie musimy wybrać takie grupy, które się nie przecinaja (ale mogą się zawierać) i pokrywają całość konstruktora struktury, na podstawie pewnej funkcji kryterialnej (modelu kosztów) zapewniającej optymalny plan wykonania. Robi się taka matematyka, że hej.

Problem jest najprawdopodobniej scholastyczny, ale za to jaki "naukowy"!

Jak by ktoś miał obrzydzenie do SBQL, informuję, ze ten sam problem występuje również dla SQL, nawet we wzmocnionej postaci. Tam liczne tabele po from są normą - pokazywano mi zdanie SQL z 30-toma tabelami po from (wygenerowane automatycznie przez 4GL). Był to n.b. przykład sytuacji, w ktorych optymalizator SQL dostaje fioła. Chociaż moja wiedza na temat optymalizacji SQL pochodzi zprzed 10-ciu lat, nikt takiego problemu nie formułował i prawdopodobnie nie uległo to zmianie w ostatnich latach.
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.189 seconds.