Computing the set difference of tables of intervals

Question

I often run into the following problem. I have two tables of intervals. They are bounded by dates (with no time component). Within each table the intervals do not overlap.

StartTs	EndTs
2015-01-03	2015-03-02
2015-03-05	2015-04-01

StartTs	EndTs
2015-01-07	2015-02-27
2015-03-01	2015-03-13
2016-01-01	2016-01-02

And I want to find the set difference of the the two tables, i.e., the intervals representing the time in the first table not in the second table.

Desired output for the dummy example above:

StartTs	EndTs
2015-01-03	2015-01-06
2015-02-28	2015-02-28
2015-03-14	2015-04-01

i.e. if the first table's dates are marked in yellow below and the ranges from the second table surrounded with a box I'd be looking for the contiguous ranges of unboxed yellow dates.

I'm currently treating intervals as inclusive on both ends, and using DateTime for my timestamps. My current approach is to take the complement of the second table via a triple self-join (yuck) and then intersecting the result with the first table via a join. Not fun.

Is there a better approach?

Answer 1

Given the various simplifying assumptions (Dates only and no overlapping intervals within a table) I might be minded to keep things simple.

First create an auxiliary numbers table (zero based)

CREATE TABLE dbo.SmallNumbers
(
Number SMALLINT PRIMARY KEY
)

INSERT INTO dbo.SmallNumbers
SELECT TOP 32768 ROW_NUMBER() OVER (ORDER BY @@SPID)-1 AS Number
FROM sys.all_columns c1, sys.all_columns c2

Then the code below expands out the ranges to their component dates, uses EXCEPT to find the difference and a gaps and islands technique to collapse the ranges back down. As each date will only be represented once we are likely only talking about expanding out to a few thousand dates per decade covered.

WITH UnmatchedDates(Date) AS
(
SELECT DATEADD(DAY,N.Number, StartTs)
FROM Table1
JOIN dbo.SmallNumbers N ON N.Number <= DATEDIFF(DAY, StartTs, EndTs)
EXCEPT 
SELECT DATEADD(DAY,N.Number, StartTs)
FROM Table2
JOIN dbo.SmallNumbers N ON N.Number <= DATEDIFF(DAY, StartTs, EndTs)
),
UnmatchedDatesWithGrp(Date, Grp) AS
(
SELECT Date, 
       DATEDIFF(DAY, 0, Date) - ROW_NUMBER() OVER (ORDER BY Date)
FROM UnmatchedDates
)
SELECT StartTs = MIN(Date), 
         EndTs = MAX(Date)
FROM UnmatchedDatesWithGrp
GROUP BY Grp

Answer 2

Two methods come to mind:

One is to identify the starts and ends of ranges via logic.

A start of a range is either a StartTs in Table1 where it’s not within another range (which handles overlapping ranges in Table1), or the day after an EndTs in Table2 which is in a Table1 range but not within another Table2 range.

An end of a range is either an EndTs in Table1 where it’s not within another range in either table, or the day before a StartTs in Table2 which is within a Table1 range but not within another a Table2 range.

So if this is correct, this logic should apply to identify all the Starts and Ends, and it should actually be complete because an End shouldn’t be able happen without a prior Start and vice-versa. If my logic is right.

This could be done with a series of WHERE EXISTS / NOT EXISTS clauses.

The second method (and my preferred) is to transform the data into a list of in = 1, out = -1 events, so that a rolling sum can identify whether that date is in a Table1 range, and whether it’s in a Table2 range (probably put the day after EndTs values). Then, comparing LAG rows, it’s easy to identify the times that a range starts (current row in a Table1 range and not in a Table2 range, where the LAG row isn’t). Similarly for the ends of ranges, where the LAG row being in and the current row being not means the day before is the end of a range.

Both these methods would then need to be transformed into the right shape as requested, which could use LAG/LEAD.

My code for the second method, built up on a series of CTEs:

drop table if exists dbo.Table1;

create table dbo.Table1 (StartTS datetime, EndTS datetime);
insert Table1 values ('20150103','20150302')
insert Table1 values ('20150305','20150401')

drop table if exists dbo.Table2;

create table dbo.Table2 (StartTS datetime, EndTS datetime);
insert Table2 values ('20150107','20150227')
insert Table2 values ('20150301','20150313')
insert Table2 values ('20160101','20160102');

go


with dates as (
select StartTS as somedate, 1 as T1, 0 as T2   from dbo.Table1
union all
select dateadd(day,1,EndTS), -1 as T1, 0 as T2 from dbo.Table1
union all
select StartTS, 0 as T1, 1 as T2               from dbo.Table2
union all
select dateadd(day,1,EndTS), 0 as T1, -1 as T2 from dbo.Table2
)
,
ins_outs as 
(
select distinct -- our rolling sums are by range, and we only want each date to appear once
    somedate
    , sum(T1) over (order by somedate range between unbounded preceding and current row) as T1
    , sum(T2) over (order by somedate range between unbounded preceding and current row) as T2
from dates
)
,
prev_row as 
(
select *
    , lag(T1,1,0) over (order by somedate) as PrevT1
    , lag(T2,1,0) over (order by somedate) as PrevT2
from ins_outs
)
, 
RangeStarts as
(
select *, 
    case 
        when T1 > 0 and T2 = 0 and (PrevT1 = 0 or PrevT2 > 0) then 'InRange' 
        when (T1 = 0 or T2 > 0) and PrevT1 > 0 and PrevT2 = 0 then 'OutRange'
    end 
    as RowType
from prev_row
)
, Ranges as 
(
select Somedate as StartTS, dateadd(day,-1,lead(Somedate) over (order by SomeDate)) as EndTs, RowType
from RangeStarts
where RowType is not null
)
select StartTS, EndTs
from Ranges
where RowType = 'InRange'
order by StartTS;