- •Оптимизация sql-запросов
- •Последовательность оптимизации запросов и используемые законы реляционной алгебры
- •Основные шаги оптимизации
- •Законы реляционной алгебры
- •Построение логического плана
- •Преобразование запроса в формулу реляционной алгебры
- •Оптимизация формулы реляционной алгебры
- •Иллюстрация логической оптимизации
- •Пример построения логического плана
- •Оптимизация запроса
- •Порядок выполнения запроса на логическом уровне
- •Построение физического плана
- •Шаги построения физического плана
- •Отличие физического плана от логического
- •Методы выбора записей из исходной таблицы
- •1. Чтение всех записей таблицы и их фильтрация.
- •2. Чтение записей с помощью индекса и их фильтрация.
- •Оценка числа кортежей в промежуточной таблице q
- •Оценка числа блоков в промежуточной таблице q
- •Порядок соединения таблиц
- •Левостороннее дерево соединений
- •Кустовое дерево соединений
- •Правостороннее дерево соединений
- •Методы соединения таблиц
- •Метод вложенных циклов (nlj – Nested Loop Join)
- •Метод сортировки-слияния (smj – Sort Merge Join)
- •Метод хешированного соединения (hj – Hash Join)
- •Число кортежей, блоков и мощности атрибутов в соединении
- •Поиск физического плана с минимальной стоимостью
- •Алгоритм поиска для левостороннего дерева соединений
- •Формат экземпляра структуры данных
- •Спецификации процедуры AccessPlan
- •Спецификации процедуры JoinPlan
- •Спецификации процедуры OptPlanReturn
- •Пример построения оптимального физического плана
- •Логический план
- •Алгоритм поиска оптимального физического плана
- •Определение метода выбора записей из исходной таблицы r1
- •Определение метода выбора записей из исходной таблицы r2
- •Оценка соединения q1 и q2 методом nlj
- •Оценка соединения q1 и q2 методом smj
- •Выбор метода соединения q1 и q2 и заполнение структуры
- •Оценка и выбор метода соединения q2 и q1
- •Вывод физического плана
Алгоритм поиска оптимального физического плана
Ниже приведена последовательность расчётов.
Определение :
1.Определение метода выбора записей из исходной таблицы R1
(Пользователь):
AccessPlan(R1) (см. п. 1.7.3).
2. Определение метода выбора записей из исходной таблицы R2
(Счёт):
AccessPlan(R2) (см. п. 1.7.3).
Определение метода и порядка соединения :
3. Оценка соединения Q1 и Q2 методом NLJ:
в JoinPlan(Q1, Q2) (см. п. 1.7.4).
4. Оценка соединения Q1 и Q2 методом SMJ:
в JoinPlan(Q1, Q2) (см. п. 1.7.4).
5. Выбор метода соединения Q1 и Q2 и заполнение структуры:
в JoinPlan(Q1, Q2) (см. п. 1.7.4).
6. Оценка и выбор метода соединения Q2 и Q1 (по аналогии с
пунктами 3 - 4), сравнение вариантов:
JoinPlan(Q2, Q1) (см. п. 1.7.4).
Вывод оптимального физического плана:
7. Вывод физического плана:
OptPlanReturn({Q1, Q2}) (см. п. 1.7.5).
8. Представление физического плана в графическом виде.
Определение метода выбора записей из исходной таблицы r1
Алгоритм AccessPlan (см. п. 1.7.3) для таблицы R1 ("Пользователь"):
1. j = 1 – чтение всей таблицы (формулы (5.4)):
2. j = 2 – использование индекса по атрибуту "код_пользователя" (формулы (5.5) и (5.6), здесь "а" – "код_пользователя"):
C = C2 = 0,32 мс – минимальная стоимость.
CI/O = CI/O2 = 0,3 мс – составляющая ввода-вывода.
(п. 1.4.4).
(п. 1.4.5).
При вычислении B(Q1) полагаем, что число записей в блоке проекции πR1.номер_счета в 10 раз больше, чем в блоке таблицы R1 .
Заполнение структуры str[1] (п. 1.7.2):
str[1] = {{Q1}, Ø, Ø, 0.32, 0.3, // W, X, Y, Z, ZIO
{2, 1, {2}, 2} } // V: {T(Q1), B(Q1), {min(T(Q1),
// I(R1,номер_счёта))}, k }
Определение метода выбора записей из исходной таблицы r2
Алгоритм AccessPlan (см. п. 1.7.3) для таблицы R2 ("Счёт"):
1. j = 1 – чтение всей таблицы (формулы (5.4)):
2. j = 2 – чтения по индексу нет, так как нет индекса по атрибуту "Остаток" (см. запрос Q2 - п. 1.8.1).
C = C1 = 11000 мс .
CI/O = CI/O1 = 10000 мс .
//При вычислении T(Q2) вероятность принята равной 1/3, поскольку
//мощность атрибута "Остаток" в таблице R2 неизвестна.
(см. п. 1.4.4).
(см. п. 1.4.5).
Заполнение структуры str[2] (п. 1.7.2):
str[2] ={{Q2}, Ø, Ø, 11000, 10000, // W, X, Y, Z, ZIO
{33000, 33, {33000}, 1}} //V:{T(Q2),B(Q2),
//{min(T(Q2),I(R2,номер счёта))},k}
Оценка соединения q1 и q2 методом nlj
В алгоритме динамического программирования (см. п. 1.7.1):
n = 2, i = 2, P = (Q1, Q2), Qj = Q2 (параметры трёх вложенных циклов).
В JoinPlan (Q1, Q2) (см. п. 1.7.4):
R = P – Q2 = Q1, S = Q2 , "а" – атрибут "номер_счета".
Алгоритм:
m1 = 1, m2 = 2 // номера экземпляров в структуре str, т.к.
// str[m1=1].W= Q1 и str[m2=2].W= Q2
// Оценка стоимости соединения R и S методом NLJ, i=1
// (формулы (5.8), для оценки используются данные из str[1],
// str[2] - см. пункты 1.8.3 и 1.8.4):