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


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


Базовый подход System R, допускающий размещение в одном блоке внешней памяти кортежей нескольких отношений, позволяет еще более оптимизировать этот алгоритм для выделенной операции эквисоединения двух или более отношений. Эти отношения можно совместно кластеризовать в соответствии со значениями полей соединения и завести "мультииндекс", позволяющий определить список TID'ов соединяемых кортежей. Эта идея развита и реализована в системе XSQL, ориентированной на использование в приложениях САПР и являющейся развитием System R. Более подробно это описывается в [129].

Наконец, третий алгоритм основывается на использовании некластеризованных индексов обоих отношений на полях соединения. Путем сканирования только индексов производится список пар (TID1, TID2) таких, что TID1 и TID2 определяют, соответственно, соединяемые кортежи первого и второго отношений. Далее этот список сортируется (по TID1, а в пределах группы пар с совпадающим TID1 - по TID2). Доступ к кортежам отношений и реальное выполнение соединения производится с использованием отсортированного списка пар.

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

Применимость третьего алгоритма ограничена недостаточно высоким уровнем интерфейса RSS. Действительно, пусть перед выполнением соединения отношений необходимо выполнить их ограничение. Предположим, что соединяются отношения R и S, причем для отношения R имеются индексы I1 и I2 такие, что I1 соответствует предикату ограничения, а I2 - предикату соединения, и аналогично обстоит дело с отношением S (индекс ограничения I3, индекс соединения - I4). Тогда было бы естественно развить алгоритм следующим образом.


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



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