Сегодняшняя задача вполне традиционна для любых учетных систем - поиск записей, содержащих максимальное значение по каждому из ключей. Что-то вроде "покажи мне последний заказ по каждому из клиентов", если переводить в прикладную область.
Кажется, что тут и споткнуться-то негде в реализации - но все оказывается совсем не тривиально.
![Постараемся не запутаться Постараемся не запутаться](https://habrastorage.org/getpro/habr/upload_files/b7e/b82/fea/b7eb82feabb0d0b74f9cacdd0433e041.png)
КДПВ
Иллюстрации взяты отсюда.
Для определенности пробовать будем на 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);
![Вот с этим индексом все как полетит!.. Вот с этим индексом все как полетит!..](https://habrastorage.org/getpro/habr/upload_files/ea9/b69/b26/ea9b69b26f0dfb927471e24e0d895094.png)
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
полностью перечитывается дважды:
![Двойной Seq Scan Двойной Seq Scan](https://habrastorage.org/getpro/habr/upload_files/ad9/743/a16/ad9743a16bb03aeeb7d8be39bd915d32.png)
!["Два раза, Карл, два раза!"... хотя, это не отсюда "Два раза, Карл, два раза!"... хотя, это не отсюда](https://habrastorage.org/getpro/habr/upload_files/9c6/ae7/fea/9c6ae7feaca1cd6e84169a15173a2915.png)
DISTINCT ON
Но вроде достаточно очевидно, что читать всю таблицу дважды - не очень хорошо. Поскольку нам необходима всего лишь одна запись для каждого client_id
, воспользуемся возможностями DISTINCT ON
:
SELECT DISTINCT ON(client_id)
*
FROM
orders
ORDER BY
client_id, dt DESC;
![Залезли в temp buffers Залезли в temp buffers](https://habrastorage.org/getpro/habr/upload_files/3db/7e6/4b7/3db7e64b78776975498f27fa213de05e.png)
Незадача... стало вдвое медленнее из-за попадания сортировки на диск.
![Путь оптимизаций тернист и опасен Путь оптимизаций тернист и опасен](https://habrastorage.org/getpro/habr/upload_files/f6a/f30/080/f6af30080be23f78b75e7475bd095dc3.png)
Попробуем исправить, увеличив объем выделяемой для узла памяти work_mem, как советует нам подсказка на explain.tensor.ru:
SET work_mem = '8MB';
![Теперь work_mem хватило для Sort Memory Теперь work_mem хватило для Sort Memory](https://habrastorage.org/getpro/habr/upload_files/c4e/988/d08/c4e988d08f406c97fcc1e683df5d1aed.png)
![Забрезжил свет в конце туннеля Забрезжил свет в конце туннеля](https://habrastorage.org/getpro/habr/upload_files/d49/306/859/d49306859c9c7f105c2fc3874ee832b1.png)
Помни о сортировке в индексе!
Но обратите внимание: Sort Key: client_id, dt DESC
- сортировка-то не совпадает с созданным нами индексом. А что если...
CREATE INDEX ON orders(client_id, dt DESC);
![Используем подходящий индекс Используем подходящий индекс](https://habrastorage.org/getpro/habr/upload_files/bd5/bdc/170/bd5bdc1703a5ac59f3b610d84db1f07b.png)
По времени сравнялись с исходным, но вот buffers теперь в 100 раз больше!
![Немного подгорает Немного подгорает](https://habrastorage.org/getpro/habr/upload_files/5b4/4ec/00b/5b44ec00bfb136cae9e14563305b131a.png)
Рекурсивный "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; -- пропускаем первую инициализационную запись
![Рекурсивный DISTINCT Рекурсивный DISTINCT](https://habrastorage.org/getpro/habr/upload_files/989/adb/efc/989adbefc76b87fa1aec895a6c7d2534.png)
Запрос стал существенно сложнее, зато такой вариант уже выглядит гораздо интереснее в плане скорости: 9.5мс/3008 buffers - в 5 раз быстрее оригинального запроса!
![Теперь-то мы - эксперты-оптимизаторы! Теперь-то мы - эксперты-оптимизаторы!](https://habrastorage.org/getpro/habr/upload_files/eab/0fd/628/eab0fd62807abd483ed7a4205be477db.png)