SQL: разбор задачи на поиск последней цены

В эфире снова Радио SQL, здравствуйте, согалактчики!

Сегодня у нас обещанный разбор задачи на поиск последней цены (https://habr.com/ru/company/postgrespro/blog/546768/). Прошёл как раз земляной месяц. У вас же 60 солов в месяце, да? Я немного путаюсь во всех этих ваших неметрических то 12-ти, то 60-тиричных системах времени. Впрочем, перейдём к делу.

Напомню условие, а чтобы оно не занимало много места в и без того длинной статье, спрячу его под спойлер:

with price(stock_id, prod_id, start_date, kind, price1, cost1, bonus1) as (
values (1,1,to_date('2000-01-01','YYYY-MM-DD'),'R',100.0,32.12,6.49),
       (1,1,'2000-01-02','P', 80.0, 0,   0),
       (1,1,'2000-01-03','P', 70.0, 0,   0),
       (1,1,'2000-01-04','R',110.0,33.48,6.19),
       (1,1,'2000-01-05','P', 90.0, 0,   0),
       (1,1,'2000-01-06','R',120.0,41.22,6.19),
       (1,1,'2000-01-07','P', 80.0, 0,   0),
       (1,1,'2000-01-08','P', 90.0, 0,   0),
       (1,1,'2000-01-09','R', 93.0,36.87,6.49),
       (1,1,'2000-01-10','R', 94.0,36.85,6.99),
       (1,2,'2000-01-01','R',101.0,52.06,9.00),
       (1,2,'2000-01-02','P', 81.0, 0,   0),
       (1,2,'2000-01-03','P', 71.0, 0,   0),
       (1,3,'2000-01-04','R',111.0,64.96,4.50),
       (1,3,'2000-01-05','P', 92.0, 0,   0),
       (1,3,'2000-01-06','R',122.0,66.83,4.60),
       (1,3,'2000-01-07','P', 82.0, 0,   0),
       (1,3,'2000-01-08','P', 92.0, 0,   0))
select ...

 stock_id | prod_id | start_date | kind | price1 | cost1 | bonus1 | price1x 
----------+---------+------------+------+--------+-------+--------+---------
        1 |       1 | 2000-01-01 | R    |  100.0 | 32.12 |   6.49 |   100.0
        1 |       1 | 2000-01-02 | P    |   80.0 |     0 |      0 |   100.0
        1 |       1 | 2000-01-03 | P    |   70.0 |     0 |      0 |   100.0
        1 |       1 | 2000-01-04 | R    |  110.0 | 33.48 |   6.19 |   110.0
        1 |       1 | 2000-01-05 | P    |   90.0 |     0 |      0 |   110.0
        1 |       1 | 2000-01-06 | R    |  120.0 | 41.22 |   6.19 |   120.0
        1 |       1 | 2000-01-07 | P    |   80.0 |     0 |      0 |   120.0
        1 |       1 | 2000-01-08 | P    |   90.0 |     0 |      0 |   120.0
        ...

Задачу эту можно решать разными способами. Начнём с самого простого:

Первый подход

Это решение в лоб. Так как у нас к каждой записи исходного набора данных нужно выбрать какие-то значения, то сделаем это подзапросом:

select * -- выбрать все поля из источника данных
       -- а тут подзапрос, выбирающий нужную цену
     , (select price1
          from price sub
         where sub.stock_id = p.stock_id -- те же склад
           and sub.prod_id  = p.prod_id  -- и товар,
           and sub.kind = 'R'            -- оставим только настоящие цены
           and sub.start_date <= p.start_date  -- с датой более ранней или такой же,
         order by start_date desc        -- отсортируем в порядке «последние цены раньше»
         limit 1                         -- и возьмём только первую строку
       ) as price1x
  from price p;

Всё очень прямолинейно и просто, комментарии объясняют, что и как выбирается. Самое главное обеспечить, чтобы такой подзапрос возвращал не более одной записи, а то будет ошибка. Попутно отметим, что если записей не нашлось, что запрос вернёт NULL. В принципе это логичное поведение, но если дальше эти цены будут участвовать в каких-то расчётах, то это надо будет принять во внимание.

Отлично, мы сделали это! Запускаем! Можно расслабиться, прыснуть себе чего-нибудь зободробительного в жвалы, сделать первый (и самый вкусный) гулп... И пока запрос работает, давайте немного отвлечёмся и поразмышляем об его эффективности.

Итак, по условию у нас исходным набором данных была сборная вьюха. Что она там и как выбирает и не перелопачивает ли для этого полбазы — неизвестно. Но сборная вьюха и эффективность — это обычно понятия плохо совместимые. То есть ожидания от вьюхи — что она тормознутая. И второй неутешительный вывод, который просто напрашивается: сборная вьюха практически не оставляет надежд на наличие индексов, так что в подзапросе, чтобы найти нужный склад и нужный товар на нём, скорее всего придётся прочитать всю вьюху целиком. На каждый подзапрос. А если она в самом деле полбазы вычитывает? Миллион строк, да для каждой полбазы перечитать... Вот так на ровном месте и без использования каких бы то ни было спецсредств можно поставить на колени практически любую базу. И мы получим highload на ровном месте. Вернее в highload это превратится, если оптимизатор найдёт способ распараллелить выполнение запроса, так что может быть всё ещё не так уж плохо. У меня на тестовых данных, кстати говоря, сумел.

А ну-ка запустим в соседнем окошке select count(*) from price и внимательно посмотрим как на количество записей, так и на время исполнения. Потому что именно эти два числа нужно будет умножить друг на друга, чтобы прикинуть общее время выполнения запроса. Наш запрос будет работать хоть сколько-нибудь обозримое время, только если количество записей не будет превышать десятков или сотен, ну максимум тысяч записей. Так что полюбовались на количество записей, и давай, тяни свои ложноножки (или ложноручки, что там у тебя) к консоли и прерывай запрос, пока не прилетели админы, чтобы убедительно объяснить на пальцах, что надо и что не надо делать на боевом сервере.

Подход второй

Второе, что приходит в голову, глядя на эту задачу — это отфильтровать все реальные цены в отдельный набор данных и соединить (с-JOIN-ить) с самим исходным набором по условию, весьма смахивающему на то, которое мы использовали в подзапросе в подходе номер один.

Это в целом годный и рабочий способ, исходная вьюха скорее всего будет прочитана только два раза, если вдруг оптимизатор не найдёт более эффективный план выполнения (что вряд ли) или банально не ошибётся. Это даст хорошую производительность, но... Что же «но»? Почему не хочется так делать? А всё очень просто. Такая конструкция в виде соединения двух наборов данных с витиеватыми условиями, включая выборку только нужных данных, довольно капризна. В этих декартовых соединениях легко ошибиться и потерять часть исходных данных или наоборот, выбрать чего-то лишнего.

А ещё тяжело будет сопровождать и развивать такой запрос. Если появятся новые требования, понадобится что-то добавить или изменить, или поменять поведение в каких-то граничных случаях, то почти на любое такое изменение скорее всего придётся переписывать запрос заново.

Так что оставим этот способ напоследок, а сперва попробуем способ получше, и это...

Подход третий

Что там у нас сделать-то надо было? Сгруппировать и для каждой группы выбрать значение?.. Ба, да сюда же прямо просятся аналитические функции! Они как раз предназначены для подобных задач, когда нужно что-то сгруппировать и выбрать для каждой группы. Если при этом нужно оставить только значения для каждой группы, то используются аналитические функции, а если нужно сохранить весь исходный набор данных — то оконные.

Ну-ка, попробуем. Для каждой строки нам нужно выбрать ближайшую реальную цену, то есть надо использовать именно оконные функции. Определить окно, в которое попадут только нужные записи, отсортировать и выбрать значение из нужной строчки окна:

select *
     , agg_func(...) over (...) -- тут нужно будет определить окно и найти подходящую функцию
  from price

Казалось бы всё просто. Функция будет из тех, которые возвращают одно из значений в группе, это first_value() или lag() или что-то подобное. А вот с определением окна нужно немного помудрить. Оконные функции позволяют определять окно, указав группировку и сортировку. Понятно, что в определении окна будет partition by stock_id, prod_id и что-то надо добавить, чтобы ближайшая предыдущая строчка с реальной ценой встала на фиксированное место в этой группе. Если это не получается сделать в лоб (как, например, если бы нам надо было выбрать просто самую первую или минимальную цену), то обычно помогает такой приём, когда определяют специальное вычислимое поле и по нему делают или группировку, или сортировку. Навскидку пишем case when kind='R' then, потому что от поля kind у нас точно есть зависимость, и задумываемся... Мнэ...

Как выразился один из комментаторов предыдущей статьи, «неожиданно стало интересно». Сходу найти подходящее под условие выражение, чтобы отделить группу записей, начинающихся со строки 'R', от других, что-то не получилось. И не сходу тоже как-то не получилось...

Решение постепенно нашлось, и вот какой приём при этом был применён. Получилась двухходовка. На первом этапе формируем специальное вычислимое поле, по которому на втором этапе уже выбираем нужные значения. Поле (назовём его уровнем цены) формируем так: суммируется нарастающим итогом для каждого склада и товара в порядке даты начала действия следующее: единица для строк с kind='R' и ноль для всего остального. Получается как раз, что уровень цены перещёлкивается на следующий, как только мы встречаем реальную цену:

select *
     , sum(case when kind='R' then 1 else 0 end) -- сумма нарастающим итогом
       over(partition by stock_id, prod_id       -- в разрезе складов и товаров
            order by start_date                  -- порядок важен!
            rows between unbounded preceding and current row) as lvl -- нам нужно именно до CURRENT ROW
  from price

Теперь осталось только оконной функцией выбрать самое первое значение в каждой такой группе:

select *
     , first_value(price1) over (partition by prod_id, stock_id, lvl
                                     order by start_date) as price1x
  from (select ...)

Собрать вместе можно хоть через подзапрос, хоть с CTE. Смотрим на результаты выполнения — вычисляется за один проход, то есть в высшей степени эффективно (достат кол!).

Итого, вот оно решение:

select p.*
     , first_value(price1) over (partition by prod_id, stock_id, lvl
                                     order by start_date) as price1x
  from (select *
             , sum(case when kind='R' then 1 else 0 end)
               over(partition by stock_id, prod_id order by start_date
                    rows between unbounded preceding and current row) as lvl
  from price) p

Дальше, если надо будет вытащить остальные значения из нужной строчки, то можно повторить first_value() нужное количество раз. Для компактности можно вынести определение окна отдельно, чтобы не загромождать запрос:

select *
     , first_value(price1) over w as price1x
     , first_value(cost1)  over w as cost1x
  from (select *
             , sum(case when kind='R' then 1 else 0 end)
               over(partition by stock_id, prod_id order by start_date
                 rows between unbounded preceding and current row) as lvl
          from price) p
window w as (partition by prod_id, stock_id, lvl order by start_date)

Вот собственно и всё, на этом можно закончить, реализация второго подхода не понадобилась.

Выводы

1. Во время составления SQL-запроса имеет смысл думать про эффективность его работы.

2. Использовать оконные функции — отличная идея.

3. Если оконную функцию не получается применить в лоб, то можно попробовать разбить задачу на две подзадачи — генерация поля для группировки, последующий вызов оконной функции поверх группировки с предыдущего шага.

4. Если оконную функцию применить так и не удалось, то подход №2 даст нужные результаты, а если время работы запроса не является проблемой, то подход №1 даже лучше, потому что он прост и понятен.

Разбор решений, приведённых в комментариях

В статье с условием задачи (https://habr.com/ru/company/postgrespro/blog/546768/) я пообещал сделать разбор решений из комментариев с раздачей каких-нибудь слонов. Выполняю обещание.

Так или иначе я насчитал 11 разных вариантов решения от 10 представителей. Вообще запросов было приведено больше, но часто следующий SQL-запрос в цепочке комментариев был развитием или исправлением предыдущего. Так что количество сильно зависит от того, как считать. Пройдёмся по хронологии.

Статья с условием задачи была опубликована 16 марта 2021 в 17:12. Первое решение от @nice17 16 марта 2021 в 17:34 было предложено уже через 22 минуты после публикации статьи (22 минуты, Карл! и ещё же надо было хоть по диагонали прочитать условие). Решение было неверным, но подход к решению явно был уже в нужном направлении. Чуть позже автор довёл его до правильного. А первое более-менее работающее решение (от @ZMB138 16 марта 2021 в 19:07) появилось меньше чем через два часа(!) после публикации, это была реализация подхода №2.

Первое решение в третьем подходе от @Kilor появилось ещё спустя полчаса 16 марта 2021 в 19:39. Автор применил хитрый ход, использовав функцию array_agg(), которая допускает использование FILTER в определении окна, что позволило отфильтровать только записи с реальными ценами и избежать рассмотренной мной двухходовости. Также продемонстрирован интересный ход, что вся найденная для сопоставления строка таблицы упаковывалась в JSON, из которого дальше выбиралось нужное поле. Или все нужные поля. Не очень универсально в плане разных диалектов SQL, но изящно. Последняя версия запроса от 17 марта 2021 в 10:18 уже без упаковки/распаковки в JSON получилась компактной и эффективной.

(замечание в сторону) Воистину, вырисовывается универсальный способ, как можно решать сложные задачи на SQL — публиковать их на хабре, и дальше остаётся только подождать пару часов!..

Аналогичный подход использовал @AngelloreA в запросе от 16 марта 2021 в 22:30. Сопоставляемая строка с реальными стоимостями упаковывалась правда не в JSON, а просто в текст, что потенциально чревато проблемами при распаковке (надо бы явно указать форматы), но это работает и тоже в один проход, то есть получилась реализация подхода №3.

@viras777 16 марта 2021 в 23:07 привёл необычное решение, где весьма остроумно для генерации уровней цены используется последовательность. В целом, как мне кажется, использовать последовательность для такого случая избыточно (да и Оккам не велел), плюс побочных эффектов в программировании обычно стараются избегать, но тем не менее оно работает.

@AlexKadetov уже 16 марта 2021 к 23:10 получил по сути такое же решение в подходе №3, к которому пришёл и я, пусть даже и с некоторыми огрехами в реализации. Вообще огрехи в реализации были много у кого, я старался не придираться, потому что в реальной жизни конечно всякий запрос ещё какое-то время доводится до кондиции, уточняется его работа и всё подобное вылавливается и исправляется.

Ночью @qvan 17 марта 2021 в 01:39 привёл несколько тяжеловесное, но рабочее решение в подходе №2. Утром @xxxcoltxxx 17 марта 2021 в 09:13 привёл более явное и ясное решение в реализации подхода №2. Чуть позже @jayrumi 17 марта 2021 в 13:11 тоже опубликовал своё пусть и несколько тяжеловесное, но работающее решение тоже в подходе №2.

Дальше опять вернулся @Kilor и 17 марта 2021 в 14:30 привёл пару красивых решений в подходе №2, продемонстрировав виртуозную технику JOIN-ов наборов данных. Ближе к вечеру @Miha_S7 17 марта 2021 в 18:19 привёл своё решение в подходе №3, повторяющее полученное мной в первой части статьи.

На этом активность в комментариях заглохла, статья скрылась из леныт сайта, и больше запросов никто не публиковал.

Итого, из интересного отмечу скорость, с которой тема была раскрыта со всех сторон, включая диалекты дружественных СУБД. Плюшкополучателем был избран @Kilor, как автор самого первого однопроходного решения (в подходе №3), а также за проявленную широту охвата техники владения SQL (использование оконных функций, JSON, FILTER, JOIN-ы) и ясную по форме реализацию с использованием всего перечисленного. С ним я уже связался. Специально отмечу самое первое работающее решение от @ZMB138, оригинальность и неожиданность использования последовательностей от @viras777, а также «эталонное» на мой взгляд решение от @AlexKadetov.

И отдельное большое спасибо всем, кто принял участие в обсуждении и поделился своими решениями.