Como obter intervalos distintos não sobrepostos de uma tabela do PostgreSQL?

Para resolver este problema fiz o seguinte:

Explicação "fácil":

Para esta parte, adicionei um pouco à definição da tabela fornecida pelo OP. Acredito firmemente que o DDL deve ser usado o máximo possível para "guiar" todo o processo de programação de banco de dados e pode ser muito mais poderoso - um exemplo disso seria SQL em CHECKrestrições - até agora fornecido apenas pelo Firebird ( exemplo aqui ) e H2 (veja referência aqui ).

No entanto, tudo isso é muito bom, mas temos que lidar com os recursos 9.6 do PostgreSQL - a versão do OP. Meu DDL ajustado para a explicação "simples" (veja o violino inteiro aqui ):

CREATE TABLE sessions
(
        id serial NOT NULL PRIMARY KEY, 
        ctn INT NOT NULL, 
        f_day DATE NOT NULL,
        f_time TIME(0) NOT NULL,
        l_time TIME(0) NOT  NULL,
        CONSTRAINT ft_less_than_lt_ck CHECK (f_time < l_time),
        CONSTRAINT ctn_f_day_f_time_uq UNIQUE (ctn, f_day, f_time),
        CONSTRAINT ctn_f_day_l_time_uq UNIQUE (ctn, f_day, l_time)
        -- could put in a DISTINCT somewhere if you don't have these constraints
        -- maybe has TIME(2) - but see complex solution
);

Índices:

CREATE INDEX ctn_ix ON sessions USING BTREE (ctn ASC);
CREATE INDEX f_day_ix ON sessions USING BTREE (f_day ASC);
CREATE INDEX f_time_ix ON sessions USING BTREE (f_time ASC);

Apenas um ponto a ser observado: não use palavras- chave SQL como nomes de tabelas ou colunas - dayé uma palavra-chave! Pode ser confuso para depurar &c - simplesmente não é uma boa prática. Eu mudei seu nome de campo original daypara f_day- observe todas as maiúsculas e minúsculas do python! Faça o que fizer, tenha um método padrão de nomear variáveis ​​e cumpra-o - existem muitos documentos de padrões de codificação por aí.

A mudança para 'f_day' não tem efeito no resto do SQL, pois não levamos em consideração as sessões que abrangem a meia-noite. Levar em conta isso pode ser feito com relativa facilidade fazendo o seguinte (veja o violino).

SELECT (f_day + f_time)::TIMESTAMP FROM sessions;

Agora com o advento das GENERATEDcolunas, você nem precisa se preocupar com isso - basta ter um GENERATEDcampo como acima!

Se uma restrição para o segundo é impraticável - logins ao mesmo tempo, você pode usar TIME(2) (or 3..6)para garantir a exclusividade. Se [você não quer | não pode ter] UNIQUErestrições, você pode colocar em DISTINCTseu SQL para tempos de login e logout idênticos - embora isso seja improvável.

O fato é que alguns DDL simples como esse simplificam enormemente seu SQL subsequente (veja a discussão no final da explicação "complexa" abaixo).

Você também pode querer colocar ctne/ou em suas restrições dayDDL como mostrado? UNIQUEEu também adicionei o que eu acho que podem ser bons índices! Você também pode querer investigar o OVERLAPSoperador?

Quanto aos dados de exemplo, também adicionei alguns registros para testar minha solução da seguinte forma:

INSERT INTO sessions (id, ctn, day, f_time, l_time)
VALUES
( 1, 707, '2019-06-18', '10:48:25', '10:56:17'), 
( 2, 707, '2019-06-18', '10:53:17', '11:00:49'),
( 3, 707, '2019-06-18', '10:54:31', '10:59:43'),  -- record 3 is completely covered 
                                                  -- by record 2

( 4, 707, '2019-06-18', '11:03:59', '11:10:39'), 
( 5, 707, '2019-06-18', '11:04:41', '11:08:02'), -- GROUP 2 record 6 completely
                                                 -- covers record 7
                                                 
