Optymalizacja zapytań w scentralizowanych systemach

Po wyznaczeniu alternatywnych ścieżek dostępu do obliczenia wyrażenia algebry relacyjnej określana jest optymalna ścieżka dostępu. W tym rozdziale zajmiemy się optymalizacją zapytań w systemie scentralizowanym, natomiast w kolejnym rozdziale zajmiemy się optymalizacją zapytań w systemie rozproszonym.

W scentralizowanym systemie przetwarzanie zapytań odbywa się w następującym celu -

Minimalizacja czasu odpowiedzi na zapytanie (czas potrzebny do uzyskania wyników na zapytanie użytkownika).
Maksymalizuj przepustowość systemu (liczbę żądań przetwarzanych w określonym czasie).
Zmniejsz ilość pamięci i miejsca wymaganego do przetwarzania.
Zwiększ równoległość.

Analiza kwerendy i tłumaczenie

Początkowo skanowane jest zapytanie SQL. Następnie jest analizowany pod kątem błędów składniowych i poprawności typów danych. Jeśli zapytanie przejdzie ten krok, zostanie rozłożone na mniejsze bloki zapytań. Każdy blok jest następnie tłumaczony na równoważne wyrażenie algebry relacyjnej.

Kroki optymalizacji zapytań

Optymalizacja zapytań obejmuje trzy kroki, a mianowicie generowanie drzewa zapytań, generowanie planu i generowanie kodu planu zapytania.

Step 1 − Query Tree Generation

Drzewo zapytań to drzewiasta struktura danych reprezentująca wyrażenie algebry relacyjnej. Tabele zapytania są reprezentowane jako węzły liści. Operacje algebry relacyjnej są reprezentowane jako węzły wewnętrzne. Rdzeń reprezentuje zapytanie jako całość.

Podczas wykonywania węzeł wewnętrzny jest wykonywany zawsze, gdy dostępne są jego tablice operandów. Węzeł jest następnie zastępowany tabelą wyników. Ten proces jest kontynuowany dla wszystkich węzłów wewnętrznych do momentu wykonania węzła głównego i zastąpienia go tabelą wynikową.

Na przykład rozważmy następujące schematy -

PRACOWNIK

EmpID	EName	Wynagrodzenie	DeptNo	Data dołączenia

DEPARTAMENT

DNo	DName	Lokalizacja

Przykład 1

Rozważmy zapytanie w następujący sposób.

$$ \ pi_ {EmpID} (\ sigma_ {EName = \ small "ArunKumar"} {(PRACOWNIK)}) $$

Odpowiednie drzewo zapytań będzie -

Przykład 2

Rozważmy inne zapytanie dotyczące złączenia.

$ \ pi_ {EName, Salary} (\ sigma_ {DName = \ small "Marketing"} {(DEPARTMENT)}) \ bowtie_ {DNo = DeptNo} {(PRACOWNIK)} $

Poniżej znajduje się drzewo zapytań dla powyższego zapytania.

Step 2 − Query Plan Generation

Po wygenerowaniu drzewa zapytań tworzony jest plan zapytań. Plan zapytań to rozszerzone drzewo zapytań, które zawiera ścieżki dostępu do wszystkich operacji w drzewie zapytań. Ścieżki dostępu określają, jak powinny być wykonywane operacje relacyjne w drzewie. Na przykład operacja wyboru może mieć ścieżkę dostępu, która zawiera szczegółowe informacje na temat użycia indeksu drzewa B + do wyboru.

Poza tym plan zapytań określa również, w jaki sposób tabele pośrednie powinny być przekazywane od jednego operatora do drugiego, jak powinny być używane tabele tymczasowe i jak operacje powinny być przetwarzane potokowo / łączone.

Step 3− Code Generation

Generowanie kodu to ostatni krok optymalizacji zapytań. Jest to wykonywalna forma zapytania, której forma zależy od typu podstawowego systemu operacyjnego. Po wygenerowaniu kodu zapytania Menedżer wykonania uruchamia go i generuje wyniki.

Podejścia do optymalizacji zapytań

Wśród podejść do optymalizacji zapytań najczęściej stosuje się wyszukiwanie wyczerpujące i algorytmy oparte na heurystyce.

Wyczerpująca optymalizacja wyszukiwania

W tych technikach dla zapytania początkowo generowane są wszystkie możliwe plany zapytań, a następnie wybierany jest najlepszy plan. Chociaż te techniki zapewniają najlepsze rozwiązanie, mają one wykładniczą złożoność czasową i przestrzenną ze względu na dużą przestrzeń rozwiązań. Na przykład technika programowania dynamicznego.

Optymalizacja oparta na heurystyce

Optymalizacja oparta na heurystyce wykorzystuje metody optymalizacji oparte na regułach do optymalizacji zapytań. Algorytmy te mają wielomianową złożoność czasową i przestrzenną, która jest niższa niż wykładnicza złożoność algorytmów opartych na wyczerpującym wyszukiwaniu. Jednak te algorytmy niekoniecznie zapewniają najlepszy plan zapytań.

Niektóre z typowych reguł heurystycznych to:

Wykonaj operacje wyboru i projektu przed połączeniem. Odbywa się to poprzez przeniesienie operacji wyboru i projektu w dół drzewa zapytań. Zmniejsza to liczbę krotek dostępnych do łączenia.
Najpierw wykonaj najbardziej restrykcyjne operacje wyboru / projektu przed innymi operacjami.
Unikaj operacji obejmujących różne produkty, ponieważ skutkują one bardzo dużymi tabelami pośrednimi.