Optymalizacja zapytań - Query optimization

Optymalizacja zapytań jest cechą wielu systemów zarządzania relacyjnymi bazami danych i innych baz danych, takich jak bazy danych wykresów . Zapytania optymalizator prób w celu określenia najbardziej efektywnego sposobu wykonania danego zapytania poprzez rozważenie możliwych planów kwerend .

Ogólnie rzecz biorąc, użytkownicy nie mogą uzyskać bezpośredniego dostępu do optymalizatora zapytań: po przesłaniu zapytań do serwera bazy danych i przeanalizowaniu ich przez parser są one następnie przekazywane do optymalizatora zapytań, w którym następuje optymalizacja. Jednak niektóre silniki baz danych umożliwiają prowadzenie optymalizatora zapytań za pomocą wskazówek .

Zapytanie to żądanie informacji z bazy danych. Może to być tak proste, jak „znajdź adres osoby z numerem ubezpieczenia społecznego 123-45-6789” lub bardziej złożone, jak „znajdź średnią pensję wszystkich zatrudnionych żonatych mężczyzn w Kalifornii w wieku od 30 do 39 lat, którzy zarabiają mniej niż ich małżonkowie”. Wynik zapytania jest generowany przez przetwarzanie wierszy w bazie danych w sposób, który zapewnia żądane informacje. Ponieważ struktury baz danych są w większości przypadków złożone, a zwłaszcza w przypadku niezbyt prostych zapytań, dane potrzebne do zapytania można zebrać z bazy danych, uzyskując do niej dostęp na różne sposoby, za pośrednictwem różnych struktur danych i w różnej kolejności. Każdy inny sposób zazwyczaj wymaga innego czasu przetwarzania. Czasy przetwarzania tego samego zapytania mogą mieć duże różnice, od ułamka sekundy do godzin, w zależności od wybranej metody. Celem optymalizacji zapytań, która jest procesem zautomatyzowanym, jest znalezienie sposobu na przetworzenie danego zapytania w jak najkrótszym czasie. Duża możliwa rozbieżność w czasie uzasadnia przeprowadzanie optymalizacji zapytań, chociaż znalezienie dokładnego optymalnego planu zapytania, spośród wszystkich możliwości, jest zazwyczaj bardzo złożone, czasochłonne samo w sobie, może być zbyt kosztowne, a często praktycznie niemożliwe. Tak więc optymalizacja zapytań zazwyczaj próbuje przybliżyć optimum poprzez porównanie kilku zdroworozsądkowych alternatyw, aby zapewnić w rozsądnym czasie „wystarczająco dobry” plan, który zazwyczaj nie odbiega zbytnio od najlepszego możliwego wyniku.

Uwagi ogólne

Istnieje kompromis między ilością czasu spędzonego na ustalaniu najlepszego planu zapytań a jakością wyboru; optymalizator może sam nie wybrać najlepszej odpowiedzi. Różne cechy systemów zarządzania bazami danych mają różne sposoby równoważenia tych dwóch. Optymalizatory zapytań oparte na kosztach oceniają wykorzystanie zasobów różnych planów zapytań i wykorzystują je jako podstawę do wyboru planu. Przypisują one szacunkowy „koszt” do każdego możliwego planu zapytań i wybierają plan o najniższym koszcie. Koszty są używane do oszacowania kosztu środowiska wykonawczego oceny zapytania, pod względem liczby wymaganych operacji we/wy, długości ścieżki procesora , ilości miejsca w buforze dysku, czasu obsługi pamięci dyskowej oraz wykorzystania połączeń między jednostkami równoległości i innych czynniki określone ze słownika danych . Zestaw programów zapytania badanego utworzone przez zbadanie możliwych dróg dostępu (na przykład pierwotny dostęp indeks wtórnego dostępu indeks pełnego skanowania plików) i różne tabeli relacyjnej techniki (na przykład przyłączyć scalające , mieszania przyłączenia , produkt przyłączenia ). Przestrzeń wyszukiwania może stać się dość duża w zależności od złożoności zapytania SQL . Istnieją dwa rodzaje optymalizacji. Obejmują one optymalizację logiczną — która generuje sekwencję algebry relacyjnej w celu rozwiązania zapytania — oraz optymalizację fizyczną — używaną do określenia sposobu wykonania każdej operacji.

Realizacja

Większość optymalizatorów zapytań przedstawia plany zapytań jako drzewo „węzłów planu”. Węzeł planu hermetyzuje pojedynczą operację wymaganą do wykonania zapytania. Węzły układają się w drzewo, w którym wyniki pośrednie przepływają od dołu drzewa do góry. Każdy węzeł ma zero lub więcej węzłów podrzędnych — są to węzły, których dane wyjściowe są przekazywane jako dane wejściowe do węzła nadrzędnego. Na przykład węzeł złączenia będzie miał dwa węzły podrzędne, które reprezentują dwa operandy złączenia, podczas gdy węzeł sortowania będzie miał jeden węzeł podrzędny (dane wejściowe do sortowania). Liście drzewa to węzły, które generują wyniki poprzez skanowanie dysku, na przykład poprzez skanowanie indeksu lub skanowanie sekwencyjne.

