Подсчет сгруппированных пробелов во времени для диапазона времени

Question

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

starting range: 2012-01-12 00:00:00
  ending range: 2012-01-18 59:59:59

Что примерно означает:

type  10 11 12 13 14 15 16 17 18 19 20 
a        |--========]
a                             |==------]
b                 |==============--]
c     |-----===========]
d        |--=====================------]

те же данные, сгруппированные по типу:

a        |--========]         |==------]
b                 |==============--]
c     |-----===========]
d        |--=====================------]

В результате:

type  gap
---------
a     1  (yes)
b     1  (yes)
c     1  (yes)
d     0  (no)

И в конечном итоге ...

SUM(gap) AS gaps
----------------
3

ОБНОВЛЕНИЕ для уточнения:

Данные хранятся с отметками времени начала и окончания для каждого типа.Например:

id  type  start_datetime       end_datetime
--------------------------------------------------
1   a     2012-01-11 00:00:00  2012-01-14 59:59:59
2   a     2012-01-18 00:00:00  2012-01-20 59:59:59
3   b     2012-01-14 00:00:00  2012-01-19 59:59:59
4   c     2012-01-10 00:00:00  2012-01-15 59:59:59
5   d     2012-01-11 00:00:00  2012-01-20 59:59:59

Answer 1

Просто чтобы избежать двойной работы, вот данные (я заменил инклюзивный верхний пограничный отсек эксклюзивным, что более распространено, ИМХО):

-- CREATE SCHEMA tmp;
DROP TABLE tmp.gaps CASCADE;
CREATE TABLE tmp.gaps
        ( id INTEGER NOT NULL PRIMARY KEY       -- surrogate key
        , ztype CHAR(1) NOT NULL
        , start_datetime TIMESTAMP NOT NULL     -- lower boundary := inclusive
        , end_datetime TIMESTAMP NOT NULL       -- upper boundary := exclusive
        );
CREATE UNIQUE INDEX gaps_forward ON tmp.gaps(ztype,start_datetime);
CREATE UNIQUE INDEX gaps_backward ON tmp.gaps(ztype,end_datetime);

INSERT INTO tmp.gaps(id,ztype,start_datetime,end_datetime) VALUES
 (1,'a', '2012-01-11 00:00:00', '2012-01-15 00:00:00' )
,(2,'a', '2012-01-18 00:00:00', '2012-01-21 00:00:00' )
,(3,'b', '2012-01-14 00:00:00', '2012-01-20 00:00:00' )
,(4,'c', '2012-01-10 00:00:00', '2012-01-16 00:00:00' )
,(5,'d', '2012-01-11 00:00:00', '2012-01-21 00:00:00' )
,(6,'e', '2012-01-11 00:00:00', '2012-01-15 00:00:00' ) -- added this
,(7,'e', '2012-01-15 00:00:00', '2012-01-21 00:00:00' ) -- and this
        ;
-- SELECT * FROM tmp.gaps;

ОБНОВЛЕНИЕ: вот идет CTE. В первом UNION я добавляю два ложных интервала слева и справа от желаемого (12 января - 19 января) интервала.

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

-- EXPLAIN ANALYZE
WITH RECURSIVE meuk(ztype,start_datetime,end_datetime) AS (
        -- For every possible "ztype" add two dummie records
        -- just before and just after our wanted interval.
        WITH plus2 AS (
                SELECT g0.ztype,g0.start_datetime,g0.end_datetime FROM tmp.gaps g0
                WHERE (g0.start_datetime <= '2012-01-12 00:00:00' AND g0.end_datetime >= '2012-01-12 00:00:00')
                   OR (g0.start_datetime >= '2012-01-12 00:00:00' AND g0.end_datetime <= '2012-01-19 00:00:00')
                   OR (g0.start_datetime <= '2012-01-19 00:00:00' AND g0.end_datetime >= '2012-01-19 00:00:00')
                UNION ALL SELECT DISTINCT g1.ztype, '1900-01-01 00:00:00'::timestamp, '2012-01-12 00:00:00'::timestamp FROM tmp.gaps g1
                UNION ALL SELECT DISTINCT g2.ztype, '2012-01-19 00:00:00'::timestamp, '2100-01-01 00:00:00'::timestamp FROM tmp.gaps g2
                )
        SELECT p0.ztype,p0.start_datetime,p0.end_datetime
        FROM plus2 p0
                -- the start of a stretch: there is no older overlapping 
                -- (or touching) interval
        WHERE NOT EXISTS (SELECT *
                FROM plus2 nx
                WHERE nx.ztype = p0.ztype
                AND nx.start_datetime < p0.start_datetime -- older
                AND nx.end_datetime >= p0.start_datetime  -- touching or overlapping
                )
        UNION
        SELECT mk.ztype
                , LEAST(mk.start_datetime,p1.start_datetime)
                , GREATEST(mk.end_datetime,p1.end_datetime)
        FROM plus2 p1
        , meuk mk
        WHERE p1.ztype = mk.ztype
        AND (p1.start_datetime >= mk.start_datetime AND p1.start_datetime <= mk.end_datetime AND p1.end_datetime > mk.end_datetime)
        )
SELECT ztype, COUNT(*)-1 AS ngap
FROM meuk mk
WHERE NOT EXISTS (SELECT *
        FROM meuk  nx
        WHERE nx.ztype = mk.ztype
        AND (nx.start_datetime,nx.end_datetime) OVERLAPS( mk.start_datetime,mk.end_datetime)
        AND (nx.end_datetime - nx.start_datetime) > (mk.end_datetime - mk.start_datetime)
        )
GROUP BY ztype
ORDER BY ztype
        ;

Создание итоговой суммы оставлено читателю в качестве упражнения; -)

РЕЗУЛЬТАТЫ:

 ztype | ngap 
-------+------
 a     |    1
 b     |    1
 c     |    1
 d     |    0
 e     |    0
(5 rows)

Answer 2

Вот вариант ответа wildplasser, в котором вместо CTE используются окна.Основано на том же тестовом приборе:

select ztype, count(*) as gaps
from (
    select ztype, datetime, sum(n) over(partition by ztype order by datetime asc) as level
    from (
        select id, ztype, start_datetime as datetime, 1 as n from tmp.gaps
        union all
        select id, ztype, end_datetime, -1 from tmp.gaps
        union all
        select 0, ztype, '2012-01-12 00:00:00', 0 from (select distinct ztype from tmp.gaps) z
        union all
        select 0, ztype, '2012-01-19 00:00:00', 0 from (select distinct ztype from tmp.gaps) z
    ) x
) x
where level = 0 and datetime >= '2012-01-12 00:00:00' and datetime < '2012-01-19 00:00:00'
group by ztype
;

Это основано на использовании sum () в качестве агрегата окна, добавляющем 1 для начала диапазона и вычитающем 1 для конца диапазона, а затем ищущем точки, в которых работаетсумма достигает 0 в пределах целевого диапазона.Мне пришлось сделать почти то же самое, что и wildplasser, добавить пару дополнительных записей, которые ничего не вносят в конечные точки границы, чтобы были найдены группы, где ничто не покрывает границу ...

Похоже, это дешевле для тестовых данных, но я думаю, что это может сильно зависеть от отсутствия большого количества данных в таблицах для прохождения.С некоторой перестройкой (которая сделает его еще труднее для чтения), он может отработать всего два полных сканирования tmp.gaps (один из которых только что получает различные ztypes).