Как стать автором
Обновить
76.58
Тензор
Разработчик системы СБИС

PostgreSQL Antipatterns: Индиана Джонс и максимальное значение ключа, или В поисках «последних» записей

Время на прочтение2 мин
Количество просмотров10K

Сегодняшняя задача вполне традиционна для любых учетных систем - поиск записей, содержащих максимальное значение по каждому из ключей. Что-то вроде "покажи мне последний заказ по каждому из клиентов", если переводить в прикладную область.

Кажется, что тут и споткнуться-то негде в реализации - но все оказывается совсем не тривиально.

Постараемся не запутаться
Постараемся не запутаться
КДПВ

Иллюстрации взяты отсюда.

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

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

Теги:
Хабы:
Всего голосов 18: ↑16 и ↓2+20
Комментарии42

Публикации

Информация

Сайт
sbis.ru
Дата регистрации
Дата основания
Численность
1 001–5 000 человек
Местоположение
Россия