Static optimization of distributed queries on broadcast networks

Abstract

Query optimization is one of the most relevant problem in the implementation of geographically distributed databases. The presented work is devoted to the study of the issue related to the query optimization algorithm in distributed databases. The author uses empirical and theoretical research methods. The work uses scientific materials of domestic and foreign authorship.

Full Text

Распределенная база данных (БД) – это несколько логически взаимосвязанных баз данных, которые расположены в узлах распределенной вычислительной системы [7]. Структура распределенной БД определяет оптимальную стратегию размещения фрагментов БД для обеспечения целостности, безопасности и производительности. Стратегия распределения определяет, как разделить БД и где хранить каждый фрагмент [2]. Узлы распределенной системы могут быть разных конфигураций. Связи между ними тоже могут быть различными. Доступ к данным и управление ими требует особого внимания со стороны распределенной системы управления базами данных (СУБД) [1; 3-6].

Когда отношения или их части хранятся в разных узлах, для получения ответов на запросы, требуется выполнять операции соединения или объединения.

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

При оптимизации запросов перед пользователями стоят две основные цели: уменьшение времени передачи данных и уменьшение времени ответа. Большинство алгоритмов оптимизации игнорируют затраты на передачу данных целевому узлу. В данной статье будем принимать во внимание фрагментацию. Для наглядности рассмотрим только вертикальную фрагментацию.

Рассмотрим распределенную базу данных Нижневартовского государственного университета, где данные студентов находятся в разных департаментах (узлах). Предположим, что данные содержатся в отношениях СТУДЕНТ, ДИСЦИПЛИНА и ЭКЗАМЕН и фрагментированы как показано ниже:

Узел 1	Узел 2	Узел 3
СТУДЕНТ	ДИСЦИПЛИНА	ЭКЗАМЕН

Необходимо получить список студентов, допущенных к экзамену по дисциплине СУБД. Для нераспределенных систем на языке SQL данный запрос выглядел бы как в Листинге 1:

SELECT СТУДЕНТ.СТФИО

FROM СТУДЕНТ

INNER JOIN ЭКЗАМЕН ON СТУДЕНТ.СТКОД = ЭКЗАМЕН.СТКОД

INNER JOIN ДИСЦИПЛИНА ON ДИСЦИПЛИНА.ДСКОД = ЭКЗАМЕН.ДСКОД

WHERE ДИСЦИПЛИНА.ДСНАЗВ=`СУБД`

Листинг 1. Локальный SQL-запрос

Для соединения трех отношений возможны четыре сайта-кандидата: сайт первого отношения, сайт второго отношения, сайт третьего отношения или четвертый сайт. Для межсайтовой передачи данных поддерживаются два метода:

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

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

1. переместить ДИСЦИПЛИНА и ЭКЗАМЕН на узел 1 и выполнить запрос (СТУДЕНТ ЭКЗАМЕН . ДИСЦИПЛИНА);
2. переместить СТУДЕНТ и ЭКЗАМЕН на узел 2 и выполнить запрос (СТУДЕНТ ЭКЗАМЕН . ДИСЦИПЛИНА);
3. переместить СТУДЕНТ и ДИСЦИПЛИНА на узел 3 и выполнить запрос (СТУДЕНТ ЭКЗАМЕН ДИСЦИПЛИНА);
4. переместить СТУДЕНТ, ДИСЦИПЛИНА и ЭКЗАМЕН на узел 4 и выполнить запрос (СТУДЕНТ ЭКЗАМЕН . ДИСЦИПЛИНА);

горитм оптимизации прогнозирует общее время каждой стратегии иыбирает самую минимальную. Учитывая, что после объединения СТУДЕНТ ⋈ ЭКЗАМЕН ⋈ ДИСЦИПЛИНА не выполняется никаких операций, очевидно, что стратегия 4 сопряжена с наибольшими затратами, поскольку должны быть переданы все отношения. Если размер (СТУДЕНТ) намного больше, чем размер (ДИСЦИПЛИНА) и (ЭКЗАМЕН), стратегии 2 и 3 минимизируют время связи и, вероятно, будут лучшими, если локальное время обработки не слишком велико по сравнению со стратегиями 1 и 4.

Если стратегия 2 не является лучшей, выбор делается между стратегиями 1 и 3. Затраты на локальную обработку в обеих этих альтернативах идентичны. Если отношение СТУДЕНТ имеет большой размер и только несколько кортежей в отношениях ДИСЦИПЛИНА и ЭКЗАМЕН совпадают по размеру, стратегия 1, вероятно, требует наиньшего времени на обмен данными и является наилучшей. В противном случае, то есть, если отношение СТУДЕНТ небольшого размера или совпало много кортежей в отношения ДИСЦИПЛИНА и ЭКЗАМЕН, необходимо выбрать между стратегиями 2 и 3.

Для решения данной задачи необходимо решить проблему оптимизации, правильно выбрать отношения для перемещения и узлы, в которых будет осуществляться обработка. Для запроса с n-отношениями n–1 отношений предстоит переместить в узел, где находится оставшееся отношение, и реплицировать. Для параллельного выполнения можно разбить отношения на k фрагментов. На выбор нужных отношений и узлов влияет еще и топология сети. В широковещательных сетях репликация выполняется легче, чем в сетях с двухточечным соединением. Количество промежуточных узлов тоже необходимо учитывать, так как при увеличении количества узлов уменьшается время ответа из-за параллельной обработки, но возрастает полное время из-за увеличения затрат на передачу данных.

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

Рассмотрим правила минимизации времени передачи данных. Допустим, в сети M узлов и отношений. обозначает отношении R, хранящийся в узле i. Время передачи b байтов на k (1≤k≤m) узлов обозначена T(b). На широковещательных сетях

$T_k\left(b\right)=T_1\left(b\right)$                                 

Тогда правило можно сформулировать в виде, как в Листинге 2:

ЕСЛИ $size\left(R_i\right)>ma{x}_{j=\mathrm{1,}n}\left(size\left(R_j\right)\right)$ ТОГДА

    обрабатывающим будет узел i с наибольшим объемом данных

ИНАЧЕ

    R_p наибольшее отношение and узел R_p является обрабатывающим

Листинг 2. Правило определение узла-процессора

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

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

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