SQL: решение задачи о рабочем времени10.07.2019 20:20

Здравствуйте, в эфире опять Радио SQL! Сегодня у нас решение задачи, которую мы передавали в нашем предыдущем эфире, и обещали разобрать в следующий раз. И вот этот следующий раз наступил.

Задача вызвала живой отклик у гуманоидов галактики Млечный путь (и неудивительно, с их-то трудовым рабством, которое они до сих пор почитают за благо цивилизации). К сожалению, на третьей планете отложили запуск космической обсерватории «Спектр-РГ» в конце июля 2019 года РХ (летоисчисление местное), с помощью которого планировалось транслировать эту передачу. Пришлось искать альтернативные пути передачи, что привело к небольшому опозданию сигнала. Но всё хорошо, что хорошо кончается.

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

with periods(id, start_time, stop_time) as (
  values(1, '2019-03-29 07:00:00'::timestamp, '2019-04-08 14:00:00'::timestamp), 
        (2, '2019-04-10 07:00:00'::timestamp, '2019-04-10 20:00:00'::timestamp), 
        (3, '2019-04-11 12:00:00'::timestamp, '2019-04-12 16:07:12'::timestamp),
        (4, '2018-12-28 12:00:00'::timestamp, '2019-01-16 16:00:00'::timestamp)
)

 id |     start_time      |      stop_time      | work_hrs 
----+---------------------+---------------------+----------
  1 | 2019-03-29 07:00:00 | 2019-04-08 14:00:00 | 58:00:00
  2 | 2019-04-10 07:00:00 | 2019-04-10 20:00:00 | 09:00:00
  3 | 2019-04-11 12:00:00 | 2019-04-12 16:07:12 | 13:07:12
  4 | 2018-12-28 12:00:00 | 2019-01-16 16:00:00 | 67:00:00

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

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

1. Определить как наиболее компактно задать рабочее расписание, да ещё так, чтобы им было удобно воспользоваться для решения.
2. Собственно посчитать длительность каждого исходного периода в рабочих часах по рабочему расписанию из предыдущей подзадачи.

Причём начинать лучше со второй, чтобы понять в каком виде нам нужно решить первую. Потом решить первую и вернуться опять ко второй, чтобы получить уже окончательный результат.
Собирать результат будем постепенно, пользуясь синтаксисом CTE, который позволяет вынести в отдельные именованные подзапросы все необходимые выборки данных, а потом связать всё воедино.

Ну и поехали.

Посчитать длительность в рабочих часах

Для подсчёта длительности каждого из периодов в рабочих часах в лоб, нужно исходный период (зелёный цвет на диаграмме) пересечь с интервалами, которые описывают рабочее время (оранжевый). Интервалы рабочего времени — это понедельники с 10:00 до 19:00, вторники с 10:00 до 19:00 и так далее. Результат показан синим:

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

Процедуру следует повторить для каждого исходного периода. Исходные периоды у нас уже заданы в табличке periods (start_time, stop_time), рабочее время будем представлять в виде таблицы, скажем, schedule (strat_time, stop_time), где присутствует каждый рабочий день. Получится полное декартово произведение всех исходных периодов и интервалов рабочего времени.

Пересечения можно посчитать классическим способом, рассмотрев все возможные варианты пересечений интервалов — пересекаем зелёный с оранжевым, результат синий:

и взяв каждом случае нужное значение для начала и конца результата:

   select s.start_time, s.stop_time -- case #1
     from periods p, schedule s
    where p.start_time <= s.start_time
      and p.stop_time  >  s.stop_time
   union all
   select p.start_time, s.stop_time -- case #2
     from periods p, schedule s
    where p.start_time >= s.start_time
      and p.stop_time  >  s.stop_time
   union all
   select s.start_time, p.stop_time -- case #3
     from periods p, schedule s
    where p.start_time <= s.start_time
      and p.stop_time  <  s.stop_time
   union all
   select p.start_time, p.stop_time -- case #4
     from periods p, schedule s
    where p.start_time >= s.start_time
      and p.stop_time  <  s.stop_time

Так как для каждого пересечения у нас возможен только один из четырёх вариантов, то все они соединены в один запрос с помощью union all.

