Kardinalitätsschätzung für> = und> für den Intra-Step-Statistikwert

9

Ich versuche zu verstehen, wie SQL Server versucht, für "größer als" und "größer als gleich" wo Klauseln in SQL Server 2014 zu schätzen.

Ich glaube, ich verstehe die Kardinalitätsschätzung, wenn sie zum Beispiel den Schritt trifft, wenn ich das tue

    select * from charge where charge_dt >= '1999-10-13 10:47:38.550'

Die Kardinalitätsschätzung ist 6672, die leicht als 32 (EQ_ROWS) + 6624 (RANGE_ROWS) + 16 (EQ_ROWS) = 6672 berechnet werden kann (Histogramm im folgenden Screenshot).

Geben Sie hier die Bildbeschreibung ein

Aber wenn ich das mache

    select * from charge where charge_dt >= '1999-10-13 10:48:38.550' 

(erhöhte die Zeit auf 10:48, so dass es kein Schritt ist)

Die Schätzung liegt bei 4844,13.

Wie wird das berechnet?

jesijesi
quelle

Antworten:

9

Die einzige Schwierigkeit besteht darin, zu entscheiden, wie mit den Histogrammschritten umgegangen werden soll, die teilweise vom Abfrageprädikatenintervall abgedeckt werden. Ganze Histogrammschritte, die vom Prädikatenbereich abgedeckt werden, sind trivial, wie in der Frage angegeben.

Legacy Cardinality Estimator

F = Bruch (zwischen 0 und 1) des vom Abfrageprädikat abgedeckten Schrittbereichs.

Die Grundidee besteht darin, mithilfe F(lineare Interpolation) zu bestimmen, wie viele der innerhalb eines Schrittes unterschiedlichen Werte vom Prädikat abgedeckt werden. Das Multiplizieren dieses Ergebnisses mit der durchschnittlichen Anzahl von Zeilen pro eindeutigem Wert (unter der Annahme einer Einheitlichkeit) und das Addieren der schrittweisen Zeilen ergibt die Kardinalitätsschätzung:

Kardinalität = EQ_ROWS + (AVG_RANGE_ROWS * F * DISTINCT_RANGE_ROWS)

Die gleiche Formel wird für >und >=im Legacy-CE verwendet.

Neuer Kardinalitätsschätzer

Das neue CE modifiziert den vorherigen Algorithmus geringfügig, um zwischen >und zu unterscheiden >=.

Die >Formel lautet zunächst:

Kardinalität = EQ_ROWS + (AVG_RANGE_ROWS * (F * (DISTINCT_RANGE_ROWS - 1)))

Denn >=es ist:

Kardinalität = EQ_ROWS + (AVG_RANGE_ROWS * ((F * (DISTINCT_RANGE_ROWS - 1)) + 1))

Das + 1spiegelt wider , dass , wenn der Vergleich Gleichheit beinhaltet, eine Übereinstimmung (die Aufnahme Annahme) angenommen wird.

Im Fragenbeispiel Fkann berechnet werden als:

DECLARE 
    @Q datetime = '1999-10-13T10:48:38.550',
    @K1 datetime = '1999-10-13T10:47:38.550',
    @K2 datetime = '1999-10-13T10:51:19.317';

DECLARE
    @QR float = DATEDIFF(MILLISECOND, @Q, @K2), -- predicate range
    @SR float = DATEDIFF(MILLISECOND, @K1, @K2) -- whole step range

SELECT
    F = @QR / @SR;

Das Ergebnis ist 0,728219019233034 . Stecken Sie das in die Formel für >=mit den anderen bekannten Werten:

Kardinalität = EQ_ROWS + (AVG_RANGE_ROWS * ((F * (DISTINCT_RANGE_ROWS - 1)) + 1))
            = 16 + (16,1956 * ((0,728219019233034 * (409-1)) + 1))
            = 16 + (16,1956 * ((0,728219019233034 * 408) + 1))
            = 16 + (16,1956 * (297,113359847077872 + 1))
            = 16 + (16,1956 * 298,113359847077872)
            = 16 + 4828.1247307393343837632
            = 4844.1247307393343837632
            = 4844.12473073933 (um die Genauigkeit zu schweben)

Dieses Ergebnis stimmt mit der in der Frage angegebenen Schätzung von 4844,13 überein.

Dieselbe Abfrage unter Verwendung des Legacy-CE (z. B. unter Verwendung des Trace-Flags 9481) sollte eine Schätzung von Folgendem ergeben:

Kardinalität = EQ_ROWS + (AVG_RANGE_ROWS * F * DISTINCT_RANGE_ROWS)
            = 16 + (16,1956 * 0,728219019233034 * 409)
            = 16 + 4823,72307468722
            = 4839,72307468722

Beachten Sie, dass die Schätzung für >und unter >=Verwendung des Legacy-CE gleich wäre.

Paul White 9
quelle
4

Die Formel zum Schätzen von Zeilen wird ein wenig albern, wenn der Filter "größer als" oder "kleiner als" ist, aber es ist eine Zahl, zu der Sie gelangen können.

