Forcer le flux distinct

J'ai une table comme celle-ci:

CREATE TABLE Updates
(
    UpdateId INT NOT NULL IDENTITY(1,1) PRIMARY KEY,
    ObjectId INT NOT NULL
)

Suivi essentiellement des mises à jour des objets avec un ID croissant.

Le consommateur de ce tableau sélectionnera un bloc de 100 ID d'objet distincts, classés par UpdateIdet à partir d'un spécifique UpdateId. Essentiellement, en gardant une trace de l'endroit où il s'est arrêté, puis en recherchant des mises à jour.

J'ai trouvé cela un problème d'optimisation intéressante parce que je ne l' ai été en mesure de générer un plan de requête au maximum optimale en écrivant des requêtes qui arrivent à faire ce que je veux en raison d'indices, mais ne vous garantis que je veux:

SELECT DISTINCT TOP 100 ObjectId
FROM Updates
WHERE UpdateId > @fromUpdateId

Où @fromUpdateIdest un paramètre de procédure stockée.

Avec un plan de:

SELECT <- TOP <- Hash match (flow distinct, 100 rows touched) <- Index seek

En raison de la recherche sur l' UpdateIdindex utilisé, les résultats sont déjà agréables et classés du ID de mise à jour le plus bas au plus élevé comme je le souhaite. Et cela génère un plan de flux distinct , ce que je veux. Mais la commande n'est évidemment pas un comportement garanti, donc je ne veux pas l'utiliser.

Cette astuce entraîne également le même plan de requête (mais avec un TOP redondant):

WITH ids AS
(
    SELECT ObjectId
    FROM Updates
    WHERE UpdateId > @fromUpdateId
    ORDER BY UpdateId OFFSET 0 ROWS
)
SELECT DISTINCT TOP 100 ObjectId FROM ids

Cependant, je ne suis pas sûr (et je ne le pense pas) si cela garantit vraiment la commande.

Voici une requête que j'espérais que SQL Server serait assez intelligent pour simplifier, mais cela finit par générer un très mauvais plan de requête:

SELECT TOP 100 ObjectId
FROM Updates
WHERE UpdateId > @fromUpdateId
GROUP BY ObjectId
ORDER BY MIN(UpdateId)

Avec un plan de:

SELECT <- Top N Sort <- Hash Match aggregate (50,000+ rows touched) <- Index Seek

J'essaie de trouver un moyen de générer un plan optimal avec une recherche d'index UpdateIdet un flux distinct pour supprimer les doublons ObjectId. Des idées?

Exemple de données si vous le souhaitez. Les objets auront rarement plus d'une mise à jour, et ne devraient presque jamais en avoir plus d'une dans un ensemble de 100 lignes, c'est pourquoi je recherche un flux distinct , à moins qu'il y ait quelque chose de mieux que je ne sache pas? Cependant, il n'y a aucune garantie qu'un seul ObjectIdne contiendra pas plus de 100 lignes dans le tableau. Le tableau compte plus de 1 000 000 de lignes et devrait croître rapidement.

Supposons que l'utilisateur de ceci ait une autre façon de trouver la suivante appropriée @fromUpdateId. Pas besoin de le renvoyer dans cette requête.

L'optimiseur SQL Server ne peut pas produire le plan d'exécution que vous recherchez avec la garantie dont vous avez besoin, car l' opérateur Hash Match Flow Distinct ne préserve pas l'ordre.

Cependant, je ne suis pas sûr (et je ne le pense pas) si cela garantit vraiment la commande.

Vous pouvez observer la conservation de l'ordre dans de nombreux cas, mais il s'agit d'un détail d'implémentation; il n'y a aucune garantie, vous ne pouvez donc pas vous y fier. Comme toujours, l'ordre de présentation ne peut être garanti que par une ORDER BYclause de niveau supérieur .

Exemple

Le script ci-dessous montre que Hash Match Flow Distinct ne préserve pas l'ordre. Il met en place le tableau en question avec des numéros correspondants de 1 à 50 000 dans les deux colonnes:

IF OBJECT_ID(N'dbo.Updates', N'U') IS NOT NULL
    DROP TABLE dbo.Updates;
GO
CREATE TABLE Updates
(
    UpdateId INT NOT NULL IDENTITY(1,1),
    ObjectId INT NOT NULL,

    CONSTRAINT PK_Updates_UpdateId PRIMARY KEY (UpdateId)
);
GO
INSERT dbo.Updates (ObjectId)
SELECT TOP (50000)
    ObjectId =
        ROW_NUMBER() OVER (
            ORDER BY C1.[object_id]) 
FROM sys.columns AS C1
CROSS JOIN sys.columns AS C2
ORDER BY
    ObjectId;

La requête de test est:

DECLARE @Rows bigint = 50000;

-- Optimized for 1 row, but will be 50,000 when executed
SELECT DISTINCT TOP (@Rows)
    U.ObjectId 
FROM dbo.Updates AS U
WHERE 
    U.UpdateId > 0
OPTION (OPTIMIZE FOR (@Rows = 1));

