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


Эффективное выполнение операций соединения - часть 6


Интересным примером практически реализованной СУБД, основанной на некоторой вариации метода многоключевого хэширования, является французская система Sabre [34]. Наиболее интересная особенность этой системы - использование предикатных деревьев для мультиатрибутной кластеризации отношений (разновидность многоключевого хэширования). Предикатное дерево задается администратором базы данных при создании отношения и содержит простые предикаты над полями отношения. При занесении кортежа вычисление предикатов, входящих в дерево, позволяет получить номер блока внешней памяти, в которые следует поместить кортеж. При поиске кортежа на основании заданных значений полей находится множество страниц, в которых может располагаться данный кортеж. При такой организации хранимых отношений естественный способ выполнения соединения отношений основывается на хэшировании.

Система Sabre интересна еще и тем, что в ней это единственный применяемый алгоритм соединения. Как отмечается в [34], в ранних версиях системы поддерживалось несколько стратегий выполнения соединений. Подобно System R, при обработке запроса с соединиями генерировалось множество альтернативных планов его выполнения, которые затем оценивались на основе статистической информации о базе данных. Однако в ходе эксплуатации ранних версий Sabre было установлено, что, как правило, используется одна стратегия выполнения соединения, естественно соответствующая физической организации отношений. Поэтому была оставлена только эта стратегия, что позволило упростить оптимизатор и ускорить процедуру выработки плана выполнения запроса, не теряя эффективность выполнения.

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

Конкретные предложения по распределению одного отношения между несколькими независимыми дисковыми устройствами приводятся, например, в [35]. В этой работе развивается идея декластеризации отношения, когда отношение разбивается на две или более части, средние характеристики которых примерно одинаковы. Эти части отношения хранятся на разных устройствах внешней памяти, что позволяет, например, производить параллельное сканирование отношения. Понятно, что критерии декластеризации могут быть различны, и, в частности, могут способствовать распараллеливанию соединений.

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

| |




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