[Перевод] Визуализируем и разбираемся с Hash Match Join
Этот пост является третьей частью серии, посвященной операторам соединения (обязательно прочитайте часть 1 — nested loops joins, и часть 2 — merge joins). Перевод статьи подготовлен специально для студентов курса «MS SQL Server разработчик».
Hash Match Joins — это надежные рабочие лошадки физических операторов соединения.
В то время как Nested Loops Join завершится неудачей, если данных будет слишком много для того, чтобы поместить их в память, а Merge Join потребует, чтобы входные данные были отсортированы, Hash Match соединит любые данные, которые вы подадите на вход (при условии что для соединения выполняется предикат равенства и пока в вашем tempdb достаточно свободного места).
Смотрите видео по теме на YouTube
Алгоритм hash match состоит из двух этапов, которые работают следующим образом:
Во время первого этапа «Build» (построение), SQL Server создает в памяти хеш-таблицу из одной из таблиц, поданных на вход (обычно наименьшей из двух). Хеши вычисляются на основе ключей входных данных и затем сохраняются вместе со строкой в хеш-таблице в соответствующий блок. В большинстве случаев в каждом блоке имеется только одна строка данных, кроме случаев, когда:
- Есть строки с дублирующими ключами.
- Хеш-функция создает коллизию, и совершенно разные ключи получают один и тот же хеш (это редко, но возможно).
После создания хеш-таблицы, начинается этап «Probe» (проверка). На втором этапе SQL Server вычисляет хэш ключа для каждой строки во второй входной таблице и проверяет, существует ли он в хеш-таблице, созданной на первом этапе. Если находится совпадение для этого хеша, то проверяется, действительно ли совпадают ключи строки (строк) в хеш-таблице и строки из второй таблицы (эту проверку необходимо выполнять из-за возможных коллизий).
Распространенный вариант алгоритма hash match возникает, когда на этапе построения не удается создать хеш-таблицу, которая может быть полностью сохранена в памяти:
Это происходит, когда данных больше, чем может быть размещено в памяти, или когда SQL Server предоставляет недостаточно памяти для hash match соединения.
Когда у SQL Server не хватает памяти для хранения хэш-таблицы на этапе построения, он продолжает работать, сохраняя некоторые блоки в памяти, а другие блоки помещая в tempdb.
На этапе проверки SQL Server соединяет строки данных из второй таблицы в блоки из этапа построения, находящиеся в памяти. Если блок, которому эта строка потенциально соответствует, в данный момент отсутствует в памяти, SQL Server записывает эту строку в tempdb для последующего сравнения.
Когда совпадения для одного блока завершены, SQL Server очищает эти данные из памяти и загружает следующие блоки в память. Затем он сравнивает строки второй таблицы (в настоящее время находящиеся в tempdb) с новыми блоками в памяти.
Как и в случае с каждым оператором физического соединения в этой серии, подробности об операторе hash match можно найти в справке Хьюго Корнелиса (Hugo Kornelis) о hash match.
Что показывает Hash Match Join?
Знание внутренних особенностей того, как работает 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 joins отлично подходят для больших соединений, поскольку они могут передаваться в tempdb, это позволяет им выполнять соединения с большими наборами данных, которые могут привести к сбою соединения в памяти с помощью nested loops или merge join операторов.
- Если вы видите оператор hash match join, то это означает, что SQL Server считает, что входные данные слишком велики. Если мы знаем, что наши входные данные не должны быть такими большими, то стоит проверить, есть ли проблемы со статистикой или оценкой, из-за которых SQL Server неправильно выбирает hash match join.
- При выполнении в памяти, hash match join довольно эффективен. Проблемы возникают, когда этап построения переходит в tempdb.
- Если я замечаю маленький желтый треугольник, указывающий, что соединение переходит в tempdb, я смотрю, почему это произошло: если данных больше, чем доступно памяти, здесь мало что можно сделать, но если выделенная память кажется неоправданно малой, это может означать, что у нас, вероятно, есть еще одна проблема со статистикой, которая приводит к слишком низким оценкам оптимизатора SQL Server.
Спасибо за то, что прочитали статью. Вам также может понравиться мой Twitter.
Мы касались этой темы на предыдущем открытом уроке. Ждем ваши комментарии!
