Методы оптимизации выполнения запросов в реляционных СУБД


Стратегии выполнения соединений в распределенных базах данных


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

Сначала обратимся к проблемам соединений в распределенных базах данных с традиционной организацией (подобных базам данных System R*). В System R* применяются несколько стратегий выполнения соединений удаленных отношений. Мы рассматриваем их в [129] и не будем здесь повторяться. Однако, в [95] на основе опыта использования System R* и анализа заложенных в эту систему предлагаются несколько улучшенных стратегий. Нам кажется полезным описать их.

Рассматривается соединение двух удаленных отношений S и T, расположенных в узлах 1 и 2, соответственно, под управлением предиката эквисоединения S.C1 = T.C2. Результат соединения должен быть получен в узле 1. Предполагается также следующее: Ни одно из отношений не кластеризовано по полям соединения; отсутствуют индексы на полях, отличных от полей соединения; в запросе не требуется проекция (т.е. кортежи результата включают все поля S и T); в запросе отсутствуют предикаты ограничения отношений S и T; отношения S и T хранятся в отдельных блоках внешней памяти (любой блок базы данных, содержащий кортежи S или T, не содержит кортежей других отношений).

Первый предлагаемый алгоритм заключается в том, что отношение T целиком пересылается в узел 1 и в этом узле для него создается временный индекс на поле C2. После этого в узле 1 выбирается наилучший локальный план выполнения соединения отношения S и временной копии отношения T.

Второй алгоритм основывается на использовании полусоединений. Оба отношения сортируются в соответствии со значениями полей C1 и C2 с образованием временных отсортированных файлов S' и T'.


Начало  Назад  Вперед