Interesting SQL puzzle

Question

Without loops or cursors, how do you take a list of date intervals and turn them into a string of 1s and 0s such that:

each bit represents each day from min(all the dates) to max(all the dates)
the bit is 1 if that day falls inside any of the date intervals
the bit is 0 if that day does not fall in any of the intervals

So for example, if the intervals were:

1/1/2011 to 1/2/2011
1/4/2011 to 1/5/2011

Then the SQL you write should output 11011. Here is a setup script you could use:

declare @TimeSpan table
(
    start datetime
    ,finish datetime
)

-- this is a good data set, with overlapping and non-overlapping time spans
insert into @TimeSpan values ('02/02/2010', '02/02/2010')
insert into @TimeSpan values ('02/03/2010', '02/03/2010')
insert into @TimeSpan values ('02/04/2010', '02/05/2010')
insert into @TimeSpan values ('02/05/2010', '02/06/2010')
insert into @TimeSpan values ('02/07/2010', '02/09/2010')
insert into @TimeSpan values ('02/08/2010', '02/08/2010')
insert into @TimeSpan values ('02/08/2010', '02/10/2010')
insert into @TimeSpan values ('02/14/2010', '02/16/2010')

-- for this set of data, the output string would be 111111111000111

If you have a string of 1s and 0s, each element is more than a bit. :-) — corsiKa, Apr 15 '11 at 17:23
@JNK - this actually came up at work and @Martin - I solved it without a recursive CTE. Like how I did that with one sentence? :) — Milimetric, Apr 15 '11 at 17:23
@milimetric you're asking when you already know the answer? Like, a trivia contest or something? -1 :-( — corsiKa, Apr 15 '11 at 17:25
@Martin - you can definitely create your own tally table if you need it — Milimetric, Apr 15 '11 at 17:27
@glowcoder - yeah, this is just for fun, didn't mean to imply otherwise. I hoped the "puzzle" in the title would indicate that. — Milimetric, Apr 15 '11 at 17:27
I'm looking at yours right now and checking out performance. I'll mark both solutions up because they're correct, but I'll accept the one with best performance. I'll post my solution as well. It's similar to yours, I think a little simpler :) — Milimetric, Apr 15 '11 at 18:37

Martin Smith · Accepted Answer · 2011-04-15T19:30:31.807

7

DECLARE @Result VARCHAR(MAX), @start DATETIME

SELECT @start= MIN(start) ,
       @Result =REPLICATE('0',1+DATEDIFF(DAY,MIN(start),MAX(finish)))
FROM @TimeSpan

SELECT @Result = STUFF(@Result,
                       DATEDIFF(DAY,@start,start)+1,
                       DATEDIFF(DAY,start,finish)+1,
                       REPLICATE('1',1+DATEDIFF(DAY,start,finish)))
FROM @TimeSpan 

SELECT @Result

edited Apr 15 '11 at 19:30

answered Apr 15 '11 at 18:14

Martin Smith

438,706
87
741
845

@Milimetric - Not particularly surprising to me. A permanent tally table will beat the cross joined CTE one especially when you start joining on it. Being a "puzzle" I wasn't worried about performance. Updated with a much simpler version anyway. – Martin Smith Apr 15 '11 at 19:04
Dude, Awesome! This is definitely the way to go. – Milimetric Apr 15 '11 at 19:07
3

In case I didn't emphasize it enough already, this is a beautiful solution, great job. – Milimetric Apr 15 '11 at 19:17
Thanks. I Fixed a bug where I forgot to add 1 to the initial string length and that meant it didn't work if the last day in the range was a single day on its own. – Martin Smith Apr 15 '11 at 19:33

Abe Miessler · Answer 2 · 2011-04-15T17:55:32.387

I'm had to use a recursive CTE ;-)

DECLARE @BitString varchar(100);
Declare @minStart datetime
DECLARE @MaxEnd datetime
declare @RangeDates table
(
    start datetime
    ,finish datetime
)

-- this is a good data set, with overlapping and non-overlapping time spans
insert into @RangeDates values ('02/02/2010', '02/02/2010')
insert into @RangeDates values ('02/03/2010', '02/03/2010')
insert into @RangeDates values ('02/04/2010', '02/05/2010')
insert into @RangeDates values ('02/05/2010', '02/06/2010')
insert into @RangeDates values ('02/07/2010', '02/09/2010')
insert into @RangeDates values ('02/08/2010', '02/08/2010')
insert into @RangeDates values ('02/08/2010', '02/10/2010')
insert into @RangeDates values ('02/14/2010', '02/16/2010')

SELECT @minStart = MIN(start) FROM @RangeDates
SELECT @MaxEnd = MAX(finish) FROM @RangeDates

;WITH Dates AS (

        SELECT myDate = CONVERT(DateTime, @minStart), 
        CASE
            WHEN exists (SELECT * FROM @RangeDates where @minStart between start and finish) then '1'
            else '0'
        END as myBit
        UNION ALL
        SELECT myDate = DATEADD(DAY,1,myDate),
        CASE
            WHEN exists (SELECT * FROM @RangeDates where myDate between start and finish) then '1'
            else '0'
        END
        FROM Dates
        where myDate <= @MaxEnd
)

SELECT @BitString = COALESCE(@BitString,'') + myBit FROM Dates
SELECT @BitString

Cool, that's a solution so +1. But I'll hold out to see if anybody does it without so many sub-queries. — Milimetric, Apr 15 '11 at 17:57

score 1 · Answer 3 · answered Apr 15 '11 at 18:45

Ok, so here's my solution. A little faster than the other tally table solution, but not great. Also, it's limited by the convert to numeric to only allow smaller min - max date ranges. It's weird that recursive CTEs are faster than tally tables. Do the tally tables scale better?

declare @Tally table
(
    N int identity(1,1),
    T bit
)

 insert into @Tally
 select TOP 11000 0 as T
   from master.dbo.SysColumns sc1, master.dbo.SysColumns sc2


declare @begin datetime = (select MIN(start) from @TimeSpan);
declare @end datetime = (select MAX(finish) from @TimeSpan);

with strings as
(
 select S.*
        ,
        '1'+
        REPLICATE('0', DATEDIFF(DAY, @begin, DATEADD(DAY,N-1,S.start)))+
        '1'+
        REPLICATE('0', DATEDIFF(DAY, DATEADD(DAY,N-1,S.start), @end)) task

   from @TimeSpan S
            inner join
        @Tally T                    ON DateAdd(DAY,T.N-1,S.start) <= S.finish
)

 select SUM(DISTINCT convert(numeric(38,0),task)) 
        - COUNT(DISTINCT task)*(convert(numeric(38,0), '1' + REPLICATE('0',DATEDIFF(d,@begin,@end)+1)))
   from strings

RE: Tally tables try adding a primary key. See this answer for some performance comparisons. http://stackoverflow.com/questions/10819/sql-auxiliary-table-of-numbers/2663232#2663232 I have changed my answer to not require either now. — Martin Smith, Apr 15 '11 at 18:53

Interesting SQL puzzle

3 Answers3