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


Стратегии выполнения соединений в распределенных базах данных - часть 2


Производится проекция S' на С1 (уничтожаются дубликаты) и результат посылается в узел 2. В этом узле выполняется полусоединение T' с полученным унарным отсортированным отношением (т.е. выбираются те кортежи T', значение поля C2 которых совпадает с каким-либо значением C1 полученного списка). Полученное промежуточное по-прежнему отсортированное отношение T'' посылается в узел 1, где выполняется соединение S' и T'' методом слияний (оба отношения уже отсортированы) и производится окончательный результат.

При наличии индексов на полях отношений S.C1 и T.C2 может быть использован либо этот же алгоритм, либо его модификация, в которой отсутствует сортировка (используются сканирования отношений через индексы).

Наконец, третий альтернативный алгоритм соединения двух отношений, предлагаемый в [95], основан на использовании так называемых фильтров Блюма [28]. В соответствии с этим алгоритмом, если индексы на полях S.C1 и T.C2 не определены, сначала в узле 1 для отношения S по полю C1 строится фильтр Блюма. Фильтр представляет собой битовый массив, инициализированный нулями. Для формирования фильтра производится сканирование отношения S, и к значению поля C1 каждого кортежа применяется хэш-функция, ставящая в соответствие этому значению позицию бита в массиве. Этот бит устанавливается в единицу.

Сформированный фильтр посылается в узел 2. В этом узле производится сканирование отношения T и к значениям поля C2 применяется та же хэш-функция, задающая позицию соответствующего бита в фильтре. Если значение этого бита равно 1, то кортеж отношения S посылается в узел 1 в потоке кортежей T'. В этом узле выполняется соединение S и T' и формируется результат.

Наличие индексов на полях S.C1 и T.C2 позволяет модифицировать алгоритм. В частности, фильтр Блюма для отношения S можно построить в этом случае, сканируя только записи индекса без потребности обращаться к кортежам отношения.

В [95] приводятся оценки для каждого из трех алгоритмов и описываются экспериментальные результаты их использования в System R* в высоко- и среднескоростных сетях.


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