Я думаю, что каждый, кто хоть немного работал с базами данных сталкивался с задачей выбрать из таблицы только те записи, атрибут которых содержится (или не содержится) в другой таблице. Совершенно банальная на первый взгляд задача, однако она может быть решена несколькими способами.

В PostgreSQL все три конструкции (NOT) IN, (NOT) EXISTS и JOIN могут выполнить поставленную задачу. В своей жизни я сталкивался с разными утверждениями - кто-то говорил, что всегда нужно использовать exists ведь "он работает до первого совпадения, а значит быстрее", кто-то утверждал, что фильтрация через join "на несколько порядков быстрее", а кто-то вообще не знал про варианты, отличные от in.

Чтобы сравнить на практике все три варианта я воссоздал, как мне кажется, две самые типичные ситуации - сравнить исходную таблицу с меньшей по объему и ожидаемой низкой селективностью и с большей по объему и ожидаемой высокой селективностью.

Итак, мой "стенд":

drop table if exists customers;
CREATE TABLE customers (
	customer_id serial4 PRIMARY KEY,
	customer_name text NULL
);

INSERT INTO customers (customer_name)
SELECT md5(random()::text)
FROM generate_series(1, 1000000);

drop table if exists transactions;
CREATE TABLE transactions (
	customer_id int4 NULL,
	transaction_id int4 NULL
);

INSERT INTO transactions (customer_id, transaction_id)
SELECT random()*800000, random()*-100000000
FROM generate_series(1, 100000000);

drop table if exists vip_customers;
CREATE TABLE vip_customers (
	customer_id int4 NULL
);

INSERT INTO vip_customers (customer_id)
SELECT random()*1000000
FROM generate_series(1, 10000);

analyze customers;
analyze transactions;
analyze vip_customers;

У нас имеется таблица покупателей с миллионом записей, таблица VIPов с 10 тыс. записей и таблица покупок со 100 млн. записей. У таблицы покупок умышленно "срезаны" 200 тыс. айдишников, чтобы не иметь 100% совпадения по покупателям.

У нас две банальные задачи:

1. Найти среди всех покупателей из таблицы customers тех, кто хоть раз что-то купил.

2. Найти среди всех покупателей из таблицы customers всех VIPов.

Начнём с малого и найдем всех VIPов:

explain analyze
select customer_id from customers 
where 
exists (select customer_id from vip_customers where vip_customers.customer_id = customers.customer_id)

explain analyze
select customer_id from customers 
where customer_id in (select customer_id from vip_customers)

explain analyze
select customer_id from customers 
join (select distinct customer_id from vip_customers) tr using (customer_id)

Выше представлены все три варианта отбора customer_id. Что же мы видим в результате? Оказывается, все три запроса имеют абсолютно идентичные планы выполнения:

Скрытый текст

В целом ничего странного в этом нет. SQL – декларативный язык. Это значит, что в отличие от большинства других языков программирования, мы описываем желаемый результат, а не даем конкретные инструкции к выполнению. Раз результат этих операций одинаков, разумно предположить, что и план их выполнения будет одинаковым. На этой веселой ноте мы двигаемся дальше.

А дальше нам необходимо выбрать всех "активных" покупателей:

explain analyze
select customer_id from customers 
where 
exists (select customer_id from transactions where transactions.customer_id = customers.customer_id)

explain analyze
select customer_id from customers 
where customer_id in (select customer_id from transactions)

explain analyze
select customer_id from customers 
join (select distinct customer_id from transactions) tr using (customer_id)

Планы выполнения этих запросов уже немного интереснее:

Скрытый текст

Первые два запроса дают одинаковый план выполнения, но тут появляется интересный элемент. Мы можем видеть Semi Join - это так называемое "полусоединение". Оно возвращает строки из таблицы 1, для которых есть хотя бы одна строка из таблицы 2 с совпадающими значениями в соединяемых столбцах. Мы не можем вызвать его явно, но постгрес использует его для фильтрации. Интересно, что это соединение предполагает за собой удаление дубликатов, хоть мы и не видим этого явно в плане запроса. В результате нам вернется количество строк не превышающее изначальное количество строк в таблице 1. Запрос же с явным join по умолчанию не предполагает удаление дубликатов. Поэтому в запросе нам приходится использовать distinct, иначе записи задублировались бы на каждую совпадающую операцию из таблицы transactions . Это можно явно увидеть на 14 строчке из плана выполнения третьего запроса.

