Детали применения Hash Match Join

Пересказ статьи Bert Wagner. Visualizing Hash Match Join Internals And Understanding Their Implications

Hash Match Joins (соединения при поиске совпадений в хэше) — надежные рабочие лошадки в среде физических операторов соединения.

В то время как Nested Loops joins потерпит неудачу, если данные слишком велики для хранения в памяти, а Merge Joins требует, чтобы входные данные были отсортированы, Hash Match будет соединять два любых входа (пока соединение выполняется по равенству значений, и в tempdb достаточно свободного пространства).

В общих чертах алгоритм hash match имеет две фазы, которые работают следующим образом.
Во время первой фазы «Build» (построение), SQL Server строит в памяти хэш-таблицу из одного входа (обычно меньшего из двух). Хэши вычисляются на основе ключей соединения входных данных, а затем сохраняются вместе со строкой в хэш-таблице в хэш-блоке, связанном с хэш-ключом. По большей части в одном хэш-блоке хранится только одна строка данных, за исключением следующих случаев:

1. Имеются строки с дубликатами ключей соединения.
2. Хэш-функция создает коллизию, и в целом различные ключи соединения имеют один и тот же хэш (не всегда, но бывает).

Как только хэш-таблица построена, SQL Server начинает фазу «Probe» (проверок). Во время этой второй фазы SQL Server вычислят хэш-ключ соединения для каждой строки во втором входе и проверяет существование его в хэш-таблице, созданной на первой фазе построения. Если он находит совпадение с этим хэшем, то сравнивает ключи соединения между строкой (строками) в хэш-таблице и строкой из второй таблицы на фактическое совпадение значений (это необходимо из-за потенциальных проблем с коллизиями).

Имеется общая вариация алгоритма hash match, когда фаза построения не может создать хэш-таблицу, полностью помещающуюся в память.

Это происходит, когда данных больше, чем может поместиться в память, или когда SQL Server выделяет недостаточное количество памяти, требуемое для hash match join.

Когда SQL Server не имеет достаточно памяти для сохранения хэш-таблицы на фазе построения, он сохраняет несколько блоков в памяти, сбрасывая остальные блоки в tempdb.

Во время фазы проверки SQL Server соединяет строки данных из второго входа с блоками, построенных в памяти на первом этапе. Если блок, с которым строка потенциально совпадает, не находится в данный момент в памяти, SQL Server записывает эту строку в tempdb для дальнейшего сравнения.

Как только поиск совпадений для одного блока завершен, SQL Server стирает эти данные из памяти и загружает следующий блок (блоки) в память. Затем он сравнивает строки второго входа (находящиеся сейчас в tempdb) с новыми блоками в памяти.

О чем говорит Hash Match Joins

Знание того, как работает Hash Match Join, позволяет нам понять, что оптимизатор думает о наших данных и операторах восходящих потоков соединения. Это помогает нам сосредоточить усилия на настройке производительности.

Вот несколько сценариев, которые вам следует принять во внимание, когда вы встретите hash match join в плане выполнения своего запроса:

  • Хотя hash match join позволяют соединять огромные наборы данных, построение хэш-таблицы из первого входа является блокирующей операцией, которая будет препятствовать выполнению операторов нисходящих потоков. Из-за этого я всегда проверяю, имеется ли простой способ преобразовать hash match либо в nested loops, либо в merge join. Иногда это невозможно (слишком много строк для nested loops или неотсортированные данные для merge join), но всегда полезно проверить, можно ли простым изменением индекса или улучшенными оценками обновленной статистики заставить SQL Server выбрать неблокирующий оператор hash match join.
  • Hash match join отлично подходит для больших соединений — поскольку они могут быть сброшены в tempdb, это позволяет выполнять соединения на больших наборах данных, которые потерпели бы неудачу при соединении в памяти при использовании либо nested loops, либо merge join операторов.
    • Наличие в плане оператора hash match join означает, что SQL Server думает, что восходящие входные потоки велики. Если вы знаете, что ваши входы не должны быть большими, то полезно проверить, нет ли у вас проблемы со статистикой/оценкой, которая вынуждает SQL Server ошибочно выбрать hash match join.
  • При выполнении в памяти соединения hash match join довольно эффективны. Проблемы возникают, когда фаза построения использует tempdb.
    • Если я замечаю небольшой желтый треугольник, указывающий, что соединение сбрасывается в tempdb, то всегда смотрю причину: если объем данных превышает доступную для сервера память, тут мало что можно сделать, но если выделение памяти кажется необычно маленьким, это может означать, что мы имеем еще одну проблему со статистикой, которая приводит к слишком низким оценкам оптимизатора SQL Server.

Добавить комментарий