Join
You may find a join gives adequate performance, despite still using nested loops. This is a variation on David Browne's updated answer:
SELECT
NumRows = COUNT_BIG(DISTINCT P.Id)
FROM #d AS D
JOIN dbo.Posts AS P
ON P.CreationDate BETWEEN D.dfrom AND D.dto;
That runs in around 150ms for me.
Remove overlaps and join
If you have significant overlapping rows, it may be worth reducing them to distinct, non-overlapping ranges, as outlined in Martin Smith's answer. My implementation of a similar idea is:
WITH
Intervals AS
(
SELECT
IntervalStart =
ISNULL
(
LAG(Q1.NextStart) OVER (ORDER BY Q1.ThisFrom),
Q1.FirstFrom
),
IntervalEnd =
IIF
(
Q1.NextStart IS NOT NULL,
Q1.ThisEnd,
Q1.LastEnd
)
FROM
(
SELECT
ThisFrom = D.dfrom,
ThisEnd = D.dto,
-- Remember the start of the next row because that row
-- may get filtered out by the outer WHERE clase if it
-- is not also the end of an interval.
NextStart = LEAD(D.dfrom) OVER (
ORDER BY D.dfrom, D.dto),
-- Start point of the first interval
FirstFrom = MIN(D.dfrom) OVER (
ORDER BY D.dfrom, D.dto
ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW),
-- End point of the last interval
LastEnd = MAX(D.dto) OVER (
ORDER BY D.dfrom, D.dto
ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
FROM #d AS D
WHERE
-- Valid intervals only
D.dto >= D.dfrom
) AS Q1
WHERE
-- Interval ends only
Q1.NextStart > Q1.ThisEnd
OR Q1.NextStart IS NULL
)
SELECT COUNT_BIG(*)
FROM dbo.Posts AS P
JOIN Intervals AS N
ON P.CreationDate BETWEEN N.IntervalStart AND N.IntervalEnd;
That runs in about 40ms for me.
Dynamic seek with no join
Another approach is to generate literal ranges dynamically:
DECLARE @SQL nvarchar(max) =
N'
SELECT Rows = COUNT_BIG(*)
FROM dbo.Posts AS P
WHERE 0 = 1
';
SELECT @SQL +=
STRING_AGG
(
CONCAT
(
CONVERT(nvarchar(max), SPACE(0)),
N'OR P.CreationDate BETWEEN ',
N'CONVERT(datetime, ',
NCHAR(39),
CONVERT(nchar(23), D.dfrom, 121),
NCHAR(39),
N', 121)',
N' AND CONVERT(datetime, ',
NCHAR(39),
CONVERT(nchar(23), D.dto, 121),
NCHAR(39),
N', 121)',
NCHAR(13), NCHAR(10)
),
N''
)
FROM #d AS D;
SET @SQL += N'OPTION (RECOMPILE);' -- Plan reuse is unlikely
EXECUTE (@SQL);
With the sample data, that produces:
SELECT Rows = COUNT_BIG(*)
FROM dbo.Posts AS P
WHERE 0 = 1
OR P.CreationDate BETWEEN CONVERT(datetime, '2013-11-20 00:00:00.000', 121)
AND CONVERT(datetime, '2013-12-05 00:00:00.000', 121)
OR P.CreationDate BETWEEN CONVERT(datetime, '2013-11-27 00:00:00.000', 121)
AND CONVERT(datetime, '2013-12-12 00:00:00.000', 121)
OPTION (RECOMPILE);
Which SQL Server simplifies to a single range seek:
That runs in about 35ms for me.
In general, the optimizer will simplify the ranges as much as possible (much like a Merge Interval would do). There doesn't appear to be a limit on the number of separate range seeks in a single Index Seek operator. I got bored after 1440 seeks.
Indexed view
Rather than count rows over and over again, it may be helpful to store and maintain bucketized counts in an indexed view. The following implementation uses hour granularity:
CREATE OR ALTER VIEW dbo.PostsTimeBucket
WITH SCHEMABINDING
AS
SELECT
HourBucket =
DATEADD(HOUR,
DATEDIFF(HOUR,
CONVERT(datetime, '20000101', 112),
P.CreationDate),
CONVERT(datetime, '20000101', 112)),
NumRows = COUNT_BIG(*)
FROM dbo.Posts AS P
GROUP BY
DATEADD(HOUR,
DATEDIFF(HOUR,
CONVERT(datetime, '20000101', 112),
P.CreationDate),
CONVERT(datetime, '20000101', 112));
GO
CREATE UNIQUE CLUSTERED INDEX [CUQ dbo.PostsTimeBucket HourBucket]
ON dbo.PostsTimeBucket (HourBucket);
The view takes around 2s to create on my laptop. At hour granularity, the indexed view holds 47,469 rows for my copy of the StackOverflow2013 database's Posts table with 17,142,169 rows.
The majority of the work can be done from the view. Only part-hour periods at the start and end of any range not covered by any other range needs to be processed separately. For example:
-- Helper inline function
CREATE OR ALTER FUNCTION dbo.RoundToHour (@d datetime)
RETURNS table
AS
RETURN
SELECT
HourBucket =
DATEADD(HOUR,
DATEDIFF(HOUR,
CONVERT(datetime, '20000101', 112), @d),
CONVERT(datetime, '20000101', 112));
-- Whole hours covered by any range in the table
SELECT
SUM(PTB.NumRows)
FROM dbo.PostsTimeBucket AS PTB
WITH (NOEXPAND)
WHERE
PTB.HourBucket >= (SELECT MIN(D.dfrom) FROM #d AS D)
AND PTB.HourBucket <= (SELECT MAX(D.dto) FROM #d AS D)
AND EXISTS
(
SELECT *
FROM #d AS D
WHERE
D.dfrom <= PTB.HourBucket
AND D.dto >= DATEADD(HOUR, 1, PTB.HourBucket)
)
-- Extra rows at start before hour boundary
SELECT
COUNT_BIG(DISTINCT P.Id)
FROM #d AS D
CROSS APPLY dbo.RoundToHour(D.dfrom) AS HF
JOIN dbo.Posts AS P
ON P.CreationDate >= D.dfrom
AND P.CreationDate < DATEADD(HOUR, 1, HF.HourBucket)
WHERE
D.dfrom <> HF.HourBucket
AND NOT EXISTS
(
-- Not covered by any hour-long period
SELECT *
FROM #d AS D2
WHERE
D2.dfrom <= HF.HourBucket
AND D2.dto > DATEADD(HOUR, 1, HF.HourBucket)
);
-- Extra rows at end
SELECT
COUNT_BIG(DISTINCT P.Id)
FROM #d AS D
CROSS APPLY dbo.RoundToHour(D.dto) AS HF
JOIN dbo.Posts AS P
ON P.CreationDate >= HF.HourBucket
AND P.CreationDate < D.dto
WHERE
D.dto <> HF.HourBucket
AND NOT EXISTS
(
-- Not covered by any hour-long period
SELECT *
FROM #d AS D2
WHERE
D2.dfrom <= HF.HourBucket
AND D2.dto > DATEADD(HOUR, 1, HF.HourBucket)
);
The three queries above complete in less than 1 ms overall. There are no part-hour periods in the sample data. Performance will decrease somewhat with more and larger part periods, or if a less precise indexed view granularity is used.