Что же по самой методике? В случае фильтрации через join у нас уже не происходит полусоединения в плане запроса. Мы видим типичную картину соединения слиянием (помним про наличие индекса на customer_id в таблице customers). В такой реализации фильтрация через join проигрывает по времени выполнения первым двум вариантам.

Интересно, но тема на этом не исчерпана. Ведь еще у нас есть проверка на невхождение. Итак, повторим наши эксперименты, в этот раз добавив ключевые слова not в первые два запроса и немного переписав третий запрос

Начнем с маленькой таблицы:

explain analyze
select customer_id from customers 
where 
not exists (select customer_id from vip_customers where vip_customers.customer_id = customers.customer_id)

explain analyze
select customer_id from customers 
where customer_id not in (select customer_id from vip_customers)

explain analyze
select customer_id from customers 
left join (select distinct customer_id from vip_customers) tr using (customer_id)
where tr.customer_id is null

И вот тут картина перестаёт быть банальной. Какие ваши предположения? Будут ли все три плана одинаковые как в случае с вхождением? Или первые два будут идентичные, а join опять найдет свой путь, как в случае с большой таблицей?

Оба варианта не верны, планы представлены под спойлером ниже:

Скрытый текст

В этот раз похожие планы выполнения у запросов один и три. Здесь используется еще один тип соединения – Anti Join. По сути это противоположность Semi Join. Оно возвращает строки из таблицы 1 для которых в таблице 2 нет строк с совпадающим значением в столбце соединения. На самом деле это хорошо - антисоединение основной механизм для определения невхождений. Прекрасно, что оптимизатор распознал нашу кастомную конструкцию с left join и фильтрацией и переписал её на антисоединение.

Что же с not in? Здесь мы видим последовательное сканирование и применение банальной фильтрации. На малой таблице разницы в скорости нет, да и увидеть её здесь просто невозможно.

Перейдем к завершающей части нашего эксперимента. Проверим невхождение на большой таблице:

explain analyze
select customer_id from customers 
where 
not exists (select customer_id from transactions where transactions.customer_id = customers.customer_id)

explain analyze
select customer_id from customers 
where customer_id not in (select customer_id from transactions)

explain analyze
select customer_id from customers 
left join (select distinct customer_id from transactions) tr using (customer_id)
where tr.customer_id is null

Планы выполнения представлены под катом. И да, это не ошибка, что их только два:

Скрытый текст

Первый и третий запросы пришли к использованию Anti Join. А вот запрос с not in видимо опять пытался обойтись последовательным сканированием и фильтрацией. После 10 минут ожидания я решил прервать выполнение запроса, но сделав просто explain, я убедился в том, что оптимизатор пошел по тому же пути, что и для малой таблицы.

Скрытый текст

Итак, я сделал для себя следующие выводы:

1. Для проверки вхождения нет разницы, какую конструкцию использовать - exists или in, потому что в большинстве случаев оптимизатор перепишет их в одинаковый план выполнения.

2. Проверка вхождения через join себя не оправдала. За кадром я пытался найти условия, при которых join будет работать быстрее других вариантов. Добавлял индексы, менял размеры таблиц и ожидаемую селективность, но каждый раз результат был либо такой же, либо хуже. При этом фильтрация через join лично для меня выглядит уж совсем не интуитивно, так что я оставлю соединения для соединений.

3. Проверка невхождения через not in никуда не годится. Нужно стараться избегать этой конструкции, особенно для больших или потенциально больших таблиц.

В целом, результаты этого эксперимента практически полностью совпали с моими ожиданиями. Если бы один из способов имел явные преимущества во всех ситуациях перед другими, то других просто не было бы. Я же для себя задумался о том, чтобы полностью перейти с использования in на exists (хоть как по мне он и менее читаем), чтобы сохранить один стиль написания кода для всех ситуаций.

На этом у меня всё, пишите в комментариях, что вы думаете по поводу вышесказанного и делитесь своими best practices нахождения вхождений. Всем спасибо за внимание!