Estimation de cardinalité pour un prédicat sur une expression COUNT

Cet article examine l'estimation de la sélectivité et de la cardinalité pour les prédicats sur COUNT(*) expressions, comme on peut le voir dans HAVING clauses. 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é.

Un exemple simple utilisant l'exemple de base de données AdventureWorks :

SELECT A.City FROM Person.[Address] AS A GROUP BY A.City HAVING COUNT_BIG(*) =1 ;

Nous sommes intéressés à voir comment SQL Server dérive une estimation pour le prédicat sur l'expression de comptage dans le HAVING clause.

Bien sûr, le HAVING clause est juste du sucre de syntaxe. Nous aurions également pu écrire la requête à l'aide d'une table dérivée ou d'une expression de table commune :

-- Table dérivéeSELECT SQ1.CityFROM( SELECT A.City, Expr1001 =COUNT_BIG(*) FROM Person.[Address] AS A GROUP BY A.City) AS SQ1WHERE SQ1.Expr1001 =1; -- CTEWITH Groupé AS( SELECT A.City, Expr1001 =COUNT_BIG(*) FROM Person.[Address] AS A GROUP BY A.City)SELECT G.CityFROM Grouped AS GWHERE G.Expr1001 =1;

Les trois formulaires de requête produisent le même plan d'exécution, avec des valeurs de hachage de plan de requête identiques.

Le plan post-exécution (réel) montre une estimation parfaite pour l'agrégat ; cependant, l'estimation pour le HAVING le filtre de clause (ou équivalent, dans les autres formulaires de requête) est médiocre :

Statistiques sur la City fournit des informations précises sur le nombre de valeurs de ville distinctes :

DBCC SHOW_STATISTICS ([Person.Address], Ville) WITH DENSITY_VECTOR ;

La toute densité chiffre est l'inverse du nombre de valeurs uniques. Calculer simplement (1 / 0,00173913) =575 donne l'estimation de cardinalité pour l'agrégat. Le regroupement par ville produit évidemment une ligne pour chaque valeur distincte.

Notez que toute densité vient du vecteur densité. Veillez à ne pas utiliser accidentellement la densité valeur de la sortie d'en-tête de statistiques de DBCC SHOW_STATISTICS . La densité d'en-tête est conservée uniquement pour la compatibilité ascendante ; il n'est pas utilisé par l'optimiseur lors de l'estimation de la cardinalité de nos jours.

Le problème

L'agrégat introduit une nouvelle colonne calculée dans le workflow, intitulée Expr1001 dans le plan d'exécution. Il contient la valeur de COUNT(*) dans chaque ligne de sortie groupée :

Il n'y a évidemment aucune information statistique dans la base de données concernant cette nouvelle colonne calculée. Alors que l'optimiseur sait qu'il y aura 575 lignes, il ne sait rien de la distribution de valeurs de comptage dans ces lignes.

Eh bien pas tout à fait rien :L'optimiseur est conscient que les valeurs de comptage seront des entiers positifs (1, 2, 3…). Pourtant, c'est la distribution de ces valeurs de nombre entier parmi les 575 lignes qui serait nécessaire pour estimer avec précision la sélectivité du COUNT(*) = 1 prédicat.

On pourrait penser qu'une sorte d'informations de distribution pourrait être dérivée de l'histogramme, mais l'histogramme ne fournit que des informations de comptage spécifiques (dans EQ_ROWS ) pour les valeurs de pas d'histogramme. Entre les étapes de l'histogramme, tout ce que nous avons est un résumé :RANGE_ROWS les lignes ont DISTINCT_RANGE_ROWS valeurs distinctes. Pour les tableaux suffisamment volumineux pour que nous nous soucions de la qualité de l'estimation de la sélectivité, il est très probable que la majeure partie du tableau soit représentée par ces résumés intra-étapes.

Par exemple, les deux premières lignes de la City l'histogramme des colonnes sont :

DBCC SHOW_STATISTICS ([Person.Address], Ville) AVEC HISTOGRAM ;

Cela nous indique qu'il y a exactement une ligne pour "Abingdon", et 29 autres lignes après "Abingdon" mais avant "Ballard", avec 19 valeurs distinctes dans cette plage de 29 lignes. La requête suivante montre la distribution réelle des lignes parmi les valeurs uniques dans cette plage intra-étape de 29 lignes :

SELECT A.City, NumRows =COUNT_BIG(*)FROM Person.[Address] AS A WHERE A.City> N'Abingdon' AND A.City  

 
 

 Il y a 29 lignes avec 19 valeurs distinctes, comme le dit l'histogramme. Pourtant, il est clair que nous n'avons aucune base pour évaluer la sélectivité d'un prédicat sur la colonne de comptage dans cette requête. Par exemple, HAVING COUNT_BIG(*) = 2 renverrait 5 lignes (pour Alexandrie, Altadena, Atlanta, Augsbourg et Austin) mais nous n'avons aucun moyen de le déterminer à partir de l'histogramme.
 
