Como encontrar recursivamente lacunas onde passaram 90 dias, entre as linhas

Enquanto leio a pergunta, o algoritmo recursivo básico necessário é:

1. Retorna a linha com a data mais antiga no conjunto
2. Defina essa data como "atual"
3. Encontre a linha com a data mais antiga mais de 90 dias após a data atual
4. Repita a partir do passo 2 até que não sejam encontradas mais linhas

Isso é relativamente fácil de implementar com uma expressão de tabela comum recursiva.

For example, using the following sample data (based on the question):

DECLARE @T AS table (TheDate datetime PRIMARY KEY);

INSERT @T (TheDate)
VALUES
    ('2014-01-01 11:00'),
    ('2014-01-03 10:00'),
    ('2014-01-04 09:30'),
    ('2014-04-01 10:00'),
    ('2014-05-01 11:00'),
    ('2014-07-01 09:00'),
    ('2014-07-31 08:00');

The recursive code is:

WITH CTE AS
(
    -- Anchor:
    -- Start with the earliest date in the table
    SELECT TOP (1)
        T.TheDate
    FROM @T AS T
    ORDER BY
        T.TheDate

    UNION ALL

    -- Recursive part   
    SELECT
        SQ1.TheDate
    FROM 
    (
        -- Recursively find the earliest date that is 
        -- more than 90 days after the "current" date
        -- and set the new date as "current".
        -- ROW_NUMBER + rn = 1 is a trick to get
        -- TOP in the recursive part of the CTE
        SELECT
            T.TheDate,
            rn = ROW_NUMBER() OVER (
                ORDER BY T.TheDate)
        FROM CTE
        JOIN @T AS T
            ON T.TheDate > DATEADD(DAY, 90, CTE.TheDate)
    ) AS SQ1
    WHERE
        SQ1.rn = 1
)
SELECT 
    CTE.TheDate 
FROM CTE
OPTION (MAXRECURSION 0);

The results are:

╔═════════════════════════╗
║         TheDate         ║
╠═════════════════════════╣
║ 2014-01-01 11:00:00.000 ║
║ 2014-05-01 11:00:00.000 ║
║ 2014-07-31 08:00:00.000 ║
╚═════════════════════════╝

With an index having TheDate as a leading key, the execution plan is very efficient:

You could choose to wrap this in a function and execute it directly against the view mentioned in the question, but my instincts are against it. Usually, performance is better when you select rows from a view into a temporary table, provide the appropriate index on the temporary table, then apply the logic above. The details depend on the details of the view, but this is my general experience.

