Optymalizacja zapytań - wykorzystanie indeksów, usuwanie martwych podzapytań
- Co to są indeksy?
- Dwie istotne własności indeksów
- Klasyfikacja indeksów
- Kiedy nie da się zastosować indeksu?
- Martwe podzapytania
- Uwzględnienie liczności wyniku zapytań
- Graf wynikania
- Co to są indeksy?
- Indeksy są pomocniczymi (redundantnymi) strukturami danych przechowywanymi po stronie serwera.
- Administrator bazy danych generuje nowe indeksy, o ile rozpozna ich potrzebę, lub je usuwa, jeżeli są nieprzydatne.
- Indeksy służą do szybkiego wyszukiwania obiektów.
- Zaletą indeksu jest jego stosunkowo mały rozmiar oraz jednoaspektowość wyszukiwania, co umożliwia ich bardzo efektywną organizację.
- W najbardziej popularnym ujęciu indeks należy rozumieć jako dwu-kolumnową tablicę, gdzie pierwsza kolumna zawiera wartości kluczowe, zaś druga - wartości niekluczowe, najczęściej referencje do obiektów.
- Wartości kluczowe są unikalne i służą jako wejście dla procedury wyszukiwania w indeksie. Wynikiem wyszukiwania według danej wartości kluczowej są wartości niekluczowe umieszczone w tym samym wierszu tablicy.
- Wartości kluczowe są wartościami zapamiętanymi w określonych atrybutach obiektów bazy danych (dla indeksów gęstych) lub są reprezentantami przedziałów tych wartości (dla indeksów zakresowych).
- Mini-baza danych
- Przykładowe indeksy
- Fizyczna organizacja indeksów
- Najbardziej popularną strukturą danych używaną do organizacji indeksów są indeksy z kodowaniem haszującym (hash coding) w bardzo wielu odmianach
- Prawie równie popularne są indeksy oparte na metodzie zwanej B-drzewem (B-tree, balanced tree), również w bardzo wielu odmianach.
- Kodowanie haszujące, oparte na funkcji haszującej (hash function) działającej na wartości kluczowej, dostarcza praktycznie jednakowego czasu wyszukiwania dla dowolnego rozmiaru indeksu.
- Wadą tej metody jest konieczność określenia z góry rozmiaru tablicy indeksu.
- Wada ta jest wyeliminowana przez tzw. dynamiczne haszowanie (dynamic hashing) lub haszowanie liniowe (linear hashing).
- Druga wada polega na konieczności rozstrzygania konfliktów (ten sam wynik funkcji haszującej dla różnych wartości kluczowych).
- Metoda oparta na B-drzewie jest nieco gorsza jeżeli chodzi o czas wyszukiwania i jest wrażliwa na częste aktualizacje indeksu.
- Jej zaletą jest prostota algorytmu i oszczędność miejsca.
- Dwie istotne własności indeksów
- Przezroczystość indeksów dla programisty baz danych.
- Programista nie uwzględnia istnienia indeksów w zapytaniach, są one uwzględniane automatycznie.
- Dzięki temu administrator bazy danych ma pełną swobodę w zakresie generowania nowych indeksów i usuwania indeksów bez konieczności zmiany programów aplikacyjnych.
- Automatyczna aktualizacja indeksów, która następuje w wyniku zmian w bazie danych.
- Indeksy, jak wszystkie struktury redundantne, mogą utracić spójność, o ile baza danych zostanie zaktualizowana.
- Automatyczny mechanizm powinien poprawić, zlikwidować lub od nowa wygenerować indeks w przypadku zmian w bazie danych.
- Architektura systemu z indeksami
- Logiczny obraz indeksu (1)
- Z punktu widzenia języka zapytań, organizacja indeksu i jego własności fizyczne mają znaczenie dla wydajności, lecz nie dla koncepcji.
- Koncepcyjnie, wszystkie indeksy maja postać funkcji, która przyjmuje argument w postaci stringu, liczby, daty, itp. i zwraca wynik w postaci referencji do obiektu lub do obiektów.
- Niekiedy funkcje te mają wiele argumentów i/lub mają argument w postaci zbioru.
- Niektóre typy indeksów (np. indeksy ścieżkowe) zwracają bag struktur referencji do obiektów.
- Same indeksy są zapamiętane w bazie danych. Informacja o nich jest zapamiętana w specjalnym rejestrze indeksów znajdującym się na serwerze i zarządzanym przez administratora bazy danych.
- Rejestr przechowuje całą informację niezbędną do automatycznego wykorzystania indeksu przez optymalizator zapytań.
- Nie będziemy zajmować się organizacją tego rejestru oraz interfejsem jego administratora.
- Logiczny obraz indeksu (2)
- Indeks można uważać za kolekcję zapamiętanych zapytań o jednakowej budowie.
- Np. indeks IndeksOsobaNazwisko(x), dotyczący nazwisk obiektów Osoba, można uważać za realizację zapytania Osoba where Nazwisko = x, gdzie x jest stringowym parametrem.
- Dzięki temu, zapytanie o postaci:
- Osoba where Nazwisko = "Nowak"
- można zastąpić wywołaniem funkcji
- IndeksOsobaNazwisko("Nowak") .
- Reguła zastępowania zapytania przez wywołanie indeksu może być dla niektórych indeksów złożona.
- Jeżeli zostanie odkryty dostatecznie często spotykany wzorzec zapytania, wówczas dla takiego wzorca można zbudować specjalny indeks, i następnie zastępować zapytania poprzez wywołanie indeksu.
- Stąd m.in. wynika duża liczba różnych typów indeksów.
- Do tego dochodzi organizacja fizyczna, która również może być specjalna.
- Klasyfikacja indeksów
- Indeks główny jest obliczony na unikalny klucz kolekcji: dla danego argumentu zwraca dokładnie jedną referencję do obiektu.
- Np. indeks, którego argumentem (wartością kluczową) jest numer PESEL.
- Indeks wtórny jest obliczony na atrybut, którego wartość nie jest unikalna dla danej kolekcji obiektów.
- Np. indeks, którego argumentem (wartością kluczową) jest stanowisko pracownika.
- Indeks gęsty oznacza, że dla każdej wartości atrybutu występującej w bazie danych tworzona jest pozycja indeksu.
- Np. dla obiektów Osoba indeks, którego argumentem jest dowolne nazwisko występujące w bazie danych.
- Indeks zakresowy dotyczy wartości z pewnego zakresu.
- Np. dla atrybutu zarobek indeks zawiera pozycje z przedziałów 0-99, 100-199, 200-299, ...
- Dla nazwisk pozycje mogą mieć postać: "nazwiska zaczynające się na A", "nazwiska zaczynające się na B", ...., "nazwiska zaczynające się na Ż".
- Oprócz tego występują indeksy nie mieszczące się w tej klasyfikacji
- Indeks gęsty
- Realizuje wzorce zapytań:
- NazwaObiektu where NazwaAtrybutu = v
- oraz
- NazwaObiektu where NazwaAtrybutu v;
gdzie v jest parametrem.
- Postępowanie zmierzające do wykorzystania indeksu gęstego IndeksObiektAtrybut nastawionego na indeksowanie obiektów o nazwie NazwaObiektu poprzez wartości atrybutu o nazwie NazwaAtrybutu jest następujące:
- Poszukujemy w drzewie syntaktycznym fragmentu mającego jedną z następujących postaci:
- ... (NazwaObiektu where NazwaAtrybutu = q) ...
- ... (NazwaObiektu where q = NazwaAtrybutu) ...
- ... (NazwaObiektu where NazwaAtrybutu q) ...
- ......
- ... (NazwaObiektu where (p1 and NazwaAtrybutu = q and p2)) ...
- ... (NazwaObiektu where (p1 and q NazwaAtrybutu and p2)) ...
- Postępowanie z indeksem gęstym
- q jest dowolnym zapytaniem objętym działaniem operatora where i niezależnym od tego operatora; p, p1, p2 są dowolnymi warunkami,
- Wiązanie nazwy NazwaObiektu odbywa się w sekcji bazy danych (o numerze 1).
- W tym celu należy wykorzystać procedurę static_eval, która ustali odpowiednie numery dla wiązania nazw.
- Jeżeli sekcji bazowych jest więcej niż jedna, należy ustalić, czy wiązanie odbędzie się w sekcji bazy danych.
- Jeżeli te warunki są spełnione, wówczas odpowiednie fragmenty zapytania należy zastąpić w drzewie syntaktycznym przez fragment drzewa będący wywołaniem funkcji indeksu:
- ...IndeksObiektAtrybut( deref( q ) )...
- Np. ostatnie 2 postacie należy zastąpić w drzewie syntaktycznym poprzez drzewo powstałe z zapytania:
- ...IndeksObiektAtrybut( deref( q ) ) where (p1 and p2)...
- Przykład - przekształcenie drzewa syntaktycznego
- Indeksy zakresowe
- Indeks zakresowy realizuje wzorce zapytań podobne do przypadku indeksu gęstego, ale jego wykorzystanie wiąże się z bardziej złożonymi regułami.
- Wymagają dopasowania aktualnej wartości występującej w zapytaniu do argumentu tego indeksu, zastosowania go, a następnie dodatkowego odfiltrowania wyniku.
- Idea indeksu zakresowego polega na indeksowaniu zbioru obiektów przedziałami wartości atrybutu.
- Np. indeks zakresowy dla zarobku pracownika może określać przedziały: 1-500, 501-1000, 1001-1500, ... Każdy z przedziałów jest jedną pozycją w indeksie.
- Pozycja indeksu zakresowego może zawierać zero, jedną lub więcej wartości niekluczowych.
- Zaletą indeksów zakresowych jest zmniejszenie rozmiaru pamięci, szybsze wyszukiwanie oraz mniejsza wrażliwość na aktualizację bazy danych.
- Indeks zakresowy ułatwia optymalizację w sytuacji, gdy w zapytaniu występuje operator <, <=, > lub >=..
- Funkcja zakresowa
- Indeks zakresowy jest skojarzony z funkcją zakresową, która dla dowolnej wartości kluczowej ustala przedział (zakres), do którego należy.
- Granice przedziału są wyznaczane pojedynczą wartością oraz ustalonym dla danego indeksu rozmiarem przedziału.
- Np. dla indeksu zakresowego dla zarobków funkcja zakresowa dla wartości 77, 345 i 499 przypisuje wartość 500, dla wartości 555, 763, 879 przypisuje wartość 1000, ..., itd.;
- Istotnym kryterium dla funkcji zakresowej jest równomierność rozmieszczenia wartości niekluczowych w poszczególnych pozycjach indeksu.
- Jeżeli np. indeks dotyczyłby polskich miejscowości i miałby mieć 10 pozycji, to (na podstawie książki telefonicznej):
- od Albigowa do Burzenin powinniśmy przypisać wartość 1,
- od Burzyn do Dzieżgoń wartość 2, ...
- od Wieluń do Żywiec wartość 10.
- To zapewnia równomierność rozmieszczenia pozycji niekluczowych.
- Wykorzystania indeksu zakresowego
- Jeżeli indeks jest nastawiony na uwzględnianie operatorów <, <=, > lub >=, wówczas wartości wyznaczane przez funkcję zakresową muszą mieć ten sam porządek liniowy, który obowiązuje dla wszystkich wartości.
- Taka funkcja zakresowa jest określana jako zachowująca porządek (order preserving).
- Jeżeli operatory <, <=, > lub >= są dla danego typu wartości nieistotne, wówczas funkcja zakresowa może być ustalona dowolnie, np. może to być funkcja haszująca.
- Postępowanie optymalizatora zmierzające do wykorzystania indeksu zakresowego jest bardzo podobne do wykorzystania indeksu gęstego, z dwoma różnicami:
- Na wartości wyznaczonej przez zapytanie q należy wykonać funkcję zakresową, a dopiero po tym funkcję indeksu;
- Warunek znajdujący się po operatorze where nie ulega zmianie, gdyż musimy dodatkowo odfiltrować niepotrzebne wartości niekluczowe.
- Zmiana drzewa syntaktycznego
- Przykładowo, jeżeli indeks IndxZakrObiektAtrybut dotyczy obiektów o nazwie NazwaObiektu i jego atrybutu o nazwie
NazwaAtrybutu, funkcja zakresowa ma nazwę FunZakrObiektAtrybut, q jest dowolnym zapytaniem objętym działaniem operatora where i niezależnym od tego operatora, NazwaObiektu jest wiązana w sekcji bazy danych, to zapytanie o postaci:
- ... (NazwaObiektu where (p1 and q NazwaAtrybutu and p2)) ...
- można przepisać do postaci:
- ... IndxZakrObiektAtrybut( FunZakrObiektAtrybut( deref( q )))
where (p1 and q NazwaAtrybutu and p2)) ...
- Odpowiednie modyfikacje drzewa syntaktycznego są podobne do przypadku indeksu gęstego.
- Porównania inne niż =
- Indeksy zakresowe buduje się niekiedy po to, aby uwzględnić optymalizację zapytań z
operatorami porównania <, <=, > lub >=.
- Odbywa się to poprzez wprowadzenie funkcji, która ustala wszystkie te pozycje indeksu, które na pewno będą spełniać warunek
porównania.
- Np. jeżeli mamy warunek
- NazwaAtrybutu < q
- i indeks zarobków dla pracowników, to funkcja FunLtObiektAtrybut(q) dla wartości q = 2450 zwróci sumę wartości niekluczowych z pozycji indeksu mających wartość kluczową 500, 1000, 1500 i 2000.
- Pozycje z przedziału FunZakrObiektAtrybut(deref(q)) mogą warunku nie spełniać, zatem należy je jak poprzednio odfiltrować.
- Jeżeli funkcja FunLtObiektAtrybut(q) wyznacza te pozycje niekluczowe z indeksu IndxZakrObiektAtrybut, które na pewno spełniają warunek NazwaAtrybutu < q, to zapytanie o postaci
- ... (NazwaObiektu where NazwaAtrybutu < q) ...
- zostanie przepisane do postaci
- ...FunLtObiektAtrybut( q )
(IndxZakrObiektAtrybut( FunZakrObiektAtrybut( deref( q )))
where NazwaAtrybutu < q) ...
- Analogiczne dla innych operatorów.
- Kiedy nie da się zastosować indeksu?
- Podane wyżej wzorce zapytań nie zawsze umożliwiają zastosowanie indeksu.
- Indeksu nie da się zastosować, jeżeli nazwa obiektu nie wiąże się w dolnej sekcji stosu (sekcji bazy danych).
- Indeksu nie da się zastosować, jeżeli obiekty identyfikuje pewne wyrażenie różne od nazwy tych obiektów (np. wywołanie funkcji).
- Indeksu nie da się również zastosować, jeżeli q występujące w przytoczonych wyżej zapytaniach jest zależne od najbliższego operatora where.
- Przykładowo, zapytanie:
- Prac where Zar > (Wiek * 100)
- uniemożliwia zastosowanie indeksu IndeksPracZar, gdyż zapytanie Wiek jest zależne od najbliższego operatora where.
- Wybór indeksu do optymalizacji
- W niektórych sytuacjach użycie dwóch lub więcej indeksów jest utrudnione lub niemożliwe. Przykładowo, w zapytaniu:
- Prac where Nazwisko = "Nowak" and Zar = 2000
- można byłoby użyć indeksu IndeksPracNazwisko lub IndeksPracZar, ale nie obu.
- Po przekształceniu zapytania poprzez użycie jednego z nich, np. do postaci:
- IndeksPracNazwisko("Nowak") where Zar = 2000
- użycie drugiego nie spełnia warunków ustalonych przez nas poprzednio.
- Możemy to zapytanie przekształcić do postaci:
- IndeksPracZar( 2000 ) where Nazwisko = "Nowak"
- ale wtedy użycie indeksu nazwisk stanie się niemożliwe.
- Można skorzystania z operatora przecięcia zbiorów:
- IndeksPracNazwisko("Nowak") IndeksPracZar( 2000 )
- ale nie jest pewne, czy będzie to opłacalne:
- Nie bardzo wiadomo, które rozwiązanie jest najlepsze.
- Wybór może wspomóc model kosztów ewaluacji zapytania.
- Model kosztów
- Ponieważ kolekcje obiektów w bazie danych mogą mieć różny rozmiar, różne proporcje wzajemne, różne cechy logiczne i fizyczne itd., zbudowanie teoretycznego modelu kosztów jest niemożliwe.
- Model kosztów jest modelem heurystyczno-empirycznym, który można uzyskać na bazie wielu eksperymentów w realnym środowisku.
- Model ten może korzystać ze wszystkich mierzalnych własności indeksów oraz metamodelu bazy danych.
- W grę wchodzą następujące elementy tego modelu:
- Rozmiar indeksowanych zbiorów obiektów;
- Selektywność indeksów, tj. ile przeciętnie wartości niekluczowych jest dostarczanych w wyniku skorzystania z indeksu;
- Czas odczytania obiektu z pamięci dyskowej (lub innej pamięci trwałej);
- Czas realizacji operatorów użytych w przekształconym zapytaniu, np. operatora przecięcia zbiorów;
- Selektywność warunku znajdującego się po operatorze where, tj. wyrażona w procentach ilość wyselekcjonowanych obiektów.
- Możliwe jest wiele innych czynników.
- Skąd biorą się martwe podzapytania?
- Martwe podzapytania mogą pojawić się jako skutek wielu przeróbek programów aplikacyjnych, w wyniku których końcowa intencja zapytania różni się od początkowej, ale o tej początkowej programista nie pamięta.
- Innym powodem może być sytuacja, w której zapytania są generowane automatycznie przez pewien interfejs (np. graficzny), który przewiduje pewien ogólny format generowania zapytań, ale w konkretnej sytuacji niektóre elementy tego formatu nie są używane.
- Najczęstszym powodem pojawiania się martwych podzapytań jest omawiana w poprzednim semestrze (JPS) metoda modyfikacji zapytań zastosowana do zapytania wywołującego funkcję lub perspektywę.
- Martwe podzapytania jako skutek modyfikacji zapytań
- Niech np. definicja funkcji ma postać:
- procedure MójPrac { return Prac. (Nazwisko as JegoNazwisko,
(Zar/avg(Prac.Zar)*100) as JegoProcentŚredniej,
(PracujeW.Dział.Nazwa) as JegoDział ) };
- Jeżeli ta funkcja będzie wywołana w zapytaniu:
- MójPrac. JegoNazwisko
- to po modyfikacji tego zapytania otrzymamy:
- Prac. (Nazwisko as JegoNazwisko,
(Zar/avg(Prac.Zar)*100) as JegoProcentŚredniej,
(PracujeW.Dział.Nazwa) as JegoDział ). JegoNazwisko
- Liczenie podzapytań JegoProcentŚredniej oraz JegoDział jest tu zbędne, gdyż końcowy wynik od nich nie zależy.
- Jednocześnie, policzenie tych podzapytań może być bardzo kosztowne, Zatem te martwe zapytania (zaznaczone na szaro) należałoby usunąć, sprowadzając zapytanie do postaci:
- Prac.(Nazwisko as JegoNazwisko). JegoNazwisko
- Obserwacje dotyczące martwych podzapytań
- Powodem powstawania martwych podzapytań są te operatory, które dają w wyniku struktury lub bagi/sekwencje struktur.
- Tylko dla nich funkcja nested sumuje bindery pochodzące z ich części.
- W języku SBQL mamy dwie konstrukcje dające w wyniku struktury: operator join oraz operator konstrukcji struktury struct(... , ... , ...)
- struct zwykle pomijamy.
- Jeżeli pewne zapytanie nie ma operatora generującego struktury, to nie może mieć martwych podzapytań.
- Dla operatora join martwe może być tylko podzapytanie z jego prawej strony.
- Dla operatora struct dowolny jego składnik może być potencjalnie martwy.
- Tylko niektóre operatory niealgebraiczne mogą prowadzić do martwych podzapytań, mianowicie, operator kropki oraz kwantyfikatory.
- Jeżeli pewne zapytanie po operatorze generującym struktury nie ma operatora kropki lub kwantyfikatora, to nie może mieć martwych podzapytań.
- Zapytanie może być pozornie martwe, gdyż jego wynik może wpływać na liczność wyniku końcowego.
- Uwzględnienie liczności wyniku zapytań
- Uwzględnienie ostatniej obserwacji wymaga algorytmu określania liczności rezultatów podzapytań.
- Liczność ta ustala w dużym przybliżeniu, ile elementów (ewentualnie, wewnątrz bagu) może dane podzapytanie odłożyć na stosie QRES.
- Do określania tej liczności można przystosować funkcję static_eval, która na bazie liczności zawartych w węzłach grafu schematu wydedukuje liczność wyników poszczególnych podzapytań, umieszczając je w węzłach drzewa syntaktycznego zapytania (dodatkowa informacja).
- Liczność może przyjąć jedną z pięciu możliwości:
- 0 - zapytanie zawsze zwraca pusty wynik;
- 1 - zapytanie zwraca dokładnie jeden wynik;
- [0..1] - zapytanie zwraca pusty wynik lub dokładnie jeden wynik;
- [0..*] - zapytanie zwraca pusty wynik lub więcej wyników;
- [1..*] - zapytanie zwraca co najmniej jeden wynik.
- Zapytanie jest martwe jeżeli jego wynikowa liczność wynosi 1.
- Graf wynikania
- Idea: należy ustalić które podzapytanie wynika z którego.
- Graf wynikania nakłada się na drzewo syntaktyczne zapytania - węzłami tego grafu są węzły drzewa syntaktycznego.
- Samo drzewo syntaktyczne również przedstawia pewien rodzaj wynikania, gdyż węzły (podzapytania) stojące wyżej wynikają z węzłów (podzapytań) znajdujących się niżej w tym drzewie.
- Tym razem chodzi nam jednak o wiązanie nazw oraz wskazanie podzapytania, w wyniku realizacji którego pewna nazwa mogła być związana.
- Na podanych dalej rysunkach poprzednio rysowane przez nas krawędzie drzewa syntaktycznego (obustronne strzałki) zostały tym razem pokazane na szaro.
- Na drzewie tym zdefiniowaliśmy nowe krawędzie (strzałki) posiadające kierunek, które będziemy określać jako wynikanie.
- Graf wynikania - przykład 1
-
pokaż animację
- Założenia grafu wynikania
- Strzałki oznaczające wynikanie prowadzą od podzapytania będącego rezultatem wynikania do podzapytania/podzapytań, z którego/których ten rezultat wynika.
- Dla każdego podzapytania wyznaczana jest liczność wyniku (szare pole na końcu węzła).
- Dla operatorów algebraicznych strzałki wynikania prowadzą od wyniku operatora do wszystkich jego argumentów.
- Podobnie dla wszystkich operatorów niealgebraicznych, z wyjątkiem operatora kropki i kwantyfikatorów.
- Dla operatora kropki i kwantyfikatorów strzałkę wynikania rysujemy tylko od operatora do jego prawej strony; lewą stronę pomijamy.
- Dla każdej nazwy występującej w drzewie zapytania rysujemy strzałkę wynikania od tej nazwy do podzapytania, z której ta nazwa wynika.
- Np. strzałka wynikania prowadzi od nazwy Nazwisko do podzapytania zawierającego nazwę Prac, gdyż wiązanie nazwy Nazwisko odbywa się na binderach, które dostarczyła na stos funkcja nested działająca na rezultacie podzapytania Prac.
- Analogicznie, dla nazwy Dział, której wiązanie umożliwiła funkcja nested działająca na podzapytaniu PracujeW.
- Wyznaczanie strzałek wynikania dla nazw odbywa się poprzez modyfikację procedury static_eval.
- Graf wynikania - przykład 2
- (Prac. (Nazwisko as JN, q1 as JPŚ, q2 as JD)).JN
- Postępowanie po wyznaczeniu grafu wynikania
- Po wyznaczeniu grafu wynikania dalsze postępowanie następuje wyłącznie na drzewie syntaktycznym zapytania i składa się z następujących kroków:
- Poczynając od korzenia drzewa (Start) poruszamy się po drzewie zgodnie z kierunkiem strzałek wynikania, markując wszystkie węzły znajdujące się na ścieżkach wynikania.
- Poczynając od każdego markowanego węzła idziemy w górę drzewa (zgodnie z normalnymi krawędziami drzewa), markując wszystkie napotkane po drodze węzły.
- Węzły, które pozostały nie zamarkowane, reprezentują potencjalnie martwe podzapytania.
- Idąc od góry drzewa syntaktycznego (po jego normalnych krawędziach) usuwamy wszystkie poddrzewa, które nie są zamarkowane i dla których liczność korzenia wynosi dokładnie 1.
- Po usunięciu węzłów konieczne jest usunięcie węzłów operatora join, o ile jego prawy argument został w całości usunięty.
- Analogicznie, można usunąć węzeł operatora struct, o ile okaże się, że liczba argumentów tego operatora wynosi 1.
- Kolejność użycia metod optymalizacyjnych
- Kolejność ta jest wyznaczona zdroworozsądkową heurystyką.
- Chodzi nam tu raczej o zasygnalizowanie problemu niż o podanie ostatecznych reguł.
- Na początku usuwamy martwe podzapytania.
- Następnie stosujemy metodę korzystającą z rozdzielności operatorów. Metodę te stosujemy wielokrotnie, aż do uzyskania sytuacji, gdy dalsze zastosowanie tej metody nie przynosi efektu.
- Następnie stosujemy metodę opartą na "wyciąganiu przed nawias" niezależnych podzapytań. Metodę tę stosujemy wielokrotnie, aż do uzyskania sytuacji, gdy dalsze jej zastosowanie nie przynosi efektu.
- Na końcu stosujemy metody zmierzające do wykorzystania indeksów. Korzystając z rejestru indeksów kolejno badamy możliwość zastosowania danego indeksu w danym zapytaniu. Metodę tę stosujemy wielokrotnie, w celu wykorzystania wszystkich zaimplementowanych indeksów.
- Selekcji właściwego indeksu dokonujemy na podstawie modelu kosztów.
- Zastosowana kolejność metod optymalizacyjnych powinna prowadzić do maksymalnego zysku w postaci czasów wykonania zapytania.