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

...начало

Оригинал всего раздела, посвящённого оптимизации 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 'чтонить'.

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

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

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

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

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

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()$$ учитывает и процессорную составляющую, и временную составляющую ввода-вывода.

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