ТОРА (9) - Лекция №10 - Логический и физический план запроса

Материал из Кафедра ИУ5 МГТУ им. Н.Э.Баумана - студенческое сообщество
Перейти к: навигация, поиск

...начало

Arrow left.png

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

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

Логический план

Порядок выполнения запроса на логическом уровне

Пример с предыдущей лекции: $\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}($$\Pi_{R_1.н-с}(\sigma_{R_1.к-п=3}(R_1))$$\times$$\Pi_{R_2.н-с, остаток}(\sigma_{R_2.о>1500}(R_2))$$))$

Каждый из подзапросов - это промежуточные таблицы $Q_1$ и $Q_2$.

1)

$Q_1$:
102
$Q_2$:
101 2000
102 3000

2)

соединение $Q_1$ и $Q_2$ (естественное соединение):
декартово произведение:
$R_{1_{ном.сч} }$ $R_{2_{ном.сч} }$ $R_{2_{ост} }$
102 101 2000
102 102 3000
соединение:
$R_{1_{ном.сч} }$ $R_{2_{ном.сч} }$ $R_{2_{ост} }$
102 102 3000
проекция:
Остаток
3000

Вот этот результат и передаётся от СУБД на рабочую станцию.

А теперь предположим, что таблицы $R_1$ и $R_2$ находятся на разных серверах. В этом случае, подзапросы $Q_1$ и $Q_2$ после оптимизации на сервере-оптимизаторе преобразуются в SELECT.

$Q_1$:

SELECT R1.ном.сч
FROM R1
WHERE R1.код.польз = 3;

$Q_2$:

SELECT R2.ном.сч, R2.ост
FROM R2
WHERE R2.ост > 1500;

Эти подзапросы направляются на сервера, где хранятся соответствующие таблицы, там они параллельно выполняются, результаты возвращаются серверу-оптимизатору, а от него - пользователю.

Физический план

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

При построении оптимального физического плана СУБД выполняет следующие действия:

  1. Последовательно строится множество физических планов на основе логического плана. Эти физические планы отличаются следующим:
    1. методом выбора записей из исходных таблиц (методом реализации подзапросов);
    2. порядком соединения промежуточных таблиц $Q_i$ (комбинация вариантов соединения нескольких таблиц);
    3. методом соединения таблиц (вложенными циклами, сортировкой слияния или ещё как);
  2. Для каждого физического плана оценивается его стоимость и выбирается план с наименьшей. В стоимости учитывается и процессорная составляющая, и составляющая времени ввода/вывода.

Методы выбора записей из исходной таблицы

Чтение всех записей и фильтрация

TableScan + Filter

kink=9sTORAl10pic3.svg

Формула стоимости:

$Cost_\Sigma = C_{CPU} + C_{IO}$

$C_{CPU} = T(R)\cdot C_{filter}$

$C_{IO} = B(R)\cdot C_B$

здесь:

$T(R)$ - общее количество записей в таблице $R$;
$B(R)$ - число физических блоков в таблице $R$;
$C_{filter}$ - среднее время фильтрации одной записи;
$C_B$ - время чтения/записи одного блока на диск.
Чтение записей из индекса и фильтрация

IndexScan + Filter

kink=9sTORAl10pic4.svg

Формула стоимости:

$Cost_\Sigma = C_{CPU} + C_{IO}$

$C_{CPU} = \frac{T(R) \cdot k}{I(R,a)}\cdot C_{filter}$

$C_{IO}$ - как и в предыдущем методе, умножаем время чтения/записи на число записей в блоке индекса. Но тут два варианта:

  1. для кластеризованного: $C_{IO} = \frac{B(Index(R,a)) \cdot k}{I(R,a)}\cdot C_B + \frac{B(R)\cdot k}{I(R,a)}\cdot C_B$. В кластеризованном индексе последовательность значений в индексе и в таблице совпадает;
  2. для индекса без кластеризации $C_{IO} = \frac{B(Index(R,a)) \cdot k}{I(R,a)}\cdot C_B + \frac{T(R)\cdot k}{I(R,a)}\cdot C_B$. Последовательность в индексе и таблице не совпадает. Число в этом случае читаемых записей равно числу блоков. Или наоборот.

здесь:

$T(R)$ - общее количество записей в таблице $R$;
$B(R)$ - число физических блоков в таблице $R$;
$I(R,a)$ - мощность индексируемого атрибута $a$ таблицы $R$ (число разных значений, исключая пустое множество);
$B(Index(R,a))$ - число блоков на листовом уровне индекса по атрибуту $a$;
$C_{filter}$ - среднее время фильтрации одной записи;
$C_B$ - время чтения/записи одного блока на диск;
$k$ - мощность атрибута $a$ в запросе (число разных значений, указанных в подзапросе $y$).

Определение $k$:

  • $k = 1$, если $y$: $a = const$;
  • $k = n$, если $y$: $a$ IN $(C_1 ... C_n)$, $C_i = const$;
  • $k =$ диапазон значений, если $y$: $a >= C_1$ AND $a <= C_2$;
  • $k =$ число атрибутов, удовлетворяющих образцу, если $y$: $a$ LIKE 'чтонить'.

Отличие физического плана от логического

Логический план не указывает, как реализуются операции реляционной алгебры, а физический определяет, как они будут реализованы.

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

kink=9sTORAl10pic1.svg

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

kink=9sTORAl10pic2.svg

Данный физический план реализуется следующим образом;

  1. для реализации подзапроса к $R_1$ читается вся таблица, записи фильтруются по $f_1$ и получаемая таблица является правым аргументов в операции соединения;
  2. из таблицы $R_2$ выделяется подусловие $y$ для индексируемого атрибута, а потом выполняется чтение записей, удовлетворяющих этому условию. Полученные записи фильтруются по $f_2$ и получаемая таблица является левым аргументом в операции соединения.

Как мы уже знаем, оптимизатор для каждого физического плана рассчитывает стоимость. Рассмотрим этот расчёт для данного примера: $Cost_\Sigma =$$Cost(TableScan(R_1), Filter(f_1, \Pi_{A_1}))$$+$$Cost(IndexScan(R_2, y), Filter(f_2, \Pi_{A_2}))$$+$$Cost(\bowtie)$

Каждая из $Cost()$ учитывает и процессорную составляющую, и временную составляющую ввода-вывода.

Arrow right.png

продолжение...