Warum schätzt SQL Server, dass nach dem Einfügen einiger Zeilen weniger Zeilen von einem Join ausgegeben werden?

Das Folgende ist eine vereinfachte Version von etwas, auf das ich in der Produktion gestoßen bin (wo sich der Plan an einem Tag, an dem eine ungewöhnlich hohe Anzahl von Chargen verarbeitet wurde, katastrophal verschlechterte).

Der Repro wurde mit dem neuen Kardinalitätsschätzer gegen 2014 und 2016 getestet.

CREATE TABLE T1 (FromDate  DATE, ToDate DATE, SomeId INT, BatchNumber INT);

INSERT INTO T1
SELECT TOP 1000 FromDate = '2017-01-01',
                ToDate = '2017-01-01',
                SomeId = ROW_NUMBER() OVER (ORDER BY @@SPID) -1,
                BatchNumber = 1
FROM   master..spt_values v1

CREATE TABLE T2 (SomeDateTime DATETIME, SomeId INT, INDEX IX(SomeDateTime));

INSERT INTO T2
SELECT TOP 1000000 '2017-01-01',
                   ROW_NUMBER() OVER (ORDER BY @@SPID) %1000
FROM   master..spt_values v1,
       master..spt_values v2

T1 enthält 1.000 Zeilen.

Die FromDate,, ToDateund BatchNumbersind in allen identisch. Der einzige Wert, der sich unterscheidet, sind SomeIdWerte zwischen 0und999

+------------+------------+--------+-----------+
|  FromDate  |   ToDate   | SomeId | BatchNumber |
+------------+------------+--------+-----------+
| 2017-01-01 | 2017-01-01 |      0 |         1 |
| 2017-01-01 | 2017-01-01 |      1 |         1 |
....
| 2017-01-01 | 2017-01-01 |    998 |         1 |
| 2017-01-01 | 2017-01-01 |    999 |         1 |
+------------+------------+--------+-----------+

T2 enthält 1 Million Zeilen

aber nur 1.000 verschiedene. Jeweils 1000 mal wie unten wiederholt.

+-------------------------+--------+-------+
|      SomeDateTime       | SomeId | Count |
+-------------------------+--------+-------+
| 2017-01-01 00:00:00.000 |      0 |  1000 |
| 2017-01-01 00:00:00.000 |      1 |  1000 |
...
| 2017-01-01 00:00:00.000 |    998 |  1000 |
| 2017-01-01 00:00:00.000 |    999 |  1000 |
+-------------------------+--------+-------+

Folgendes ausführen

SELECT *
FROM   T1
       INNER JOIN T2
               ON CAST(t2.SomeDateTime AS DATE) BETWEEN T1.FromDate AND T1.ToDate
                  AND T1.SomeId = T2.SomeId
WHERE  T1.BatchNumber = 1

Dauert auf meiner Maschine ungefähr 7 Sekunden. Die tatsächlichen und geschätzten Zeilen sind für alle Bediener im Plan perfekt.

Fügen Sie nun 3.000 zusätzliche Chargen zu T1 hinzu (mit den Chargennummern 2 bis 3001). Diese klonen jeweils die vorhandenen tausend Zeilen für Chargennummer 1

INSERT INTO T1
SELECT T1.FromDate,
       T1.ToDate,
       T1.SomeId,
       Nums.NewBatchNumber
FROM   T1
       CROSS JOIN (SELECT TOP (3000) 1 + ROW_NUMBER() OVER (ORDER BY @@SPID) AS NewBatchNumber
                   FROM   master..spt_values v1, master..spt_values v2) Nums

und aktualisieren Sie die Statistiken für Glück

 UPDATE STATISTICS T1 WITH FULLSCAN

Führen Sie die ursprüngliche Abfrage erneut aus.

SELECT *
FROM   T1
       INNER JOIN T2
               ON CAST(t2.SomeDateTime AS DATE) BETWEEN T1.FromDate AND T1.ToDate
                  AND T1.SomeId = T2.SomeId
WHERE  T1.BatchNumber = 1

Ich ließ es eine Minute lang laufen, bevor ich es tötete. Zu diesem Zeitpunkt hatte es 40.380 Zeilen ausgegeben, also würde es wohl 25 Minuten dauern, um die volle Million auszugeben.

Das einzige, was sich geändert hat, ist, dass ich einige zusätzliche Zeilen hinzugefügt habe, die nicht mit dem T1.BatchNumber = 1Prädikat übereinstimmen .

Der Plan hat sich nun jedoch geändert. Stattdessen werden verschachtelte Schleifen verwendet, und während die Anzahl der auskommenden Zeilen t1immer noch korrekt auf 1.000 (①) geschätzt wird, ist die Schätzung der Anzahl der verbundenen Zeilen jetzt von 1 Million auf tausend (②) gesunken.

Die Frage ist also ...

Warum wirkt sich das Hinzufügen zusätzlicher Zeilen BatchNumber <> 1irgendwie auf die Schätzungen für verbundene Zeilen aus, wenn BatchNumber = 1?

Es scheint sicherlich nicht intuitiv zu sein, dass das Hinzufügen von Zeilen zu einer Tabelle die geschätzte Anzahl von Zeilen aus der gesamten Abfrage reduzieren sollte.

sql-server sql-server-2014 cardinality-estimates Martin Smith
quelle

Ihr erster Plan ist auch seltsam, weil er seriell ist, auch wenn das geschätzte Ergebnis mehr Zeilen enthält als der zweite, der parallel ist. Sind Sie sicher, dass diese beiden Pläne vom selben Server stammen? Der erste scheint maxdop = 1 zu haben

sepupic

@sepupic - yep. beide auf derselben Instanz - vermutlich glaubt SQL Server nicht, dass sich der Aufwand für Parallelität im ersten Plan lohnt.

Martin Smith

Das Erzwingen einer Hash-Verknüpfung mit dem größeren T1 ergibt einen parallelen Plan. Der Hash-Join-Operator 9.10751kostet jetzt bei MAXDOP 1 im Vergleich zum Original 7.6675465- ich bin mir nicht sicher, worauf das basiert, da die Eingaben gleich sind.

Martin Smith

Es ist wichtig zu beachten, dass Ihnen beim Ändern von Abfragen oder Daten in den Tabellen keine Konsistenz garantiert wird. Das Abfrageoptimierungsprogramm wechselt möglicherweise zu einer anderen Methode zur Kardinalitätsschätzung (z. B. zur Verwendung der Dichte im Gegensatz zu Histogrammen), wodurch zwei Abfragen als inkonsistent erscheinen können. Trotzdem scheint es, als würde der Abfrageoptimierer in Ihrem Fall eine unvernünftige Entscheidung treffen. Lassen Sie uns also näher darauf eingehen.

Ihre Demo ist zu kompliziert, daher werde ich an einem einfacheren Beispiel arbeiten, von dem ich glaube, dass es dasselbe Verhalten zeigt. Starten der Datenvorbereitung und Tabellendefinitionen:

DROP TABLE dbo.T1 IF EXISTS;
CREATE TABLE dbo.T1 (FromDate DATE, ToDate DATE, SomeId INT);

INSERT INTO dbo.T1 WITH (TABLOCK)
SELECT TOP 1000 NULL, NULL, 1
FROM master..spt_values v1;

DROP TABLE dbo.T2 IF EXISTS;
CREATE TABLE dbo.T2 (SomeDateTime DATETIME, INDEX IX(SomeDateTime));

INSERT INTO dbo.T2 WITH (TABLOCK)
SELECT TOP 2 NULL
FROM master..spt_values v1
CROSS JOIN master..spt_values v2;

Hier ist die SELECTzu untersuchende Abfrage:

SELECT *
FROM T1
INNER JOIN T2 ON t2.SomeDateTime BETWEEN T1.FromDate AND T1.ToDate
WHERE T1.SomeId = 1;

Diese Abfrage ist einfach genug, damit wir die Formel für die Kardinalitätsschätzung ohne Trace-Flags erarbeiten können. Ich werde jedoch versuchen, TF 2363 zu verwenden, um besser zu veranschaulichen, was im Optimierer vor sich geht. Es ist nicht klar, ob ich erfolgreich sein werde.

Definieren Sie folgende Variablen:

C₁ = Anzahl der Zeilen in Tabelle T1

C₂ = Anzahl der Zeilen in Tabelle T2

S₁= die Selektivität des T1.SomeIdFilters

Mein Anspruch ist, dass die Kardinalitätsschätzung für die obige Abfrage wie folgt lautet:

Wenn > = * :C₂S₁C₁

C₂* mit einer Untergrenze von * S₁S₁C₁

Wenn < * :C₂S₁C₁

164.317* * mit einer Obergrenze von *C₂S₁S₁C₁

Lassen Sie uns einige Beispiele durchgehen, obwohl ich nicht jedes einzelne durchgehen werde, das ich getestet habe. Für die anfängliche Datenvorbereitung haben wir:

C₁ = 1000

C₂ = 2

S₁ = 1,0

Daher sollte die Kardinalitätsschätzung wie folgt lauten:

2 * 164,317 = 328,634

Der unten nicht zu fälschende Screenshot beweist dies:

Mit dem undokumentierten Trace-Flag 2363 können wir einige Hinweise darauf erhalten, was los ist:

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB2].[dbo].[T1].SomeId

Loaded histogram for column QCOL: [SE_DB2].[dbo].[T1].SomeId from stats with id 2

Selectivity: 1

Stats collection generated: 

  CStCollFilter(ID=3, CARD=1000)

      CStCollBaseTable(ID=1, CARD=1000 TBL: T1)

End selectivity computation

Begin selectivity computation

Input tree:

...

Plan for computation:

  CSelCalcSimpleJoinWithUpperBound (Using base cardinality)

      CSelCalcOneSided (RIGHT)

          CSelCalcCombineFilters_ExponentialBackoff (AND)

              CSelCalcFixedFilter (0.3)

              CSelCalcFixedFilter (0.3)

Selectivity: 0.164317

Stats collection generated: 

  CStCollJoin(ID=4, CARD=328.634 x_jtInner)

      CStCollFilter(ID=3, CARD=1000)

          CStCollBaseTable(ID=1, CARD=1000 TBL: T1)

      CStCollBaseTable(ID=2, CARD=2 TBL: T2)

End selectivity computation

Mit dem neuen CE erhalten wir die übliche Schätzung von 16% für a BETWEEN. Dies ist auf ein exponentielles Backoff mit dem neuen CE 2014 zurückzuführen. Jede Ungleichung hat eine Kardinalitätsschätzung von 0,3 und wird daher BETWEENals 0,3 * sqrt (0,3) = 0,164317 berechnet. Multiplizieren Sie die 16% -Selektivität mit der Anzahl der Zeilen in T2 und T1, und wir erhalten unsere Schätzung. Scheint vernünftig genug. Erhöhen T2wir die Anzahl der Zeilen auf 7. Jetzt haben wir Folgendes:

C₁ = 1000

C₂ = 7

S₁ = 1,0

Daher sollte die Kardinalitätsschätzung 1000 sein, weil:

7 * 164,317 = 1150> 1000

Der Abfrageplan bestätigt dies:

Wir können mit TF 2363 noch einen Blick darauf werfen, aber es sieht so aus, als ob die Selektivität hinter den Kulissen angepasst wurde, um die Obergrenze zu berücksichtigen. Ich vermute, dass dies CSelCalcSimpleJoinWithUpperBoundverhindert , dass die Kardinalitätsschätzung über 1000 hinausgeht.

Loaded histogram for column QCOL: [SE_DB2].[dbo].[T1].SomeId from stats with id 2

Selectivity: 1

Stats collection generated: 

  CStCollFilter(ID=3, CARD=1000)

      CStCollBaseTable(ID=1, CARD=1000 TBL: T1)

End selectivity computation

Begin selectivity computation

Input tree:

...

Plan for computation:

  CSelCalcSimpleJoinWithUpperBound (Using base cardinality)

      CSelCalcOneSided (RIGHT)

          CSelCalcCombineFilters_ExponentialBackoff (AND)

              CSelCalcFixedFilter (0.3)

              CSelCalcFixedFilter (0.3)

Selectivity: 0.142857

Stats collection generated: 

  CStCollJoin(ID=4, CARD=1000 x_jtInner)

      CStCollFilter(ID=3, CARD=1000)

          CStCollBaseTable(ID=1, CARD=1000 TBL: T1)

      CStCollBaseTable(ID=2, CARD=7 TBL: T2)

Lassen Sie uns T2auf 50000 Zeilen stoßen . Jetzt haben wir:

C₁ = 1000

C₂ = 50000

S₁ = 1,0

Daher sollte die Kardinalitätsschätzung wie folgt lauten:

50000 * 1,0 = 50000

Der Abfrageplan bestätigt dies erneut. Es ist viel einfacher, die Schätzung zu erraten, nachdem Sie die Formel bereits herausgefunden haben:

TF-Ausgabe:

Loaded histogram for column QCOL: [SE_DB2].[dbo].[T1].SomeId from stats with id 2

Selectivity: 1

Stats collection generated: 

  CStCollFilter(ID=3, CARD=1000)

      CStCollBaseTable(ID=1, CARD=1000 TBL: T1)

...

Plan for computation:

  CSelCalcSimpleJoinWithUpperBound (Using base cardinality)

      CSelCalcOneSided (RIGHT)

          CSelCalcCombineFilters_ExponentialBackoff (AND)

              CSelCalcFixedFilter (0.3)

              CSelCalcFixedFilter (0.3)

Selectivity: 0.001

Stats collection generated: 

  CStCollJoin(ID=4, CARD=50000 x_jtInner)

      CStCollFilter(ID=3, CARD=1000)

          CStCollBaseTable(ID=1, CARD=1000 TBL: T1)

      CStCollBaseTable(ID=2, CARD=50000 TBL: T2)

