4. Optymalizacja zapytań

Opracowanie sprawnych metod optymalizacji jest fundamentalnym problemem w konstrukcji dowolnego języka zapytań. Przyjmując podane wyżej własności języków zapytań, takie jak deklaracyjność, makroskopowość i wysoki poziom abstrakcji, jest regułą, że bezpośrednia, naiwna ewaluacja zapytań musi prowadzić do nieakceptowalnych czasów wykonania i konsumpcji pamięci. Np. proste zapytanie w SQL:

wymaga wykonania produktu kartezjańskiego relacji wymienionych w klauzuli from. Przyjmując (dość rozsądnie) 10000 dostawców, 10000 produktów, 100000 krotek w relacji DP (wiążącej dostawców z produktami) i średnio 100 bajtów w każdej krotce tych relacji, produkt kartezjański miałby 1013 elementów i zajmowałby 1015 bajtów, czyli ponad 930000 GB. Jeżeli sprawdzenie warunku w klauzuli where dla pojedynczej krotki trwałoby jedną tysięczną sekundy, to wyselekcjonowanie z produktu kartezjańskiego właściwych krotek trwałoby 1010 sekund, czyli ok. 300 lat. Obliczenie takiego zapytania metodą naiwną i pomieszczenie wyników pośrednich w dostępnej pamięci jest więc niemożliwe. Dzięki metodom optymalizacyjnym obliczenie powyższego zapytania trwa kilka sekund i nie wymaga zbyt dużo pamięci.

Metody optymalizacji zapytań można podzielić na następujące grupy:

• Metody oparte na przepisywaniu (rewriting). W metodach tych dokonuje się semantycznie równoważnego przekształcenia zapytania (lub częściej pewnej jego wewnętrznej reprezentacji, np. drzewa syntaktycznego) na taką równoważną semantycznie postać, która rokuje lepszy czas wykonania.

• Wprowadzenie specjalnych struktur danych lub specjalnej organizacji danych. Do tej kategorii można zaliczyć różnego rodzaju indeksy, organizacje plików oparte na kodowaniu mieszającym (hash coding), struktury danych oparte na łańcuchach lub tablicach pointerów, specjalne organizacje tablic w bazie danych umożliwiające bardzo szybkie złączenia itd.

• Unikanie obliczania pewnych fragmentów zapytań. Jest to szczególny przypadek poprzedniej metody. Chodzi tu o unikanie obliczania "martwych" podzapytań, tj. takich fragmentów zapytania, które nie mają wpływu na jego końcowy wynik. Tego rodzaju sytuacje szczególnie często pojawiają się w przypadku automatycznej generacji zapytań z innych języków lub interfejsów, albo wykorzystania wirtualnych perspektyw (views).

• Zapamiętywanie wyników poprzednio obliczonych zapytań. W metodach tych niektóre szczególnie często spotykane zapytania są "materializowane", dzięki czemu nie jest potrzebna powtórna ich ewaluacja. Temat ten wiąże się z zagadnieniem określanym jako "zmaterializowane perspektywy" (materialized views). Metody te często umożliwiają tzw. przyrostową (incremental) aktualizację zmaterializowanego wyniku zapytania jako reakcję na aktualizację bazy danych.

• Jednoczesna optymalizacja wielu zapytań. W sytuacji, kiedy zapytania ewaluuje jeden serwer obsługujący bardzo wiele jednoczesnych zleceń od użytkowników, możliwe jest wyodrębnienie wspólnych części tych zapytań (np. pewnych złączeń) i następnie jednorazowa ich ewaluacja.

• Wybór planu ewaluacji zapytania. Temat ten pojawia się wtedy, gdy istnieje wiele semantycznie równoważnych sposobów ewaluacji zapytania. Np. jeżeli w warunku where pojawiają się podwarunki połączone operatorem AND, to należy wybrać na początku taki elementarny podwarunek, który jest szybki w wykonaniu (np. wykorzystuje indeks) i najsilniej ograniczy obszar danych podlegających przetwarzaniu przez inne warunki.

Przy budowie optymalizatora zapytań zwykle wykorzystuje się szereg wymienionych wyżej metod oraz ich różnorodnych wariantów. Szczególne znaczenie w optymalizacji zapytań mają metody oparte na przepisywaniu oraz metody wprowadzające specjalne struktury i organizacje danych (np. indeksy).