Эффективное выполнение операций соединения
При традиционной организации структур хранения и управляющих структур реляционной базы данных и использовании в качестве подсистемы базового доступа к хранимым данным типа RSS System R наиболее эффективно выполняются операции, соответствующие ограничению и проекции одного хранимого отношения. Двуместные операции - объединения, пересечения, соединения отношений специально не поддерживаются структурами данных и операциями нижнего уровня. Особенно болезненно ощущается отсутствие поддержки одного часто употребимого случая соединения - эквисоединения. Это действительно распространенная операция в реляционных системах, причем ее употребление в запросах тем чаще, чем более правильно с точки зрения теории реляционных баз данных спроектирована конкретная база данных. Поэтому естественно стремление исследователей и разработчиков реляционных СУБД к повышению эффективности выполнения этой операции.
Предлагаемые решения отличаются разной степенью радикальности - от повышения уровня интерфейса подсистемы доступа к данным нижнего уровня до полного пересмотра физической организации данных на внешней памяти.
Для начала коротко напомним основные алгоритмы выполнения операций эквисоединения в System R. В этой системе употребляются три алгоритма. Первый алгоритм основан на множественных сканированиях двух соединяемых отношений. Для каждого кортежа первого отношения производится полное сканирование второго отношения с выделением соединяемых кортежей и произведением очередной порции результата. Этот алгоритм не требует наличия какого-либо порядка при сканировании кортежей, следовательно, сканирование может производиться любым допустимым образом.
Второй алгоритм предполагает предварительную сортировку обоих отношений в соответствии со значениями полей соединения. После этого соединение выполняется с использованием процедуры, напоминающей процедуру слияния, применяемую в алгоритмах внешней сортировки файлов. Если отношение кластеризовано по полям соединения, и, следовательно, для него определен индекс на этих полях, то исходная сортировка этого отношения не требуется; в цикле слияния используется сканирование отношения по этому кластеризованному индексу.
Как и раньше, производится список пар TID'ов соединяемых кортежей с использованием индексов I2 и I4. Кроме того, на основе индексов I1 и I3 и условий, задаваемых предикатами ограничений, формируются два списка TID'ов L1 и L2 кортежей первого и второго отношений, удовлетворяющих предикатам ограничения. Далее производится своего рода пересечение этих трех списков таким образом, что пара (TID1, TID2) оставляется в результирующем списке пар в том и только том случае, когда TID1 присутствует в списке L1, а TID2 - в списке L2.
Такой вариант алгоритма описан в [2], но он не использовался в System R, поскольку RSS не обеспечивает операций пересечения отсортированных временных объектов, а накладные расходы, которые потребуются для выполнения подобных операций выше уровня RSS, очень трудно оценить. В литературе имеются предложения по повышению в этом направлении уровня подсистемы управления доступа к хранимым данным. Например, в [45] предлагается расширить возможности такой подсистемы, включив в число ее функций выполнение теоретико-множественных операций над отсортированными списками TID'ов. В ряде случаев это позволяет произвести все выполнение запроса в терминах идентификаторов кортежей и произвести реальное обращение к кортежам отношения только на завершающей стадии выдачи результата. При этом, поскольку результирующий список TID'ов отсортирован, число обращений к блокам внешней памяти, хранящим кортежи, будет оптимально.
Другой путь примерно в том же направлении, но с введением управляющих структур нового типа, предлагается в [38]. Новый тип управляющей структуры - индекс соединения. В общем виде, если f (R.C1, S.C2) - предикат соединения отношений R и S по полям C1 и C2, то индекс соединения R и S по f определяется как бинарное отношение JI = { (TIDi, TIDj) | f (кортеж (TIDi).C1, кортеж(TIDj).C2) = true }. (Поля C1 и C2 могут быть составными, а f - не обязательно предикат эквисоединения.) Индексы соединения предлагается хранить в виде двух B-деревьев, в одном из которых порядок поддерживается по TIDi, а в другом - по TIDj.
Это требуется для того, чтобы можно было эффективно учитывать предикаты ограничения отношений, для которых существуют обычные индексы. В [38] описаны основные алгоритмы поддержания индексов соединения при выполнении операций вставки и удаления кортежей, а также использования этих индексов при выполнении операций полусоединения, соединения и запросов общего вида. Из этого описания следует, что некоторые запросы удается выполнять достаточно эффективно, причем эффективность возрастает при увеличении объема доступной оперативной памяти. Но совершенно очевидно, что как и в случае с обычными индексами, определение слишком большого числа индексов соединения приведет в деградации системы за счет черезчур больших накладных расходов, требуемых при выполнении операций занесения и удаления кортежей.
В [48] предлагается иной вид управляющей структуры, позволяющей эффективно реализовывать операции соединения отношений, - частичные отношения. Идея состоит в том, что на стадии проектирования базы данных для каждого отношения принимается решение о наборе полей, на которых могут задаваться предикаты ограничения и соединения. Отношения хранятся как обычно в виде наборов кортежей, содержащих все поля, но, кроме того каждому отношению соответствует частичное отношение, кортежи которого содержат только те поля базового отношения, на которых могут задаваться предикаты, и одно дополнительное поле, хранящее TID соответствующего кортежа базового отношения. Кроме того, для длинных текстовых полей базового отношения можно определить функцию сжатия, приводящую такие значения к значениям соответствующих полей частичного отношения (например, действие функции сжатия может состоять в том, что из текстовой строки берутся несколько первых символов).
При таком подходе операции ограничения и соединения выполняются над частичными отношениями, а при формировании окончательного результата по имеющимся ссылкам выбираются значения других полей. Отмечается, что в ряде случаев, определяемых степенью селективности предикатов ограничения, алгоритмы соединения на основе частичных отношений оказываются эффективнее традиционных.
Много внимания в современной литературе уделяется способам физической организации баз данных на внешней памяти на основе идей многоключевого хэширования и соответствующим алгоритмам выполнения реляционных операций. Этот подход хорошо иллюстрирует работа [36]. Каждому полю каждого отношения базы данных соответствует, вообще говоря, своя хэш-функция. При занесении кортежа в отношение номер блока внешней памяти, в который будет помещен этот кортеж, вычисляется как конкатенация вырезок значений хэш-функций, примененных к значениям полей кортежа. В полученной после конкатенации битовой строке допускается перестановка битов, причем правила перестановки, как и набор используемых хэш-функций, являются характеристикой выбранного алгоритма многоключевого хэширования. Понятно, что при неполном указании значений полей искомого кортежа после применения алгоритма хэширования будет получен список страниц, в которых может находиться искомый кортеж.
Алгоритм (экви)соединения, основанный на такой организации хранимых отношений, разбивает соединение на последовательность подсоединений. При этом гарантируется, что ни один блок, содержащий кортежи соединяемых отношений, не будет использован в двух подсоединениях. Основная проблема - выбрать такое разбиение соединений на подсоединения, которое минимизирует требуемое число буферов оперативной памяти. В предлагаемом в [36] алгоритме предполагается, что число буферов оперативной памяти достаточно для выполнения каждого подсоединения. Это предположение достаточно естественно, поскольку параметры алгоритма многоключевого хэширования могут варьироваться. Снятие предположения усложняет алгоритм соединения и делает его эффективность сомнительной.
В этой работе не рассматриваются проблемы возможных переполнений страниц при расширении отношений. Однако, предложенная техника легко расширяется с использованием идей динамического многоключевого хэширования. Этому предмету в последнее время посвящается очень много работ. Основные концепции подхода изложены, например, в [37].
Интересным примером практически реализованной СУБД, основанной на некоторой вариации метода многоключевого хэширования, является французская система Sabre [34]. Наиболее интересная особенность этой системы - использование предикатных деревьев для мультиатрибутной кластеризации отношений (разновидность многоключевого хэширования). Предикатное дерево задается администратором базы данных при создании отношения и содержит простые предикаты над полями отношения. При занесении кортежа вычисление предикатов, входящих в дерево, позволяет получить номер блока внешней памяти, в которые следует поместить кортеж. При поиске кортежа на основании заданных значений полей находится множество страниц, в которых может располагаться данный кортеж. При такой организации хранимых отношений естественный способ выполнения соединения отношений основывается на хэшировании.
Система Sabre интересна еще и тем, что в ней это единственный применяемый алгоритм соединения. Как отмечается в [34], в ранних версиях системы поддерживалось несколько стратегий выполнения соединений. Подобно System R, при обработке запроса с соединиями генерировалось множество альтернативных планов его выполнения, которые затем оценивались на основе статистической информации о базе данных. Однако в ходе эксплуатации ранних версий Sabre было установлено, что, как правило, используется одна стратегия выполнения соединения, естественно соответствующая физической организации отношений. Поэтому была оставлена только эта стратегия, что позволило упростить оптимизатор и ускорить процедуру выработки плана выполнения запроса, не теряя эффективность выполнения.
Хотя мы не рассматриваем в этой статье специфику реляционных систем, использующих специализированную аппаратную поддержку, необходимо отметить, что физическая организация реляционных баз данных на основе мультиатрибутного хэширования позволяет легко распараллеливать выполнение операций соединения. Поэтому такая организация хорошо соответствует специфике мультипроцессорных машин баз данных, которые могут реально распараллеливать выполнение запроса. Конкретные предложения по распределению одного отношения между несколькими независимыми дисковыми устройствами приводятся, например, в [35]. В этой работе развивается идея декластеризации отношения, когда отношение разбивается на две или более части, средние характеристики которых примерно одинаковы. Эти части отношения хранятся на разных устройствах внешней памяти, что позволяет, например, производить параллельное сканирование отношения. Понятно, что критерии декластеризации могут быть различны, и, в частности, могут способствовать распараллеливанию соединений.
Множество вариаций алгоритмов соединения существует для распределенных реляционных СУБД. Они очень специфичны, хотя некоторые работы близки тематике машин баз данных. Проблемы оптимизации в распределенных системах рассматриваются в следующем разделе.
| |