Dołącz do zamawiania

Wydajność planu zapytań zależy w dużej mierze od kolejności łączenia tabel. Na przykład podczas łączenia 3 tabel A, B, C o rozmiarze odpowiednio 10, 10 000 i 1 000 000 wierszy wykonanie planu zapytania, który łączy B i C jako pierwszy, może zająć kilka rzędów wielkości więcej czasu niż wykonanie łączy A i C jako pierwsze. Większość optymalizatorów zapytań określa kolejność łączenia za pomocą dynamicznego algorytmu programowania , którego pionierem był projekt bazy danych IBM System R. Ten algorytm działa w dwóch etapach:

  1. Najpierw obliczane są wszystkie sposoby dostępu do każdej relacji w zapytaniu. Do każdej relacji w zapytaniu można uzyskać dostęp poprzez skanowanie sekwencyjne. Jeśli istnieje indeks w relacji, który może być użyty do odpowiedzi na predykat w zapytaniu, można również użyć skanowania indeksu. Dla każdej relacji optymalizator rejestruje najtańszy sposób skanowania relacji, a także najtańszy sposób skanowania relacji, który generuje rekordy w określonej kolejności sortowania.
  2. Optymalizator następnie rozważa połączenie każdej pary relacji, dla której istnieje warunek złączenia. Dla każdej pary optymalizator rozważy dostępne algorytmy łączenia zaimplementowane przez DBMS . Zachowa najtańszy sposób łączenia każdej pary relacji, oprócz najtańszego sposobu łączenia każdej pary relacji, która generuje wynik zgodnie z określonym porządkiem sortowania.
  3. Następnie obliczane są wszystkie plany zapytań z trzema relacjami, łącząc każdy plan z dwiema relacjami utworzony w poprzedniej fazie z pozostałymi relacjami w zapytaniu.

Kolejność sortowania pozwala uniknąć zbędnej operacji sortowania w późniejszym czasie podczas przetwarzania zapytania. Po drugie, określony porządek sortowania może przyspieszyć kolejne łączenie, ponieważ grupuje dane w określony sposób.

Planowanie zapytań dla zagnieżdżonych zapytań SQL

Zapytanie SQL do nowoczesnego relacyjnego DBMS to coś więcej niż tylko selekcje i łączenie. W szczególności zapytania SQL często zagnieżdżają kilka warstw bloków SPJ (Select-Project-Join), za pomocą operatorów grupuj według , istnieje i nie istnieje . W niektórych przypadkach takie zagnieżdżone zapytania SQL można spłaszczyć do zapytania wybierającego z dołączeniem do projektu, ale nie zawsze. Plany zapytań dla zagnieżdżonych zapytań SQL można również wybrać przy użyciu tego samego dynamicznego algorytmu programowania, który jest używany do porządkowania złączeń, ale może to prowadzić do ogromnej eskalacji czasu optymalizacji zapytań. Dlatego niektóre systemy zarządzania bazami danych stosują alternatywne podejście oparte na regułach, które wykorzystuje model wykresu zapytań.

Oszacowanie kosztów

Jednym z najtrudniejszych problemów w optymalizacji zapytań jest dokładne oszacowanie kosztów alternatywnych planów zapytań. Optymalizatory kosztują plany zapytań przy użyciu matematycznego modelu kosztów wykonania zapytań, który w dużej mierze opiera się na szacunkach kardynalności lub liczbie krotek przepływających przez każdą krawędź w planie zapytania. Z kolei estymacja liczności zależy od estymacji czynnika wyboru predykatów w zapytaniu. Tradycyjnie systemy baz danych szacują selektywności za pomocą dość szczegółowych statystyk dotyczących rozkładu wartości w każdej kolumnie, takich jak histogramy . Technika ta sprawdza się dobrze przy estymacji selektywności poszczególnych predykatów. Jednak wiele zapytań zawiera koniunkcje predykatów, takie jak . Predykaty zapytań są często silnie skorelowane (na przykład implikuje ) i bardzo trudno jest ogólnie oszacować selektywność koniunkcji. Słabe oszacowania kardynalności i nieprzechwycona korelacja to jeden z głównych powodów, dla których optymalizatory zapytań wybierają słabe plany zapytań. Jest to jeden z powodów, dla których administrator bazy danych powinien regularnie aktualizować statystyki bazy danych, zwłaszcza po dużych załadowaniach/rozładowaniach danych. select count(*) from R where R.make='Honda' and R.model='Accord'model='Accord'make='Honda'

Rozszerzenia

Klasyczna optymalizacja zapytań zakłada, że ​​plany zapytań są porównywane według jednej metryki kosztów, zwykle czasu wykonania, oraz że koszt każdego planu zapytań można obliczyć bez niepewności. Oba założenia są czasami łamane w praktyce, a w literaturze naukowej badano liczne rozszerzenia klasycznej optymalizacji zapytań, które przezwyciężają te ograniczenia. Te warianty rozszerzonego problemu różnią się sposobem modelowania kosztów planów pojedynczego zapytania oraz celem ich optymalizacji.

