Como obter o último valor não nulo em uma coluna ordenada de uma tabela enorme?

Uma solução comum para este tipo de problema é dada por Itzik Ben-Gan em seu artigo The Last non NULL Puzzle :

DROP TABLE IF EXISTS dbo.Example;

CREATE TABLE dbo.Example
(
    id integer PRIMARY KEY,
    val integer NULL
);

INSERT dbo.Example
    (id, val)
VALUES
    (1, 136),
    (2, NULL),
    (3, 650),
    (4, NULL),
    (5, NULL),
    (6, NULL),
    (7, 954),
    (8, NULL),
    (9, 104),
    (10, NULL);

SELECT
    E.id,
    E.val,
    lastval =
        CAST(
            SUBSTRING(
                MAX(CAST(E.id AS binary(4)) + CAST(E.val AS binary(4))) OVER (
                    ORDER BY E.id
                    ROWS UNBOUNDED PRECEDING),
            5, 4)
        AS integer)
FROM dbo.Example AS E
ORDER BY
    E.id;

Demonstração: db<>fiddle

Eu esperava que o t-sql o otimizasse - em um nível de bloco/registro, a tarefa a ser feita é muito fácil e linear, essencialmente um loop for ( O(n) ).

Essa não é a consulta que você escreveu. Pode não ser equivalente à consulta que você escreveu, dependendo de alguns detalhes menores do esquema da tabela. Você está esperando demais do otimizador de consultas.

Com a indexação correta, você pode obter o algoritmo que procura através do seguinte T-SQL:

SELECT t1.id, ca.[VALUE] 
FROM dbo.[BIG_TABLE(FOR_U)] t1
CROSS APPLY (
    SELECT TOP (1) [VALUE]
    FROM dbo.[BIG_TABLE(FOR_U)] t2
    WHERE t2.ID <= t1.ID AND t2.[VALUE] IS NOT NULL
    ORDER BY t2.ID DESC
) ca; --ORDER BY t1.ID ASC

Para cada linha, o processador de consultas percorre o índice para trás e para quando encontra uma linha com um valor não nulo para [VALUE]. Na minha máquina, isso termina em cerca de 90 segundos para 100 milhões de linhas na tabela de origem. A consulta é executada por mais tempo do que o necessário porque algum tempo é desperdiçado no cliente descartando todas essas linhas.

Não está claro para mim se você precisa de resultados ordenados ou o que planeja fazer com um conjunto de resultados tão grande. A consulta pode ser ajustada para atender ao cenário real. A maior vantagem dessa abordagem é que ela não requer uma classificação no plano de consulta. Isso pode ajudar para conjuntos de resultados maiores. Uma desvantagem é que o desempenho não será ótimo se houver muitos NULLs na tabela porque muitas linhas serão lidas do índice e descartadas. Você deve conseguir melhorar o desempenho com um índice filtrado que exclua NULLs para esse caso.

Dados de amostra para o teste:

DROP TABLE IF EXISTS #t;

CREATE TABLE #t (
ID BIGINT NOT NULL
);

INSERT INTO #t WITH (TABLOCK)
SELECT TOP (10000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) - 1
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);

DROP TABLE IF EXISTS dbo.[BIG_TABLE(FOR_U)];

CREATE TABLE dbo.[BIG_TABLE(FOR_U)] (
ID BIGINT NOT NULL,
[VALUE] BIGINT NULL
);

INSERT INTO dbo.[BIG_TABLE(FOR_U)] WITH (TABLOCK)
SELECT 10000 * t1.ID + t2.ID, CASE WHEN (t1.ID + t2.ID) % 3 = 1 THEN t2.ID ELSE NULL END
FROM #t t1
CROSS JOIN #t t2;

CREATE UNIQUE CLUSTERED INDEX ADD_ORDERING ON dbo.[BIG_TABLE(FOR_U)] (ID);

Um método, usando OVER()and MAX()e COUNT()com base nessa fonte , pode ser:

SELECT ID, MAX(value) OVER (PARTITION BY Value2) as value
FROM
(
    SELECT ID, value
        ,COUNT(value) OVER (ORDER BY ID) AS Value2
    FROM dbo.HugeTable
) a
ORDER BY ID;

Resultado

Id  UpdatedValue
1   136
2   136
3   650
4   650
5   650
6   650
7   954
8   954
9   104
10  104

Outro método baseado nesta fonte , intimamente relacionado com o primeiro exemplo

;WITH CTE As 
( 
SELECT  value,
        Id, 
        COUNT(value) 
        OVER(ORDER BY Id) As  Value2 
FROM dbo.HugeTable
),

CTE2 AS ( 
SELECT Id,
       value,
       First_Value(value)  
       OVER( PARTITION BY Value2
             ORDER BY Id) As UpdatedValue 
FROM CTE 
            ) 
SELECT Id,UpdatedValue 
FROM CTE2;