Можно поступить иначе, воспользовавшись имеющимся в PostgreSQL типом диапазона tsrange и уже имеющейся для него операцией пересечения:

   select tsrange(s.start_time, s.stop_time)
          * tsrange(s.start_time, s.stop_time)
     from periods p, schedule s

Согласитесь, что так — ээээ — несколько проще. Вообще в PostgreSQL довольно много таких удобных мелочей, так что писать на нём запросы весьма приятно.

Сгенерировать календарь

Теперь вернёмся к подзадаче с заданием расписания рабочего времени.

Рабочее расписание нам нужно получить в виде интервалов рабочего времени с 10:00 до 19:00 для каждого рабочего дня, что-то типа schedule (start_time, stop_time). Как мы поняли, так будет удобно решать нашу задачу. В реальной жизни такое расписание следовало бы задать таблично, для двух лет это всего около 500 записей, для практических целей понадобится задать пусть даже десяток лет — это пара с половиной тысяч записей, сущая ерунда для современных баз данных. Но у нас задачка, которая будет решаться в один запрос, и перечислять в ней всю такую таблицу целиком не очень практично. Попробуем реализовать её покомпактнее.

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

 dates_exclude(d) as (
    values('2018-01-01'::date), -- 2018
          ('2018-01-02'::date),
          ('2018-01-03'::date),
          ('2018-01-04'::date),
          ('2018-01-05'::date),
          ('2018-01-08'::date),
          ('2018-02-23'::date),
          ('2018-03-08'::date),
          ('2018-03-09'::date),
          ('2018-05-01'::date),
          ('2018-05-02'::date),
          ('2018-05-09'::date),
          ('2018-06-11'::date),
          ('2018-06-12'::date),
          ('2018-11-05'::date),
          ('2018-12-31'::date),
          ('2019-01-01'::date), -- 2019
          ('2019-01-02'::date),
          ('2019-01-03'::date),
          ('2019-01-04'::date),
          ('2019-01-07'::date),
          ('2019-01-08'::date),
          ('2019-03-08'::date),
          ('2019-05-01'::date),
          ('2019-05-02'::date),
          ('2019-05-03'::date),
          ('2019-05-09'::date),
          ('2019-05-10'::date),
          ('2019-06-12'::date),
          ('2019-11-04'::date) )

и дополнительные рабочие дни, которые надо будет добавить:

 dates_include(d) as (
    values -- только 2018, в 2019 нету
          ('2018-04-28'::date),
          ('2018-06-09'::date),
          ('2018-12-29'::date) )

Последовательность рабочих дней на два года можно сгенерировать специальной и очень подходящей функцией generate_series (), сразу попутно выкинув субботы и воскресенья:

    select d
      from generate_series( '2018-01-01'::timestamp
                          , '2020-01-01'::timestamp
                          , '1 day'::interval ) as d
        where extract(dow from d) not in (0,6) -- убрать субботы и воскресенья

Получим рабочие дни, соединив всё вместе: генерируем последовательность всех рабочих дней за два года, добавим дополнительные рабочие дни из dates_include и уберём дополнительно все дни из dates_exclude:

 schedule_base as (
      select d
        from generate_series( '2018-01-01'::timestamp
                          , '2020-01-01'::timestamp
                          , '1 day'::interval ) as d
     where extract(dow from d) not in (0,6) -- убрать субботы и воскресенья
    union
      select d from dates_include -- добавить дополнительные рабочие дни
    except
      select d from dates_exclude -- и убрать дополнительные выходные
)

И теперь получаем нужные нам интервалы рабочего времени:

 schedule(start_time, stop_time) as (
    select d + '10:00:00'::time, d + '19:00:00'::time
      from schedule_base
)

Вот так, расписание получили.

Собираем всё вместе

Теперь будем получать пересечения:

   select p.*
        , tsrange(p.start_time, p.stop_time) * tsrange(s.start_time, s.stop_time) as wrkh
     from periods p
     join schedule s
       on tsrange(p.start_time, p.stop_time) && tsrange(s.start_time, s.stop_time)

