Размер операции соединения. Алгоритм соединения, основанный на двух вложенных циклах

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

Пусть существуют отношения r(R) и s(S). Декартово произведение rхs включает nr*nsкортежей. Каждый кортеж занимает sr+ss байт. Таким будет размер результата соединения в худшем случае. Размер натурального соединения может быть более компактным.

Рассмотрим варианты:

а) Если пересечение атрибутов R и S = 0, то результат натурального соединения равен результату декартова произведения.

б) Если пересечение атрибутов R и S равно ключу отношения R, то каждая строка отношения s будет соединена максимум с одной строкой отношения r, то есть кортежей в результате соединения будет не больше числа кортежей отношения s.

в) Если пересечение атрибутов = {A}, причем это множество не является ключом ни для одного из отношений. Среднее количество записей в отношении s с некоторым значением атрибутов {A} равно ns\V(A,s). При соединении каждой строки отношения r с отношением s будет равно (nr*ns)\V(A, s). Если отношения поменять местами, то оценка составит (ns*nr)\V(A, r). Если V(A, r) не равно V(A, s), то выбирают меньшую из оценок.

Простейший алгоритм соединения.

Этот алгоритм основан на использовании вложенных циклов. Рассмотрим работу алгоритма для q-соединения отношений r и s.

Для каждого кортежа tr отношения r выполнить

Для каждого кортежа ts отношения s выполнить

Если пара (ts, tr) соответствует условию

то tr?ts добавить к результату

Отношение r в этом случае называется внешним, а отношение s – внутренним. Через tr?ts обозначена конкатенация значений атрибутов кортежей tr и ts. Вычисление натурального соединения согласно алгоритму выполняется аналогично, но после конкатенации из результирующей строки исключаются повторяющиеся атрибуты.

Приведенный алгоритм неэффективен, так как для каждого кортежа внешнего отношения осуществляется просмотр каждого кортежа внутреннего отношения. В худшем случае в памяти помещается только по одному блоку каждого отношения. Тогда для построения соединения потребуется nr*bs+br доступов к диску. /*Второе слагаемое чтение всех блоков внешнего отношения, первое слагаемое – сколько доступов нужно по внутреннему отношению */. В случае, если оба отношения целиком помещаются в памяти, потребуется bs+br обращений к диску для чтения. Более того, для получения такой же эффективности достаточно, что бы в памяти целиком поместилось внутреннее отношение.