Kardinalitätsschätzungsproblem beim inneren Join

Ich habe Probleme zu verstehen, warum die Zeilenschätzung so schrecklich falsch ist. Hier ist mein Fall:

Einfache Verknüpfung - unter Verwendung von SQL Server 2016 SP2 (dasselbe Problem auf 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 schätzt 1 Zeile, während es 107131 ist und eine verschachtelte Schleife ausführt ( Link zum Plan ). Nachdem die Statistiken für CurrencyShareds aktualisiert wurden, ist die Schätzung in Ordnung und es wird ein Zusammenführungs-Join ausgewählt ( Link zu neuem Plan ). Sobald nur ein Datensatz zu CurrencyShareds hinzugefügt wird, werden die Statistiken "veraltet" und sql kehrt zur falschen Schätzung zurück.

Ich würde mir nicht so viele Sorgen um diese einfache Abfrage machen, aber dies ist nur ein Teil einer größeren Abfrage, und dies ist der Beginn eines Dominos ...

Warum verursacht das Hinzufügen einer Zeile zur 100-Datensätze-Tabelle einen solchen Schaden? Wenn ich mir die Ausgabe des Kardinalitätsschätzungs-Trace ansehe, sehe ich diese Warnung, ***WARNING: badly-formed histogram ***aber ich konnte zu diesem Thema nichts mehr finden.

Hier wird die vollständige Ausgabe der Kardinalitätsschätzung ausgegeben:

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

Und wenn ich die Statistiken auf CurrencyShareds aktualisiere, ändert sich der Teil mit dem "schlecht geformten Histogramm" und die Kardinalität wird korrekt berechnet

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

Und Statistikinformationen für diese "[CurrencyShareds] .Id von Statistiken mit der ID 1" mit Warnung über das Histogramm, das für mich gut aussieht ...

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

und Infos zum zweiten 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
quelle

Antworten:

Basierend auf Ihrem Histogramm konnte ich repro das Thema im Jahr 2017 CU6. Ich würde nicht sagen, dass du etwas falsch machst. Vielmehr läuft bei der Kardinalitätsschätzung etwas schief. Folgendes erhalte ich vor dem Einfügen einer Zeile:

Die endgültige Kardinalitätsschätzung sinkt nach dem Einfügen einer Zeile erheblich:

Du hast hier einen ziemlich einfachen Repro, also ist mein Rat zu Produkt-Feedback einzureichen oder ein Support-Ticket bei Microsoft zu eröffnen. Ich konnte einige Problemumgehungen finden, die mit Ihren Beispieldaten funktionierten, und eine davon ist möglicherweise für Sie akzeptabel.

Legen Sie den eindeutigen Index auf CurrencyShareds.Id. Ohne einen eindeutigen Index kann ich den Repro nicht zum Laufen bringen. Die Tabelle ist klein, also kommen Sie vielleicht ohne den Index aus. Natürlich könnten Sie sehr gute Gründe dafür haben, es zu behalten.
Materialisieren Sie die Ergebnisse des Joins in einer temporären Tabelle. Basierend auf Ihrer Frage ist es wichtig, in diesem Schritt eine vernünftige Schätzung zu erhalten, damit die größere Abfrage eine gute Leistung erbringt. Eine temporäre Tabelle ist eine Möglichkeit, dies zu erreichen.
Verwenden Sie das ältere CE. Ich kann das Problem nicht damit reproduzieren. Dies kann sich natürlich negativ auf den Rest Ihrer Anfrage auswirken.
Trick den Query Optimizer mit albernem Code. In meinen Tests funktioniert beispielsweise das folgende Umschreiben hervorragend:

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

Ich vermute, dass dies funktioniert, weil der CE scheint, die Dichte anstelle des Histogramms zu verwenden. Andere ähnliche Umschreibungen können den gleichen Effekt haben. Es gibt keine Garantie dafür, dass die Art der Abfrage auch in Zukunft gut funktioniert. Aus diesem Grund sollten Sie sich an Microsoft wenden, um die Wahrscheinlichkeit zu erhöhen, dass eines Tages ein Fix für Ihr Problem in das veröffentlichte Produkt aufgenommen wird.

Joe Obbish
quelle

Ok, ich hoffe ich verstehe es jetzt - also das ist unser Fall

Gegeben

Eine Referenztabelle (CurrencyShareds) mit ~ 100 Zeilen, aber großen IDs und sehr unterschiedlichen minimalen und maximalen Werten - min: 119.762.190.797.406.464 vs max: 977.955.748.426.318.592
Eine Tabelle (Anhänge) mit einfachen FK zu CurrencyShared, aber nur wenigen verwendeten Währungen - Sie können sehen, dass das Histogramm für IX_FK_Amount_TransactionCurrency 5 IDs auflistet - und was wichtig ist, nur diese "niedrigen" IDs, da andere nicht verwendet werden.

Wenn alle Statistiken dann aktuell sind

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

Dann ist die für den Join berechnete Selektivität mit 100 * 107,131 * 0,01 = 107,131 in Ordnung

Wenn die Statistiken für currencyshareds nicht aktuell sind, dann

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

Die Selektivität sinkt dramatisch, und daher beträgt die geschätzte Zeilennummer des Joins 1.

Wenn sich das Histogramm ändert

Nachdem ich Anhängen, die CurrencyShared mit hoher ID enthalten, eine einzelne Zeile hinzugefügt habe, ändert sich das Histogramm für IX_FK_Amount_TransactionCurrency in

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

Mit diesem Histogramm verschwindet das Problem, und das Hinzufügen einer neuen Zeile zu currencyshareds führt nicht zu einem dramatischen Abfall der Kardinalitätsschätzung.

Warum das?

Ich vermute, dass der grobe Histogrammschätzungsalgorithmus in sql2014 + so funktioniert, und ich beziehe mich auf diesen großartigen Beitrag https://www.sqlshack.com/join-estimation-internals/

Die grobe Histogrammschätzung ist ein neuer Algorithmus, der selbst im Hinblick auf allgemeine Konzepte weniger dokumentiert ist. Es ist bekannt, dass Histogramme nicht schrittweise, sondern nur mit minimalen und maximalen Histogrammgrenzen ausgerichtet werden. Diese Methode führt möglicherweise zu weniger CE-Fehlern (nicht immer, da wir uns daran erinnern, dass dies nur ein Modell ist).

Nur um alles klar zu machen - warum haben wir so seltsame IDs in currencyshareds?

Es ist ganz einfach - unsere IDs sind weltweit einzigartig und basieren teilweise auf dem Zeitstempel (Implementierung basiert auf Schneeflocke) ). Die gebräuchlichsten Währungen wurden vor einigen Jahren zu Beginn der Anwendung hinzugefügt, und nur die wenigen werden tatsächlich in der Produktion verwendet. Deshalb gibt es im Histogramm nur solche mit einer "niedrigen" ID.

Das Problem trat in unseren Testumgebungen auf. In einigen automatisierten Tests wurden Testwährungen hinzugefügt, wodurch einige Abfragen länger ausgeführt wurden oder eine Zeitüberschreitung auftrat.

Wie kann das Problem behoben werden?

Wir werden die Statistiken für diese Referenztabellen häufiger aktualisieren (möglicherweise haben wir ein ähnliches Problem mit anderen ähnlichen Referenzdatentabellen) - diese Tabellen sind klein, sodass die Aktualisierung der Statistiken kein Problem darstellt

gewonnene Erkenntnisse

Aktuelle Statistiken sind wichtig !!!
Eine einfache alte Identitätsspalte würde diese Probleme nicht verursachen :)

LeMaciek
quelle

In Bezug auf die grobe Ausrichtung: sqlperformance.com/2018/11/sql-optimizer/…

Paul White setzt Monica wieder ein