Руководство по созданию эффективных запросов

54

Еще больше теории: алгоритмы
Алгоритмы на основе хеширования
Результат естественного соединения состоит из пар строк из таблиц 
R
и 
S
, 
которые имеют равные значения атрибутов, по которым выполняется со-
единение. Идея алгоритма соединения хешированием проста: если значения 
равны, то и хеш-значения тоже равны.
Алгоритм разбивает обе входные таблицы по корзинам в соответствии со 
значениями хеш-функции, а затем независимо соединяет строки в каждой 
корзине. Схема этого алгоритма показана на рис. 3.9.
Корзины 
Рис. 3.9 

Алгоритм соединения хешированием
Базовая версия алгоритма соединения хешированием включает две фазы:
1) на этапе 
построения
все кортежи таблицы 
R
сохраняются в корзинах 
согласно значениям хеш-функции;
2) на этапе 
проверки
каждая строка таблицы 
S
направляется в соответ-
ствующую ей корзину. Если подходящие строки таблицы 
R
находятся 
в этой корзине, порождаются выходные строки.
Самый простой способ найти подходящие строки в корзине – использовать 
вложенные циклы (фактически нужно перебирать все строки в корзине для 
каждой строки таблицы 
S
).
Две фазы алгоритма на основе хеширования показаны как отдельные фи-
зические операции в плане выполнения.
Стоимость соединения хешированием приблизительно можно оценить по 
следующей формуле, где 
JA
– атрибут, по которому выполняется соединение:
cost(hash,R,S) = size(R) + size(S) + size(R)*size(S)/size(JA)
Первое и второе слагаемые в этой формуле приблизительно равны стоимо-
сти одного прохода по всем строкам таблиц 
R
и 
S
. Последнее слагаемое обо-
значает размер порождаемого результата соединения. Конечно, стоимость 
вывода одинакова для всех алгоритмов соединения, но нам не нужно было 
включать его в оценку стоимости алгоритма вложенного цикла, потому что 
она меньше, чем стоимость вложенных циклов.

---

Сочетание отношений 

55
Эта формула показывает, что алгоритм на основе хеширования значитель-
но лучше вложенных циклов подходит для больших таблиц и большого коли-
чества различных значений атрибута соединения. Например, если атрибут 
соединения в одной из входных таблиц уникален, то последнее слагаемое 
всего лишь будет равно размеру другой таблицы.
Базовый алгоритм соединения хешированием работает, если все корзины, 
созданные на этапе построения хеш-таблицы, помещаются в оперативную 
память. Другой вариант, называемый гибридным соединением хеширова-
нием, соединяет таблицы, которые не могут поместиться в оперативную 
память. Гибридное соединение хешированием разделяет обе таблицы так, 
чтобы отдельные разделы помещались в память, а затем выполняет базовый 
алгоритм для каждой пары соответствующих разделов. Стоимость гибридно-
го соединения хешированием выше, потому что разделы временно хранятся 
на жестком диске и обе таблицы сканируются дважды. Однако стоимость по-
прежнему пропорциональна сумме размеров таблиц, а не их произведению.