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

Оригинал всего раздела, посвящённого оптимизации 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$

КОНЕЦ ДЛЯ

КОНЕЦ ДЛЯ

КОНЕЦ ДЛЯ

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

$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)$ // вывод метода выбора записей из правого аргумента соединения

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