Analyses inattendues lors d'une opération de suppression à l'aide de WHERE IN

J'ai une requête comme celle-ci:

DELETE FROM tblFEStatsBrowsers WHERE BrowserID NOT IN (
    SELECT DISTINCT BrowserID FROM tblFEStatsPaperHits WITH (NOLOCK) WHERE BrowserID IS NOT NULL
)

tblFEStatsBrowsers a 553 lignes.
tblFEStatsPaperHits a 47.974.301 lignes.

tblFEStatsBrowsers:

CREATE TABLE [dbo].[tblFEStatsBrowsers](
    [BrowserID] [smallint] IDENTITY(1,1) NOT NULL,
    [Browser] [varchar](50) NOT NULL,
    [Name] [varchar](40) NOT NULL,
    [Version] [varchar](10) NOT NULL,
    CONSTRAINT [PK_tblFEStatsBrowsers] PRIMARY KEY CLUSTERED ([BrowserID] ASC)
)

tblFEStatsPaperHits:

CREATE TABLE [dbo].[tblFEStatsPaperHits](
    [PaperID] [int] NOT NULL,
    [Created] [smalldatetime] NOT NULL,
    [IP] [binary](4) NULL,
    [PlatformID] [tinyint] NULL,
    [BrowserID] [smallint] NULL,
    [ReferrerID] [int] NULL,
    [UserLanguage] [char](2) NULL
)

Il existe un index clusterisé sur tblFEStatsPaperHits qui n'inclut pas BrowserID. L'exécution de la requête interne nécessitera donc une analyse complète de la table de tblFEStatsPaperHits - ce qui est totalement OK.

Actuellement, une analyse complète est exécutée pour chaque ligne dans tblFEStatsBrowsers, ce qui signifie que j'ai 553 analyses complètes de la table de tblFEStatsPaperHits.

La réécriture dans un fichier WHERE EXISTS ne change pas le plan:

DELETE FROM tblFEStatsBrowsers WHERE NOT EXISTS (
    SELECT * FROM tblFEStatsPaperHits WITH (NOLOCK) WHERE BrowserID = tblFEStatsBrowsers.BrowserID
)

Cependant, comme l'a suggéré Adam Machanic, l'ajout d'une option HASH JOIN donne un plan d'exécution optimal (un seul balayage de tblFEStatsPaperHits):

DELETE FROM tblFEStatsBrowsers WHERE NOT EXISTS (
    SELECT * FROM tblFEStatsPaperHits WITH (NOLOCK) WHERE BrowserID = tblFEStatsBrowsers.BrowserID
) OPTION (HASH JOIN)

Maintenant, ce n’est plus une question de solution: je peux utiliser OPTION (HASH JOIN) ou créer une table temporaire manuellement. Je me demande davantage pourquoi l'optimiseur de requêtes utiliserait jamais le plan actuel.

Le QO n'ayant aucune statistique dans la colonne BrowserID, j'imagine qu'il suppose le pire - 50 millions de valeurs distinctes, nécessitant ainsi une table de travail en mémoire / tempdb assez importante. En tant que tel, le moyen le plus sûr consiste à effectuer des analyses pour chaque ligne dans tblFEStatsBrowsers. Il n'y a pas de relation de clé étrangère entre les colonnes de BrowserID dans les deux tables. Le QO ne peut donc déduire aucune information de tblFEStatsBrowsers.

Est-ce aussi simple que cela puisse paraître, la raison?

Mise à jour 1
Pour donner quelques statistiques: OPTION (HASH JOIN):
208.711 lectures logiques (12 scans)

OPTION (LOOP JOIN, HASH GROUP):
11.008.698 lectures logiques (~ analyse par ID de navigateur (339))

Aucune option:
11.008.775 lectures logiques (~ analyse par ID de navigateur (339))

Mise à jour 2
Excellentes réponses à toutes et à tous - merci! Difficile d'en choisir un seul. Bien que Martin ait été le premier et que Remus fournisse une excellente solution, je dois la donner au Kiwi pour ne pas perdre de vue les détails :)

"Je me demande davantage pourquoi l'optimiseur de requêtes utiliserait jamais le plan qu'il utilise actuellement."

En d'autres termes, la question est de savoir pourquoi l'optimiseur offre le plan le moins cher par rapport aux alternatives (qui sont nombreuses ).

Le côté interne de la jointure exécute essentiellement une requête de la forme suivante pour chaque valeur corrélée de BrowserID:

DECLARE @BrowserID smallint;

SELECT 
    tfsph.BrowserID 
FROM dbo.tblFEStatsPaperHits AS tfsph 
WHERE 
    tfsph.BrowserID = @BrowserID 
OPTION (MAXDOP 1);

Notez que le nombre estimé de lignes est 185220 (non 289013 ) puisque la comparaison de l' égalité exclut implicitement NULL(sauf ANSI_NULLSest OFF). Le coût estimé du plan ci-dessus est de 206,8 unités.

Ajoutons maintenant une TOP (1)clause:

DECLARE @BrowserID smallint;

SELECT TOP (1)
    tfsph.BrowserID 
FROM dbo.tblFEStatsPaperHits AS tfsph 
WHERE 
    tfsph.BrowserID = @BrowserID 
OPTION (MAXDOP 1);

Le coût estimé est maintenant de 0,00452 unité. L’ajout de l’opérateur physique Top définit un objectif de ligne de 1 ligne sur l'opérateur Top. La question est alors de savoir comment obtenir un «objectif de ligne» pour l'analyse d'index clusterisé; Autrement dit, combien de lignes l'analyse devrait-elle traiter avant qu'une ligne ne corresponde au BrowserIDprédicat?

Les informations statistiques disponibles indiquent 166BrowserID valeurs distinctes (1 / [Toute la densité] = 1 / 0,006024096 = 166). Le calcul des coûts suppose que les valeurs distinctes sont réparties uniformément sur les lignes physiques. Par conséquent, l'objectif de la ligne dans l'analyse en cluster par cluster est défini sur 166,302 (en tenant compte du changement de cardinalité du tableau depuis la collecte des statistiques échantillonnées).

Le coût estimé de l'analyse des 166 lignes attendues n'est pas très élevé (même exécuté 339 fois, une fois pour chaque changement de BrowserID) - l'analyse par cluster en cluster affiche un coût estimé à 1,3219 unités, illustrant l'effet de mise à l'échelle de l'objectif de ligne. Les coûts d’opérateur non mis à l’échelle pour les E / S et la CPU sont indiqués comme suit : 153.931 et 52.8698. respectivement:

En pratique, il est très peu probable que les 166 premières lignes analysées à partir de l'index (dans l'ordre de leur renvoi) contiendront une des BrowserIDvaleurs possibles . Néanmoins, le DELETEplan est chiffré à 1,40921 unités au total et est sélectionné par l'optimiseur pour cette raison. Bart Duncan montre un autre exemple de ce type dans un article récent intitulé Row Goals Gone Rogue .

Il est également intéressant de noter que l’opérateur Top dans le plan d’exécution n’est pas associé à la fonction Anti semi-jointure (en particulier, mentionne le «court-circuitage» de Martin). Nous pouvons commencer à voir d'où vient le sommet en désactivant d'abord une règle d'exploration appelée GbAggToConstScanOrTop :

DBCC RULEOFF ('GbAggToConstScanOrTop');
GO
DELETE FROM tblFEStatsBrowsers 
WHERE BrowserID NOT IN 
(
    SELECT DISTINCT BrowserID 
    FROM tblFEStatsPaperHits WITH (NOLOCK) 
    WHERE BrowserID IS NOT NULL
) OPTION (MAXDOP 1, LOOP JOIN, RECOMPILE);
GO
DBCC RULEON ('GbAggToConstScanOrTop');

Ce plan a un coût estimé à 364 912 et montre que le Top a remplacé un groupe par agrégat (regroupement par la colonne corrélée BrowserID). L'agrégat n'est pas dû au redondant DISTINCTdans le texte de la requête: il s'agit d'une optimisation pouvant être introduite par deux règles d'exploration, LASJNtoLASJNonDist et LASJOnLclDist . Désactiver ces deux aussi produit ce plan:

DBCC RULEOFF ('LASJNtoLASJNonDist');
DBCC RULEOFF ('LASJOnLclDist');
DBCC RULEOFF ('GbAggToConstScanOrTop');
GO
DELETE FROM tblFEStatsBrowsers 
WHERE BrowserID NOT IN 
(
    SELECT DISTINCT BrowserID 
    FROM tblFEStatsPaperHits WITH (NOLOCK) 
    WHERE BrowserID IS NOT NULL
) OPTION (MAXDOP 1, LOOP JOIN, RECOMPILE);
GO
DBCC RULEON ('LASJNtoLASJNonDist');
DBCC RULEON ('LASJOnLclDist');
DBCC RULEON ('GbAggToConstScanOrTop');

Ce plan a un coût estimé de 40729,3 unités.

Sans la transformation de Group By to Top, l'optimiseur choisit «naturellement» un plan de jointure de hachage avec BrowserIDagrégation avant la jointure anti-semi:

DBCC RULEOFF ('GbAggToConstScanOrTop');
GO
DELETE FROM tblFEStatsBrowsers 
WHERE BrowserID NOT IN 
(
    SELECT DISTINCT BrowserID 
    FROM tblFEStatsPaperHits WITH (NOLOCK) 
    WHERE BrowserID IS NOT NULL
) OPTION (MAXDOP 1, RECOMPILE);
GO
DBCC RULEON ('GbAggToConstScanOrTop');

