Comment obtenir la dernière valeur non nulle dans une colonne ordonnée d'une immense table?

13

J'ai l'entrée suivante:

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

J'attends le résultat suivant:

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

La solution triviale serait de joindre les tables avec une <relation, puis de sélectionner la MAXvaleur dans a 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;

Cependant, l'exécution triviale de ce code créerait en interne le carré du compte des lignes de la table d'entrée ( O (n ^ 2) ). Je m'attendais à ce que t-sql l'optimise - au niveau bloc / enregistrement, la tâche à faire est très facile et linéaire, essentiellement une boucle for ( O (n) ).

Cependant, lors de mes expériences, le dernier MS SQL 2016 ne peut pas optimiser correctement cette requête, ce qui rend cette requête impossible à exécuter pour une grande table d'entrée.

De plus, la requête doit s'exécuter rapidement, ce qui rend impossible une solution basée sur un curseur similaire (mais très différente).

L'utilisation d'une table temporaire sauvegardée en mémoire pourrait être un bon compromis, mais je ne sais pas si elle peut être exécutée beaucoup plus rapidement, étant donné que mon exemple de requête utilisant des sous-requêtes n'a pas fonctionné.

Je pense également à déterrer une fonction de fenêtrage des documents t-sql, ce qui pourrait être trompé pour faire ce que je veux. Par exemple, la somme cumulée fait des choses très similaires, mais je ne pouvais pas le tromper pour donner le dernier élément non nul, et non la somme des éléments précédents.

La solution idéale serait une requête rapide sans code procédural ni tables temporaires. Alternativement, une solution avec des tables temporaires est également correcte, mais itérer la table de manière procédurale ne l'est pas.

peterh - Réintégrer Monica
la source

Réponses:

12

Itzik Ben-Gan propose une solution courante à ce type de problème dans son article 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;

Démo: db <> violon

Paul White 9
la source
11

Je m'attendais à ce que t-sql l'optimise - au niveau bloc / enregistrement, la tâche à faire est très facile et linéaire, essentiellement une boucle for (O (n)).

Ce n'est pas la requête que vous avez écrite. Elle peut ne pas être équivalente à la requête que vous avez écrite en fonction de certains détails par ailleurs mineurs du schéma de table. Vous attendez trop de l'optimiseur de requêtes.

Avec la bonne indexation, vous pouvez obtenir l'algorithme que vous recherchez via le T-SQL suivant:

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

Pour chaque ligne, le processeur de requêtes parcourt l'index vers l'arrière et s'arrête lorsqu'il trouve une ligne avec une valeur non nulle pour [VALUE]. Sur ma machine, cela se termine en environ 90 secondes pour 100 millions de lignes dans la table source. La requête s'exécute plus longtemps que nécessaire, car un certain temps est perdu pour le client qui supprime toutes ces lignes.

Je ne sais pas si vous avez besoin de résultats ordonnés ou ce que vous prévoyez de faire avec un ensemble de résultats aussi important. La requête peut être ajustée pour répondre au scénario réel. Le plus grand avantage de cette approche est qu'elle ne nécessite pas de tri dans le plan de requête. Cela peut aider pour de plus grands ensembles de résultats. Un inconvénient est que les performances ne seront pas optimales s'il y a beaucoup de NULL dans la table car de nombreuses lignes seront lues à partir de l'index et supprimées. Vous devriez être en mesure d'améliorer les performances avec un index filtré qui exclut les valeurs NULL pour ce cas.

Exemples de données pour le test:

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);
Joe Obbish
la source
7

Une méthode, en utilisant OVER()et MAX()et COUNT()basée sur cette source pourrait être:

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;

Résultat

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

Une autre méthode basée sur cette source , étroitement liée au premier exemple

;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;
Randi Vertongen
la source
3
Pensez à ajouter des détails sur les performances de ces approches avec une "table énorme".
Joe Obbish