Що таке корельований підзапит?

🟢 Junior Level

Корельований підзапит — це підзапит, який залежить від значень зовнішнього запиту. Він виконується для кожного рядка зовнішнього запиту.

Навіщо це розуміти: такі підзапити виглядають елегантно та інтуїтивно зрозумілі, але на великих таблицях можуть паралізувати базу даних — підзапит виконується для кожного рядка зовнішнього запиту, що дає складність O(N × M).

Проста аналогія: Уявіть, що ви перевіряєте кожен документ у папці. Для кожного документа ви відкриваєте окрему папку і шукаєте там пов’язані файли. Це як цикл у коді: для кожного елемента → виконати пошук.

Приклад:

-- Для кожного користувача знайти його останнє замовлення
SELECT u.name,
       (SELECT o.amount
        FROM orders o
        WHERE o.user_id = u.id  -- ← залежить від зовнішнього рядка!
        ORDER BY o.created_at DESC
        LIMIT 1) as last_order
FROM users u;

Як це працює:

Беремо перший рядок з users
Виконуємо підзапит для цього user_id
Беремо другий рядок з users
Виконуємо підзапит для цього user_id
… і так для кожного рядка

Коли використовувати:

Коли потрібно обчислити щось для кожного рядка окремо
Для простих випадків з малими таблицями
Часто краще замінити на JOIN або віконні функції

🟡 Middle Level

Логічна модель виконання

Класична модель: O(N × M) — підзапит виконується N разів (за числом рядків зовнішнього запиту).

-- Корельований підзапит в SELECT
SELECT u.name,
       (SELECT SUM(amount) FROM orders o WHERE o.user_id = u.id) as total
FROM users u;

-- Логічно це:
for user in users:              -- 1,000,000 рядків
    total = SELECT SUM(amount)  -- Виконується 1,000,000 разів!
        FROM orders
        WHERE user_id = user.id
    print(user.name, total)

Фізична реальність: Декореляція

PostgreSQL намагається «розгорнути» корельовані підзапити:

-- Вихідний запит
SELECT * FROM users u
WHERE EXISTS (
    SELECT 1 FROM orders o WHERE o.user_id = u.id AND amount > 100
);

-- Після декореляції:
-- Plan: Hash Semi-Join (виконується ОДИН раз для всіх рядків!)
-- Складність: O(N + M) замість O(N × M)

SubPlan vs InitPlan в EXPLAIN

SubPlan — виконується для кожного рядка (погано):

EXPLAIN SELECT u.name,
       (SELECT SUM(amount) FROM orders o WHERE o.user_id = u.id)
FROM users u;

-- Plan:
-- Seq Scan on users
--   SubPlan 1
--     -> Aggregate
--        -> Index Scan on orders
-- ⚠️ SubPlan 1 виконується для кожного рядка users!

InitPlan — виконується один раз (добре):

EXPLAIN SELECT * FROM users
WHERE amount > (SELECT AVG(amount) FROM orders);

-- Plan:
-- InitPlan 1
--   -> Aggregate (AVG)
--      -> Seq Scan on orders
-- → Seq Scan on users
-- ✅ InitPlan виконується 1 раз!

Корельовані підзапити в UPDATE та DELETE

Це часта причина повільних операцій:

-- ❌ ПОГАНО: корельований підзапит в UPDATE
UPDATE orders o SET status = 'OLD'
WHERE created_at < (
    SELECT MIN(created_at)
    FROM users u
    WHERE u.id = o.user_id
);
-- Для кожного замовлення → підзапит!

-- ✅ ДОБРЕ: UPDATE з FROM (JOIN-подібний синтаксис)
UPDATE orders o SET status = 'OLD'
FROM users u
WHERE o.user_id = u.id
  AND o.created_at < u.min_created_at;
-- Plan: Hash Join (набагато швидше!)

EXISTS: Важливі нюанси

