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

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

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

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

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

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

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

Разбор запросов и перевод

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

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

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