Как только альтернативные пути доступа для вычисления выражения реляционной алгебры получены, определяется оптимальный путь доступа. В этой главе мы рассмотрим оптимизацию запросов в централизованной системе, а в следующей главе мы изучим оптимизацию запросов в распределенной системе.
В централизованной системе обработка запросов выполняется с целью:
-
Минимизация времени отклика на запрос (время, затраченное на получение результатов по запросу пользователя).
-
Максимизируйте пропускную способность системы (количество запросов, которые обрабатываются за определенный промежуток времени).
-
Уменьшите объем памяти и памяти, необходимых для обработки.
-
Увеличить параллелизм.
Минимизация времени отклика на запрос (время, затраченное на получение результатов по запросу пользователя).
Максимизируйте пропускную способность системы (количество запросов, которые обрабатываются за определенный промежуток времени).
Уменьшите объем памяти и памяти, необходимых для обработки.
Увеличить параллелизм.
Анализ запросов и перевод
Изначально SQL-запрос сканируется. Затем он анализируется на предмет синтаксических ошибок и правильности типов данных. Если запрос проходит этот шаг, запрос разбивается на меньшие блоки запроса. Каждый блок затем переводится в эквивалентное выражение реляционной алгебры.
Шаги для оптимизации запросов
Оптимизация запросов включает в себя три этапа, а именно: создание дерева запросов, создание плана и создание кода плана запроса.
Шаг 1 — Генерация дерева запросов
Дерево запросов — это древовидная структура данных, представляющая выражение реляционной алгебры. Таблицы запроса представлены в виде листовых узлов. Операции реляционной алгебры представлены как внутренние узлы. Корень представляет запрос в целом.
Во время выполнения внутренний узел выполняется всякий раз, когда доступны его таблицы операндов. Затем узел заменяется таблицей результатов. Этот процесс продолжается для всех внутренних узлов, пока корневой узел не будет выполнен и заменен таблицей результатов.
Например, давайте рассмотрим следующие схемы —
РАБОТНИК
| EmpID | Ename | Оплата труда | DeptNo | Дата присоединения |
ОТДЕЛ
| Дно | Dname | Место нахождения |
Пример 1
Давайте рассмотрим запрос следующим образом.
$$ \ pi_ {EmpID} (\ sigma_ {EName = \ small «ArunKumar»} {(EMPLOYEE)}) $$
Соответствующее дерево запросов будет —
Пример 2
Давайте рассмотрим другой запрос, включающий соединение.
$ \ pi_ {EName, Salary} (\ sigma_ {DName = \ small «Marketing»} {(DEPARTMENT)}) \ bowtie_ {DNo = DeptNo} {(EMPLOYEE)} $
Ниже приведено дерево запросов для вышеуказанного запроса.
Шаг 2 — Генерация плана запроса
После создания дерева запросов составляется план запроса. План запроса — это расширенное дерево запросов, которое включает пути доступа для всех операций в дереве запросов. Пути доступа определяют, как должны выполняться реляционные операции в дереве. Например, операция выбора может иметь путь доступа, который дает подробную информацию об использовании индекса дерева B + для выбора.
Кроме того, в плане запроса также указывается, как промежуточные таблицы должны передаваться от одного оператора к другому, как должны использоваться временные таблицы и как должны выполняться операции конвейеризации / объединения.
Шаг 3 — Генерация кода
Генерация кода — это последний шаг в оптимизации запросов. Это исполняемая форма запроса, форма которой зависит от типа базовой операционной системы. После того, как код запроса сгенерирован, диспетчер выполнения запускает его и выдает результаты.
Подходы к оптимизации запросов
Среди подходов к оптимизации запросов чаще всего используются алгоритмы исчерпывающего поиска и эвристики.
Исчерпывающая поисковая оптимизация
В этих методах для запроса сначала создаются все возможные планы запроса, а затем выбирается лучший план. Хотя эти методы обеспечивают лучшее решение, они имеют экспоненциальную временную и пространственную сложность из-за большого пространства решений. Например, техника динамического программирования.
Эвристическая оптимизация
Эвристическая оптимизация использует оптимизацию на основе правил для оптимизации запросов. Эти алгоритмы имеют полиномиальную временную и пространственную сложность, которая ниже, чем экспоненциальная сложность алгоритмов исчерпывающего поиска. Однако эти алгоритмы не обязательно дают лучший план запроса.
Некоторые из общих эвристических правил —
Выполните операции выбора и проецирования перед операциями объединения. Это делается путем перемещения операций select и project вниз по дереву запросов. Это уменьшает количество кортежей, доступных для объединения.
Сначала выполняйте самые строгие операции выбора / проекта перед другими операциями.
Избегайте операций с несколькими продуктами, поскольку они приводят к промежуточным таблицам очень большого размера.