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


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


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

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

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

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




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