Auffinden von „ToTime“ anhand von Aggregaten anstelle eines Joins
Ich möchte eine wirklich wilde Abfrage teilen, die nur 1 Scan der Tabelle mit 1 logischen Lesevorgang benötigt. Im Vergleich dazu benötigt die beste andere Antwort auf der Seite, die Abfrage von Simon Kingston, zwei Scans.
Bei einem sehr großen Datensatz (17.408 Eingabezeilen, die 8.193 Ergebniszeilen erzeugen) benötigt es 574 CPU und 2645 Zeit, während die Abfrage von Simon Kingston 63.820 CPU und 37.108 Zeit in Anspruch nimmt.
Es ist möglich, dass die anderen Abfragen auf der Seite mit Indizes um ein Vielfaches besser abschneiden könnten, aber es ist interessant für mich, eine 111-fache CPU-Verbesserung und eine 14-fache Geschwindigkeitsverbesserung zu erreichen, indem ich einfach die Abfrage umschreibe.
(Bitte beachten Sie:Ich möchte Simon Kingston oder irgendjemand anderem gegenüber keineswegs respektlos sein; ich bin einfach nur begeistert, dass meine Idee für diese Abfrage so gut ankommt. Seine Abfrage ist besser als meine, da sie viel Leistung bietet und tatsächlich verständlich und wartbar ist , im Gegensatz zu meinem.)
Hier ist die unmögliche Abfrage. Es ist schwer zu verstehen. Es war schwer zu schreiben. Aber es ist großartig. :)
WITH Ranks AS (
SELECT
T = Dense_Rank() OVER (ORDER BY Time, Num),
N = Dense_Rank() OVER (PARTITION BY Name ORDER BY Time, Num),
*
FROM
#Data D
CROSS JOIN (
VALUES (1), (2)
) X (Num)
), Items AS (
SELECT
FromTime = Min(Time),
ToTime = Max(Time),
Name = IsNull(Min(CASE WHEN Num = 2 THEN Name END), Min(Name)),
I = IsNull(Min(CASE WHEN Num = 2 THEN T - N END), Min(T - N)),
MinNum = Min(Num)
FROM
Ranks
GROUP BY
T / 2
)
SELECT
FromTime = Min(FromTime),
ToTime = CASE WHEN MinNum = 2 THEN NULL ELSE Max(ToTime) END,
Name
FROM Items
GROUP BY
I, Name, MinNum
ORDER BY
FromTime
Hinweis:Dies erfordert SQL 2008 oder höher. Damit es in SQL 2005 funktioniert, ändern Sie die VALUES-Klausel in SELECT 1 UNION ALL SELECT 2 .
Aktualisierte Abfrage
Nachdem ich ein wenig darüber nachgedacht hatte, wurde mir klar, dass ich zwei getrennte logische Aufgaben gleichzeitig erledigte, was die Abfrage unnötig kompliziert machte:1) Beschneide Zwischenzeilen, die keinen Einfluss auf die endgültige Lösung haben (Zeilen, die nicht beginnen eine neue Aufgabe) und 2) ziehen Sie den "ToTime"-Wert aus der nächsten Zeile. Durch Ausführen von #1 vorher #2, die Abfrage ist einfacher und benötigt etwa die Hälfte der CPU!
Hier ist also die vereinfachte Abfrage, die zuerst dann die Zeilen entfernt, die uns nicht interessieren Ruft den ToTime-Wert unter Verwendung von Aggregaten statt eines JOINs ab. Ja, es hat 3 Windowing-Funktionen statt 2, aber letztendlich hat es wegen der weniger Zeilen (nach dem Beschneiden derjenigen, die uns nicht interessieren) weniger Arbeit zu tun:
WITH Ranks AS (
SELECT
Grp =
Row_Number() OVER (ORDER BY Time)
- Row_Number() OVER (PARTITION BY Name ORDER BY Time),
[Time], Name
FROM #Data D
), Ranges AS (
SELECT
Result = Row_Number() OVER (ORDER BY Min(R.[Time]), X.Num) / 2,
[Time] = Min(R.[Time]),
R.Name, X.Num
FROM
Ranks R
CROSS JOIN (VALUES (1), (2)) X (Num)
GROUP BY
R.Name, R.Grp, X.Num
)
SELECT
FromTime = Min([Time]),
ToTime = CASE WHEN Count(*) = 1 THEN NULL ELSE Max([Time]) END,
Name = IsNull(Min(CASE WHEN Num = 2 THEN Name ELSE NULL END), Min(Name))
FROM Ranges R
WHERE Result > 0
GROUP BY Result
ORDER BY FromTime;
Diese aktualisierte Abfrage hat die gleichen Probleme, die ich in meiner Erklärung dargestellt habe, sie sind jedoch einfacher zu lösen, da ich mich nicht mit den zusätzlichen unnötigen Zeilen befasse. Ich sehe auch, dass die Row_Number() / 2 Wert von 0 musste ich ausschließen, und ich bin mir nicht sicher, warum ich ihn nicht aus der vorherigen Abfrage ausgeschlossen habe, aber auf jeden Fall funktioniert das perfekt und ist erstaunlich schnell!
Äußere Anwendung bringt Ordnung
Zuletzt ist hier eine Version, die im Grunde identisch mit der Abfrage von Simon Kingston ist, die meiner Meinung nach eine leichter verständliche Syntax hat.
SELECT
FromTime = Min(D.Time),
X.ToTime,
D.Name
FROM
#Data D
OUTER APPLY (
SELECT TOP 1 ToTime = D2.[Time]
FROM #Data D2
WHERE
D.[Time] < D2.[Time]
AND D.[Name] <> D2.[Name]
ORDER BY D2.[Time]
) X
GROUP BY
X.ToTime,
D.Name
ORDER BY
FromTime;
Hier ist das Setup-Skript, wenn Sie einen Leistungsvergleich für einen größeren Datensatz durchführen möchten:
CREATE TABLE #Data (
RecordId int,
[Time] int,
Name varchar(10)
);
INSERT #Data VALUES
(1, 10, 'Running'),
(2, 18, 'Running'),
(3, 21, 'Running'),
(4, 29, 'Walking'),
(5, 33, 'Walking'),
(6, 57, 'Running'),
(7, 66, 'Running'),
(8, 77, 'Running'),
(9, 81, 'Walking'),
(10, 89, 'Running'),
(11, 93, 'Walking'),
(12, 99, 'Running'),
(13, 107, 'Running'),
(14, 113, 'Walking'),
(15, 124, 'Walking'),
(16, 155, 'Walking'),
(17, 178, 'Running');
GO
insert #data select recordid + (select max(recordid) from #data), time + (select max(time) +25 from #data), name from #data
GO 10
Erklärung
Hier ist die Grundidee hinter meiner Anfrage.
-
Die Zeiten, die einen Wechsel darstellen, müssen in zwei benachbarten Zeilen erscheinen, eine zum Beenden der vorherigen Aktivität und eine zum Beginnen der nächsten Aktivität. Die natürliche Lösung hierfür ist ein Join, sodass eine Ausgabezeile aus ihrer eigenen Zeile (für die Startzeit) und der nächsten Änderung ziehen kann Zeile (für die Endzeit).
-
Meine Abfrage erfüllt jedoch die Notwendigkeit, Endzeiten in zwei verschiedenen Zeilen erscheinen zu lassen, indem die Zeile zweimal wiederholt wird, mit
CROSS JOIN (VALUES (1), (2)). Wir haben jetzt alle unsere Zeilen dupliziert. Die Idee ist, dass wir, anstatt einen JOIN zu verwenden, um spaltenübergreifende Berechnungen durchzuführen, eine Form der Aggregation verwenden, um jedes gewünschte Zeilenpaar zu einer zusammenzufassen. -
Die nächste Aufgabe besteht darin, jede doppelte Zeile ordnungsgemäß aufzuteilen, sodass eine Instanz zum vorherigen Paar und eine zum nächsten Paar gehört. Dies wird mit der T-Spalte erreicht, einer
ROW_NUMBER()geordnet nachTime, und dann durch 2 geteilt (obwohl ich es geändert habe, mache ein DENSE_RANK() für Symmetrie, da es in diesem Fall denselben Wert wie ROW_NUMBER zurückgibt). Aus Effizienzgründen habe ich die Division im nächsten Schritt durchgeführt, damit die Zeilennummer in einer anderen Berechnung wiederverwendet werden kann (lesen Sie weiter). Da die Zeilennummer bei 1 beginnt und die Division durch 2 implizit in int konvertiert, hat dies den Effekt, dass die Sequenz0 1 1 2 2 3 3 4 4 ...erzeugt wird was das gewünschte Ergebnis hat:durch Gruppieren nach diesem berechneten Wert, da wir auch nachNumgeordnet haben in der Zeilennummer haben wir jetzt erreicht, dass alle Sätze nach dem ersten aus einer Num =2 aus der "vorherigen" Zeile und einer Num =1 aus der "nächsten" Zeile bestehen. -
Die nächste schwierige Aufgabe besteht darin, einen Weg zu finden, die Zeilen zu eliminieren, die uns nicht interessieren, und irgendwie die Startzeit eines Blocks in dieselbe Zeile wie die Endzeit eines Blocks zu bringen. Was wir wollen, ist eine Möglichkeit, jedem einzelnen Satz von Laufen oder Gehen eine eigene Nummer zuzuweisen, damit wir danach gruppieren können.
DENSE_RANK()ist eine natürliche Lösung, aber ein Problem ist, dass es auf jeden Wert inORDER BYachtet -Klausel - wir haben keine Syntax, umDENSE_RANK() OVER (PREORDER BY Time ORDER BY Name)auszuführen damit dieTimeverursacht nicht denRANKBerechnung zu ändern, außer bei jeder Änderung inName. Nach einigem Nachdenken wurde mir klar, dass ich etwas von der Logik hinter Itzik Ben-Gans Lösung für gruppierte Inseln abschreiben konnte, und ich fand heraus, dass der Rang der Zeilen nachTimegeordnet ist , subtrahiert vom Rang der durchNamepartitionierten Zeilen und nachTimegeordnet , würde einen Wert ergeben, der für jede Zeile in derselben Gruppe gleich ist, sich aber von anderen Gruppen unterscheidet. Die generische Technik gruppierter Inseln besteht darin, zwei berechnete Werte zu erstellen, die beide im Gleichschritt mit den Zeilen aufsteigen, z. B.4 5 6und1 2 3, die beim Subtrahieren denselben Wert ergeben (in diesem Beispielfall3 3 3als Ergebnis von4 - 1,5 - 2, und6 - 3). Hinweis:Ich habe zunächst mitROW_NUMBER()begonnen für meinNBerechnung, aber es funktionierte nicht. Die richtige Antwort warDENSE_RANK()obwohl es mir leid tut, sagen zu müssen, dass ich mich nicht erinnere, warum ich das damals abgeschlossen habe, und ich müsste noch einmal eintauchen, um es herauszufinden. Aber wie auch immer, das istT-Nberechnet:eine Zahl, die gruppiert werden kann, um jede "Insel" eines Status (entweder Laufen oder Gehen) zu isolieren. -
Aber das war noch nicht das Ende, denn es gibt einige Falten. Zunächst einmal enthält die "nächste" Zeile in jeder Gruppe die falschen Werte für
Name,N, undT. Wir umgehen dies, indem wir aus jeder Gruppe den Wert ausNum = 2auswählen Zeile, wenn es existiert (aber wenn nicht, dann verwenden wir den verbleibenden Wert). Dies ergibt Ausdrücke wieCASE WHEN NUM = 2 THEN x END:Dadurch werden die falschen "nächsten" Zeilenwerte ordnungsgemäß ausgesondert. -
Nach einigem Experimentieren stellte ich fest, dass es nicht ausreichte, nach
T - Nzu gruppieren allein, weil sowohl die Gehgruppen als auch die Laufgruppen den gleichen berechneten Wert haben können (im Fall meiner bis zu 17 bereitgestellten Beispieldaten gibt es zweiT - NWerte von 6). Sondern einfach nachNamegruppieren löst auch dieses Problem. Keine Gruppe von „Laufen“ oder „Gehen“ wird die gleiche Anzahl von dazwischenliegenden Werten vom entgegengesetzten Typ haben. Das heißt, da die erste Gruppe mit „Running“ beginnt und zwei „Walking“-Zeilen vor der nächsten „Running“-Gruppe dazwischenliegen, ist der Wert für N um 2 kleiner als der Wert fürTin dieser nächsten "Running"-Gruppe. Mir ist gerade klar geworden, dass eine Möglichkeit, darüber nachzudenken, darin besteht, dassT - NDie Berechnung zählt die Anzahl der Zeilen vor der aktuellen Zeile, die NICHT zu demselben Wert "Running" oder "Walking" gehören. Einige Gedanken werden zeigen, dass dies wahr ist:Wenn wir zur dritten "Lauf"-Gruppe weitergehen, ist es nur die dritte Gruppe, da eine "Geh"-Gruppe sie trennt, also hat sie eine andere Anzahl von dazwischenliegenden Reihen, die hereinkommen davor, und da es an einer höheren Position beginnt, ist es hoch genug, dass die Werte nicht dupliziert werden können. -
Schließlich, da unsere letzte Gruppe nur aus einer Zeile besteht (es gibt keine Endzeit und wir müssen einen
NULLanzeigen stattdessen) musste ich eine Berechnung einwerfen, die verwendet werden konnte, um festzustellen, ob wir eine Endzeit hatten oder nicht. Dies wird mit demMin(Num)erreicht Ausdruck und schließlich feststellen, dass, wenn Min(Num) 2 war (was bedeutet, dass wir keine "nächste" Zeile hatten), dann einNULLangezeigt wird anstelle vonMax(ToTime)Wert.
Ich hoffe, diese Erklärung ist für die Leute von Nutzen. Ich weiß nicht, ob meine "Zeilenmultiplikations"-Technik allgemein nützlich und auf die meisten SQL-Abfrageschreiber in Produktionsumgebungen anwendbar ist, da sie schwer zu verstehen und zu warten ist und sicherlich für die nächste Person, die die besucht, auftreten wird Code (die Reaktion ist wahrscheinlich "Was um alles in der Welt macht es da!?!", gefolgt von einem schnellen "Zeit zum Umschreiben!").
Wenn Sie es bis hierher geschafft haben, dann danke ich Ihnen für Ihre Zeit und dafür, dass Sie sich meinen kleinen Ausflug in ein unglaublich lustiges SQL-Puzzle-Land gegönnt haben.
Überzeugen Sie sich selbst
A.k.a. Simulieren eines "PREORDER BY":
Eine letzte Anmerkung. Um zu sehen, wie T - N erledigt die Aufgabe – und beachten Sie, dass die Verwendung dieses Teils meiner Methode möglicherweise nicht allgemein auf die SQL-Community anwendbar ist – führen Sie die folgende Abfrage für die ersten 17 Zeilen der Beispieldaten aus:
WITH Ranks AS (
SELECT
T = Dense_Rank() OVER (ORDER BY Time),
N = Dense_Rank() OVER (PARTITION BY Name ORDER BY Time),
*
FROM
#Data D
)
SELECT
*,
T - N
FROM Ranks
ORDER BY
[Time];
Dies ergibt:
RecordId Time Name T N T - N
----------- ---- ---------- ---- ---- -----
1 10 Running 1 1 0
2 18 Running 2 2 0
3 21 Running 3 3 0
4 29 Walking 4 1 3
5 33 Walking 5 2 3
6 57 Running 6 4 2
7 66 Running 7 5 2
8 77 Running 8 6 2
9 81 Walking 9 3 6
10 89 Running 10 7 3
11 93 Walking 11 4 7
12 99 Running 12 8 4
13 107 Running 13 9 4
14 113 Walking 14 5 9
15 124 Walking 15 6 9
16 155 Walking 16 7 9
17 178 Running 17 10 7
Der wichtige Teil ist, dass jede Gruppe von "Walking" oder "Running" den gleichen Wert für T - N hat die sich von allen anderen Gruppen mit demselben Namen unterscheidet.
Leistung
Ich möchte nicht darauf eingehen, dass meine Abfrage schneller ist als die anderer Leute. Angesichts dessen, wie auffällig der Unterschied ist (wenn es keine Indizes gibt), wollte ich die Zahlen jedoch in einem Tabellenformat anzeigen. Dies ist eine gute Technik, wenn eine hohe Leistung dieser Art von Zeile-zu-Zeile-Korrelation benötigt wird.
Vor jeder Abfrage habe ich DBCC FREEPROCCACHE; DBCC DROPCLEANBUFFERS; . Ich setze MAXDOP für jede Abfrage auf 1, um die zeitlich zusammenbrechenden Effekte der Parallelität zu entfernen. Ich habe jeden Ergebnissatz in Variablen ausgewählt, anstatt sie an den Client zurückzugeben, um nur die Leistung und nicht die Client-Datenübertragung zu messen. Allen Abfragen wurden die gleichen ORDER BY-Klauseln gegeben. Alle Tests verwendeten 17.408 Eingabezeilen mit 8.193 Ergebniszeilen.
Aus folgenden Personen/Gründen werden keine Ergebnisse angezeigt:
RichardTheKiwi *Could not test--query needs updating*
ypercube *No SQL 2012 environment yet :)*
Tim S *Did not complete tests within 5 minutes*
Ohne Index:
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 344 344 99 0
Simon Kingston 68672 69582 549203 49
Mit Index CREATE UNIQUE CLUSTERED INDEX CI_#Data ON #Data (Time); :
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 328 336 99 0
Simon Kingston 70391 71291 549203 49 * basically not worse
Mit Index CREATE UNIQUE CLUSTERED INDEX CI_#Data ON #Data (Time, Name); :
CPU Duration Reads Writes
----------- ----------- ----------- -----------
ErikE 375 414 359 0 * IO WINNER
Simon Kingston 172 189 38273 0 * CPU WINNER
Die Moral der Geschichte lautet also:
Geeignete Indizes sind wichtiger als Abfragezauberei
Mit dem entsprechenden Index gewinnt die Version von Simon Kingston insgesamt, insbesondere wenn es um die Abfragekomplexität/Wartbarkeit geht.
Beachte diese Lektion gut! 38.000 Lesevorgänge sind nicht wirklich viele, und Simon Kingstons Version lief in der Hälfte der Zeit wie meine. Die Geschwindigkeitssteigerung meiner Abfrage war ausschließlich darauf zurückzuführen, dass es keinen Index in der Tabelle gab, und die damit einhergehenden katastrophalen Kosten für jede Abfrage, die einen Join benötigte (was bei mir nicht der Fall war):ein Hash-Match mit vollständigem Tabellenscan, das seine Leistung beeinträchtigte. Mit einem Index konnte seine Abfrage eine verschachtelte Schleife mit einer geclusterten Indexsuche (auch bekannt als Lesezeichensuche) ausführen, was die Dinge wirklich machte schnell.
Es ist interessant, dass ein geclusterter Index für die Zeit allein nicht ausreichte. Obwohl Zeiten eindeutig waren, was bedeutet, dass nur ein Name pro Zeit vorkam, musste der Name dennoch Teil des Indexes sein, um ihn richtig zu verwenden.
Das Hinzufügen des gruppierten Index zur Tabelle, wenn er voll mit Daten war, dauerte weniger als 1 Sekunde! Vernachlässigen Sie Ihre Indizes nicht.