Обратите внимание на условие соединения ON, в нём не выполняется сопоставления двух соответствующих записей из соединяемых таблиц, такого соответствия не существует, но вводится некоторая оптимизация, отсекающая интервалы рабочего времени, с которыми наш исходный период не пересекается. Делается это с помощью оператора &&, проверяющего пересечение интервалов tsrange. Это убирает массу пустых пересечений, чтобы не мешались перед глазами, но, с другой стороны, убирает и информацию о тех исходных периодах, которые полностью приходятся на нерабочее время. Так что любуемся, что наш подход работает, и переписываем запрос так:

 periods_wrk as (
   select p.*
        , tsrange(p.start_time, p.stop_time) * tsrange(s.start_time, s.stop_time) as wrkh
     from periods p
        , schedule s )

select id, start_time, stop_time
     , sum(upper(wrkh)-lower(wrkh))
  from periods_wrk
 group by id, start_time, stop_time

В periods_wrk раскладываем каждый исходный период на рабочие интервалы, а потом считаем их общую длительность. Получилось полное декартово произведение всех периодов на интервалы, но зато ни один период не потерян.

Всё, результат получен. Не понравились значения NULL для пустых интервалов, пусть лучше запрос показывает интервал нулевой длины. Завернём сумму в coalesce ():

select id, start_time, stop_time
     , coalesce(sum(upper(wrkh)-lower(wrkh)), '0 sec'::interval)
  from periods_wrk
 group by id, start_time, stop_time

Всё вместе даёт итоговый результат:

with periods(id, start_time, stop_time) as (
  values(1, '2019-03-29 07:00:00'::timestamp, '2019-04-08 14:00:00'::timestamp) 
      , (2, '2019-04-10 07:00:00'::timestamp, '2019-04-10 20:00:00'::timestamp) 
      , (3, '2019-04-11 12:00:00'::timestamp, '2019-04-12 16:00:00'::timestamp)
      , (4, '2018-12-28 12:00:00'::timestamp, '2019-01-16 16:00:00'::timestamp)
),

 dates_exclude(d) as (
    values('2018-01-01'::date), -- 2018
          ('2018-01-02'::date),
          ('2018-01-03'::date),
          ('2018-01-04'::date),
          ('2018-01-05'::date),
          ('2018-01-08'::date),
          ('2018-02-23'::date),
          ('2018-03-08'::date),
          ('2018-03-09'::date),
          ('2018-05-01'::date),
          ('2018-05-02'::date),
          ('2018-05-09'::date),
          ('2018-06-11'::date),
          ('2018-06-12'::date),
          ('2018-11-05'::date),
          ('2018-12-31'::date),
          ('2019-01-01'::date), -- 2019
          ('2019-01-02'::date),
          ('2019-01-03'::date),
          ('2019-01-04'::date),
          ('2019-01-07'::date),
          ('2019-01-08'::date),
          ('2019-03-08'::date),
          ('2019-05-01'::date),
          ('2019-05-02'::date),
          ('2019-05-03'::date),
          ('2019-05-09'::date),
          ('2019-05-10'::date),
          ('2019-06-12'::date),
          ('2019-11-04'::date)
),

 dates_include(start_time, stop_time) as (
    values -- только 2018, в 2019 нету
            ('2018-04-28 10:00:00'::timestamp, '2018-04-28 19:00:00'::timestamp),
          ('2018-06-09 10:00:00'::timestamp, '2018-06-09 19:00:00'::timestamp),
          ('2018-12-29 10:00:00'::timestamp, '2018-12-29 19:00:00'::timestamp) )
),

 schedule_base(start_time, stop_time) as (
    select d::timestamp + '10:00:00', d::timestamp + '19:00:00'
      from generate_series( (select min(start_time) from periods)::date::timestamp
                          , (select max(stop_time)  from periods)::date::timestamp
                          , '1 day'::interval ) as days(d)
    where extract(dow from d) not in (0,6)
),

 schedule as (
    select * from schedule_base
       where start_time::date not in (select d from dates_exclude)
    union
      select * from dates_include
),

 periods_wrk as (
   select p.*
        , tsrange(p.start_time, p.stop_time) * tsrange(s.start_time, s.stop_time) as wrkh
     from periods p
        , schedule s )

select id, start_time, stop_time
     , sum(coalesce(upper(wrkh)-lower(wrkh), '0 sec'::interval))
  from periods_wrk
 group by id, start_time, stop_time

