Классика баз данных - статьи
с хэшированием разбивает большое соединение
Алгоритм соединения с хэшированием разбивает большое соединение на множество мелких соединений. При выборе хорошей хэш-функции и наличии не слишком больших перекосах в данных размеры блоков, содержащих кортежи с одинаковым значением хэш-функции, отличаются незначительно. В этих случаях соединение с хэшированием представляет собой линейный по времени алгоритм соединения с линейными ускорением и масштабируемостью. За последнее десятилетие появилось множество оптимизаций параллельного алгоритма соединения с хэшированием. В случае патологических перекосов, когда многие или все кортежи имеют то же самое значение атрибута, один блок может содержать все кортежи. Алгоритм, способный обеспечить ускорение и масштабируемость в этих случаях, не известен.
Пример соединения с хэшированием показывает, что новые параллельные алгоритмы могут улучшать производительность реляционных операторов. Это благодатная область для исследований [4, 8, 18, 20, 25, 26, 38, 39]. Хотя параллелизм может быть достигнут на основе традиционных последовательных реляционных алгоритмов при помощи операторов расщепления и слияния, мы надеемся, что в будущем будут изобретены многие новые алгоритмы.
