Классика баз данных - статьи

       

Метод сканирования со слиянием применяется


Метод сканирования со слиянием применяется только к эквисоединениям, хотя, в принципе, его можно было бы применить и к другим типам соединения. Если у одного или обоих соединяемых отношений отсутствуют индексы на столбце соединения, они должны быть отсортированы и помещены во временный список (list), упорядоченный по столбцу соединения.

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

Соединение n отношений может быть воплощено как последовательность соединений двух отношений. В этом воплощении соединяются два отношения, результирующее отношение соединяется с третьим отношением и т.д. На каждом шаге соединения n отношений можно определить внешнее отношение (как правило, составное) и внутреннее отношение (добавляемое к соединению). Таким образом, описанные выше методы легко обобщаются для соединения n отношений. Однако следует подчеркнуть, что первое соединение двух отношений не обязательно должно быть полностью завершено да начала выполнения второго соединения двух отношений. Как только мы получим составной кортеж для первого соединения двух отношений, он может быть соединен с кортежами третьего отношения, образуя кортежи для соединения с четвертым отношением и т.д. При выполнении одного запроса могут смешиваться методы соединения вложенными циклами и сканированием со слиянием, например, при соединении трех отношений первые два отношения могут соединяться методом сканирования со слиянием, а результирующее отношение может соединяться с третьим отношением методом вложенных циклов.

Содержание  Назад  Вперед