Сарыбаева А.М.
Южно-Казахстанский
государственный университет им.М.Ауезова
Обработка запроса - это процесс трансляции
декларативного определения запроса в операции манипулирования данными низкого
уровня.
Оптимизация запроса - это процедура выбора
"наилучшей" стратегии для реализации запроса из множества
альтернатив.
Распределенные базы данных организуются и
поддерживаются в децентрализованными СУБД [1].
При этом процесс обработки запроса обычно состоит из двух шагов:
·
декомпозиции запроса;
·
оптимизации запроса.
На стадии декомпозиции запроса происходит его
трансляция с языка SQL в выражение реляционной алгебры. Запрос подвергается
семантическому анализу при котором некорректные запросы отвергаются, а
корректные упрощаются. Упрощение заключается, в частности, в исключении
избыточных предикатов, которые могли быть привнесены за счет использования
представлений, а также исходя из требований безопасности и семантической
целостности. Ниже представлен пример анализа и упрощения предикатов в составе запросов.
where
position="manager" and position="assistant" - предикат противоречив;
where
(position="manager" and position="assistant") or salary
>2000 - может быть заменен на предикат where salary>2000, т.к. противоречивую фразу можно заменить на False.
Оптимизация SQL-запроса производится тогда, когда существует
более чем одно его алгебраическое представление, причем таких из которых одни
могут быть в определенном смысле "лучше" других. Обычно "качество"
алгебраического выражения определяется исходя из объема затрат, необходимых для
его вычисления.
Традиционная процедура оптимизации запроса состоит в
том, что сначала транслируется SQL-запрос в какое-нибудь выражение, а затем, путем
применяя правила эквивалентных алгебраических преобразований, из него получаются
другие алгебраические преобразования. Процедура продолжается до тех пор, пока
не будет найдено "наилучшее" преобразование. Поиск
"наилучшего" выражения происходит на основе использования функция
стоимости, отражающая сумму затрат, необходимых для выполнения запроса.
Между
шагами декомпозиции и оптимизации запроса включаются еще два действия:
·
локализация данных;
·
глобальная оптимизация
запроса.
Существо локализации данных заключается в том, чтобы
локализовать данные, участвующие в запросе, используя информацию об их
распределении. При этом выявляются фрагменты, реально участвующие в запросе, а сам запрос преобразуется таким образом, что
предписываемые операции применяются уже не к глобальным отношениям, а к их фрагментам.
Исходной информацией для локализации данных служит алгебраическое выражение,
полученное на этапе декомпозиции запроса, в котором фигурируют глобальные
отношения без учета их фрагментации или распределения.
Распределенные отношения реконструируются путем
применения инверсии правил фрагментации. Такая реконструкция рассматривается
как программа локализации. Программа локализации для горизонтально
фрагментированного запроса - есть объединение (union) его фрагментов. Соответственно
для вертикально фрагментированного запроса - есть соединение (join) его
фрагментов.
Цель глобальной оптимизации заключается в отыскании
стратегии выполнения запроса, если не оптимальную, то близкую к оптимальной. Исходную
информацию для этого представляет фрагментный запрос, т. е. алгебраическое
выражение над фрагментами. Стратегия выполнения
распределенного запроса выражается в терминах операций реляционной алгебры и
коммуникационных примитивов описывающих пересылки данных между узлами. Путем
перестановок операций в рамках фрагментного запроса можно получить множество
эквивалентных планов его выполнения, среди которых ищется
"наилучший".
Оптимизация запросов обычно базируется на
использовании трех компонентов: пространство поиска, модель стоимости и
стратегия поиска.
Пространство поиска - это множество альтернативных
планов выполнения исходного запроса. Рассматриваемые планы являются эквивалентными
в том смысле, что они дают один и тот же результат, но различаются порядком и
способами выполнения отдельных операций.
Модель стоимости представляет формализованный способ
оценки стоимости реализации рассматриваемого плана. Для того чтобы оценка была
близка к реальности, модель стоимости должна учитывать свойства используемой среды
параллельных вычислений.
Стратегия поиска - это способ поиска и выбора
наилучшего плана на пространстве поиска. Она определяет, какие планы и в каком
порядке следует выбирать и оценивать.
В распределенной среде функция стоимости определяется
в единицах времени и оценивает затраты таких ресурсов, как:
·
дисковое пространство;
·
число обменов с дисками;
·
время CPU;
·
коммуникации и т. д.
Обычно это некоторая взвешенная сумма затрат
ввода-вывода, CPU и коммуникаций. Иногда в распределенных СУБД применяется
упрощенный подход, когда в качестве наиболее значимых рассматриваются лишь
коммуникационные затраты. Это справедливо для глобальных сетей, где из-за
ограниченной пропускной способности линий связи пересылки данных обходятся
значительно дороже, чем при локальной обработке.
Важнейший аспект оптимизации запросов представляет
порядок выполнения соединений (самая дорогостоящая операция), поскольку его
изменение может вызвать эффект ускорения либо замедления соединений до
нескольких порядков. Базовая методика для оптимизации последовательности
соединений заключается в применении оператора полусоединений (semijoin). Применение оператора полусоединений в распределенной системе позволяет сократить
размеры операндов, участвующих в соединениях, и, следовательно,
коммуникационных затрат.
В распределенных СУБД часто применяется упрощенный подход, когда в
качестве наиболее значимых рассматриваются лишь коммуникационные затраты. В
частности, в случае глобальных сетей, где из-за ограниченной пропускной
способности линий связи пересылки данных обходятся значительно дороже, чем при
локальной обработке. В данном случае, для того чтобы определить порядок
выполнения операций, необходимо оценить вычислительные затраты для множества
альтернативных упорядочений. Определение вычислительных затрат до выполнения
запроса (статическая оптимизация) основано на статистике фрагментов и на
формулах для оценки мощности результатов реляционных операций. Таким образом, решения,
принимаемые в ходе оптимизации, зависят от имеющейся статистики фрагментов.
В распределенной среде процесс оптимизации запросов должен
быть также распределенным, как и процесс выполнения запросов. Таким образом, в
общем случае процесс оптимизации будет содержать этап глобальной оптимизации,
за которым последуют этапы локальной оптимизации на каждом задействованном узле.
К примеру, предположим, что запрос Q представлен на рассмотрение узлу X, при этом запрос Q включает объединение отношения Ry, содержащее сто кортежей узле Y, с отношением Rz, в котором миллион кортежей на узле Z. Задача оптимизации запроса Q состоит в том, чтобы выбрать глобальную
стратегию его выполнения.
В данном случае очевидно, что было бы выгоднее переслать
отношение Ry
на узел Z, а не отношение Rz на узел Y и, конечно же, не
оба отношения Ry и
Rz на узел X. Затем, после принятия решения, пересылка
отношения Ry
на узел Z. Реальная стратегия
выполнения отношения на узле Z будет определяться локальным оптимизатором этого узла.
Проиллюстрируем это на следующем примере [2, 3].
Рассматривается
упрощенная База данных поставщиков и изделий
S {Si, CITY } 10
000 хранимых кортежей на узле А
Р { Pi, COLOR } 100 000 хранимых кортежей на узле Б
SP {
Si, Р# } 1 000 000 хранимых кортежей на узле А
Предположим, что каждый хранимый кортеж имеет длину 25 байт
(200 бит).
Требуется обработать запрос
следующего содержания ("Получить
номера поставщиков изделий красного цвета из Лондона")
( ( S JOIN SP
JOIN P ) WHERE CITY = 'London' AND
COLOR
= COLOR ('Red')
) { Si }
Количество изделий красного цвета - 10 ед.
Количество поставок, выполненных поставщиками из Лондона - 100
000
Предполагаемая скорость передачи данных - 50 000 бит/с.
Задержка доступа - 0,1 с.
Рассмотрим шесть возможных стратегий выполнения этого
запроса. Для каждой стратегии i рассчитаем общее время Т[i] передачи данных по следующей формуле:
Т[i] = ( общая задержка доступа ) +( общий
объем данных / скорость передачи данных )
Применительно к нашему случаю, данная
формула сводится к следующей:
Т[i] = ( количество сообщений / 10 ) +
(количество битов / 50000 )
Рассмотрим различные
возможные стратегии обработки запроса.
1.
Пересылка
записей об изделиях на узел А и обработка запроса на узле А.
Т[1] = 0,1 + ( lOflDOO * 200 ) / 50000 ~ 400 с
(приблизительно 6,67 мин)
2.
Пересылка
записей о поставщиках и поставках на узел Б и обработка запроса.
Т[2] = 0,2 + ( ( 10000 + 1000000 ) * 200 ) / 50000 = 4040 с. ( 1,12 ч.)
3.
Соединение
отношений поставщиков и поставок на узле А, выборка из результирующего
отношения кортежей для поставщиков из Лондона с последующей проверкой на узле Б
для каждого выбранного поставщика соответствующих изделий.
Т[3] = 20000 с. (5,56 ч.)
4.
Выборка
изделий красного изделий на узле Б и проверка на узле А наличия поставок,
связывающих изделие с поставщиком из Лондона. Каждая из таких проверок включает два сообщения. Время передачи
этих сообщений будет мало по сравнению
с задержкой доступа.
Т[4] = 2 с.
5.
Соединение
отношений поставщиков и поставок на узле А, выборка из рез кортежей для
поставщиков из Лондона, проекция этих кортежей по атрибут Р# и пересылка
результата на узел Б. Завершение обработки на узле Б.
Т[5] = 0,1 + ( 100000 *
200 ) / 50000 = 400 с (6,67 мин.)
6. Выборка изделий красного цвета на узле Б и пересылка
результата на узел А с последующей обработкой на узле А.
Т[6] = 0,1 + ( 10 * 200 ) / 50000 = 0,1 с (приблизительно)
Полученные результаты отображены в следующей таблице.
|
№ |
Стратегия |
Время передачи данных |
|
1 |
Пересылка
Р на А |
6,67 мин |
|
2 |
Пересылка
S и SP на Б |
1,12 ч |
|
3 |
Для
каждой поставки из Лондона проверка изделий красного цвета |
5,56 ч |
|
4 |
Для каждого изделия красного цвета проверка поставщика
из Лондона |
2,00 с |
|
5 |
Пересылка
поставок из Лондона на Б |
6,67 мин |
|
6 |
Пересылка
изделий красного цвета на А |
0,10 |
Каждая из рассмотренных стратегий
представляет возможный вариант обработки запроса. Их анализ позволяет
сформулировать следующие выводы:
1. В зависимости от стратегии выполнения
запроса время передачи данных может изменяться в широких пределах.
2. Скорость обмена данными и задержки доступа имеют важное значение для
выбора стратегии.
3. Для неудачных стратегий время вычислений и ввода-вывода ничтожно
мало по сравнению со временем передачи данных. Для лучших стратегий эти
отношения могут зависеть от дополнительных обстоятельств.
4. Параллельная обработка запроса на двух узлах
значительно сокращает время ответа системы пользователю по сравнению с его обработкой
и исполнением на одном узле.
1.
Оптимизация запросов СУБД: [электронный ресурс] – Режим доступа : http://dic.academic.ru/dic.nsf/ruwiki/356734
3. Методы повышения производительности:
[электронный ресурс] – Режим доступа : http://wworacle.narod.ru/glava7.html