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

Материал из Кафедра ИУ5 МГТУ им. Н.Э.Баумана - студенческое сообщество
Перейти к: навигация, поиск

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

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