Warum durchsucht meine SELECT DISTINCT TOP N-Abfrage die gesamte Tabelle?

27

Ich bin auf einige SELECT DISTINCT TOP NAbfragen 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);
Joe Obbish
quelle
Ein Cursor könnte sogar für 10 funktionieren
paparazzo

Antworten:

29

Es scheint drei verschiedene Optimierungsregeln zu geben, die den DISTINCTVorgang 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:

SELECT DISTINCT TOP 10 ID
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1, QUERYRULEOFF GbAggToSort, QUERYRULEOFF GbAggToHS, QUERYRULEOFF GbAggToStrm);

Nachricht 8622, Ebene 16, Status 1, Zeile 1

Der Abfrageprozessor konnte aufgrund der in dieser Abfrage definierten Hinweise keinen Abfrageplan erstellen. Senden Sie die Abfrage erneut, ohne Hinweise anzugeben und ohne SET FORCEPLAN zu verwenden.

GbAggToSortImplementiert das Group-By-Aggregat (distinct) als verschiedene Sortierung. Dies ist ein Blockierungsoperator, der alle Daten aus der Eingabe liest, bevor Zeilen erstellt werden. GbAggToStrmImplementiert das Group-by-Aggregat als Stream-Aggregat (was in dieser Instanz auch eine Eingabesortierung erfordert). Dies ist auch ein Blockierungsoperator. GbAggToHSimplementiert 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.

Der logische Operator "Flow Distinct" durchsucht die Eingabe und entfernt Duplikate. Während der Operator "Distinct" alle Eingaben verbraucht, bevor eine Ausgabe erstellt wird, gibt der Operator "Flow Distinct" jede Zeile so zurück, wie sie aus der Eingabe abgerufen wird (es sei denn, diese Zeile ist ein Duplikat. In diesem Fall wird sie verworfen).

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:

DROP TABLE IF EXISTS X_PLAN_GUIDE_TARGET;

CREATE TABLE X_PLAN_GUIDE_TARGET (VAL VARCHAR(10) NOT NULL);

INSERT INTO X_PLAN_GUIDE_TARGET WITH (TABLOCK)
SELECT CAST(N % 10000 AS VARCHAR(10))
FROM dbo.GetNums(10000000);

UPDATE STATISTICS X_PLAN_GUIDE_TARGET WITH FULLSCAN;

-- run this query
SELECT DISTINCT TOP 10 VAL  FROM X_PLAN_GUIDE_TARGET  OPTION (MAXDOP 1)

Holen Sie sich das Planhandle und erstellen Sie daraus einen Planleitfaden:

-- plan handle is 0x060007009014BC025097E88F6C01000001000000000000000000000000000000000000000000000000000000
SELECT qs.plan_handle, st.text FROM 
sys.dm_exec_query_stats AS qs   
CROSS APPLY sys.dm_exec_sql_text(qs.sql_handle) AS st  
WHERE st.text LIKE '%X[_]PLAN[_]GUIDE[_]TARGET%'
ORDER BY last_execution_time DESC;

EXEC sp_create_plan_guide_from_handle 
'EVIL_PLAN_GUIDE', 
0x060007009014BC025097E88F6C01000001000000000000000000000000000000000000000000000000000000;

Planhinweise arbeiten nur mit dem genauen Abfragetext. Kopieren Sie ihn also aus dem Planhinweis zurück:

SELECT query_text
FROM sys.plan_guides
WHERE name = 'EVIL_PLAN_GUIDE';

Setzen Sie die Daten zurück:

TRUNCATE TABLE X_PLAN_GUIDE_TARGET;

INSERT INTO X_PLAN_GUIDE_TARGET WITH (TABLOCK)
SELECT REPLICATE(CHAR(65 + (N / 100000 ) % 10 ), 10)
FROM dbo.GetNums(10000000);

Abrufen eines Abfrageplans für die Abfrage mit angewendetem Planungshandbuch:

SELECT DISTINCT TOP 10 VAL  FROM X_PLAN_GUIDE_TARGET  OPTION (MAXDOP 1)

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 FORAbfragehinweis erreicht werden:

DECLARE @j INT = 10;