-- Ці два запити ЕКВІВАЛЕНТНІ в PostgreSQL:
EXISTS (SELECT 1 FROM orders WHERE user_id = u.id)
EXISTS (SELECT * FROM orders WHERE user_id = u.id)
EXISTS (SELECT amount FROM orders WHERE user_id = u.id)

-- Оптимізатор ігнорує SELECT list всередині EXISTS
-- Йому важливий лише факт наявності хоча б одного рядка
-- Пишіть так, як прийнято у вашій команді (зазвичай SELECT 1)

Типові помилки

Скалярний підзапит в SELECT на великих даних

-- ❌ 1 млн користувачів → 1 млн підзапитів
SELECT u.name,
       (SELECT COUNT(*) FROM orders WHERE user_id = u.id) as orders_count
FROM users u;

-- ✅ Замініть на JOIN + GROUP BY
SELECT u.name, COUNT(o.id) as orders_count
FROM users u
LEFT JOIN orders o ON u.id = o.user_id
GROUP BY u.id, u.name;

Корельований UPDATE без індекса

-- ❌ Якщо orders.user_id не індексований → Seq Scan в циклі!
UPDATE users u SET total_orders =
    (SELECT COUNT(*) FROM orders o WHERE o.user_id = u.id);

-- ✅ Спочатку створіть індекс
CREATE INDEX idx_orders_user_id ON orders(user_id);

Ігнорування Memoize (PG 14+)

-- На PG 14+ з Memoize може бути швидко навіть з LATERAL
-- Перевіряйте EXPLAIN, не оптимізуйте завчасно

Альтернативи

Ситуація	Корельований підзапит	Альтернатива
Агрегація для кожного рядка	Підзапит в SELECT	JOIN + GROUP BY
Пошук одного значення	Підзапит з LIMIT 1	LATERAL JOIN
Перевірка існування	Підзапит в WHERE	EXISTS (Semi-Join)
Складна логіка на рядок	Корельований підзапит	Віконні функції

Практичний приклад

-- ❌ Корельований підзапит (повільно)
SELECT u.name,
       (SELECT AVG(amount) FROM orders WHERE user_id = u.id) as avg_amount
FROM users u
WHERE (SELECT AVG(amount) FROM orders WHERE user_id = u.id) > 100;

-- ✅ Віконна функція (швидко)
-- Віконна функція робить один прохід по даних з сортуванням: O(N log N).
-- Корельований підзапит виконує окремий запит для кожного рядка:
-- O(N × M). На таблиці з 1 млн рядків це 1 млн окремих запитів
-- проти одного проходу — різниця в сотні та тисячі разів.
SELECT name, avg_amount
FROM (
    SELECT u.name,
           AVG(o.amount) OVER(PARTITION BY u.id) as avg_amount
    FROM users u
    INNER JOIN orders o ON u.id = o.user_id
) sub
WHERE avg_amount > 100;

🔴 Senior Level

Фізичні механізми виконання

1. SubPlan (наївний)

Для кожного рядка зовнішнього запиту:
  → Виконати підзапит
  → Повернути результат

Складність: O(N × M)

2. InitPlan (незалежний)

Один раз перед основним запитом:
  → Обчислити підзапит
  → Зберегти результат

Основний запит використовує результат
Складність: O(M) + O(N)

3. Param (корельований, але оптимізований)

Підзапит приймає параметр із зовнішнього рядка
→ Може використати індекс за параметром
→ Може бути кешований (Memoize)

Декореляція (Unnesting)

Оптимізатор намагається перетворити корельований підзапит на JOIN:

-- Вихідний: корельований EXISTS
SELECT * FROM users u
WHERE EXISTS (
    SELECT 1 FROM orders o WHERE o.user_id = u.id AND o.amount > 100
);

-- Після декореляції:
-- Hash Semi-Join
--   Hash Cond: (o.user_id = u.id)
--   Hash Filter: (o.amount > 100)

-- Складність: O(N + M) замість O(N × M)!

Коли декореляція НЕ можлива:

Підзапит містить LIMIT / OFFSET
Підзапит містить агрегати із залежністю від зовнішнього рядка
Підзапит містить ORDER BY без декорельованого ключа

