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 раз быстрее оригинального запроса!