Welcome Guest Search | Active Topics | Members | Log In

Optymalizacja zapytań - rozszerzone (lub uogólnione) wyciąganie niezależnych podzapytań Options · View
tkowals
Posted: Monday, June 08, 2009 6:01:29 PM
Rank: Advanced Member

Joined: 4/8/2006
Posts: 31
Points: 51
Location: PŁ
W czasie prac z Michałem Bleją nad optymalizacją słabo zależnych zapytań trafiliśmy na zapytania, z którymi jak się nam wydaje metoda "independent" nie bardzo sobie daje radę.

Ogólnie rzecz biorąc, w podrzewie X2 zapytania X1 (OP.NIEALG) X2 zawierającym niezależne zapytanie Y może się również znaleźć podzapytanie Z, które zależy tylko i wyłącznie od zapytania Y. Może wystąpić wtedy problem, że wyciągając zapytanie Y "independent" nie może wyciągnąć zapytania Z.
Dla przykładu w zapytaniu:
Code:
(Emp as e) join (((Dept where manager.Emp.salary > 2000) as d).
   (e.name, d.name, e.salary * 10 > sum(d.employs.Emp.salary)))

podzapytanie (Y)
Code:
(((Dept where manager.Emp.salary > 2000) as d)
jest niezależne, a (Z)
Code:
sum(d.employs.Emp.salary))
(zależne od niego) jest liczone osobno dla każdego d.
Metoda niezależnych podzapytań przekształca je do postaci:
Code:
(((Dept where manager.Emp.salary > 2000) as d) groupas aux0).(Emp as e) join
   (aux0.(e.name, d.name, e.salary * 10 > sum(d.employs.Emp.salary)))

niestety nie optymalizując przetwarzania sum(d.employs.Emp.salary)).

Mam pomysł na trasformacje, która by ten problem rozwiązała, ale jeszcze nie zdążyłem usiąść na nią, żeby ją sformalizować. Z wstępnych testów widać, że optymalizacja przyności duży zysk. Nic nie napisze narazie, bo nie chce nic sugerować, może ktoś chciałby coś w tym temacie konkurencyjne wymyślić.
Chciałbym też zwrócić uwagę, że tych zapytań zależnych może być dowolnie dużo oraz możliwe są chyba zapytania zależne od zapytań zależnych itp. Wydaje mi się, że całkiem sporo zapytań może taka optymalizacja dotyczyć. Czy ktoś może już się natknął na ten problem?
stencel
Posted: Monday, June 08, 2009 6:12:09 PM

Rank: Advanced Member

Joined: 12/7/2004
Posts: 598
Points: 74
Location: Raszyn
Code:
(((Dept where manager.Emp.salary > 2000) as d) groupas aux0).(Emp as e) join
   (aux0.(e.name, d.name, e.salary * 10 > sum(d.employs.Emp.salary)))


tkowals wrote:
niestety nie optymalizując przetwarzania sum(d.employs.Emp.salary)).


Nie rozumiem. Teraz przeciez mozna zapylic niezalezne podzapytania jeszcze raz i bedzie git:

Code:
(((Dept where manager.Emp.salary > 2000) as d) groupas aux0).((sum(aux0.d.employs.Emp.salary)) groupas aux1).(Emp as e) join
   (aux0.(e.name, d.name, e.salary * 10 > aux1)))

tkowals
Posted: Monday, June 08, 2009 7:07:04 PM
Rank: Advanced Member

Joined: 4/8/2006
Posts: 31
Points: 51
Location: PŁ
No właśnie nie bardzo można. Chyba to przekształcenie zupełnie zmienia rezultat tego zapytania jeżeli aux0 będzie zawierało więcej niż jeden dział. Jak aux1 będzie odpowiadał temu działowi, który jest aktualnie przetwarzany?
Poza tym wydaje mi się w przykladzie co podałeś, że aux0 wogóle nie będzie widoczne za joinem.
subieta
Posted: Monday, June 08, 2009 9:52:48 PM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
Rzeczywiście, kolejne stosowanie metody niezależnych podzapytań nie przyniesie w tym przypadku właściwego rezultatu, poniewaz d w wyrazeniu
sum(d.employs.Emp.salary) wiązę się w sekcji otwartej przez kropkę po aux0. Zatem potrzebna jest uogólniona metoda, która pozwala wyłączyć także podzapytania zależne wyłącznie od niezależnego podzapytania, ewentualnie rekurencyjnie. Osobę, która rozwiąże poprawnie ten problem, nagrodzę dobrą miksturą leczącą wszystkie choroby (no, prawie wszystkie), zaś osoby mające niechęć do wszelkich tego rodzaju mikstur nagrodzę jakąś dobrą książką.
tkowals
Posted: Tuesday, June 09, 2009 3:00:11 PM
Rank: Advanced Member

Joined: 4/8/2006
Posts: 31
Points: 51
Location: PŁ
Zmotywowany perspektywą mikstury, która wyleczyłaby mnie z astmy, skoliozy, a przynajmniej z masakrycznego przeziębienia :) naskrobałem algorytm, które wg mnie będzie sobie radził z taką optymalizacją.

File Attachment(s):
Uogólnienie do metody niezależnych podzapytań.pdf (475kb) downloaded 29 time(s).


subieta
Posted: Tuesday, June 09, 2009 4:35:05 PM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
tkowals wrote:
Zmotywowany perspektywą mikstury, która wyleczyłaby mnie z astmy, skoliozy, a przynajmniej z masakrycznego przeziębienia :) naskrobałem algorytm, które wg mnie będzie sobie radził z taką optymalizacją.

Nie jestem pewien czy algorytm jest poprawny, niepokoi mnie troche to, że niezależne podzapytanie wyciągane na poczatek traktowane jest operatorem as a nie groupas. Ogólnie, idea jest moim zdaniem dobra, natomiast ze względu na złożoność szczegóły tego algorytmu nie są intuicyjne dla generalnego przypadku. Bez implementacji i testów trudno się przekonać. Ale bede jeszcze mysleć, do czego zachęcam także innych uczestników tego wątku.
tkowals
Posted: Tuesday, June 09, 2009 5:16:21 PM
Rank: Advanced Member

Joined: 4/8/2006
Posts: 31
Points: 51
Location: PŁ
Bezpośrednio przy wyciąganiu zapytanie jest zawsze traktowane operatorem groupas:
Code:
Y1 groupas aux0

Jak algorytm znajduje zalezne podzapytania Z1,Z2,...,Zn, również używa operatora groupas do ich wyciągnięcia:
Code:
((Y1 as aux00) join aux00.(Z1 groupas aux1, Z2 groupas aux2, ..., Zn groupas auxn)) groupas aux0

Binder aux0 jest utworzony za pomocą groupas, więc jest z punktu widzenia dalszej części zapytania jest pojedynczy.
Operator as stosuje tylko przed joinem, ale wydaje mi się to w tym przypadku uzasadnione, gdyż potrzebujemy aby zostały złączone osobno elementy zwracane przez Y1 z odpowiadającymi im Z1, Z2... itd.
Załóżmy, że Y1 zwraca kolekcje bag(y1_res1, y1_res2,..., y1_resm), wtedy binder aux0 będzie wyglądał następująco

aux0(
struct(
aux00(y1_res1)
aux1(Wynik zapytania Z1 w kontekście y1_res1)
aux2(Wynik zapytania Z2 w kontekście y1_res1)
...
auxn(Wynik zapytania Zn w kontekście y1_res1)
)
struct(
aux00(y1_res2)
aux1(Wynik zapytania Z1 w kontekście y1_res2)
aux2(Wynik zapytania Z2 w kontekście y1_res2)
...
auxn(Wynik zapytania Zn w kontekście y1_res2)
)
...
struct(
aux00(y1_resm)
aux1(Wynik zapytania Z1 w kontekście y1_resm)
aux2(Wynik zapytania Z2 w kontekście y1_resm)
...
auxn(Wynik zapytania Zn w kontekście y1_resm)
)
)
taki binder umożliwia poprawne wykorzystanie obliczonych wyników w właściwej części zapytania. Widać na przykładzie zapytania
Code:
aux0.(aux00, aux1, aux2,..., auxn)

że dzięki takiemu podejściu kropka po aux0 spowoduje iteracje kolejno po strukturach znajdujących się w aux0, a wyniki aux1, aux2, itp. będą skojadzone z odpowiednimi aux00.
Dlatego wg mnie trzeba skorzystać z operatora as przed joinem. Oczywiście mogłem nie przewidzieć wszystkich sytuacji i pewnie można rozwiązać ten problem też inaczej.
stencel
Posted: Wednesday, June 10, 2009 6:16:51 PM

Rank: Advanced Member

Joined: 12/7/2004
Posts: 598
Points: 74
Location: Raszyn
tkowals wrote:
Zmotywowany perspektywą mikstury, która wyleczyłaby mnie z astmy, skoliozy, a przynajmniej z masakrycznego przeziębienia :) naskrobałem algorytm, które wg mnie będzie sobie radził z taką optymalizacją.


Moim zdaniem metoda jest poprawna.