Memoize Node (PostgreSQL 14+)

Революційна оптимізація для корельованих запитів:

-- Запит з LATERAL (вимусений Nested Loop)
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 1
) o ON true;

-- Plan з Memoize (PG 14+):
-- Nested Loop
--   → Seq Scan on users
--   → Memoize (cache_size: 10MB)
--       → Limit
--          → Index Scan Backward on orders

-- Memoize кешує:
--   user_id = 1 → amount = 500
--   user_id = 2 → amount = 300
--   user_id = 1 → HIT! (беремо з кешу)

Метрики Memoize:

Memoize (cost=... rows=...)
  Hits: 950,000     ← взято з кешу
  Misses: 50,000    ← обчислено заново
  Evictions: 5,000  ← витіснено з кешу (нестача місця)

Hit rate = 950,000 / 1,000,000 = 95% → відмінно!
Hit rate < 50% → Memoize не допомагає (занадто багато унікальних ключів)

Обмеження Memoize:

Кеш обмежений пам’яттю (параметр memoize_cache_size, за замовчуванням 10MB)
Працює лише в межах одного вузла Nested Loop
Не допомагає, якщо всі ключі унікальні (0% повторів)

Корельовані UPDATE/DELETE: Глибокий аналіз

Проблема:

UPDATE orders o SET status = 'OLD'
WHERE created_at < (
    SELECT MIN(created_at)
    FROM users u
    WHERE u.id = o.user_id
);

Що відбувається:

for order in orders:                      -- 100,000,000 рядків
    min_date = SELECT MIN(created_at)     -- 100,000,000 підзапитів!
        FROM users
        WHERE id = order.user_id
    if order.created_at < min_date:
        UPDATE order SET status = 'OLD'

Рішення через UPDATE FROM:

-- Крок 1: Передобчислюємо мінімум один раз
WITH user_min_dates AS (
    SELECT user_id, MIN(created_at) as min_date
    FROM users
    GROUP BY user_id
)
-- Крок 2: JOIN замість підзапиту
UPDATE orders o SET status = 'OLD'
FROM user_min_dates umd
WHERE o.user_id = umd.user_id
  AND o.created_at < umd.min_date;

-- План:
-- CTE Scan on user_min_dates
--   → HashAggregate (1 раз)
-- Hash Join
--   → Seq Scan on orders
--   → Hash on user_min_dates
-- Разом: 2 проходи замість 100,000,000!

EXISTS та NULL: Міфи

-- Міф: SELECT 1 швидший за SELECT *
-- Реальність: ОПТИМІЗАТОР ІГНОРУЄ SELECT LIST в EXISTS

EXPLAIN EXISTS (SELECT 1 FROM orders WHERE user_id = 1);
EXPLAIN EXISTS (SELECT * FROM orders WHERE user_id = 1);
EXPLAIN EXISTS (SELECT amount, created_at FROM orders WHERE user_id = 1);

-- Усі три дають ІДЕНТИЧНИЙ план!
-- Пишіть SELECT 1 для читабельності (семантично ясно, що перевіряємо наявність)

Віконні функції як альтернатива

-- ❌ Корельований підзапит для кожного рядка
SELECT o.*,
       (SELECT AVG(amount)
        FROM orders o2
        WHERE o2.user_id = o.user_id) as user_avg
FROM orders o;

-- ✅ Віконна функція (один прохід!)
SELECT o.*,
       AVG(amount) OVER(PARTITION BY user_id) as user_avg
FROM orders o;

-- Різниця:
-- Підзапит: O(N × M) — для кожного рядка шукаємо всі замовлення користувача
-- Віконна: O(N log N) — один прохід з сортуванням/хешуванням

Edge Cases

Скалярний підзапит повертає > 1 рядок

-- ❌ Помилка: more than one row returned by a subquery used as an expression
SELECT u.name,
       (SELECT amount FROM orders WHERE user_id = u.id) -- 10 замовлень!
FROM users u;

