Тестовое задание от компании Mercaux
В этой статье разберем задание от компании Mercaux на знание PostgreSQL и Java. Найдем все возможные решения и выберем лучшее на базе анализа результата команды EXPLAIN.
Задача
В sql базе данных есть таблица product_recommendation(id, product_id1, product_id2)
, где id - primary key, а две других колонки - foreign key на таблицу product (вид которой для задачи не важен), всё колонки integer. В таблице несколько миллионов записей.
В Java приложении есть массив или любая коллекция (на ваш выбор) из 100000 айдишников продуктов (тоже integer). Нужно получить список всех рекомендаций (строчек из таблицы product_recommendation
), у которых product_id1
НЕ из этого списка.
Укажите основные шаги в решении поставленной задачи и напишите основной SQL запрос, который нужно будет выполнить в процессе.
Таблицы
create table product (
id INTEGER NOT NULL,
CONSTRAINT product_pkey PRIMARY KEY (id)
);
create table product_recommendation (
id INTEGER NOT NULL,
product_id1 INTEGER NOT NULL REFERENCES product,
product_id2 INTEGER NOT NULL REFERENCES product,
CONSTRAINT product_recommendation_pkey PRIMARY KEY (id)
);
CREATE INDEX product_recommendation_product_id1 on product_recommendation (product_id1);
Данные для тестов
INSERT INTO product(id)
SELECT id
FROM generate_series(1, 4000000) id;
INSERT INTO product_recommendation(id, product_id1, product_id2)
SELECT id, id, id
FROM generate_series(1, 4000000) id;
Использование IN (плохой вариант)
В рамках условий задачи к решению IN
нужно подходить аккуратно. В базовом его виде, в случае использования PreparedStatement, мы упремся в лимит на количество аргументов. Поэтому данный кусок кода просто не будет работать, если мы придем с массивом/коллекцией на 100000 элементов:
try {
String namedSql = """
SELECT *
FROM product_recommendation
WHERE product_id1 NOT IN (:ids);
""";
return getNamedParameterJdbcTemplate()
.queryForList(
namedSql,
new MapSqlParameterSource()
.addValue("ids", ids),
ProductRecommendation.class
);
} catch (EmptyResultDataAccessException ex) {
return null;
}
Связано это с тем, что каждый элемент массива выставляется как аргумент параметризованный запроса. И в целом это нельзя назвать какой-то проблемой PreparedStatement
, использование параметризованных запросов с большим количеством аргументов - это плохая практика.
Чтобы избежать этого, нужно выставить массив в аргумент запроса, для этого достаточно прописать подзапрос для IN с использованием UNNEST
:
SELECT *
FROM product_recommendation
WHERE product_id1 NOT IN (
SELECT UNNEST(:ids)
);
Запрос для ANALYZE
:
EXPLAIN(ANALYZE, BUFFERS)
SELECT * FROM
product_recommendation
WHERE product_id1 NOT IN (
select generate_series(2000001, 2100000)
);
Здесь уже обычный Seq Scan
с фильтрацией, но при этом запрос показывает хороший результат выполнения в рамках условиях задачи (коллекция из 100000 айдишников). В любом случае, если входной массив будет увеличен, запрос будет очень сильно деградировать и скорее его невозможно будет использовать.
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
Seq Scan on product_recommendation (cost=750.02..93998.32 rows=2000212 width=12) (actual time=11.766..424.333 rows=3900000 loops=1)
Filter: (NOT (hashed SubPlan 1))
Rows Removed by Filter: 100000
Buffers: shared hit=10926 read=32317
SubPlan 1
-> ProjectSet (cost=0.00..500.02 rows=100000 width=4) (actual time=0.001..2.480 rows=100000 loops=1)
-> Result (cost=0.00..0.01 rows=1 width=0) (actual time=0.000..0.000 rows=1 loops=1)
Planning:
Buffers: shared hit=19 read=9 dirtied=1
Planning Time: 1.141 ms
Execution Time: 502.663 ms
(11 rows)
Использование EXISTS
Наверное самый базовый запрос с использованием EXISTS
для подобных задач.
SELECT * FROM
product_recommendation
WHERE NOT EXISTS (
SELECT 1 FROM UNNEST(:ids) product_id
WHERE product_id = product_recommendation.product_id1
);
Запрос для ANALYZE
:
EXPLAIN (ANALYZE, BUFFERS)
WITH series AS (
SELECT
generate_series(2000001, 2100000) product_id
)
SELECT
*
FROM
product_recommendation
WHERE
NOT EXISTS(
SELECT
1
FROM
series
WHERE
series.product_id = product_recommendation.product_id1
);
Ожидаемый Anti Join
, запрос попадает в индекс, оптимальное использование диска на Index Scan
.
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Merge Anti Join (cost=9805.27..206914.69 rows=3900424 width=12) (actual time=29.469..513.411 rows=3900000 loops=1)
Merge Cond: (product_recommendation.product_id1 = (generate_series(2000001, 2100000)))
Buffers: shared hit=437 read=32116
-> Index Scan using product_recommendation_product_id1 on product_recommendation (cost=0.43..185608.79 rows=4000424 width=12) (actual time=0.239..265.239 rows=4000000 loops=1)
Buffers: shared hit=437 read=32116
-> Sort (cost=9804.84..10054.84 rows=100000 width=4) (actual time=29.218..31.092 rows=100000 loops=1)
Sort Key: (generate_series(2000001, 2100000))
Sort Method: quicksort Memory: 7760kB
-> ProjectSet (cost=0.00..500.02 rows=100000 width=4) (actual time=0.012..9.255 rows=100000 loops=1)
-> Result (cost=0.00..0.01 rows=1 width=0) (actual time=0.005..0.005 rows=1 loops=1)
Planning Time: 0.568 ms
Execution Time: 592.153 ms
(12 rows)
Использование EXCEPT
Такой же базовый запрос EXCEPT
, для фильтрации во второй выборке используем = ANY
, чтоб сразу убрать описанные выше проблемы с IN
для java-приложения.
SELECT *
FROM product_recommendation
EXCEPT
SELECT *
FROM product_recommendation
WHERE product_id1 = ANY(:ids);
Запрос для ANALYZE
:
EXPLAIN(ANALYZE, BUFFERS)
WITH series AS (
SELECT
generate_series(2000001, 2100000)
)
SELECT *
FROM product_recommendation
EXCEPT
SELECT *
FROM product_recommendation
WHERE product_id1 = ANY(ARRAY(TABLE series));
Здесь видно два момента:
- из-за того, что идет
Seq Scan
на первой выборке, чем больше будет становиться таблица, тем сильнее будет деградировать запрос. - хоть и вторая выборка попадает в
Index Scan
, запрос страдает от неэфективности фильтров= ANY
илиIN
, и чем больше будет входной массив, тем сильнее будет страдать.
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
HashSetOp Except (cost=0.00..174805.50 rows=4000424 width=16) (actual time=1359.957..1726.060 rows=3900000 loops=1)
Buffers: shared hit=311374 read=32411
-> Append (cost=0.00..144802.24 rows=4000434 width=16) (actual time=0.014..553.550 rows=4100000 loops=1)
Buffers: shared hit=311374 read=32411
-> Subquery Scan on "*SELECT* 1" (cost=0.00..123251.48 rows=4000424 width=16) (actual time=0.014..343.141 rows=4000000 loops=1)
Buffers: shared hit=10832 read=32411
-> Seq Scan on product_recommendation (cost=0.00..83247.24 rows=4000424 width=12) (actual time=0.012..154.525 rows=4000000 loops=1)
Buffers: shared hit=10832 read=32411
-> Subquery Scan on "*SELECT* 2" (cost=1500.45..1548.59 rows=10 width=16) (actual time=6.213..62.302 rows=100000 loops=1)
Buffers: shared hit=300542
-> Index Scan using product_recommendation_product_id1 on product_recommendation product_recommendation_1 (cost=1500.45..1548.49 rows=10 width=12) (actual time=6.213..57.065 rows=100000 loops=1)
Index Cond: (product_id1 = ANY ($0))
Buffers: shared hit=300542
InitPlan 1 (returns $0)
-> ProjectSet (cost=0.00..500.02 rows=100000 width=4) (actual time=0.002..2.486 rows=100000 loops=1)
-> Result (cost=0.00..0.01 rows=1 width=0) (actual time=0.000..0.000 rows=1 loops=1)
Planning Time: 0.188 ms
Execution Time: 1863.398 ms
(18 rows)
Использование LEFT JOIN
Классическое выполнение Anti Join
на базе LEFT JOIN
и фильтрации на IS NULL
в WHERE
. Важно учитывать, что после JOIN
, для java-приложения не нужно отдавать отправленные ей идентификаторы, поэтому в SELECT
выставляется product_recommendation.*
.
WITH query AS (
select UNNEST(:ids)
)
SELECT product_recommendation.* FROM
product_recommendation
LEFT JOIN (table query) product_query(product_id)
ON (product_recommendation.product_id1 = product_query.product_id)
WHERE product_id IS NULL;
Запрос для ANALYZE
:
EXPLAIN(ANALYZE, BUFFERS)
WITH series AS (
SELECT
generate_series(2000001, 2100000)
)
SELECT
product_recommendation.*
FROM
product_recommendation
LEFT JOIN
(TABLE series) product_query(product_id)
ON product_recommendation.product_id1 = product_query.product_id
WHERE
product_id IS NULL;
Ожидаемый Anti Join
, попадает в индекс, но, в отличии от EXISTS
, сильно использует диск на Index Scan
.
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Merge Anti Join (cost=9805.27..207190.80 rows=3809668 width=12) (actual time=24.131..3287.732 rows=3900516 loops=1)
Merge Cond: (product_recommendation.product_id1 = (generate_series(2000001, 2100000)))
Buffers: shared hit=3007782 read=1001581
-> Index Scan using product_recommendation_product_id1 on product_recommendation (cost=0.43..184982.64 rows=4000000 width=12) (actual time=0.219..3036.368 rows=4000000 loops=1)
Buffers: shared hit=3007782 read=1001581
-> Sort (cost=9804.84..10054.84 rows=100000 width=4) (actual time=23.899..25.826 rows=100000 loops=1)
Sort Key: (generate_series(2000001, 2100000))
Sort Method: quicksort Memory: 7760kB
-> ProjectSet (cost=0.00..500.02 rows=100000 width=4) (actual time=0.008..8.658 rows=100000 loops=1)
-> Result (cost=0.00..0.01 rows=1 width=0) (actual time=0.002..0.002 rows=1 loops=1)
Planning Time: 0.511 ms
Execution Time: 3364.786 ms
(12 rows)
Итог
Из всех вариантов, наиболее эфективны варианты на базе LEFT JOIN
и EXISTS
. Они имеют схожий query plan на базе Merge Anti Join
, но решение на базе EXISTS
показывает лучшую работу с диском, что на практике должно делать его быстрее.
Единственный вариант, который отбраковывается, это вариант с IN
. Будет работать в рамках условий задачи, но из-за своей неэфективности выборку больше уже принять не сможет.