26.06.2019 11:18
bzq 23 5300 Источник
В эфире опять Радио 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. Разбор задачи с решением, как я и обещал, будет, но чуть позже. Уже пишу, но времени не хватает.

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


  1. vav180480_2
    26.06.2019 15:20
    #20327542

    Поддерживаю выбор, мне решение понравилось в том смысле что я не знал что есть нечто подобное типам *range, т.е. образовательный момент во всем конкурсе — главный, кто что то новое узнал тот тоже победил:)


    1. bzq Автор
      26.06.2019 15:29
      #20327610

      Спасибо за поддержку. Выбирать в самом деле было сложно.


  1. OrmEugensson
    26.06.2019 16:43
    #20328048

    Своё решение писал, исходя из предпосылки — что, если у нас будут периоды длительностью в тысячи лет (ну или хотя бы в сотни)? :)


    1. vav180480_2
      26.06.2019 17:07
      #20328156

      я свое решение потестил 3019 годом (очень частая ошибка кстати, у нас так клиента подключили и он около года работал бесплатно:)), рухнуло и ругнулось на память, да:) Но в задаче четко прописано — рабочее время, так что границы некие есть.


  1. StrangerInTheKy
    27.06.2019 00:17
    #20329740

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


  1. nikotin77
    27.06.2019 15:47
    #20332888

    Пожалуй что именно его решение (ссылка) показалось мне самым интересным по компактности и выразительности.

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

    Без претензий на лавры, PostgreSQL вообще не мой родной.


    1. vav180480_2
      27.06.2019 17:11
      #20333362

      А ваше решение работает на 10% медленнее чем моё и дело там не в постгресе:)


      1. bzq Автор
        27.06.2019 17:51
        #20333544

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

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


        1. nikotin77
          27.06.2019 18:28
          #20333710

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

          Вот на это интересно посмотреть, буду ждать.


          1. bzq Автор
            27.06.2019 19:35
            #20333986

            Не ждите слишком многого. Разбор решения будет интересен скорее тем, кто не представляет себе, как такие задачи вообще решаются. Для Вас, соответственно, это будет слишком тривиально.


        1. StrangerInTheKy
          27.06.2019 21:28
          #20334348

          Видимо придётся добавить в разбор задачи слова про производительность.
          Конечно, на вкус и цвет все фломастеры разные, но на мое имхо, производительность в БД — это самое интересное.


        1. OrmEugensson
          28.06.2019 10:43
          #20335684

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

          Так моё ж решение так и работает, или я что-то не понимаю?


          1. bzq Автор
            28.06.2019 13:11
            #20336396

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

            Вот так, например:
            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


            1. OrmEugensson
              28.06.2019 13:50
              #20336612

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


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


              1. bzq Автор
                28.06.2019 19:42
                #20338138

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

                И, кстати, именно Ваше решение сподвигло меня на эти размышления и в конечном итоге реализацию такого подхода, как самого оптимального по времени.


      1. nikotin77
        27.06.2019 18:26
        #20333700

        А ваше решение работает на 10% медленнее чем моё и дело там не в постгресе:)

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

        И у Вас ошибка где-то, не сходится сумма…


        1. vav180480_2
          28.06.2019 06:51
          #20335104

          И у Вас ошибка где-то, не сходится сумма…

          … или у вас;)


          1. vav180480_2
            28.06.2019 11:36
            #20335908

            … или у вас;)


            Ага, вы озаботились вставить 4000 одинаковых строк заявок, но не озаботились вставить одинаковые выходные и одинаковые перенесенные рабочие дни. Я озаботился в итоге тютелька в тютельку. И насчет «объективных» сравнений, у меня быстрее посчитает одну конкретную заявку, т.к. запрос проще и быстрее пройдет разбор, у вас посчитает быстрее общую сумму большого массива заявок. С чего вы взяли что ваша задача (подсчет общей суммы массива), более актуальнее моей (подсчет для конкретной заявки)?


            1. nikotin77
              28.06.2019 13:25
              #20336470

              Я лишь взял Ваше решение по вашей же ссылке. Почему у вас там оказался неверный набор выходных и праздников — спросите у себя.
              Так что тут неизвестно кто первый не озаботился. :)

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

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

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

              Мне такие кейсы встречаются чаще. Как-то даже не пришло в голову иначе протестировать.


              1. vav180480_2
                28.06.2019 15:02
                #20337006

                Мне такие кейсы встречаются чаще. Как-то даже не пришло в голову иначе протестировать.


                В реальной рабочей системе у вас есть заявка в состоянииях 1) «открыта» когда она заведена и в ней можно править исходные данные, время начала и время окончания 2) «закрыта» когда уже ничего нельзя править в исходных данных. Внимание вопрос, в какой момент будет рассчитываться рабочее время заявки? В момент ее закрытия, в ходе операции закрытия над конкретной ОДНОЙ заявкой с конкретным ID. При этом мы в РЕАЛЬНОМ ВРЕМЕНИ имеем актуальную информацию об отработанном времени и соответственно наших затратах на оное, при этом временные затраты на этот расчет заявок будут растянуты во времени, закрыли — тут же посчитали, затратив минимум ресурсов. Или мы просто переведем ее в состояние «закрыта» а потом, неизвестно когда, будем рассчитывать отработанное время больших массивов заявок, при этом мы должны ввести третье состояние «рассчитана», чтобы не пересчитывать два раза, при этом у нас нет актуальных данных в каждый момент времени, а есть только данные последнего массового расчета предыдущего массива, при этом система понесет пиковую нагрузку в момент массового перерасчета и редактирования записей, может что то подвесить или с чем то сконфликтовать. Странные у вас кейсы:) А так то в оракле точно (в посгресе не помню), есть подсказки оптимизатору на ускоренный возврат либо первой записи либо всех записей, потому как и то и это важны в определенных ситуациях. В нашем случае оптимально иметь 2 состояния заявки вместо 3, и рассчитывать время в момент закрытия. Т.е. тестирование быстродействия это не только на массиве записей (когда время разбора запроса относительно не велико), но и на одной записи (когда время разбора относительно велико и именно оно определяет быстродействие) В нашем случае нужно тестировать быстродействие именно на одной записи, т.к. в реальной боевой системе оптимальнее считать именно по одной заявке.


          1. bzq Автор
            28.06.2019 12:47
            #20336258

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


            1. vav180480_2
              28.06.2019 13:06
              #20336358
              -1

              Демагогия, это когда говорят «у ВАС ошибка» вместо «у НАС не сходятся результаты». А чтобы не надо было вдумчиво дописывать, нудно сначала вдумчиво дать ВСЕ исходные данные. В частности вы обязали ВСЕХ искать перечень праздников и переносов, вместо того чтобы САМОМУ все сделать, выложить или дать ссылку. Т.е. вместо того чтобы затратить лишние 30минут, вы заставили ВСЕХ это проделать, в итоге человечество потеряло X*30минут времени, где X-количество участников, причем из-за того что источники у всех были разные, разными были и перечни праздников (например не граждане РФ по инерции могли взять праздники и переносы Украины), а потом вы же создали СЕБЕ сложности при сверке, затратив гораздо больше чем 30минут. Т.е. все как обычно, переложили на программистов то что должен изначально делать постановщик, плохо стало в итоге всем. Я из просмотра альтернативных решений извлек свои уроки, вы из неправильной и не полной постановки задачи, думаю должны извлечь свои;)


  1. uaggster
    28.06.2019 20:49
    #20338260

    Мда… Это не бубль-гум нифига не iso.
    Впрочем, меня обнадеживает, что я практически все понял, всего то раза три загуглив :-)
    … можно тешить себя надеждой, что когда приспичит — смогу пересесть.