SQL Server 2014: Gibt es eine Erklärung für die inkonsistente Schätzung der Kardinalität von Self-Joins?

Betrachten Sie den folgenden Abfrageplan in SQL Server 2014:

Im Abfrageplan ar.fId = ar.fIdergibt eine Selbstverknüpfung eine Schätzung von 1 Zeile. Dies ist jedoch eine logisch inkonsistente Schätzung: Sie arenthält 20,608Zeilen und nur einen eindeutigen Wert von fId(in der Statistik genau wiedergegeben). Daher erzeugt dieser Join das vollständige Kreuzprodukt von Zeilen ( ~424MMZeilen), wodurch die Abfrage mehrere Stunden ausgeführt wird.

Es fällt mir schwer zu verstehen, warum SQL Server eine Schätzung erstellt hat, die sich so leicht als mit der Statistik inkonsistent erweisen lässt. Irgendwelche Ideen?

Erstuntersuchung und zusätzliches Detail

Basierend auf der Antwort von Paul scheint es, dass sowohl die SQL 2012- als auch die SQL 2014-Heuristik zur Schätzung der Join-Kardinalität leicht mit einer Situation fertig werden sollten, in der zwei identische Histogramme verglichen werden müssen.

Ich habe mit der Ausgabe des Trace-Flags 2363 begonnen, konnte das aber nicht so einfach nachvollziehen. Bedeutet das folgende Snippet, dass SQL Server Histogramme für fIdund vergleicht bId, um die Selektivität eines Joins zu schätzen, der nur verwendet wird fId? Wenn ja, wäre das offensichtlich nicht richtig. Oder habe ich die Trace-Flag-Ausgabe falsch gelesen?

Plan for computation:
  CSelCalcExpressionComparedToExpression( QCOL: [ar].fId x_cmpEq QCOL: [ar].fId )
Loaded histogram for column QCOL: [ar].bId from stats with id 3
Loaded histogram for column QCOL: [ar].fId from stats with id 1
Selectivity: 0

Beachten Sie, dass ich mehrere Problemumgehungen gefunden habe, die im vollständigen Reproskript enthalten sind und diese Abfrage auf Millisekunden reduzieren. Diese Frage konzentriert sich darauf, das Verhalten zu verstehen, wie es in zukünftigen Abfragen vermieden werden kann und ob es sich um einen Fehler handelt, der bei Microsoft eingereicht werden sollte.

Hier ist ein vollständiges Reproskript , hier ist die vollständige Ausgabe des Ablaufverfolgungsflags 2363 und hier sind die Abfrage- und Tabellendefinitionen, falls Sie sie schnell anzeigen möchten, ohne das vollständige Skript zu öffnen:

WITH cte AS (
    SELECT ar.fId, 
        ar.bId,
        MIN(CONVERT(INT, ar.isT)) AS isT,
        MAX(CONVERT(INT, tcr.isS)) AS isS
    FROM  #SQL2014MinMaxAggregateCardinalityBug_ar ar 
    LEFT OUTER JOIN #SQL2014MinMaxAggregateCardinalityBug_tcr tcr
        ON tcr.rId = 508
        AND tcr.fId = ar.fId
        AND tcr.bId = ar.bId
    GROUP BY ar.fId, ar.bId
)
SELECT s.fId, s.bId, s.isS, t.isS
FROM cte s 
JOIN cte t 
    ON t.fId = s.fId 
    AND t.isT = 1

---

CREATE TABLE #SQL2014MinMaxAggregateCardinalityBug_ar (
    fId INT NOT NULL,
    bId INT NOT NULL,
    isT BIT NOT NULL
    PRIMARY KEY (fId, bId)
)

CREATE TABLE #SQL2014MinMaxAggregateCardinalityBug_tcr (
    rId INT NOT NULL,
    fId INT NOT NULL,
    bId INT NOT NULL,
    isS BIT NOT NULL
    PRIMARY KEY (rId, fId, bId, isS)
)

Es fällt mir schwer zu verstehen, warum SQL Server eine Schätzung erstellt hat, die sich so leicht als mit der Statistik inkonsistent erweisen lässt.

Konsistenz

Es gibt keine allgemeine Garantie für die Konsistenz. Schätzungen können auf verschiedenen (aber logisch äquivalenten) Teilbäumen zu verschiedenen Zeiten unter Verwendung verschiedener statistischer Methoden berechnet werden.

Es ist nichts falsch an der Logik, die besagt, dass das Zusammenfügen dieser beiden identischen Teilbäume ein Kreuzprodukt ergeben sollte, aber es gibt auch nichts zu sagen, dass die Wahl der Argumentation fundierter ist als jede andere.

Erstschätzung