-- ✅ LIMIT 1 або агрегація
SELECT u.name,
       (SELECT amount FROM orders WHERE user_id = u.id ORDER BY created_at DESC LIMIT 1)
FROM users u;

Скалярний підзапит повертає NULL

-- Якщо підзапит не знайшов рядків → NULL
SELECT u.name,
       (SELECT amount FROM orders WHERE user_id = u.id LIMIT 1)
FROM users u;
-- У користувачів без замовлень → NULL

-- ⚠️ NULL в арифметиці → NULL
SELECT u.name,
       (SELECT SUM(amount) FROM orders WHERE user_id = u.id) + 10
FROM users u;
-- Без замовлень: NULL + 10 = NULL!
-- Рішення: COALESCE

Множинні корельовані підзапити

-- ❌ 3 підзапити на рядок → 3N виконань
SELECT u.name,
       (SELECT COUNT(*) FROM orders WHERE user_id = u.id) as orders_count,
       (SELECT SUM(amount) FROM orders WHERE user_id = u.id) as total_amount,
       (SELECT MAX(created_at) FROM orders WHERE user_id = u.id) as last_order
FROM users u;

-- ✅ Один JOIN + GROUP BY
SELECT u.name,
       COUNT(o.id) as orders_count,
       COALESCE(SUM(o.amount), 0) as total_amount,
       MAX(o.created_at) as last_order
FROM users u
LEFT JOIN orders o ON u.id = o.user_id
GROUP BY u.id, u.name;

Performance Comparison

Підхід	Складність	Коли використовувати
SubPlan	O(N × M)	Уникайте на великих даних
InitPlan	O(M) + O(N)	Підзапит не залежить від зовнішнього рядка
Decorrelated (Semi-Join)	O(N + M)	EXISTS / IN з декореляцією
Memoize (PG 14+)	O(N × log M) з кешем	LATERAL з повторами ключів
Window Function	O(N log N)	Агрегація для кожного рядка
UPDATE FROM	O(N + M)	Корельований UPDATE

Production Experience

Реальний сценарій #1: SubPlan паралізує БД

CRM система: для кожного контакту рахуємо суму угод
Запит: скалярний підзапит в SELECT (50 000 контактів)
Час: 12 хвилин (50 000 підзапитів до orders)
EXPLAIN: SubPlan 1 → Index Scan (виконується 50,000 разів)

Рішення:

SELECT c.*, COALESCE(SUM(o.amount), 0) as total_deals
FROM contacts c
LEFT JOIN orders o ON c.id = o.contact_id
GROUP BY c.id;

Результат: 800ms (прискорення в 900 разів)

Реальний сценарій #2: Memoize рятує LATERAL

API: останні 3 замовлення для кожного клієнта (100 000 клієнтів)
LATERAL без Memoize (PG 13): > 3 хвилин
LATERAL з Memoize (PG 14): 2 секунди
Memoize: Hits = 98%, Misses = 2% (багато клієнтів повторюються в кеші)

Реальний сценарій #3: Корельований UPDATE

E-commerce: позначити старі замовлення (100 млн рядків)
UPDATE з корельованим підзапитом: > 8 годин

Рішення: UPDATE FROM + CTE

WITH cutoff_dates AS (
    SELECT user_id, MIN(created_at) + INTERVAL '1 year' as cutoff
    FROM users
    GROUP BY user_id
)
UPDATE orders o SET status = 'ARCHIVED'
FROM cutoff_dates cd
WHERE o.user_id = cd.user_id
  AND o.created_at < cd.cutoff;

Результат: 15 хвилин (прискорення в 32 рази)

Monitoring

-- 1. Пошук SubPlan в планах
EXPLAIN (ANALYZE, BUFFERS)
SELECT u.name, (SELECT COUNT(*) FROM orders WHERE user_id = u.id)
FROM users u;

-- Шукайте:
-- "SubPlan" → виконується для кожного рядка
-- "InitPlan" → виконується один раз

