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

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

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

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

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

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

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

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

Сначала проверяется SQL-запрос. Затем он анализируется на предмет синтаксических ошибок и правильности типов данных. Если запрос проходит этот шаг, запрос разбивается на более мелкие блоки. Затем каждый блок переводится в эквивалентное выражение реляционной алгебры.

Шаги по оптимизации запросов

Оптимизация запросов включает три этапа, а именно создание дерева запросов, создание плана и создание кода плана запроса.

Step 1 − Query Tree Generation

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

Во время выполнения внутренний узел выполняется всякий раз, когда доступны его таблицы операндов. Затем узел заменяется таблицей результатов. Этот процесс продолжается для всех внутренних узлов, пока корневой узел не будет выполнен и заменен таблицей результатов.

Например, давайте рассмотрим следующие схемы -

РАБОТНИК

EmpID

EName

Зарплата

DeptNo

Дата присоединения

ОТДЕЛЕНИЕ

DNo

DName

Расположение

Пример 1

Рассмотрим запрос следующим образом.

$$ \ pi_ {EmpID} (\ sigma_ {EName = \ small "ArunKumar"} {(СОТРУДНИК)}) $$

Соответствующее дерево запросов будет -

Пример 2

Давайте рассмотрим другой запрос, включающий соединение.

$ \ pi_ {EName, Salary} (\ sigma_ {DName = \ small "Marketing"} {(DEPARTMENT)}) \ bowtie_ {DNo = DeptNo} {(EMPLOYEE)} $

Ниже приводится дерево запросов для вышеуказанного запроса.

Step 2 − Query Plan Generation

После того, как дерево запроса создано, составляется план запроса. План запроса - это расширенное дерево запросов, которое включает пути доступа для всех операций в дереве запроса. Пути доступа определяют, как должны выполняться реляционные операции в дереве. Например, операция выбора может иметь путь доступа, который дает подробную информацию об использовании индекса дерева B + для выбора.

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

Step 3− Code Generation

Генерация кода - это последний шаг в оптимизации запросов. Это исполняемая форма запроса, форма которой зависит от типа базовой операционной системы. Как только код запроса сгенерирован, Execution Manager запускает его и выдает результаты.

Подходы к оптимизации запросов

Среди подходов к оптимизации запросов в основном используются исчерпывающий поиск и алгоритмы на основе эвристики.

Исчерпывающая поисковая оптимизация

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

Оптимизация на основе эвристики

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

Некоторые из общих эвристических правил:

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

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

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