SELECT DISTINCT TOP (@j) VAL
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1, OPTIMIZE FOR (@j = 1));

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_HEAPund 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()und RAND(). Tut LAG()jedoch den Trick für diese Abfrage. Das Abfrageoptimierungsprogramm erwartet 10 Millionen verschiedene Werte für den LAGAusdruck, wodurch ein Hash-Übereinstimmungsplan (flow distinct) ausgelöst wird :

SELECT DISTINCT TOP 10 LAG(VAL, 0) OVER (ORDER BY (SELECT NULL)) AS ID
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1);

Auf meinem Computer durchsucht diese Abfrage 892800 Zeilen X_10_DISTINCT_HEAPund wird in 1165 ms mit 1109 ms CPU-Zeit und 2537 logischen Lesevorgängen abgeschlossen LAG(). @Paul White schlug vor, die Stapelverarbeitung für diese Abfrage zu versuchen. In SQL Server 2016 können wir sogar mit Stapelverarbeitung arbeiten MAXDOP 1. Eine Möglichkeit, eine Stapelverarbeitung für eine Rowstore-Tabelle zu erhalten, besteht darin, eine leere CCI wie folgt zu verknüpfen:

CREATE TABLE #X_DUMMY_CCI (ID INT NOT NULL);

CREATE CLUSTERED COLUMNSTORE INDEX X_DUMMY_CCI ON #X_DUMMY_CCI;

SELECT DISTINCT TOP 10 VAL
FROM
(
    SELECT LAG(VAL, 1) OVER (ORDER BY (SELECT NULL)) AS VAL
    FROM X_10_DISTINCT_HEAP
    LEFT OUTER JOIN #X_DUMMY_CCI ON 1 = 0
) t
WHERE t.VAL IS NOT NULL
OPTION (MAXDOP 1);

Dieser Code führt zu diesem Abfrageplan .

