Problème d'estimation de cardinalité sur la jointure interne

J'ai du mal à comprendre pourquoi l'estimation des lignes est si terriblement erronée, voici mon cas:

Jointure simple - en utilisant SQL Server 2016 sp2 (même problème sur sp1), dbcompatiblity = 130.

select Amount_TransactionCurrency_id, CurrencyShareds.id 
from CurrencyShareds 
    INNER JOIN annexes ON Amount_TransactionCurrency_id = CurrencyShareds.Id 
option (QUERYTRACEON 3604, QUERYTRACEON 2363);

SQL estime 1 ligne, alors que c'est 107131 et choisit de faire une boucle imbriquée ( lien vers le plan ). Une fois les statistiques mises à jour sur CurrencyShareds, l'estimation est correcte et une jointure de fusion est choisie ( lien vers le nouveau plan ). Dès qu'un seul enregistrement est ajouté à CurrencyShareds, les statistiques deviennent "périmées" et sql revient à une mauvaise estimation.

Je ne m'inquiéterais pas beaucoup de cette simple requête, mais ce n'est qu'une partie d'une plus grande, et c'est le début d'un domino ...

Pourquoi l'ajout d'une ligne à la table de 100 enregistrements provoque un tel dommage? Lorsque je regarde la sortie de la trace d'estimation de cardinalité, je vois cet avertissement ***WARNING: badly-formed histogram ***mais je n'ai rien trouvé de plus sur ce sujet.

Voici la sortie complète de l'estimation de cardinalité:

Begin selectivity computation
Input tree:

LogOp_Join

CStCollBaseTable(ID=1, CARD=107131 TBL: annexes)

CStCollBaseTable(ID=2, CARD=100 TBL: CurrencyShareds)

ScaOp_Comp x_cmpEq

ScaOp_Identifier QCOL: [test.MasterData].[dbo].[CurrencyShareds].Id

ScaOp_Identifier QCOL: [test.MasterData].[dbo].[Annexes].Amount_TransactionCurrency_id

Plan for computation:

CSelCalcExpressionComparedToExpression( QCOL: [test.MasterData].[dbo].[Annexes].Amount_TransactionCurrency_id x_cmpEq QCOL: [test.MasterData].[dbo].[CurrencyShareds].Id )

Loaded histogram for column QCOL: [test.MasterData].[dbo].[Annexes].Amount_TransactionCurrency_id from stats with id 7

Loaded histogram for column QCOL: [test.MasterData].[dbo].[CurrencyShareds].Id from stats with id 1 *** WARNING: badly-formed histogram ***

Selectivity: 4.59503e-018

Stats collection generated:

CStCollJoin(ID=3, CARD=1 x_jtInner)

CStCollBaseTable(ID=1, CARD=107131 TBL: annexes)

CStCollBaseTable(ID=2, CARD=100 TBL: CurrencyShareds)

End selectivity computation

Estimating distinct count in utility function

Input stats collection:

CStCollBaseTable(ID=1, CARD=107131 TBL: annexes)

Columns to distinct on:QCOL: [test.MasterData].[dbo].[Annexes].Amount_TransactionCurrency_id

Plan for computation:

CDVCPlanLeaf

0 Multi-Column Stats, 1 Single-Column Stats, 0 Guesses

Covering multi-col stats id: 7

Using ambient cardinality 107131 to combine distinct counts:

5

Combined distinct count: 5

Result of computation: 5

Estimating distinct count in utility function

Input stats collection:

CStCollBaseTable(ID=2, CARD=100 TBL: CurrencyShareds)

Columns to distinct on:QCOL: [test.MasterData].[dbo].[CurrencyShareds].Id

Plan for computation:

CDVCPlanUniqueKey

Result of computation: 100

Et quand je mets à jour les statistiques sur CurrencyShareds, la partie avec les changements d'histogramme mal formés et la cardinalité est calculée correctement

Plan for computation:

CSelCalcExpressionComparedToExpression( QCOL: [test.MasterData].[dbo].[Annexes].Amount_TransactionCurrency_id x_cmpEq QCOL: [test.MasterData].[dbo].[CurrencyShareds].Id )

Loaded histogram for column QCOL: [test.MasterData].[dbo].[Annexes].Amount_TransactionCurrency_id from stats with id 7

