PostgreSQL Antipatterns: Индиана Джонс и максимальное значение ключа, или В поисках «последних» записей
Сегодняшняя задача вполне традиционна для любых учетных систем - поиск записей, содержащих максимальное значение по каждому из ключей. Что-то вроде "покажи мне последний заказ по каждому из клиентов", если переводить в прикладную область.
Кажется, что тут и споткнуться-то негде в реализации - но все оказывается совсем не тривиально.
КДПВ
Иллюстрации взяты отсюда.
Для определенности пробовать будем на PostgreSQL 13 и начнем с генерации тестовых данных о наших "заказах":
CREATE TABLE orders AS
SELECT
(random() * 1e3)::integer client_id -- один из 1K клиентов
, now()::date - (random() * 1e3)::integer dt -- дата заказа
, (random() * 1e3)::integer order_data -- извлекаемые данные по заказу
FROM
generate_series(1, 1e5); -- 100K произвольных
Как опытные разработчики мы уже понимаем, что "последний заказ по клиенту" подразумевает индекс по (client_id, dt)
:
CREATE INDEX ON orders(client_id, dt);
max + JOIN = 2 x Seq Scan
Сначала на ум приходит самый "тупой" вариант - найти эти самые "последние" значения по каждому из ключей, а потом извлечь соответствующую запись:
SELECT
*
FROM
(
SELECT
client_id
, max(dt) dt
FROM
orders
GROUP BY
client_id
) T
JOIN
orders
USING(client_id, dt);
Это дает вот такой план на 47мс/1082 buffers, при котором таблица orders
полностью перечитывается дважды:
DISTINCT ON
Но вроде достаточно очевидно, что читать всю таблицу дважды - не очень хорошо. Поскольку нам необходима всего лишь одна запись для каждого client_id
, воспользуемся возможностями DISTINCT ON
:
SELECT DISTINCT ON(client_id)
*
FROM
orders
ORDER BY
client_id, dt DESC;
Незадача... стало вдвое медленнее из-за попадания сортировки на диск.
Попробуем исправить, увеличив объем выделяемой для узла памяти work_mem, как советует нам подсказка на explain.tensor.ru:
SET work_mem = '8MB';
Помни о сортировке в индексе!
Но обратите внимание: Sort Key: client_id, dt DESC
- сортировка-то не совпадает с созданным нами индексом. А что если...
CREATE INDEX ON orders(client_id, dt DESC);
По времени сравнялись с исходным, но вот buffers теперь в 100 раз больше!
Рекурсивный "DISTINCT"
Поскольку мы знаем, что клиентов существенно меньше, чем заказов, да и в общем количестве достаточно немного, мы можем использовать модель поиска "следующих" значений client_id
прямо из индекса:
WITH RECURSIVE rec AS (
SELECT
-1 client_id -- инициализируем наименьший ключ индекса
, NULL::orders r
UNION ALL
SELECT
(X).client_id
, X
FROM
rec
, LATERAL (
SELECT
X -- возвращаем целую запись таблицы
FROM
orders X
WHERE
client_id > rec.client_id -- шагаем к "следующему" клиенту
ORDER BY
client_id, dt DESC -- помним о правильной сортировке
LIMIT 1 -- нам нужна всего одна запись
) T
)
SELECT
(r).* -- разворачиваем поля записи в столбцы
FROM
rec
OFFSET 1; -- пропускаем первую инициализационную запись
Запрос стал существенно сложнее, зато такой вариант уже выглядит гораздо интереснее в плане скорости: 9.5мс/3008 buffers - в 5 раз быстрее оригинального запроса!