7. Оптимизация запросов

Оптимизация запросов сводится к минимизации времени выполнения запросов. Минимум обращений к диску. Минимизация основана на законах эквивалентности алгебры отношений. Основой всех методов оптимизации является дерево операций.

7.1. Основные операции реляционной алгебры и их обозначения

Рис. 7.1 – Схема отношения

Объединение.

.

Рис. 7.2 - Пример операции объединения

Операции изображаются с помощью деревьев.

Терминальными листьями являются отношения, а в узлах записываются операции реляционной алгебры.

Рис. 7.3 - Схема операции объединения

Пересечение.

.

Рис. 7.4 - Пример операции пересечения

Рис. 7.5 - Схема операции пересечения

Разность.

.

Рис. 7.6 - Пример операции разности

Рис. 7.7 - Схема операции разности

Произведение.

.

Рис. 7.8 - Пример операции произведения

Рис. 7.9 - Схема операции произведения

Естественное соединение.

.

Рис. 7.10 - Пример операции естественного соединения

Рис. 7.11 - Схема операции естественного соединения

Тетта-соединение.

.

^F

F – функция, по которой осуществляется соединение.

Рис. 7.12 - Схема операции тетта-соединения

Деление.

.

Рис. 7.13 - Пример операции деления

Рис. 7.14 - Схема операции деления

Селекция

Рис. 7.15 - Пример операции селекции

q=σ_F(r),

q=σ(r(ABCD)),

A>B AND C=D

Операция проекции

Рис. 7.16 - Пример операции проекции

q=π_X(r).

схема, на которую осуществляется проекция.

Пример запроса в базе данных, реализованной на основании её схемы.

( 1) Рис. 7.17 - Схема базы данных

π_AKFT(σ_F>T(((((r₁ r₂) r₃) r₅) r₄))). (2)

AND D>C

AND B=C

Рис. 7.18 - Дерево запроса

К операциям, сокращающим число строк в таблице, относятся селекция, проекция не на ключевой атрибут и устранение строк-дубликатов.

8. Статистические данные, используемые для минимизации запросов

8.1. Анализ стоимости операций

Предположим, что запрос подвергнут синтаксическому разбору и преобразован в логический план. Далее с помощью определенных алгебраических правил план трансформирован в некий "предпочтительный" логический план. Остается превратить его в физический план. Обычно с этой целью рассматривается множество различных физических планов, проистекающих из окончательного логического плана, и вычисляется либо оценивается эффективность (или стоимость) каждого из них. По завершении подобного процесса, часто называемого подсчетом стоимости (cost-based enumeration), выбирается физический план, обладающий низшей оценкой стоимости; именно этот план передается исполняющей машине (execution engine) — компоненту процессора запросов, ответственному за практическое осуществление каждой из операций, предусмотренных выбранным физическим планом запроса. При подсчете «стоимости всех возможных физических планов, которые удается сконструировать на основе заданного логического плана, для каждого физического плана выбираются:

1) порядок следования и способ группирования одноименных ассоциативно-коммутативных операторов, таких как соединение (join), объединение (union) и пересечение (intersection);

2) алгоритм реализации каждого оператора логического плана — скажем, метод соединения посредством вложенных циклов против алгоритма соединения на основе хеширования;

3) дополнительные операторы — сканирования, сортировки и т.д., — необхо­димые для реализации физического плана, но отсутствующие в явном виде в логическом плане;

4) способ передачи значений аргументов от одного оператора к другому — на­пример, посредством сохранения промежуточных результатов на диске либо с помощью итераторов, позволяющих пересылать данные по одному корте­жу или одному буферу оперативной памяти в каждый момент времени.

Таким образом, прежде чем перейти к обсуждению тонкостей процесса подсчета стоимости физических планов, целесообразно остановиться на том, каким образом могут быть получены адекватные оценки стоимости планов. Подобные оценки осно­вываются на параметрах (см. врезку "Еще раз о системе обозначений" выше), значе­ния которых либо вычисляются точно, либо приобретаются в процессе сбора стати­стических характеристик (statistics gathering). Имея такие значения, мы получаем возможность говорить о размерах отношений, вовлеченных в те или иные операции, и осмысленно предсказывать стоимость полного физического плана.

Система обозначений

Соглашения для представ­ления размеров отношений, служащих аргументами операций:

• B(R) — количество блоков, требуемых для хранения всех кортежей отношения R;

• T(R) — количество кортежей отношения R;

• V(R, a) — счетчик значений атрибута а отношения R, т.е. количество различных значений в пределах определенного столбца-атрибута а отношения R. В более общем случае, если (a₁, а₂,..., а_п) — некоторый список атрибутов отношения R,тогда V(R, (a₁, а₂,..., а_п)) — количество различных наборов значений атрибутов a₁, а₂,..., а_п, или число кортежей в σ(π_{a1, а2,..., ап}(R)).