По материалам статьи Craig Freedman: Hash Join
Когда Вы встречаете случай использования оператора Hash Join (хэш-соединение), это говорит о наличии тяжелого запроса. В отличие то соединения Nested Loops Join, которое хорошо для относительно маленьких наборов данных, и от соединения Merge Join, которое помогает при умеренных размерах наборов данных, хэш-соединение превосходит другие типы соединений при необходимости соединения огромных наборов данных. Хэш-соединения распараллеливается и масштабируется лучше любого другого соединения и сильно выигрывает при большой производительности информационных хранилищ (я вернусь к обсуждению параллельного выполнения запросов в следующей серии статей).
Хэш-соединение имеет много общего с соединением слиянием. Подобно соединению слиянием, для него требуются не менее одного предиката объединения по эквивалентности, оно поддерживает остаточные предикаты, а также все внешние соединения и полусоединения. В отличие от соединения слиянием, для него не требуется наличие упорядоченных входных потоков и для поддержки полного внешнего соединения требуется наличие предиката соединения по эквивалентности.
Алгоритм
Хэш-соединение выполняется в две стадии: компоновка и проба. Во время компоновки осуществляется чтение всех строк первого входного потока (часто, его называют левым потоком или потоком компоновки), хеширование строк по ключам соединения эквивалентности и создание в оперативной памяти хеш-таблицы. Во время пробы осуществляется чтение всех строк второго входного потока (часто его называют правым потоком или пробным потоком), хеширование строк этого потока по тем же ключам соединения эквивалентности, а потом осуществляется просмотр или поиск соответствий строк в хеш-таблице. Так как хеш-функции могут быть подвержены коллизиям (два разных значения ключа имеют одинаковый хэш), приходится проверять каждое потенциальное соответствие, что необходимо для гарантии того, что в этом случае действительно совпадение обусловлено соединением, а не коллизией.
Алгоритм в псевдокоде:
|
for each row R1 in the build table begin calculate hash value on R1 join key(s) insert R1 into the appropriate hash bucket end for each row R2 in the probe table begin calculate hash value on R2 join key(s) for each row R1 in the corresponding hash bucket if R1 joins with R2 return (R1, R2) end |
Обратите внимание, что в отличие от вложенных циклов и слияния, которые немедленно начинают выдавать результат, хэш-соединение блокируют вывод до окончания компоновки. То есть вначале должны быть полностью прочитан и обработан поток компоновки, и только потом могут быть возвращены какие-либо строки. Кроме того, в отличие от других методов соединения, хэш-соединение требует предоставления памяти для хранения хеш-таблиц. Таким образом, существует предел числа параллельных хэш-соединений, которые SQL Server может поддерживать в какой то момент времени. Хотя эти ограничения не являются проблемой для информационных хранилищ, они могут оказаться нежелательными для большинства OLTP приложений.
Память и сброс на диск
До начала выполнения хэш-соединения, SQL Server пытается оценить, сколько памяти потребуется для хеш-таблиц. Выполняется оценка кардинальности элементов для размера потока компоновки, базирующаяся на ожидаемом среднем размере строк, что позволяет оценить требующийся объем и конфигурацию памяти. Для уменьшения задействуемой хэш-соединением памяти, в качестве таблицы потока компоновки выбирается самая маленькая из двух таблиц. После этого выполняется попытка резервирования такого объёма памяти, который бы гарантировал успешное выполнение хэш-соединения.
Что же случается, если хэш-соединению будет предоставлено меньше памяти, чем было запрошено, или если оценка оказалось слишком низкой? В этих случаях, на стадии компоновки хэш-соединение может выйти за пределы памяти. Если хэш-соединение вышло за пределы памяти, начинается сброс на диск небольшого процента от всей хеш-таблицы (во временный объект tempdb). Хэш-соединение следит, какие разделы хеш-таблицы все еще находятся в памяти, а какие были сброшены на диск. Поскольку каждая новая строка читается из таблицы компоновки, можно легко проверить, является ли она хэшем раздела в оперативной памяти, или она находиться в разделе на диске. Если это хэш в оперативной памяти, всё происходит по обычной схеме. Если это хэш на дисковом разделе, осуществляется запись строки на диск. Этот процесс позволяет управлять превышением памяти и сбросом разделов на диск, и он может занимать много времени, до тех пор, пока стадия компоновки не будет закончена.
Подобный процесс исполняется во время стадии пробы. Для каждой новой строки из таблицы пробного потока выполняется проверка, является ли она хэшем раздела в оперативной памяти или на диске. Если это хэш раздела в оперативной памяти, берутся пробы из хеш-таблицы, генерируются соответствующие условиям соединения строки, и после этого строка отбрасывается. Если это хэш раздела на диске, осуществляется запись строки на диск. Как только будет завершен первый проход таблицы пробного потока, процесс возвращается поочерёдно к другим разделам, которые были сброшены на диск, считывает в память строки потока компоновки, восстанавливает хеш-таблицу для каждого из разделов, и затем считывает соответствующее разделы пробного потока, завершая соединение.
Сравнение Left Deep, Right Deep и Bushy - деревьев хэш-соединений
Эти термины относятся к форме плана исполнения запроса, что проиллюстрировано на этом рисунке:
Форма дерева соединения особенно важна для хэш-соединений, поскольку от этого зависит потребление памяти.
В густом слева дереве, выходной поток одного хэш-соединения является входным потоком компоновки следующего хэш-соединения. Поскольку хэш-соединения должны получить весь входной поток компоновки до того, как начнётся стадия проб, в густом слева дереве активными одновременно могут быть только смежные пары хэш-соединений. Например, на показанном выше рисунке всё начинается с построения хеш-таблицы для HJ1. Когда HJ1 перейдёт на стадию проб, становится возможным использовать выходной поток HJ1, который нужен для формирования хеш-таблиц для HJ2. Когда HJ1 прошёл стадию проб, используемая для хеш-таблиц память может быть освобождена. Только после этого можно начинать стадию проб для HJ2 и строить хеш-таблицу для HJ3. Таким образом, HJ1 и HJ3 никогда не будут активны одновременно и поэтому могут использовать одно и то же распределение памяти. Полный объем необходимой памяти займёт: max(HJ1 + HJ2, HJ2 + HJ3).
В густом справа дереве, выходной поток одного хэш-соединения является входным пробным потоком следующего хэш-соединения. Все хэш-соединения должны полностью сформировать свои хеш-таблицы до того, как начнётся стадия проб. Все хэш-соединения активны одновременно и не могут использовать одну и ту же память совместно. Когда начинается стадия проб, поток строк заполняет дерево хэш-соединений, без использования блокировок. Таким образом, полный объем необходимой памяти будет равен: HJ1 + HJ2 + HJ3.
Примеры
Следующие примеры используют эту схему:
create table T1 (a int, b int, x char(200))
create table T2 (a int, b int, x char(200))
create table T3 (a int, b int, x char(200))
set nocount on
declare @i int
set @i = 0
while @i < 1000
begin
insert T1 values (@i * 2, @i * 5, @i)
set @i = @i + 1
end
declare @i int
set @i = 0
while @i < 10000
begin
insert T2 values (@i * 3, @i * 7, @i)
set @i = @i + 1
end
declare @i int
set @i = 0
while @i < 100000
begin
insert T3 values (@i * 5, @i * 11, @i)
set @i = @i + 1
end
Начнём с простого примера:
select *
from T1 join T2 on T1.a = T2.a |
Rows Executes 334 1 |--Hash Match(Inner Join, HASH:([T1].[a])=([T2].[a]),RESIDUAL:([T2].[a]=[T1].[a])) 1000 1 |--Table Scan(OBJECT:([T1])) 10000 1 |--Table Scan(OBJECT:([T2])) |
Обратите внимание, что у T2 строк в десять раз больше чем у T1, и поэтому оптимизатор использует T1 в качестве таблицы потока компоновки, а T2 в качестве таблицы пробного потока.
Теперь рассмотрим соединение трёх таблиц:
select *
from (T1 join T2 on T1.a = T2.a)
join T3 on T1.b = T3.a|
Rows Executes 334 1 |--Hash Match(Inner Join, HASH:([T1].[b])=([T3].[a]),RESIDUAL:([T1].[b]=[T3].[a])) 334 1 |--Hash Match(Inner Join, HASH:([T1].[a])=([T2].[a]),RESIDUAL:([T1].[a]=[T2].[a])) 1000 1 | |--Table Scan(OBJECT:([T1])) 10000 1 | |--Table Scan(OBJECT:([T2])) 100000 1 |--Table Scan(OBJECT:([T3])) |
Обратите внимание, что оптимизатор выбрал план с густым слева деревом. Сначала соединяются две маленькие таблицы, T1 и T2. Результаты этого соединения выдаёт всего 334 строки, которые используются для формирования хеш-таблицы перед соединением с большой таблицей T3.
Теперь посмотрим, что случится, если добавить предикат, ограничивающий размер меньшей из двух таблиц (единственным условием для оптимизатора может быть: "T2.a < 100" from "T1.a < 100" and "T1.a = T2.a").
|
Rows Executes 17 1 |--Hash Match(Inner Join, HASH:([T2].[a])=([T1].[a]),RESIDUAL:([T1].[a]=[T2].[a])) 34 1 |--Table Scan(OBJECT:([T2]), WHERE:([T2].[a]<(100))) 50 1 |--Hash Match(Inner Join, HASH:([T1].[b])=([T3].[a]),RESIDUAL:([T1].[b]=[T3].[a])) 50 1 |--Table Scan(OBJECT:([T1]), WHERE:([T1].[a]<(100))) 100000 1 |--Table Scan(OBJECT:([T3])) |
На сей раз оптимизатор для плана выбрал густое справа дерево. T1 и T2 теперь настолько малы (34 и 50 строк), что лучше формировать хеш-таблицу по этим двум таблицам, а на стадии проб использовать большую таблицу T3, формируя хеш-таблицу на промежуточном уровне хэш-соединения.
Что далее?
После того, как я закончил краткий обзор трёх операторов соединения, в следующих статьях я планирую резюмировать некоторые характеристики этих операторов и показать несколько примеров того, как ведёт себя SQL Server при некоторых вариантах соединений таблиц.
DrunkBear
Мораль сей басни такова: не пытайтесь угадать, хватит ли памяти под хэши.
Нужен быстрый и частый join по полям, особенно текстовым?
Сделайте отдельную колонку с хэшем.
Ну а если не частый - хотя бы CTE с хэшем.