SQL: задача о рабочем времени: разбор полётов

    В эфире опять Радио SQL! Сегодня у нас совсем краткий выпуск, посвящённый подведению итогов решения задачки участниками хабросообщества. Я обещал разыграть небольшой приз, так что подвести итоги лучше небольшой, но всё же статьёй. Дописать строчку в оригинальную статью (что я, впрочем, тоже сделал) — было явно недостаточно, заинтересованные лица могут пропустить такое подведение итогов. Поэтому подстраивайте свои ложементы и вытягивайте омматофоры, мы начинаем!


    Разбор полётов


    В те дни души были смелыми, ставки – высокими, мужчины были настоящими мужчинами, женщины – настоящими женщинами, и мохнатые зверюшки с Альфы Центавра – настоящими мохнатыми зверюшками с Альфа Центавра. И все пускались навстречу неизвестности, навстречу ужасным опасностям, великим свершениям, и определению неопределенных форм глагола, чего никогда доселе не делали.

    Дуглас Адамс, Путеводитель автостопом по галактике

    Статья с условием задачи была опубликована почти в полдень, первые комментарии с работающими запросами появились уже спустя пару часов с хвостиком (прошу прощения за эээ… некоторую вольность в выражениях к хвостатым обитателям Вселенной), а первое правильно работающее решение уже к вечеру! Кто другой сказал бы, что вот, мол, везёт же некоторым — на работе ничего не делают, только хабр читают, да задачки решают… Но мы так не скажем! Мы скажем, что есть в природе правильные админы, у которых всё настроено и отстроено, и не требует при штатной эксплуатации ручного вмешательства, позволяя в освободившееся время разминать ум! И ещё скажем, что представители Западного завитка Галактики проявили небывалый интерес к приведённой задаче (по непроверенным данным отклонение составило более трёх сигм)! Общее количество индивидуумов, написавших запросы, оказалось равным почти двум десяткам, количество комментариев уверенно перевалило за сотню. И это (прикинь!) без всякой политоты, без флеймов, без троллинга и практически без набросов… Мы конечно надеялись на отклик в душах землян, именно про их офисное рабство и сформулирована задача, но такой резонанс…

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

    Первое работающее решение от the_unbridled_goose появилось уже через два часа после публикации задачи. Решение было красивым: разложить исходные периоды на часы, выкинуть из них нерабочие и посчитать сумму оставшихся, но, увы, неполным. Довести его до конца, увы, так и не получилось. Первое же полностью рабочее решение появилось к концу рабочего дня агломерации Московского региона третьей планеты Солнечной системы (XareH 18:17). Интересным оказался подход, когда длительность рабочего времени периода определялась следующим образом: считаем общее количество дней, вычитаем выходные и праздники, прибавляем дополнительные рабочие дни и результат умножаем на длительность рабочего дня в часах (OrmEugensson). Встречались также решения под MS SQL (uaggster), под Oracle (Mazdik) с последующим переводом на PostgreSQL (Mazdik, StrangerInTheKy). Был вариант с парсингом и автоматическим формированием рабочего календаря (valery1707), были домашние заготовки (Megacinder). По меньшей мере трое индивидуумов зарегистрировались, чтобы опубликовать свои решения (но это неточно, только догадки), а ещё несколько вышли из тени (написали наконец-то свои первые комментарии на Хабре).

    Остальных не перечисляю поимённо (все решения присутствуют в комментариях к исходной статье), но большое Вам спасибо за проявленный интерес и участие. А также особое спасибо за упоротостьство тем, у кого не получилось корректно и полностью решить поставленную задачу с первого раза, но кто нашёл в себе силы дойти до конца. Работа над своими ошибками и умение завершать начатое – это ценнейшие качества!

    И, наконец, обещанный победитель, который получит приглашение на PGConf.Russia 2020 – это eranthis (пройдите пожалуйста в кассу, в личных сообщениях вас ждёт сюрприз). Пожалуй что именно его решение (ссылка) показалось мне самым интересным по компактности и выразительности.

    Ещё раз спасибо всем участникам! Stay tuned!..

    P.S. Разбор задачи с решением, как я и обещал, будет, но чуть позже. Уже пишу, но времени не хватает.
    Postgres Professional
    131,40
    Разработчик СУБД Postgres Pro
    Поделиться публикацией

    Похожие публикации

    Комментарии 23

    • НЛО прилетело и опубликовало эту надпись здесь
        0
        Спасибо за поддержку. Выбирать в самом деле было сложно.
        0
        Своё решение писал, исходя из предпосылки — что, если у нас будут периоды длительностью в тысячи лет (ну или хотя бы в сотни)? :)
        • НЛО прилетело и опубликовало эту надпись здесь
          0
          Круто, почаще бы такие штуки видеть.
          Я работал с постгресом на заре свой карьеры, был тогда полным чайником, а потом жизнь заставила перейти на оракл. Теперь потихонечку начинаю использовать постгрес для своих проектов, очень познавательно и полезно получается — сразу кучу всего увидел.
            0
            Пожалуй что именно его решение (ссылка) показалось мне самым интересным по компактности и выразительности.

            Но не по производительности.
            Его решение работает в 10 раз медленнее, чем, например, мое.

            Без претензий на лавры, PostgreSQL вообще не мой родной.
            • НЛО прилетело и опубликовало эту надпись здесь
                0
                Интереса ради померял оба ваших решения на скорость. Да, ваши запросы действительно на (десятичный) порядок быстрее. 10% не уловил, более-менее равная производительность на количестве периодов около 3 тыс. Ну может чуть быстрее, но это уже сравнимо с погрешностями измерений.

                Но пожалуй производительность тут не была основным критерием, если только запрос не тормозил слишком уж чрезмерно. Интереса ради я написал запрос, который работает быстрее ваших ещё на (десятичный) порядок, избавившись от суммы по интервалам, и получив скорость работы линейно зависящую только от количества периодов. Видимо придётся добавить в разбор задачи слова про производительность.
                  0
                  Интереса ради я написал запрос, который работает быстрее ваших ещё на (десятичный) порядок, избавившись от суммы по интервалам, и получив скорость работы линейно зависящую только от количества интервалов. Видимо придётся добавить в разбор задачи слова про производительность.

                  Вот на это интересно посмотреть, буду ждать.
                    0
                    Не ждите слишком многого. Разбор решения будет интересен скорее тем, кто не представляет себе, как такие задачи вообще решаются. Для Вас, соответственно, это будет слишком тривиально.
                    0
                    Видимо придётся добавить в разбор задачи слова про производительность.
                    Конечно, на вкус и цвет все фломастеры разные, но на мое имхо, производительность в БД — это самое интересное.
                      0
                      Интереса ради я написал запрос, который работает быстрее ваших ещё на (десятичный) порядок, избавившись от суммы по интервалам, и получив скорость работы линейно зависящую только от количества интервалов. Видимо придётся добавить в разбор задачи слова про производительность.

                      Так моё ж решение так и работает, или я что-то не понимаю?
                        0
                        Да, Вы пошли именно в этом направлении, но немного не дошли до конца. Можно посчитать один раз количество рабочих часов на каждый день в календаре и дальше уже брать готовый ответ, не считая каждый раз количества рабочих и выходных дней, попадающих в период.
                        Вот так, например:
                        with recursive calendar(d, is_working) as (
                              select '2017-12-31'::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 calendar where d < '2020-01-01'
                        ), calendar_w(d, is_working, work_hours_acc) as (
                          select d, is_working
                               , sum(is_working*'9 hours'::interval) over (order by d range between unbounded preceding and current row)
                            from calendar
                        )
                        select p.*
                             , c2.work_hours_acc - c1.work_hours_acc
                               + ('19:00:00'::time - least(greatest(p.start_time::time,'10:00:00'::time),'19:00:00'::time)) * c1.is_working
                               - ('19:00:00'::time - least(greatest(p.stop_time::time, '10:00:00'::time),'19:00:00'::time)) * c2.is_working as work_hours
                          from periods p, calendar_w c1, calendar_w c2
                         where c1.d = p.start_time::date
                           and c2.d = p.stop_time::date

                          0
                          Да, Вы пошли именно в этом направлении, но немного не дошли до конца


                          хм. В моём решении смысл был другой — избавиться от перехода от данных {одна строка на период} к данным {одна строка на дату} и от последующей агрегации. В решении приведенном сверху вы красиво избавились от агрегации и от увеличения количества данных на каждую строку, но все равно осталась необходимость увеличения количества данных один раз.
                          В моём решении сложности добавляет то, что необходимо проверять попадание праздников в период. То есть у меня сложность была, грубо говоря (если для простоты считать, что джойн выполняется за константу независимую от объема данных), O(количество праздников * количество периодов), а у Вас O(количество дней между минимальной и максимальной допустимой датой + 2 * количество периодов). То есть, скорее всего, с небольшим количеством праздников или с периодами длиной в сто лет, думаю, моё решение будет работать быстрее, но с большим количеством периодов в интервале двух годов и/или большим количеством праздников — будет быстрее работать Ваше.
                            0
                            Я посчитал сразу количество рабочих часов на каждую дату и расчёт длительности для периодов в рабочих часах стал одной операцией вычитания. А у Вас в результате остались итерации по каждому из периодов. Посмотрите на планы исполнения мой и Ваш. Именно по этой причине я и сказал, что Вы не дошли до конца. В философском смысле. Уж если от внутреннего цикла избавляться, то полностью, чего уж там.

                            И, кстати, именно Ваше решение сподвигло меня на эти размышления и в конечном итоге реализацию такого подхода, как самого оптимального по времени.
                      0
                      А ваше решение работает на 10% медленнее чем моё и дело там не в постгресе:)

                      Тут можно сравнить более объективно:
                      Ваше решение
                      Мое

                      И у Вас ошибка где-то, не сходится сумма…
                      • НЛО прилетело и опубликовало эту надпись здесь
                        • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            Я лишь взял Ваше решение по вашей же ссылке. Почему у вас там оказался неверный набор выходных и праздников — спросите у себя.
                            Так что тут неизвестно кто первый не озаботился. :)

                            Ваше решение мне нравится лаконичностью, понятностью и чистотой.

                            Решение от OrmEugensson более мудреное и сложное, но и гораздо более производительное, чем наши с вами.

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

                            Мне такие кейсы встречаются чаще. Как-то даже не пришло в голову иначе протестировать.
                            • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            Не занимайтесь демагогией. Ваше решение даёт неправильный результат, потому что Вы не все даты из рабочего календаря включили в свой запрос. И чтобы получить правильный результат, надо сперва вдумчиво Ваш запрос дописать. Я на это указывал ещё в комментариях к предыдущей статье. Мне во время проверки приходилось делать исправления (что, признаться, несколько раздражало), так как я вроде бы был заводилой всей этой движухи, а прочим окружающим этим заниматься совершенно неинтересно.
                            • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      Мда… Это не бубль-гум нифига не iso.
                      Впрочем, меня обнадеживает, что я практически все понял, всего то раза три загуглив :-)
                      … можно тешить себя надеждой, что когда приспичит — смогу пересесть.

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое