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
baza
Przykładowe indeksy
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
indeksy
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 ev; 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 e q) ...
......
... (NazwaObiektu where (p1 and NazwaAtrybutu = q and p2)) ...
... (NazwaObiektu where (p1 and q e 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
np
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 e NazwaAtrybutu and p2)) ...
można przepisać do postaci:
... IndxZakrObiektAtrybut( FunZakrObiektAtrybut( deref( q )))
where (p1 and q e 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 ) e
(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") e 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

graf
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
graf
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.