Классика баз данных - статьи
Далее находится наилучший способ соединения
Далее находится наилучший способ соединения какого-либо отношения с каждым из имеющегося набора с учетом эвристики для порядка соединений. В результате производятся решения для соединения пар отношений. Затем находится наилучший способ соединения наборов из трех отношений путем рассмотрения всех наборов из двух отношений и их соединения с каждым третьим отношением, допускаемым эвристикой о порядке соединения. Для каждого плана соединения набора отношений порядок составного результата сохраняется в дереве. Это позволяет рассматривать возможность соединения сканированием со слиянием, для которого не требуется сортировка композиции. После нахождения всех полных решений (соединений всех отношений) оптимизатор выбирает наиболее дешевое решение, выдающее требуемый порядок, если таковой был специфицирован. Заметим, что если существует решение с правильным порядком, сортировка для ORDER BY или GROUP BY не выполняется, если только упорядоченное решение не является более дорогостоящем, чем самое дешевое неупорядоченное решение плюс стоимость сортировки в требуемом порядке.
Число решений, которые требуется сохранять, не превышает 2**n (число подмножеств из n таблиц), умноженное на число интересных порядко результатов. Время вычислений для генерации дерева приблизительно пропорционально тому же числу. Часто это число существенно уменьшается эвристикой порядка соединений. По нашему опыту в типичных случаях требуется всего несколько тысяч байт памяти т несколько десятых долей секунды времени ЦП 370/158. Соединения восьми таблиц оптимизируются за несколько секунд.
