Quel est l'algorithme derrière l'opérateur EXCEPT?

Quel est l'algorithme interne du fonctionnement de l' opérateur Except sous les couvertures de SQL Server? Faut-il en interne un hachage de chaque ligne et comparer?

David Lozinksi a mené une étude, SQL: le moyen le plus rapide d'insérer de nouveaux enregistrements là où il n'y en a pas déjà. Il a montré que l'instruction Except est la plus rapide pour les lignes à grand nombre; étroitement lié à nos résultats ci-dessous.

Hypothèse: je pense que la jointure gauche serait la plus rapide, car elle ne compare qu'une seule colonne, sauf qu'elle prendrait le plus de temps, car elle doit comparer toutes les colonnes.
Avec ces résultats, maintenant notre pensée est Exceptée automatiquement et prend en interne un hachage de chaque ligne? J'ai regardé Except plan d'exécution et il utilise un peu de hachage.

Contexte: Notre équipe comparait deux tables de tas. Tableau A Les lignes ne figurant pas dans le tableau B ont été insérées dans le tableau B.

Les tables de tas (du système de fichiers texte hérité) n'ont pas de clés primaires / guides / identificateurs. Certaines tables avaient des lignes en double, nous avons donc trouvé le hachage de chaque ligne, supprimé les doublons et créé des identificateurs de clé primaire.

1) Nous avons d'abord exécuté une instruction except, excluant (colonne de hachage)

select * from TableA
Except
Select * from TableB,

2) Ensuite, nous avons exécuté une comparaison de jointure gauche entre les deux tables sur le HashRowId

select * 
FROM dbo.TableA A
left join dbo.TableB B
    on A.RowHash =  B.RowHash
where B.Hash is null

étonnamment, l'insertion de déclaration Except était la plus rapide.

Les résultats sont proches des résultats des tests de David Lozinksi

Quel est l'algorithme interne du fonctionnement de l'opérateur Except sous les couvertures de SQL Server?

Je ne dirais pas qu'il existe un algorithme interne spécial pour EXCEPT. Pour A EXCEPT B, le moteur prend des tuples distincts (si nécessaire) de A et soustrait les lignes qui correspondent en B. Il n'y a pas d'opérateurs de plan de requête spéciaux. Le distinct et la soustraction sont implémentés via les opérateurs typiques que vous verriez avec un tri ou avec une jointure. La jointure par boucle imbriquée, la jointure par fusion et la jointure par hachage sont toutes prises en charge. Pour montrer cela, je jetterai 15 millions de rangées dans une paire de tas:

DROP TABLE IF EXISTS dbo.TABLE_1;

CREATE TABLE dbo.TABLE_1 (
    COL1 BIGINT NULL,
    COL2 BIGINT NULL
);

INSERT INTO dbo.TABLE_1 WITH (TABLOCK)
SELECT TOP (15000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), NULL
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);


DROP TABLE IF EXISTS dbo.TABLE_2;

CREATE TABLE dbo.TABLE_2 (
    COL1 BIGINT NULL,
    COL2 BIGINT NULL
);

INSERT INTO dbo.TABLE_2 WITH (TABLOCK)
SELECT TOP (15000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), NULL
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);

L'optimiseur prend les décisions habituelles basées sur les coûts sur la façon d'implémenter le tri et la jointure. Avec deux tas, j'obtiens une jointure de hachage comme prévu. Vous pouvez voir d'autres types de jointures naturellement en ajoutant des index ou en modifiant les données dans l'une ou l'autre table. Ci-dessous, je force les jointures de fusion et de boucle avec des conseils uniquement à des fins d'illustration:

Faut-il en interne un hachage de chaque ligne et comparer?

Non. Il est implémenté comme n'importe quelle autre jointure. Une différence est que les valeurs NULL sont traitées comme égales. C'est un type de comparaison que vous pouvez voir dans le plan d'exécution: <Compare CompareOp="IS">. Cependant, vous pouvez obtenir ce même plan avec T-SQL qui n'inclut pas le EXCEPTmot clé. Par exemple, ce qui suit a exactement le même plan de requête que la EXCEPTrequête qui utilise une jointure de hachage:

SELECT t1.*
FROM
(
    SELECT DISTINCT COL1, COL2
    FROM dbo.TABLE_1
) t1
WHERE NOT EXISTS (
    SELECT 1
    FROM dbo.TABLE_2 t2
    WHERE (t1.COL1 = t2.COL1 OR (t1.COL1 IS NULL AND t2.COL1 IS NULL))
    AND (t1.COL2 = t2.COL2 OR (t1.COL2 IS NULL AND t2.COL2 IS NULL))
);

La différence du XML des plans d'exécution ne révèle que des différences superficielles autour des alias et des choses comme ça. Les résidus de sonde pour les jointures de hachage font la comparaison de lignes. Ils sont identiques pour les deux requêtes:

Si vous avez encore des doutes, j'ai exécuté PerfView avec le taux d'échantillonnage le plus élevé disponible pour obtenir des piles d'appels pour la requête avec EXCEPTet la requête sans. Voici les résultats côte à côte:

Il n'y a pas vraiment de différence. Les piles d'appels de hachage de référence sont présentes en raison des correspondances de hachage dans le plan. Si j'ajoute des index pour obtenir une jointure de fusion naturelle, vous ne verrez aucune référence au hachage dans les piles d'appels:

Tout hachage qui se produit est dû à l'implémentation des opérateurs de correspondance de hachage. Il n'y a rien de spécial EXCEPTqui mène à une comparaison de hachage interne spéciale.