Thinking outside the box

Patron Saint of Lost Yaks
posts - 203, comments - 734, trackbacks - 4

My Links

Advertisement

News

Archives

Post Categories

Lightning fast collapsed date ranges and missing date ranges

The last two days I have been involved in a rather interesting discussion.

The original poster wanted a fast way to get missing date ranges in a series of date pairs.
Naturally I posted the link to the Script Library topic http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=88422
Traditional T-SQL proved to be very inefficient. Even when using the CTE approch which proved to be second fastest and still 100 to 1,600 times slower!

I started out with creating 1,000 date pairs with following code


-- Prepare sample data
CREATE TABLE #ProcessCellAllocation
              (
                     AllocationID INT IDENTITY(1, 1) NOT NULL,
                     ProcessCell VARCHAR(50) NOT NULL,
                     DateFrom DATETIME NOT NULL,
                     DateTo DATETIME,
                     Seq INT
              )

INSERT        #ProcessCellAllocation
                (
                     ProcessCell,
                     DateFrom
                )
SELECT        TOP 10000
              CHAR(65 + ABS(CHECKSUM(NEWID())) % 26),
              25000 + ABS(CHECKSUM(NEWID())) % 25000
FROM          syscolumns AS c1
CROSS JOIN    syscolumns AS c2

UPDATE #ProcessCellAllocation
SET    DateTo = DATEADD(DAY, ABS(CHECKSUM(NEWID())) % 30, DateFrom)

CREATE CLUSTERED INDEX IX_DateFrom ON #ProcessCellAllocation (ProcessCell, DateFrom, DateTo) WITH FILLFACTOR = 95


The various techniques used to produce the wanted results were very inefficient.
Ultimately I come up with this idea, which produced both collapsed date ranges and missing date ranges.

I started out with clearing a preexisting Seq columns. I can clear all records or only a certain range of ProcessCells.


UPDATE #ProcessCellAllocation
SET    Seq = NULL
WHERE  ProcessCell BETWEEN 'A' AND 'F'


I then initialize some variables to speed up counting

DECLARE     @Seq INT,
           
@ProcessCell VARCHAR(50),
@DateFrom DATETIME,
@DateTo DATETIME
 
SELECT      TOP 1
            @Seq = 0,
            @ProcessCell = ProcessCell
            @DateFrom = DateFrom,
            @DateTo = DateTo
FROM        #ProcessCellAllocation
ORDER BY    ProcessCell,
  
                        DateFrom

This is only for initializing the documented trick I use, the Clustered Index Update.
The code used for the actual update looks like this

UPDATE #ProcessCellAllocation
SET    @Seq = CASE
                 WHEN DateFrom > @DateTo THEN @Seq + 1
                 WHEN ProcessCell > @ProcessCell THEN @Seq + 1
                 ELSE @Seq
              END,
       @DateFrom = CASE
                      WHEN DateTo > @DateTo THEN DateFrom
                      WHEN ProcessCell > @ProcessCell THEN DateFrom
                      ELSE @DateFrom
                   END,
       @DateTo = CASE
                    WHEN DateTo > @DateTo THEN DateTo
                    WHEN ProcessCell > @ProcessCell THEN DateTo
                    ELSE @DateTo
                 END,
       Seq = @Seq,
       @ProcessCell = ProcessCell

Now all work is done, and we can either show the collapgsed date ranges with this

-- Get the collapsed date ranges
SELECT      ProcessCell,
            MIN(DateFrom) AS DateFrom,
            MAX(DateTo) AS DateTo
FROM        #ProcessCellAllocation
GROUP BY    ProcessCell,
            Seq
ORDER BY    Seq


Or we can get the missing date ranges with this


-- Get the missing date ranges
SELECT     a.ProcessCell,
           a.DateFrom,
           b.DateTo
FROM       (
               SELECT   ProcessCell,
                        Seq,
                        MAX(DateTo) AS DateFrom
               FROM     #ProcessCellAllocation
               GROUP BY ProcessCell,
                        Seq
           ) AS a
INNER JOIN (
                  SELECT      ProcessCell,
                              Seq,
                              MIN(DateFrom) AS DateTo
                  FROM        #ProcessCellAllocation
                  GROUP BY    ProcessCell,
                              Seq
            ) AS b ON b.ProcessCell = a.ProcessCell
WHERE       a.Seq = b.Seq - 1
ORDER BY    a.Seq

This technique is very fast!

For 1,000 date pairs the algorithm runs in 80 ms.
For 10,000 date pairs the algorithm runs in 360 ms.
For 100,000 date pairs the algorithm runs in 900 ms.
For 1,000,000 date pairs the algorithm runs in 2250 ms.

Print | posted on Tuesday, May 13, 2008 4:16 PM | Filed Under [ Optimization SQL Server 2008 Algorithms SQL Server 2005 SQL Server 2000 ]

Feedback

Gravatar

# re: Lightning fast collapsed date ranges and missing date ranges

Nicely done, Peter... but you really need to change your tab size or convert them to spaces ;-)
8/12/2008 4:40 AM | --Jeff Moden
Gravatar

# re: Lightning fast collapsed date ranges and missing date ranges

Is it possible to do the same to merge data ranges when they are contiguous (rather than overlapping?).

For example,

Seq No. Group From To
1 1 1/1/1950 12/31/1970
2 1 1/1/1971 12/31/1990
3 1 1/1/1991 12/31/2010
4 2 1/1/2005 12/31/2005
5 2 1/1/2007 12/31/2007

Output:

Group From To
1 1/1/1950 12/31/2010 <-- merged first 3 rows
2 1/1/2005 12/31/2005 <-- cannot merge
2 1/1/2007 12/31/2007 <-- cannot merge

Thanks

8/8/2009 3:15 AM | NewSQL
Gravatar

# re: Lightning fast collapsed date ranges and missing date ranges

Sure. Change ">" to ">=".
8/8/2009 8:12 AM | Peso
Gravatar

# re: Lightning fast collapsed date ranges and missing date ranges

Any thoughts on how to get missing date ranges in access.mdb SQL
11/2/2009 5:27 AM | Ben
Gravatar

# re: Lightning fast collapsed date ranges and missing date ranges

Thanks Peso!!!
12/23/2010 12:35 AM | Langston
Gravatar

# re: Lightning fast collapsed date ranges and missing date ranges

Wow. Just Wow.

That, my friend, has to be one of the slickest SQL tricks I've seen in a LONG time.

Took a 60+ minute query down to <30seconds.

That's definitely one for the ol' toolbox!

Thanks!
3/2/2011 10:37 PM | Darin
Gravatar

# re: Lightning fast collapsed date ranges and missing date ranges

I'm fairly new to SQL. I've solved this problem before using object oriented programming. I don't completely understand your method here. You didn't explain what some of these columns are or what they mean like AllocationID, ProcessCell, and Seq. Given raw data like:

DECLARE @TimeFrames AS TABLE
(start_date DATETIME,end_date DATETIME)

INSERT @TimeFrames SELECT TOP 10 DateFrom as start_date,DateTo as end_date FROM #ProcessCellAllocation

SELECT * FROM @TimeFrames t

------------
Results:
------------

start_date end_date
1968-06-23 00:00:00.000 1968-07-10 00:00:00.000
1968-08-14 00:00:00.000 1968-08-20 00:00:00.000
1968-10-08 00:00:00.000 1968-11-02 00:00:00.000
1968-12-15 00:00:00.000 1968-12-21 00:00:00.000
1969-06-29 00:00:00.000 1969-07-19 00:00:00.000
1969-09-11 00:00:00.000 1969-09-14 00:00:00.000
1969-11-21 00:00:00.000 1969-12-08 00:00:00.000
1969-12-03 00:00:00.000 1969-12-24 00:00:00.000
1970-01-26 00:00:00.000 1970-02-03 00:00:00.000
1970-03-12 00:00:00.000 1970-03-30 00:00:00.000

How would one collapse this?

Thanks,
Wes
5/28/2011 6:25 AM | Wes
Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET