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.
posted @ Tuesday, May 13, 2008 4:16 PM