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

       

Выбор пути доступа для соединений


В 1976 г. Блазген и Эсваран [] исследовали ряд методов выполнения соединений двух отношений. Эффективность каждого из этих методов анализировалась при разных мощностях отношений. Данные авторов показывают, что для любых не слишком мелких отношений один из двух методов соединения всегда является оптимальным или близким к оптимальному. Оптимизатор System R производит выбор одного из этих методов. Сначала мы опишем эти метод, а потом обсудим, как они расширяются для случая соединения n отношений. В заключение мы указываем, как выбирается порядок соединений (порядок, в котором соединяются отношения). Для соединения двух отношений выделяются внешнее отношение, из которого сначала выбирается кортеж, и внутреннее отношение, из которого выбираются кортежи, возможно, в зависимости от значений полученного кортежа внешнего отношения. Предикат, связывающий столбцы двух отношений для порождения соединения, называется предикатом соединения. Столбцы, заданные в предикате соединения, называются столбцами соединения.

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

Для применения второго метода соединения, называемого сканированием со слиянием, требуется, чтобы внешнее и внутреннее отношения сканировались в порядке столбца соединения. Из этого следует, что наряду со столбцами, указанными в разделах ORDER BY и GROUP BY, столбцы предикатов эквисоединения (вида Table1.columnl = Table2.column2) также определяют "интересный" порядок. Если имеется более одного предиката соединения, то один из них используется как предикат соединения, а остальные - как обычные предикаты.

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