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


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


Как и раньше, производится список пар 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.


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



Книжный магазин