Melhore o desempenho de vários predicados de intervalo de datas

Juntar

Você pode descobrir que uma junção oferece desempenho adequado, apesar de ainda usar loops aninhados. Esta é uma variação da resposta atualizada de David Browne :

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;

Isso dura cerca de 150 ms para mim.

Remova sobreposições e junte-se

Se você tiver linhas sobrepostas significativas, pode valer a pena reduzi-las a intervalos distintos e não sobrepostos, conforme descrito na resposta de Martin Smith . Minha implementação de uma ideia semelhante é:

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;

Isso dura cerca de 40ms para mim.

Busca dinâmica sem junção

Outra abordagem é gerar intervalos literais dinamicamente:

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

Com os dados de amostra, isso produz:

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

Qual SQL Server simplifica para uma única busca de intervalo:

Isso dura cerca de 35ms para mim.

Em geral, o otimizador simplificará os intervalos tanto quanto possível (assim como faria um Merge Interval ). Não parece haver um limite para o número de buscas de intervalo separadas em um único operador de busca de índice . Fiquei entediado depois de 1440 buscas .

Visualização indexada

Em vez de contar linhas repetidamente, pode ser útil armazenar e manter contagens agrupadas em uma visualização indexada. A implementação a seguir usa granularidade horária:

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.

Se você tiver um número pequeno de datas, poderá materializar uma lista ordenada de todas as datas válidas, por exemplo

CREATE TABLE #d
(
    d datetime primary key
)

E então obtenha uma junção de mesclagem. Ou vá na outra direção, por exemplo

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;

E você pode apenas COUNT_BIG(*) se pré-processar #D para mesclar intervalos sobrepostos.

Usar SQL Dinâmico para gerar uma série de UNIONinstruções parece eliminar o Nested Loopse resulta em Hash Match:

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;

Plano de Execução Real

Parece correr muito rápido do meu lado. É claro que isso poderia resultar em uma longa lista de UNIONcláusulas, dependendo de quantas linhas existem na #dtabela temporária. YMMV.

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

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.

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

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.

Você pode melhorar bastante o desempenho dividindo cada data válida em sua própria linha. O truque é também transportar informações de tempo para excluir dados nos terminais, se necessário. Por exemplo, considere o intervalo de datas '20230709 18:00:00' a '20230711 04:00:00'. Para esse intervalo, você incluiria linhas com data de 20230709 com hora >= 18:00:00, todas as linhas para 20230710 e linhas com data de 20230711 com hora <= 04:00:00.

Abaixo estão os mesmos dados de amostra, juntamente com uma tabela temporária extra que resume os intervalos de datas da maneira que descrevi anteriormente:

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;

Esta consulta é executada em 64 ms na minha máquina:

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

Para uma aceleração relativa de cerca de 300X. Aqui está o plano de consulta:

Existe um conceito interessante chamado árvore de intervalo relacional estático, Itzik escreveu algumas coisas sobre ele, mas acho que houve algum problema em sua postagem no blog com o código de exemplo, então nunca consegui fazê-lo funcionar, de qualquer forma, encontrei um link de exemplo e há mais se você usar esses termos para uma pesquisa na web

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

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