c1...ck - это атрибуты отношения R2

Πb1...bn,c1...ck(R1×R2) = Πb1...bn(R1)×Πc1...ck(R2)

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

Πa1...an(R1⋃R2)=Πa1...an(R1)⋃Πa1...an(R2)

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

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

Правила:

1. переместить каждую селекцию внутрь декартова произведения, используя законы 1, 4, 6, 7, 8;

2. переместить каждую проекцию внутрь декартова произведения, используя законы 1, 3, 5, 9, 10;

3. по возможности скомбинировать каждый каскад селекции в одиночную селекцию и каждый каскад проекции в одиночную проекцию. Тогда всё можно будет сделать за один проход.

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

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

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

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

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

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

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

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

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

ΠA(σF(R1×...×Rn)), где

от R1 до Rn - это декартово произведение отношений (таблиц), указанных за ключевым словом 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(ΠAi(σf2(R1))×...×ΠAn(σfn(Rn)))), которое можно представить в графическом виде - это и будет логический план выполнения запроса:

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

Пример:

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

SELECT остаток

FROM R2

WHERE остаток > 1500 AND

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

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

FROM R1

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

);

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

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

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

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

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

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

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

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

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

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

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

Порядок выполнения запроса на логическом уровне

Пример с предыдущей лекции: Πостаток(σR1.н−c=R2.н−с(ΠR1.н−с(σR1.к−п=3(R1))×ΠR2.н−с,остаток(σR2.о>1500(R2))))

Каждый из подзапросов - это промежуточные таблицы Q1 и Q2.

1)

2)

соединение Q1 и Q2 (естественное соединение):

Вот этот результат и передаётся от СУБД на рабочую станцию.

А теперь предположим, что таблицы R1 и R2 находятся на разных серверах. В этом случае, подзапросы Q1 и Q2 после оптимизации на сервере-оптимизаторе преобразуются в SELECT.

Q1:

SELECT R1.ном.сч

FROM R1

WHERE R1.код.польз = 3;

Q2:

SELECT R2.ном.сч, R2.ост

FROM R2

WHERE R2.ост > 1500;

Эти подзапросы направляются на сервера, где хранятся соответствующие таблицы, там они параллельно выполняются, результаты возвращаются серверу-оптимизатору, а от него - пользователю.

Физический план

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

При построении оптимального физического плана СУБД выполняет следующие действия:

1. Последовательно строится множество физических планов на основе логического плана. Эти физические планы отличаются следующим:

   1. методом выбора записей из исходных таблиц (методом реализации подзапросов);

   2. порядком соединения промежуточных таблиц Qi (комбинация вариантов соединения нескольких таблиц);

   3. методом соединения таблиц (вложенными циклами, сортировкой слияния или ещё как);

2. Для каждого физического плана оценивается его стоимость и выбирается план с наименьшей. В стоимости учитывается и процессорная составляющая, и составляющая времени ввода/вывода.

Методы выбора записей из исходной таблицы

Чтение всех записей и фильтрация

TableScan + Filter

Формула стоимости:

CostΣ=CCPU+CIO

CCPU=T(R)⋅Cfilter

CIO=B(R)⋅CB

здесь:

T(R) - общее количество записей в таблице R;

B(R) - число физических блоков в таблице R;

Cfilter - среднее время фильтрации одной записи;

CB - время чтения/записи одного блока на диск.

Чтение записей из индекса и фильтрация

IndexScan + Filter

Формула стоимости:

CostΣ=CCPU+CIO

CCPU=T(R)I(R,a)⋅Cfilter

CIO - как и в предыдущем методе, умножаем время чтения/записи на число записей в блоке индекса. Но тут два варианта:

1. для кластеризованного: CIO=B(Index(R,a))I(R,a)⋅CB+B(R)⋅kI(R,a)⋅CB. В кластеризованном индексе последовательность значений в индексе и в таблице совпадает;

2. для индекса без кластеризации CIO=B(Index(R,a))I(R,a)⋅CB+T(R)⋅kI(R,a)⋅CB. Последовательность в индексе и таблице не совпадает. Число в этом случае читаемых записей равно числу блоков. Или наоборот.

здесь:

T(R) - общее количество записей в таблице R;

B(R) - число физических блоков в таблице R;

I(R,a) - мощность индексируемого атрибута a таблицы R (число разных значений, исключая пустое множество);

B(Index(R,a)) - число блоков на листовом уровне индекса по атрибуту a;

Cfilter - среднее время фильтрации одной записи;

CB - время чтения/записи одного блока на диск;

k - мощность атрибута a в запросе (число разных значений, указанных в подзапросе y).

Определение k:

• k=1, если y: a=const;

• k=n, если y: a IN (C1...Cn), Ci=const;

• k= диапазон значений, если y: a>=C1 AND a<=C2;

• k= число атрибутов, удовлетворяющих образцу, если y: a LIKE 'чтонить'.

Отличие физического плана от логического

Логический план не указывает, как реализуются операции реляционной алгебры, а физический определяет, как они будут реализованы.

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

Пример физического плана

Данный физический план реализуется следующим образом;

1. для реализации подзапроса к R1 читается вся таблица, записи фильтруются по f1 и получаемая таблица является правым аргументов в операции соединения;

2. из таблицы R2 выделяется подусловие y для индексируемого атрибута, а потом выполняется чтение записей, удовлетворяющих этому условию. Полученные записи фильтруются по f2 и получаемая таблица является левым аргументом в операции соединения.

Как мы уже знаем, оптимизатор для каждого физического плана рассчитывает стоимость. Рассмотрим этот расчёт для данного примера: CostΣ=Cost(TableScan(R1),Filter(f1,ΠA1))+Cost(IndexScan(R2,y),Filter(f2,ΠA2))+Cost(⋈)

Каждая из Cost() учитывает и процессорную составляющую, и временную составляющую ввода-вывода.

Лекция №11 - Оценки

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

Физический план

Методы выбора записей из исходной таблицы

Оценка числа кортежей в промежуточной таблице

В таблице Q. Вычисляется по формуле:

Q=ΠA(σf(R))

T(Q)=T(R)⋅p

здесь:

Q - промежуточная таблица;

T(Q) - число кортежей в промежуточной таблице;

T(R) - число записей в исходной таблице R;

p - вероятность того, запись из таблицы R удовлетворяет условию F.

Расчёт p:

1. если f=F1⋂F2, то p=p1⋅p2;

2. если f=F1⋃F2, то p=p1+p2−p1⋅p2;

3. если f=F1¯¯¯¯, то p=1−p1.

Для i-ой вероятности:

pi=kI(R,a)

здесь:

k - мощность атрибута a в запросе;

I(R,a) - мощность атрибута a в таблице R.

Пример

Допустим, T(R)=1000, I(R,a)=5, I(R,b)=10, I(R,c)=2, где a,b,c - положительные натуральные числа.

И f=(a<3 OR b≥5) AND c=2

Найти T(Q).

Обозначим:

• a<3 как F1;

• b≥5 как F2;

• f=(a<3 OR b≥5) как F3;

• c=2 как F4.

1)

F1⋃F2=F3

p3=p1+p2−p1⋅p2=25+610−25⋅610=0.76

2)

f=F3⋂F4

p=p3⋅p4=0.76⋅12=0.38 - это вероятность того, что запись из R удовлетворяет условию f.

3)

T(Q)=1000⋅0.38=380

Оценка количества блоков

Q=ΠA(σf(R))

B(Q)=[T(Q)LB] - скобки обзначают, что огругление с избытком.

здесь:

T(Q) - прогнозируемое число записей в подзапросе;

LB - длина блока (число записей в блоке) с учётом ΠA.

Порядок соединения промежуточных таблиц

Деревья соединения

Используются деревья соединения, которые бывают трёх видов:

• левостороннее;

• кустовое, ветвящееся;

• правостороннее.

Левостороннее

Предположим, соединяются таблицы R,S,T,U: