SQL: solução de tarefas para horário de trabalho

Olá, Radio SQL está no ar novamente! Hoje, temos uma solução para o problema que transmitimos em nossa transmissão anterior e prometemos decifrar da próxima vez. E esta próxima vez chegou.

A tarefa despertou uma resposta animada entre os humanóides da galáxia da Via Láctea (e não surpreendentemente, com a escravidão do trabalho, que eles ainda respeitam em benefício da civilização). Infelizmente, no terceiro planeta, o lançamento do observatório espacial Spektr-RG foi adiado no final de julho de 2019, o RC (cronologia local), com a ajuda da qual estava planejado transmitir este programa. Eu tive que procurar rotas de transmissão alternativas, o que levou a um pequeno atraso no sinal. Mas tudo está bem quando acaba bem.

Devo dizer imediatamente que não haverá mágica na análise da tarefa, não há necessidade de procurar revelações aqui ou esperar por alguma implementação particularmente eficaz (ou especialmente em outro sentido). Esta é apenas uma tarefa de análise. Nele, aqueles que não souberem abordar a solução de tais problemas poderão ver como resolvê-los. Além disso, não há nada de terrível aqui.

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 

A tarefa dá uma ligeira ênfase ao fato de eu ter dado conscientemente uma boa metade da condição de forma descritiva (como geralmente acontece na vida real), deixando a critério da implementação técnica como o cronograma deve ser definido. Por um lado, isso requer algumas habilidades de pensamento arquitetural. E, por outro lado, o formato pronto desse cronograma teria solicitado algum uso do modelo. E se você omitir, o pensamento e a fantasia funcionarão mais plenamente. A recepção valeu a pena completamente, permitindo-me também encontrar abordagens interessantes nas soluções publicadas.

Portanto, para resolver o problema original dessa maneira, duas subtarefas precisarão ser resolvidas:

1. Determine como definir de maneira mais compacta um cronograma de trabalho e até mesmo para que seja conveniente usar uma solução.
2. Calcule realmente a duração de cada período de origem nas horas de trabalho, de acordo com o cronograma de trabalho da subtarefa anterior.

E é melhor começar com o segundo, para entender de que forma precisamos resolver o primeiro. Resolva o primeiro e volte ao segundo para obter o resultado final.
Coletaremos o resultado gradualmente, usando a sintaxe CTE, que nos permite colocar todas as amostras de dados necessárias em subconsultas nomeadas separadas e, em seguida, vincular tudo.

Bem, vamos lá.

Calcular a duração em horário comercial

Para calcular a duração de cada um dos períodos nas horas de trabalho na testa, você precisa cruzar o período inicial (cor verde no diagrama) com os intervalos que descrevem o tempo de trabalho (laranja). Os intervalos de horário de trabalho são segundas-feiras, das 10h às 19h, terças-feiras, das 10h às 19h e assim por diante. O resultado é mostrado em azul:

A propósito, para ficar menos confuso, continuarei a me referir aos períodos iniciais como períodos iniciais e chamarei intervalos de horas de trabalho.

O procedimento deve ser repetido para cada período inicial. Os períodos iniciais para nós já estão definidos na guia de períodos ( horário de início , horário de parada) ; representaremos as horas de trabalho na forma de uma tabela, por exemplo, horário (horário de estratificação, horário de parada) , onde todos os dias úteis estão presentes. O resultado é um produto cartesiano completo de todos os períodos e intervalos iniciais do tempo de trabalho.

As interseções podem ser contadas da maneira clássica, considerando todas as opções possíveis para intervalos de interseção - interceptamos verde com laranja, o resultado é azul:

e tomando em cada caso o valor desejado para o início e o final do resultado:

  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 and p.start_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 and p.stop_time > s.start_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 

Como para cada interseção, podemos ter apenas uma das quatro opções, todas elas são combinadas em uma solicitação usando union all .

Você pode fazer o contrário usando o tipo de intervalo tsrange disponível no PostgreSQL e a operação de interseção já disponível para ele:

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

Concorde que isso é um pouco mais fácil. Em geral, existem muitas coisas convenientes no PostgreSQL; portanto, escrever consultas sobre ele é muito bom.

Gerar calendário

Agora, de volta à subtarefa com a programação do horário de trabalho.

