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



Пример: Оптимизатор System R


Проект System R существенно улучшил состояние оптимизации запросов в реляционных системах. Идеи [55], внедренные во многие коммерческие оптимизаторы, продолжают оставаться удивительно современными. Я представлю здесь некоторые из этих важных идей в контексте запросов Select-Project-Join (SPJ). Класс SPJ-запросов тесно связан с конъюнктивными запросами, которые обычно изучаются в теории баз данных, и включает эти запросы.

Пространство поиска оптимизатора System R в контексте SPJ-запросов состоит из деревьев операций, которые соответствуют линейной последовательности операций соединения; например, последовательность Join (Join (Join (A,B),C),D) проиллюстрирована на рис. 2(a). Такие последовательности логически эквивалентны, поскольку соединения обладают свойствами ассоциативности и коммутативности. Для реализации операции соединения могут быть использованы методы вложенных циклов или сортировки и слияния. В каждом узле сканирования может использоваться индексное сканирование (на основе кластеризованного или некластеризованного индекса) или последовательное сканирование. Наконец, предикаты вычисляются как можно раньше.

Стоимостная модель присваивает оценочную стоимость любому частичному или полному плану в пространстве поиска. Она также определяет оценочный размер потока данных для вывода каждой операции плана. Эти оценки базируются на следующем:

  • Набор статистик, поддерживаемых для отношений и индексов, например, число страниц данных в отношении, число страниц в индексе, число различных значений в столбце.
  • Формулы для оценки селективности предикатов и для прогнозирования размера выходного потока данных для каждого узла-операции. Например, размер вывода соединения оценивается путем перемножения размеров отношений-операндов и применения совместной селективности всех относящихся к соединению предикатов.
  • Формулы для оценки стоимости расходов ЦП и ввода/вывода при выполнении запроса для каждой операции. В этих формулах принимаются во внимание статистические свойства входных потоков данных операции, существующие методы доступа к данным входных потоков, какой-либо имеющийся порядок данных входного потока (например, если входной поток упорядочен, то стоимость соединения методом сортировки и слияния может быть существенно снижена).


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