( 6, 707, '2019-06-18', '11:11:04', '11:19:39'), -- GROUP 3

( 7, 707, '2019-06-18', '12:15:15', '13:13:13'),
( 8, 707, '2019-06-18', '13:04:41', '13:20:02'), 
( 9, 707, '2019-06-18', '13:17:17', '13:22:22'), -- GROUP 4

(10, 707, '2019-06-18', '14:05:17', '14:14:14'); -- GROUP 5

Vou percorrer minha lógica passo a passo - bom para você talvez, mas também para mim, pois me ajuda a esclarecer meu pensamento e garantirá que as lições que aprendi com este exercício permaneçam comigo - "Eu ouço e Eu esqueço. Eu vejo e lembro. Eu faço e eu entendo." - Confúcio .

Todos os itens a seguir estão incluídos no violino.

/**

So, the desired result is:

Interval 1 - start: 10:48:25 - end 11:00:49
Interval 2 - start: 11:03:59 - end 11:10:39 
Interval 3 - start: 11:11:04 - end 11:19:39
Interval 4 - start: 12:15:15 - end 13:22:22
Interval 5 - start: 14:05:17 - end 14:14:14

**/

O primeiro passo é usar a LAGfunção ( documentation ) da seguinte forma:

SELECT 
  s.id AS id, s.ctn AS ctn, s.f_time AS ft, s.l_time AS lt, 
  CASE
    WHEN LAG(s.l_time) OVER () > f_time THEN 0
    ELSE 1
  END AS ovl
FROM sessions s

Resultado:

id  ctn     ft  lt  ovl
1   707     10:48:25    10:56:17    1
2   707     10:53:17    11:00:49    0
3   707     10:54:31    10:59:43    0
4   707     11:03:59    11:10:39    1
5   707     11:04:41    11:08:02    0
6   707     11:11:04    11:19:39    1
7   707     12:15:15    13:13:13    1
8   707     13:04:41    13:20:02    0
9   707     13:17:17    13:22:22    0
10  707     14:05:17    14:14:14    1

Portanto, sempre que houver um novo intervalo, haverá um 1 na ovlcoluna (sobreposição).

Em seguida, tomamos o cumulativo SUMdesses 1s da seguinte forma:

SELECT 
  t1.id, t1.ctn, t1.ft, t1.lt, t1.ovl,
  SUM(ovl) OVER (ORDER BY t1.ft ASC ROWS BETWEEN UNBOUNDED PRECEDING 
                                          AND CURRENT ROW) AS s
FROM
(
  SELECT 
    s.id AS id, s.ctn AS ctn, s.f_time AS ft, s.l_time AS lt, 
    CASE
      WHEN LAG(s.l_time) OVER () > f_time THEN 0
      ELSE 1
    END AS ovl
  FROM sessions s
) AS t1
ORDER BY lt, id

Resultado:

id  ctn     ft  lt  ovl     s
1   707     10:48:25    10:56:17    1   1
3   707     10:54:31    10:59:43    0   1
2   707     10:53:17    11:00:49    0   1
5   707     11:04:41    11:08:02    0   2
4   707     11:03:59    11:10:39    1   2
6   707     11:11:04    11:19:39    1   3
7   707     12:15:15    13:13:13    1   4
8   707     13:04:41    13:20:02    0   4
9   707     13:17:17    13:22:22    0   4
10  707     14:05:17    14:14:14    1   5

Então, agora "dividimos" e temos uma maneira de distinguir entre nossos intervalos - cada intervalo tem um valor diferente de s- 1..5.

Então, agora queremos obter o menor valor de f_timee o maior valor de l_timepara esses intervalos. Minha primeira tentativa usando MAX()e MIN()ficou assim:

SELECT 
  ROW_NUMBER() OVER (PARTITION BY s) AS rn,
  MIN(ft) OVER (PARTITION BY s ORDER BY ft, lt) AS min_f, 
  MAX(lt) OVER (PARTITION BY s ORDER BY ft, lt) AS max_l,
  s
FROM
(
  SELECT 
    t1.id, t1.ctn, t1.ft, t1.lt, t1.ovl,
    SUM(ovl) OVER (ORDER BY t1.ft ASC ROWS BETWEEN UNBOUNDED PRECEDING 
                                           AND CURRENT ROW) AS s
  FROM
  (
    SELECT 
      s.id AS id, s.ctn AS ctn, s.f_time AS ft, s.l_time AS lt, 
      CASE
        WHEN LAG(s.l_time) OVER () > f_time THEN 0
        ELSE 1
      END AS ovl
    FROM sessions s
  ) AS t1;
  ORDER BY id, lt
)AS t2
ORDER BY s, rn ASC, min_f;

Resultado:

rn  min_f   max_l   s
1   10:48:25    10:56:17    1
2   10:48:25    11:00:49    1
3   10:48:25    11:00:49    1
1   11:03:59    11:10:39    2
2   11:03:59    11:10:39    2
1   11:11:04    11:19:39    3
1   12:15:15    13:13:13    4
2   12:15:15    13:20:02    4
3   12:15:15    13:22:22    4
1   14:05:17    14:14:14    5

Observe como temos que obter rn= 3 para o primeiro intervalo, rn= 3 para o quarto e valores diferentes de rnpara diferentes intervalos - se houvesse 7 subintervalos formando um intervalo, teríamos que recuperar rn= 7 - isso me deixou perplexo por um tempo!

Então o poder das funções do Windows veio em socorro - se você classificar o MAX()e MIN()de maneira diferente, o resultado correto cai em nosso colo:

SELECT 
  ROW_NUMBER() OVER (PARTITION BY s) AS rn,
  MIN(ft) OVER (PARTITION BY s ORDER BY ft, lt DESC) AS min_f, 
  MAX(lt) OVER (PARTITION BY s ORDER BY ft DESC, lt) AS max_l,
  s
FROM
(
  SELECT 
    t1.id, t1.ctn, t1.ft, t1.lt, t1.ovl,
    SUM(ovl) OVER (ORDER BY t1.ft ASC ROWS BETWEEN UNBOUNDED PRECEDING 
                                           AND CURRENT ROW) AS s
  FROM
  (
    SELECT 
      s.id AS id, s.ctn AS ctn, s.f_time AS ft, s.l_time AS lt, 
      CASE
        WHEN LAG(s.l_time) OVER () > f_time THEN 0
        ELSE 1
      END AS ovl
    FROM sessions s
  ) AS t1
  ORDER BY id, lt
)AS t2
ORDER BY s, rn ASC, min_f;

Resultado:

rn  min_f   max_l   s
1   10:48:25    11:00:49    1
2   10:48:25    11:00:49    1
3   10:48:25    10:59:43    1
1   11:03:59    11:10:39    2
2   11:03:59    11:08:02    2
1   11:11:04    11:19:39    3
1   12:15:15    13:22:22    4
2   12:15:15    13:22:22    4
3   12:15:15    13:22:22    4
1   14:05:17    14:14:14    5

Observe que agora, rn= 1 é sempre nosso registro desejado - este é o resultado de:

  MIN(ft) OVER (PARTITION BY s ORDER BY ft, lt DESC) AS min_f, 
  MAX(lt) OVER (PARTITION BY s ORDER BY ft DESC, lt) AS max_l,

Observe que para MIN(), a ordenação é por lt DESCe para MAX()(particionado por intervalo - ou seja s) é por ft DESC. Isso combina o menor ftcom o maior lt, que é o que queremos.

Este é essencialmente o nosso resultado desejado - basta adicionar um pouco de organização e formatação de acordo com os requisitos do OP e estamos prontos. Esta parte também demonstra o uso de outra função Window muito útil - ROW_NUMBER().

SELECT 
  ROW_NUMBER() OVER () AS "Interval No.", 
  ' Start time: ' AS " ",
  t3.min_f AS "Interval start" , 
  ' End time: ' AS " ",
  t3.max_l AS "Interval stop", 
  ' Duration: ' AS " ",
  (t3.max_l - t3.min_f) AS "Duration"
FROM
(
  SELECT 
    ROW_NUMBER() OVER (PARTITION BY s) AS rn,
    MIN(ft) OVER (PARTITION BY s ORDER BY ft, lt DESC) AS min_f, 
    MAX(lt) OVER (PARTITION BY s ORDER BY ft DESC, lt) AS max_l,
    s
  FROM
  (
    SELECT 
      t1.id, t1.ctn, t1.ft, t1.lt, t1.ovl,
      SUM(ovl) OVER (ORDER BY t1.ft ASC ROWS BETWEEN UNBOUNDED PRECEDING 
                                             AND CURRENT ROW) AS s
    FROM
    (
      SELECT 
        s.id AS id, s.ctn AS ctn, s.f_time AS ft, s.l_time AS lt, 
        CASE
          WHEN LAG(s.l_time) OVER () > f_time THEN 0
          ELSE 1
        END AS ovl
      FROM sessions s
    ) AS t1
    ORDER BY id, lt
  )AS t2
  ORDER BY s, rn ASC, min_f
) AS t3 
WHERE t3.rn = 1;

Resultado final:

Interval No.        Interval start      Interval stop       Duration
1    Start time:    10:48:25     End time:  11:00:49     Duration:  00:12:24
2    Start time:    11:03:59     End time:  11:10:39     Duration:  00:06:40
3    Start time:    11:11:04     End time:  11:19:39     Duration:  00:08:35
4    Start time:    12:15:15     End time:  13:22:22     Duration:  01:07:07
5    Start time:    14:05:17     End time:  14:14:14     Duration:  00:08:57

Não posso dar garantias sobre o desempenho desta consulta se houver um grande número de registros, veja o resultado EXPLAIN (ANALYZE, BUFFERS)no final do violino. No entanto, estou assumindo que, como está em um formato de estilo de relatório, pode ser para um determinado valor de ctne/ou day- ou seja, não há muitos registros?

Explicação "complexa":

Não mostrarei todas as etapas - depois de eliminar os f_times e s duplicados l_time, as etapas são idênticas.

Aqui, a definição e os dados da tabela são um pouco diferentes (fiddle disponível aqui ):

CREATE TABLE sessions
(
        id serial NOT NULL PRIMARY KEY, 
        ctn INT NOT NULL, 
        f_day DATE NOT NULL,
        f_time TIME(0) NOT NULL,
        l_time TIME(0) NOT  NULL,
        CONSTRAINT ft_lt_lt CHECK (f_time < l_time),
        -- CONSTRAINT ft_uq UNIQUE (f_time),
        -- CONSTRAINT lt_uq UNIQUE (l_time)
        CONSTRAINT ft_lt_uq UNIQUE(f_time, l_time) 
        -- could put in a DISTINCT somewhere to counter this possibility or
        -- maybe have TIME(2) to ensure no duplicates?
);

As únicas restrições que mantive são CHECK (f_time < l_time)(não poderia ser de outra forma) e UNIQUE f_time, l_time(talvez adicionar daye/ou ctna isso - o conselho TIME(2) or (3...6)acima também se aplica.

Vou deixar para o leitor aplicar UNIQUEa combinações de ctne f_dayconforme aplicável!

INSERT INTO sessions (id, ctn, day, f_time, l_time)
VALUES
( 1, 707, '2019-06-18', '10:48:25', '10:56:17'), -- note - same l_times
( 2, 707, '2019-06-18', '10:48:33', '10:56:17'), -- need one with lowest f_time
( 3, 707, '2019-06-18', '10:53:17', '11:00:49'),
( 4, 707, '2019-06-18', '10:54:31', '10:59:43'), -- note - same f_times
                                                 -- need one with greatest l_time
( 5, 707, '2019-06-18', '10:54:31', '10:57:37'), -- GROUP 1

( 6, 707, '2019-06-18', '11:03:59', '11:10:39'), 
( 7, 707, '2019-06-18', '11:04:41', '11:08:02'), -- GROUP 2, record 6 completely
                                                 -- covers record 7
( 8, 707, '2019-06-18', '11:11:04', '11:19:39'), -- GROUP 3

( 9, 707, '2019-06-18', '12:15:15', '13:13:13'),
(10, 707, '2019-06-18', '13:04:41', '13:20:02'), 
(11, 707, '2019-06-18', '13:17:17', '13:22:22'), -- GROUP 4

(12, 707, '2019-06-18', '14:05:17', '14:14:14'); -- GROUP 5

Eu adicionei alguns registros potencialmente "problemáticos" (2 e 4) com o mesmo f_timee l_timedentro do mesmo intervalo. Assim, no caso de um idêntico f_time, queremos o subintervalo com o maior l_timee vice-versa para o caso de um idêntico l_time(ou seja, o menor f_time).

So, what I did in this case was to eliminate duplicates by chaining CTE's (aka the WITH clause) as follows:

WITH cte1 AS 
(
  SELECT s.*, t.mt, t.lt
  FROM sessions s
  JOIN
  (
    SELECT
      DISTINCT 
      ctn,
      MIN(f_time) AS mt,
      l_time AS lt
    FROM sessions
    GROUP BY ctn, l_time
    ORDER BY l_time
  ) AS t
  ON (s.ctn, s.f_time, s.l_time) = (t.ctn, t.mt, t.lt)
  ORDER BY s.l_time
), 
cte2 AS
(
  SELECT
    DISTINCT
    ctn,
    f_time AS ft,
    MAX(lt) AS lt
  FROM cte1
  GROUP BY ctn, f_time
  ORDER BY f_time
)
SELECT * FROM cte2
ORDER BY ft;

Result:

ctn     ft  lt
707     10:48:25    10:56:17
707     10:53:17    11:00:49
707     10:54:31    10:59:43
707     11:03:59    11:10:39
707     11:04:41    11:08:02
707     11:11:04    11:19:39
707     12:15:15    13:13:13
707     13:04:41    13:20:02
707     13:17:17    13:22:22
707     14:05:17    14:14:14

And then I treat cte2 as the starting point for the process in the "easy" explanation.

The final SQL is as follows:

WITH cte1 AS 
(
  SELECT s.*, t.mt, t.lt
  FROM sessions s
  JOIN
  (
    SELECT
      DISTINCT 
      ctn,
      MIN(f_time) AS mt,
      l_time AS lt
    FROM sessions
    GROUP BY ctn, l_time
    ORDER BY l_time
  ) AS t
  ON (s.ctn, s.f_time, s.l_time) = (t.ctn, t.mt, t.lt)
  ORDER BY s.l_time
), 
cte2 AS
(
  SELECT
    DISTINCT
    ctn,
    f_time AS ft,
    MAX(lt) AS lt
  FROM cte1
  GROUP BY ctn, f_time
  ORDER BY f_time
)
SELECT 
  ROW_NUMBER() OVER () AS "Interval No.", 
  ' Start time: ' AS " ",
  t3.min_f AS "Interval start" , 
  ' End time: ' AS " ",
  t3.max_l AS "Interval stop", 
  ' Duration: ' AS " ",
  (t3.max_l - t3.min_f) AS "Duration"
FROM
(
  SELECT 
    ROW_NUMBER() OVER (PARTITION BY s) AS rn,
    MIN(ft) OVER (PARTITION BY s ORDER BY ft, lt DESC) AS min_f, 
    MAX(lt) OVER (PARTITION BY s ORDER BY ft DESC, lt) AS max_l,
    s
  FROM
  (
    SELECT 
    t1.ctn, t1.ft, t1.lt, t1.ovl,
    SUM(ovl) OVER (ORDER BY t1.ft ASC ROWS BETWEEN UNBOUNDED PRECEDING 
                                           AND CURRENT ROW) AS s
    FROM
    (
      SELECT 
        c.ctn AS ctn, c.ft AS ft, c.lt AS lt, 
        CASE
          WHEN LAG(c.lt) OVER () > ft THEN 0
          ELSE 1
        END AS ovl
      FROM cte2 c
    ) AS t1
    ORDER BY t1.lt
  ) AS t2
  ORDER BY s, rn ASC, min_f
) AS t3
WHERE t3.rn = 1
ORDER BY t3.rn;

Result:

Interval No.        Interval start      Interval stop       Duration
1    Start time:    10:48:25     End time:  11:00:49     Duration:  00:12:24
2    Start time:    11:03:59     End time:  11:08:02     Duration:  00:04:03
3    Start time:    11:11:04     End time:  11:19:39     Duration:  00:08:35
4    Start time:    12:15:15     End time:  13:22:22     Duration:  01:07:07
5    Start time:    14:05:17     End time:  14:14:14     Duration:  00:08:57

As you can see, it's pretty hairy stuff - not having the UNIQUE constraints in the DDL has doubled the length of the SQL and the time taken for the planning and executions stages, and made it pretty horrible into the bargain.

See the end of the fiddle for the plans for both queries! Lessons to be learnt there! As a rule of thumb, the longer the plan, the slower the query!

I'm not sure that the indexes can play any role here since we're selecting from the entire table and it's very small! If we were filtering a large table by ctn and/or f_day and/or f_time, I'm pretty sure that we would start to see differences in the plans (and timings!) if there were no indexes!

I used the accepted answer for my own needs until I found a limit:

What if we have these rows ?

( 9, 707, '2019-06-18', '12:15:15', '13:13:13'),
(10, 707, '2019-06-18', '13:04:41', '13:10:02'), 
(11, 707, '2019-06-18', '13:12:17', '13:22:22'),

Both queries create a new group starting on row 10 instead of grouping these 3 rows together.

 Interval No. |               | Interval start |             | Interval stop |             | Duration
--------------+---------------+----------------+-------------+---------------+-------------+----------
            1 |  Start time:  | 10:48:25       |  End time:  | 11:00:49      |  Duration:  | 00:12:24
            2 |  Start time:  | 11:03:59       |  End time:  | 11:10:39      |  Duration:  | 00:06:40
            3 |  Start time:  | 11:11:04       |  End time:  | 11:19:39      |  Duration:  | 00:08:35
            4 |  Start time:  | 12:15:15       |  End time:  | 13:13:13      |  Duration:  | 00:57:58
            5 |  Start time:  | 13:12:17       |  End time:  | 13:22:22      |  Duration:  | 00:10:05
            6 |  Start time:  | 14:05:17       |  End time:  | 14:14:14      |  Duration:  | 00:08:57
Intervals 4 and 5 are overlapping.

The answer is to tweak the core query

WHEN LAG(c.lt) OVER () > ft THEN 0

needs to be replace by

WHEN max(c.lt) over (order by c.ft, c.lt rows between unbounded preceding and 1 preceding) > ft THEN 0

then you'll get:

 Interval No. |               | Interval start |             | Interval stop |             | Duration
--------------+---------------+----------------+-------------+---------------+-------------+----------
            1 |  Start time:  | 10:48:25       |  End time:  | 11:00:49      |  Duration:  | 00:12:24
            2 |  Start time:  | 11:03:59       |  End time:  | 11:10:39      |  Duration:  | 00:06:40
            3 |  Start time:  | 11:11:04       |  End time:  | 11:19:39      |  Duration:  | 00:08:35
            4 |  Start time:  | 12:15:15       |  End time:  | 13:22:22      |  Duration:  | 01:07:07
            5 |  Start time:  | 14:05:17       |  End time:  | 14:14:14      |  Duration:  | 00:08:57
(5 rows)