ТОРА (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())$$