Ура!… На этом можно было бы и закончить, но мы для полноты картины рассмотрим ещё некоторые смежные темы.

Дальнейшее развитие темы

Укороченные предпраздничные дни, перерывы на обед, разное расписание на разные дни недели… В принципе тут всё понятно, нужно поправить определение schedule, просто дам пару примеров.

Вот так можно задать разные время начала и окончания рабочего дня в зависимости от дня недели:

    select d + case extract(dow from d)
               when 1 then '10:00:00'::time -- пн
               when 2 then '11:00:00'::time -- вт
               when 3 then '11:00:00'::time -- ср
               -- тут остальные дни или значение по умолчанию
               else '10:00:00'::time end
         , d + case extract(dow from d) -- всегда до 19 кроме пятницы
               when 5 then '14:00:00'::time -- пт
               else '19:00:00'::time end
      from schedule_base

Если нужно учесть обеденные перерывы с 13:00 до 14:00, то вместо одного интервала в день делаем два:

    select d + '10:00:00'::time
         , d + '13:00:00'::time
      from schedule_base
    union all
    select d + '14:00:00'::time
         , d + '19:00:00'::time
      from schedule_base

Ну и так далее.

Производительность

Скажу пару слов про производительность, так как про неё постоянно возникают вопросы. Тут уже разжёвывать сильно не буду, это раздел со звёздочкой.

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

Поэтому запрос всегда пишем максимально читаемо, а оптимизировать начинаем тогда и только тогда, когда выяснится, что производительность недостаточная. Причём оптимизировать будем именно там, где производительность окажется недостаточной и ровно до той степени, когда станет достаточной. Если Вы конечно цените собственное время, и Вам есть чем заняться.

А вот не делать в запросе лишней работы — это правильно, это всегда надо стараться учитывать.

Исходя из этого, одну оптимизацию мы включим в запрос сразу — пусть каждый исходный период пересекается только с теми интервалами рабочего времени, с которыми он имеет общие точки (вместо длинного классического условия на границы диапазона удобнее использовать встроенный оператор && для типа tsrange). Эта оптимизация уже появлялась в запросе, но привела к тому, что из результатов пропали исходные периоды, которые полностью попали на нерабочее время.

Вернём эту оптимизацию обратно. Для этого воспользуемся LEFT JOIN, который сохранит все записи из таблицы periods. Теперь подзапрос periods_wrk будет выглядеть так:

, periods_wrk as (
   select p.*
        , tsrange(p.start_time, p.stop_time) * tsrange(s.start_time, s.stop_time) as wrkh
     from periods p
     left join schedule s
       on tsrange(p.start_time, p.stop_time) && tsrange(s.start_time, s.stop_time))

Анализ запроса показывает, что время на тестовых данных уменьшилась приблизительно вдвое. Так как время выполнения зависит от того, чем в тот же момент времени занимался сервер, я сделал несколько замеров и привёл некоторый «типичный» результат, не самый большой, не самый маленький, из серединки.

Старый запрос:

explain (analyse)
with periods(id, start_time, stop_time) as (
...
                                     QUERY PLAN
------------------------------------------------------------------------------------
HashAggregate  (cost=334.42..338.39 rows=397 width=36) (actual time=10.724..10.731 rows=4 loops=1)
...

Новый:

explain (analyse)
with periods(id, start_time, stop_time) as (
...
                                     QUERY PLAN
------------------------------------------------------------------------------------
HashAggregate  (cost=186.37..186.57 rows=20 width=36) (actual time=5.431..5.440 rows=4 loops=1)
...

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

И на этом я бы с оптимизациями остановился. Когда я решал эту задачу для себя, то производительности мне хватило даже в куда как более страшном виде этого запроса, но оптимизировать реально было незачем. Для получения отчёта по своим данным раз в квартал я могу и подождать лишних десять секунд. Потраченный на оптимизацию лишний час времени в таких условиях никогда не окупится.

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

Первое, что приходит в голову — это посчитать один раз и положить в базу таблицу с рабочими интервалами. Могут найтись противопоказания: если база не может быть изменена, или ожидаются сложности с поддержкой актуальных данных в такой таблице. Тогда так и придётся оставить генерацию рабочего времени «на лету» в самом запросе, благо это не слишком тяжёлый подзапрос.

Следующий и наиболее мощный (но не всегда применимый) подход — алгоритмическая оптимизация. Некоторые из таких подходов уже были представлены в комментариях к статье с условием задачи.

Мне же более всего нравится такой. Если сделать таблицу со всеми (не только рабочими) днями календаря и посчитать накопительным итогом, сколько на каждый день прошло рабочих часов от некоего «сотворения мира», то получить количество рабочих часов между двумя датами можно одной операцией вычитания. Останется только корректно учесть рабочее время за первый и последний день — и готово. Вот что у меня получилось в таком подходе:

 schedule_base(d, is_working) as (
      select '2018-01-01'::date, 0
      union all
      select d+1, case when extract(dow from d+1) not in (0,6)
                        and d+1 <> all('{2019-01-01,2019-01-02,2019-01-03,2019-01-04,2019-01-07,2019-01-08,2019-03-08,2019-05-01,2019-05-02,2019-05-03,2019-05-09,2019-05-10,2019-06-12,2019-11-04,2018-01-01,2018-01-02,2018-01-03,2018-01-04,2018-01-05,2018-01-08,2018-02-23,2018-03-08,2018-03-09,2018-04-30,2018-05-01,2018-05-02,2018-05-09,2018-06-11,2018-06-12,2018-11-05,2018-12-31}')
                         or d+1 = any('{2018-04-28,2018-06-09,2018-12-29}')
                       then 1 else 0 end
         from schedule_base where d < '2020-01-01'
),

 schedule(d, is_working, work_hours) as (
  select d, is_working
       , sum(is_working*'9 hours'::interval) over (order by d range between unbounded preceding and current row)
    from schedule_base
)

select p.*
     , s2.work_hours - s1.work_hours
       + ('19:00:00'::time - least(greatest(p.start_time::time, '10:00:00'::time), '19:00:00'::time)) * s1.is_working
       - ('19:00:00'::time - least(greatest(p.stop_time::time, '10:00:00'::time), '19:00:00'::time)) * s2.is_working as wrk
  from periods p, schedule s1, schedule s2
 where s1.d = p.start_time::date
   and s2.d = p.stop_time::date

Поясню кратко, что здесь происходит. В подзапросе schedule_base генерируем все дни календаря за два года и к каждому дню определяем признак, рабочий ли день (=1) или нет (=0). Дальше в подзапросе schedule оконной функцией считаем нарастающим итогом количество рабочих часов с 2018–01–01. Можно было бы всё в один подзапрос сделать, но получилось бы более громоздко, что ухудшило бы читаемость. Потом в основном запросе считаем разницу между количеством рабочих часов на конец и начало периода и, несколько витиевато, учитываем рабочее время для первого и последнего дня периода. Витиеватость связана с тем, чтобы сдвинуть время до начала рабочего дня к его началу, а время после окончания рабочего дня к его концу. Причём если часть запроса с shedule_base и schedule убрать в отельную заранее просчитанную таблицу (как предлагалось ранее), что запрос превратится в совсем уже тривиальный.

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

Я взял около 3 тыс. периодов. Приведу только верхнюю итоговую строчку в EXPLAIN, типичные значения такие.

Оригинальный вариант:

GroupAggregate  (cost=265790.95..296098.23 rows=144320 width=36) (actual time=656.654..894.383 rows=2898 loops=1)
...

Оптимизрованный:

Hash Join  (cost=45.01..127.52 rows=70 width=36) (actual time=1.620..5.385 rows=2898 loops=1)
...

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

Казалось бы всё хорошо, но почему, сделав такую оптимизацию, я для себя оставил первый вариант запроса до тех пор, пока его производительности будет хватать? Да потому что оптимизированный вариант несомненно быстрее, но требует куда как больше времени на понимание того, как он работает, то есть сильно ухудшилась читаемость. То есть в следующий раз, когда мне понадобится переписать запрос под свои изменившиеся условия, мне (или не мне) придётся потратить значительно больше времени на понимание того, как запрос работает.

На этом сегодня всё, держите щупальца в тепле, а я прощаюсь с вами до следующего выпуска Радио SQL.

© Habrahabr.ru