Учебники

Оптимизация запросов в централизованных системах

Как только альтернативные пути доступа для вычисления выражения реляционной алгебры получены, определяется оптимальный путь доступа. В этой главе мы рассмотрим оптимизацию запросов в централизованной системе, а в следующей главе мы изучим оптимизацию запросов в распределенной системе.

В централизованной системе обработка запросов выполняется с целью:

  • Минимизация времени отклика на запрос (время, затраченное на получение результатов по запросу пользователя).

  • Максимизируйте пропускную способность системы (количество запросов, которые обрабатываются за определенный промежуток времени).

  • Уменьшите объем памяти и памяти, необходимых для обработки.

  • Увеличить параллелизм.

Минимизация времени отклика на запрос (время, затраченное на получение результатов по запросу пользователя).

Максимизируйте пропускную способность системы (количество запросов, которые обрабатываются за определенный промежуток времени).

Уменьшите объем памяти и памяти, необходимых для обработки.

Увеличить параллелизм.

Анализ запросов и перевод

Изначально 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 вниз по дереву запросов. Это уменьшает количество кортежей, доступных для объединения.

Сначала выполняйте самые строгие операции выбора / проекта перед другими операциями.

Избегайте операций с несколькими продуктами, поскольку они приводят к промежуточным таблицам очень большого размера.