Paul wies darauf hin, dass ich die zu verwendende Abfrage ändern musste, LAG(..., 1)da LAG(..., 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 SUBSTRINGAusdruck verwenden, der immer eine leere Zeichenfolge zurückgibt. SQL Server geht nicht davon aus, dass dies die SUBSTRINGAnzahl 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:

SELECT DISTINCT TOP 10 VAL + SUBSTRING(CAST(PK AS VARCHAR(10)), 11, 1)
FROM X_10_DISTINCT_CI
OPTION (MAXDOP 1);

Auf meinem Computer durchsucht diese Abfrage 900000 Zeilen X_10_DISTINCT_CIund 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 NAbfragen alle Zeilen aus der Tabelle gelesen werden, wenn N> = 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 das OPTIMIZE FORZeilenziel mithilfe des Hinweises verringern oder die geschätzte Anzahl unterschiedlicher Zeilen mithilfe von LAG()oder SUBSTRINGin einer eindeutigen Spalte erhöhen .

Joe Obbish
quelle
12

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 :

CREATE CLUSTERED COLUMNSTORE INDEX CCSI 
ON dbo.X_10_DISTINCT_HEAP;

Die einfache Abfrage:

SELECT DISTINCT TOP (10)
    XDH.VAL 
FROM dbo.X_10_DISTINCT_HEAP AS XDH
OPTION (MAXDOP 1);

dann gibt:

Ausführungsplan

Tabelle 'X_10_DISTINCT_HEAP'. Scananzahl 1,
 logische Lesevorgänge 0, physikalische Lesevorgänge 0, Vorauslesevorgänge 0, 
 lob logische Lesevorgänge 66 , lob physikalische Lesevorgänge 0, lob Vorauslesevorgänge 0.
Tabelle 'X_10_DISTINCT_HEAP'. Segment liest 13, Segment übersprungen 0.

 SQL Server-Ausführungszeiten:
   CPU-Zeit = 0 ms, abgelaufene Zeit = 11 ms.

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:

SET ROWCOUNT 10;

SELECT DISTINCT 
    XDH.VAL
FROM dbo.X_10_DISTINCT_HEAP AS XDH
OPTION (FAST 1);

SET ROWCOUNT 0;

Gibt:

Flow Distinct Execution Plan

Tabelle 'X_10_DISTINCT_HEAP'. Scananzahl 1,
 logische Lesevorgänge 0, physikalische Lesevorgänge 0, Vorauslesevorgänge 0, 
 lob logisch lautet 20 , lob physikalische Lesevorgänge 0, lob Vorauslesevorgänge 0.
Tabelle 'X_10_DISTINCT_HEAP'. Segment liest 4 , Segment übersprungen 0.

 SQL Server-Ausführungszeiten:
   CPU-Zeit = 640 ms, abgelaufene Zeit = 680 ms.

Dies ist langsamer als wenn die Tabelle als Rowstore-Heap organisiert ist.

Paul White sagt GoFundMonica
quelle
4

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:

  • Im TOPrekursiven Teil nicht erlaubt. Wir verwenden ROW_NUMBER()stattdessen eine Unterabfrage und .
  • Wir können nicht mehrfach auf den konstanten Teil verweisen oder ihn LEFT JOINoder ihn NOT IN (SELECT id FROM cte)aus dem rekursiven Teil verwenden. Um dies zu umgehen, erstellen wir einen VARCHARString, der alle idWerte sammelt, die STRING_AGGder hierarchyID ähneln oder mit der hierarchyID vergleichbar sind LIKE.

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.

WITH ct (id, found, list) AS
  ( SELECT TOP (1) id, 1, CAST('/' + id + '/' AS VARCHAR(MAX))
    FROM x_large_table_2
  UNION ALL
    SELECT y.ID, ct.found + 1, CAST(ct.list + y.id + '/' AS VARCHAR(MAX))
    FROM ct
      CROSS APPLY 
      ( SELECT x.id, 
               rn = ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
        FROM x_large_table_2 AS x
        WHERE ct.list NOT LIKE '%/' + id + '/%'
      ) AS y
    WHERE ct.found < 3         -- the TOP (n) parameter here
      AND y.rn = 1
  )
SELECT id FROM ct ;

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:

WITH ct (unique_key, id, found, list) AS
  ( SELECT TOP (1) unique_key, id, 1, CAST(CONCAT('/',id, '/') AS VARCHAR(MAX))
    FROM x_large_table_2
  UNION ALL
    SELECT y.unique_key, y.ID, ct.found + 1, 
        CAST(CONCAT(ct.list, y.id, '/') AS VARCHAR(MAX))
    FROM ct
      CROSS APPLY 
      ( SELECT x.unique_key, x.id, 
               rn = ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
        FROM x_large_table_2 AS x
        WHERE x.unique_key > ct.unique_key
          AND ct.list NOT LIKE '%/' + id + '/%'
      ) AS y
    WHERE ct.found < 5       -- the TOP (n) parameter here
      AND y.rn = 1
  )
-- SELECT * FROM ct ;        -- for debugging
SELECT id FROM ct ;
ypercubeᵀᴹ
quelle
Bei dieser Lösung tritt ein ziemlich subtiles Leistungsproblem auf. Es endet damit, dass ein zusätzlicher Suchvorgang für die Tabelle ausgeführt wird, nachdem der N-te Wert gefunden wurde. Wenn es also 10 verschiedene Werte für eine Top 10 gibt, wird nach einem 11. Wert gesucht, der nicht vorhanden ist. Sie erhalten einen zusätzlichen vollständigen Scan und die 10 Millionen ROW_NUMBER () - Berechnungen summieren sich wirklich. Ich habe hier eine Problemumgehung, die die Abfrage 20X auf meinem Computer beschleunigt. Was denkst du? brentozar.com/pastetheplan/?id=SkDhAmFKe
Joe Obbish
2

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 APPLYOperator 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 wir TOPin den abgeleiteten Tabellen anstelle der ROW_NUMBER()Problemumgehung verwenden können. Ein großer Nachteil ist, dass der Abfragetext mit Nzunehmender Länge länger wird.

Hier ist eine Implementierung für die Abfrage gegen den Heap:

SELECT VAL
FROM (
    SELECT t1.VAL VAL1, t2.VAL VAL2, t3.VAL VAL3, t4.VAL VAL4, t5.VAL VAL5, t6.VAL VAL6, t7.VAL VAL7, t8.VAL VAL8, t9.VAL VAL9, t10.VAL VAL10
    FROM 
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP 
    ) t1
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t2 WHERE t2.VAL NOT IN (t1.VAL)
    ) t2
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t3 WHERE t3.VAL NOT IN (t1.VAL, t2.VAL)
    ) t3
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t4 WHERE t4.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL)
    ) t4
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t5 WHERE t5.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL)
    ) t5
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t6 WHERE t6.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL)
    ) t6
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t7 WHERE t7.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL)
    ) t7
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t8 WHERE t8.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL, t7.VAL)
    ) t8
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t9 WHERE t9.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL, t7.VAL, t8.VAL)
    ) t9
    OUTER APPLY
    ( 
    SELECT TOP 1 VAL FROM X_10_DISTINCT_HEAP t10 WHERE t10.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL, t7.VAL, t8.VAL, t9.VAL)
    ) t10
) t
UNPIVOT 
(
  VAL FOR VALS IN (VAL1, VAL2, VAL3, VAL4, VAL5, VAL6, VAL7, VAL8, VAL9, VAL10)
) AS upvt;

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:

DECLARE @j INT = 10;

SELECT DISTINCT TOP (@j) VAL
FROM X_10_DISTINCT_HEAP
OPTION (MAXDOP 1, OPTIMIZE FOR (@j = 1));

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:

SELECT VAL
FROM (
    SELECT t1.VAL VAL1, t2.VAL VAL2, t3.VAL VAL3, t4.VAL VAL4, t5.VAL VAL5, t6.VAL VAL6, t7.VAL VAL7, t8.VAL VAL8, t9.VAL VAL9, t10.VAL VAL10
    FROM 
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI 
    ) t1
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t2 WHERE PK > t1.PK AND t2.VAL NOT IN (t1.VAL)
    ) t2
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t3 WHERE PK > t2.PK AND t3.VAL NOT IN (t1.VAL, t2.VAL)
    ) t3
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t4 WHERE PK > t3.PK AND t4.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL)
    ) t4
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t5 WHERE PK > t4.PK AND t5.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL)
    ) t5
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t6 WHERE PK > t5.PK AND t6.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL)
    ) t6
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t7 WHERE PK > t6.PK AND t7.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL)
    ) t7
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t8 WHERE PK > t7.PK AND t8.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL, t7.VAL)
    ) t8
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t9 WHERE PK > t8.PK AND t9.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL, t7.VAL, t8.VAL)
    ) t9
    OUTER APPLY
    ( 
    SELECT TOP 1 PK, VAL FROM X_10_DISTINCT_CI t10 WHERE PK > t9.PK AND t10.VAL NOT IN (t1.VAL, t2.VAL, t3.VAL, t4.VAL, t5.VAL, t6.VAL, t7.VAL, t8.VAL, t9.VAL)
    ) t10
) t
UNPIVOT 
(
  VAL FOR VALS IN (VAL1, VAL2, VAL3, VAL4, VAL5, VAL6, VAL7, VAL8, VAL9, VAL10)
) AS upvt;

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 FORAbfrage 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 von sys.dm_exec_sessionsund zu betrachten sys.dm_exec_session_wait_stats. Sitzung 56 war die APPLYAbfrage und Sitzung 63 war die OPTIMIZE FORAbfrage.

Ausgabe von sys.dm_exec_sessions:

╔════════════╦══════════╦════════════════════╦═══════════════╗
 session_id  cpu_time  total_elapsed_time  logical_reads 
╠════════════╬══════════╬════════════════════╬═══════════════╣
         56      1360                1373          32030 
         63      2094                2091          30400 
╚════════════╩══════════╩════════════════════╩═══════════════╝

Es scheint einen klaren Vorteil in Bezug auf cpu_time und elapsed_time für die APPLYAbfrage zu geben.

Ausgabe von sys.dm_exec_session_wait_stats:

╔════════════╦════════════════════════════════╦═════════════════════╦══════════════╦══════════════════╦═════════════════════╗
 session_id            wait_type             waiting_tasks_count  wait_time_ms  max_wait_time_ms  signal_wait_time_ms 