For completeness (and prompted by ypercube's answer) I should mention that my other go-to solution for this type of problem (until T-SQL gets proper ordered set functions) is a SQLCLR cursor (see my answer here for an example of the technique). This performs much better than a T-SQL cursor, and is convenient for those with skills in .NET languages and the ability to run SQLCLR in their production environment. It may not offer much in this scenario over the recursive solution because the majority of the cost is the sort, but it is worth mentioning.

Since this is a SQL Server 2014 question I might as well add a natively compiled stored procedure version of a "cursor".

Source table with some data:

create table T 
(
  TheDate datetime primary key
);

go

insert into T(TheDate) values
('2014-01-01 11:00'),
('2014-01-03 10:00'),
('2014-01-04 09:30'),
('2014-04-01 10:00'),
('2014-05-01 11:00'),
('2014-07-01 09:00'),
('2014-07-31 08:00');

A table type that is the parameter to the stored procedure. Adjust the bucket_count appropriately.

create type TType as table
(
  ID int not null primary key nonclustered hash with (bucket_count = 16),
  TheDate datetime not null
) with (memory_optimized = on);

And a stored procedure that loops through the table valued parameter and collects the rows in @R.

create procedure dbo.GetDates
  @T dbo.TType readonly
with native_compilation, schemabinding, execute as owner 
as
begin atomic with (transaction isolation level = snapshot, language = N'us_english', delayed_durability = on)

  declare @R dbo.TType;
  declare @ID int = 0;
  declare @RowsLeft bit = 1;  
  declare @CurDate datetime = '1901-01-01';
  declare @LastDate datetime = '1901-01-01';

  while @RowsLeft = 1
  begin
    set @ID += 1;

    select @CurDate = T.TheDate
    from @T as T
    where T.ID = @ID

    if @@rowcount = 1
    begin
      if datediff(day, @LastDate, @CurDate) > 90
      begin
        insert into @R(ID, TheDate) values(@ID, @CurDate);
        set @LastDate = @CurDate;
      end;
    end
    else
    begin
      set @RowsLeft = 0;
    end

  end;

  select R.TheDate
  from @R as R;
end

Code to fill a memory optimized table variable that is used as a parameter to the natively compiled stored procedure and call the procedure.

declare @T dbo.TType;

insert into @T(ID, TheDate)
select row_number() over(order by T.TheDate),
       T.TheDate
from T;

exec dbo.GetDates @T;

Result:

TheDate
-----------------------
2014-07-31 08:00:00.000
2014-01-01 11:00:00.000
2014-05-01 11:00:00.000

Update:

If you for some reason don't need to visit every row in the table you can do the equivalent of the "jump to next date" version that is implemented in the recursive CTE by Paul White.

O tipo de dados não precisa da coluna ID e você não deve usar um índice de hash.

create type TType as table
(
  TheDate datetime not null primary key nonclustered
) with (memory_optimized = on);

E o procedimento armazenado usa a select top(1) ..para localizar o próximo valor.

create procedure dbo.GetDates
  @T dbo.TType readonly
with native_compilation, schemabinding, execute as owner 
as
begin atomic with (transaction isolation level = snapshot, language = N'us_english', delayed_durability = on)

  declare @R dbo.TType;
  declare @RowsLeft bit = 1;  
  declare @CurDate datetime = '1901-01-01';

  while @RowsLeft = 1
  begin

    select top(1) @CurDate = T.TheDate
    from @T as T
    where T.TheDate > dateadd(day, 90, @CurDate)
    order by T.TheDate;

    if @@rowcount = 1
    begin
      insert into @R(TheDate) values(@CurDate);
    end
    else
    begin
      set @RowsLeft = 0;
    end

  end;

  select R.TheDate
  from @R as R;
end

A solution that uses a cursor.
(first, some needed tables and variables):

-- a table to hold the results
DECLARE @cd TABLE
(   TheDate datetime PRIMARY KEY,
    Qualify INT NOT NULL
);

-- some variables
DECLARE
    @TheDate DATETIME,
    @diff INT,
    @Qualify     INT = 0,
    @PreviousCheckDate DATETIME = '1900-01-01 00:00:00' ;

The actual cursor:

-- declare the cursor
DECLARE c CURSOR
    LOCAL STATIC FORWARD_ONLY READ_ONLY
    FOR
    SELECT TheDate
      FROM T
      ORDER BY TheDate ;

-- using the cursor to fill the @cd table
OPEN c ;

FETCH NEXT FROM c INTO @TheDate ;

WHILE @@FETCH_STATUS = 0
BEGIN
    SET @diff = DATEDIFF(day, @PreviousCheckDate, @Thedate) ;
    SET @Qualify = CASE WHEN @diff > 90 THEN 1 ELSE 0 END ;

    INSERT @cd (TheDate, Qualify)
        SELECT @TheDate, @Qualify ;

    SET @PreviousCheckDate = 
            CASE WHEN @diff > 90 
                THEN @TheDate 
                ELSE @PreviousCheckDate END ;

    FETCH NEXT FROM c INTO @TheDate ;
END

CLOSE c;
DEALLOCATE c;

And getting the results:

-- get the results
SELECT TheDate, Qualify
    FROM @cd
    -- WHERE Qualify = 1        -- optional, to see only the qualifying rows
    ORDER BY TheDate ;

Tested at SQLFiddle

IF  EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[dbo].[vGetVisits]') AND type in (N'U'))
DROP TABLE [dbo].[vGetVisits]
GO

CREATE TABLE [dbo].[vGetVisits](
    [id] [int] NOT NULL,
    [mydate] [datetime] NOT NULL,
 CONSTRAINT [PK_vGetVisits] PRIMARY KEY CLUSTERED 
(
    [id] ASC
)
)

GO

INSERT INTO [dbo].[vGetVisits]([id], [mydate])
VALUES
    (1, '2014-01-01 11:00'),
    (2, '2014-01-03 10:00'),
    (3, '2014-01-04 09:30'),
    (4, '2014-04-01 10:00'),
    (5, '2014-05-01 11:00'),
    (6, '2014-07-01 09:00'),
    (7, '2014-07-31 08:00');
GO


-- Clean up 
IF OBJECT_ID (N'dbo.udfLastHitRecursive', N'FN') IS NOT NULL
DROP FUNCTION udfLastHitRecursive;
GO

-- Actual Function  
CREATE FUNCTION dbo.udfLastHitRecursive
( @MyDate datetime)

RETURNS TINYINT

AS
    BEGIN 
        -- Your returned value 1 or 0
        DECLARE @Returned_Value TINYINT;
        SET @Returned_Value=0;
    -- Prepare gaps table to be used.
    WITH gaps AS
    (
                        -- Select Date and MaxDiff from the original table
                        SELECT 
                        CONVERT(Date,mydate) AS [date]
                        , DATEDIFF(day,ISNULL(LAG(mydate, 1) OVER (ORDER BY mydate), mydate) , mydate) AS [MaxDiff]
                        FROM dbo.vGetVisits
    )

        SELECT @Returned_Value=
            (SELECT DISTINCT -- DISTINCT in case we have same date but different time
                    CASE WHEN
                     (
                    -- It is a first entry
                    [date]=(SELECT MIN(CONVERT(Date,mydate)) FROM dbo.vGetVisits))
                    OR 
                    /* 
                    --Gap between last qualifying date and entered is greater than 90 
                        Calculate Running sum upto and including required date 
                        and find a remainder of division by 91. 
                    */
                     ((SELECT SUM(t1.MaxDiff)  
                    FROM (SELECT [MaxDiff] FROM gaps WHERE [date]<=t2.[date] 
                    ) t1 
                    )%91 - 
                    /* 
                        ISNULL added to include first value that always returns NULL 
                        Calculate Running sum upto and NOT including required date 
                        and find a remainder of division by 91 
                    */
                    ISNULL((SELECT SUM(t1.MaxDiff)  
                    FROM (SELECT [MaxDiff] FROM gaps WHERE [date]<t2.[date] 
                    ) t1 
                    )%91, 0) -- End ISNULL
                     <0 )
                    /* End Running sum upto and including required date */
                    OR
                    -- Gap between two nearest dates is greater than 90 
                    ((SELECT SUM(t1.MaxDiff)  
                    FROM (SELECT [MaxDiff] FROM gaps WHERE [date]<=t2.[date] 
                    ) t1 
                    ) - ISNULL((SELECT SUM(t1.MaxDiff)  
                    FROM (SELECT [MaxDiff] FROM gaps WHERE [date]<t2.[date] 
                    ) t1 
                    ), 0) > 90) 
                    THEN 1
                    ELSE 0
                    END 
                    AS [Qualifying]
                    FROM gaps t2
                    WHERE [date]=CONVERT(Date,@MyDate))
        -- What is neccesary to return when entered date is not in dbo.vGetVisits?
        RETURN @Returned_Value
    END
GO

SELECT 
dbo.udfLastHitRecursive(mydate) AS [Qualifying]
, [id]
, mydate 
FROM dbo.vGetVisits
ORDER BY mydate 

Resultado

Também dê uma olhada em Como calcular o total em execução no SQL Server

atualização: veja abaixo os resultados dos testes de desempenho.

Por causa da lógica diferente usada para encontrar "intervalo de 90 dias", as soluções do ypercube e minhas, se deixadas intactas, podem retornar resultados diferentes para a solução de Paul White. Isso se deve ao uso das funções DATEDIFF e DATEADD , respectivamente.

Por exemplo:

SELECT DATEADD(DAY, 90, '2014-01-01 00:00:00.000')

retorna '2014-04-01 00:00:00.000', o que significa que '2014-04-01 01:00:00.000' está além do intervalo de 90 dias

mas

SELECT DATEDIFF(DAY, '2014-01-01 00:00:00.000', '2014-04-01 01:00:00.000')

Retorna '90', o que significa que ainda está dentro do intervalo.

Considere um exemplo de um varejista. Neste caso, vender um produto perecível com data de validade '2014-01-01' em '2014-01-01 23:59:59:999' é aceitável. Portanto, o valor DATEDIFF(DAY, ...) neste caso está OK.

Outro exemplo é um paciente esperando para ser atendido. Para alguém que chega em '2014-01-01 00:00:00:000' e sai em '2014-01-01 23:59:59:999', é 0 (zero) dias se DATEDIFF for usado, mesmo que o a espera real foi de quase 24 horas. Novamente, o paciente que chega em '2014-01-01 23:59:59' e sai em '2014-01-02 00:00:01' esperou um dia se DATEDIFF for usado.

Mas eu discordo.

Deixei as soluções DATEDIFF e até testei o desempenho delas, mas elas realmente deveriam estar em sua própria liga.

Também foi notado que para os grandes conjuntos de dados é impossível evitar valores no mesmo dia. Portanto, se tivermos 13 milhões de registros abrangendo 2 anos de dados, acabaremos tendo mais de um registro por alguns dias. Esses registros estão sendo filtrados na primeira oportunidade nas soluções DATEDIFF minhas e do ypercube. Espero que o ypercube não se importe com isso.

As soluções foram testadas na tabela a seguir

CREATE TABLE [dbo].[vGetVisits](
    [id] [int] NOT NULL,
    [mydate] [datetime] NOT NULL,
) 

com dois índices clusterizados diferentes (mydate neste caso):

CREATE CLUSTERED INDEX CI_mydate on vGetVisits(mydate) 
GO

A tabela foi preenchida da seguinte maneira

SET NOCOUNT ON
GO

INSERT INTO dbo.vGetVisits(id, mydate)
VALUES (1, '01/01/1800')
GO

DECLARE @i bigint
SET @i=2

DECLARE @MaxRows bigint
SET @MaxRows=13001

WHILE @i<@MaxRows 
BEGIN
INSERT INTO dbo.vGetVisits(id, mydate)
VALUES (@i, DATEADD(day,FLOOR(RAND()*(3)),(SELECT MAX(mydate) FROM dbo.vGetVisits)))
SET @i=@i+1
END

Para um caso de vários milhões de linhas, INSERT foi alterado de forma que entradas de 0 a 20 minutos fossem adicionadas aleatoriamente.

Todas as soluções foram cuidadosamente agrupadas no seguinte código

SET NOCOUNT ON
GO

DECLARE @StartDate DATETIME

SET @StartDate = GETDATE()

--- Code goes here

PRINT 'Total milliseconds: ' + CONVERT(varchar, DATEDIFF(ms, @StartDate, GETDATE()))

Códigos reais testados (em nenhuma ordem específica):

Solução DATEDIFF da Ypercube ( YPC, DATEDIFF )

DECLARE @cd TABLE
(   TheDate datetime PRIMARY KEY,
    Qualify INT NOT NULL
);

DECLARE
    @TheDate DATETIME,
    @Qualify     INT = 0,
    @PreviousCheckDate DATETIME = '1799-01-01 00:00:00' 


DECLARE c CURSOR
    LOCAL STATIC FORWARD_ONLY READ_ONLY
    FOR
SELECT 
   mydate
FROM 
 (SELECT
       RowNum = ROW_NUMBER() OVER(PARTITION BY cast(mydate as date) ORDER BY mydate)
       , mydate
   FROM 
       dbo.vGetVisits) Actions
WHERE
   RowNum = 1
ORDER BY 
  mydate;

OPEN c ;

FETCH NEXT FROM c INTO @TheDate ;

WHILE @@FETCH_STATUS = 0
BEGIN

    SET @Qualify = CASE WHEN DATEDIFF(day, @PreviousCheckDate, @Thedate) > 90 THEN 1 ELSE 0 END ;
    IF  @Qualify=1
    BEGIN
        INSERT @cd (TheDate, Qualify)
        SELECT @TheDate, @Qualify ;
        SET @PreviousCheckDate=@TheDate 
    END
    FETCH NEXT FROM c INTO @TheDate ;
END

CLOSE c;
DEALLOCATE c;


SELECT TheDate
    FROM @cd
    ORDER BY TheDate ;

Solução DATEADD da Ypercube ( YPC, DATEADD )

DECLARE @cd TABLE
(   TheDate datetime PRIMARY KEY,
    Qualify INT NOT NULL
);

DECLARE
    @TheDate DATETIME,
    @Next_Date DATETIME,
    @Interesting_Date DATETIME,
    @Qualify     INT = 0

DECLARE c CURSOR
    LOCAL STATIC FORWARD_ONLY READ_ONLY
    FOR
  SELECT 
  [mydate]
  FROM [test].[dbo].[vGetVisits]
  ORDER BY mydate
  ;

OPEN c ;

FETCH NEXT FROM c INTO @TheDate ;

SET @Interesting_Date=@TheDate

INSERT @cd (TheDate, Qualify)
SELECT @TheDate, @Qualify ;

WHILE @@FETCH_STATUS = 0
BEGIN

    IF @TheDate>DATEADD(DAY, 90, @Interesting_Date)
    BEGIN
        INSERT @cd (TheDate, Qualify)
        SELECT @TheDate, @Qualify ;
        SET @Interesting_Date=@TheDate;
    END

    FETCH NEXT FROM c INTO @TheDate;
END

CLOSE c;
DEALLOCATE c;


SELECT TheDate
    FROM @cd
    ORDER BY TheDate ;

A solução de Paul White ( PW )

;WITH CTE AS
(
    SELECT TOP (1)
        T.[mydate]
    FROM dbo.vGetVisits AS T
    ORDER BY
        T.[mydate]

    UNION ALL

    SELECT
        SQ1.[mydate]
    FROM 
    (
        SELECT
            T.[mydate],
            rn = ROW_NUMBER() OVER (
                ORDER BY T.[mydate])
        FROM CTE
        JOIN dbo.vGetVisits AS T
            ON T.[mydate] > DATEADD(DAY, 90, CTE.[mydate])
    ) AS SQ1
    WHERE
        SQ1.rn = 1
)

SELECT 
    CTE.[mydate]
FROM CTE
OPTION (MAXRECURSION 0);

Minha solução DATEADD ( PN, DATEADD )

DECLARE @cd TABLE
(   TheDate datetime PRIMARY KEY
);

DECLARE @TheDate DATETIME

SET @TheDate=(SELECT MIN(mydate) as mydate FROM [dbo].[vGetVisits])

WHILE (@TheDate IS NOT NULL)
    BEGIN

        INSERT @cd (TheDate) SELECT @TheDate;

        SET @TheDate=(  
            SELECT MIN(mydate) as mydate 
            FROM [dbo].[vGetVisits]
            WHERE mydate>DATEADD(DAY, 90, @TheDate)
                    )
    END

SELECT TheDate
    FROM @cd
    ORDER BY TheDate ;

Minha solução DATEDIFF ( PN, DATEDIFF )

DECLARE @MinDate DATETIME;
SET @MinDate=(SELECT MIN(mydate) FROM dbo.vGetVisits);
    ;WITH gaps AS
    (
       SELECT 
       t1.[date]
       , t1.[MaxDiff]
       , SUM(t1.[MaxDiff]) OVER (ORDER BY t1.[date]) AS [Running Total]
            FROM
            (
                SELECT 
                mydate AS [date]
                , DATEDIFF(day,LAG(mydate, 1, mydate) OVER (ORDER BY mydate) , mydate) AS [MaxDiff] 
                FROM 
                    (SELECT
                    RowNum = ROW_NUMBER() OVER(PARTITION BY cast(mydate as date) ORDER BY mydate)
                    , mydate
                    FROM dbo.vGetVisits
                    ) Actions
                WHERE RowNum = 1
            ) t1
    )

    SELECT [date]
    FROM gaps t2
    WHERE                         
         ( ([Running Total])%91 - ([Running Total]- [MaxDiff])%91 <0 )      
         OR
         ( [MaxDiff] > 90) 
         OR
         ([date]=@MinDate)    
    ORDER BY [date]

Estou usando o SQL Server 2012, então peço desculpas ao Mikael Eriksson, mas o código dele não será testado aqui. Eu ainda esperaria que suas soluções com DATADIFF e DATEADD retornassem valores diferentes em alguns conjuntos de dados.

E os resultados reais são:

Ok, eu perdi alguma coisa ou por que você simplesmente não pularia a recursão e voltaria para si mesmo? Se a data for a chave primária, ela deve ser única e em ordem cronológica se você planeja calcular o deslocamento para a próxima linha

    DECLARE @T AS TABLE
  (
     TheDate DATETIME PRIMARY KEY
  );

INSERT @T
       (TheDate)
VALUES ('2014-01-01 11:00'),
       ('2014-01-03 10:00'),
       ('2014-01-04 09:30'),
       ('2014-04-01 10:00'),
       ('2014-05-01 11:00'),
       ('2014-07-01 09:00'),
       ('2014-07-31 08:00');

SELECT [T1].[TheDate]                               [first],
       [T2].[TheDate]                               [next],
       Datediff(day, [T1].[TheDate], [T2].[TheDate])[offset],
       ( CASE
           WHEN Datediff(day, [T1].[TheDate], [T2].[TheDate]) >= 30 THEN 1
           ELSE 0
         END )                                      [qualify]
FROM   @T[T1]
       LEFT JOIN @T[T2]
              ON [T2].[TheDate] = (SELECT Min([TheDate])
                                   FROM   @T
                                   WHERE  [TheDate] > [T1].[TheDate]) 

Rendimentos

A menos que eu tenha perdido totalmente algo importante....