Trova tutte le intersezioni di tutti i gruppi di intervalli in PostgreSQL

Question

Sto cercando un modo efficace per trovare tutte le intersezioni tra i gruppi di intervalli di data e ora. Deve funzionare con PostgreSQL 9.2.

Diciamo che le gamme rappresentano le volte in cui una persona è disponibile a incontrarsi. Ogni persona può avere uno o più intervalli di volte quando sono disponibili. Voglio trovare tutti i periodi di tempo in cui una riunione può avere luogo (cioè durante il quale tutte le persone sono disponibili).

Questo è quello che ho ottenuto finora. Sembra funzionare, ma non penso che sia molto efficiente, dal momento che considera la disponibilità di una persona alla volta.

WITH RECURSIVE td AS 
(
    -- Test data. Returns: 
    -- ["2014-01-20 00:00:00","2014-01-31 00:00:00") 
    -- ["2014-02-01 00:00:00","2014-02-20 00:00:00") 
    -- ["2014-04-15 00:00:00","2014-04-20 00:00:00") 
    SELECT 1 AS entity_id, '2014-01-01'::timestamp AS begin_time, '2014-01-31'::timestamp AS end_time 
    UNION SELECT 1, '2014-02-01', '2014-02-28' 
    UNION SELECT 1, '2014-04-01', '2014-04-30' 
    UNION SELECT 2, '2014-01-15', '2014-02-20' 
    UNION SELECT 2, '2014-04-15', '2014-05-05' 
    UNION SELECT 3, '2014-01-20', '2014-04-20' 
) 
, ranges AS 
(
    -- Convert to tsrange type 
    SELECT entity_id, tsrange(begin_time, end_time) AS the_range 
    FROM td 
) 
, min_max AS 
(
    SELECT MIN(entity_id), MAX(entity_id) 
    FROM td 
) 
, inter AS 
(
    -- Ranges for the lowest ID 
    SELECT entity_id AS last_id, the_range 
    FROM ranges r 
    WHERE r.entity_id = (SELECT min FROM min_max) 

    UNION ALL 

    -- Iteratively intersect with ranges for the next higher ID 
    SELECT entity_id, r.the_range * i.the_range 
    FROM ranges r 
    JOIN inter i ON r.the_range && i.the_range 
    WHERE r.entity_id > i.last_id 
     AND NOT EXISTS 
     (
      SELECT * 
      FROM ranges r2 
      WHERE r2.entity_id < r.entity_id AND r2.entity_id > i.last_id 
     ) 
) 
-- Take the final set of intersections 
SELECT * 
FROM inter 
WHERE last_id = (SELECT max FROM min_max) 
ORDER BY the_range; 

Answer 1

ho creato il tsrange_interception_agg aggregata

create function tsrange_interception (
    internal_state tsrange, next_data_values tsrange 
) returns tsrange as $$ 
    select internal_state * next_data_values; 
$$ language sql; 

create aggregate tsrange_interception_agg (tsrange) (
    sfunc = tsrange_interception, 
    stype = tsrange, 
    initcond = $$[-infinity, infinity]$$ 
); 

Poi questa query

with td (id, begin_time, end_time) as 
(
    values 
    (1, '2014-01-01'::timestamp, '2014-01-31'::timestamp), 
    (1, '2014-02-01', '2014-02-28'), 
    (1, '2014-04-01', '2014-04-30'), 
    (2, '2014-01-15', '2014-02-20'), 
    (2, '2014-04-15', '2014-05-05'), 
    (3, '2014-01-20', '2014-04-20') 
), ranges as (
    select 
     id, 
     row_number() over(partition by id) as rn, 
     tsrange(begin_time, end_time) as tr 
    from td 
), cr as (
    select r0.tr tr0, r1.tr as tr1 
    from ranges r0 cross join ranges r1 
    where 
     r0.id < r1.id and 
     r0.tr && r1.tr and 
     r0.id = (select min(id) from td) 
) 
select tr0 * tsrange_interception_agg(tr1) as interseptions 
from cr 
group by tr0 
having count(*) = (select count(distinct id) from td) - 1 
; 
       interseptions     
----------------------------------------------- 
["2014-02-01 00:00:00","2014-02-20 00:00:00") 
["2014-01-20 00:00:00","2014-01-31 00:00:00") 
["2014-04-15 00:00:00","2014-04-20 00:00:00") 

Answer 2

OK, ho scritto e testato questo in TSQL ma dovrebbe funzionare o almeno essere abbastanza vicino per voi di tradurre indietro, è tutti i costrutti abbastanza vaniglia. Tranne forse il mezzo, ma può essere suddiviso in una clausola < e una clausola>. (grazie @Horse)