Precisamos obter o cronograma de trabalho na forma de intervalos de horário de trabalho das 10:00 às 19:00 para cada dia útil, algo como cronograma (horário de início, horário de parada) . Como entendemos, será conveniente resolver nosso problema. Na vida real, esse cronograma deve ser definido, por dois anos, são apenas cerca de 500 registros; para fins práticos, será necessário definir até dez anos - são dois mil e quinhentos registros, lixo real para bancos de dados modernos. Mas temos um problema que será resolvido em uma solicitação e listar toda essa tabela nela não é muito prático. Vamos tentar implementá-lo de forma mais compacta.

De qualquer forma, precisamos de feriados para removê-los da programação básica e aqui apenas a listagem é adequada:

  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) ) 

e dias úteis adicionais a serem adicionados:

  dates_include(d) as ( values --  2018,  2019  ('2018-04-28'::date), ('2018-06-09'::date), ('2018-12-29'::date) ) 

A sequência de dias úteis por dois anos pode ser gerada por uma função generate_series () especial e muito adequada, lançando imediatamente sábados e domingos pelo caminho:

  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) --     

Temos dias úteis conectando tudo: geramos uma sequência de todos os dias úteis em dois anos, adicionamos dias úteis adicionais de datas_include e removemos todos os dias de datas_exclude além disso :

  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 --     ) 

E agora temos os intervalos de tempo que precisamos:

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

Então, nós temos o cronograma.

Juntando tudo

Agora teremos os cruzamentos:

  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) 

Preste atenção à condição de conexão LIGADA , ela não corresponde a dois registros correspondentes das tabelas unidas, essa correspondência não existe, mas é introduzida uma otimização que corta os intervalos de tempo de trabalho com os quais nosso período inicial não se cruza. Isso é feito usando o operador && , que verifica a interseção dos intervalos de intervalo. Isso remove muitas interseções vazias para não atrapalhar os olhos, mas, por outro lado, remove informações sobre os períodos iniciais que ficam fora do expediente. Portanto, admiramos que nossa abordagem funcione e reescrevamos a solicitação da seguinte maneira:

  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 

Em period_wrk, decompomos cada período de origem em intervalos de trabalho e, em seguida, consideramos sua duração total. O resultado foi um produto cartesiano completo de todos os períodos e intervalos, mas nenhum período foi perdido.

Tudo, o resultado é recebido. Não gostei dos valores NULL para intervalos vazios. Deixe a consulta mostrar um intervalo de tamanho zero melhor. Envolva a quantidade em coalescência () :

 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 

Todos juntos dão o resultado final:

 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 

Hurrah! .. Isso pode estar terminado, mas por uma questão de integridade, consideraremos alguns tópicos mais relacionados.

Desenvolvimento adicional do tópico

Dias pré-feriado mais curtos, intervalos para almoço, horários diferentes para dias da semana diferentes ... Em princípio, tudo está claro, é necessário corrigir a definição de horário , apenas alguns exemplos.

É assim que você pode definir diferentes horários de início e término de um dia útil, dependendo do dia da semana:

  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 

Se você precisar levar em consideração os intervalos para o almoço das 13:00 às 14:00, em vez de um intervalo por dia, faça dois:

  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 

Bem e assim por diante.

Desempenho

Vou dizer algumas palavras sobre o desempenho, pois sempre há perguntas sobre ele. Eu não vou mastigar muito, esta é uma seção com um asterisco.

Em geral, a otimização prematura é ruim. De acordo com meus muitos anos de observação, a legibilidade do código é sua vantagem mais importante. Se o código for bem lido, será mais fácil manter e desenvolver. O código legível requer implicitamente uma boa arquitetura da solução, comentários adequados e bons nomes de variáveis, compactação sem sacrificar a legibilidade, etc., ou seja, tudo pelo que o código é bom.

Portanto, a solicitação é sempre escrita da forma mais legível possível e começamos a otimizar se e somente se o desempenho for insuficiente. Além disso, otimizaremos precisamente onde o desempenho é insuficiente e exatamente na medida em que ele se torna suficiente. Se você certamente valoriza seu tempo e tem algo a fazer.

Mas não é certo fazer um trabalho desnecessário na solicitação; você deve sempre tentar levar isso em consideração.

Com base nisso, incluiremos uma otimização na consulta imediatamente - deixe que cada período de origem se cruze apenas com os intervalos de tempo de trabalho com os quais possui pontos em comum (em vez de uma longa condição clássica nos limites do intervalo, é mais conveniente usar o operador && interno para o tipo tsrange ). Essa otimização já apareceu na solicitação, mas levou ao fato de que os períodos iniciais que caíram completamente fora do horário de trabalho desapareceram dos resultados.

