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

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