Отличие от методов NLJ и SMJ

Метод хешированного соединения имеет важную особенность. В методах NLJ или SMJ соединяемые таблицы должны уже храниться на сервере перед выполнением соединения. А в этом методе соединение таблиц может выполняться асинхронно, по мере поступления записей с других серверов.

На серверах 1 и 2 выполняются подзапросы, а на сервере 0 выполняется соединение.

Предположим, с сервера 2 на сервер 0 поступила очередная запись из таблицы S. При этом СУБД на сервере 0 выполняет следующие действия:

1. вычисляется хеш-функция для атрибута соединения;
2. значение атрибута соединения сравнивается со значениями атрибутов соединения из раздела R 1. Если есть совпадения, то выводятся результаты соединения;
3. запись сохраняется в разделе S i.
4. и так далее.

 

Лекция №14 - Оценки (продолжение)

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

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

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

Число кортежей, блоков и мощности атрибутов в соединениях

Справедливы для NLJ, SMJ и HJ.

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

T (Q 1⋈ Q 2)= T (Q 1)⋅ T (Q 2) max (I (Q 1, a), I (Q 2, a))

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

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

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

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

I (Q 1⋈ Q 2, a)= min (I (Q 1, a), I (Q 2, a))

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

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

· I (Q 1⋈ Q 2, b)= min (T (Q 1⋈ Q 2, I (Q 1, b)), если b - атрибут таблицы Q 1;

· I (Q 1⋈ Q 2, b)= min (T (Q 1⋈ Q 2, I (Q 2, b)), если b - атрибут таблицы Q 2.

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

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

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

// камент

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

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

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

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

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

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

ДЛЯ i =1, n

AccessPlan (R i); // определение параметров подзапроса Q i =Π A i (Σ f i (R i)).

КОНЕЦ ДЛЯ

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

ДЛЯ i =2, n

ДЛЯ всех подмножеств P ⊂ Q 1.. Q n,

// для i =2

// P =(Q 1, Q 2), P =(Q 2, Q 3), P =(Q 1, Q 3)

// для i =3

// P =(Q 1, Q 2, Q 3) и так же все варианты комбинаций

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

JoinPlan (P − Q j, Q j) // (P − Q j)⋈ Q j

КОНЕЦ ДЛЯ

КОНЕЦ ДЛЯ

КОНЕЦ ДЛЯ

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

OptPlanReturn (Q 1.. Q n)

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

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

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

• AccessPlan ();
• JoinPlan ();
• OptPlanReturn ().

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

W

X

Y

Z

ZIO

V

W:

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

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

X:

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

Y:

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

Z:

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

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

ZIO:

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

V:

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

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

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

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

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

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

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

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

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

AccessPlan()

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

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

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

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

// j =1 - TableScan

// j =2 - IndexScan

ДЛЯ i =1,2

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

КОНЕЦ ДЛЯ

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

С= min (C 1, C 2) // здесь C = C k

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

str [ i ]=

{

Q i, ∅, ∅ // W, X, Y

C, C I / O k // Z, ZIO

T (Q i), B (Q i), min (T (Q i), I (R i, A i)), k // V

}

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

JoinPlan()

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

Выход: str [ n ].

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

1)

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

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

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

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

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

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

2)

ДЛЯ i =1,3

C i = C CPU i + C I / O i // для разных i разные формулы из предыдущих лекций

КОНЕЦ ДЛЯ

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

C = str [ m 1]. Z + str [ m 2]. Z + C

3)

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

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

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

str [ n ]=

{

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

C, C I / O k // Z, ZIO

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

}

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

OptPlanReturn()

Вход: список таблиц Q i = Q 1.. Q n

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

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

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 (R 1) = 10000, количество записей в таблице T (R 2) = 100000;

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

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

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

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

• R 1, код_пользователя 5000;
• R 1, номер_счёта 10000;
• R 2, номер_счёта 100000
• R 2, остаток - неизвестно.

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

6) b = 10, C COMP = C MOVE = C filter =0.01 мс, C B =10 мс.

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

Алгоритм:

1) AccessPlan

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

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

C 1= C CPU 1+ C I / O 1= T (R 1)⋅ C filter + B (R 1)⋅ C B =10000⋅0.01+10000100⋅10=1100 мс

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

C 2= C CPU 2+ C I / O 2= T (R 1)⋅ KI (R 1, a)⋅ C filter + B (Index (a))⋅ kI (R 1, a)⋅ C b + B (R 2)⋅ kI (R 1, 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 = C I / O 2=0.3 мс

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

B (Q 1)=⌈ T (Q 1) L (R 1)⋅10⌉=⌈2100⋅10⌉=1

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

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

j =1

C 1=100000⋅0.01+100000100⋅10=11000 мс

j =2

C = C 1=11000 мс

C I / O = C I / O 1=10000 мс

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

B (Q 2)=⌈ T (Q 2) L (R 2)⋅10⌉=⌈33000100⋅10⌉=33

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

2) JoinPlan

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

а)

i =1, NLJ

C 1= C CPU 1+ C I / O 1= T (Q 1)⋅ T (Q 2)⋅ C COMP +⌊ B (Q 1) b ⌋⋅ C I / O (Q 2)=2⋅33000⋅0.01+⌊110⌋⋅10000=660 мс

i =2, SMJ

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

С2=С CPU 2+ C I / O 2= C SORTCPU (Q 1)+С JOINCPU (Q 1, Q 2)+ C SORTI / O (Q 1)+ C JOINI / O (Q 1, Q 2)=

=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 (C 1, C 2)=340

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

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

T (Q 1⋈ Q 2)= T (Q 1)⋅ T (Q 2) max (I (Q 1, a), I (Q 2, a))=2⋅33000 max (2,33000)=2

B (Q 1⋈ Q 2)=⌈21000⌉=1

I (Q 1⋈ Q 2, a)= min (I (Q 1, a), I (Q 2, a))= min (2,33000)=2

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

б)

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

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

1) (Q 1, Q 2)= Q 1⋈ Q 2

2) Q 1=(IndexScan ()+ Filter ())

3) Q 2=(TableScan ()+ Filter ())