Классика баз данных - статьи
Соединения на основе хэширования
Во множестве прототипных реализаций и академических статей было показано, что алгоритмы соединений на основе хэширования [DeWi85, Schn89] являются предпочтительными при наличии достаточного объема основной памяти и отсутствии индекса, органичивающего число проб на внутренней таблице. Обычно достаточным размером памяти считается квадрат размера внутренней таблицы (в блоках).
Для использование премуществ большого объема основной памяти, распространенной в современных системах, в NonStop SQL поддерживаются алгоритмы соединения на основе хэширования вдобавок к традиционным алгоритмам вложенных циклов и сортировки со слиянием. Используемый в NonStop SQL адаптивный алгоритм соединения на основе хэширования (Adaptive Hash Join algorithm) [Zell90b] является разовидностью хорошо известного гибридного алгоритма соединения с использованием хэширования (Hybrid Hash Join), разработанного в проекте параллельной машины баз данных GAMMA в University of Wisconsin [DeWi85].
Гибридный алгоритм соединения с использованием хэширования в NonStop SQL усовершенствован: он стал более устойчивым к ошибкам оценки размера внутреннего отношения и объему доступной памяти. Это позволяет оптимизатору выбирать соединение хэшированием даже в тех случаях, когда реальные значения этих параметров заранее неизвестны. При выборе алгоритма соединения оптимизатор принимает во внимание, среди прочих, следующий факторы:
- оценку размера входных отношений и
- оценку объема памяти, доступной для соединения.
Эти оценки используются для определения стоимости различных алгоритмов соединения. Выбирается алоритм с наименьшей стоимостью. Соединения методами вложенных циклов и сортировки со слиянием не испытывают деградации эффективности, если реальные значения размеров входных отношений и размера памяти отличаются от оценок оптимизатора. Это связано с тем, что их планы выполнения не зависят от размера таблиц и доступной памяти. Однако для выполнения соединения хэшированием некоторые параметры, такие как число хэш-классов и объем информации, поддерживаемой в основной памяти, являются предопределенными. Изменение условий среды может вызвать деградацию производительности или даже отказ выполнения соединения. В адаптивном алгоритме соединения с хэшированием используется несколько методов, делающих его более надежным и производительным в большом диапазоне размеров основной памяти:
- обмены с дисками порциями переменного размера;
- динамический своппинг частей хэш-таблицы в дисковые файлы;
- алгоритм «hash loop» для случаев предельного переполнения.
Следовательно, адаптивный алгоритм соединения хэшированием может настаиваться на различное потребление памяти в разных точках своего выполнения. Подробности описывются в [Zell90b].
