🟢 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