Jak uzyskać ostatnią wartość inną niż null w uporządkowanej kolumnie ogromnej tabeli?

Mam następujące dane wejściowe:

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

Oczekuję następującego wyniku:

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

Trywialnym rozwiązaniem byłoby połączenie tabel z <relacją, a następnie wybranie MAXwartości w 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;

Jednak trywialne wykonanie tego kodu stworzyłoby wewnętrznie kwadrat liczby wierszy tabeli wejściowej ( O (n ^ 2) ). Spodziewałem się, że t-sql zoptymalizuje to - na poziomie bloku / rekordu zadanie do wykonania jest bardzo łatwe i liniowe, zasadniczo dla pętli for ( O (n) ).

Jednak w moich eksperymentach najnowszy MS SQL 2016 nie może poprawnie zoptymalizować tego zapytania, co uniemożliwia wykonanie tego zapytania dla dużej tabeli wejściowej.

Ponadto zapytanie musi być uruchamiane szybko, co sprawia, że ​​podobnie łatwe (ale bardzo różne) rozwiązanie oparte na kursorach jest niemożliwe.

Użycie tabeli tymczasowej opartej na pamięci może być dobrym kompromisem, ale nie jestem pewien, czy można ją uruchomić znacznie szybciej, biorąc pod uwagę, że moje przykładowe zapytanie wykorzystujące podzapytania nie działało.

Zastanawiam się również nad wykryciem jakiejś funkcji okienkowania z dokumentów t-sql, co może być trudne do zrobienia, co chcę. Na przykład suma skumulowana działa bardzo podobnie, ale nie mogłem oszukać, aby uzyskać najnowszy element inny niż null, a nie sumę elementów wcześniej.

Idealnym rozwiązaniem byłoby szybkie zapytanie bez kodu proceduralnego lub tabel tymczasowych. Alternatywnie, również rozwiązanie z tabelami tymczasowymi jest w porządku, ale procedury powtarzania tabeli nie są.

Typowe rozwiązanie tego rodzaju problemu podaje Itzik Ben-Gan w swoim artykule 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;

Demo: skrzypce db <>

Spodziewałem się, że t-sql zoptymalizuje to - na poziomie bloku / rekordu zadanie do wykonania jest bardzo łatwe i liniowe, zasadniczo dla pętli for (O (n)).

To nie jest zapytanie, które napisałeś. Może nie być to odpowiednik zapytania, które napisałeś, w zależności od pewnych drobnych szczegółów schematu tabeli. Za dużo oczekujesz od optymalizatora zapytań.

Dzięki właściwemu indeksowaniu możesz uzyskać algorytm, którego szukasz poprzez następujący 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

Dla każdego wiersza procesor zapytań przegląda indeks wstecz i zatrzymuje się, gdy znajdzie wiersz o wartości innej niż null dla [VALUE]. Na mojej maszynie kończy się to w około 90 sekund dla 100 milionów wierszy w tabeli źródłowej. Kwerenda działa dłużej niż to konieczne, ponieważ marnuje się pewien czas na odrzucanie przez klienta wszystkich tych wierszy.

Nie jest dla mnie jasne, czy potrzebujesz uporządkowanych wyników lub co planujesz zrobić z tak dużym zestawem wyników. Zapytanie można dostosować do rzeczywistego scenariusza. Największą zaletą tego podejścia jest to, że nie wymaga sortowania w planie zapytań. Może to pomóc w przypadku większych zestawów wyników. Wadą jest to, że wydajność nie będzie optymalna, jeśli w tabeli jest dużo wartości NULL, ponieważ wiele wierszy zostanie odczytanych z indeksu i odrzuconych. Powinieneś być w stanie poprawić wydajność dzięki filtrowanemu indeksowi, który wyklucza wartości NULL dla tego przypadku.

Przykładowe dane do testu:

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

Jedną z metod, za pomocą OVER()i MAX()i COUNT()na podstawie tego źródła mogą być:

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;

Wynik

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

Kolejna metoda oparta na tym źródle , ściśle związana z pierwszym przykładem

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