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

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