Генерация планов доступа
Планы доступа описывают последовательности операций (представленные графами операций) или промежуточных результатов (объектные графы), ведущие от существующих данных к результату запроса. Оптимизатор запросов должен генерировать достаточно обильный набор планов, чтобы в нем содержался оптимальный план, и достаточно умеренный, чтобы удержать накладные расходы на приемлемом уровне.
Два предельных подхода демонстрируются в [Smith and Chang 1975 и Yao 1979]. Смит и Чанг используют жесткий набор "автоматически программирующих" правил преобразования запросов, похожих на те, которые обуждались в разд. 3. Их процедура генерирует ровно один план, не обязательно оптимальный. Метод Яо генерирует все недоминируемые планы доступа, возможные в данной физической среде. Хотя этот подход может быть пригодным в контексте запросов с двумя переменными, он становится недопустимо дорогостоящим для более сложных запросов.
В других подходах ищется компромисс между эвристическим выбором и детальной генерацией альтернативных планов доступа. Например, в System R [Chamberlin et al. 1981; Selinger et al. 1979] применяется эвристическая процедура, основанная на концепции вложенных блоков SQL. На более нижнем уровне генерируются и сравниваются планы выполнения для каждого блока запроса. На верхнем уровне определяется последовательность выполнения блоков запроса. В [Kim 1982] отмечается, что зависящей от пользователя блочной структуре запроса уделяется слишком много внимания, и предлагается ввести в обработку SQL-запросов шаги стандартизации.
Аналогичный компромисс был выбран в INGRES [Youssefi and Wong 1979]. Поход эвристической декомпозиции преобразует подход к набору подзапросов, каждый из которых содержит не более двух переменных. Для каждого из этих подзапросов производится более детальный анализ его оптимальной реализации.
Исчерпывающая процедура генерации планов доступа для решения конъюнктивных запрросов без кванторов всеобщности и агрегатов предложена в [Rosenthal and Reiner 1982]. Расширенное представление в виде объектного графа используется для моделирования стратегий вычисления, в которых применяются вспомогательные структуры прямого доступа. Чтобы избежать генерации чрезмерного числа стратегий, генерация планов доступа перекрывается с шагом выбора. Не создаются стратегии, противоречащие другим процедурам.
