ТОРА (9) - Лекция №14 - Оценки (продолжение): различия между версиями
ILobster (обсуждение | вклад) м (реструктуризация) |
|||
Строка 203: | Строка 203: | ||
:// поиск в массиме структур {{Формула|f=str[]}} экземпляра, который {{Формула|f=str[i].W = Q}} | :// поиск в массиме структур {{Формула|f=str[]}} экземпляра, который {{Формула|f=str[i].W = Q}} | ||
:печать{{Формула|f=(Q}}, " = ", {{Формула|f=str[i].X}}, " {{Формула|f=\bowtie}} ", {{Формула|f=str[ | :печать{{Формула|f=(Q}}, " = ", {{Формула|f=str[i].X}}, " {{Формула|f=\bowtie}} ", {{Формула|f=str[i].Y}}, " метод ", {{Формула|f=str[i].V.k)}} | ||
2) | 2) |
Текущая версия от 19:15, 5 февраля 2018
Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого Григорьева можно загрузить здесь.
Оптимизация SQL-запросов
Физический план
Методы соединения таблиц
Число кортежей, блоков и мощности атрибутов в соединениях
Справедливы для NLJ, SMJ и HJ.
1) количество кортежей в соединении:
- $$T(Q_1\bowtie Q_2) = \frac{T(Q_1)\cdot T(Q_2)}{max(I(Q_1, a), I(Q_2, a))}$$
2) числов блоков:
- $$B(Q_1\bowtie Q_2) = \Bigl\lceil\frac{T(Q_1\bowtie Q_2)}{JOIN}\Bigr\rceil$$ - верхние неполные квадратные скобки означают округление с избытком;
3) мощности атрибутов:
- атрибутов ($$a$$) в результирующей таблице:
- $$I(Q_1\bowtie Q_2, a) = min(I(Q_1, a), I(Q_2, a))$$
- остальных атрибутов ($$b$$):
- два варианта:
- $$I(Q_1\bowtie Q_2, b) = min(T(Q_1\bowtie Q_2, I(Q_1, b))$$, если $$b$$ - атрибут таблицы $$Q_1$$;
- $$I(Q_1\bowtie Q_2, b) = min(T(Q_1\bowtie Q_2, I(Q_2, b))$$, если $$b$$ - атрибут таблицы $$Q_2$$.
Алгоритмы для поиска физического плана
Алгоритмы описываются на псевдоязыке с заимствованиями из C++:
- комментарии обозначаются косыми:
// камент
- обращение к полям структуры через точку:
структура.поле
Алгоритм поиска физического плана с минимальной стоимостью (для левостороннего дерева)
Вход: логический план выполнения запроса с таблицами $$R_1 .. R_n$$ (декартово соединение таблиц).
Выход: квазиоптимальный (потому что рассматриваем левосторонние деревья) план выполнения запроса.
@НАЧАЛО АЛГОРИТМА
ДЛЯ $$i = 1,n$$
- $$AccessPlan(R_i)$$; // определение параметров подзапроса $$Q_i = \Pi_{A_i}(\Sigma_{f_i}(R_i))$$.
КОНЕЦ ДЛЯ
// поиск оптимального плана
ДЛЯ $$i = 2,n$$
- ДЛЯ всех подмножеств $$P\subset {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\in P$$
- $$JoinPlan(P - Q_j, Q_j)$$ // $$(P - Q_j)\bowtie Q_j$$
- КОНЕЦ ДЛЯ
- ДЛЯ всех таблиц $$Q_j\in P$$
- КОНЕЦ ДЛЯ
КОНЕЦ ДЛЯ
// вывод оптимального плана
$$OptPlanReturn({Q_1..Q_n})$$
@КОНЕЦ АЛГОРИТМА
Массив структур
Процедуры из алгоритма выше:
- $$AccessPlan()$$;
- $$JoinPlan()$$;
- $$OptPlanReturn()$$.
Процедуры алгоритма работают с массивом структур. Формат экземпляра структуры:
$$W$$ | $$X$$ | $$Y$$ | $$Z$$ | $$ZIO$$ | $$V$$ |
$$W$$:
- если мощность $$W > 1$$, то $$W\subset {Q_i}$$, $$W = X\bigcup Y$$;
- если мощность $$W = 1$$, то $$W$$ - это имя таблицы {Q_i}}}.
$$X$$:
- $$X\subset {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}$$, $$\varnothing$$, $$\varnothing$$ // $$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$$, " $$\bowtie$$ ", $$str[i].Y$$, " метод ", $$str[i].V.k)$$
2)
- // если поле $$str[i].X$$ пусто, то выйти из алгоритма
- // иначе рекурсивно вызываем сами себя, $$OptPlanReturn(str[i].X)$$ // вывод оптимального плана для левого аргумента соединения
3)
- $$OptPlanReturn(str[i].Y)$$ // вывод метода выбора записей из правого аргумента соединения
@КОНЕЦ АЛГОРИТМА