Optymalizacja zapytań parametrycznych

Klasyczna optymalizacja zapytań kojarzy każdy plan zapytania z jedną wartością kosztu skalarnego. Optymalizacja zapytania parametrycznego zakłada, że ​​koszt planu zapytania zależy od parametrów, których wartości są nieznane w czasie optymalizacji. Takie parametry mogą na przykład reprezentować selektywność predykatów zapytań, które nie są w pełni określone w czasie optymalizacji, ale zostaną dostarczone w czasie wykonywania. Optymalizacja zapytań parametrycznych wiąże zatem każdy plan zapytania z funkcją kosztów, która mapuje z wielowymiarowej przestrzeni parametrów do jednowymiarowej przestrzeni kosztów.

Celem optymalizacji jest zwykle wygenerowanie wszystkich planów zapytań, które mogą być optymalne dla dowolnej z możliwych kombinacji wartości parametrów. Daje to zestaw odpowiednich planów zapytań. W czasie wykonywania najlepszy plan jest wybierany z tego zestawu, gdy znane są prawdziwe wartości parametrów. Zaletą optymalizacji zapytań parametrycznych jest to, że unika się optymalizacji (która jest ogólnie bardzo kosztowną operacją) w czasie wykonywania.

Optymalizacja zapytań wielocelowych

Oprócz czasu wykonania często istnieją inne metryki kosztów, które są istotne przy porównywaniu planów zapytań. Na przykład w scenariuszu przetwarzania w chmurze należy porównywać plany zapytań nie tylko pod względem czasu ich wykonania, ale także pod względem kosztów wykonania. Lub w kontekście przybliżonej optymalizacji zapytań możliwe jest wykonanie planów zapytań na losowo wybranych próbkach danych wejściowych w celu uzyskania przybliżonych wyników przy zmniejszonych narzutach na wykonanie. W takich przypadkach alternatywne plany zapytań należy porównać pod względem czasu ich wykonania, ale także pod względem precyzji lub wiarygodności generowanych przez nie danych.

Optymalizacja zapytań wielocelowych modeluje koszt planu zapytania jako wektor kosztów, w którym każdy składnik wektora reprezentuje koszt zgodnie z inną metryką kosztów. Klasyczną optymalizację zapytań można uznać za szczególny przypadek optymalizacji zapytań wielokryterialnych, gdzie wymiar przestrzeni kosztów (tj. liczba składników wektora kosztów) wynosi jeden.

Różne metryki kosztów mogą ze sobą kolidować (np. może istnieć jeden plan z minimalnym czasem realizacji i inny plan z minimalnymi opłatami za wykonanie w chmurze w scenariuszu przetwarzania w chmurze). Dlatego celem optymalizacji nie może być znalezienie planu zapytań, który minimalizuje wszystkie metryki kosztów, ale musi być znalezienie planu zapytań, który zapewnia najlepszy kompromis między różnymi metrykami kosztów. Najlepszy kompromis zależy od preferencji użytkownika (np. niektórzy użytkownicy mogą preferować tańszy plan, podczas gdy inni wolą szybszy plan w scenariuszu z chmurą). Celem optymalizacji jest zatem albo znalezienie najlepszego planu zapytań na podstawie określonej specyfikacji preferencji użytkownika dostarczonych jako dane wejściowe do optymalizatora (np. użytkownicy mogą zdefiniować wagi między różnymi metrykami kosztów, aby wyrazić względną wagę lub zdefiniować sztywne ograniczenia kosztów dla niektórych metryk). lub wygenerować aproksymację zestawu planów zapytań optymalnych w sensie Pareto (tj. planów, w których żaden inny plan nie ma lepszych kosztów według wszystkich metryk), tak aby użytkownik mógł wybrać preferowany kompromis kosztowy z tego zestawu planów.

Wielocelowa parametryczna optymalizacja zapytań

Optymalizacja zapytań parametrycznych wielokryterialnych uogólnia optymalizację zapytań parametrycznych i wielokryterialnych. Plany są porównywane według wielu metryk kosztów, a koszty planu mogą zależeć od parametrów, których wartości są nieznane w czasie optymalizacji. Koszt planu zapytania jest zatem modelowany jako funkcja z wielowymiarowej przestrzeni parametrów do wielowymiarowej przestrzeni kosztów. Celem optymalizacji jest wygenerowanie zestawu planów zapytań, które mogą być optymalne dla każdej możliwej kombinacji wartości parametrów i preferencji użytkownika.

Szereg narzędzi wyświetla plany wykonania zapytań, aby pokazać, które operacje mają najwyższy koszt przetwarzania. Microsoft SMS, ApexSQLPlan, Hana i Tableau to tylko niektóre przykłady. Naprawienie tych problemów znalezionych w tych planach może skrócić dziesiątki procent czasu wykonania, a w niektórych przypadkach może skrócić wyszukiwania dwuwymiarowe do liniowych.

Jedną z podstawowych i najprostszych list kontrolnych optymalizacji jest użycie operacji, które większość RDMS zaprojektowano pod kątem wydajnego wykonywania. Zobacz Sargable .

Zobacz też

Bibliografia