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