Z drugiej strony mam watpliwosci, czy sluszna droga idziemy. Co chwile pojawiaja sie jakies partykularne przepisywania: metoda podzapytan niezaleznych, slabo zaleznych, mala-duza kolekcja, uogolniona metoda niezaleznych TK itd. Wszystko to sa metody skuteczne, ale brakuje mi jakiegos ogolniejszego obrazu calosci. Jak takie wszystkie rzeczy zunifikowac (jak w fizyce Wielka Unifikacja)? Moze sie nie da? Moze to bez sensu? Moze to scholastyka? Ale brakuje mi.
subieta
Posted: Wednesday, June 10, 2009 9:48:01 PM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
stencel wrote:
Z drugiej strony mam watpliwosci, czy sluszna droga idziemy. Co chwile pojawiaja sie jakies partykularne przepisywania: metoda podzapytan niezaleznych, slabo zaleznych, mala-duza kolekcja, uogolniona metoda niezaleznych TK itd. Wszystko to sa metody skuteczne, ale brakuje mi jakiegos ogolniejszego obrazu calosci. Jak takie wszystkie rzeczy zunifikowac (jak w fizyce Wielka Unifikacja)? Moze sie nie da? Moze to bez sensu? Moze to scholastyka? Ale brakuje mi.

Obawiam się, że będzie ciężko z ogólną metodą. SBQL ma zbyt wiele ciemnych zakamarków, które niekoniecznie poddają się jednolitej chwytliwej teorii. Powtórzę swoje stare złośliwości, ze takie teorie istnieją tylko dla problemów nieistniejących, np. dedukcyjnych baz danych lub programowania w logice. W konkretnym życiu z problemami tego rodzaju trzeba się zmagać jak z reumatyzmem: wyleczyć się kompletnie nie da, istnieje mnóstwo sposobów, aby uniknąć bólu, od ziółek, poprzez oklady aż do interwencji chirurga, ale tak czy inaczej od tych sposobów nie zależy czy przeżyjemy.

Wracając do tematu, kto napisze artykuł? Również na temat przesuwania selekcji przed coś tam. Mikstura czeka.
tkowals
Posted: Wednesday, June 10, 2009 10:08:43 PM
Rank: Advanced Member

Joined: 4/8/2006
Posts: 31
Points: 51
Location: PŁ
O artykule nie było mowy w temacie... czuje się oszukany;).
Osobiście planuje miesiąc dać sobie teraz wolnego.
stencel
Posted: Wednesday, June 10, 2009 10:09:16 PM

Rank: Advanced Member

Joined: 12/7/2004
Posts: 598
Points: 74
Location: Raszyn
subieta wrote:
Wracając do tematu, kto napisze artykuł? Również na temat przesuwania selekcji przed coś tam. Mikstura czeka.


Ja się chetnie podejmę, ale nie chcę odbierać Tomkowi jego pomysłu, bo to właśnie on dopial algorytm. Tak więc proponuje by Tomek zdecydował, czy chce o tym pisać, i o tym, kogo chce zaprosić do tego dzieła.
tkowals
Posted: Thursday, June 11, 2009 10:57:39 AM
Rank: Advanced Member

Joined: 4/8/2006
Posts: 31
Points: 51
Location: PŁ
Dajmy sobie może chociaż chwile czasu zanim artykuł napiszemy. Ja teraz nie mam do tego głowy. Z drugiej strony może tak jak piszę Krzysiek, przyjdzie do głowy jakaś idea, żeby tą problematyke ugryźć jakoś ogólniej. Oprócz problemu optymalizacyjnego z tego topicu z Michałem Bleją wpadliśmy na jeszcze na jeden związany z "ulotnym indeksowaniem", a który może da się w ogólniejszym przypadku ująć jako cachowanie. Opracuje ten temat jeszcze, ale dopiero jakoś po obronie.
subieta
Posted: Thursday, June 11, 2009 6:46:57 PM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
tkowals wrote:
O artykule nie było mowy w temacie... czuje się oszukany;).
Osobiście planuje miesiąc dać sobie teraz wolnego.

Mikstura będzie, niezależnie od artykułu. Musze tylko zmobilizować moich ludzi, aby skontaktowali sie z papą Smerfem lub Gargamelem.
ptab
Posted: Thursday, June 11, 2009 10:09:11 PM
Rank: Newbie

Joined: 11/26/2008
Posts: 7
Points: 21
Location: Warsaw
Wpuściłem to zapytanie w metodę budowania ,,strumieniowego query-planu'' (więcej o tej metodzie tutaj: http://jloxim.mimuw.edu.pl/svn/trunk/docs/our_papers/sbql_streaming/eng/sbql_streaming.pdf):

I wyszła mi taka sieć obliczeniowa: http://jloxim.mimuw.edu.pl/svn/trunk/docs/our_papers/sbql_streaming/imgs/nets/DoubleIndependend.jpg

Sądzę, że ta sieć pracuje prawidłowo i częściwo niezależne podzapytania zostały "wychwycone", ale problem "mixturowy" nie został rozwiązany.

1. (Emp as e) oraz ((`Dept` WHERE (`manager`.(`Emp`.`salary` > 2000))) AS `d`) liczą się na początku zupełnie niezależnie.
2. Komponenty <Merge>[0,3,4], <Struct>, <MakeBag>[0,3] przekształcają na bieżąco wyniki z punktu 1 w bag structów e i d
3. Niestety dla kolejnych structów w tym bagu jest uruchamiane podzapytanie: sum((`d`.(`employs`.(`Emp`.`salary`))))

Wydaje mi się, że oczyszczając tę sieć dało by się przesunąć wiązanie d ponad struct'a (czyli podobnie jak w metodzie martywych podzapytań).
subieta
Posted: Sunday, June 14, 2009 10:02:23 AM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
ptab wrote:
Wpuściłem to zapytanie w metodę budowania ,,strumieniowego query-planu'' (więcej o tej metodzie tutaj: http://jloxim.mimuw.edu.pl/svn/trunk/docs/our_papers/sbql_streaming/eng/sbql_streaming.pdf):

I wyszła mi taka sieć obliczeniowa: http://jloxim.mimuw.edu.pl/svn/trunk/docs/our_papers/sbql_streaming/imgs/nets/DoubleIndependend.jpg

Sądzę, że ta sieć pracuje prawidłowo i częściwo niezależne podzapytania zostały "wychwycone", ale problem "mixturowy" nie został rozwiązany.

1. (Emp as e) oraz ((`Dept` WHERE (`manager`.(`Emp`.`salary` > 2000))) AS `d`) liczą się na początku zupełnie niezależnie.
2. Komponenty <Merge>[0,3,4], <Struct>, <MakeBag>[0,3] przekształcają na bieżąco wyniki z punktu 1 w bag structów e i d
3. Niestety dla kolejnych structów w tym bagu jest uruchamiane podzapytanie: sum((`d`.(`employs`.(`Emp`.`salary`))))

Wydaje mi się, że oczyszczając tę sieć dało by się przesunąć wiązanie d ponad struct'a (czyli podobnie jak w metodzie martywych podzapytań).

Próbowałem zapoznać sie z metodą strumieniową, wydaje się, ze trzeba jeszcze popracować nad prezentacją materiału. Szczególnie niejasne są motywacje co do wprowadzonych pojęć oraz uwikłanie koncepcji w matematyczne definicje, których celu i znaczenia trudno się doszukać. Potrzebny jest jakis prosty przykład na samym poczatku, ktory wyjaśniałby łopatologicznie o co w tym wszystkim chodzi.

Poniewaz temat posrednio dotyczy systemu ODRA, albo trzeba wyodrebnic oddzielny temat, albo dyskusje przeniesc na forum Loxima.
stencel
Posted: Sunday, June 14, 2009 10:54:57 AM

Rank: Advanced Member

Joined: 12/7/2004
Posts: 598
Points: 74
Location: Raszyn
subieta wrote:
Poniewaz temat posrednio dotyczy systemu ODRA, albo trzeba wyodrebnic oddzielny temat, albo dyskusje przeniesc na forum Loxima.


Moze rzeczywiscie Piotrze stworzmy nowy watek o strumieniach i tam bedziemy dyskutowac. Zacznijmy od najprostszego przykladu. Jakis prosty Prac where Zar > 100.
subieta
Posted: Sunday, June 14, 2009 9:34:19 PM

Rank: Advanced Member

Joined: 12/22/2004
Posts: 675
Points: 704
Location: Legionowo
tkowals wrote:
O artykule nie było mowy w temacie... czuje się oszukany;).
Osobiście planuje miesiąc dać sobie teraz wolnego.

Mikstura już nabyta. Niestety, moi ludzie nie skontaktowali się papą Smerfem, więc w tej sytuacji zdecydowalem sie na ofertę Gargamela. Rzeczywiście, trudno przełknąć. Ale leczy wszystko (no, prawie wszystko).
tkowals
Posted: Sunday, June 14, 2009 9:50:30 PM
Rank: Advanced Member

Joined: 4/8/2006
Posts: 31
Points: 51
Location: PŁ
Choróbsko mnie wciąż trzyma, więc będę zobowiązany;)... katar mam, zapchany nos, nic nie czuję, więc jakoś powiniennem przełknąć.
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.171 seconds.