In Ihrem speziellen Fall wird die anfängliche Kardinalitätsschätzung für den Join nicht für zwei identische Teilbäume durchgeführt . Die Baumform zu dieser Zeit ist:

  LogOp_Join
     LogOp_GbAgg
        LogOp_LeftOuterJoin
           LogOp_Get TBL: ar
           LogOp_Select
              LogOp_Get TBL: tcr
              ScaOp_Comp x_cmpEq
                 ScaOp_Identifier [tcr] .rId
                 ScaOp_Const-Wert = 508
           ScaOp_Logical x_lopAnd
              ScaOp_Comp x_cmpEq
                 ScaOp_Identifier [ar] .fId
                 ScaOp_Identifier [tcr] .fId
              ScaOp_Comp x_cmpEq
                 ScaOp_Identifier [ar] .bId
                 ScaOp_Identifier [tcr] .bId
        AncOp_PrjList 
           AncOp_PrjEl Expr1003 
              ScaOp_AggFunc stopMax
                 ScaOp_Convert int
                    ScaOp_Identifier [tcr] .isS
     LogOp_Select
        LogOp_GbAgg
           LogOp_LeftOuterJoin
              LogOp_Get TBL: ar
              LogOp_Select
                 LogOp_Get TBL: tcr
                 ScaOp_Comp x_cmpEq
                    ScaOp_Identifier [tcr] .rId
                    ScaOp_Const-Wert = 508
              ScaOp_Logical x_lopAnd
                 ScaOp_Comp x_cmpEq
                    ScaOp_Identifier [ar] .fId
                    ScaOp_Identifier [tcr] .fId
                 ScaOp_Comp x_cmpEq
                    ScaOp_Identifier [ar] .bId
                    ScaOp_Identifier [tcr] .bId
           AncOp_PrjList 
              AncOp_PrjEl Expr1006 
                 ScaOp_AggFunc stopMin
                    ScaOp_Convert int
                       ScaOp_Identifier [ar] .isT
              AncOp_PrjEl Expr1007 
                 ScaOp_AggFunc stopMax
                    ScaOp_Convert int
                       ScaOp_Identifier [tcr] .isS
        ScaOp_Comp x_cmpEq
           ScaOp_Identifier Expr1006 
           ScaOp_Const-Wert = 1
     ScaOp_Comp x_cmpEq
        ScaOp_Identifier QCOL: [ar] .fId
        ScaOp_Identifier QCOL: [ar] .fId

Der erste Eingang verbinden wird ein Aggregat nicht projiziert vereinfacht entfernt hat, und die zweiten Eingang verbindet das Prädikat aufweist t.isT = 1darunter geschoben, wo t.isTist MIN(CONVERT(INT, ar.isT)). Trotzdem kann die Selektivitätsberechnung für das isTPrädikat CSelCalcColumnInIntervalfür ein Histogramm verwendet werden:

  CSelCalcColumnInInterval
      Spalte: COL: Expr1006 

Geladenes Histogramm für Spalte QCOL: [ar] .istT aus Statistiken mit ID 3

Selektivität: 4,85248e-005

Statistikerfassung generiert: 
  CStCollFilter (ID = 11, CARD = 1)
      CStCollGroupBy (ID = 10, CARD = 20608)
          CStCollOuterJoin (ID = 9, CARD = 20608 x_jtLeftOuter)
              CStCollBaseTable (ID = 3, CARD = 20608 TBL: ar)
              CStCollFilter (ID = 8, CARD = 1)
                  CStCollBaseTable (ID = 4, CARD = 28 TBL: tcr)

Die (richtige) Erwartung ist, dass 20.608 Zeilen durch dieses Prädikat auf 1 Zeile reduziert werden.

Schätzung beitreten

Die Frage lautet nun, wie die 20.608 Zeilen der anderen Join-Eingabe mit dieser einen Zeile übereinstimmen:

  LogOp_Join
      CStCollGroupBy (ID = 7, CARD = 20608)
          CStCollOuterJoin (ID = 6, CARD = 20608 x_jtLeftOuter)
              ...

      CStCollFilter (ID = 11, CARD = 1)
          CStCollGroupBy (ID = 10, CARD = 20608)
              ...

      ScaOp_Comp x_cmpEq
          ScaOp_Identifier QCOL: [ar] .fId
          ScaOp_Identifier QCOL: [ar] .fId

Es gibt verschiedene Möglichkeiten, den Join im Allgemeinen zu schätzen. Wir könnten zum Beispiel:

• Leiten Sie neue Histogramme für jeden Planoperator in jedem Teilbaum ab, richten Sie sie am Join aus (interpolieren Sie die Schrittwerte nach Bedarf) und überprüfen Sie, wie sie übereinstimmen. oder
• Führen Sie eine einfachere "grobe" Ausrichtung der Histogramme durch (unter Verwendung von Minimal- und Maximalwerten, nicht schrittweise). oder
• Berechnen Sie separate Selektivitäten nur für die Verknüpfungsspalten (ausgehend von der Basistabelle und ohne Filterung) und fügen Sie dann den Selektivitätseffekt der Nicht-Verknüpfungs-Vergleichselemente hinzu.
• ...

Abhängig von dem verwendeten Kardinalitätsschätzer und einigen Heuristiken kann eine dieser (oder eine Variation) verwendet werden. Weitere Informationen finden Sie im Microsoft White Paper Optimieren Ihrer Abfragepläne mit dem SQL Server 2014 Cardinality Estimator .

Fehler?

Nun, wie in der Frage erwähnt, verwendet in diesem Fall der "einfache" einspaltige Join (on fId) den CSelCalcExpressionComparedToExpressionTaschenrechner:

Plan für die Berechnung:

  CSelCalcExpressionComparedToExpression [ar] .fId x_cmpEq [ar] .fId

Geladenes Histogramm für Spalte QCOL: [ar] .bId aus Statistiken mit ID 2
Geladenes Histogramm für Spalte QCOL: [ar] .fId aus Statistiken mit ID 1

Selektivität: 0

Diese Berechnung geht davon aus, dass das Zusammenführen der 20.608 Zeilen mit der 1 gefilterten Zeile eine Selektivität von Null hat: Es stimmen keine Zeilen überein (in endgültigen Plänen als eine Zeile angegeben). Ist das falsch? Ja, wahrscheinlich gibt es hier einen Fehler im neuen CE. Man könnte argumentieren, dass 1 Zeile mit allen Zeilen oder mit keiner Zeile übereinstimmt, so dass das Ergebnis möglicherweise vernünftig ist, aber es gibt Grund zu der Annahme, dass dies nicht der Fall ist.

Die Details sind eigentlich ziemlich schwierig, aber die Erwartung, dass die Schätzung auf ungefilterten fIdHistogrammen basiert , die durch die Selektivität des Filters modifiziert werden und 20608 * 20608 * 4.85248e-005 = 20608Zeilen ergeben, ist sehr vernünftig.

Wenn Sie dieser Berechnung folgen, müssen Sie stattdessen den Taschenrechner CSelCalcSimpleJoinWithDistinctCountsverwenden CSelCalcExpressionComparedToExpression. Es gibt keine dokumentierte Möglichkeit, dies zu tun, aber wenn Sie neugierig sind, können Sie das undokumentierte Ablaufverfolgungsflag 9479 aktivieren:

Beachten Sie, dass der endgültige Join 20.608 Zeilen aus zwei einzeiligen Eingaben erstellt. Dies sollte jedoch nicht überraschen. Es ist derselbe Plan, der vom ursprünglichen CE unter TF 9481 erstellt wurde.

Ich erwähnte, dass die Details schwierig (und zeitaufwendig zu untersuchen) sind, aber soweit ich das beurteilen kann, hängt die Grundursache des Problems mit dem Prädikat zusammen rId = 508, mit einer Selektivität von Null. Diese Nullschätzung wird auf normale Weise auf eine Zeile angehoben, was zur Nullselektivitätsschätzung bei dem fraglichen Join beizutragen scheint, wenn niedrigere Prädikate in der Eingabebaumstruktur berücksichtigt werden (daher werden Statistiken für geladen bId).

Wenn Sie dem Outer Join erlauben, eine innere Schätzung von null Zeilen beizubehalten (anstatt auf eine Zeile zu erhöhen) (damit alle äußeren Zeilen qualifiziert sind), erhalten Sie mit beiden Rechnern eine fehlerfreie Join-Schätzung. Wenn Sie daran interessiert sind, dies zu untersuchen, lautet das undokumentierte Ablaufverfolgungsflag 9473 (allein):

Das Verhalten der Join-Kardinalitätsschätzung mit CSelCalcExpressionComparedToExpressionkann auch geändert werden, um `` bId`` mit einem anderen undokumentierten Variationsflag nicht zu berücksichtigen (9494). Ich erwähne all dies, weil ich weiß, dass Sie an solchen Dingen interessiert sind. nicht, weil sie eine Lösung bieten. Bis Sie Microsoft das Problem melden und es beheben (oder nicht), ist es wahrscheinlich die beste Möglichkeit, die Abfrage anders auszudrücken. Unabhängig davon, ob das Verhalten beabsichtigt ist oder nicht, sollten sie daran interessiert sein, etwas über die Regression zu erfahren.

Abschließend möchte ich noch eines aufräumen, das im Reproduktionsskript erwähnt wurde: Die endgültige Position des Filters im Fragenplan ist das Ergebnis einer kostenbasierten Untersuchung GbAggAfterJoinSel, bei der das Aggregat und der Filter über den Join verschoben wurden, da die Join-Ausgabe so gering ist Anzahl der Reihen. Der Filter befand sich anfangs wie erwartet unterhalb des Joins.