Оптимизация формул реляционной алгебры

Пусть условие F = f 1∧...∧ f n

Правила:

1. переместить каждую селекцию внутрь декартова произведения, используя законы 1, 4, 6, 7, 8;
2. переместить каждую проекцию внутрь декартова произведения, используя законы 1, 3, 5, 9, 10;
3. по возможности скомбинировать каждый каскад селекции в одиночную селекцию и каждый каскад проекции в одиночную проекцию. Тогда всё можно будет сделать за один проход.

После выполнения этих трёх правил выражение Π A (σ F (R 1×...× R n)) преобразуется к виду:

Π A (σ F (Π A 1(σ f 1(R 1))×...×Π A n (σ f n (R n)))), здесь каждый Π A i (σ f i (R i)) - это подзапрос.

Суть в том, что сначала выполняются подзапросы, а они имеют намного меньшую размерность, чем исходная таблица, и время выполнения будет меньше, чем по исходной формуле Π A (σ F (R 1×...× R n)).

Логический план

Построение логического плана

Порядок построения:

1. запрос преобразуется в формулу реляционной алгебры;
2. выполняется преобразование (оптимизация) этой формулы.

Оператор SELECT (без агрегирования, группирования и удаления дубликатов) может быть представлен так:

Π A (σ F (R 1×...× R n)), где

от R 1 до R n - это декартово произведение отношений (таблиц), указанных за ключевым словом FROM;

σ F - это селекция кортежей декартова произведения в соответствии с условием, указанным за ключевым словом WHERE;

Π A - это проекция селекции на множество атрибутов A, указанных за ключевым словом SELECT

В чём суть такой логической оптимизации? Сначала надо выполнить декартово произведение, потом селекцию, потом проекцию - всё по порядку скобок в этом выражении. Потому что если таблица имеет большой размер, то это выражение будет выполняться очень долго.

Пример: найти фамилии поставщиков, поставляющих детали с названием "винт".

ρ =(S, P, SP)

SELECT фамилия

FROM S, P, SP

WHERE P.название = 'винт' AND

S.номер_поставки = SP.номер_поставки AND

SP.номер_детали = P.номер_детали;

Πфамилия(σ P. н="винт"∧ S. н−п= SP. н−п∧ SP. н−д= P. н−д(S × P × SP))

После преобразования и выделения подзапросов (как в описании, приведённом выше) получится выражение Π A (σ F (Π A i (σ f 2(R 1))×...×Π A n (σ f n (R n)))), которое можно представить в графическом виде - это и будет логический план выполнения запроса:

Получается, подзапросы можно выполнять параллельно, а это тоже уменьшает время выполнения всего запроса.

Пример:

Запрос найти значение остатков больше 1500 на счетах пользователя с кодом 3:

SELECT остаток

FROM R2

WHERE остаток > 1500 AND

номер_счёта IN(

                SELECT номер_счёта

                FROM R1

                WHERE код_пользователя = 3

              );

Этот запрос преобразуется сервером в неявном виде в формулу реляционной алгебры:

Πостаток(σ R 2.о>1500∧ R 1.к−п=3∧ R 1.н− c = R 2.н−с(R 1× R 2))

Теперь оптимизируем:

=4Πостаток(σ R 1.н− c = R 2.н−с(σ R 2.о>1500∧ R 1.к−п=3(R 1× R 2)))=6

=Πостаток(σ R 1.н− c = R 2.н−с(σ R 1.к−п=3(R 1)× σ R 2.о>1500(R 2)=5,2

=Πостаток(σ R 1.н− c = R 2.н−с(Πостаток, R 1.н−с, R 2.н−с(σ R 1.к−п=3(R 1)× σ R 2.о>1500(R 2))=9

=Πостаток(σ R 1.н− c = R 2.н−с(Π R 1.н−с(σ R 1.к−п=3(R 1))×Π R 2.н−с,остаток(σ R 2.о>1500(R 2))))

Полученное выражение - результат оптимизации. Можно построить логический план выполнения запроса.

 

Лекция №10 - Логический и физический план запроса

 

Оптимизация SQL-запросов

Логический план