-- 2. Перевірка ефективності Memoize
EXPLAIN (ANALYZE)
SELECT ... LATERAL ...;

-- Memoize (actual rows=...)
--   Hits: 500000
--   Misses: 10000
--   Evictions: 500
-- Hit rate = Hits / (Hits + Misses)

-- 3. Пошук корельованих підзапитів в pg_stat_statements
SELECT query, mean_exec_time, calls
FROM pg_stat_statements
WHERE query ~ '\(SELECT.*WHERE.*=.*\)'
  AND query LIKE '%SELECT%'
ORDER BY mean_exec_time DESC
LIMIT 10;

-- 4. Перевірка UPDATE з підзапитами
SELECT query FROM pg_stat_activity
WHERE query LIKE 'UPDATE%'
  AND query LIKE '%SELECT%';

Best Practices

Уникайте скалярних підзапитів в SELECT на великих таблицях
EXISTS > IN для перевірки існування (Semi-Join)
UPDATE FROM / DELETE USING замість корельованих підзапитів
Віконні функції для агрегації на кожен рядок
Memoize (PG 14+) може врятувати LATERAL — перевіряйте Hit rate
Індекси на ключах кореляції критичні для SubPlan
COALESCE для підзапитів, які можуть повернути NULL
Завжди перевіряйте план: шукайте SubPlan vs InitPlan

Резюме для Senior

SubPlan = виконується для кожного рядка → O(N × M) → уникайте
InitPlan = виконується один раз → O(M) + O(N) → відмінно
Декореляція перетворює SubPlan на Semi-Join → O(N + M)
Memoize (PG 14+) кешує результати LATERAL → перевіряйте Hits/Misses
Віконні функції — найкраща альтернатива для агрегації на рядок
UPDATE FROM / DELETE USING — завжди швидше корельованих підзапитів
EXISTS ігнорує SELECT list — пишіть SELECT 1 для читабельності
Моніторте: EXPLAIN (ANALYZE), шукайте SubPlan, перевіряйте Hit rate Memoize

🎯 Шпаргалка для співбесіди

Обов’язково знати:

Корельований підзапит залежить від зовнішнього рядка → виконується для кожного рядка
SubPlan = O(N × M) → катастрофа на великих даних
InitPlan = O(M) + O(N) → обчислюється один раз
Декореляція: оптимізатор перетворює підзапит на Hash Semi-Join → O(N + M)
Декореляція НЕ можлива при LIMIT, OFFSET, агрегатах із зовнішньою залежністю
Memoize (PG 14+): кешує результати → Hit rate > 80% = відмінно
EXISTS = Semi-Join: зупиняється після першого збігу, немає дублів
Скалярний підзапит в SELECT → JOIN + GROUP BY краще
UPDATE FROM / DELETE USING → Hash Join замість N підзапитів
Віконні функції: O(N log N) замість O(N × M) для агрегації на рядок

Часті уточнюючі питання:

«Як знайти SubPlan в плані?» → Шукайте SubPlan в EXPLAIN (виконується для кожного рядка)
«Коли Memoize марний?» → Усі ключі унікальні → 0% Hits
«Чому EXISTS кращий за JOIN для перевірки існування?» → Немає Join Amplification
«Як прискорити корельований UPDATE?» → UPDATE FROM + CTE

Червоні прапорці (НЕ говорити):

❌ «Корельований підзапит — норма для великих таблиць» (SubPlan = катастрофа!)
❌ «SELECT * в EXISTS повільніший за SELECT 1» (оптимізатор ігнорує SELECT list)
❌ «Memoize завжди врятує» (потрібні повторювані ключі)
❌ «LATERAL JOIN завжди хороший» (Nested Loop → тільки для малих зовнішніх)

Пов’язані теми:

[[Що краще: JOIN чи підзапит]] → Unnesting, Decorrelation
[[Які типи JOIN існують]] → Semi-Join, Hash Join
[[Що таке віконні функції]] → альтернатива для агрегації на рядок
[[Що таке explain plan]] → пошук SubPlan в плані