Für dieses Beispiel scheint das exponentielle Backoff irrelevant zu sein:

5000 * 1000 * 0,001 = 50000.

Fügen wir nun 3k Zeilen zu T1 mit dem SomeIdWert 0 hinzu. Code dazu:

INSERT INTO T1 WITH (TABLOCK)
SELECT TOP 3000 NULL, NULL, 0
FROM   master..spt_values v1,
       master..spt_values v2;

UPDATE STATISTICS T1 WITH FULLSCAN;

Jetzt haben wir:

C₁ = 4000

C₂ = 50000

S₁ = 0,25

Daher sollte die Kardinalitätsschätzung wie folgt lauten:

50000 * 0,25 = 12500

Der Abfrageplan bestätigt dies:

Dies ist das gleiche Verhalten, das Sie in der Frage genannt haben. Ich habe einer Tabelle irrelevante Zeilen hinzugefügt, und die Kardinalitätsschätzung hat abgenommen. Warum ist das passiert? Achten Sie auf die fetten Linien:

Loaded histogram for column QCOL: [SE_DB2].[dbo].[T1].SomeId from stats with id 2

Selektivität: 0,25

Stats collection generated: 

  CStCollFilter(ID=3, CARD=1000)

      CStCollBaseTable(ID=1, CARD=4000 TBL: T1)

End selectivity computation

Begin selectivity computation

Input tree:

...

Plan for computation:

  CSelCalcSimpleJoinWithUpperBound (Using base cardinality)

      CSelCalcOneSided (RIGHT)

          CSelCalcCombineFilters_ExponentialBackoff (AND)

              CSelCalcFixedFilter (0.3)

              CSelCalcFixedFilter (0.3)

Selektivität: 0,00025

Stats collection generated: 

  CStCollJoin(ID=4, CARD=12500 x_jtInner)

      CStCollFilter(ID=3, CARD=1000)

          CStCollBaseTable(ID=1, CARD=4000 TBL: T1)

      CStCollBaseTable(ID=2, CARD=50000 TBL: T2)

End selectivity computation

Es scheint, als ob die Kardinalitätsschätzung für diesen Fall wie folgt berechnet wurde:

C₁* * * / ( * )S₁C₂S₁S₁C₁

Oder für dieses spezielle Beispiel:

4000 * 0,25 * 50000 * 0,25 / (0,25 * 4000) = 12500

Die allgemeine Formel kann natürlich vereinfacht werden zu:

C₂ * * S₁

Welches ist die Formel, die ich oben behauptet habe. Es scheint, als gäbe es eine Absage, die nicht sein sollte. Ich würde erwarten, dass die Gesamtzahl der Zeilen T1für die Schätzung relevant ist.

Wenn wir mehr Zeilen einfügen, sehen T1wir die Untergrenze in Aktion:

INSERT INTO T1 WITH (TABLOCK)
SELECT TOP 997000 NULL, NULL, 0
FROM   master..spt_values v1,
       master..spt_values v2;

UPDATE STATISTICS T1 WITH FULLSCAN;

Die Kardinalitätsschätzung beträgt in diesem Fall 1000 Zeilen. Ich werde den Abfrageplan und die TF 2363-Ausgabe weglassen.

Abschließend ist dieses Verhalten ziemlich verdächtig, aber ich weiß nicht genug, um zu erklären, ob es sich um einen Fehler handelt oder nicht. Mein Beispiel passt nicht genau zu Ihrem Repro, aber ich glaube, dass ich das gleiche allgemeine Verhalten beobachtet habe. Ich würde auch sagen, dass Sie ein bisschen Glück haben, wie Sie Ihre ursprünglichen Daten ausgewählt haben. Der Optimierer scheint ziemlich viel zu raten, damit ich mich nicht zu sehr auf die Tatsache einlasse, dass die ursprüngliche Abfrage 1 Million Zeilen zurückgegeben hat, die genau der Schätzung entsprechen.

Joe Obbish
quelle

In dem Beispiel in meiner Frage hatte ich versucht, eine unterschiedliche Anzahl von Chargen einzufügen, und das stimmt tatsächlich mit dem Muster hier überein. Rextester.com/WUJJJ48346 mit einem stetigen Rückgang pro Charge, bis eine Etage von 1.000, so dass nur der C2 * S1> S1 * C1, C2 * S1, S1 * C1Fall auftrat.

Martin Smith

Warum schätzt SQL Server, dass nach dem Einfügen einiger Zeilen weniger Zeilen von einem Join ausgegeben werden?

Antworten: