1) количество кортежей в соединении:

T(Q1⋈Q2)=T(Q1)⋅T(Q2)max(I(Q1,a),I(Q2,a))

2) числов блоков:

B(Q1⋈Q2)=⌈T(Q1⋈Q2)JOIN⌉ - верхние неполные квадратные скобки означают округление с избытком;

3) мощности атрибутов:

• атрибутов (a) в результирующей таблице:

I(Q1⋈Q2,a)=min(I(Q1,a),I(Q2,a))

• остальных атрибутов (b):

два варианта:

• I(Q1⋈Q2,b)=min(T(Q1⋈Q2,I(Q1,b)), если b - атрибут таблицы Q1;

• I(Q1⋈Q2,b)=min(T(Q1⋈Q2,I(Q2,b)), если b - атрибут таблицы Q2.

Алгоритмы для поиска физического плана

Алгоритмы описываются на псевдоязыке с заимствованиями из C++:

• комментарии обозначаются косыми:

// камент

• обращение к полям структуры через точку:

структура.поле

Алгоритм поиска физического плана с минимальной стоимостью (для левостороннего дерева)

Вход: логический план выполнения запроса с таблицами R1..Rn (декартово соединение таблиц).

Выход: квазиоптимальный (потому что рассматриваем левосторонние деревья) план выполнения запроса.

@НАЧАЛО АЛГОРИТМА

ДЛЯ i=1,n

AccessPlan(Ri); // определение параметров подзапроса Qi=ΠAi(Σfi(Ri)).

КОНЕЦ ДЛЯ

// поиск оптимального плана

ДЛЯ i=2,n

ДЛЯ всех подмножеств P⊂Q1..Qn,

// для i=2

// P=(Q1,Q2), P=(Q2,Q3), P=(Q1,Q3)

// для i=3

// P=(Q1,Q2,Q3) и так же все варианты комбинаций

ДЛЯ всех таблиц Qj∈P

JoinPlan(P−Qj,Qj) // (P−Qj)⋈Qj

КОНЕЦ ДЛЯ

КОНЕЦ ДЛЯ

КОНЕЦ ДЛЯ

// вывод оптимального плана

OptPlanReturn(Q1..Qn)

@КОНЕЦ АЛГОРИТМА

Массив структур

Процедуры из алгоритма выше:

• AccessPlan();

• JoinPlan();

• OptPlanReturn().

Процедуры алгоритма работают с массивом структур. Формат экземпляра структуры:

W

X

Y

Z

ZIO

V

W:

если мощность W>1, то W⊂Qi, W=X⋃Y;

если мощность W=1, то W - это имя таблицы {Q_i}}}.

X:

X⊂Qi, которые были использованы в качестве левого аргумента соединения.

Y:

имя таблицы Qi, которая была использована в качестве правого аргумента соединения. Если мощность W=1, то X и Y пустые.

Z:

если W>1, Z - текущая стоимость выполнения плана, включающая стоимость выполнения подзапросов и промежуточных соединений;

если W=1, Z - оценка времени выполнения(?) Qi.

ZIO:

составляющая Z, касающаяся ввода/вывода.

V:

опции. Включает в себя:

1) число записей:

• если мощность W>1, то T(W) - число прогнозируемых записей;

• если мощность W=1, то T(Qi) - оценка числа записей в подзапросе;

2) B(W) - прогнозируемое число блоков;

3) I(W,Ai) - мощности атрибутов, по которым было выполнено или выполняется соединение;

4) идентификатор:

• если мощность W>1, то k - идентификатор метода соединения таблиц;

• если мощность W=1, то k - идентификатор метода выбора записей из исходных таблиц.

AccessPlan()

Вход: Ri - имя исходной таблицы.

Выход: str[i] - заполненный экземпляр структуры (описанной выше).

@НАЧАЛО АЛГОРИТМА

// оценка стоимости выбора записей из Ri для различных методов

// j=1 - TableScan

// j=2 - IndexScan

ДЛЯ i=1,2

Cj=CCPU+CI/O // для разных j разные формулы из прошлых лекций

КОНЕЦ ДЛЯ

// определение оптимального метода выбора записей из Ri

С=min(C1,C2) // здесь C=Ck

// заполнение экземпляра str[i]

str[i]=

{

Qi, ∅, ∅ // W, X, Y

C, CI/Ok // Z, ZIO

T(Qi),B(Qi),min(T(Qi),I(Ri,Ai)),k // V

}

@КОНЕЦ АЛГОРИТМА

JoinPlan()

Вход: R=(P−Qj), S=Q.

Выход: str[n].

@НАЧАЛО АЛГОРИТМА

1)

// поиск в массиве структур str[] номеров экземпляров m1 и m2, для которых str[m1].W=R и str[m2].W=S

// оценка стоимости соединения для различных методов

// если i=1, то NLJ

// если i=2, то SMJ

// если i=3, то HJ

// k - выбор оптимального из этих трёх

2)

ДЛЯ i=1,3

Ci=CCPUi+CI/Oi // для разных i разные формулы из предыдущих лекций

КОНЕЦ ДЛЯ

C=min(C1,C2) // стоимость соединения R и S

C=str[m1].Z+str[m2].Z+C

3)

// поиск str[n].W=P

// а) если такого экземпляра не существует, то заполнить очередной пустой экземпляр n.

// б) если такой экземпляр найден, то сравнить стоимость выполнения плана. И если str[n].Z>C, то перезаписать экземпляр n.

str[n]=

{

P, R, S // W, X, Y

C, CI/Ok // Z, ZIO

T(P),B(P),I(P,Ai)i,k // V

}

@КОНЕЦ АЛГОРИТМА

OptPlanReturn()

Вход: список таблиц Qi=Q1..Qn

Выход: вывод оптимального плана.

@НАЧАЛО АЛГОРИТМА

1)

// поиск в массиме структур str[] экземпляра, который str[i].W=Q

печать(Q, " = ", str[i].X, " ⋈ ", str[y].Y, " метод ", str[i].V.k)

2)

// если поле str[i].X пусто, то выйти из алгоритма

// иначе рекурсивно вызываем сами себя, OptPlanReturn(str[i].X) // вывод оптимального плана для левого аргумента соединения

3)

OptPlanReturn(str[i].Y) // вывод метода выбора записей из правого аргумента соединения

@КОНЕЦ АЛГОРИТМА

Лекция №15 - Пример оценки

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

Методы соединения таблиц

Алгоритмы для поиска физического плана

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

Исходные данные:

1) количество записей в таблице T(R1) = 10000, количество записей в таблице T(R2) = 100000;

2) количество записей в одном блоке таблицы L(R1)=L(R2) = 100, количество записей в соединении LJOIN = 1000;

3) количество записей в блоке индекса код_пользователя {{Формула|f=L} = 200, количество записей в блоке индекса номер_счёта {{Формула|f=L} = 200;

Примечание: записи исходных таблиц могут читаться в сортированном виде по своим индексированным атрибутам. Записи в таблице R1 сгруппированы по атрибуту код_пользователя (кластеризованный индекс), а в таблице R2 не сгруппированы.

4) мощность атрибутов:

• R1, код_пользователя 5000;

• R1, номер_счёта 10000;

• R2, номер_счёта 100000

• R2, остаток - неизвестно.

5) тут почему-то пусто

6) b = 10, CCOMP=CMOVE=Cfilter=0.01 мс, CB=10 мс.

Для построение оптимального физического плана используется алгоритм динамического программирования (из предыдущей лекции).

Алгоритм:

1) AccessPlan

а) R1 - таблица пользователи;

j=1, чтение всей таблицы

C1=CCPU1+CI/O1=T(R1)⋅Cfilter+B(R1)⋅CB=10000⋅0.01+10000100⋅10=1100 мс

j=2 - индекс по атрибуту код_пользователя

C2=CCPU2+CI/O2=T(R1)⋅KI(R1,a)⋅Cfilter+B(Index(a))⋅kI(R1,a)⋅Cb+B(R2)⋅kI(R1,a)=

=10000⋅15000⋅0.01+(10000/200)⋅15000⋅10+10000/100⋅15000⋅10=0.02+0.3=0.32 мс

С=min(С1,С2)=0.32 мс

СI/O=CI/O2=0.3 мс

T(Q1)=T(R2)⋅Pкод_пользователя=3=T(R2)⋅kI(R1,a)=10000⋅1/5000=2

B(Q1)=⌈T(Q1)L(R1)⋅10⌉=⌈2100⋅10⌉=1

str[1]={{Q1},∅,∅,0.32,0.3,{2,1,{2},2}}

б) R2 - таблица счёт.

j=1

C1=100000⋅0.01+100000100⋅10=11000 мс

j=2

C=C1=11000 мс

CI/O=CI/O1=10000 мс

T(Q2)=T(R2)⋅PR2.остаток>1500=100000⋅1/3=33000, вероятность принята равной 1/3, так как по условию эта мощность неизвестна

B(Q2)=⌈T(Q2)L(R2)⋅10⌉=⌈33000100⋅10⌉=33

str[2]={{Q2},∅,∅,11000,10000,{33000,33,{33000},1}}

2) JoinPlan

m1=1, m2=2 - номера экземпляров структур, таких, что str[m1].W=Q1 и str[m2].W=Q2

а)

i=1, NLJ

C1=CCPU1+CI/O1=T(Q1)⋅T(Q2)⋅CCOMP+⌊B(Q1)b⌋⋅CI/O(Q2)=2⋅33000⋅0.01+⌊110⌋⋅10000=660 мс

i=2, SMJ

таблица Q2 уже отсортирована по номер_счёта, так как имеется индекс по номеру счёта

С2=СCPU2+CI/O2=CSORTCPU(Q1)+СJOINCPU(Q1,Q2)+CSORTI/O(Q1)+CJOINI/O(Q1,Q2)=

=2⋅log22⌊1/10⌋⋅(0.01+0.01)+(log101−1)⋅2⋅(10⋅0.01+0.01)+((3300033000+2⋅2+

+33000⋅(1−233000))⋅0.01+(2⋅1⋅log10⋅1)⋅10+(1+0)⋅10=340 мс

C=min(C1,C2)=340

C=str[1].Z+str[2].Z+C=0.32+11000+340=11340.32 мс

CI/O=str[1].ZIO+str[2].ZIO+CI/O2=0.3+10000+10=10010.3 мс

T(Q1⋈Q2)=T(Q1)⋅T(Q2)max(I(Q1,a),I(Q2,a))=2⋅33000max(2,33000)=2

B(Q1⋈Q2)=⌈21000⌉=1

I(Q1⋈Q2,a)=min(I(Q1,a),I(Q2,a))=min(2,33000)=2

str[3]={{Q1,Q2},{Q1},{Q2},11340,10010,{2,1,{2},2}}

б)

структура остаётся такая же

3) OptPlanReturn - вывод оптимального плана и представление этого плана в графическом виде.

1) (Q1,Q2)=Q1⋈Q2

2) Q1=(IndexScan()+Filter())

3) Q2=(TableScan()+Filter())

68