W podrozdziale 16.7 pokazano, e po czenie iteratorów w planie zapytania pozwala uzy-
ska wysok wydajno . Inaczej dzia a materializacja, kiedy to wynik dzia ania ka dego
operatora jest zwracany w ca o ci zostaje zapisany albo na dysku, albo w pami ci g ów-
nej. Przy stosowaniu iteratorów jednocze nie aktywnych jest wiele operacji. Krotki s
przekazywane mi dzy operatorami na danie, co zmniejsza zapotrzebowanie na pami .
Oczywi cie, co opisano dalej, nie wszystkie operatory fizyczne umo liwiaj sensown ob-
s ug iteracji (potokowania). Czasem prawie wszystkie zadania trzeba wykona w metodzie
Open(), co przypomina materializacj .
15.2. Algorytmy jednoprzebiegowe
W tym miejscu rozpoczyna si omówienie bardzo wa nego zagadnienia w obszarze optymali-
zowania zapyta : Jak nale y wykonywa ka dy z poszczególnych kroków na przyk ad z -
czenie lub selekcj logicznego planu zapytania? . Wybór algorytmu dla ka dego operatora
to kluczowa cz procesu przekszta cania logicznego planu zapytania na plan fizyczny. Cho
zaproponowano wiele algorytmów dla operatorów, nale one g ównie do trzech klas.
(1) Metody oparte na sortowaniu (podrozdzia 15.4).
(2) Metody oparte na haszowaniu (podrozdzia y 15.5 i 20.1).
(3) Metody oparte na indeksach (podrozdzia 15.6).
Ponadto algorytmy dzia ania operatorów mo na podzieli na trzy stopnie na podstawie
trudno ci i kosztów.
a) Niektóre metody wymagaj tylko jednokrotnego wczytania danych z dysku. S to algo-
rytmy jednoprzebiegowe. Omówiono je w tym podrozdziale. Zwykle przynajmniej jeden
z argumentów musi mie ci si w pami ci g ównej, cho zdarzaj si wyj tki, zw aszcza
w zakresie selekcji i projekcji, co opisano w podrozdziale 15.2.1.
b) Niektóre metody dzia aj dla danych, które nie mieszcz si w dost pnej pami ci g ównej,
ale nie dzia aj dla najwi kszych wyobra alnych zbiorów danych. S to algorytmy dwu-
przebiegowe, cechuj ce si pocz tkowym odczytem danych z dysku, przetwarzaniem ich
w pewien sposób, zapisem wszystkich (lub prawie wszystkich) na dysku i pó niejszym
wczytywaniem ich po raz wtóry w celu dalszego przetwarzania w ramach drugiego przebiegu.
Algorytmy tego typu pojawiaj si w podrozdzia ach 15.4 i 15.5.
c) Niektóre metody dzia aj dla dowolnie du ych danych. Metody te wymagaj trzech lub
wi cej przebiegów i s naturalnym, rekurencyjnym uogólnieniem algorytmów dwuprze-
biegowych. Metody wieloprzebiegowe omówiono w podrozdziale 15.8.
W tym podrozdziale skoncentrowano si na metodach jednoprzebiegowych. Tu i w dal-
szych punktach operatory dzielone s na trzy ogólne grupy.
(1) Krotkowe operacje jednoargumentowe (dzia aj ce na pojedynczych krotkach). Te operacje
selekcja i projekcja nie wymagaj jednoczesnego zapisania ca ej relacji (a nawet du ej
jej cz ci) w pami ci. Dlatego mo na wczytywa dane blok po bloku, u ywa jednego bufora
w pami ci g ównej i generowa dane wyj ciowe.
15.2. ALGORYTMY JEDNOPRZEBIEGOWE 635
(2) Operacje jednoargumentowe na ca ych relacjach. Jednoargumentowe operacje tego typu wy-
magaj jednoczesnego umieszczenia w pami ci wszystkich lub wi kszo ci krotek, dlatego
algorytmy jednoprzebiegowe dzia aj tylko dla relacji o rozmiarze M (liczba dost pnych
buforów pami ci g ównej) lub mniejszym. Operacje tej klasy to (grupowanie) i (usuwanie
powtórze ).
(3) Operacje dwuargumentowe na ca ych relacjach. Do tej klasy nale wszystkie pozosta e operacje
suma, cz wspólna, ró nica, z czenia i iloczyny w wersjach dla zbiorów oraz wielo-
zbiorów. Aby zastosowa algorytm jednoprzebiegowy, w ka dej operacji, z wyj tkiem sumy
wielozbiorów, przynajmniej jeden argument musi mie rozmiar nie wi kszy ni M.
15.2.1. Algorytmy jednoprzebiegowe dla operacji krotkowych
Operacjom krotkowym, (R) i (R), odpowiadaj oczywiste algorytmy niezale nie od tego, czy
relacja mie ci si w pami ci g ównej. Nale y wczytywa bloki relacji R jeden po drugim do
bufora wej ciowego, wykonywa operacje na ka dej krotce i przenosi pobrane lub zrzutowane
krotki do bufora wyj ciowego, co pokazano na rysunku 15.5. Poniewa bufor wyj ciowy mo e
by buforem wej ciowym innego operatora lub udost pnia dane u ytkownikowi albo aplikacji,
nie uwzgl dniono bufora wyj ciowego przy obliczaniu potrzebnej pami ci. Dlatego konieczne [ Pobierz całość w formacie PDF ]