Как выполняются JOIN на физическом уровне (алгоритмы: nested loops, hash join)?

Question

Основные алгоритмы:Nested Loops: Для маленьких таблиц. Сравнивает каждую строку первой таблицы со всеми строками второй.Hash Join: Для больших таблиц. Строит хеш-таблицу по одной таблице, ищет совпадения во второй.Merge Join: Для предварительно отсортированных данных. Проходит по обеим таблицам за один проход.

YeaHub · Accepted Answer

1. Nested Loops Join:Принцип работы:Для каждой строки в таблице A:
    Для каждой строки в таблице B:
        Если условие JOIN выполнено → вернуть строкуКогда эффективен:Одна из таблиц маленькая (например, < 1000 строк).Есть индексы для быстрого поиска по второй таблице.Недостатки:Сложность O(n*m) — медленно для больших таблиц.2. Hash Join:Этапы:Построение хеш-таблицы: По ключу JOIN из меньшей таблицы.Проверка: Для каждой строки большей таблицы вычисляется хеш и ищется в хеш-таблице.Когда эффективен:Для больших несортированных таблиц без индексов.Ограничения:Требует много памяти.Работает только для условий равенства (=).3. Merge Join:Принцип работы:Одновременный проход по двум отсортированным таблицам (как слияние в сортировке).Когда эффективен:Данные предварительно отсортированы (например, по индексу).Для диапазонных условий (>, <).Пример выбора алгоритма:SELECT * 
FROM orders 
JOIN customers ON orders.customer_id = customers.id;Если customers маленькая → Nested Loops.Если обе таблицы большие → Hash Join.Если обе отсортированы по customer_id → Merge Join.