Cet article montre comment SQL Server combine les informations de densité de plusieurs statistiques à une seule colonne, pour produire une estimation de cardinalité pour une agrégation sur plusieurs colonnes. Les détails sont, espérons-le, intéressants en eux-mêmes. Ils donnent également un aperçu de certaines des approches générales et des algorithmes utilisés par l'estimateur de cardinalité.
Considérez l'exemple de requête de base de données AdventureWorks suivant, qui répertorie le nombre d'articles d'inventaire de produits dans chaque casier sur chaque étagère de l'entrepôt :
SELECT INV.Shelf, INV.Bin, COUNT_BIG(*) FROM Production.ProductInventory AS INV GROUP BY INV.Shelf, INV.Bin ORDER BY INV.Shelf, INV.Bin;
Le plan d'exécution estimé indique que 1 069 lignes sont lues à partir de la table, triées dans Shelf
et Bin
ordre, puis agrégé à l'aide d'un opérateur Stream Aggregate :
Plan d'exécution estimé
La question est, comment l'optimiseur de requête SQL Server est-il arrivé à l'estimation finale de 744 lignes ?
Statistiques disponibles
Lors de la compilation de la requête ci-dessus, l'optimiseur de requête créera des statistiques à une seule colonne sur le Shelf
et Bin
colonnes, si les statistiques appropriées n'existent pas déjà. Entre autres choses, ces statistiques fournissent des informations sur le nombre de valeurs de colonnes distinctes (dans le vecteur de densité) :
DBCC SHOW_STATISTICS ( [Production.ProductInventory], [Shelf] ) WITH DENSITY_VECTOR; DBCC SHOW_STATISTICS ( [Production.ProductInventory], [Bin] ) WITH DENSITY_VECTOR;
Les résultats sont résumés dans le tableau ci-dessous (la troisième colonne est calculée à partir de la densité) :
Colonne | Densité | 1 / Densité |
---|---|---|
Étagère | 0.04761905 | 21 |
Bac | 0.01612903 | 62 |
Informations vectorielles sur la densité des étagères et des bacs
Comme le note la documentation, l'inverse de la densité est le nombre de valeurs distinctes dans la colonne. D'après les informations statistiques présentées ci-dessus, SQL Server sait qu'il y avait 21 éléments Shelf
distincts. valeurs et 62 Bin
distincts valeurs dans le tableau, lorsque les statistiques ont été collectées.
La tâche d'estimation du nombre de lignes produites par un GROUP BY
La clause est triviale lorsqu'une seule colonne est impliquée (en supposant qu'il n'y a pas d'autres prédicats). Par exemple, il est facile de voir que GROUP BY Shelf
produira 21 rangées ; GROUP BY Bin
en produira 62.
Cependant, on ne sait pas immédiatement comment SQL Server peut estimer le nombre de (Shelf, Bin)
distincts combinaisons pour notre GROUP BY Shelf, Bin
requête. Pour poser la question d'une manière légèrement différente :étant donné 21 étagères et 62 bacs, combien y aura-t-il de combinaisons uniques d'étagères et de bacs ? Laissant de côté les aspects physiques et les autres connaissances humaines du domaine du problème, la réponse pourrait être n'importe où entre max(21, 62) =62 et (21 * 62) =1 302. Sans plus d'informations, il n'y a aucun moyen évident de savoir où présenter une estimation dans cette fourchette.
Pourtant, pour notre exemple de requête, SQL Server estime 744.312 lignes (arrondies à 744 dans la vue Plan Explorer) mais sur quelle base ?
Événement étendu d'estimation de cardinalité
La manière documentée d'examiner le processus d'estimation de la cardinalité consiste à utiliser l'événement étendu query_optimizer_estimate_cardinality
(bien qu'il soit dans le canal "debug"). Lorsqu'une session collectant cet événement est en cours d'exécution, les opérateurs de plan d'exécution obtiennent une propriété supplémentaire StatsCollectionId
qui relie les estimations individuelles des opérateurs aux calculs qui les ont produites. Pour notre exemple de requête, l'identifiant de collecte de statistiques 2 est lié à l'estimation de cardinalité pour le groupe par opérateur d'agrégation.
La sortie pertinente de l'événement étendu pour notre requête de test est :
<data name="calculator"> <type name="xml" package="package0"></type> <value> <CalculatorList> <DistinctCountCalculator CalculatorName="CDVCPlanLeaf" SingleColumnStat="Shelf,Bin" /> </CalculatorList> </value> </data> <data name="stats_collection"> <type name="xml" package="package0"></type> <value> <StatsCollection Name="CStCollGroupBy" Id="2" Card="744.31"> <LoadedStats> <StatsInfo DbId="6" ObjectId="258099960" StatsId="3" /> <StatsInfo DbId="6" ObjectId="258099960" StatsId="4" /> </LoadedStats> </StatsCollection> </value> </data>
Il y a certainement des informations utiles là-bas.
Nous pouvons voir que la classe de calculateur de valeurs distinctes de feuille de plan (CDVCPlanLeaf
) a été utilisé, en utilisant des statistiques à une seule colonne sur Shelf
et Bin
comme entrées. L'élément de collection stats fait correspondre ce fragment à l'id (2) indiqué dans le plan d'exécution, qui indique l'estimation de cardinalité de 744.31 , et plus d'informations sur les identifiants d'objets de statistiques utilisés également.
Malheureusement, rien dans la sortie de l'événement ne dit exactement comment la calculatrice est arrivée au chiffre final, ce qui nous intéresse vraiment.
Combiner des comptages distincts
En suivant un itinéraire moins documenté, nous pouvons demander un plan estimé pour la requête avec des indicateurs de trace 2363 et 3604 activé :
SELECT INV.Shelf, INV.Bin, COUNT_BIG(*) FROM Production.ProductInventory AS INV GROUP BY INV.Shelf, INV.Bin ORDER BY INV.Shelf, INV.Bin OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363);
Cela renvoie les informations de débogage à l'onglet Messages dans SQL Server Management Studio. La partie intéressante est reproduite ci-dessous :
Begin distinct values computation Input tree: LogOp_GbAgg OUT(QCOL: [INV].Shelf,QCOL: [INV].Bin,COL: Expr1001 ,) BY(QCOL: [INV].Shelf,QCOL: [INV].Bin,) CStCollBaseTable(ID=1, CARD=1069 TBL: Production.ProductInventory AS TBL: INV) AncOp_PrjList AncOp_PrjEl COL: Expr1001 ScaOp_AggFunc stopCountBig ScaOp_Const TI(int,ML=4) XVAR(int,Not Owned,Value=0) Plan for computation: CDVCPlanLeaf 0 Multi-Column Stats, 2 Single-Column Stats, 0 Guesses Loaded histogram for column QCOL: [INV].Shelf from stats with id 3 Loaded histogram for column QCOL: [INV].Bin from stats with id 4 Using ambient cardinality 1069 to combine distinct counts: 21 62 Combined distinct count: 744.312 Result of computation: 744.312 Stats collection generated: CStCollGroupBy(ID=2, CARD=744.312) CStCollBaseTable(ID=1, CARD=1069 TBL: Production.ProductInventory AS TBL: INV) End distinct values computation
Cela montre à peu près les mêmes informations que l'événement étendu dans un format (sans doute) plus facile à consommer :
- L'opérateur relationnel d'entrée pour calculer une estimation de cardinalité pour (
LogOp_GbAgg
– regroupement logique par agrégat) - Le calculateur utilisé (
CDVCPlanLeaf
) et les statistiques d'entrée - Les détails de la collecte de statistiques résultante
La nouvelle information intéressante est la partie sur l'utilisation de la cardinalité ambiante pour combiner des comptages distincts .
Cela montre clairement que les valeurs 21, 62 et 1069 ont été utilisées, mais (frustrant) toujours pas exactement quels calculs ont été effectués pour arriver au 744.312 résultat.
Au débogueur !
Attacher un débogueur et utiliser des symboles publics nous permet d'explorer en détail le chemin de code suivi lors de la compilation de l'exemple de requête.
L'instantané ci-dessous montre la partie supérieure de la pile d'appels à un point représentatif du processus :
MSVCR120!log sqllang!OdblNHlogN sqllang!CCardUtilSQL12::ProbSampleWithoutReplacement sqllang!CCardUtilSQL12::CardDistinctMunged sqllang!CCardUtilSQL12::CardDistinctCombined sqllang!CStCollAbstractLeaf::CardDistinctImpl sqllang!IStatsCollection::CardDistinct sqllang!CCardUtilSQL12::CardGroupByHelperCore sqllang!CCardUtilSQL12::PstcollGroupByHelper sqllang!CLogOp_GbAgg::PstcollDeriveCardinality sqllang!CCardFrameworkSQL12::DeriveCardinalityProperties
Il y a quelques détails intéressants ici. En travaillant de bas en haut, nous voyons que la cardinalité est dérivée à l'aide du CE mis à jour (CCardFrameworkSQL12
) disponible dans SQL Server 2014 et versions ultérieures (le CE d'origine est CCardFrameworkSQL7
), pour l'opérateur logique de regroupement par agrégat (CLogOp_GbAgg
).
Le calcul de la cardinalité distincte implique la combinaison (munging) de plusieurs entrées, en utilisant un échantillonnage sans remplacement.
La référence à H
et un logarithme (naturel) dans la deuxième méthode à partir du haut montre l'utilisation de l'entropie de Shannon dans le calcul :
Entropie de Shannon
L'entropie peut être utilisée pour estimer la corrélation informationnelle (information mutuelle) entre deux statistiques :
Informations mutuelles
En rassemblant tout cela, nous pouvons construire un script de calcul T-SQL correspondant à la façon dont SQL Server utilise l'échantillonnage sans remplacement, l'entropie de Shannon et les informations mutuelles pour produire l'estimation finale de la cardinalité.
Nous commençons par les nombres d'entrée (cardinalité ambiante et nombre de valeurs distinctes dans chaque colonne) :
DECLARE @Card float = 1069, @Distinct1 float = 21, @Distinct2 float = 62;
La fréquence de chaque colonne est le nombre moyen de lignes par valeur distincte :
DECLARE @Frequency1 float = @Card / @Distinct1, @Frequency2 float = @Card / @Distinct2;
L'échantillonnage sans remplacement (SWR) consiste simplement à soustraire le nombre moyen de lignes par valeur distincte (fréquence) du nombre total de lignes :
DECLARE @SWR1 float = @Card - @Frequency1, @SWR2 float = @Card - @Frequency2, @SWR3 float = @Card - @Frequency1 - @Frequency2;
Calculez les entropies (N log N) et les informations mutuelles :
DECLARE @E1 float = (@SWR1 + 0.5) * LOG(@SWR1), @E2 float = (@SWR2 + 0.5) * LOG(@SWR2), @E3 float = (@SWR3 + 0.5) * LOG(@SWR3), @E4 float = (@Card + 0.5) * LOG(@Card); -- Using logarithms allows us to express -- multiplication as addition and division as subtraction DECLARE @MI float = EXP(@E1 + @E2 - @E3 - @E4);
Maintenant que nous avons estimé à quel point les deux ensembles de statistiques sont corrélés, nous pouvons calculer l'estimation finale :
SELECT (1e0 - @MI) * @Distinct1 * @Distinct2;
Le résultat du calcul est 744,311823994677, soit 744,312 arrondi à trois décimales.
Pour plus de commodité, voici l'intégralité du code en un seul bloc :
DECLARE @Card float = 1069, @Distinct1 float = 21, @Distinct2 float = 62; DECLARE @Frequency1 float = @Card / @Distinct1, @Frequency2 float = @Card / @Distinct2; -- Sample without replacement DECLARE @SWR1 float = @Card - @Frequency1, @SWR2 float = @Card - @Frequency2, @SWR3 float = @Card - @Frequency1 - @Frequency2; -- Entropy DECLARE @E1 float = (@SWR1 + 0.5) * LOG(@SWR1), @E2 float = (@SWR2 + 0.5) * LOG(@SWR2), @E3 float = (@SWR3 + 0.5) * LOG(@SWR3), @E4 float = (@Card + 0.5) * LOG(@Card); -- Mutual information DECLARE @MI float = EXP(@E1 + @E2 - @E3 - @E4); -- Final estimate SELECT (1e0 - @MI) * @Distinct1 * @Distinct2;
Réflexions finales
L'estimation finale est imparfaite dans ce cas :l'exemple de requête renvoie en fait 441 lignes.
Pour obtenir une meilleure estimation, nous pourrions fournir à l'optimiseur de meilleures informations sur la densité du Bin
et Shelf
colonnes à l'aide d'une statistique multicolonne. Par exemple :
CREATE STATISTICS stat_Shelf_Bin ON Production.ProductInventory (Shelf, Bin);
Avec cette statistique en place (soit telle qu'elle est donnée, soit comme effet secondaire de l'ajout d'un index multicolonne similaire), l'estimation de cardinalité pour l'exemple de requête est tout à fait correcte. Il est cependant rare de calculer une agrégation aussi simple. Avec des prédicats supplémentaires, la statistique multicolonne peut être moins efficace. Néanmoins, il est important de se rappeler que les informations de densité supplémentaires fournies par les statistiques multicolonnes peuvent être utiles pour les agrégations (ainsi que les comparaisons d'égalité).
Sans statistique multicolonne, une requête agrégée avec des prédicats supplémentaires peut toujours être en mesure d'utiliser la logique essentielle présentée dans cet article. Par exemple, au lieu d'appliquer la formule à la cardinalité de la table, elle peut être appliquée aux histogrammes d'entrée étape par étape.
Contenu connexe :Estimation de la cardinalité d'un prédicat sur une expression COUNT