CODEWITHSUNDEEP
sqloracle-databaseperformance
Max
Max

Reputation: 85

Count max number of overlapping timeranges in a timerange

I explain it with an example. We have 5 events (each with an start- and end-date) which partly overlap:

create table event (
  id integer primary key,
  date_from date,
  date_to date
);
--
insert into event (id, date_from, date_to) values (1, to_date('01.01.2016', 'DD.MM.YYYY'), to_date('03.01.2016 23:59:59', 'DD.MM.YYYY HH24:MI:SS'));
insert into event (id, date_from, date_to) values (2, to_date('05.01.2016', 'DD.MM.YYYY'), to_date('08.01.2016 23:59:59', 'DD.MM.YYYY HH24:MI:SS'));
insert into event (id, date_from, date_to) values (3, to_date('03.01.2016', 'DD.MM.YYYY'), to_date('05.01.2016 23:59:59', 'DD.MM.YYYY HH24:MI:SS'));
insert into event (id, date_from, date_to) values (4, to_date('03.01.2016', 'DD.MM.YYYY'), to_date('03.01.2016 23:59:59', 'DD.MM.YYYY HH24:MI:SS'));
insert into event (id, date_from, date_to) values (5, to_date('05.01.2016', 'DD.MM.YYYY'), to_date('07.01.2016 23:59:59', 'DD.MM.YYYY HH24:MI:SS'));
--
commit;

Here the events visualized:

1.JAN  2.JAN  3.JAN  4.JAN  5.JAN  6.JAN  7.JAN  8.JAN
---------1---------         ------------2-------------
              ---------3---------
              --4--         ---------5---------

Now I would like to select the maximum number of events which overlap in a given timerange.

For the timerange 01.01.2016 00:00:00 - 08.01.2016 23:59:59 the result should be 3 because max 3 events overlap (between 03.01.2016 00:00:00 - 03.01.2016 23:59:59 and between 05.01.2016 00:00:00 - 05.01.2016 23:59:59).

For the timerange 06.01.2016 00:00:00 - 08.01.2016 23:59:59 the result should be 2 because max 2 events overlap (between 06.01.2016 00:00:00 - 07.01.2016 23:59:59).

Would there be a (performant) solution in SQL? I am thinking about performance because there could be many events in a wide timerange.

Update #1

I like MTOs answer most. It even works for the timerange 01.01.2016 00:00:00 - 01.01.2016 23:59:59. I adapted the SQL to my exact needs:

select max(num_events)
from (
  select sum(startend) over (order by dt) num_events
  from (
    select e1.date_from dt,
      1 startend
    from event e1
    where e1.date_to >= :date_from
      and e1.date_from <= :date_to
    union all
    select e2.date_to dt,
      -1 startend
    from event e2
    where e2.date_to >= :date_from
      and e2.date_from <= :date_to
  )
);

Upvotes: 0

Views: 144

Answers (4)

Stefan Riegler
Stefan Riegler

Reputation: 45

This will return all peaks of overlaps of events, including the start of the peak and the end.

select distinct
    max(e1.date_from), 
    case when
      min(e1.date_to) < min(e2.date_to)
    then
      min(e1.date_to)
    else
      min(e2.date_to)
    end,
    count(1) + 1
from event e1 inner join event e2 on (e2.date_from <= e1.date_from and e2.date_to >= e1.date_from and e1.id != e2.id)
group by e1.ID;

Upvotes: 0

MT0
MT0

Reputation: 168361

This will get all the time ranges and the count of events occurring within those ranges:

SELECT *
FROM   (
  SELECT dt AS date_from,
         LEAD( dt ) OVER ( ORDER BY dt ) AS date_to
         SUM( startend ) OVER ( ORDER BY dt ) AS num_events
  FROM   (
    SELECT date_from AS dt, 1 AS startend FROM event
    UNION ALL
    SELECT date_to, -1 FROM event
  )
)
WHERE date_from < date_to;

Upvotes: 2

guthy
guthy

Reputation: 326

You will have to break up the problem into several sub-problems:

  1. Find all affected events within your given timerange
  2. Find all starts of the affected events
  3. For each start, look how many events are overlapping at this time
  4. Find the maximum of these overlaps

You could try following query, in which these sub-problems are modeled in with-statements (common table expressions):

    with myinterval as (
        select to_date('2016-01-01 0:00:00', 'yyyy-mm-dd hh24:mi:ss') as date_from,
            to_date('2016-01-08 23:59:59', 'yyyy-mm-dd hh24:mi:ss') as date_to
        from dual
    ), affected_events as (
    select * 
    from event e
    where wm_overlaps(
                    wm_period(myinterval.date_from, myinterval.date_to),
                    wm_period(e.date_from, e.date_to)
                ) = 1
    ), starts as (
        select distinct date_from from affected_events
    ), overlapped as (
        select starts.date_from, count(*) as cnt
        from affected_events ae
        join starts on (wm_overlaps(wm_period(starts.date_from, starts.date_from+0.001), wm_period(ae.date_from, ae.date_to))= 1)
        group by starts.date_from
    )
    select max(cnt) from overlapped

Upvotes: 0

SkyHigh
SkyHigh

Reputation: 19

If you need only to get the number and don't need to operate with more precise time values, it will be just something like this:

SELECT MAX(c) max_overlap FROM
(SELECT d, COUNT(1) c 
FROM
(SELECT date_from d FROM event
UNION ALL
SELECT date_to FROM event
) A
GROUP BY A.d
) B

Otherwise it will need to use recursion etc.

Upvotes: 0

Related Questions