Что такое алгоритм соединения HASH JOIN в SQL?

HASH JOIN — это алгоритм физического соединения (join) таблиц в СУБД, который использует хеш-таблицу для эффективного поиска совпадающих строк. Он часто применяется оптимизатором запросов для соединения больших наборов данных.

Принцип работы (двухэтапный процесс):

1. Build Phase (Фаза построения):

   • СУБД выбирает меньшую из двух таблиц (или результат подзапроса), называемую build input.
   • Она сканирует эту таблицу, вычисляет хеш-значение для ключа соединения (join key) каждой строки и помещает пару (hash_key, row) в хеш-таблицу в памяти.

2. Probe Phase (Фаза проверки):

   • Затем сканируется вторая, большая таблица — probe input.
   • Для каждой её строки также вычисляется хеш ключа соединения.
   • СУБД ищет это хеш-значение в построенной хеш-таблице. При совпадении хешей происходит дополнительная проверка самих ключей (на случай коллизии) и строки объединяются в результат.

Псевдокод, иллюстрирующий логику:

# BUILD PHASE
hash_table = new HashMap()
for row_build in build_table:
    hash_key = hash(row_build.join_key)
    hash_table.insert(hash_key, row_build)

# PROBE PHASE
for row_probe in probe_table:
    hash_key = hash(row_probe.join_key)
    matching_rows = hash_table.lookup(hash_key)
    for matched_row in matching_rows:
        if row_probe.join_key == matched_row.join_key: # Проверка на коллизию
            output(row_probe + matched_row)

Когда HASH JOIN эффективен:

• При соединении больших таблиц, не отсортированных по ключу.
• Когда вся хеш-таблица (build input) помещается в оперативную память.
• Часто используется для операций INNER JOIN и LEFT JOIN при отсутствии индексов.

Ограничения и нюансы:

• Если build input не помещается в память, СУБД использует Grace Hash Join или Recursive Hash Join, записывая части хеш-таблицы на диск, что сильно замедляет процесс.
• Неэффективен для соединений по неравенству (<, >, BETWEEN), только для равенства (=).
• В современных СУБД (PostgreSQL, Oracle, SQL Server) выбор между HASH JOIN, NESTED LOOP и MERGE JOIN делает оптимизатор на основе статистики таблиц.