Traga essa otimização de volta. Para fazer isso, use LEFT JOIN , que salvará todos os registros da tabela de períodos . Agora a subconsulta period_wrk ficará assim:

 , 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)) 

A análise da solicitação mostra que o tempo nos dados do teste diminuiu cerca da metade. Como o tempo de execução depende do que o servidor estava fazendo ao mesmo tempo, fiz várias medições e dei um resultado "típico", não o maior, nem o menor, do meio.

Consulta antiga:

 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) ... 

Novo:

 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) ... 

Mas o mais importante é que essa solicitação também será dimensionada melhor, exigindo menos recursos do servidor, pois o produto cartesiano completo cresce muito rapidamente.

E nisso eu pararia com otimizações. Quando resolvi esse problema, tive desempenho suficiente mesmo em uma forma muito mais terrível dessa solicitação, mas realmente não havia necessidade de otimizar. Para obter um relatório sobre meus dados uma vez por trimestre, posso esperar mais dez segundos. A hora extra gasta em otimização nessas condições nunca será recompensada.

Mas acaba sendo desinteressante; ainda vamos pensar em como os eventos poderiam se desenvolver se a otimização em termos de tempo de execução fosse realmente necessária. Por exemplo, queremos monitorar esse parâmetro em tempo real para cada um de nossos registros no banco de dados, ou seja, para cada espirro, uma solicitação desse tipo será chamada. Bem, ou invente seu próprio motivo, por que você precisaria otimizar.

A primeira coisa que vem à mente é contar uma vez e colocar no banco de dados uma tabela com intervalos de trabalho. Pode haver contra-indicações: se o banco de dados não puder ser alterado ou forem esperadas dificuldades com o suporte de dados relevantes nessa tabela. Então você terá que deixar a geração de tempo de trabalho “on the fly” na própria solicitação, pois essa não é uma subconsulta muito pesada.

A próxima e mais poderosa abordagem (mas nem sempre aplicável) é a otimização algorítmica. Algumas dessas abordagens já foram apresentadas nos comentários do artigo com a condição do problema.

Eu gosto deste acima de tudo. Se você criar uma tabela com todos os dias (não apenas úteis) do calendário e calcular o total acumulado de quantas horas de trabalho por dia a partir de uma certa "criação do mundo" se passaram, será possível obter o número de horas de trabalho entre duas datas com uma operação de subtração. Resta apenas considerar corretamente as horas de trabalho do primeiro e do último dia - e pronto. Aqui está o que eu consegui nessa abordagem:

  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 

Vou explicar brevemente o que está acontecendo aqui. Na subconsulta schedule_base , geramos todos os dias do calendário por dois anos e a cada dia determinamos o sinal, seja o dia útil (= 1) ou não (= 0). Além disso, na subconsulta de agendamento , consideramos a função de janela como o número total acumulado de horas de trabalho de 01/01/2018. Seria possível fazer tudo em uma subconsulta, mas seria mais complicado, o que prejudicaria a legibilidade. Em seguida, na solicitação principal, consideramos a diferença entre o número de horas de trabalho no final e no início do período e, de certa forma florida, levamos em consideração as horas de trabalho do primeiro e do último dia do período. A floridez está associada à mudança do tempo antes do início do dia útil para o início e do tempo após o final do dia útil até o final. Além disso, se a parte da solicitação com shedule_base e o cronograma for removida em uma tabela pré-calculada separada (como sugerido anteriormente), essa solicitação se tornará completamente trivial.

Vamos comparar a execução em uma amostra maior para mostrar melhor a otimização realizada, por quatro períodos da condição da tarefa, mais tempo é gasto na geração de um cronograma de trabalho.

Eu levei cerca de 3 mil períodos. Vou dar apenas a linha de resumo superior em EXPLAIN, os valores típicos são os seguintes.

Opção original:

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

Otimizado:

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

O ganho de tempo foi de duas ordens de magnitude. Com o aumento do número de períodos e sua duração em anos, a diferença só aumentará.

Tudo parecia estar bem, mas por que, tendo feito essa otimização, deixei a primeira versão do pedido para mim até que seu desempenho fosse suficiente? Sim, porque a versão otimizada é, sem dúvida, mais rápida, mas requer muito mais tempo para entender como funciona, ou seja, a legibilidade piorou. Ou seja, da próxima vez que precisar reescrever a solicitação sob minhas condições alteradas, eu (ou não eu) terei que gastar muito mais tempo entendendo como a solicitação funciona.

É tudo por hoje, mantenha os tentáculos aquecidos, e digo adeus a você até o próximo lançamento do Radio SQL.