WITH cteSched AS (--Schedule for everyone 
    -- Test data. Returns: 
    -- ["2014-01-20 00:00:00","2014-01-31 00:00:00") 
    -- ["2014-02-01 00:00:00","2014-02-20 00:00:00") 
    -- ["2014-04-15 00:00:00","2014-04-20 00:00:00") 
    SELECT 1 AS entity_id, '2014-01-01' AS begin_time, '2014-01-31' AS end_time 
    UNION SELECT 1, '2014-02-01', '2014-02-28' 
    UNION SELECT 1, '2014-04-01', '2014-04-30' 
    UNION SELECT 2, '2014-01-15', '2014-02-20' 
    UNION SELECT 2, '2014-04-15', '2014-05-05' 
    UNION SELECT 3, '2014-01-20', '2014-04-20' 
), cteReq as ( --List of people to schedule (or is everyone in Sched required? Not clear, doesn't hurt) 
    SELECT 1 as entity_id UNION SELECT 2 UNION SELECT 3 
), cteBegins as (
    SELECT distinct begin_time FROM cteSched as T 
    WHERE NOT EXISTS (SELECT entity_id FROM cteReq as R 
         WHERE NOT EXISTS (SELECT * FROM cteSched as X 
             WHERE X.entity_id = R.entity_id 
              AND T.begin_time BETWEEN X.begin_time AND X.end_time)) 
) SELECT B.begin_time, MIN(S.end_time) as end_time 
    FROM cteBegins as B cross join cteSched as S 
    WHERE B.begin_time between S.begin_time and S.end_time 
    GROUP BY B.begin_time 
-- NOTE: This assume users do not have schedules that overlap with themselves! That is, nothing like 
-- John is available 2014-01-01 to 2014-01-15 and 2014-01-10 to 2014-01-20. 

EDIT: Aggiungere uscita dall'alto (quando eseguito su SQL-Server 2008R2)
BEGIN_TIME end_time
2014-01-20 2014-01-31
2014-02- 01 2014-02-20
2014-04-15 2014-04-20

Answer 3

Se si dispone di un numero fisso di entità che si vuole attraversare di riferimento, è possibile utilizzare un cross join per ciascuno di essi, e costruire il intersezione (utilizzando l'operatore * su intervalli).

L'utilizzo di un cross join come questo è probabilmente meno efficiente. L'esempio seguente ha più a che fare con la spiegazione dell'esempio più complesso di seguito.

WITH td AS 
(
    SELECT 1 AS entity_id, '2014-01-01'::timestamp AS begin_time, '2014-01-31'::timestamp AS end_time 
    UNION SELECT 1, '2014-02-01', '2014-02-28' 
    UNION SELECT 1, '2014-04-01', '2014-04-30' 
    UNION SELECT 2, '2014-01-15', '2014-02-20' 
    UNION SELECT 2, '2014-04-15', '2014-05-05' 
    UNION SELECT 4, '2014-01-20', '2014-04-20' 
) 
,ranges AS 
(
    -- Convert to tsrange type 
    SELECT entity_id, tsrange(begin_time, end_time) AS the_range 
    FROM td 
) 
SELECT r1.the_range * r2.the_range * r3.the_range AS r 
FROM ranges r1 
CROSS JOIN ranges r2 
CROSS JOIN ranges r3 
WHERE r1.entity_id=1 AND r2.entity_id=2 AND r3.entity_id=4 
    AND NOT isempty(r1.the_range * r2.the_range * r3.the_range) 
ORDER BY r 

In questo caso un multiplo cross join è probabilmente meno efficiente perché in realtà non hanno bisogno di avere tutte le possibili combinazioni di ogni fascia, in realtà, dal momento che isempty(r1.the_range * r2.the_range) è abbastanza per fare isempty(r1.the_range * r2.the_range * r3.the_range) vero.

Non penso che si possa evitare di passare attraverso la disponibilità di ciascuna persona al momento, dal momento che si desidera che tutti vengano comunque raggiunti.

Ciò che può essere utile è creare in modo incrementale l'insieme di intersezioni, collegando trasversalmente la disponibilità di ciascuna persona al sottoinsieme precedente che è stato calcolato utilizzando un altro CTE ricorsivo (intersections nell'esempio seguente). È quindi costruire le intersezioni in modo incrementale e liberarsi delle catene vuote, entrambi gli array memorizzati:

WITH RECURSIVE td AS 
(
    SELECT 1 AS entity_id, '2014-01-01'::timestamp AS begin_time, '2014-01-31'::timestamp AS end_time 
    UNION SELECT 1, '2014-02-01', '2014-02-28' 
    UNION SELECT 1, '2014-04-01', '2014-04-30' 
    UNION SELECT 2, '2014-01-15', '2014-02-20' 
    UNION SELECT 2, '2014-04-15', '2014-05-05' 
    UNION SELECT 4, '2014-01-20', '2014-04-20' 
) 
,ranges AS 
(
    -- Convert to tsrange type 
    SELECT entity_id, tsrange(begin_time, end_time) AS the_range 
    FROM td 
) 
,ranges_arrays AS (
    -- Prepare an array of all possible intervals per entity 
    SELECT entity_id, array_agg(the_range) AS ranges_arr 
    FROM ranges 
     GROUP BY entity_id 
) 
,numbered_ranges_arrays AS (
    -- We'll join using pos+1 next, so we want continuous integers 
    -- I've changed the example entity_id from 3 to 4 to demonstrate this. 
    SELECT ROW_NUMBER() OVER() AS pos, entity_id, ranges_arr 
    FROM ranges_arrays 
) 
,intersections (pos, subranges) AS (
    -- We start off with the infinite range. 
    SELECT 0::bigint, ARRAY['[,)'::tsrange] 
    UNION ALL 
    -- Then, we unnest the previous intermediate result, 
    -- cross join it against the array of ranges from the 
    -- next row in numbered_ranges_arrays (joined via pos+1). 
    -- We take the intersection and remove the empty array. 
    SELECT r.pos, 
      ARRAY(SELECT x * y FROM unnest(r.ranges_arr) x CROSS JOIN unnest(i.subranges) y WHERE NOT isempty(x * y)) 
    FROM numbered_ranges_arrays r 
     INNER JOIN intersections i ON r.pos=i.pos+1 
) 
,last_intersections AS (
    -- We just really want the result from the last operation (with the max pos). 
    SELECT subranges FROM intersections ORDER BY pos DESC LIMIT 1 
) 
SELECT unnest(subranges) r FROM last_intersections ORDER BY r 

non sono sicuro se questo è probabile che un rendimento migliore, purtroppo. Probabilmente avrai bisogno di un set di dati più ampio per avere benchmark significativi.