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


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


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

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

В этой работе не рассматриваются проблемы возможных переполнений страниц при расширении отношений. Однако, предложенная техника легко расширяется с использованием идей динамического многоключевого хэширования. Этому предмету в последнее время посвящается очень много работ. Основные концепции подхода изложены, например, в [37].




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



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