🟢 Junior Level

JOIN — это операция, которая объединяет строки из двух или более таблиц на основе условия связи.

Зачем: базы данных нормализуются — данные хранятся в отдельных таблицах (пользователи отдельно, заказы отдельно) для избежания дублирования и аномалий при записи. JOIN позволяет «склеить» их обратно при чтении, когда нужно увидеть связанную информацию.

Простая аналогия: Представьте, что у вас есть два списка:

• Список учеников с их ID
• Список оценок с ID ученика

JOIN позволяет соединить эти списки и увидеть: “Иванов (ID=1) — оценка 5, Петров (ID=2) — оценка 4”.

Основные типы JOIN:

Тип	Описание	Пример
INNER JOIN	Только строки, где есть совпадение в обеих таблицах	“Показать заказы и клиентов, которые их сделали”
LEFT JOIN	Все строки из левой таблицы + совпадения из правой	“Показать всех клиентов, даже без заказов”
RIGHT JOIN	Все строки из правой + совпадения из левой	Редко используется
FULL JOIN	Все строки из обеих таблиц	“Показать всех клиентов и все заказы, даже если нет совпадений”
CROSS JOIN	Все со всеми (декартово произведение)	“Сгенерировать все комбинации”

Пример:

-- INNER JOIN: только заказы с клиентами
SELECT u.name, o.amount
FROM users u
INNER JOIN orders o ON u.id = o.user_id;

-- LEFT JOIN: все пользователи, даже без заказов
SELECT u.name, o.amount
FROM users u
LEFT JOIN orders o ON u.id = o.user_id;
-- Если заказов нет → o.amount = NULL

Когда использовать:

• INNER JOIN — когда нужны только связанные данные
• LEFT JOIN — когда нужны все записи из основной таблицы
• CROSS JOIN — редко, для генерации комбинаций

---

🟡 Middle Level

Физические стратегии выполнения (Execution Plan)

PostgreSQL использует три алгоритма для выполнения JOIN:

1. Nested Loop Join

Для каждой строки из таблицы A:
  → Ищем совпадения в таблице B (по индексу)

• Когда используется: Одна таблица маленькая, в другой есть индекс
• Сложность: O(N × log M) с индексом
• Пример: 100 пользователей → для каждого ищем заказы по индексу

2. Hash Join

1. Строим хэш-таблицу из меньшей таблицы
2. Сканируем большую таблицю, ищем совпадения в хэше

• Когда используется: Большие таблицы, нет подходящего индекса
• Требует: work_mem для хранения хэш-таблицы (work_mem — параметр PostgreSQL, определяющий сколько памяти может выделить одна операция до сброса на диск; по умолчанию 4MB)
• Сложность: O(N + M)

3. Merge Join

1. Сортируем обе таблицы по ключу JOIN
2. Сливаем как два отсортированных массива

• Когда используется: Данные уже отсортированы (по индексу)
• Сложность: O(N log N + M log M) для сортировки, потом O(N + M)

Продвинутые логические типы

Semi-Join (EXISTS):

-- Показать пользователей, у которых есть заказы
SELECT * FROM users u
WHERE EXISTS (
    SELECT 1 FROM orders o WHERE o.user_id = u.id
);
-- Plan: Hash Semi-Join (останавливается после первого совпадения)
-- Semi-Join эффективнее обычного JOIN: как только найдено ПЕРВОЕ совпадение
-- для строки левой таблицы, сканирование правой прекращается.
-- Обычный JOIN вернёт ВСЕ совпадения (если у пользователя 100 заказов — 100 строк),
-- а потом DISTINCT их схлопнет. Semi-Join сразу вернёт пользователя один раз.

Anti-Join (NOT EXISTS):

-- Показать пользователей БЕЗ заказов
SELECT * FROM users u
WHERE NOT EXISTS (
    SELECT 1 FROM orders o WHERE o.user_id = u.id
);
-- Plan: Hash Anti-Join

Lateral Join:

-- Для каждого пользователя найти 3 последних заказа
SELECT u.name, o.amount
FROM users u
LEFT JOIN LATERAL (
    SELECT amount FROM orders o
    WHERE o.user_id = u.id
    ORDER BY created_at DESC
    LIMIT 3
) o ON true;
-- Как «flatmap» в программировании: для каждой строки из левой таблицы
-- выполняется подзапрос, и его результаты «разворачиваются» в итоговую таблицу.
-- Если подзапрос вернул 3 заказа — в результате будет 3 строки для этого пользователя.

Типичные ошибки

