Обработка и оптимизация запросов

Обработка запроса (query processing) — это процесс трансляции декларативного определения запроса в операции манипулирования данными низкого уровня. Стандартным языком запросов, поддерживаемым современными СУБД, является SQL. Оптимизация запроса (query optimization) — это процедура выбора «наилучшей» стратегии выполнения запроса из множества альтернатив.

Для централизованной СУБД весь процесс состоит обычно из двух шагов: декомпозиции запроса (query decomposition) и оптимизации запроса. Декомпозиция запроса — это трансляция его с языка SQL в выражение реляционной алгебры. В ходе декомпозиции запрос подвергается семантическому анализу; при этом некорректные запросы отвергаются, а корректные упрощаются. Упрощение заключается, в частности, в исключении избыточных предикатов, которые могли быть привнесены за счет использования представлений, а также исходя из ограничений безопасности и семантической целостности. Упрощенный запрос преобразуется в алгебраическую форму.

Для заданного SQL-запроса существует более чем одно алгебраическое представление, причем некоторые из них могут быть «лучше» других. «Качество» алгебраического выражения определяется исходя из объема затрат, необходимых для его вычисления. Традиционная процедура состоит в том, чтобы сначала оттранслировать SQL-запрос в какое-нибудь выражение, а затем, применяя правила эквивалентных алгебраических преобразований, получать из него другие алгебраические преобразования, пока не будет найдено «наилучшее». При поиске «наилучшего» выражения используется функция стоимости, в соответствии с которой вычисляется сумма затрат, необходимых для выполнения запроса. Этот процесс и называется оптимизацией запросов.

В распределенной СУБД между шагами декомпозиции и оптимизации запроса включаются еще два действия: локализация данных (data localization) и глобальная оптимизация запроса (global query optimization).

Исходной информацией для локализации данных служит исходное алгебраическое выражение, полученное на шаге декомпозиции запроса. В исходном алгебраическом выражении фигурируют глобальные отношения без учета их фрагментации или распределения. Основная роль локализации данных заключается в том, чтобы локализовать участвующие в запросе данные, используя информацию об их распределении. На этом шаге выявляются фрагменты, реально участвующие в запросе, и запрос преобразуется к форме, где операции применяются уже не к глобальным отношениям, а к фрагментам. Как отмечалось выше, правила фрагментации выражаются посредством реляционных операций (селекции для горизонтальной фрагментации и проекции для вертикальной). Распределенные отношения реконструируются путем применения инверсии правил фрагментации. Это называется программой локализации. Программа локализации для горизонтально (вертикально) фрагментированного отношения представляет собой объединение (union) (соединение (join)) соответствующих фрагментов. Таким образом, на шаге локализации данных каждое глобальное отношение запрос заменяется его программой локализации, а затем результирующий фрагментный запрос упрощается и реструктурируется с целью получения другого «хорошего» запроса. Для упрощения и реструктуризации могут использоваться те же правила, что и на шаге декомпозиции. Как и на шаге декомпозиции, окончательный запрос над фрагментами может быть еще далек от оптимального; данный процесс лишь исключает «плохие» алгебраические запросы.

Исходной информацией для третьего шага является фрагментный запрос, т. е. алгебраическое выражение над фрагментами. Цель глобальной оптимизации — найти стратегию выполнения запроса, близкую к оптимальной. Напомним, что нахождение оптимальной стратегии — вычислительно трудноразрешимая задача. Стратегию выполнения распределенного запроса можно выразить в терминах операций реляционной алгебры и коммуникационных примитивов (операций send/receive), используемых для пересылки данных между узлами. На предыдущих шагах запрос уже был в определенной мере оптимизирован, в частности, за счет удаления избыточных выражений. Однако проведенная оптимизация не зависела от характеристик фрагментов, например их мощности. Кроме того, на предыдущих шагах еще не учитывались коммуникационные операции. Путем изменения порядка операций внутри одного фрагментного запроса можно получить много эквивалентных планов его выполнения. Оптимизация запроса заключается в нахождении «наилучшего» плана из множества возможных планов, исследуемых оптимизатором¹⁾ .

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

В распределенной среде функция стоимости, часто определяемая в единицах времени, оценивает затраты вычислительных ресурсов, таких как дисковое пространство, число обменов с дисками, время центрального процессора, коммуникации и т. д. Обычно это некоторая взвешенная сумма затрат ввода-вывода, центрального процессора и коммуникаций. В распределенных СУБД применяется упрощенный подход, когда в качестве наиболее значимых рассматриваются лишь коммуникационные затраты. Это справедливо для глобальных сетей, где из-за ограниченной пропускной способности линий связи пересылки данных обходятся значительно дороже, чем при локальной обработке. Чтобы определить порядок выполнения операций, необходимо оценить стоимости выполнения планов с другим порядком операций. Определение стоимости выполнения до реального выполнения запроса (статическая оптимизация) основано на статистике фрагментов и формулах для оценки мощности результатов реляционных операций. Таким образом, решения, принимаемые в ходе оптимизации, зависят от имеющейся статистики фрагментов.

Важным аспектом оптимизации запросов является порядок выполнения соединений, поскольку его изменение может привести к ускорению на нескольких порядков. Базовый метод оптимизации последовательности распределенных операций соединения заключается в применении операции полусоединения (semijoin). Основное преимущество полусоединений в распределенной системе — это сокращение размеров операндов, участвующих в соединениях, и, следовательно, коммуникационных затрат. Однако в более современных методах, учитывающих, наряду с коммуникационным расходами, также и затраты на локальную обработку, полусоединения не используются, поскольку они приводят к увеличению объема локальной обработки. Результатом работы глобального оптимизатора является оптимизированное алгебраическое выражение, включающее коммуникационные операции над фрагментами.

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

Внутриоперационный (intra-operation) параллелизм достигается за счет выполнения операции сразу на нескольких узлах многопроцессорной машины. Для этого необходимо предварительное разбиение операндов, т. е. их горизонтальная фрагментация по узлам. Способ разделения базового отношения относится к области физического проектирования базы данных. Обычно разделение производится путем применения некоторой хэш-функции к тому атрибуту отношения, который будет часто являться атрибутом соединения. Набор узлов, в которых хранится отношение, называется домашним набором (home). Домашним набором узлов операции (home of an operation) называется набор узлов, в которых она выполняется; оно должно совпадать с домашним набором узлов ее операндов, чтобы операция имела доступ к своим операндам. Это значит, что для бинарных операций, таких как соединения, может потребоваться переразделение (repartitioning) одного из операндов. В некоторых случаях оптимизатор, возможно, сочтет целесообразным провести переразделение обоих операндов. Для реализации внутриоперационного параллелизма в параллельных СУБД применимы некоторые методы, разработанные для распределенных баз данных.

Межоперационный (inter-operation) параллелизм имеет место, когда одновременно выполняются две или более операции, независимые или связанные общим потоком данных. Термином поток данных (dataflow) мы обозначаем форму параллелизма, реализуемую методами конвейерной обработки (pipelining). При независимом параллелизме операции выполняются одновременно или в произвольном порядке. Независимый параллелизм возможен, только если операции не содержат в качестве операндов общих данных.