Порядок объединения таблиц

Оценить
(0 голоса)

При определении порядка объединения данных из многочисленных таблиц оптимизаторы должны выбрать стратегию оценки альтернативных соединений. Наиболее быстрая стратегия (называемая иногда greedy join enumeration - перечисление поглощающих объединений) производит упрощения, поэтому может оказаться вполне умеренной в расходовании пространства и времени. Однако и эта стратегия может упустить наилучший план. Более охватывающая стратегия (называемая иногда dynamic join enumeration - перечисление динамических объединений) является исчерпывающей в своем поиске наилучшего плана. Однако эта стратегия может занять много времени в случае сложных слияний, что вызвано большим количеством потенциальных планов.

Оптимизаторы запросов могут также выбрать одну из трех стратегий объединения данных из таблиц: left-deep (углубленного влево дерева), right-deep (углубленного вправо дерева) и bushy tree (низкорослого дерева, или куста). Углубленные деревья имеют лист во всех внутренних узлах, в то время как низкорослые деревья могут их не иметь. Все три типа приведены на рисунке 8.2.

Буквы от а до h представляют таблицы. Углубленное влево дерево, приведенное на рисунке 8.2, может следовать через процесс объединения, как показано в следующих этапах, где tl-t5 - временные таблицы:

На каждом этапе происходит сканирование (просмотр) строк из последующей таблицы, прилагаются предикаты, а результирующие строки присоединяются к содержимому предыдущей временной таблицы, чтобы создать новую временную таблицу. Итоговый набор содержится во временной таблице t5. Обратите внимание, однако, что не все методы объединения будут требовать временные таблицы для промежуточных результатов.

Количество возможных комбинаций объединения углубленных вправо деревьев также может быть вычислено как «!, поэтому оптимизатору снова необходимо оценить 120 возможных порядков объединения таблиц с а по е. В зависимости от метода объединения углубленные вправо деревья могут потребовать большее временное хранилище (и. естественно, больше памяти), чем углубленные влево деревья, поскольку все временные таблицы необходимы вплоть до заключительного этапа. С увеличением количества таблиц в объединении и количества строк, необходимых для слияния, существенно повышаются и требования к временному хранилищу.

Для иллюстрации процесса объединения в случае стратегии низкорослого дерева рассмотрим подмножество такого дерева, приведенное на рисунке 8.2, особенно той его части, которая включает таблицы а, Ь, с и d. Процесс объединения может включать следующие этапы:

Наибольшим неудобством стратегии низкорослого дерева, или куста, является сложность возможностей объединения. Низкорослое дерево лишь с четырьмя таблицами порождает 120 вероятных планов запросов только с двумя методами объединения (методы объединения описаны в следующем разделе) и 960 вероятных планов с четырьмя методами объединения.

Большое число оптимизаторов баз данных не предусматривают низкорослые деревья по причине дополнительного уровня сложности, а углубленные вправо деревья могут не использоваться в тех местах, где для них необходим большой объем рабочего хранилища во время объединения. Наиболее часто реализуются деревья, углубленные влево.

Методы объединения
Объединения вложенного цикла
Объединения посредством слияния-сортировки
Хэш-объединения
Звездообразные объединения

Добавить комментарий


Защитный код
Обновить