Anti и semi joins на собеседовании Data Engineer

Зачем спрашивают на собесе DE

Anti/semi joins — основа корректной фильтрации по другой таблице. На собесе DE обязательно: «как найти пользователей без заказов», «чем NOT IN отличается от NOT EXISTS», «почему NOT IN лжёт на NULL». Senior — нюансы плана и поведение в распределённых движках.

Главная боль без понимания — DE использовал NOT IN, в подзапросе случился NULL, результат — пустой набор. Аналитика заметила через неделю.

Что такое semi join

Semi join — «найти строки таблицы A, для которых существует хотя бы одна соответствующая строка в B». Возвращает только колонки A, без раздува за счёт дубликатов B.

В стандартном SQL нет ключевого слова SEMI JOIN, но это поведение даёт EXISTS или IN:

-- пользователи, у кого есть хотя бы один заказ
SELECT u.*
FROM users u
WHERE EXISTS (
  SELECT 1 FROM orders o WHERE o.user_id = u.id
);

-- то же через IN
SELECT u.*
FROM users u
WHERE u.id IN (SELECT user_id FROM orders);

В Spark SQL можно явно: SELECT * FROM users LEFT SEMI JOIN orders ON users.id = orders.user_id.

Зачем не INNER JOIN? INNER JOIN с orders раздул бы users по числу заказов. semi-join гарантирует ровно одну строку на user.

Что такое anti join

Anti join — «найти строки A, для которых нет соответствующих в B».

-- пользователи без заказов
SELECT u.*
FROM users u
WHERE NOT EXISTS (
  SELECT 1 FROM orders o WHERE o.user_id = u.id
);

В Spark / Hive: LEFT ANTI JOIN.

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

-- LEFT JOIN + IS NULL
SELECT u.*
FROM users u
LEFT JOIN orders o ON o.user_id = u.id
WHERE o.user_id IS NULL;

-- NOT IN (опасно с NULL — см. ниже)
SELECT u.*
FROM users u
WHERE u.id NOT IN (SELECT user_id FROM orders);

EXISTS vs IN vs JOIN

EXISTS:

• Останавливается на первой найденной строке.
• Корректно работает с NULL.
• Чаще всего оптимально для проверки наличия.

IN с подзапросом:

• Семантически как EXISTS, в Postgres-планировщик обычно их объединяет.
• Опасно с NULL в NOT IN.

JOIN + DISTINCT:

• Может работать, но раздувает данные перед DISTINCT.
• Медленнее на больших B.

-- плохо: раздуем users по числу заказов, потом дедупим
SELECT DISTINCT u.*
FROM users u
JOIN orders o ON o.user_id = u.id;

-- лучше
SELECT u.* FROM users u WHERE EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id);

В современных оптимизаторах (PG 12+, Spark 3+) разница в плане часто стирается, но писать EXISTS — более явный intent.

NOT EXISTS vs NOT IN vs LEFT JOIN ... NULL

Тут — типовая ловушка собеса.

NOT IN с NULL.

SELECT u.*
FROM users u
WHERE u.id NOT IN (SELECT user_id FROM orders);
-- Если в orders.user_id есть NULL → результат полностью пустой

Причина: 1 NOT IN (2, NULL) = 1 != 2 AND 1 != NULL = TRUE AND UNKNOWN = UNKNOWN (не TRUE).

NOT EXISTS — безопасно:

SELECT u.*
FROM users u
WHERE NOT EXISTS (
  SELECT 1 FROM orders o WHERE o.user_id = u.id
);
-- Корректно даже при NULL в orders.user_id

LEFT JOIN ... IS NULL — тоже безопасно:

SELECT u.*
FROM users u
LEFT JOIN orders o ON o.user_id = u.id
WHERE o.user_id IS NULL;

Правило: для anti join всегда NOT EXISTS или LEFT JOIN ... IS NULL. NOT IN — только если железобетонно гарантировано отсутствие NULL.

Производительность в Postgres и Spark

Postgres. Планировщик умеет превращать EXISTS в hash anti/semi join автоматически.

->  Hash Anti Join
      Hash Cond: (u.id = o.user_id)
      ->  Seq Scan on users u
      ->  Hash
            ->  Seq Scan on orders o

Если индекс на orders.user_id — Nested Loop Anti Join по индексу. Хорошо для маленькой users.

Spark. Аналогично — BroadcastHashJoin (LeftAnti) для маленькой правой таблицы или SortMergeJoin (LeftAnti). На больших данных skewed key — узкое место (например, миллион заказов от одного пользователя). Salting помогает.

ClickHouse. Поддерживает ANTI JOIN и SEMI JOIN с версии 22+. Полезно для больших анти-фильтров: LEFT ANTI JOIN отрабатывает быстрее, чем эмуляция через NOT IN.

Частые ошибки

NOT IN с подзапросом, в котором может быть NULL. Самая популярная ловушка. Лечение: NOT IN (SELECT user_id FROM orders WHERE user_id IS NOT NULL) или замена на NOT EXISTS.

SELECT * FROM EXISTS подзапрос. В EXISTS можно SELECT 1 или SELECT * — оптимизатор умный, но писать стоит SELECT 1 для ясности.

Anti join через NOT EXISTS без коррелирующего условия. NOT EXISTS (SELECT 1 FROM orders) — проверяет, есть ли вообще заказы (не привязано к user). Всегда добавляй WHERE o.user_id = u.id.

LEFT JOIN без IS NULL для anti. Без IS NULL это обычный LEFT JOIN — все строки A с заказами и без, плюс их полная история.

Считать, что DISTINCT после JOIN бесплатен. На миллиардах строк JOIN раздувает, потом DISTINCT тратит ресурсы. EXISTS обычно дешевле.

IN для больших списков. WHERE id IN (1, 2, ..., 100000) — query parser задыхается. Использовать JOIN с временной таблицей или ANY (ARRAY[...]).

Игнорировать индекс на правой колонке anti join. Без индекса на orders.user_id — sequential scan правой таблицы при каждом probe для Nested Loop. Hash Anti Join обходит, но индекс всё равно полезен.

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

• SQL для Data Engineer: собеседование
• LAG и LEAD на собесе DE
• EXPLAIN и план запроса для DE
• Recursive CTE на собесе DE
• Подготовка к собесу Data Engineer

FAQ

EXCEPT — это anti join?

Близко: SELECT id FROM users EXCEPT SELECT user_id FROM orders даст id из users, отсутствующих в orders. Но EXCEPT работает по всем колонкам и убирает дубли. Anti join гибче — может фильтровать по сложному условию.

EXISTS останавливается на первой строке?

Да, как только нашёл одну строку — возвращает TRUE. На индексированной правой это очень быстро.

Что такое CORRELATED subquery?

Подзапрос, ссылающийся на колонку внешней. EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id) — коррелирует с u. Современные оптимизаторы умеют разворачивать в join.

NOT IN можно сделать безопасным?

Да: NOT IN (SELECT user_id FROM orders WHERE user_id IS NOT NULL). Но NOT EXISTS понятнее и не требует помнить про NULL.

Spark LEFT ANTI vs Postgres NOT EXISTS?

Семантически идентично. Spark позволяет явно прописать в JOIN-конструкции, Postgres делает trans automatically.

Это официальная информация?

Нет. Статья основана на стандарте SQL:1992, документации Postgres 14+, Spark 3.x и ClickHouse 23+.

Тренируйте Data Engineering — откройте тренажёр с 1500+ вопросами для собесов.