Методы оптимизации выполнения запросов в реляционных СУБД


Логическая оптимизация запросов - часть 5


Более важной, особенно в контексте проблем оптимизации, причиной является то, что реляционная алгебра более проста, чем язык SQL. Поэтому, если запрос преобразован к алгебраической форме, дальнейшие действия оптимизатора по выборке оптимальных планов выполнения запроса становятся более простыми. Другими словами, вообще говоря, развитый оптимизатор запросов системы, ориентированной на SQL, должен выявить все возможные планы выполнения любого запроса, но при этом "пространство поиска" этих планов в общем случае очень велико, и в каждом конкретном оптимизаторе используются свои эвристики для сокращения пространства поиска. При этом некоторые потенциально возможные планы вообще никогда не будут рассматриваться (а они могут оказаться более оптимальными). Разумное преобразование запроса на SQL к алгебраическому представлению сокращает пространтво поиска планов выполнения запроса с гарантией того, что оптимальные планы потеряны не будут.

Как нам кажется, наиболее интересными работами, в которых рассматриваются специфические проблемы преобразований запросов на SQL к алгебраической форме, являются работы [57] и [65]. В [54] В.Ким заложил основу подхода, обосновал его важность и предложил ряд конкретных алгоритмов. Но при этом в некоторых конкретных методах он немного ошибся при согласовании семантики SQL и реляционной алгебры. У.Дайял в [65] показал это, ввел более точные формулировки и рассмотрел все возможные случаи.

Основной особенностью языка SQL, отличающей его от языка реляционной алгебры, являются наличие возможности использовать в логическом условии выборки предикаты, содержащие вложенные подзапросы. При этом глубина вложенности не ограничивается языком, т.е., вообще говоря, может быть произвольной. Различные предикаты с вложенными подзапросами при наличии общего синтаксиса могут обладать весьма различной семантикой. Единственным общим для всех возможных семантик вложенных подзапросов алгоритмом выполнения запроса является вычисление вложенного подзапроса всякий раз при вычислении значения предиката.


Начало  Назад  Вперед



Книжный магазин