Loaded histogram for column QCOL: [test.MasterData].[dbo].[CurrencyShareds].Id from stats with id 1

Selectivity: 0.01

Stats collection generated:

CStCollJoin(ID=3, CARD=107131 x_jtInner)

CStCollBaseTable(ID=1, CARD=107131 TBL: annexes)

CStCollBaseTable(ID=2, CARD=100 TBL: CurrencyShareds)

End selectivity computation

Et des informations sur les statistiques pour ce "[CurrencyShareds] .Id à partir des statistiques avec l'ID 1" avec un avertissement sur l'histogramme, qui me semble bien ...

Name                                                                                                                             Updated              Rows                 Rows Sampled         Steps  Density       Average key length String Index Filter Expression                                                                                                                                                                                                                                                Unfiltered Rows      Persisted Sample Percent
-------------------------------------------------------------------------------------------------------------------------------- -------------------- -------------------- -------------------- ------ ------------- ------------------ ------------ ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------- ------------------------
PK_CurrencyShareds_Id                                                                                                            May 23 2018 10:43PM  98                   98                   75     1             8                  NO           NULL                                                                                                                                                                                                                                                             98                   0

(1 row affected)

All density   Average Length Columns
------------- -------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
0,01020408    8              Id

(1 row affected)

RANGE_HI_KEY         RANGE_ROWS    EQ_ROWS       DISTINCT_RANGE_ROWS  AVG_RANGE_ROWS
-------------------- ------------- ------------- -------------------- --------------
119762190797406464   0             1             0                    1
119762190797406466   1             1             1                    1
119762190797406468   1             1             1                    1
119762190797406470   1             1             1                    1
119762190797406472   1             1             1                    1
119762190797406474   1             1             1                    1
119762190797406476   1             1             1                    1
119762190797406478   1             1             1                    1
119762190797406480   1             1             1                    1
119762190797406482   1             1             1                    1
119762190797406484   1             1             1                    1
119762190797406486   1             1             1                    1
119762190797406488   1             1             1                    1
119762190797406490   1             1             1                    1
119762190797406492   1             1             1                    1
119762190797406494   1             1             1                    1
119762190797406496   1             1             1                    1
119762190797406498   1             1             1                    1
119762190797406500   1             1             1                    1
119762190797406502   1             1             1                    1
119762190797406504   1             1             1                    1
119762190797406506   1             1             1                    1
119762190797406507   0             1             0                    1
478531702587687680   0             1             0                    1
478531702591881728   0             1             0                    1
478531702591881729   0             1             0                    1
478531702591881984   0             1             0                    1
478531702591881985   0             1             0                    1
478531702596076032   0             1             0                    1
478531702596076033   0             1             0                    1
478531702596076288   0             1             0                    1
478531702600270336   0             1             0                    1
478531702600270592   0             1             0                    1
478532235583062528   0             1             0                    1
478532235583062784   0             1             0                    1
478532235587256832   0             1             0                    1
530792464911467264   0             1             0                    1
530792464924049920   0             1             0                    1
530792464924050176   0             1             0                    1
530792464928244224   0             1             0                    1
530792464928244480   0             1             0                    1
530792464932438528   0             1             0                    1
530792464932438784   0             1             0                    1
530792464936632832   0             1             0                    1
530792464936632833   0             1             0                    1
530792464936633088   0             1             0                    1
530792464940827136   0             1             0                    1
530792464940827392   0             1             0                    1
530792464949216000   2             1             2                    1
530792464953410048   0             1             0                    1
530792464953410304   0             1             0                    1
530792464957604352   0             1             0                    1
530792464957604353   0             1             0                    1
530792464957604608   0             1             0                    1
530792464961798656   0             1             0                    1
530792464961798912   0             1             0                    1
530792464965992960   0             1             0                    1
530792464965993216   0             1             0                    1
530792464965993217   0             1             0                    1
530792464970187264   0             1             0                    1
530792464970187265   0             1             0                    1
530792464970187520   0             1             0                    1
530792464974381568   0             1             0                    1
530792464974381824   0             1             0                    1
530792464974381825   0             1             0                    1
530792464978575872   0             1             0                    1
530792464978575873   0             1             0                    1
530792464978576128   0             1             0                    1
867420708903354880   0             1             0                    1
867420708903355136   0             1             0                    1
867420708903355137   0             1             0                    1
960876568220042240   0             1             0                    1
976385263448130048   0             1             0                    1
977302121709864192   0             1             0                    1
977955748426318592   0             1             0                    1

et info pour le deuxième index:

Name                                                                                                                             Updated              Rows                 Rows Sampled         Steps  Density       Average key length String Index Filter Expression                                                                                                                                                                                                                                                Unfiltered Rows      Persisted Sample Percent
-------------------------------------------------------------------------------------------------------------------------------- -------------------- -------------------- -------------------- ------ ------------- ------------------ ------------ ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------- ------------------------
IX_FK_Amount_TransactionCurrency                                                                                                 May 21 2018  3:29PM  107204               107204               5      0             16                 NO           NULL                                                                                                                                                                                                                                                             107204               0

(1 row affected)

All density   Average Length Columns
------------- -------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
0,2           8              Amount_TransactionCurrency_id
9,32801E-06   16             Amount_TransactionCurrency_id, Id

(2 rows affected)

RANGE_HI_KEY         RANGE_ROWS    EQ_ROWS       DISTINCT_RANGE_ROWS  AVG_RANGE_ROWS
-------------------- ------------- ------------- -------------------- --------------
119762190797406475   0             160           0                    1
119762190797406478   0             867           0                    1
119762190797406481   0             106           0                    1
119762190797406494   0             105742        0                    1
119762190797406496   0             329           0                    1

sql-server query-performance sql-server-2016 cardinality-estimates LeMaciek
la source

Réponses:

Sur la base de vos histogrammes, j'ai pu reprocher le problème en 2017 CU6. Je ne dirais pas que tu fais quelque chose de mal. Au contraire, quelque chose ne va pas avec l'estimation de la cardinalité. Voici ce que j'obtiens avant d'insérer une ligne:

L'estimation finale de la cardinalité diminue un peu après l'insertion d'une ligne:

Vous avez une repro assez simple ici, donc mon conseil est de déposer des commentaires sur les produits ou d'ouvrir un ticket de support avec Microsoft. J'ai pu trouver quelques solutions de contournement qui ont fonctionné sur vos exemples de données et l'une des solutions pourrait être acceptable pour vous.

Déposez l'index unique sur CurrencyShareds.Id. Je ne peux pas faire fonctionner la repro sans un index unique. Le tableau est petit, donc vous pouvez peut-être vous en tirer sans l'index. Bien sûr, vous pourriez avoir de très bonnes raisons de le conserver.
Matérialisez les résultats de la jointure dans une table temporaire. Sur la base de votre question, il est important d'obtenir une estimation raisonnable à cette étape pour que la requête plus volumineuse fonctionne bien. Une table temporaire est un moyen d'y parvenir.
Utilisez l'héritage CE. Je n'arrive pas à reproduire le problème avec. Bien sûr, cela pourrait avoir des conséquences négatives sur le reste de votre requête.
Tromper l'optimiseur de requête avec un code stupide. Par exemple, lors de mes tests, la réécriture suivante fonctionne très bien:

select Amount_TransactionCurrency_id, CurrencyShareds.id
from CurrencyShareds 
INNER JOIN annexes
ON Amount_TransactionCurrency_id % 9223372036854775809 = CurrencyShareds.Id % 9223372036854775809

Je soupçonne que cela fonctionne parce que le CE semble utiliser la densité au lieu de l'histogramme. D'autres réécritures similaires peuvent avoir le même effet. Il n'y a aucune garantie que le type de requête continuera de bien fonctionner à l'avenir. C'est pourquoi vous devez contacter Microsoft pour améliorer les chances qu'un jour un correctif de votre problème se transforme en produit commercialisé.

Joe Obbish
la source

Ok, j'espère que je le comprends maintenant - donc c'est notre cas

Donné

Une table de référence (CurrencyShareds) avec environ 100 lignes, mais les identifiants sont grands et les valeurs min et max diffèrent beaucoup - min: 119,762,190,797,406,464 vs max: 977,955,748,426,318,592
Un tableau (Annexes) qui a FK simple vers CurrencyShared, mais seules quelques devises sont utilisées - vous pouvez voir que l'histogramme pour IX_FK_Amount_TransactionCurrency répertorie 5 identifiants - et ce qui est important uniquement ces identifiants "faibles", car d'autres ne sont pas utilisés.

Lorsque toutes les statistiques sont à jour,

CSelCalcExpressionComparedToExpression( QCOL: [test.MasterData].[dbo].[Annexes].Amount_TransactionCurrency_id x_cmpEq QCOL: [test.MasterData].[dbo].[CurrencyShareds].Id )

Loaded histogram for column QCOL: [test.MasterData].[dbo].[Annexes].Amount_TransactionCurrency_id from stats with id 7

Loaded histogram for column QCOL: [test.MasterData].[dbo].[CurrencyShareds].Id from stats with id 1

Selectivity: 0.01

Ensuite, la sélectivité calculée pour la jointure est correcte, car 100 * 107,131 * 0,01 = 107,131

Lorsque les statistiques de partage de courant ne sont pas à jour,

CSelCalcExpressionComparedToExpression( QCOL: [test.MasterData].[dbo].[Annexes].Amount_TransactionCurrency_id x_cmpEq QCOL: [test.MasterData].[dbo].[CurrencyShareds].Id )

Loaded histogram for column QCOL: [test.MasterData].[dbo].[Annexes].Amount_TransactionCurrency_id from stats with id 7

Loaded histogram for column QCOL: [test.MasterData].[dbo].[CurrencyShareds].Id from stats with id 1 *** WARNING: badly-formed histogram ***

Selectivity: 4.59503e-018

La sélectivité diminue considérablement et le nombre de lignes estimé de la jointure est donc de 1.

Lorsque l'histogramme change

Après avoir ajouté une seule ligne aux annexes qui référence CurrencyShared avec un ID élevé, l'histogramme pour IX_FK_Amount_TransactionCurrency se transforme en

RANGE_HI_KEY         RANGE_ROWS    EQ_ROWS       DISTINCT_RANGE_ROWS  AVG_RANGE_ROWS
-------------------- ------------- ------------- -------------------- --------------
119762190797406475   0             173           0                    1
119762190797406478   0             868           0                    1
119762190797406481   0             107           0                    1
119762190797406494   0             105745        0                    1
119762190797406496   0             330           0                    1
119762190797406618   0             1             0                    1
119762190797406628   0             1             0                    1
977955748426318623   0             1             0                    1

Avec cet histogramme, le problème disparaît, maintenant l'ajout d'une nouvelle ligne à currencyshareds ne provoque pas de baisse spectaculaire de l'estimation de la cardinalité.

Pourquoi donc?

Je soupçonne que c'est ainsi que l'algorithme d'estimation d'histogramme grossier fonctionne dans sql2014 +, et je base ma supposition sur ce grand article https://www.sqlshack.com/join-estimation-internals/

L'estimation d'histogramme grossier est un nouvel algorithme et moins documenté, même en termes de concepts généraux. Il est connu qu'au lieu d'aligner les histogrammes pas à pas, il les aligne uniquement avec les limites d'histogramme minimum et maximum. Cette méthode introduit potentiellement moins d'erreurs CE (pas toujours cependant, car nous nous souvenons que ce n'est qu'un modèle).

Juste pour que tout soit clair - pourquoi avons-nous des identifiants aussi étranges dans currencyshareds?

C'est assez simple - nos identifiants sont globalement uniques et sont basés en partie sur l'horodatage (implémentation basée sur flocon de neige ). Les monnaies les plus courantes ont été ajoutées au début de l'application il y a plusieurs années, et seules quelques-unes sont réellement utilisées dans la production, c'est pourquoi dans l'histogramme, il n'y a que celles avec un ID "faible".

Le problème est apparu dans nos environnements de test, où certains tests automatisés ont commencé à ajouter des devises de test, entraînant l'exécution de certaines requêtes plus longtemps ou un délai d'expiration ...

Comment resoudre le probleme?

Nous mettrons à jour les statistiques de ces tables de référence (nous pourrions avoir un problème similaire avec d'autres tables de données de référence similaires) plus souvent - ces tables sont petites, donc la mise à jour des statistiques n'est pas un problème

Leçons apprises

Les statistiques à jour sont importantes !!!
une ancienne colonne d'identité simple ne causerait pas ces problèmes :)

LeMaciek
la source

Concernant l'alignement grossier: sqlperformance.com/2018/11/sql-optimizer/…

Paul White 9