Comment l'optimiseur de SQL Server estime-t-il le nombre de lignes dans une table jointe?

J'exécute cette requête dans la base de données AdventureWorks2012 :

SELECT 
    s.SalesOrderID,
    d.CarrierTrackingNumber,
    d.ProductID,
    d.OrderQty
FROM Sales.SalesOrderHeader s 
JOIN Sales.SalesOrderDetail d 
    ON s.SalesOrderID = d.SalesOrderID
WHERE s.CustomerID = 11077

Si je regarde le plan d'exécution estimé, je vois ce qui suit:

La recherche d'index initiale (en haut à droite) utilise l'index IX_SalesOrderHeader_CustomerID et effectue une recherche sur le littéral 11077. Elle a une estimation de 2,6192 lignes.

Si j'utilise DBCC SHOW_STATISTICS ('Sales.SalesOrderHeader', 'IX_SalesOrderHeader_CustomerID') WITH HISTOGRAM, cela montre que la valeur 11077 se situe entre les deux clés échantillonnées 11019 et 11091.

Le nombre moyen de lignes distinctes entre 11019 et 11091 est de 2,619718, ou arrondi à 2,61972, qui est la valeur des lignes estimées indiquées pour la recherche d'index.

La partie que je ne comprends pas est le nombre estimé de lignes pour la recherche d'index cluster par rapport à la table SalesOrderDetail.

Si je cours DBCC SHOW_STATISTICS ('Sales.SalesOrderDetail', 'PK_SalesOrderDetail_SalesOrderID_SalesOrderDetailID'):

La densité de SalesOrderID (sur laquelle je me joins) est donc de 3.178134E-05. Cela signifie que 1 / 3.178134E-05 (31465) est égal au nombre de valeurs SalesOrderID uniques dans la table SalesOrderDetail.

S'il y a 31465 SalesOrderID uniques dans SalesOrderDetail, alors avec une distribution paire, le nombre moyen de lignes par SalesOrderID est 121317 (nombre total de lignes) divisé par 31465. La moyenne est de 3 85561.

Donc, si le nombre estimé de lignes à parcourir est de 2,61972, et la moyenne à renvoyer dans 3.85561, le je pense que le nombre estimé de lignes serait 2.61972 * 3.85561 = 10.10062.

Mais le nombre estimé de lignes est de 11,4867.

Je pense que ma compréhension de la deuxième estimation est incorrecte et les chiffres différents semblent l'indiquer. Qu'est-ce que je rate?

Je pense que ma compréhension de la deuxième estimation est incorrecte et les chiffres différents semblent l'indiquer. Qu'est-ce que je rate?

À l'aide de l'estimateur de cardinalité SQL Server 2012, la sélectivité de la jointure détermine le nombre estimé de lignes sur le côté intérieur de la jointure de boucles imbriquées, et non l'inverse.

Le nombre 11.4867 est dérivé (pour affichage dans showplan) en divisant la cardinalité estimée calculée de la sortie de jointure (30.0919) par le nombre d'itérations (2.61972). Le résultat, en utilisant l'arithmétique à virgule flottante simple précision, est 11,4867 .

C'est aussi simple que ça. Notez que la sélectivité de jointure (logique) est indépendante du choix de l'opérateur de jointure physique. Il reste le même que la jointure soit finalement effectuée à l'aide d'un opérateur physique Nested Loops, Hash ou Merge Join.

Dans SQL Server 2012 et versions antérieures, la sélectivité de jointure (dans son ensemble) est estimée à l'aide des SalesOrderIDhistogrammes de chaque table (calculée pour chaque étape de l'histogramme, après l'alignement des limites de l'étape en utilisant une interpolation linéaire si nécessaire). L' SalesOrderIDhistogramme associé au SalesOrderHeadertableau est également ajusté pour l'effet de mise à l'échelle du CustomerIDfiltre indépendant .

Cela ne veut pas dire qu'il y a quelque chose de fondamentalement «mauvais» dans le calcul alternatif proposé dans la question; il fait simplement un ensemble différent d'hypothèses. Il y aura toujours différentes façons de calculer ou de combiner des estimations pour une séquence donnée d'opérations logiques. Il n'y a aucune garantie générale que différentes méthodes statistiques appliquées aux mêmes données produiront les mêmes réponses, ou qu'une méthode serait toujours supérieure à l'autre. Des incohérences résultant de l'application de différentes méthodes statistiques peuvent même apparaître dans un même plan d'exécution final, même si elles sont rarement constatées.

En guise de remarque, l'estimateur de cardinalité SQL Server 2014 adopte une approche différente pour combiner les informations d'histogramme ajustées par filtre indépendant ( "alignement grossier" ), ce qui se traduit par une estimation finale différente de 10 10000 lignes pour cette requête:

Plan for computation:

  CSelCalcExpressionComparedToExpression
  (QCOL: [s].SalesOrderID x_cmpEq QCOL: [d].SalesOrderID)

Loaded histogram for column QCOL: [s].SalesOrderID from stats with id 1
Loaded histogram for column QCOL: [d].SalesOrderID from stats with id 1

Stats collection generated: 

  CStCollJoin(ID=4, **CARD=10.1006** x_jtInner)
      CStCollFilter(ID=3, CARD=2.61972)
          CStCollBaseTable(ID=1, CARD=31465 TBL: Sales.SalesOrderHeader AS TBL: s)
      CStCollBaseTable(ID=2, CARD=121317 TBL: Sales.SalesOrderDetail AS TBL: d)

Cela se trouve être le même résultat que le calcul de la question, bien que le raisonnement détaillé soit différent (c'est-à-dire qu'il ne soit pas basé sur une implémentation supposée de boucles imbriquées).