Как получить последнее ненулевое значение в упорядоченном столбце огромной таблицы?

У меня есть следующий вход:

 id | value 
----+-------
  1 |   136
  2 |  NULL
  3 |   650
  4 |  NULL
  5 |  NULL
  6 |  NULL
  7 |   954
  8 |  NULL
  9 |   104
 10 |  NULL

Я ожидаю следующий результат:

 id | value 
----+-------
  1 |   136
  2 |   136
  3 |   650
  4 |   650
  5 |   650
  6 |   650
  7 |   954
  8 |   954
  9 |   104
 10 |   104

Тривиальным решением было бы объединить таблицы с <отношением, а затем выбрать MAXзначение в GROUP BY:

WITH tmp AS (
  SELECT t2.id, MAX(t1.id) AS lastKnownId
  FROM t t1, t t2
  WHERE
    t1.value IS NOT NULL
    AND
    t2.id >= t1.id
  GROUP BY t2.id
)
SELECT
  tmp.id, t.value
FROM t, tmp
WHERE t.id = tmp.lastKnownId;

Тем не менее, тривиальное выполнение этого кода создаст внутренне квадрат числа строк входной таблицы ( O (n ^ 2) ). Я ожидал, что t-sql оптимизирует его - на уровне блоков / записей задача очень проста и линейна, по сути это цикл for ( O (n) ).

Однако в моих экспериментах последняя версия MS SQL 2016 не может правильно оптимизировать этот запрос, что делает невозможным его выполнение для большой входной таблицы.

Кроме того, запрос должен выполняться быстро, делая невозможным аналогичное простое (но очень отличающееся) решение на основе курсора.

Использование некоторой временной таблицы с поддержкой памяти может быть хорошим компромиссом, но я не уверен, что ее можно будет выполнить значительно быстрее, учитывая, что мой пример запроса с использованием подзапросов не работал.

Я также думаю о том, чтобы откопать некоторую оконную функцию из документации t-sql, что можно было сделать, чтобы сделать то, что я хочу. Например, накопленная сумма делает нечто очень похожее, но я не мог обмануть ее, чтобы получить последний ненулевой элемент, а не сумму элементов ранее.

Идеальным решением был бы быстрый запрос без процедурного кода или временных таблиц. В качестве альтернативы, также возможно решение с временными таблицами, но процедурная итерация таблицы - нет.

Распространенное решение проблемы такого типа дает Ицик Бен-Ган в своей статье «Последняя не пустая головоломка» :

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;

Демо: db <> скрипка

Я ожидал, что t-sql оптимизирует его - на уровне блоков / записей задача очень проста и линейна, по сути это цикл for (O (n)).

Это не тот запрос, который вы написали. Это может быть не эквивалентно написанному вами запросу, в зависимости от некоторых незначительных деталей схемы таблицы. Вы ожидаете слишком многого от оптимизатора запросов.

С правильной индексацией вы можете получить алгоритм, который вы ищете через следующий 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

Для каждой строки обработчик запросов просматривает индекс в обратном направлении и останавливается, когда находит строку с ненулевым значением для [VALUE]. На моей машине это заканчивается примерно за 90 секунд для 100 миллионов строк в исходной таблице. Запрос выполняется дольше, чем необходимо, поскольку на клиенте теряется некоторое время, отбрасывающее все эти строки.

Мне не ясно, нужны ли вам упорядоченные результаты или что вы планируете делать с таким большим набором результатов. Запрос может быть скорректирован с учетом фактического сценария. Самым большим преимуществом этого подхода является то, что он не требует сортировки в плане запроса. Это может помочь для больших наборов результатов. Одним из недостатков является то, что производительность не будет оптимальной, если в таблице много NULL, поскольку многие строки будут считаны из индекса и отброшены. Вы должны иметь возможность улучшить производительность с помощью отфильтрованного индекса, который исключает NULL для этого случая.

Пример данных для теста:

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

Один из способов, с помощью OVER()и MAX()и на COUNT()основе этого источника может быть:

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;

Результат

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

Еще один метод, основанный на этом источнике , тесно связан с первым примером

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