Ich bin auf einige SELECT DISTINCT TOP N
Abfragen gestoßen, die vom SQL Server-Abfrageoptimierungsprogramm schlecht optimiert zu sein scheinen. Betrachten wir zunächst ein einfaches Beispiel: eine Million-Zeilen-Tabelle mit zwei abwechselnden Werten. Ich werde die GetNums- Funktion verwenden, um die Daten zu generieren:
DROP TABLE IF EXISTS X_2_DISTINCT_VALUES;
CREATE TABLE X_2_DISTINCT_VALUES (PK INT IDENTITY (1, 1), VAL INT NOT NULL);
INSERT INTO X_2_DISTINCT_VALUES WITH (TABLOCK) (VAL)
SELECT N % 2
FROM dbo.GetNums(1000000);
UPDATE STATISTICS X_2_DISTINCT_VALUES WITH FULLSCAN;
Für die folgende Abfrage:
SELECT DISTINCT TOP 2 VAL
FROM X_2_DISTINCT_VALUES
OPTION (MAXDOP 1);
SQL Server kann zwei unterschiedliche Werte finden, indem nur die erste Datenseite der Tabelle durchsucht wird . Stattdessen werden jedoch alle Daten durchsucht . Warum scannt SQL Server nicht einfach, bis die angeforderte Anzahl unterschiedlicher Werte gefunden wurde?
Für diese Frage verwenden Sie bitte die folgenden Testdaten, die 10 Millionen Zeilen mit 10 verschiedenen Werten enthalten, die in Blöcken generiert wurden:
DROP TABLE IF EXISTS X_10_DISTINCT_HEAP;
CREATE TABLE X_10_DISTINCT_HEAP (VAL VARCHAR(10) NOT NULL);
INSERT INTO X_10_DISTINCT_HEAP WITH (TABLOCK)
SELECT REPLICATE(CHAR(65 + (N / 100000 ) % 10 ), 10)
FROM dbo.GetNums(10000000);
UPDATE STATISTICS X_10_DISTINCT_HEAP WITH FULLSCAN;
Antworten für eine Tabelle mit einem Clustered-Index sind ebenfalls zulässig:
DROP TABLE IF EXISTS X_10_DISTINCT_CI;
CREATE TABLE X_10_DISTINCT_CI (PK INT IDENTITY (1, 1), VAL VARCHAR(10) NOT NULL, PRIMARY KEY (PK));
INSERT INTO X_10_DISTINCT_CI WITH (TABLOCK) (VAL)
SELECT REPLICATE(CHAR(65 + (N / 100000 ) % 10 ), 10)
FROM dbo.GetNums(10000000);
UPDATE STATISTICS X_10_DISTINCT_CI WITH FULLSCAN;
Die folgende Abfrage durchsucht alle 10 Millionen Zeilen der Tabelle . Wie kann ich etwas bekommen, das nicht den gesamten Tisch scannt? Ich verwende SQL Server 2016 SP1.
SELECT DISTINCT TOP 10 VAL
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1);
quelle
Antworten:
Es scheint drei verschiedene Optimierungsregeln zu geben, die den
DISTINCT
Vorgang in der obigen Abfrage ausführen können . Die folgende Abfrage löst einen Fehler aus, der darauf hindeutet, dass die Liste vollständig ist:GbAggToSort
Implementiert das Group-By-Aggregat (distinct) als verschiedene Sortierung. Dies ist ein Blockierungsoperator, der alle Daten aus der Eingabe liest, bevor Zeilen erstellt werden.GbAggToStrm
Implementiert das Group-by-Aggregat als Stream-Aggregat (was in dieser Instanz auch eine Eingabesortierung erfordert). Dies ist auch ein Blockierungsoperator.GbAggToHS
implementiert als Hash-Match, was wir in dem schlechten Plan aus der Frage gesehen haben, aber es kann als Hash-Match (aggregiert) oder Hash-Match (flow distinct) implementiert werden.Der Hash-Match- Operator ( flow distinct ) ist eine Möglichkeit, dieses Problem zu lösen, da er nicht blockiert. SQL Server sollte in der Lage sein, den Scan zu stoppen, sobald genügend unterschiedliche Werte gefunden wurden.
Warum verwendet die Abfrage in der Frage Hash-Übereinstimmungen (Aggregate) anstelle von Hash-Übereinstimmungen (Flow-distinct)? Da sich die Anzahl der eindeutigen Werte in der Tabelle ändert, würde ich davon ausgehen, dass die Kosten für die Hash-Übereinstimmungsabfrage (flow distinct) sinken, da die Schätzung der Anzahl der Zeilen, die in die Tabelle gescannt werden müssen, sinken sollte. Ich würde erwarten, dass die Kosten für den Hash-Match-Plan (aggregiert) steigen, da die zu erstellende Hash-Tabelle größer wird. Eine Möglichkeit, dies zu untersuchen, besteht darin , einen Planungsleitfaden zu erstellen . Wenn ich zwei Kopien der Daten erstelle, aber einen Planleitfaden auf eine von ihnen anwende, sollte es mir möglich sein, die Hash-Übereinstimmung (aggregiert) mit der Hash-Übereinstimmung (eindeutig) nebeneinander mit denselben Daten zu vergleichen. Beachten Sie, dass ich dazu die Regeln des Abfrageoptimierers nicht deaktivieren kann, da für beide Pläne dieselbe Regel gilt (
GbAggToHS
).Hier ist eine Möglichkeit, den Plan zu finden, nach dem ich suche:
Holen Sie sich das Planhandle und erstellen Sie daraus einen Planleitfaden:
Planhinweise arbeiten nur mit dem genauen Abfragetext. Kopieren Sie ihn also aus dem Planhinweis zurück:
Setzen Sie die Daten zurück:
Abrufen eines Abfrageplans für die Abfrage mit angewendetem Planungshandbuch:
Dies hat den Hash-Match-Operator (flow distinct), den wir mit unseren Testdaten wollten. Beachten Sie, dass SQL Server erwartet, alle Zeilen aus der Tabelle zu lesen, und dass die geschätzten Kosten genau die gleichen sind wie für den Plan mit der Hash-Übereinstimmung (Aggregat). Die von mir durchgeführten Tests haben ergeben, dass die Kosten für die beiden Pläne identisch sind, wenn das Zeilenziel für den Plan größer oder gleich der Anzahl unterschiedlicher Werte ist, die SQL Server aus der Tabelle erwartet, die in diesem Fall einfach aus der Tabelle abgeleitet werden kann Statistiken. Leider wählt der Optimierer (für unsere Abfrage) die Hash-Übereinstimmung (aggregiert) über die Hash-Übereinstimmung (flussunabhängig), wenn die Kosten gleich sind. Wir sind also 0,0000001 Magic Optimizer-Einheiten vom gewünschten Plan entfernt.
Eine Möglichkeit, dieses Problem anzugehen, besteht darin, das Zeilenziel zu verringern. Wenn das Zeilenziel aus der Sicht des Optimierers kleiner ist als die eindeutige Anzahl der Zeilen, erhalten wir wahrscheinlich eine Hash-Übereinstimmung (Flow distinct). Dies kann mit dem
OPTIMIZE FOR
Abfragehinweis erreicht werden:Für diese Abfrage erstellt der Optimierer einen Plan, als ob die Abfrage nur die erste Zeile benötigt, aber wenn die Abfrage ausgeführt wird, werden die ersten 10 Zeilen zurückgegeben. Auf meinem Computer durchsucht diese Abfrage 892800 Zeilen
X_10_DISTINCT_HEAP
und wird in 299 ms mit 250 ms CPU-Zeit und 2537 logischen Lesevorgängen abgeschlossen.Beachten Sie, dass diese Technik nicht funktioniert, wenn die Statistik nur einen bestimmten Wert ausgibt. Dies kann bei Stichprobenstatistiken mit verzerrten Daten der Fall sein. In diesem Fall ist es jedoch unwahrscheinlich, dass Ihre Daten dicht genug gepackt sind, um die Verwendung solcher Techniken zu rechtfertigen. Sie verlieren möglicherweise nicht viel, wenn Sie alle Daten in der Tabelle scannen, insbesondere wenn dies parallel erfolgen kann.
Eine andere Möglichkeit, dieses Problem zu bekämpfen, besteht darin, die Anzahl der geschätzten unterschiedlichen Werte zu erhöhen, die SQL Server von der Basistabelle erwartet. Das war schwieriger als erwartet. Das Anwenden einer deterministischen Funktion kann möglicherweise die eindeutige Anzahl der Ergebnisse nicht erhöhen. Wenn dem Abfrageoptimierer diese mathematische Tatsache bekannt ist (einige Tests legen dies zumindest für unsere Zwecke nahe), erhöht die Anwendung deterministischer Funktionen (die alle Zeichenfolgenfunktionen enthalten ) nicht die geschätzte Anzahl unterschiedlicher Zeilen.
Viele der nicht deterministischen Funktionen funktionierten auch nicht, einschließlich der offensichtlichen Auswahl von
NEWID()
undRAND()
. TutLAG()
jedoch den Trick für diese Abfrage. Das Abfrageoptimierungsprogramm erwartet 10 Millionen verschiedene Werte für denLAG
Ausdruck, wodurch ein Hash-Übereinstimmungsplan (flow distinct) ausgelöst wird :Auf meinem Computer durchsucht diese Abfrage 892800 Zeilen
X_10_DISTINCT_HEAP
und wird in 1165 ms mit 1109 ms CPU-Zeit und 2537 logischen Lesevorgängen abgeschlossenLAG()
. @Paul White schlug vor, die Stapelverarbeitung für diese Abfrage zu versuchen. In SQL Server 2016 können wir sogar mit Stapelverarbeitung arbeitenMAXDOP 1
. Eine Möglichkeit, eine Stapelverarbeitung für eine Rowstore-Tabelle zu erhalten, besteht darin, eine leere CCI wie folgt zu verknüpfen:Dieser Code führt zu diesem Abfrageplan .
Paul wies darauf hin, dass ich die zu verwendende Abfrage ändern musste,
LAG(..., 1)
daLAG(..., 0)
anscheinend keine Berechtigung für die Fensteraggregatoptimierung besteht. Diese Änderung reduzierte die verstrichene Zeit auf 520 ms und die CPU-Zeit auf 454 ms.Beachten Sie, dass der
LAG()
Ansatz nicht der stabilste ist. Wenn Microsoft die Eindeutigkeitsannahme für die Funktion ändert, funktioniert sie möglicherweise nicht mehr. Es hat eine andere Schätzung mit dem Erbe CE. Auch diese Art der Optimierung gegen einen Haufen ist keine gute Idee. Wenn die Tabelle neu erstellt wird, kann es im schlimmsten Fall vorkommen, dass fast alle Zeilen aus der Tabelle gelesen werden müssen.Gegenüber einer Tabelle mit einer eindeutigen Spalte (wie dem Beispiel für einen gruppierten Index in der Frage) haben wir bessere Optionen. Zum Beispiel können wir den Optimierer überlisten, indem wir einen
SUBSTRING
Ausdruck verwenden, der immer eine leere Zeichenfolge zurückgibt. SQL Server geht nicht davon aus, dass dies dieSUBSTRING
Anzahl der unterschiedlichen Werte ändert. Wenn Sie diese also auf eine eindeutige Spalte wie PK anwenden, beträgt die geschätzte Anzahl der unterschiedlichen Zeilen 10 Millionen. Diese folgende Abfrage ruft den Hash-Match-Operator (flow distinct) ab:Auf meinem Computer durchsucht diese Abfrage 900000 Zeilen
X_10_DISTINCT_CI
und wird in 333 ms mit 297 ms CPU-Zeit und 3011 logischen Lesevorgängen abgeschlossen.Zusammenfassend scheint das Abfrageoptimierungsprogramm davon auszugehen, dass bei
SELECT DISTINCT TOP N
Abfragen alle Zeilen aus der Tabelle gelesen werden, wennN
> = die Anzahl der geschätzten unterschiedlichen Zeilen aus der Tabelle ist. Der Hash-Übereinstimmungsoperator (Aggregatoperator) kann die gleichen Kosten verursachen wie der Hash-Übereinstimmungsoperator (Flow-distinct-Operator), der Optimierer wählt jedoch immer den Aggregatoperator aus. Dies kann zu unnötigen logischen Lesevorgängen führen, wenn sich zu Beginn der Tabellensuche genügend unterschiedliche Werte befinden. Sie können den Optimierer auf zwei Arten dazu verleiten, den Hash-Match-Operator (Flow distinct) zu verwenden, indem Sie dasOPTIMIZE FOR
Zeilenziel mithilfe des Hinweises verringern oder die geschätzte Anzahl unterschiedlicher Zeilen mithilfe vonLAG()
oderSUBSTRING
in einer eindeutigen Spalte erhöhen .quelle
Sie haben Ihre eigenen Fragen bereits richtig beantwortet.
Ich möchte nur eine Bemerkung hinzufügen, die besagt, dass es am effizientesten ist, den gesamten Tisch zu scannen - wenn es sich um einen "Haufen" im Spaltenspeicher handelt :
Die einfache Abfrage:
dann gibt:
Hash Match (Flow Distinct) kann derzeit nicht im Batch-Modus ausgeführt werden. Die Methoden, die dies verwenden, sind aufgrund des (unsichtbaren) teuren Übergangs von der Stapelverarbeitung zur Zeilenverarbeitung viel langsamer. Beispielsweise:
Gibt:
Dies ist langsamer als wenn die Tabelle als Rowstore-Heap organisiert ist.
quelle
Hier ist ein Versuch, eine wiederholte Teilabtastung (ähnlich einer Übersprungabtastung, aber nicht gleich einer Übersprungabtastung) unter Verwendung eines rekursiven CTE zu emulieren. Das Ziel - da wir keinen Index haben
(id)
- ist es, Sortierungen und Mehrfachscans auf dem Tisch zu vermeiden.Es werden einige Tricks ausgeführt, um einige rekursive CTE-Einschränkungen zu umgehen:
TOP
rekursiven Teil nicht erlaubt. Wir verwendenROW_NUMBER()
stattdessen eine Unterabfrage und .LEFT JOIN
oder ihnNOT IN (SELECT id FROM cte)
aus dem rekursiven Teil verwenden. Um dies zu umgehen, erstellen wir einenVARCHAR
String, der alleid
Werte sammelt, dieSTRING_AGG
der hierarchyID ähneln oder mit der hierarchyID vergleichbar sindLIKE
.Für einen Heap (unter der Annahme, dass die Spalte benannt ist
id
) test-1 auf rextester.com .Dies vermeidet - wie Tests gezeigt haben - nicht mehrere Scans, sondern führt zu einer guten Leistung, wenn auf den ersten Seiten unterschiedliche Werte gefunden werden. Wenn die Werte jedoch nicht gleichmäßig verteilt sind, werden möglicherweise mehrere Scans an großen Teilen der Tabelle durchgeführt - was natürlich zu einer schlechten Leistung führt.
und wenn die Tabelle geclustert ist (CI an
unique_key
), test-2 auf rextester.com .Dies verwendet den Clustered Index (
WHERE x.unique_key > ct.unique_key
), um mehrere Scans zu vermeiden:quelle
Der Vollständigkeit halber besteht eine andere Möglichkeit zur Lösung dieses Problems in der Verwendung von OUTER APPLY . Wir können einen
OUTER APPLY
Operator für jeden einzelnen Wert hinzufügen , den wir finden müssen. Dies ähnelt im Konzept dem rekursiven Ansatz von ypercube, lässt die Rekursion jedoch effektiv von Hand ausschreiben. Ein Vorteil ist, dass wirTOP
in den abgeleiteten Tabellen anstelle derROW_NUMBER()
Problemumgehung verwenden können. Ein großer Nachteil ist, dass der Abfragetext mitN
zunehmender Länge länger wird.Hier ist eine Implementierung für die Abfrage gegen den Heap:
Hier ist der aktuelle Abfrageplan für die obige Abfrage. Auf meinem Computer wird diese Abfrage in 713 ms mit 625 ms CPU-Zeit und 12605 logischen Lesevorgängen abgeschlossen. Wir bekommen alle 100k Zeilen einen neuen eindeutigen Wert, daher würde ich erwarten, dass diese Abfrage ungefähr 900000 * 10 * 0,5 = 4500000 Zeilen scannt. Theoretisch sollte diese Abfrage das Fünffache der logischen Lesevorgänge dieser Abfrage aus der anderen Antwort ausführen:
Diese Abfrage hat 2537 logische Lesevorgänge ausgeführt. 2537 * 5 = 12685, was ziemlich nahe an 12605 liegt.
Für die Tabelle mit dem Clustered-Index können wir bessere Ergebnisse erzielen. Dies liegt daran, dass wir den letzten gruppierten Schlüsselwert an die abgeleitete Tabelle übergeben können, um zu vermeiden, dass dieselben Zeilen zweimal durchsucht werden. Eine Implementierung:
Hier ist der aktuelle Abfrageplan für die obige Abfrage. Auf meinem Computer ist diese Abfrage in 154 ms mit 140 ms CPU-Zeit und 3203 logischen Lesevorgängen abgeschlossen. Dies schien etwas schneller zu laufen als die
OPTIMIZE FOR
Abfrage für die gruppierte Indextabelle. Ich habe das nicht erwartet, also habe ich versucht, die Leistung genauer zu messen. Meine Methode bestand darin, jede Abfrage zehnmal ohne Ergebnismengen auszuführen und die aggregierten Zahlen vonsys.dm_exec_sessions
und zu betrachtensys.dm_exec_session_wait_stats
. Sitzung 56 war dieAPPLY
Abfrage und Sitzung 63 war dieOPTIMIZE FOR
Abfrage.Ausgabe von
sys.dm_exec_sessions
:Es scheint einen klaren Vorteil in Bezug auf cpu_time und elapsed_time für die
APPLY
Abfrage zu geben.Ausgabe von
sys.dm_exec_session_wait_stats
:Die
OPTIMIZE FOR
Abfrage hat den zusätzlichen Wartetyp RESERVED_MEMORY_ALLOCATION_EXT . Ich weiß nicht genau, was das bedeutet. Es kann sich lediglich um eine Messung des Overheads im Hash-Match-Operator (flow distinct) handeln. In jedem Fall lohnt es sich vielleicht nicht, sich über einen Unterschied von 70 ms in der CPU-Zeit Gedanken zu machen.quelle
Ich denke, Sie haben eine Antwort auf die Frage, warum
dies eine Möglichkeit ist, dies zu beheben.
Ich weiß, dass es chaotisch aussieht, aber der Ausführungsplan besagt, dass die eindeutigen Top-2-Werte 84% der Kosten ausmachen
quelle
Ich denke, Sie müssen zurücktreten und Ihre Frage objektiv betrachten, um zu verstehen, was Sie sehen.
Wie ist es dem Abfrageoptimierer möglich, die 10 wichtigsten unterschiedlichen Werte auszuwählen, ohne zuerst die vollständige Liste der unterschiedlichen Werte zu identifizieren?
Select Distinct erfordert einen vollständigen Tabellenscan (oder einen umfassenden Indexscan), um die Ergebnismenge zu identifizieren. Denken Sie darüber nach - die letzte Zeile in der Tabelle enthält möglicherweise einen Wert, den sie noch nicht gesehen hat.
Select Distinct ist eine sehr stumpfe Waffe.
quelle