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

1. Nested Loops Join:

• Принцип работы:

  Для каждой строки в таблице A:
      Для каждой строки в таблице B:
          Если условие JOIN выполнено → вернуть строку

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

  • Одна из таблиц маленькая (например, < 1000 строк).

  • Есть индексы для быстрого поиска по второй таблице.

• Недостатки:

  • Сложность O(n*m) — медленно для больших таблиц.

2. Hash Join:

• Этапы:

  1. Построение хеш-таблицы: По ключу JOIN из меньшей таблицы.

  2. Проверка: Для каждой строки большей таблицы вычисляется хеш и ищется в хеш-таблице.

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

  • Для больших несортированных таблиц без индексов.

• Ограничения:

  • Требует много памяти.

  • Работает только для условий равенства (=).

3. Merge Join:

• Принцип работы:

  • Одновременный проход по двум отсортированным таблицам (как слияние в сортировке).

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

  • Данные предварительно отсортированы (например, по индексу).

  • Для диапазонных условий (>, <).

Пример выбора алгоритма:

SELECT * 
FROM orders 
JOIN customers ON orders.customer_id = customers.id;

• Если customers маленькая → Nested Loops.

• Если обе таблицы большие → Hash Join.

• Если обе отсортированы по customer_id → Merge Join.