╠════════════╬════════════════════════════════╬═════════════════════╬══════════════╬══════════════════╬═════════════════════╣
         56  SOS_SCHEDULER_YIELD                             340             0                 0                    0 
         56  MEMORY_ALLOCATION_EXT                            38             0                 0                    0 
         63  SOS_SCHEDULER_YIELD                             518             0                 0                    0 
         63  MEMORY_ALLOCATION_EXT                            98             0                 0                    0 
         63  RESERVED_MEMORY_ALLOCATION_EXT                  400             0                 0                    0 
╚════════════╩════════════════════════════════╩═════════════════════╩══════════════╩══════════════════╩═════════════════════╝

Die OPTIMIZE FORAbfrage 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.

Joe Obbish
quelle
1

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

SELECT distinct top (2)  [enumID]
FROM [ENRONbbb].[dbo].[docSVenum1]

declare @table table (enumID tinyint);
declare @enumID tinyint;
set @enumID = (select top (1) [enumID] from [docSVenum1]);
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
set @enumID = (select top (1) [enumID] from [docSVenum1] where [enumID] not in (select enumID from @table));
insert into @table values (@enumID);
select enumID from @table;
Paparazzo
quelle
Dieser Code hat auf meinem Computer 5 Sekunden gedauert. Es sieht so aus, als würden die Verknüpfungen mit der Tabellenvariablen einen erheblichen Mehraufwand verursachen. In der letzten Abfrage wurde die Tabellenvariable 892800 Mal gescannt. Diese Abfrage benötigte 1359 ms CPU-Zeit und 1374 ms verstrichene Zeit. Auf jeden Fall mehr als ich erwartet hatte. Das Hinzufügen eines Primärschlüssels zur Tabellenvariablen scheint zu helfen, obwohl ich nicht sicher bin, warum. Möglicherweise gibt es andere Optimierungsmöglichkeiten.
Joe Obbish
-4

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.

Bucket123
quelle
2
Nicht wirklich. Wenn ich eine Tabelle scanne und die ersten 20 Zeilen 10 unterschiedliche Werte haben, warum muss ich dann den Rest der Tabelle weiter scannen?
ypercubeᵀᴹ
2
Warum sollte es weiter suchen, wenn ich nur nach 10 frage? Es wurden bereits 10 verschiedene Werte gefunden, die beendet werden sollten. Das ist das Problem der Frage.
ypercubeᵀᴹ
3
Warum muss bei einer Top-N-Suche zuerst die gesamte Ergebnismenge angezeigt werden? Wenn es 10 verschiedene Werte hat und das ist alles, was Sie interessiert, könnte es aufhören, nach anderen Werten zu suchen. Wenn es die gesamte Ergebnismenge sortieren musste, um zu wissen, welche die ersten 10 sind, ist das eine andere Geschichte, aber wenn Sie nur 10 verschiedene Werte wollen, ohne sich um welche 10 zu kümmern, ist es nicht logisch, die gesamte Ergebnismenge zu erhalten.
Tom V - Team Monica
2
Stellen Sie sich vor, Sie hätten die Aufgabe, das angeforderte Set zurückzugeben. Sie wurden aufgefordert, eindeutige Top-Ten-Werte von mehreren zehn Millionen anzugeben, und Sie wurden nicht angewiesen, eine Sortierreihenfolge einzuhalten. Würden Sie sich verpflichtet fühlen, den gesamten Wertesatz durchzugehen, wenn Sie das Ergebnis erreicht hätten, nachdem Sie beispielsweise die ersten 100 von ihnen betrachtet haben? Das wäre einfach sinnlos. Die Implementierung dieser Logik in einem Datenbankprodukt ist eine andere Angelegenheit, aber Sie scheinen zu suggerieren, dass es logisch notwendig ist, die gesamte Tabelle nach diesem Problem zu durchsuchen , was es nicht ist.
Andriy M
4
@Marco: Ich bin anderer Meinung, das ist eine Antwort. Es kommt einfach so vor, dass der Antwortende mit der Prämisse der Frage nicht einverstanden ist und antwortet, was er / sie als Missverständnis des OP ansieht.
Andriy M