Die Zahlen

Unter Verwendung von Schritt 193 sind hier die relevanten Zahlen:

RANGE_ROWS = 6624

EQ_ROWS = 16

AVG_RANGE_ROWS = 16.1956

RANGE_HI_KEY aus dem vorherigen Schritt = 1999-10-13 10: 47: 38.550

RANGE_HI_KEY aus dem aktuellen Schritt = 1999-10-13 10: 51: 19.317

Wert aus der WHERE-Klausel = 1999-10-13 10: 48: 38.550

Die Formel

1) Suchen Sie die ms zwischen den beiden Hi-Tasten

SELECT DATEDIFF (ms, '1999-10-13 10:47:38.550', '1999-10-13 10:51:19.317')

Das Ergebnis ist 220767 ms.

2) Passen Sie die Anzahl der Zeilen an

Wir müssen die Zeilen pro Millisekunde finden, aber bevor wir dies tun, müssen wir die AVG_RANGE_ROWS von den RANGE_ROWS subtrahieren:

6624 - 16.1956 = 6607.8044 Zeilen

3) Berechnen Sie die Zeilen pro ms mit der angepassten Anzahl von Zeilen:

6607.8044 Zeilen / 220767 ms = .0299311 Zeilen pro ms

4) Berechnen Sie die ms zwischen dem Wert aus der WHERE-Klausel und dem aktuellen Schritt RANGE_HI_KEY

SELECT DATEDIFF (ms, '1999-10-13 10:48:38.550', '1999-10-13 10:51:19.317')

Dies ergibt 160767 ms.

5) Berechnen Sie die Zeilen in diesem Schritt anhand der Zeilen pro Sekunde:

.0299311 Zeilen / ms * 160767 ms = 4811,9332 Zeilen

6) Erinnern Sie sich, wie wir die AVG_RANGE_ROWS früher subtrahiert haben? Zeit, sie wieder hinzuzufügen. Nachdem wir die Zahlen für Zeilen pro Sekunde berechnet haben, können wir auch die EQ_ROWS sicher hinzufügen:

4811,9332 + 16,1956 + 16 = 4844,1288

Abgerundet ist dies unsere Schätzung von 4844,13.

Testen der Formel

Ich konnte keine Artikel oder Blog-Beiträge darüber finden, warum AVG_RANGE_ROWS abgezogen wird, bevor die Zeilen pro ms berechnet werden. Ich war sie in der Lage zu bestätigen , wird in der Schätzung berücksichtigt, sondern nur in der letzten Millisekunde - buchstäblich.

Unter Verwendung der WideWorldImporters-Datenbank habe ich einige inkrementelle Tests durchgeführt und festgestellt, dass die Abnahme der Zeilenschätzungen bis zum Ende des Schritts linear ist, wobei plötzlich 1x AVG_RANGE_ROWS berücksichtigt wird.

Hier ist meine Beispielabfrage:

SELECT PickingCompletedWhen
FROM Sales.Orders
WHERE PickingCompletedWhen >= '2016-05-24 11:00:01.000000'

Ich habe die Statistiken für PickingCompletedWhen aktualisiert und dann das Histogramm erhalten:

DBCC SHOW_STATISTICS([sales.orders], '_WA_Sys_0000000E_44CA3770')

Histogramm für _WA_Sys_0000000E_44CA3770 (letzte 3 Schritte)

Um zu sehen, wie sich die geschätzten Zeilen verringern, wenn wir uns dem RANGE_HI_KEY nähern, habe ich während des gesamten Schritts Proben gesammelt. Die Abnahme ist linear, verhält sich jedoch so, als ob eine Anzahl von Zeilen, die dem AVG_RANGE_ROWS-Wert entsprechen, nicht Teil des Trends ist ... bis Sie den RANGE_HI_KEY treffen und sie plötzlich wie nicht eingezogene Schulden fallen. Sie können es in den Beispieldaten sehen, insbesondere in der Grafik.

Geben Sie hier die Bildbeschreibung ein

Beachten Sie den stetigen Rückgang der Zeilen, bis wir RANGE_HI_KEY und dann BOOM treffen, wobei der letzte AVG_RANGE_ROWS-Block plötzlich subtrahiert wird. Es ist auch leicht, in einem Diagramm zu erkennen.

Geben Sie hier die Bildbeschreibung ein

Zusammenfassend lässt sich sagen, dass die ungerade Behandlung von AVG_RANGE_ROWS die Berechnung von Zeilenschätzungen komplexer macht. Sie können jedoch jederzeit abgleichen, was der CE tut.

Was ist mit Exponential Backoff?

Exponential Backoff ist die Methode, die der neue Kardinalitätsschätzer (ab SQL Server 2014) verwendet, um bessere Schätzungen zu erhalten, wenn mehrere einspaltige Statistiken verwendet werden. Da es sich bei dieser Frage um eine einspaltige Statistik handelt, handelt es sich nicht um die EB-Formel.

Doug Lane
quelle