1. Использование JOIN вместо EXISTS

   -- ❌ Может дублировать строки, если у пользователя много заказов
   SELECT DISTINCT u.* FROM users u
   JOIN orders o ON u.id = o.user_id;
      
   -- ✅ EXISTS эффективнее (останавливается после первого совпадения)
   SELECT * FROM users u
   WHERE EXISTS (
       SELECT 1 FROM orders o WHERE o.user_id = u.id
   );
   

2. NOT IN с NULL

   -- ❌ Если в orders есть NULL → вернёт пустой результат!
   SELECT * FROM users
   WHERE id NOT IN (SELECT user_id FROM orders);
      
   -- ✅ Всегда используйте NOT EXISTS
   SELECT * FROM users u
   WHERE NOT EXISTS (
       SELECT 1 FROM orders o WHERE o.user_id = u.id
   );
   

3. Забытый ON → CROSS JOIN

   -- ❌ Забыли условие → декартово произведение!
   SELECT * FROM users u JOIN orders o;
   -- 1000 users × 10000 orders = 10,000,000 строк!
   

Hash Join и work_mem

-- Если хэш-таблица не помещается в work_mem → сброс на диск
EXPLAIN ANALYZE SELECT * FROM orders o
JOIN users u ON o.user_id = u.id;

-- Если видите: "Batches: 4" → хэш не поместился в память
-- Решение: увеличить work_mem для сессии
SET work_mem = '256MB';

Практическое сравнение

JOIN	Когда использовать	Стратегия
INNER + индексы	Маленькая + большая с индексом	Nested Loop
INNER без индексов	Две большие таблицы	Hash Join
INNER + отсортированные	Данные отсортированы	Merge Join
LEFT JOIN	Нужно сохранить все из левой	Зависит от данных
EXISTS	Проверка существования	Semi-Join
LATERAL	Зависимые подзапросы	Nested Loop

---

🔴 Senior Level

Логические vs Физические JOIN

Логические JOIN — это то, что вы пишете в SQL:

• INNER, LEFT, RIGHT, FULL, CROSS

Физические JOIN — это то, как PostgreSQL их выполняет:

• Nested Loop, Hash, Merge, Semi, Anti

Важно: Оптимизатор может трансформировать логические JOIN в физические по-разному!

Nested Loop Join

Механизм:

for row_a in table_a:           -- Outer (Driving)
    for row_b in table_b:       -- Inner (Probed)
        if match(row_a, row_b):
            emit(row_a, row_b)

Оптимальные условия:

• Внешняя таблица: < 10,000 строк
• Внутренняя таблица: индекс по ключу JOIN
• Селективность: высокая

Сложность:

• Без индекса: O(N × M) — катастрофа на больших данных
• С индексом: O(N × log M) — отлично

Hash Join

Механизм:

-- Phase 1: Build
for row in smaller_table:
    hash_table[hash(join_key)] = row

-- Phase 2: Probe
for row in larger_table:
    if hash(join_key) in hash_table:
        emit(row, hash_table[hash(join_key)])

Оптимальные условия:

• Обе таблицы большие
• Нет подходящего индекса
• Равенство в условии JOIN (=)

Batches (когда не помещается в work_mem):

Если хэш-таблица > work_mem:
  1. Разбиваем данные на batches
  2. Каждый batch обрабатывается отдельно
  3. Batches сбрасываются на диск (temp_files)
  → Сильное замедление!

Мониторинг:

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM a JOIN b ON a.id = b.a_id;
-- Hash Join (cost=... rows=...)
--   Batches: 8  ← плохо!
--   Memory Usage: 256MB
--   Disk Spill: 2GB  ← очень плохо!

Merge Join

Механизм:

sort(table_a by join_key)
sort(table_b by join_key)

ptr_a = 0, ptr_b = 0
while ptr_a < len(a) and ptr_b < len(b):
    if a[ptr_a].key == b[ptr_b].key:
        emit(a[ptr_a], b[ptr_b])
        ptr_a++, ptr_b++
    elif a[ptr_a].key < b[ptr_b].key:
        ptr_a++
    else:
        ptr_b++

Оптимальные условия:

• Данные уже отсортированы (по индексу)
• Большие объёмы данных
• Условие JOIN: =, <, >, <=, >=

GEQO (Genetic Query Optimizer)

При > 12 таблиц в одном запросе (параметр geqo_threshold):

• Полный перебор вариантов Join Reordering становится слишком дорогим
• PostgreSQL переключается на генетический алгоритм
• Может выбрать неоптимальный план!

Решение:

-- Увеличить порог (больше вариантов рассмотрит, но дольше планирование)
SET geqo_threshold = 20;

-- Или отключить GEQO (осторожно!)
SET geqo = off;

Join Reordering и OUTER JOIN

INNER JOIN: Ассоциативен и коммутативен

(A JOIN B) JOIN C = A JOIN (B JOIN C) = (A JOIN C) JOIN B

Планировщик может переставлять таблицы для поиска оптимального плана.

LEFT JOIN: НЕ ассоциативен

(A LEFT JOIN B) LEFT C ≠ A LEFT JOIN (B LEFT JOIN C)

Планировщик ограничен в перестановках → может привести к субоптимальному плану.

Outer Join Removal (PG 10+)

Оптимизация: PostgreSQL может удалить ненужный LEFT JOIN:

-- LEFT JOIN будет удалён, если:
-- 1. Не выбираем колонки из правой таблицы
-- 2. Ключ в правой таблице UNIQUE/PRIMARY KEY

SELECT u.name FROM users u
LEFT JOIN orders o ON u.id = o.user_id;
-- orders удалён из плана! (o не используется в SELECT)

Мониторинг через EXPLAIN:

EXPLAIN SELECT u.name FROM users u
LEFT JOIN orders o ON u.id = o.user_id;
-- Seq Scan on users (последовательное чтение всей таблицы) ← orders НЕТ в плане!
-- Внешний JOIN удалён из плана оптимизатором (Outer Join Removal)

Edge Cases

1. Join Amplification

   -- ❌ Если у пользователя 10 заказов, он появится 10 раз!
   SELECT u.name, o.amount
   FROM users u
   JOIN orders o ON u.id = o.user_id;
      
   -- ✅ Группируем или используем EXISTS
   SELECT u.name, SUM(o.amount)
   FROM users u
   JOIN orders o ON u.id = o.user_id
   GROUP BY u.name;
   

2. Join Collapse Limits

   -- Параметры, влияющие на оптимизацию JOIN
   SHOW from_collapse_limit;    -- По умолчанию: 8
   SHOW join_collapse_limit;    -- По умолчанию: 8
      
   -- Если > 8 подзапросов/JOIN → планировщик не будет их "расплющивать"
   -- Может привести к субоптимальному плану
   

3. Lateral Join и Nested Loop

   -- Lateral почти всегда выбирает Nested Loop
   -- Отлично для малых внешних выборок
   -- Катастрофа для больших!
      
   -- ✅ users = 100 → быстро
   SELECT * FROM users u
   LEFT JOIN LATERAL (
       SELECT * FROM orders o WHERE o.user_id = u.id LIMIT 3
   ) o ON true;
      
   -- ❌ users = 1,000,000 → медленно
   

Performance Tuning

work_mem для Hash Join:

-- Проверка текущего значения
SHOW work_mem;  -- По умолчанию: 4MB

-- Для конкретных запросов (осторожно!)
SET work_mem = '256MB';
SELECT * FROM large_table a JOIN large_table b ON a.id = b.a_id;
RESET work_mem;

-- ⚠️ work_mem выделяется НА ОПЕРАЦИЮ, не на сессию!
-- 10 параллельных Hash Join × 256MB = 2.5GB RAM!

enable_* флаги (для отладки):

-- Временно отключить стратегию для тестирования
SET enable_hashjoin = off;  -- Проверить Nested Loop
SET enable_mergejoin = off; -- Проверить Hash Join
SET enable_nestloop = off;  -- Проверить Hash/Merge

-- ⚠️ ТОЛЬКО для отладки! Не в production!
EXPLAIN ANALYZE SELECT ...;

-- Вернуть назад
RESET enable_hashjoin;

Production Experience

Реальный сценарий #1: Hash Join Disk Spill

• Аналитическая платформа: JOIN таблиц с 50 млн и 100 млн строк
• Проблема: Запрос > 5 минут
• EXPLAIN ANALYZE: Hash Join, Batches: 32, Disk Spill: 8GB
• Причина: work_mem = 4MB (по умолчанию)
• Решение: SET work_mem = '512MB' для сессии
• Результат: Запрос < 30 секунд (ускорение в 10 раз)

Реальный сценарий #2: GEQO выбирает плохой план

• Отчёт: JOIN 15 таблиц
• Проблема: Запрос 2 минуты вместо ожидаемых 5 секунд
• Причина: GEQO (генетический алгоритм) выбрал плохой порядок JOIN
• Решение:
  • Разбили запрос на 2 CTE
  • Уменьшили количество JOIN в одном запросе до 8
• Результат: Запрос < 3 секунд

Реальный сценарий #3: Lateral Join на больших данных

• API: Для каждого из 1 млн пользователей найти последний заказ
• Запрос с LATERAL > 10 минут
• Решение: Заменили на Window Function

  -- ✅ Window Function вместо LATERAL
  SELECT * FROM (
      SELECT *, 
             ROW_NUMBER() OVER(PARTITION BY user_id ORDER BY created_at DESC) as rn
      FROM orders
  ) sub WHERE rn = 1;
  

• Результат: Запрос < 5 секунд

Monitoring

-- 1. Проверка используемых стратегий JOIN
SELECT query, call_count, mean_exec_time
FROM pg_stat_statements
WHERE query LIKE '%JOIN%'
ORDER BY mean_exec_time DESC
LIMIT 10;

-- 2. Анализ конкретного запроса
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT) 
SELECT * FROM orders o
JOIN users u ON o.user_id = u.id
WHERE o.created_at > '2024-01-01';

-- 3. Проверка work_mem USAGE
-- В логах PostgreSQL при нехватке:
-- "temporary file: path ..., size ..."

-- 4. Проверка GEQO
SELECT query FROM pg_stat_activity
WHERE query LIKE '%JOIN%JOIN%JOIN%JOIN%JOIN%JOIN%JOIN%JOIN%JOIN%JOIN%JOIN%JOIN%JOIN%';
-- > 12 JOIN → возможно GEQO

Best Practices

1. EXISTS вместо DISTINCT JOIN для проверки существования
2. NOT EXISTS вместо NOT IN (избегайте NULL ловушки)
3. LATERAL только для малых внешних выборок (< 10,000 строк)
4. work_mem увеличивайте для конкретных запросов с Hash Join
5. Следите за Batches в EXPLAIN — если > 1, увеличивайте work_mem
6. Избегайте > 12 JOIN в одном запросе (GEQO)
7. Индексы на полях JOIN критичны для Nested Loop
8. Разбивайте сложные запросы через CTE для лучшего контроля

Резюме для Senior

• 3 физических стратегии: Nested Loop (малые + индекс), Hash (большие без индекса), Merge (отсортированные)
• GEQO при > 12 таблиц → может выбрать плохой план
• Batches > 1 в Hash Join → увеличивайте work_mem
• Outer Join Removal (PG 10+) может удалить ненужный JOIN
• LATERAL ≈ Nested Loop → только для малых внешних выборок
• NOT EXISTS > NOT IN (NULL-безопасность)
• EXISTS > DISTINCT JOIN (Semi-Join эффективнее)
• Всегда проверяйте план через EXPLAIN (ANALYZE, BUFFERS)

---

🎯 Шпаргалка для интервью

Обязательно знать:

• 5 логических JOIN: INNER, LEFT, RIGHT, FULL, CROSS
• 3 физических стратегии: Nested Loop, Hash, Merge
• Nested Loop: O(N × log M) с индексом, отлично для малых + индекс
• Hash Join: O(N + M), требует work_mem, Batches > 1 → spill на диск
• Merge Join: требует отсортированные данные, O(N + M) после сортировки
• GEQO при > 12 таблиц → генетический алгоритм → может выбрать плохой план
• LATERAL ≈ Nested Loop → только для < 10,000 внешних строк
• Semi-Join (EXISTS) эффективнее DISTINCT JOIN (нет дублей)

Частые уточняющие вопросы:

• «Почему Hash Join медленный?» → Batches > 1 → disk spill → увеличьте work_mem
• «Когда Nested Loop лучше Hash Join?» → Внешняя таблица малая + индекс на внутренней
• «Что такое GEQO и почему это плохо?» → Генетический алгоритм при > 12 таблиц → субоптимальный план
• «Когда LATERAL JOIN оправдан?» → Малая внешняя таблица + индекс на внутренней

Красные флаги (НЕ говорить):

• ❌ «JOIN всегда быстрее подзапроса» (зависит от декорреляции)
• ❌ «work_mem не важен для JOIN» (Hash Join требует work_mem!)
• ❌ «LATERAL JOIN решит всё» (только для малых внешних выборок!)
• ❌ «NOT IN безопасен» (NULL вернёт пустой результат!)

Связанные темы:

• [[В чём разница между INNER JOIN и LEFT JOIN]] → логические vs физические JOIN
• [[Что лучше JOIN или подзапрос]] → Semi-Join, декорреляция
• [[Для чего нужны индексы]] → индексы на полях JOIN
• [[Что такое коррелированный подзапрос]] → EXISTS vs JOIN