Что такое HASH JOIN?

HASH JOIN в базах данных

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

Три типа JOIN алгоритмов

1. Nested Loop Join — простой перебор
2. Sort Merge Join — для отсортированных данных
3. Hash Join — для больших таблиц

Как работает HASH JOIN

Фаза 1: Build (Построение таблицы)

Базу данных берёт меньшую таблицу и создаёт в памяти хеш-таблицу по join ключу:

Таблица users:
id | name
---+-------
1  | Alice
2  | Bob
3  | Carol

Шаг 1: Создать хеш-таблицу
Hash Table: {1: Alice, 2: Bob, 3: Carol}

Фаза 2: Probe (Проверка)

Затем проходит по большей таблице и для каждой строки ищет совпадение в хеш-таблице:

Таблица orders:
id | user_id | amount
---+---------+-------
101| 1       | 100
102| 2       | 200
103| 1       | 150

Шаг 2: Для каждой строки orders найти в Hash Table по user_id
order_id 101 -> user_id 1 -> найти в Hash Table -> Alice
order_id 102 -> user_id 2 -> найти в Hash Table -> Bob
order_id 103 -> user_id 1 -> найти в Hash Table -> Alice

SQL Пример

SELECT 
    o.id,
    u.name,
    o.amount
FROM orders o
HASH JOIN users u ON o.user_id = u.id;

В PostgreSQL/MySQL запрос автоматически выбирает HASH JOIN если это оптимально. Явно указать алгоритм обычно нельзя, но можно повлиять на план запроса.

Когда БД выбирает HASH JOIN

Оптимально использовать HASH JOIN когда:

• Одна таблица достаточно большая для создания хеш-таблицы
• Join ключ — простой атрибут (не выражение)
• Нет индекса на join ключе
• Условие join — равенство (=), не диапазон

-- HASH JOIN оптимален
SELECT * FROM orders o
JOIN users u ON o.user_id = u.id;

-- Nested Loop оптимален (если есть индекс на user_id)
SELECT * FROM orders o
JOIN users u ON u.id = o.user_id
WHERE u.id > 100;  -- Фильтрация после индекса

-- Sort Merge оптимален (если обе таблицы отсортированы)
SELECT * FROM orders o
JOIN users u ON o.user_id = u.id
ORDER BY o.user_id;

Производительность HASH JOIN

Сложность:

• Build фаза: O(n) — где n размер меньшей таблицы
• Probe фаза: O(m) — где m размер большей таблицы
• Итого: O(n + m) — линейная сложность!

Nested Loop:

• O(n * m) — квадратичная, очень медленная

Пример производительности:

Таблица users: 100,000 строк
Таблица orders: 1,000,000 строк

Nested Loop: 100,000 * 1,000,000 = 100 миллиардов операций ❌
Hash Join: 100,000 + 1,000,000 = 1.1 миллиона операций ✅

Memory Requirements

Хеш-таблица хранится в памяти (hash buffer):

Если таблица не помещается в памяти, СУБД может:
1. Использовать disk-based hashing (медленнее)
2. Разбить таблицу на партиции (partitioned hashing)

В PostgreSQL:

-- Можно влиять на work_mem (память для операций)
SET work_mem = 1GB;
SELECT * FROM orders JOIN users ON ...;

Примеры из Java приложений

Проверка EXPLAIN PLAN:

@Repository
public class OrderRepository {
    @Autowired
    private JdbcTemplate jdbcTemplate;
    
    public List<OrderDto> getOrdersWithUsers() {
        String sql = "SELECT o.id, u.name, o.amount " +
                     "FROM orders o " +
                     "JOIN users u ON o.user_id = u.id";
        
        // Проверяем execution plan
        List<Map<String, Object>> plan = jdbcTemplate.queryForList(
            "EXPLAIN ANALYZE " + sql
        );
        // Hash Join должен быть в плане для оптимальности
        
        return jdbcTemplate.query(sql,
            new OrderDtoRowMapper());
    }
}

Spring Data JPA:

@Entity
public class Order {
    @Id
    private Long id;
    
    @ManyToOne
    @JoinColumn(name = "user_id")
    private User user;  // JOIN автоматически оптимизируется
}

@Repository
public interface OrderRepository extends JpaRepository<Order, Long> {
    // Используй FETCH JOIN для явного управления JOIN типом
    @Query("SELECT o FROM Order o " +
           "JOIN FETCH o.user u")
    List<Order> findAllWithUsers();
}

Оптимизация запросов с JOIN

1. Добавь индексы на join ключи:

CREATE INDEX idx_orders_user_id ON orders(user_id);
CREATE INDEX idx_users_id ON users(id);

2. Используй EXPLAIN для анализа:

EXPLAIN (ANALYZE, BUFFERS)
SELECT o.*, u.name FROM orders o
JOIN users u ON o.user_id = u.id
WHERE o.created_at > 2024-01-01;

3. Избегай сложных выражений в ON:

-- ❌ Плохо — выражение препятствует использованию индекса
JOIN users u ON LOWER(u.email) = LOWER(o.email)

-- ✅ Хорошо — простое равенство
JOIN users u ON u.id = o.user_id

HASH JOIN vs другие алгоритмы

Вложенный цикл (Nested Loop):

• Быстро для малых таблиц
• Может использовать индексы
• Медленно для больших таблиц

Sort Merge Join:

• Хорош для больших отсортированных наборов
• Может выполнять outer join эффективно
• Требует сортировки (дополнительные затраты)

Hash Join:

• Лучший для больших таблиц без индексов
• Только для inner/left join (обычно)
• Требует достаточно памяти

Понимание HASH JOIN критично для оптимизации сложных SQL запросов в приложении.