How to find overlapping periods recursively in SQL Server

Question

I have this example dataset

ID  StartDate   EndDate
------------------------------
1   2014-01-05  2014-01-10
2   2014-01-06  2014-01-11
3   2014-01-07  2014-01-12
4   2014-01-08  2014-01-13
5   2014-01-09  2014-01-14
6   2014-01-26  2014-01-31
7   2014-01-27  2014-02-01
8   2014-01-28  2014-02-02
9   2014-01-29  2014-02-03
10  2014-01-30  2014-02-04

I want to select any rows that overlap a supplied period, and any rows those overlap with and so on.

So If I want to select any rows that over lap period 2014-01-06 to 2014-01-07

The following are directly overlapping (immediate overlaps)

1   2014-01-05  2014-01-10
2   2014-01-06  2014-01-11

But I also need rows that overlap with 1 and 2 (child overlap)

3   2014-01-07  2014-01-12
4   2014-01-08  2014-01-13
5   2014-01-09  2014-01-14

And if 3 to 5 had overlaps, return them too. but in this case, there are none.

This is my attempt so far but it has two problems I see that I don't know how to fix.

;WITH cte
AS 
(
    SELECT  t.ID, 
            t.StartTime, 
            t.EndTime
    FROM    
            dbo.Tasks AS t
    UNION ALL
    SELECT  t.ID, 
            t.StartTime, 
            t.EndTime 
    FROM    
            dbo.Tasks AS t INNER JOIN
            cte AS c ON t.StartTime < c.EndTime
                    AND t.EndTime > c.StartTime

)
SELECT * FROM cte AS a WHERE   a.StartTime < @NewEnd
                    AND a.EndTime > @NewStart

When it goes to get overlapping periods of child overlap, the immediate overlap is re-included and causes an infinite recursion. And Secondly,

SELECT * FROM cte AS a WHERE   a.StartTime < @NewEnd
                        AND a.EndTime > @NewStart

The where clause will filter out any recursively found overlaps.

Answer 1

I would first work out where the islands are in your data set, and only after that, work out which ones are overlapped by your query ranges:

declare @t table (ID int,StartDate date,EndDate date)
insert into @t(ID,StartDate,EndDate) values
(1   ,'20140105','20140110'),
(2   ,'20140106','20140111'),
(3   ,'20140107','20140112'),
(4   ,'20140108','20140113'),
(5   ,'20140109','20140114'),
(6   ,'20140126','20140131'),
(7   ,'20140127','20140201'),
(8   ,'20140128','20140202'),
(9   ,'20140129','20140203'),
(10  ,'20140130','20140204')

declare @Start date
declare @End date
select @Start='20140106',@End='20140107'

;With PotIslands as (
    --Find ranges which aren't overlapped at their start
    select StartDate,EndDate from @t t where
        not exists (select * from @t t2 where
                      t2.StartDate < t.StartDate and
                      t2.EndDate >= t.StartDate)
    union all
    --Extend the ranges by any other ranges which overlap on the end
    select pi.StartDate,t.EndDate
    from PotIslands pi
            inner join
        @t t
            on
                pi.EndDate >= t.StartDate and pi.EndDate < t.EndDate
), Islands as (
    select StartDate,MAX(EndDate) as EndDate from PotIslands group by StartDate
)
select * from Islands i where @Start <= i.EndDate and @End >= i.StartDate

Result:

StartDate  EndDate
---------- ----------
2014-01-05 2014-01-14

If you need the individual rows, you can now join the selected islands back to the @t table for a simple range query.

This works because, for example, if any row within an island is ever included in a range, the entire remaining rows on an island will always also be included. So we find the islands first.

Answer 2

This should do it, you could put it into a function if needed and use a cross apply to join to another table. I did not test it but it should work with minimal (if any) errors.

declare @rt table
(
    ID int not null,
    StartTime date not null,
    EndTime date not null
)

insert into @rt (ID, StartTime, EndTime)
select t.*
from Tasks t
where (@StartTime <= t.StartTime and @EndTime  > t.StartTime)
    or (@StartTime < t.EndTime and @EndTime  >= t.EndTime)

declare @found int = @@rowcount

while @found > 0
begin
    insert into @rt (ID, StartTime, EndTime)
    select t.*
    from Tasks t
    left join @rt rt
        on (rt.StartTime <= t.StartTime and rt.EndTime  > t.StartTime)
        or (rt.StartTime < t.EndTime and rt.EndTime  >= t.EndTime)
    where t.ID not in (select ID from @rt)

    set @found = @@rowcount
end

select * from @rt