Une supposition éclairée
 

 L'approche adoptée par SQL Server consiste à supposer que chaque groupe est le plus probable pour contenir le nombre moyen global (moyen) de lignes. Il s'agit simplement de la cardinalité divisée par le nombre de valeurs uniques. Par exemple, pour 1000 lignes avec 20 valeurs uniques, SQL Server supposerait que (1000/20) =50 lignes par groupe est la valeur la plus probable.
 

 Pour en revenir à notre exemple d'origine, cela signifie que la colonne de comptage calculée est "la plus susceptible" de contenir une valeur autour de (19614/575) ~=34.1113 . Depuis la densité est l'inverse du nombre de valeurs uniques, nous pouvons également l'exprimer sous la forme de cardinalité * densité =(19614 * 0.00173913), donnant un résultat très similaire.
 
Répartition
 

 Dire que la valeur moyenne est très probablement ne nous emmène que très loin. Nous devons également établir exactement dans quelle mesure cela est probable ; et comment la probabilité change à mesure que nous nous éloignons de la valeur moyenne. Supposer que tous les groupes ont exactement 34 113 lignes dans notre exemple ne serait pas une supposition très "instruite" !
 

 SQL Server gère cela en supposant une distribution normale. Cela a la forme de cloche caractéristique que vous connaissez peut-être déjà (image de l'entrée Wikipédia liée):
 

 
 

 La forme exacte de la distribution normale dépend de deux paramètres :la moyenne (µ ) et l'écart type (σ ). La moyenne détermine l'emplacement du pic. L'écart type spécifie à quel point la courbe en cloche est "aplatie". Plus la courbe est plate, plus le pic est bas et plus la densité de probabilité est répartie sur d'autres valeurs.
 

 SQL Server peut dériver la moyenne à partir d'informations statistiques, comme indiqué précédemment. L'écart type des valeurs de colonne de comptage calculées est inconnue. SQL Server l'estime comme la racine carrée de la moyenne (avec un léger ajustement détaillé plus loin). Dans notre exemple, cela signifie que les deux paramètres de la distribution normale sont approximativement 34,1113 et 5,84 (la racine carrée).
 

 La norme la distribution normale (la courbe rouge dans le diagramme ci-dessus) est un cas particulier remarquable. Cela se produit lorsque la moyenne est de zéro et que l'écart type est de 1. Toute distribution normale peut être transformée en distribution normale standard en soustrayant la moyenne et en divisant par l'écart type.
 
Zones et intervalles
 

 Nous sommes intéressés par l'estimation de la sélectivité, nous recherchons donc la probabilité que la colonne calculée par le nombre ait une certaine valeur (x). Cette probabilité n'est pas donnée par la valeur de l'axe des ordonnées ci-dessus, mais par la aire sous la courbe à gauche de x.
 

 Pour la distribution normale avec une moyenne de 34,1113 et un écart type de 5,84, l'aire sous la courbe à gauche de x =30 est d'environ 0,2406 :
 

 
 

 Cela correspond à la probabilité que la colonne de comptage calculée soit inférieure ou égale à 30 pour notre exemple de requête.
 

 Cela conduit bien à l'idée qu'en général, nous ne recherchons pas la probabilité d'une valeur spécifique, mais un intervalle . Pour trouver la probabilité que le nombre est égal une valeur entière, nous devons tenir compte du fait que les entiers couvrent un intervalle de taille 1. La façon dont nous convertissons un entier en intervalle est quelque peu arbitraire. SQL Server gère cela en ajoutant et en soustrayant 0,5 pour donner les bornes inférieure et supérieure de l'intervalle.
 

 Par exemple, pour trouver la probabilité que la valeur de comptage calculée soit égale à 30, nous devons soustraire l'aire sous la courbe de distribution normale pour (x =29,5) à partir de l'aire pour (x =30,5). Le résultat correspond à la tranche pour (29,5  

 
 

 L'aire de la tranche rouge est d'environ 0,0533 . En bonne première approximation, il s'agit de la sélectivité d'un prédicat count =30 dans notre requête de test.
 
La fonction de distribution cumulée
 

 Le calcul de l'aire sous une distribution normale à gauche d'une valeur donnée n'est pas simple. La formule générale est donnée par la fonction de distribution cumulative (CDF). Le problème est que la CDF ne peut pas être exprimée en termes de fonctions mathématiques élémentaires, donc des méthodes d'approximation numérique doivent être utilisées à la place.
 

 Étant donné que toutes les distributions normales peuvent être facilement transformées en distribution normale standard (moyenne =0, écart type =1), les approximations fonctionnent toutes pour estimer la normale standard. Cela signifie que nous devons transformer nos limites d'intervalle de la distribution normale particulière appropriée à la requête, à la distribution normale standard. Cela se fait, comme mentionné précédemment, en soustrayant la moyenne et en divisant par l'écart type.
 

 Si vous êtes familier avec Excel, vous connaissez peut-être les fonctions NORM.DIST et NORM.S.DIST qui peuvent calculer les CDF (en utilisant des méthodes d'approximation numérique) pour une distribution normale particulière ou la distribution normale standard.
 

 Il n'y a pas de calculateur CDF intégré à SQL Server, mais nous pouvons facilement en créer un. Sachant que la CDF pour la distribution normale standard est :
 

 
 

 …où erf est la fonction d'erreur :
 

 
 

 Une implémentation T-SQL pour obtenir le CDF pour la distribution normale standard est présentée ci-dessous. Il utilise une approximation numérique pour la fonction d'erreur qui est très proche de celui que SQL Server utilise en interne :
 
CREATE PROCEDURE dbo.GetStandardNormalCDF( @x float, @cdf float OUTPUT)ASBEGIN SET NOCOUNT, XACT_ABORT ON ; DECLARE @sign float, @erf float ; SET @sign =SIGN(@x); SET @x =ABS(@x) / SQRT(2); SET @erf =1 ; SET @erf =@erf + (0.0705230784 * @x); SET @erf =@erf + (0.0422820123 * PUISSANCE(@x, 2)); SET @erf =@erf + (0.0092705272 * PUISSANCE(@x, 3)); SET @erf =@erf + (0.0001520143 * PUISSANCE(@x, 4)); SET @erf =@erf + (0.0002765672 * PUISSANCE(@x, 5)); SET @erf =@erf + (0.0000430638 * PUISSANCE(@x, 6)); SET @erf =PUISSANCE(@erf, -16); SET @erf =1 - @erf ; SET @erf =@erf * @sign ; SET @cdf =0.5 * (1 + @erf);END;
 

 Un exemple, pour calculer le CDF pour x =30 en utilisant la distribution normale pour notre requête de test :
 
DECLARE @cdf float;DECLARE @x float;-- HAVING COUNT_BIG(*) =xSET @x =30;-- Normaliser 30 en soustrayant la moyenne-- et en divisant par l'écart typeSET @x =(@x - 34.1113) / 5.84;EXECUTE dbo.GetStandardNormalCDF @x =@x, @cdf =@cdf OUTPUT;SELECT CDF =@cdf;
 

 Notez l'étape de normalisation pour convertir en distribution normale standard. La procédure renvoie la valeur 0,2407196…, qui correspond au résultat Excel correspondant à sept décimales.
 
Derniers détails et exemples
 

 Le code suivant modifie notre exemple de requête pour produire une estimation plus grande pour le filtre (la comparaison est maintenant avec la valeur 32, qui est beaucoup plus proche de la moyenne qu'auparavant) :
 
SELECT A.CityFROM Person.[Address] AS GROUP BY A.CityHAVING COUNT_BIG(*) =32 ;
 

 
 

 L'estimation de l'optimiseur est désormais 36,7807 .
 

 Pour calculer l'estimation manuellement, nous devons d'abord régler quelques derniers détails :
 
 
La moyenne utilisée pour dériver l'écart type (via la racine carrée) est mise à l'échelle par un facteur de ((valeurs distinctes - 1) / (valeurs distinctes) . Dans l'exemple, le nombre de valeurs distinctes est de 575, donc le facteur d'échelle est (574/575) ~=0,99826. 
Si la limite inférieure de l'intervalle (entier) est 1, SQL Server traite l'intervalle comme illimité sur le côté inférieur. La sélectivité est égale à la CDF de la borne supérieure de l'intervalle (1,5) seul. La borne inférieure (qui serait de 0,5) n'est pas utilisée. 
L'ancien estimateur de cardinalité (CE) a une logique complexe pour COUNT(*) = 1 , qui n'est pas détaillé ici. 
En dehors du COUNT(*) = 1 Dans ce cas, l'ancien CE utilise la même logique que le nouveau CE (disponible dans SQL Server 2014 et versions ultérieures).
 
 

 La procédure suivante intègre tous les détails de cet article. Il nécessite la procédure CDF donnée précédemment :
 
CREATE PROCEDURE dbo.GetCountPredicateEstimate( @From integer, @To integer, @Cardinality float, @Density float, @Selectivity float OUTPUT, @Estimate float OUTPUT)ASBEGIN SET NOCOUNT, XACT_ABORT ON ; BEGIN TRY DECLARE @Start float, @End float, @Distinct float, @Mean float, @MeanAdj float, @Stdev float, @NormStart float, @NormEnd float, @CDFStart float, @CDFEnd float ; -- Valider l'entrée et appliquer les valeurs par défaut IF ISNULL(@From, 0) =0 SET @From =1; IF @From <1 RAISERROR ('@From doit être>=1', 16, 1); IF ISNULL(@Cardinality, -1) <=0 RAISERROR('@Cardiality doit être positif', 16, 1); IF ISNULL(@Density, -1) <=0 RAISERROR('@Density must be positive', 16, 1); IF ISNULL(@To, 0) =0 SET @To =PLAFOND(1 / @Densité); IF @To <@From RAISERROR('@To doit être>=@From', 16, 1); -- Convertir une plage d'entiers en intervalle SET @Start =@From - 0.5 ; SET @Fin =@To + 0.5 ; -- Obtenir le nombre de valeurs distinctes SET @Distinct =1 / @Density ; -- Calculer la moyenne SET @Mean =@Cardinality * @Density ; -- Ajuster la moyenne ; SET @MeanAdj =@Mean * ((@Distinct - 1) / @Distinct); -- Obtenir l'écart type (estimation) SET @Stdev =SQRT(@MeanAdj); -- Normaliser l'intervalle SET @NormStart =(@Start - @Mean) / @Stdev ; SET @NormEnd =(@End - @Mean) / @Stdev ; -- Calculer les CDF EXECUTE dbo.GetStandardNormalCDF @x =@NormStart, @cdf =@CDFStart OUTPUT; EXÉCUTER dbo.GetStandardNormalCDF @x =@NormEnd, @cdf =@CDFEnd SORTIE ; -- Sélectivité SET @Selectivity =CASE -- Début illimité QUAND @From =1 ALORS @CDFEnd -- Fin illimité QUAND @To>=@Distinct ALORS 1 - @CDFStart -- Intervalle normal SINON @CDFEnd - @CDFStart FIN ; -- Renvoie l'estimation de ligne SET @Estimate =@Selectivity * @Distinct; END TRY BEGIN CATCH DECLARE @EM nvarchar(4000) =ERROR_MESSAGE(); SI @@TRANCOUNT> 0 ROLLBACK TRANSACTION ; RAISERROR (@EM, 16, 1); RETOURNER; END CATCH;END;
 

 Nous pouvons maintenant utiliser cette procédure pour générer une estimation pour notre nouvelle requête de test :
 
DECLARE @Selectivity float, @Estimate float;EXECUTE dbo.GetCountPredicateEstimate @From =32, @To =32, @Cardinality =19614, @Density =0.00173913, @Selectivity =@Selectivity OUTPUT, @Estimate =@Estimate OUTPUT ; SELECT Sélectivité =@Sélectivité, Estimation =@Estimation, Arrondi =ARRONDI(@Estimation, 4);
 

 La sortie est :
 

 
 

 Cela se compare très bien à l'estimation de cardinalité de l'optimiseur de 36,7807. 
 
Exemples d'intervalles d'inégalité
 

 La procédure peut être utilisée pour d'autres intervalles de comptage en dehors des tests d'égalité. Il suffit de définir le @From et @To paramètres aux limites de l'intervalle entier. Pour spécifier unbounded, passez zéro ou NULL comme vous préférez.
 
SELECT A.CityFROM Person.[Address] AS GROUP BY A.CityHAVING COUNT_BIG(*) <50 ;
 

 
 

 Pour l'utiliser avec notre procédure, nous définissons @From = NULL et @To = 49 (parce que 50 est exclu par moins de):
 
DECLARE @Selectivity float, @Estimate float;EXECUTE dbo.GetCountPredicateEstimate @From =NULL, @To =49, @Cardinality =19614, @Density =0.00173913, @Selectivity =@Selectivity OUTPUT, @Estimate =@Estimate OUTPUT ; SELECT Sélectivité =@Sélectivité, Estimation =@Estimation, Arrondi =ARRONDI(@Estimation, 4);
 

 Le résultat est 572,5964 :
 

 
 

 Un dernier exemple utilisant BETWEEN :
 
SELECT A.CityFROM Person.[Address] AS GROUP BY A.CityHAVING COUNT_BIG(*) BETWEEN 25 AND 30 ;
 

 L'estimation de l'optimiseur est 
 

 
 

 Depuis BETWEEN est inclusif, on passe la procédure @From = 25 et @To = 30 . Le résultat est :
 

 
 

 Là encore, cela correspond à l'estimation de l'optimiseur.