Я думаю, что каждый, кто хоть немного работал с базами данных сталкивался с задачей выбрать из таблицы только те записи, атрибут которых содержится (или не содержится) в другой таблице. Совершенно банальная на первый взгляд задача, однако она может быть решена несколькими способами.
В 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% совпадения по покупателям.
У нас две банальные задачи:
-
Найти среди всех покупателей из таблицы
customers
тех, кто хоть раз что-то купил. -
Найти среди всех покупателей из таблицы
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
, я убедился в том, что оптимизатор пошел по тому же пути, что и для малой таблицы.
Скрытый текст

Итак, я сделал для себя следующие выводы:
-
Для проверки вхождения нет разницы, какую конструкцию использовать -
exists
илиin
, потому что в большинстве случаев оптимизатор перепишет их в одинаковый план выполнения. -
Проверка вхождения через
join
себя не оправдала. За кадром я пытался найти условия, при которыхjoin
будет работать быстрее других вариантов. Добавлял индексы, менял размеры таблиц и ожидаемую селективность, но каждый раз результат был либо такой же, либо хуже. При этом фильтрация черезjoin
лично для меня выглядит уж совсем не интуитивно, так что я оставлю соединения для соединений. -
Проверка невхождения через
not in
никуда не годится. Нужно стараться избегать этой конструкции, особенно для больших или потенциально больших таблиц.
В целом, результаты этого эксперимента практически полностью совпали с моими ожиданиями. Если бы один из способов имел явные преимущества во всех ситуациях перед другими, то других просто не было бы. Я же для себя задумался о том, чтобы полностью перейти с использования in
на exists
(хоть как по мне он и менее читаем), чтобы сохранить один стиль написания кода для всех ситуаций.
На этом у меня всё, пишите в комментариях, что вы думаете по поводу вышесказанного и делитесь своими best practices нахождения вхождений. Всем спасибо за внимание!
Автор: oldlama