🟢 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;

Как это работает:

1. Берём первую строку из users
2. Выполняем подзапрос для этого user_id
3. Берём вторую строку из users
4. Выполняем подзапрос для этого user_id
5. … и так для каждой строки

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

• Когда нужно вычислить что-то для каждой строки отдельно
• Для простых случаев с малыми таблицами
• Часто лучше заменить на 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)

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

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;
   

2. Коррелированный 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);
   

3. Игнорирование 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. Скалярный подзапрос возвращает > 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;
   

2. Скалярный подзапрос возвращает 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. Множественные коррелированные подзапросы

   -- ❌ 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

1. Избегайте скалярных подзапросов в SELECT на больших таблицах
2. EXISTS > IN для проверки существования (Semi-Join)
3. UPDATE FROM / DELETE USING вместо коррелированных подзапросов
4. Оконные функции для агрегации на каждую строку
5. Memoize (PG 14+) может спасти LATERAL — проверяйте Hit rate
6. Индексы на ключах корреляции критичны для SubPlan
7. COALESCE для подзапросов, которые могут вернуть NULL
8. Всегда проверяйте план: ищите 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 в плане