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 полностью перечитывается дважды:

Двойной Seq ScanДвойной Seq Scan«Два раза, Карл, два раза!»… хотя, это не отсюда

DISTINCT ON

Но вроде достаточно очевидно, что читать всю таблицу дважды — не очень хорошо. Поскольку нам необходима всего лишь одна запись для каждого client_id, воспользуемся возможностями DISTINCT ON:

SELECT DISTINCT ON(client_id)
  *
FROM
  orders
ORDER BY
  client_id, dt DESC;

Залезли в temp buffersЗалезли в temp buffers

Незадача… стало вдвое медленнее из-за попадания сортировки на диск.

Путь оптимизаций тернист и опасенПуть оптимизаций тернист и опасен

Попробуем исправить, увеличив объем выделяемой для узла памяти work_mem, как советует нам подсказка на explain.tensor.ru:

SET work_mem = '8MB';

Теперь work_mem хватило для Sort MemoryТеперь work_mem хватило для Sort MemoryЗабрезжил свет в конце туннеляЗабрезжил свет в конце туннеля

Помни о сортировке в индексе!

Но обратите внимание: 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; -- пропускаем первую инициализационную запись

Рекурсивный DISTINCTРекурсивный DISTINCT

Запрос стал существенно сложнее, зато такой вариант уже выглядит гораздо интереснее в плане скорости: 9.5 мс/3008 buffers — в 5 раз быстрее оригинального запроса!

Теперь-то мы - эксперты-оптимизаторы!Теперь-то мы — эксперты-оптимизаторы!

© Habrahabr.ru