ТОРА (9) - Лекция №15 - Пример оценки

Этот конспект ещё не дописан. Здесь не хватает:    - описаний формул. А также в некоторых формулах должны быть ошибки;    - графического представления оптимального плана.

...начало

Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого Григорьева можно загрузить здесь.

Оптимизация SQL-запросов

Методы соединения таблиц

Алгоритмы для поиска физического плана

Пример оценки физического плана

Исходные данные:

1) количество записей в таблице $T(R_1)$ = 10000, количество записей в таблице $T(R_2)$ = 100000;

2) количество записей в одном блоке таблицы $L(R_1) = L(R_2)$ = 100, количество записей в соединении $L_{JOIN}$ = 1000;

3) количество записей в блоке индекса код_пользователя {{Формула|f=L} = 200, количество записей в блоке индекса номер_счёта {{Формула|f=L} = 200;

Примечание: записи исходных таблиц могут читаться в сортированном виде по своим индексированным атрибутам. Записи в таблице $R_1$ сгруппированы по атрибуту код_пользователя (кластеризованный индекс), а в таблице $R_2$ не сгруппированы.

4) мощность атрибутов:

• $R_1$, код_пользователя 5000;
• $R_1$, номер_счёта 10000;
• $R_2$, номер_счёта 100000
• $R_2$, остаток - неизвестно.

5) тут почему-то пусто

6) $b$ = 10, $C_{COMP} = C_{MOVE} = C_{filter} = 0.01$ мс, $C_B = 10$ мс.

Для построение оптимального физического плана используется алгоритм динамического программирования (из предыдущей лекции).

Алгоритм:

1) $AccessPlan$

а) $R_1$ - таблица пользователи;

$j = 1$, чтение всей таблицы

$C_1 = C_{CPU1} + C_{I/O1} = T(R_1)\cdot C_{filter} + B(R_1)\cdot C_B = 10000\cdot 0.01 + \frac{10000}{100}\cdot 10 = 1100$ мс

$j = 2$ - индекс по атрибуту код_пользователя

$C_2 = C_{CPU2} + C_{I/O2} = \frac{T(R_1)\cdot K}{I(R_1, a)}\cdot C_{filter} + \frac{B(Index(a))\cdot k}{I(R_1, a)} \cdot C_b + \frac{B(R_2)\cdot k}{I(R_1, a)} =$

$=\frac{10000\cdot 1}{5000}\cdot 0.01 + \frac{(10000/200)\cdot 1}{5000}\cdot 10 + \frac{10000/100\cdot 1}{5000}\cdot 10 = 0.02 + 0.3 = 0.32$ мс

$С = min(С_1, С_2) = 0.32$ мс

$С_{I/O} = C_{I/O2} = 0.3$ мс

$T(Q_1) = T(R_2)\cdot P_{код\_ пользователя = 3} = T(R_2)\cdot \frac{k}{I(R_1, a)} = 10000 \cdot 1/5000 = 2$

$B(Q_1) = \lceil\frac{T(Q_1)}{L(R_1)\cdot 10}\rceil = \lceil\frac{2}{100\cdot 10}\rceil = 1$

$str[1] = \{\{Q_1\}, \varnothing, \varnothing, 0.32, 0.3, \{2, 1, \{2\}, 2\}\}$

б) $R_2$ - таблица счёт.

$j = 1$

$C_1 = 100000\cdot 0.01 + \frac{100000}{100}\cdot 10 = 11000$ мс

$j = 2$

$C = C_1 = 11000$ мс

$C_{I/O} = C_{I/O1} = 10000$ мс

$T(Q_2) = T(R_2)\cdot P_{R_2.остаток > 1500} = 100000\cdot 1/3 = 33000$, вероятность принята равной $1/3$, так как по условию эта мощность неизвестна

$B(Q_2) = \lceil\frac{T(Q_2)}{L(R_2)\cdot 10}\rceil = \lceil\frac{33000}{100\cdot 10}\rceil = 33$

$str[2] = \{\{Q_2\}, \varnothing, \varnothing, 11000, 10000, \{33000, 33, \{33000\}, 1\}\}$

2) $JoinPlan$

$m_1 = 1$, $m_2 = 2$ - номера экземпляров структур, таких, что $str[m_1].W = Q_1$ и $str[m_2].W = Q_2$

а)

$i = 1$, NLJ

$C_1 = C_{CPU1} + C_{I/O1} = T(Q_1)\cdot T(Q_2)\cdot C_{COMP} + \lfloor\frac{B(Q_1)}{b}\rfloor\cdot C_{I/O}(Q_2) = 2\cdot 33000\cdot 0.01 + \lfloor\frac{1}{10}\rfloor\cdot 10000 = 660$ мс

$i = 2$, SMJ

таблица $Q_2$ уже отсортирована по номер_счёта, так как имеется индекс по номеру счёта

$С_2 = С_{CPU2} + C_{I/O2} = C^{SORT}_{CPU}(Q_1) + С^{JOIN}_{CPU}(Q_1, Q_2) + C^{SORT}_{I/O}(Q_1) + C^{JOIN}_{I/O}(Q_1, Q_2) =$

$= 2\cdot \log_2\frac{2}{\lfloor 1/10\rfloor}\cdot (0.01 + 0.01) + (\log_{10}1 - 1)\cdot 2\cdot (10\cdot 0.01 + 0.01) + ((\frac{33000}{33000} + 2\cdot 2 +$

$+ 33000\cdot(1 - \frac{2}{33000}))\cdot 0.01 + (2\cdot 1\cdot \log_{10}\cdot 1)\cdot 10 + (1 + 0)\cdot 10 = 340$ мс

$C = min(C_1, C_2) = 340$

$C = str[1].Z + str[2].Z + C = 0.32 + 11000 + 340 = 11340.32$ мс

$C_{I/O} = str[1].ZIO + str[2].ZIO + C_{I/O2} = 0.3 + 10000 + 10 = 10010.3$ мс

$T(Q_1\bowtie Q_2) = \frac{T(Q_1)\cdot T(Q_2)}{max(I(Q_1, a), I(Q_2, a))} = \frac{2\cdot 33000}{max(2, 33000)} =2$

$B(Q_1\bowtie Q_2) = \lceil\frac{2}{1000}\rceil= 1$

$I(Q_1\bowtie Q_2, a) = min(I(Q_1, a), I(Q_2, a)) = min(2, 33000) = 2$

$str[3] = \{\{Q_1, Q_2\}, \{Q_1\}, \{Q_2\}, 11340, 10010, \{2, 1, \{2\}, 2\}\}$

б)

структура остаётся такая же

3) $OptPlanReturn$ - вывод оптимального плана и представление этого плана в графическом виде.

1) $(Q_1, Q_2) = Q_1\bowtie Q_2$

2) $Q_1 = (IndexScan() + Filter())$

3) $Q_2 = (TableScan() + Filter())$