Pavel Popov
Pavel Popov
Chief troubleshooting officer, software ninjaneer and digital migrant 🥷

Тестовое задание от компании 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. Будет работать в рамках условий задачи, но из-за своей неэфективности выборку больше уже принять не сможет.

Backlinks to this note

PostgreSQL
PostgreSQL

PostgreSQL, often referred to as “Postgres”, is an open-source relational database management system (RDBMS) known for its robustness, extensibility, and adherence to SQL standards.