Find the crossroads between date ranges in PostgreSQL

Question

I have records with two dates check_inand check_outI want to know the ranges when several people were checked at the same time.

So, if I have the following checkin / checkouts:

• Face A: 1PM - 6PM
• Person B: 3PM - 10PM
• Person C: 9PM - 11PM

I would like to receive 3PM - 6PM(Overlapping faces A and B) and 9PM - 10PM(overlapping faces B and C).

I can write an algorithm for this in linear time with code, is it possible to do this through a relational query in linear time with PostgreSQL?

It should have a minimal response, which means no overlapping ranges. Therefore, if there was a result that gave a range of 6PM - 9PMand 8PM - 10PM, that would be wrong. Instead, he should return 6PM - 10pm.

Answer 1

Assumptions

The decision is largely dependent on the definition of the exact table, including all restrictions. Due to the lack of information in the question, I will take this table:

CREATE TABLE booking (
  booking_id serial PRIMARY KEY
, check_in   timestamptz NOT NULL
, check_out  timestamptz NOT NULL
, CONSTRAINT valid_range CHECK (check_out > check_in)
);

So, no NULL values, only valid ranges with inclusive lower and exclusive upper bounds, and we don’t care who checks.

Also assuming the current version of Postgres is at least 9.2 .

Query

One way to do this is with SQL only UNION ALLand with window functions:

SELECT ts AS check_id, next_ts As check_out
FROM  (
   SELECT *, lead(ts) OVER (ORDER BY ts) AS next_ts
   FROM  (
      SELECT *, lag(people_ct, 1 , 0) OVER (ORDER BY ts) AS prev_ct
      FROM  (
         SELECT ts, sum(sum(change)) OVER (ORDER BY ts)::int AS people_ct
         FROM  (
            SELECT check_in AS ts, 1 AS change FROM booking
            UNION ALL
            SELECT check_out, -1 FROM booking
            ) sub1
         GROUP  BY 1
         ) sub2
      ) sub3
   WHERE  people_ct > 1 AND prev_ct < 2 OR  -- start overlap
          people_ct < 2 AND prev_ct > 1     -- end overlap
   ) sub4
WHERE  people_ct > 1 AND prev_ct < 2;

SQL Fiddle

Explanation

• sub1 check_in check_out . check_in , check_out .

• sub2 : sum() sum() - integer numeric :

   sum(sum(change)) OVER (ORDER BY ts)::int
  

• sub3
• sub4 , , lead().
• , , .

---

, plpgsql, dba.SE:

• PostgreSQL/SSRS

Answer 2

, .

• 0 -
• 1 - -

, 1 , - 1 .

• 000000000000000000000000 , .
• 000000000000000000000110 , - 21 23.
• 000000000000011111000000 , - 13 18.
• 000000000000000111111100 , - 15 22.

, .

• 000000000000011111111110

. Oracle, PostgreSQL.

with rec (checkin, checkout)
as ( select 13, 18 from dual 
   union all 
    select 15, 22 from dual 
   union all 
    select 21, 23 from dual )
,spanempty ( empt)
 as ( select '000000000000000000000000' from dual) ,
 spanfull( full)
 as ( select '111111111111111111111111' from dual)
, bookingbin( binbook) as ( select  substr(empt, 1, checkin) || 
        substr(full, checkin, checkout-checkin) || 
        substr(empt, checkout, 24-checkout) 
 from rec 
 cross join spanempty
 cross join spanfull ),
 bookingInt (rn, intbook) as 
 ( select rownum, bin2dec(binbook) from bookingbin),
 bitAndSum (bitAndSumm) as (
 select sum(bitand(b1.intbook, b2.intbook)) from bookingInt b1 
 join bookingInt b2 
 on b1.rn = b2.rn -1 ) ,
 SumAll (sumall) as (
 select sum(bin2dec(binbook)) from bookingBin  )
select lpad(dec2bin(sumall - bitAndSumm), 24, '0')
from SumAll, bitAndSum

:

000000000000011111111110