Обзор методов оптимизации запросов в реляционных системах




Пример: Оптимизатор System R - часть 2


Кроме того, проверяется также, не будут ли иметь какой-то порядок данные в выходном потоке.

В оценочной модели механизмы (a)-(c) используются для вычисления для операций плана и связывания с этими операциями следующей информации (вычисления и связывание происходят в направлении от листьев к корню дерева):

  1. Размер выходного потока данных узла-операции.
  2. Любая упорядоченность кортежей, создаваемая или сохраняемая в выходном потоке данных узла-операции.
  3. Оценочная стоимость выполнения операции (и общая стоимость произведенного к этому моменту частичного плана).

Линейное (a) и кустовое (b) соединения

Рис. 2. Линейное (a) и кустовое (b) соединения

Алгоритм перебора в оптимизаторе System R демонстрирует два важных метода: использование динамического программирования и использование интересных упорядочений.

Суть подхода динамического программирования основывается на предположении, что оценочная модель удовлетворяет принципам оптимальности. Более точно, предполагается, что для получения оптимального плана SPJ-запроса Q, состоящего из k соединений, достаточно рассматривать только оптимальные планы для подвыражений Q, которые состоят из (k-1) соединений, и расширять эти планы добавочным соединением. Другими словами, для определения оптимального плана выполнения Q не требуется рассматривать не самые оптимальные планы для подвыражений Q (называемых также подзапросами) с (k-1) соединениями. Соответственно, основанный на динамическом программировании алгоритм перебора представляет SPJ-запрос Q как множество соединяемых отношений { R1, ..., Rn }. Алгоритм перебора работает снизу вверх. В конце j-го шага алгоритм производит оптимальные планы для всех подзапросов размера j. Для получения оптимального плана для подзапроса, включающего (j+1) соединение, мы рассматриваем все возможные способы конструирования плана путем расширения планов, построенных на j-ом шаге. Например, оптимальный план для { R1, R2, R3, R4 } получается выбора плана с наименьшей стоимостью из оптимальных планов для:

  • Join ( {R1, R2, R3}, R4} )
  • Join ( {R1, R2, R4}, R3} )
  • Join ( {R1, R3, R4}, R2} )
  • Join ( {R2, R3, R4}, R1} ).




    Содержание  Назад  Вперед