Классика баз данных - статьи
Генерация планов
Оптимизатор производит исчерпывающее перечисление планов выполнения запроса. Для каждой таблицы он генерирует план, в котором используется базовый путь доступа, а также по одному плану для каждого альтернативного пути доступа. Каждый план выполнения для одиночной таблицы служит основой для генерации планов соединения.
Оптимизатор строит дерево планов доступа, называемое деревом поиска для перечисляемых планов соединения. С логической точки зрения, рассматриваются все возможные планы. Однако пространство поиска сокращается путем использования следующих эвристик:
- Рассматриваются только праволинейные деревья соединений. Это означает, что соединение четырех таблиц (ABCD) может быть реализовано как (((AB) C)D) или (((AC) B)D), но не как ((AB)(CD)).
- Рассматриваются три метода соединения, а именно, вложенные циклы, хэширование и сортировка со слиянием.
- Новая таблица может быть соединена с существующей композитной (соединенной) таблицей, если либо существует предикат эквисоединения, связывающий композитную и новую таблицы, либо ни для одной из оставшихся таблиц нет предиката эквисоединения, связывающего их с композитом.
- На каждом шаге к дереву поиска добавляется только один план, производящий декартово произведение. К дереву поиска добавляется наименьшая таблица, которая еще не принадлежит композиту, и для которой отсутствует предикат эквисоединения, связывающий ее с композитом. Этот план позволяет оптимизировать некоторые запросы (звездообразные запросы), которые выполняются наилучшим образом, если декартово произведение наименьших таблиц формируется раньше соединения результата с более крупными таблицами.
Каждый узел дерева поиска представляет путь доступа для соединенного набора таблиц. Он характеризуется следующим:
- набором содержащихся в нем таблиц;
- путем доступа для чтения из него строк;
- набором вычисленных предикатов;
- порядком сортировки;
- мощностью.
Важным является понятие порядка. Например, при сканировании таблицы с выборкой строк через индекс строки будут выдаваться в некотором порядке. От этого порядка зависит, можно ли избежать последующей сортировки (для ORDER BY или GROUP BY), или можно ли использовать предикат на ключе индекса, или следует ли выполнить сортировку со слиянием.
Оптимизатор может сокращать дерево поиска при добавлении нового композита. При наличии двух деревьев поиска с одинаковыми характеристиками оставляется дерево с меньшей стоимостью.
Оптимизатор вычисляет результаты всех подзапросов без корреляции на шаге инициализации. Подзапросы с корреляцией выполняются сразу, как только становятся доступными внешние значения.