Le plan estimé montre une recherche et un flux d'indices distincts:

La sortie semble certainement ordonnée de commencer par:

... mais des valeurs plus basses commencent à devenir "manquantes":

...et éventuellement:

L'explication dans ce cas particulier est que l'opérateur de hachage se renverse:

Une fois qu'une partition s'est renversée, toutes les lignes hachées vers la même partition se sont également renversées. Les partitions déversées sont traitées plus tard, ce qui brise l'espoir que des valeurs distinctes rencontrées seront émises immédiatement dans l'ordre où elles sont reçues.

Il existe de nombreuses façons d'écrire une requête efficace pour produire le résultat ordonné souhaité, comme la récursivité ou l'utilisation d'un curseur. Cependant, cela ne peut pas être fait en utilisant Hash Match Flow Distinct .

Je ne suis pas satisfait de cette réponse car je n'ai pas réussi à obtenir un opérateur de flux distinct avec des résultats garantis corrects. Cependant, j'ai une alternative qui devrait obtenir de bonnes performances avec des résultats corrects. Malheureusement, cela nécessite qu'un index non cluster soit créé sur la table.

J'ai abordé ce problème en essayant de penser à une combinaison de colonnes que je pouvais ORDER BYet d'obtenir les résultats corrects après DISTINCTleur avoir appliqué . La valeur minimale de UpdateIdper ObjectIdavec ObjectIdest une de ces combinaisons. Cependant, demander directement le minimum UpdateIdsemble entraîner la lecture de toutes les lignes du tableau. Au lieu de cela, nous pouvons indirectement demander la valeur minimale de UpdateIdavec une autre jointure à la table. L'idée est de scanner le Updatestableau dans l'ordre, de jeter toutes les lignes pour lesquelles ce UpdateIdn'est pas la valeur minimale pour cette ligne.ObjectId et de conserver les 100 premières lignes. Sur la base de votre description de la distribution des données, nous ne devrions pas avoir besoin de jeter trop de lignes.

Pour la préparation des données, j'ai mis 1 million de lignes dans une table avec 2 lignes pour chaque ObjectId distinct:

INSERT INTO Updates WITH (TABLOCK)
SELECT t.RN / 2
FROM 
(
    SELECT TOP 1000000 -1 + ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
    FROM master..spt_values t1
    CROSS JOIN master..spt_values t2
) t;

CREATE INDEX IX On Updates (Objectid, UpdateId);

L'index non clusterisé sur Objectidet UpdateIdest important. Il nous permet de jeter efficacement des lignes qui n'ont pas le minimum UpdateIdpar Objectid. Il existe plusieurs façons d'écrire une requête qui correspond à la description ci-dessus. Voici une telle façon d'utiliser NOT EXISTS:

DECLARE @fromUpdateId INT = 9999;
SELECT ObjectId
FROM (
    SELECT DISTINCT TOP 100 u1.UpdateId, u1.ObjectId
    FROM Updates u1
    WHERE UpdateId > @fromUpdateId
    AND NOT EXISTS (
        SELECT 1
        FROM Updates u2
        WHERE u2.UpdateId > @fromUpdateId
        AND u1.ObjectId = u2.ObjectId
        AND u2.UpdateId < u1.UpdateId
    )
    ORDER BY u1.UpdateId, u1.ObjectId
) t;

Voici une image du plan de requête :

Dans le meilleur des cas, SQL Server ne fera que 100 recherches d'index par rapport à l'index non cluster. Pour simuler la malchance, j'ai modifié la requête pour renvoyer les 5000 premières lignes au client. Cela a abouti à 9999 recherches d'index, c'est donc comme obtenir une moyenne de 100 lignes par distinct ObjectId. Voici la sortie de SET STATISTICS IO, TIME ON:

Tableau «Mises à jour». Nombre de scans 10000, lectures logiques 31900, lectures physiques 0

Temps d'exécution SQL Server: temps CPU = 31 ms, temps écoulé = 42 ms.

J'adore la question - Flow Distinct est l'un de mes opérateurs préférés.

Maintenant, la garantie est le problème. Lorsque vous pensez que l'opérateur FD extrait les lignes de l'opérateur Seek de manière ordonnée, produisant chaque ligne comme il la détermine comme étant unique, cela vous donnera les lignes dans le bon ordre. Mais il est difficile de savoir s'il peut y avoir des scénarios où le FD ne gère pas une seule ligne à la fois.

Théoriquement, le FD pourrait demander 100 lignes à la recherche et les produire dans l'ordre qu'il en a besoin.

Les conseils de requête OPTION (FAST 1, MAXDOP 1)pourraient aider, car cela évitera d'obtenir plus de lignes que nécessaire de l'opérateur Seek. Est-ce une garantie cependant? Pas assez. Il pourrait toujours décider de tirer une page de lignes à la fois, ou quelque chose comme ça.

Je pense qu'avec OPTION (FAST 1, MAXDOP 1), votre OFFSETversion vous donnerait beaucoup de confiance dans la commande, mais ce n'est pas une garantie.