Лекция №9 - Оптимизация запросов

 

Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого Григорьева можно загрузить здесь.

 

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

Запрос, поступающий в СУБД, подвергается оптимизации с целью уменьшения времени его выполнения.

Шаги оптимизатора:

1. строится логический план выполнения запроса (дерево логических операций);
2. на основе логического плана строится физический план выполнения запроса (дерево физических операций);
3. реализация этого физического плана.

Законы реляционной алгебры

Закон коммутативности декартова произведения отношений

R 1× R 2= R 2× R 1, здесь и далее R 1 и R 2 - экземпляры отношений.

Закон ассоциативности декартова произведения

(R 1× R 2)× R 3= R 1×(R 2× R 3)

Закон каскада проекций

Допустим, (a 1... an)⊆(b 1... bn), ai, bi - это атрибуты отношения R

тогда Π a 1... an (Π b 1... bn (R))=Π a 1... an (R)

Закон каскада селекций

Допустим, F = f 1∧ f 2

тогда σF (R)= σf 1(σf 2(R))

Закон перестановки проекции и селекции

1)

Допустим, в условия поиска F входят атрибуты только из множества a 1... an

тогда Π a 1... an (σF (R))= σF (Π a 1... an (R))

2)

Допустим, в условия поиска F входят атрибуты не только из множества a 1... an, но и из b 1... bn

тогда Π a 1... an (σF (R))=Π a 1... an (σF (Π a 1... an, b 1... bn (R)))

Селекция декартова произведения

Отношение f 1 содержит атрибуты только из отношения R 1

тогда σf 1(R 1× R 2)= σf 1(R 1)× R 2

Следствие:

пусть F = f 1∧ f 2 и в f 1 входят атрибуты R 1, а в f 2 входят из R 2,

тогда σF (R 1× R 2)= σf 1(R 1)× σf 2(R 2)

Доказательство:

σf 1∧ f 2(R 1× R 2)= σf 1(σf 2(R 1× R 2))= σf 1(σf 2(R 2× R 1))=

= σf 1(R 1× σf 2(R 2))= σf 1(R 1)× σf 2(R 2)

Закон перестановки селекции и объединения

σF (R 1⋃ R 2)= σF (R 1)⋃ σF (R 2)

Закон перестановки селекции и разности отношений

σF (R 1− R 2)= σF (R 1)− σF (R 2)

Закон перестановки проекции и декартова произведения

b 1... bn - это атрибуты отношения R 1

c 1... ck - это атрибуты отношения R 2

Π b 1... bn, c 1... ck (R 1× R 2) = Π b 1... bn (R 1)×Π c 1... ck (R 2)

Закон перестановки проекции и объединения

Π a 1... an (R 1⋃ R 2)=Π a 1... an (R 1)⋃Π a 1... an (R 2)

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

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

Правила:

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

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

Π A (σF (Π A 1(σf 1(R 1))×...×Π An (σfn (Rn)))), здесь каждый Π Ai (σfi (Ri)) - это подзапрос.

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

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