Et sans la restriction MAXDOP 1, un plan parallèle:

Une autre façon de "réparer" la requête initiale serait de créer l'index manquant sur BrowserID lequel le plan d'exécution est signalé. Les boucles imbriquées fonctionnent mieux lorsque le côté intérieur est indexé. L'estimation de la cardinalité pour les semi-jointures est difficile dans les meilleures conditions. Ne pas avoir l'indexation appropriée (la grande table n'a même pas de clé unique!) N'aidera pas du tout.

J'ai écrit plus à ce sujet dans Row Goals, Part 4: The Anti Join Anti Pattern .

Lorsque j'exécute votre script pour créer une base de données contenant uniquement des statistiques et la requête de la question, je reçois le plan suivant.

Les cardinalités de la table montrées dans le plan sont

• tblFEStatsPaperHits: 48063400
• tblFEStatsBrowsers : 339

Il estime donc qu’il devra effectuer l’analyse tblFEStatsPaperHits339 fois. Chaque analyse a le prédicat corrélé tblFEStatsBrowsers.BrowserID=tblFEStatsPaperHits.BrowserID AND tblFEStatsPaperHits.BrowserID IS NOT NULLqui est enfoncé dans l'opérateur d'analyse.

Le plan ne signifie cependant pas qu'il y aura 339 analyses complètes. Comme il est placé sous un opérateur anti-jointure dès que la première ligne correspondante de chaque analyse est trouvée, elle peut court-circuiter le reste. Le coût estimé de la sous-arborescence pour ce noeud est égal au coût 1.32603total du plan 1.41337.

Pour le hachage rejoindre, il donne le plan ci-dessous

Le plan global est chiffré à 418.415(environ 300 fois plus cher que le plan à boucles imbriquées), avec la seule analyse d'index en cluster complet tblFEStatsPaperHitschiffrée en 206.8autonome. Comparez cela avec l' 1.32603estimation de 339 analyses partielles données précédemment (coût estimé moyen de l'analyse partielle =0.003911592 ).

Cela indiquerait donc que chaque analyse partielle coûte 53 000 fois moins chère qu'une analyse complète. Si les coûts devaient évoluer de manière linéaire avec le nombre de lignes, cela signifierait que l'on suppose qu'en moyenne, il ne devrait traiter que 900 lignes à chaque itération avant de trouver une ligne correspondante et de pouvoir court-circuiter.

Je ne pense cependant pas que les coûts s’échelonnent de manière linéaire. Je pense qu'ils incorporent également un élément de coût de démarrage fixe. Essayer différentes valeurs de TOPdans la requête suivante

SELECT TOP 147 BrowserID 
FROM [dbo].[tblFEStatsPaperHits] 

147donne le coût estimé le plus proche de sous - arbre 0.003911592à 0.0039113. Quoi qu'il en soit, il est clair que les coûts sont fondés sur l'hypothèse que chaque analyse ne doit traiter qu'une infime proportion du tableau, dans l'ordre de centaines de lignes plutôt que de millions.

Je ne sais pas exactement sur quoi se base cette hypothèse en termes mathématiques, et cela ne correspond pas vraiment aux estimations du nombre de lignes dans le reste du plan (les 236 lignes estimées issues de la jointure des boucles imbriquées impliqueraient qu'il y avait 236 cas où aucune ligne correspondante n’a été trouvée et qu’une analyse complète était requise). Je suppose qu’il s’agit simplement d’un cas où les hypothèses de modélisation retenues s’effondrent quelque peu et laissent le plan des boucles imbriquées sous-estimé de manière chiffrée.

Dans mon livre, même un balayage de 50 millions de lignes est inacceptable ... Mon astuce habituelle consiste à matérialiser les valeurs distinctes et à déléguer le moteur pour le maintenir à jour:

create view [dbo].[vwFEStatsPaperHitsBrowserID]
with schemabinding
as
select BrowserID, COUNT_BIG(*) as big_count
from [dbo].[tblFEStatsPaperHits]
group by [BrowserID];
go

create unique clustered index [cdxVwFEStatsPaperHitsBrowserID] 
  on [vwFEStatsPaperHitsBrowserID]([BrowserID]);
go

Cela vous donne un index matérialisé d'une ligne par BrowserID, éliminant le besoin d'analyser 50 millions de lignes. Le moteur le conservera pour vous et le responsable de la qualité l'utilisera «tel quel» dans la déclaration que vous avez publiée (sans indication ni réécriture de requête).

L'inconvénient est bien sûr la controverse. Toute opération d’insertion ou de suppression dans tblFEStatsPaperHits(et je suppose qu’il s’agit d’une table de journalisation avec des insertions lourdes) devra sérialiser l’accès à un BrowserID donné. Il existe des moyens de rendre cette opération réalisable (mises à jour retardées, journalisation en deux étapes, etc.) si vous êtes prêt à l'acheter.