Технологии распределенных баз данных :

Источник:http://ami.nstu.ru/~vms/lecture/lecture10/lecture10.htm

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

Обработка запроса - это процесс трансляции декларативного определения запроса в операции манипулирования данными низкого уровня.

Оптимизация запроса - это процедура выбора "наилучшей" стратегии для реализации запроса из множества альтернатив.

Для централизованной СУБД весь процесс состоит обычно из двух шагов:

декомпозиции запроса (1) и

оптимизации запроса (2).

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

Примеры анализа предикатов:

where position="manager" and position="assistant" - предикат противоречив;

where (position="manager" and position="assistant") or salary >2000 может быть заменен на предикат where salary>2000, т.к. противоречивую фразу можно заменить на False.

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

В распределенной СУБД между шагами декомпозиции и оптимизации запроса включаются еще два действия:

локализация данных (1+) и

глобальная оптимизация запроса (2-).

(1+) Исходной информацией для локализации данных служит алгебраическое выражение, полученное на этапе декомпозиции запроса. В этом выражении фигурируют глобальные отношения без учета их фрагментации или распределения. Сущность данного шага заключается в том, чтобы локализовать участвующие в запросе данные, используя информацию об их распределении. При этом выявляются фрагменты, реально участвующие в запросе, а запрос преобразуется к форме, где операции применяются уже не к глобальным отношениям, а к фрагментам. Ранее отмечалось, что правила фрагментации выражаются посредством реляционных операций:

селекции для горизонтальной фрагментации и

проекции для вертикальной.

Распределенные отношения реконструируются путем применения инверсии правил фрагментации. Это называется программой локализации. Программа локализации для

горизонтально фрагментированного запроса есть объединение (union) его фрагментов;

вертикально фрагментированного запроса есть соединение (join) его фрагментов.

(2-) Исходной информацией для третьего шага является фрагментный запрос, т. е. алгебраическое выражение над фрагментами. Цель глобальной оптимизации - найти стратегию выполнения запроса, близкую к оптимальной (вычислительно трудноразрешимая задача). Стратегия выполнения распределенного запроса выражается в терминах операций реляционной алгебры и коммуникационных примитивов (операций "послать"/"получить"), описывающих пересылки данных между узлами. Ранее (1) запрос уже был в определенной мере оптимизирован, в частности, за счет удаления избыточных выражений. Однако проведенные оптимизации не зависели от характеристик фрагментов, например их мощности и не были учитывали коммуникационных операций. Путем перестановок операций в рамках фрагментного запроса можно получить множество эквивалентных планов его выполнения, среди которых ищется "наилучший".

Оптимизатор запросов обычно представляется в виде трех компонентов: пространство поиска (1), модель стоимости (2) и стратегия поиска (3).

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

Модель стоимости (2) - это способ оценить стоимость реализации заданного плана. Для того чтобы оценка была близка к реальности, модель стоимости должна учитывать свойства среды параллельных вычислений.

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

В распределенной среде функции стоимости определяется в единицах времени и оценивает затраты таких ресурсов, как

дисковое пространство,

число обменов с дисками,

время CPU,

коммуникации и т. д. (обычно это некоторая взвешенная сумма затрат ввода-вывода, CPU и коммуникаций).

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

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

Операция полусоединения отношений R и S определяет отношение, которое содержит кортежи отношения R, которые входят в соединение отношений R и S.
II. Управление одновременным доступом

Проблема эта уже нами рассматривалась ранее: для поддержания согласованного состояния данных необходимо обеспечить синхронизацию доступа. Синхронизация достигается путем применения алгоритмов управления одновременным доступом

Алгоритмы управления одновременным доступом обеспечивают:

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

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

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

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