Давайте предположим, что вы разрабатываете главную страницу в интернет-магазине. На этой странице должны отображаться категории товаров с 10 товарами в каждой. Как сделать запрос к базе данных? Какие индексы нужно создать, чтобы ускорить выполнение запроса?
В начале давайте создадим таблицу products и заполним ее данными:
CREATE TABLE products (id int, category_id int, name varchar);
INSERT INTO products SELECT i, FLOOR(RANDOM() * 5 + 1), 'name' || i FROM generate_series(1, 1000000) i;Таблица содержит 1 миллион товаров, разделенные на 5 категорий.
Первое, о чем вы можете подумать – это использовать LIMIT с GROUP BY, но это не сработает, т.к. в начале каждая группа будет схлопнута в одну строку, а после этого будет применен LIMIT. Чтобы все строки из одной группы могли схлопнуться в одну строку, для всех остальных колонок нужно использовать агрегатную функцию (COUNT, SUM, AVG и др), иначе мы получим ошибку.
SELECT COUNT(id), category_id FROM products GROUP BY category_id LIMIT 10; count | category_id
--------+-------------
199645 | 1
199753 | 2
199833 | 3
200037 | 4
200732 | 5Это определенно не то, что мы хотим.
Существует 2 способа решить данную проблему. Давайте разберем оба варианта, поймем какие индексы необходимы для ускорения запросов и определим какой SQL-запрос самый быстрый.
Способ 1. Использование оконной функции
Оконная функция позволяет выполнять определенные действия над строками из каждой группы, также так же, как это делают агрегатные функции (COUNT, SUM, AVG и др), но строки из одной и той же группы не схлопываются в одну строку.
Чтобы было понятнее, давайте добавим новую таблицу deals и выполним агрегатную фукнцию и оконную функцию.
CREATE TABLE deals (id int, user_id int);
INSERT INTO deals SELECT i, i % 2 + 1 FROM generate_series(1, 7) i;В таблице 7 сделок. У первого пользователя 3 сделки, у второго 4 сделки.
В начале воспользуемся агрегатной функцией COUNT.
SELECT COUNT(*) FROM deals; count
-------
7
(1 row)Агрегатная функция COUNT просуммировала все строки и вывела сумму в виде одной строки. Если мы добавим GROUP BY user_id, то будет выведена сумма всех сделок по каждому пользователю.
SELECT user_id, COUNT(*) FROM deals GROUP BY user_id; user_id | count
---------+-------
2 | 4
1 | 3
(2 rows)Теперь давайте рассмотрим оконную функцию COUNT. Чтобы ей воспользоваться, нужно после функции написать OVER().
SELECT id, COUNT(*) OVER() FROM deals; id | count
----+-------
1 | 7
2 | 7
3 | 7
4 | 7
5 | 7
6 | 7
7 | 7
(7 rows)Как вы можете увидеть, было также вычислено количество всех строк, но в отличии от SELECT COUNT(*) FROM deals это количество выведено в каждой строке, а не в одной строке. Если OVER указан без параметров, то в 1 группу (окно) будут входить все строки из таблицы.
Чтобы вывести количество сделок по пользователю, нужно окном сделать не всю таблицу, а группу, используя PARTITION BY.
SELECT *, COUNT(*) OVER(PARTITION BY user_id) FROM deals; id | user_id | count
----+---------+-------
4 | 1 | 3
2 | 1 | 3
6 | 1 | 3
1 | 2 | 4
5 | 2 | 4
7 | 2 | 4
3 | 2 | 4
(7 rows)В качестве оконных функций можно использовать как любые агрегатные, так и специализированные оконные.
Давайте воспользуемся оконной функцией ROW_NUMBER, которая выводит номер текущей строки в группе.
SELECT *, ROW_NUMBER() OVER(PARTITION BY user_id) FROM deals; id | user_id | row_number
----+---------+------------
4 | 1 | 1
2 | 1 | 2
6 | 1 | 3
1 | 2 | 1
5 | 2 | 2
7 | 2 | 3
3 | 2 | 4
(7 rows)У нас есть порядковый номер сделки по каждому пользователю. Теперь дополнительным запросом можно отфильтровать все строки, которые имеют порядковый номер меньше или равный 2. В итоге мы получим по 2 сделки на каждого пользователя.
SELECT * FROM (
SELECT *, ROW_NUMBER() OVER(PARTITION BY user_id) FROM deals
) t WHERE row_number <= 2; id | user_id | row_number
----+---------+------------
4 | 1 | 1
2 | 1 | 2
1 | 2 | 1
5 | 2 | 2
(4 rows)Можно также задать порядок, в котором будут обрабатываться строки оконной функцией, используя ORDER BY внутри OVER.
SELECT * FROM (
SELECT *, ROW_NUMBER() OVER(PARTITION BY user_id ORDER BY id) FROM deals
) t WHERE row_number <= 2; id | user_id | row_number
----+---------+------------
2 | 1 | 1
4 | 1 | 2
1 | 2 | 1
3 | 2 | 2
(4 rows)Строки внутри каждой группы теперь отсортированы по колонке id.
Давайте вернемся к таблице products с 1 миллионом строк и посмотрим сколько времени будет выполняться подобный запрос.
EXPLAIN ANALYZE SELECT * FROM (
SELECT *, ROW_NUMBER() OVER (
PARTITION BY category_id ORDER BY id DESC
)
FROM products
) t WHERE row_number <= 10; Subquery Scan on t (cost=136536.84..169036.84 rows=333333 width=26) (actual time=3128.932..3912.707 rows=50 loops=1)
Filter: (t.row_number <= 10)
Rows Removed by Filter: 999950
-> WindowAgg (cost=136536.84..156536.84 rows=1000000 width=26) (actual time=3128.929..3855.424 rows=1000000 loops=1)
-> Sort (cost=136536.84..139036.84 rows=1000000 width=18) (actual time=3123.940..3440.984 rows=1000000 loops=1)
Sort Key: products.category_id, products.id DESC
Sort Method: external merge Disk: 28304kB
-> Seq Scan on products (cost=0.00..16369.00 rows=1000000 width=18) (actual time=0.060..53.225 rows=1000000 loops=1)
Planning Time: 1.518 ms
Execution Time: 3915.502 msЗапрос выполнялся почти 4 сек.
Как вы можете увидеть, в начале был выполнен вложенный запрос. Для этого была просканирована вся таблица products, отсортирована по колонке id по убыванию и выполнена оконная фукнция, которая пронумеровала строки внутри каждой группы. Затем был выполнен основной запрос, который отфильтровал строки с порядковым номером меньше либо равным 10.
Чтобы ускорить этот запрос, давайте добавим B-Tree индекс по 2 колонкам: category_id и id, чтобы из таблицы products строки выбирались сразу в отсортированном порядке.
CREATE INDEX products_category_id_id_idx ON products (category_id, id DESC);Еще раз выполним запрос.
EXPLAIN ANALYZE SELECT * FROM (
SELECT *, ROW_NUMBER() OVER (
PARTITION BY category_id ORDER BY id DESC
)
FROM products
) t WHERE row_number <= 10; Subquery Scan on t (cost=0.42..81053.98 rows=333333 width=26) (actual time=1.585..686.557 rows=50 loops=1)
Filter: (t.row_number <= 10)
Rows Removed by Filter: 999950
-> WindowAgg (cost=0.42..68553.98 rows=1000000 width=26) (actual time=1.583..619.792 rows=1000000 loops=1)
-> Index Scan using products_category_id_id_idx on products (cost=0.42..51053.98 rows=1000000 width=18) (actual time=1.568..180.026 rows=1000000 loops=1)
Planning Time: 3.580 ms
Execution Time: 686.628 msТеперь запрос выполнился за 687 мс.
Если, как в моем случае, вам необходимо группировать не по 1 колонке, а по нескольким, то после PARTITION BY вы можете указать несколько колонок. Например, PARTITION BY record_id, field_id.
Если используется пагинация (постраничный вывод) для вывода категорий (если категорий много), то во внутреннем запросе нужно добавить условие WHERE category_id IN (1,2,4), где 1,2,4 - это id категорий, которые нужно показать на данной странице (предположим, что категория с id=3 была удалена). В этом случае запрос выполнится еще быстрее.
Главный недостаток данного подхода заключается в том, что на первом этапе (в подзапросе) необходимо выбрать все строки, которые находятся в указанных группах (категориях товаров). Эти строки нумеруются оконной функцией и после этого происходит фильтрация первых N строк в каждой группе.
Можно ли сразу выбрать N строк для каждой группы, чтобы не тратить время на чтение всех строк и фильтрацию?
Способ 2. Использование JOIN LATERAL
Идеальным решением нашей проблемы было бы выполнение только 2 шагов:
- Взять все группы. В нашем примере это категории товаров.
- Для каждой группы взять только N результатов и объеденить в одну таблицу.
Давайте в начале выберем все категории товаров, которые используются в таблице products. Для этого воспользуемся DISTINCT, который возьмет из таблицы только строки с уникальным значением category_id. Подробнее об этом тут.
SELECT DISTINCT category_id FROM products; category_id
-------------
1
3
5
4
2
(5 rows)Теперь, используя JOIN LATERAL, для каждой группы возьем N результатов и объеденим это в одну таблицу. LATERAL позволяет в JOIN запросе ссылаться на уже объявленные ранее таблицы. Тем самым мы можем в начале получить все категории, а затем для каждой категории взять N товаров.
SELECT r.*
FROM (
SELECT DISTINCT category_id FROM products ORDER BY category_id
) categories
JOIN LATERAL (
SELECT * FROM products
WHERE category_id = categories.category_id
ORDER BY id DESC
LIMIT 2
) r ON true; id | category_id | name
---------+-------------+-------------
999997 | 1 | name999997
999995 | 1 | name999995
999992 | 2 | name999992
999984 | 2 | name999984
999999 | 3 | name999999
999998 | 3 | name999998
999996 | 4 | name999996
999994 | 4 | name999994
1000000 | 5 | name1000000
999993 | 5 | name999993
(10 rows) Nested Loop (cost=18869.53..18873.03 rows=10 width=18) (actual time=225.723..225.749 rows=10 loops=1)
-> Sort (cost=18869.11..18869.12 rows=5 width=4) (actual time=225.675..225.676 rows=5 loops=1)
Sort Key: products.category_id
Sort Method: quicksort Memory: 25kB
-> HashAggregate (cost=18869.00..18869.05 rows=5 width=4) (actual time=225.648..225.650 rows=5 loops=1)
Group Key: products.category_id
Batches: 1 Memory Usage: 24kB
-> Seq Scan on products (cost=0.00..16369.00 rows=1000000 width=4) (actual time=0.012..55.384 rows=1000000 loops=1)
-> Limit (cost=0.42..0.73 rows=2 width=18) (actual time=0.013..0.013 rows=2 loops=5)
-> Index Scan using products_category_id_id_idx on products products_1 (cost=0.42..30662.64 rows=200000 width=18) (actual time=0.012..0.013 rows=2 loops=5)
Index Cond: (category_id = products.category_id)
Planning Time: 0.172 ms
Execution Time: 225.824 msЗапрос выполнился за 226 мс, что быстрее в 3 раза, чем запрос, в котором использовалась оконная функция. Запрос выполняется следующим образом:
- Выбираются все категории, которые используются в таблице products и сортируются по возрастанию.
- Для каждой категории, которые были выбраны в первом подзапросе, выбираются 2 последние товара. ON true означает, что все полученные строки будут объеденены со строками из таблицы с категориями.
- Выбираются только колонки из JOIN-таблицы, чтобы избежать дублирования колонки category_id.
Для ускорения запроса необходим тот же индекс, который мы уже создали ранее:
CREATE INDEX products_category_id_id_idx ON products (category_id, id DESC);Для выполнения первого подзапроса было произведено последовательное сканирование. Если выбрать, только часть из всех категорий (напр, 2 из 5), то будет использоваться индекс.
Можно заметить, что почти все время занимает выполнение первого подзапроса, который ищет все категории, используемые в таблице products.
EXPLAIN ANALYZE SELECT DISTINCT category_id FROM products ORDER BY category_id; Sort (cost=18869.11..18869.12 rows=5 width=4) (actual time=225.985..225.986 rows=5 loops=1)
Sort Key: category_id
Sort Method: quicksort Memory: 25kB
-> HashAggregate (cost=18869.00..18869.05 rows=5 width=4) (actual time=225.961..225.963 rows=5 loops=1)
Group Key: category_id
Batches: 1 Memory Usage: 24kB
-> Seq Scan on products (cost=0.00..16369.00 rows=1000000 width=4) (actual time=0.010..56.372 rows=1000000 loops=1)
Planning Time: 0.076 ms
Execution Time: 226.043 msСкорее всего, у вас уже есть отдельная таблица с категориями товаров.
CREATE TABLE categories (id int, name varchar);
INSERT INTO categories SELECT i, 'name' || i FROM generate_series(1, 5) i;А значит нет смысла сканировать всю таблицу products для поиска этих категорий. Давайте возьмем эти категории сразу из таблицы categories.
EXPLAIN ANALYZE SELECT r.*
FROM (
SELECT id FROM categories ORDER BY id
) categories
JOIN LATERAL (
SELECT * FROM products
WHERE category_id = categories.id
ORDER BY id DESC
LIMIT 2
) r ON true; Nested Loop (cost=1.53..5.03 rows=10 width=18) (actual time=0.083..0.127 rows=10 loops=1)
-> Sort (cost=1.11..1.12 rows=5 width=4) (actual time=0.038..0.040 rows=5 loops=1)
Sort Key: categories.id
Sort Method: quicksort Memory: 25kB
-> Seq Scan on categories (cost=0.00..1.05 rows=5 width=4) (actual time=0.012..0.014 rows=5 loops=1)
-> Limit (cost=0.42..0.73 rows=2 width=18) (actual time=0.015..0.016 rows=2 loops=5)
-> Index Scan using products_category_id_id_idx2 on products (cost=0.42..30662.64 rows=200000 width=18) (actual time=0.014..0.015 rows=2 loops=5)
Index Cond: (category_id = categories.id)
Planning Time: 0.301 ms
Execution Time: 0.226 msЗапрос выполнился за 0.2 мс, в 1000 раз быстрее предыдущего запроса с DISTINCT и в 3000 раз быстрее запроса с оконной функцией.
Выводы
Чтобы получить N строк в каждой группе лучше использовать запрос с JOIN LATERAL, который выполняется гораздо быстрее, чем запрос с оконной функцией. Это связано с тем, что при использовании оконной функции на первом этапе выбираются все строки в каждой группе, а уже после этого отсекаются ненужные строки. JOIN LATERAL позволяет сослаться на уже выбранные группы и для каждой группы сразу взять N строк.
Выбирать группы можно одним из 3 способов:
- Выбрать их из отдельной таблицы. Например, SELECT id FROM categories.
- Сгенерировать их, если они уже известны. Например, SELECT i id FROM generate_series(1, 5) i.
- Выбрать их из той же таблицы. Например, SELECT DISTINCT category_id FROM products.
Для ускорения поиска необходимо создать индекс по используемым колонкам.
Шпаргалка
-- Создаем таблицы с категориями и товарами
CREATE TABLE categories (id int, name varchar);
CREATE TABLE products (id int, category_id int, name varchar);
-- Наполняем таблицы
INSERT INTO categories SELECT i, 'name' || i FROM generate_series(1, 5) i;
INSERT INTO products SELECT i, FLOOR(RANDOM() * 5 + 1), 'name' || i FROM generate_series(1, 1000000) i;
-- Создаем B-Tree индекс для ускорения поиска
CREATE INDEX products_category_id_id_idx ON products (category_id, id DESC);
-- Выбираем 2 последних товара в каждой категории
EXPLAIN ANALYZE SELECT r.*
FROM (
SELECT id FROM categories ORDER BY id
) categories
JOIN LATERAL (
SELECT * FROM products
WHERE category_id = categories.id
ORDER BY id DESC
LIMIT 2
) r ON true;