Проектирование баз данных

Стратегия эвристической обработки запросов
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.
Улучшение логического плана запроса
Улучшению качества логических планов способны послужить многие из алгебраических законов, рассмотренных ранее, но наиболее широкое применение в оптимизаторах запросов находят следующие подходы:
Продвижение операторов выбора «вниз» по дереву до максимально «глубокого» уровня. Если условие выбора представляет собой конъюнкцию (AND) нескольких частных условий, его можно расщепить, чтобы продвигать каждый оператор отдельно.
При определенных обстоятельствах целесообразнее вначале продвинуть оператор выбора «вверх» по дереву выражений, и только затем – «вниз».
Продвижение существующих операторов проекции «вниз» по дереву или добавление новых операторов, что, как и в случае с операторами выбора, требует тщательного анализа.
Изъятие операторов удаления кортежей-дубликатов или перемещение в требуемые позиции дерева.
Сочетание определенных операторов выбора с расположенными ниже по дереву операторами декартова произведения с целью замены пары операций одной операцией соединения посредством равенства (equijoin).

Группирование ассоциативно-коммутативных операторов
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.
Традиционными синтаксическими анализаторами не создаются деревья с вершинами, обладающими неограниченно большим количеством дочерних вершин, – обычно операторы пребывают только в унарной или бинарной форме.
Операторы, для которых справедливы ассоциативный и коммутативный законы, способны обладать произвольным количеством операндов.
Группирование соседних вершин дерева, представляющих одноименные ассоциативно-коммутативные операторы, в единую вершину со многими дочерними вершинами (естественное соединение, объединение и пересечение).
Операторы естественного и Θ-соединения допускают возможность взаимного сочетания при выполнении следующих условий :
операторы естественного соединения заменены Θ-соединениями с условиями равенства одноименных атрибутов отношений-аргументов;
при переходе от естественного соединения к Θ-соединению с помощью оператора проекции удаляются дубликаты атрибутов;
условия операторов Θ- соединения ассоциативны.
Оператор декартова произведения, интерпретируемый как частный случай естественного соединения, может сочетаться с операторами соединения, если они представлены смежными вершинами дерева выражений.

Анализ стоимости операций
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.
При подсчете стоимости всех возможных физических планов, которые удается построить на основе логического плана, учитывается следующая информация:
порядок следования и группирования одноименных, ассоциативно-коммутативных операторов;
алгоритм реализации каждого оператора логического плана;
дополнительные операторы, необходимые для реализации физического плана, но отсутствующие в явном виде в логическом плане;
способ передачи значений атрибутов от одного оператора другому.

Оценка результатов промежуточных отношений
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.
Цель прогнозирования размеров промежуточных отношений – не получение точных оценок, а упрощение выбора физического плана по принципу: минимальная стоимость – наилучший план.
Физический план выбирается таким образом, чтобы свести к минимуму примерную стоимость выполнения запроса.
Введем обозначения:

Оценка результата проекции
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.
Проекция относится к операторам, объем результата выполнения которых вычисляется точно. Изменение объема может быть обусловлено только изменением структуры.
Пусть имеется:

Оценка результата проекции (пример)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.

Оценка результата выборки
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.
В этом случае размер отдельного кортежа сохраняется, количество кортежей уменьшается.

Оценка результата выборки (продолжение)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.

Оценка результата выборки (примеры)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.

Оценка результата выборки (продолжение)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.

Оценка результата соединения
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.

Оценка результата соединения (продолжение)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.

Оценка результата соединения (допущения)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.
Упрощающие допущения:

Оценка результата соединения (один общий атрибут)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.

Оценка результата соединения с одним общим атрибутом (пример)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.
Пусть имеются отношения R(a,b), S(b,c), U(c,d)

Оценка результата соединения с одним общим атрибутом (вариант 1)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.
1.

Оценка результата соединения с одним общим атрибутом (вариант 2)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.
2.

Естественное соединение отношений с несколькими общими атрибутами
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.

Естественное соединение отношений с несколькими общими атрибутами (продолжение)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.

Естественное соединение отношений с несколькими общими атрибутами (пример)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.
Пусть имеются отношения R(a,b,с), S(d,e,f) , обладающие следующими статистическими характеристиками:

Естественное соединение отношений с несколькими общими атрибутами (пример)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.

Соединение нескольких отношений
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.

Соединение нескольких отношений (продолжение)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.

Соединение нескольких отношений (пример)
Раздел 2.
Компиляция и оптимизация. Анализ стоимости операций.
Пусть имеются отношения R(a,b,с), S(b,c,d) и U(b,e), обладающие следующими статистическими характеристиками: