10

let's say

You have a stored procedure that accepts arrays of datetimes, which are loaded into a temp table, and used to filter on a datetime column in a table.

  • There can be any number of values inserted as begin and end dates.
  • Date ranges may overlap sometimes, but it's not a condition that I'd count on regularly.
  • It's also possible for dates with times to be supplied.

What's the most efficient way to write a query to perform the filtering?

setup

USE StackOverflow2013;

CREATE TABLE
    #d
(
    dfrom datetime,
    dto datetime,
    PRIMARY KEY (dfrom, dto)
)
INSERT
    #d
(
    dfrom,
    dto
)
SELECT
    dfrom = '2013-11-20',
    dto =   '2013-12-05'
UNION ALL
SELECT
    dfrom = '2013-11-27',
    dto =   '2013-12-12'; 

CREATE INDEX
    p
ON dbo.Posts
    (CreationDate)
WITH
    (SORT_IN_TEMPDB = ON, DATA_COMPRESSION = PAGE);

query

The best I've been able to get is using EXISTS like so:

SELECT
    c = COUNT_BIG(*)
FROM dbo.Posts AS p
WHERE EXISTS
(
    SELECT
        1/0
    FROM #d AS d
    WHERE p.CreationDate BETWEEN d.dfrom
                             AND d.dto
);

Which results in a rather sad-looking execution plan:

NUTS

Nested Loops is the only join operator available, since we don't have an equality predicate.

What I’m looking for is alternative syntax that produces a different type of join.

Thanks!

0

7 Answers 7

9

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;

Join plan

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;

Merged intervals

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:

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)
    )

Indexed view

-- 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 start periods

-- 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)
    );

Extra rows at end

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.

0
4

If you have a small enough number of dates you could a materialize a sorted list of all valid dates, eg

CREATE TABLE #d
(
    d datetime primary key
)

And then get a merge join. Or go the other direction, eg

SELECT COUNT_BIG(distinct p.id)
FROM #D d
CROSS APPLY (select p.Id 
       from dbo.Posts AS p
       where p.CreateDate >= d.fromDate
         and p.CreateDate < d.toDate) p;

And you can just COUNT_BIG(*) if you pre-process #D to merge overlapping ranges.

1
  • 3
    Thanks, but the dates are allowed to have times as well, so this wouldn’t work cleanly. Jul 11 at 0:56
4

Using Dynamic SQL to generate a series of UNION statements seems to eliminate the Nested Loops and results in a Hash Match instead:

DECLARE @DynamicSQL NVARCHAR(MAX) = N'';

SELECT @DynamicSQL = 
    CONCAT
    (
        '
        SELECT
            c = COUNT_BIG(*)
        FROM (
        ',
            STRING_AGG
            (
                CONCAT
                (
                    '
                    SELECT p.Id
                    FROM dbo.Posts AS p
                    WHERE p.CreationDate BETWEEN ''', dfrom, ''' AND ''', dto, ''''
                ),
                CONCAT(CHAR(13), CHAR(10), CHAR(13), CHAR(10), 'UNION', CHAR(13), CHAR(10))
            ),
        '
        ) AS PostIds
        '
    )
FROM #d

--PRINT @DynamicSQL;
EXEC sp_ExecuteSQL @DynamicSQL;

Actual Execution Plan

Seems to run pretty fast on my end. Of course this could result in a long list of UNION clauses, depending on how many rows are in the #d temp table. YMMV.

1
  • It's clever, but I can't use it in the larger query this would be part of. Jul 11 at 10:51
3

What I would really like is to be able to get a plan like

enter image description here

Where SQL Server uses its built in merge interval operator to combine overlapping ranges.

I don't think this is currently possible though to get this driven by a table in this case.

My attempt to manually simulate this is below

WITH T1 AS
(
SELECT *, 
        IsIntervalStart = CASE WHEN dfrom <= MAX(dto) OVER (ORDER BY dfrom, dto ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) THEN 0 ELSE 1 END, 
        IsLastRow = CASE WHEN LEAD(dfrom) OVER (ORDER BY dfrom, dto) IS NULL THEN 1 ELSE 0 END,
        MaxDtoSoFar = MAX(dto) OVER (ORDER BY dfrom, dto ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING)
FROM #d
)
, T2
     AS (SELECT dfrom,
                dto = CASE
                        WHEN IsLastRow = 1 THEN IIF(dto > MaxDtoSoFar, dto, ISNULL(MaxDtoSoFar, dto))
                        ELSE LEAD(CASE WHEN IsLastRow = 1 AND IsIntervalStart = 0 THEN IIF(dto > MaxDtoSoFar, dto, ISNULL(MaxDtoSoFar, dto)) ELSE MaxDtoSoFar END, 1) OVER (ORDER BY dfrom, dto) END,
                IsIntervalStart
         FROM   T1
         WHERE  1 IN ( IsIntervalStart, IsLastRow ))
,Mergedintervals AS
(
SELECT *
FROM T2
WHERE IsIntervalStart = 1
)
SELECT Rows = COUNT_BIG(*)
FROM Mergedintervals
JOIN dbo.Posts AS p ON p.CreationDate  BETWEEN dfrom AND dto

If I got the overlapping range logic correct (which has taken a few stabs at it so far but hopefully is now correct) then this should collapse down the distinct ranges efficiently and then seek exactly the needed rows for those ranges from Posts.

enter image description here

  • Follow the rows in order of dfrom, dto (which conveniently is the order of the PK) and keep track of largest dto value seen in preceding rows (MaxDtoSoFar).
  • If the dfrom in a row is <= MaxDtoSoFar then we are continuing an existing interval and set IsIntervalStart to 0 otherwise we are starting a new interval and set that to 1.
  • Finally select all rows where IsIntervalStart = 1 and fill in the relevant MaxDtoSoFar value.
  • For this purpose we need to be careful not to remove the final row too early as we will need to get the values from it for the end date of the final interval.
  • And we need to also be careful about the case that the last row itself is an interval start - in which case the preceding interval should only be looking at MaxDtoSoFar and not GREATEST(dto, MaxDtoSoFar).

NB: The above method does do the interval merging with a single ordered clustered index scan and no sort operations but does have a wide execution plan with multiple of each of Segment/Sequence Project/Window Spool/ Stream Aggregate operators.

Paul White provided an alternative method in the comments that can use batch mode Window Aggregates exclusively and has a much more streamlined plan (as well as likely being simpler SQL)

enter image description here

0
2

First I'd like to apologize for the odd query plan in my answer. My computer was recently hacked and I've been unable to remove the SSMS plugin.

You can greatly improve performance by splitting each valid date into its own row. The trick is to also carry along time information to exclude data at the endpoints if necessary. For example, consider the date range '20230709 18:00:00' to '20230711 04:00:00'. For that range, you would include rows with a date of 20230709 with a time >= 18:00:00, all rows for 20230710, and rows with a date of 20230711 with a time <= 04:00:00.

Below is your same sample data along with an extra temp table that summarizes the date ranges in the manner I described earlier:

DROP TABLE IF EXISTS #d;
CREATE TABLE #d
(
    dfrom datetime,
    dto datetime,
    PRIMARY KEY (dfrom, dto)
);

INSERT #d (dfrom, dto)
SELECT
    dfrom = '2013-11-20',
    dto =   '2013-12-05'
UNION ALL
SELECT
    dfrom = '2013-11-27',
    dto =   '2013-12-12'; 

DROP TABLE IF EXISTS #d_expanded;
CREATE TABLE
    #d_expanded
(
    base_date DATE,
    IsFullDate BIT,
    dfrom datetime,
    dto datetime,
    PRIMARY KEY (base_date)
);

INSERT INTO #d_expanded (base_date, IsFullDate, dfrom, dto)
SELECT base_date, CASE WHEN MIN(dfrom) <= base_date AND MAX(dto) >= DATEADD(DAY, 1, base_date) THEN 1 ELSE 0 END , MIN(dfrom), MAX(dto)
FROM (
    SELECT ca.base_date, dfrom, dto
    FROM #d d
    CROSS APPLY (
        SELECT TOP (1 + DATEDIFF_BIG(DAY, d.dfrom, d.dto))
        DATEADD(DAY, ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) - 1, CAST(d.dfrom AS DATE))
        FROM master..spt_values t1
        CROSS JOIN master..spt_values t2
    ) ca (base_date)
) q
GROUP BY base_date;

This query executes in 64 ms on my machine:

SELECT COUNT_BIG(*)
FROM #d_expanded d
INNER JOIN dbo.Posts AS p ON p.CreationDate >= d.base_date AND p.CreationDate < DATEADD(DAY, 1, d.base_date)
WHERE (d.IsFullDate = 1 OR p.CreationDate BETWEEN d.dfrom AND d.dto);

For a relative speedup of around 300X. Here is the query plan:

enter image description here

1
  • Maybe put the query plan on Paste The Plan to workaround that interesting background. 😉
    – J.D.
    Jul 12 at 12:32
0

There is an interesting concept called a static relational interval tree, Itzik has written some stuff on it but I think there was some problem on his blog post with the example code so I didn’t ever manage to get it working, anyway I found an example link & there are more if you use these terms for a web search

https://lucient.com/blog/a-static-relational-interval-tree/#

1
-2

Seems your objective is to find the number of matching posts, that are in the given date ranges. Given you don't have more information on data distribution and quantity structure, it is hard to give proper recommendations.

How about the obvious, assuming that there's primary key "id" in Posts:

SELECT count(distinct p.id) 
  FROM dbo.Posts AS p, 
       #d AS d
 WHERE p.CreationDate BETWEEN d.dfrom
                          AND d.dto

and creating an index on Posts(CreationDate, id).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.