Kürzlich wurde ich von meinem Freund Erland Sommarskog in eine neue Inselherausforderung eingeführt. Es basiert auf einer Frage aus einem öffentlichen Datenbankforum. Die Herausforderung selbst ist nicht kompliziert zu handhaben, wenn bekannte Techniken verwendet werden, die hauptsächlich Fensterfunktionen verwenden. Diese Techniken erfordern jedoch trotz des Vorhandenseins eines unterstützenden Indexes eine explizite Sortierung. Dies wirkt sich auf die Skalierbarkeit und Reaktionszeit der Lösungen aus. Ich liebte Herausforderungen und machte mich auf die Suche nach einer Lösung, um die Anzahl der expliziten Sort-Operatoren im Plan zu minimieren, oder besser noch, deren Notwendigkeit ganz zu eliminieren. Und ich habe eine solche Lösung gefunden.
Ich beginne mit einer verallgemeinerten Form der Herausforderung. Ich zeige dann zwei Lösungen, die auf bekannten Techniken basieren, gefolgt von der neuen Lösung. Abschließend werde ich die Leistung der verschiedenen Lösungen vergleichen.
Ich empfehle, dass Sie versuchen, eine Lösung zu finden, bevor Sie meine implementieren.
Die Herausforderung
Ich werde eine verallgemeinerte Form von Erlands ursprünglicher Inselherausforderung vorstellen.
Verwenden Sie den folgenden Code, um eine Tabelle mit dem Namen T1 zu erstellen, und füllen Sie sie mit einem kleinen Satz von Beispieldaten:
SET NOCOUNT ON; TEMPDB VERWENDEN; DROP TABLE IF EXISTS dbo.T1 CREATE TABLE dbo.T1( grp VARCHAR(10) NOT NULL, ord INT NOT NULL, val VARCHAR(10) NOT NULL, CONSTRAINT PK_T1 PRIMARY KEY(grp, ord));GO INSERT INTO dbo. T1(grp, ord, val) WERTE ('Gruppe A', 1002, 'Y'), ('Gruppe A', 1003, 'Y'), ('Gruppe A', 1005, 'Y'), (' Gruppe A', 1007, 'N'), ('Gruppe A', 1011, 'N'), ('Gruppe A', 1013, 'N'), ('Gruppe A', 1017, 'Y'), ('Gruppe A', 1019, 'Y'), ('Gruppe A', 1023, 'N'), ('Gruppe A', 1029, 'N'), ('Gruppe B', 1001, 'X' ), ('Gruppe B', 1002, 'X'), ('Gruppe B', 1003, 'Z'), ('Gruppe B', 1005, 'Z'), ('Gruppe B', 1008, ' Z'), ('Gruppe B', 1013, 'Z'), ('Gruppe B', 1021, 'Y'), ('Gruppe B', 1034, 'Y'); Die Herausforderung lautet wie folgt:
Unter der Annahme einer Partitionierung basierend auf der Spalte grp und einer Sortierung basierend auf der Spalte ord, berechnen Sie fortlaufende Zeilennummern beginnend mit 1 innerhalb jeder aufeinanderfolgenden Gruppe von Zeilen mit demselben Wert in der Spalte val. Das Folgende ist das gewünschte Ergebnis für den gegebenen kleinen Satz von Beispieldaten:
grp ord val seqno-------- ----- ---- ------Gruppe A 1002 J 1Gruppe A 1003 J 2Gruppe A 1005 J 3Gruppe A 1007 N 1Gruppe A 1011 N 2Gruppe A 1013 N 3Gruppe A 1017 J 1Gruppe A 1019 J 2Gruppe A 1023 N 1Gruppe A 1029 N 2Gruppe B 1001 X 1Gruppe B 1002 X 2Gruppe B 1003 Z 1Gruppe B 1005 Z 2Gruppe B 1008 Z 3Gruppe B 1013 Z 4Gruppe B 1021 J 1Gruppe B 1034 J 2
Beachten Sie die Definition der Primärschlüsseleinschränkung basierend auf dem zusammengesetzten Schlüssel (grp, ord), was zu einem gruppierten Index führt, der auf demselben Schlüssel basiert. Dieser Index kann möglicherweise Fensterfunktionen unterstützen, die nach grp partitioniert und nach ord geordnet sind.
Um die Leistung Ihrer Lösung zu testen, müssen Sie die Tabelle mit größeren Mengen an Beispieldaten füllen. Verwenden Sie den folgenden Code, um die Hilfsfunktion GetNums zu erstellen:
CREATE FUNCTION dbo.GetNums(@low AS BIGINT =1, @high AS BIGINT) RETURN TABLEASRETURN WITH L0 AS ( SELECT 1 AS c FROM (VALUES(1),(1),(1),(1), (1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1),(1)) AS D (c) ), L1 AS ( SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B ), L2 AS ( SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B ), L3 AS ( SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B ), Nums AS ( SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum FROM L3 ) SELECT TOP(@high - @low + 1) rownum AS rn, @high + 1 - rownum AS op, @low - 1 + rownum AS n FROM Nums ORDER BY rownum;GO
Verwenden Sie den folgenden Code, um T1 zu füllen, nachdem Sie die Parameter, die die Anzahl der Gruppen, die Anzahl der Zeilen pro Gruppe und die Anzahl der unterschiedlichen Werte darstellen, wie gewünscht geändert haben:
DECLARE @numgroups AS INT =1000, @rowspergroup AS INT =10000, -- Test mit 1000 bis 10000 hier @uniquevalues AS INT =5; ALTER TABLE dbo.T1 DROP CONSTRAINT PK_T1; KÜRZE TABELLE dbo.T1; INSERT INTO dbo.T1 WITH(TABLOCK) (grp, ord, val) SELECT CAST(G.n AS VARCHAR(10)) AS grp, CAST(R.n AS INT) AS ord, CAST(ABS(CHECKSUM(NEWID())) % @uniquevalues + 1 AS VARCHAR(10)) AS val FROM dbo.GetNums(1, @numgroups) AS G CROSS JOIN dbo.GetNums(1, @rowspergroup) AS R; ALTER TABLE dbo.T1 ADD CONSTRAINT PK_T1 PRIMARY KEY CLUSTERED(grp, ord);
In meinen Leistungstests habe ich die Tabelle mit 1.000 Gruppen gefüllt, zwischen 1.000 und 10.000 Zeilen pro Gruppe (also 1 Mio. bis 10 Mio. Zeilen) und 5 unterschiedliche Werte. Ich habe ein SELECT INTO verwendet Anweisung, um das Ergebnis in eine temporäre Tabelle zu schreiben.
Mein Testcomputer verfügt über vier logische CPUs, auf denen SQL Server 2019 Enterprise ausgeführt wird.
Ich gehe davon aus, dass Sie eine Umgebung verwenden, die darauf ausgelegt ist, den Stapelmodus im Zeilenspeicher zu unterstützen, entweder direkt, z. B. mit SQL Server 2019 Enterprise Edition wie meiner, oder indirekt, indem Sie einen Dummy-Columnstore-Index für die Tabelle erstellen.
Denken Sie daran, zusätzliche Punkte, wenn Sie es schaffen, eine effiziente Lösung ohne explizites Sortieren im Plan zu finden. Viel Glück!
Wird ein Sort-Operator bei der Optimierung von Fensterfunktionen benötigt?
Bevor ich auf Lösungen eingehe, ein wenig Optimierungshintergrund, damit das, was Sie später in den Abfrageplänen sehen, sinnvoller ist.
Die gebräuchlichsten Techniken zum Lösen von Inselaufgaben wie der unseren beinhalten die Verwendung einer Kombination von Aggregat- und/oder Ranking-Fensterfunktionen. SQL Server kann solche Fensterfunktionen entweder mit einer Reihe älterer Zeilenmodusoperatoren (Segment, Sequence Project, Segment, Window Spool, Stream Aggregate) oder mit dem neueren und normalerweise effizienteren Window Aggregate-Operator im Batchmodus verarbeiten.
In beiden Fällen müssen die Operatoren, die die Berechnung der Fensterfunktion handhaben, die von den Fensterpartitionierungs- und -ordnungselementen geordneten Daten aufnehmen. Wenn Sie keinen unterstützenden Index haben, muss SQL Server natürlich einen Sort-Operator in den Plan einführen. Wenn Sie beispielsweise mehrere Fensterfunktionen in Ihrer Lösung mit mehr als einer eindeutigen Kombination aus Partitionierung und Reihenfolge haben, müssen Sie im Plan eine explizite Sortierung haben. Aber was ist, wenn Sie nur eine eindeutige Kombination aus Partitionierung und Sortierung und einen unterstützenden Index haben?
Die ältere Zeilenmodusmethode kann sich auf vorgeordnete Daten stützen, die aus einem Index aufgenommen werden, ohne dass ein expliziter Sort-Operator sowohl im seriellen als auch im parallelen Modus erforderlich ist. Der neuere Batch-Modus-Operator eliminiert viele der Ineffizienzen der älteren Zeilenmodus-Optimierung und hat die inhärenten Vorteile der Batch-Modus-Verarbeitung. Die aktuelle parallele Implementierung erfordert jedoch einen zwischengeschalteten Stapelmodus-Parallel-Sort-Operator, selbst wenn ein unterstützender Index vorhanden ist. Nur seine serielle Implementierung kann sich auf die Indexreihenfolge ohne Sort-Operator verlassen. Dies ist alles, um zu sagen, wenn der Optimierer eine Strategie wählen muss, um Ihre Fensterfunktion zu handhaben, vorausgesetzt, Sie haben einen unterstützenden Index, wird es im Allgemeinen eine der folgenden vier Optionen sein:
- Zeilenmodus, seriell, keine Sortierung
- Zeilenmodus, parallel, keine Sortierung
- Stapelmodus, seriell, keine Sortierung
- Batch-Modus, parallel, Sortierung
Es wird diejenige gewählt, die zu den niedrigsten Plankosten führt, vorausgesetzt natürlich, dass die Voraussetzungen für Parallelität und Stapelmodus erfüllt sind, wenn diese berücksichtigt werden. Damit der Optimierer einen parallelen Plan rechtfertigen kann, müssen die Vorteile der Parallelität normalerweise die zusätzliche Arbeit wie die Threadsynchronisierung überwiegen. Bei der obigen Option 4 müssen die Vorteile der Parallelität die übliche zusätzliche Arbeit, die mit der Parallelisierung verbunden ist, sowie die zusätzliche Sortierung aufwiegen.
Beim Experimentieren mit verschiedenen Lösungen für unsere Herausforderung hatte ich Fälle, in denen der Optimierer Option 2 oben gewählt hat. Es entschied sich trotz der Tatsache, dass das Zeilenmodusverfahren einige Ineffizienzen mit sich bringt, da die Vorteile der Parallelität und der fehlenden Sortierung zu einem Plan mit niedrigeren Kosten als die Alternativen führten. In einigen dieser Fälle führte das Erzwingen eines seriellen Plans mit einem Hinweis zu Option 3 oben und zu einer besseren Leistung.
Sehen wir uns vor diesem Hintergrund Lösungen an. Ich beginne mit zwei Lösungen, die sich auf bekannte Techniken für Inselaufgaben stützen, die einer expliziten Sortierung im Plan nicht entkommen können.
Lösung basierend auf bekannter Technik 1
Im Folgenden finden Sie die erste Lösung für unsere Herausforderung, die auf einer seit einiger Zeit bekannten Technik basiert:
WITH C AS( SELECT *, ROW_NUMBER() OVER(PARTITION BY grp ORDER BY ord) - ROW_NUMBER() OVER(PARTITION BY grp, val ORDER BY ord) AS island FROM dbo.T1)SELECT grp, ord, val , ROW_NUMBER() OVER(PARTITION BY grp, val, island ORDER BY ord) AS seqnoFROM C;
Ich werde es als bekannte Lösung 1 bezeichnen.
Der CTE namens C basiert auf einer Abfrage, die zwei Zeilennummern berechnet. Die erste (ich nenne sie rn1) ist nach grp partitioniert und nach ord geordnet. Die zweite (ich nenne sie rn2) wird durch grp und val partitioniert und nach ord geordnet. Da rn1 Lücken zwischen verschiedenen Gruppen desselben Werts aufweist und rn2 nicht, ist die Differenz zwischen rn1 und rn2 (Spalte mit Inselnamen) ein eindeutiger konstanter Wert für alle Zeilen mit denselben grp- und val-Werten. Es folgt das Ergebnis der inneren Abfrage, einschließlich der Ergebnisse der zweizeiligen Zahlenberechnungen, die nicht als separate Spalten zurückgegeben werden:
grp ord val rn1 rn2 island-------- ----- ---- ---- ---- -------Gruppe A 1002 J 1 1 0Gruppe A 1003 J 2 2 0Gruppe A 1005 J 3 3 0Gruppe A 1007 N 4 1 3Gruppe A 1011 N 5 2 3Gruppe A 1013 N 6 3 3Gruppe A 1017 J 7 4 3Gruppe A 1019 J 8 5 3Gruppe A 1023 N 9 4 5Gruppe A 1029 N 10 5 5Gruppe B 1001 X 1 1 0Gruppe B 1002 X 2 2 0Gruppe B 1003 Z 3 1 2Gruppe B 1005 Z 4 2 2Gruppe B 1008 Z 5 3 2Gruppe B 1013 Z 6 4 2Gruppe B 1021 Y 7 1 6Gruppe B 1034 Y 8 2 6
Was die äußere Abfrage noch zu tun hat, ist die Berechnung der Ergebnisspalte seqno mit der ROW_NUMBER-Funktion, partitioniert nach grp, val und island und geordnet nach ord, wodurch das gewünschte Ergebnis generiert wird.
Beachten Sie, dass Sie denselben Inselwert für verschiedene val-Werte innerhalb derselben Partition erhalten können, wie in der obigen Ausgabe. Aus diesem Grund ist es wichtig, grp, val und island als Fensterpartitionierungselemente zu verwenden und nicht nur grp und island.
Wenn Sie es mit einer Islands-Aufgabe zu tun haben, bei der Sie die Daten nach Island gruppieren und Gruppenaggregate berechnen müssen, würden Sie die Zeilen nach grp, val und island gruppieren. Aber das ist bei unserer Challenge nicht der Fall. Hier wurden Sie damit beauftragt, die Zeilennummern für jede Insel einzeln zu berechnen.
Abbildung 1 zeigt den Standardplan, den ich für diese Lösung auf meinem Computer erhalten habe, nachdem ich die Tabelle mit 10 Millionen Zeilen gefüllt habe.
Abbildung 1:Parallelplan für bekannte Lösung 1
Die Berechnung von rn1 kann sich auf die Indexreihenfolge stützen. Daher wählte der Optimierer für diesen Modus die Strategie „keine Sortierung + parallele Zeilen“ (erste Segment- und Sequenzprojektoperatoren im Plan). Da die Berechnungen sowohl von rn2 als auch von seqno ihre eigenen eindeutigen Kombinationen von Partitionierungs- und Ordnungselementen verwenden, ist eine explizite Sortierung für diejenigen unvermeidlich, unabhängig von der verwendeten Strategie. Daher wählte der Optimierer für beide die Strategie Sortieren + paralleler Stapelmodus. Dieser Plan beinhaltet zwei explizite Sort-Operatoren.
In meinem Leistungstest hat diese Lösung 3,68 Sekunden für 1 Million Zeilen und 43,1 Sekunden für 10 Millionen Zeilen benötigt.
Wie erwähnt, habe ich alle Lösungen auch getestet, indem ich einen seriellen Plan erzwungen habe (mit einem MAXDOP 1-Hinweis). Der serielle Plan für diese Lösung ist in Abbildung 1 dargestellt.
Abbildung 2:Serienplan für bekannte Lösung 1
Wie erwartet verwendet diesmal auch die Berechnung von rn1 die Batch-Modus-Strategie ohne vorangehenden Sort-Operator, aber der Plan hat immer noch zwei Sort-Operatoren für die nachfolgenden Berechnungen der Zeilennummer. Der serielle Plan schnitt auf meinem Computer mit allen von mir getesteten Eingabegrößen schlechter ab als der parallele Plan. Er dauerte 4,54 Sekunden für 1 Million Zeilen und 61,5 Sekunden für 10 Millionen Zeilen.
Lösung basierend auf bekannter Technik 2
Die zweite Lösung, die ich vorstellen werde, basiert auf einer brillanten Technik zur Inselerkennung, die ich vor einigen Jahren von Paul White gelernt habe. Es folgt der vollständige Lösungscode, der auf dieser Technik basiert:
WITH C1 AS( SELECT *, CASE WHEN val =LAG(val) OVER(PARTITION BY grp ORDER BY ord) THEN 0 ELSE 1 END AS isstart FROM dbo.T1),C2 AS( SELECT *, SUM(isstart) OVER(PARTITION BY grp ORDER BY ord ROWS UNBOUNDED PRECEDING) AS island FROM C1)SELECT grp, ord, val, ROW_NUMBER() OVER(PARTITION BY grp, island ORDER BY ord) AS seqnoFROM C2;
Ich werde diese Lösung als bekannte Lösung 2 bezeichnen.
Die Abfrage, die die CTE-C1-Berechnungen definiert, verwendet einen CASE-Ausdruck und die LAG-Fensterfunktion (partitioniert nach grp und geordnet nach ord), um eine Ergebnisspalte namens isstart zu berechnen. Diese Spalte hat den Wert 0, wenn der aktuelle val-Wert gleich dem vorherigen ist, andernfalls 1. Mit anderen Worten, es ist 1, wenn die Zeile die erste in einer Insel ist, und sonst 0.
Es folgt die Ausgabe der Abfrage, die C1 definiert:
grp ord val isstart-------- ----- ---- --------Gruppe A 1002 J 1Gruppe A 1003 J 0Gruppe A 1005 J 0Gruppe A 1007 N 1Gruppe A 1011 N 0Gruppe A 1013 N 0Gruppe A 1017 J 1Gruppe A 1019 J 0Gruppe A 1023 N 1Gruppe A 1029 N 0Gruppe B 1001 X 1Gruppe B 1002 X 0Gruppe B 1003 Z 1Gruppe B 1005 Z 0Gruppe B 1008 Z 0Gruppe B 1013 Z 0Gruppe B 1021 J 1Gruppe B 1034 Y 0
Die Magie der Inselerkennung findet im CTE C2 statt. Die ihn definierende Abfrage berechnet eine Inselkennung unter Verwendung der SUM-Fensterfunktion (ebenfalls partitioniert nach grp und geordnet nach ord), die auf die isstart-Spalte angewendet wird. Die Ergebnisspalte mit der Inselkennung wird als Insel bezeichnet. Innerhalb jeder Partition erhalten Sie 1 für die erste Insel, 2 für die zweite Insel und so weiter. Die Kombination der Spalten grp und island ist also eine Inselkennung, die Sie in Inselaufgaben verwenden können, die eine Gruppierung nach Insel beinhalten, falls relevant.
Es folgt die Ausgabe der Abfrage, die C2 definiert:
grp ord val isstart island-------- ----- ---- -------- -------Gruppe A 1002 J 1 1Gruppe A 1003 J 0 1Gruppe A 1005 J 0 1Gruppe A 1007 N 1 2Gruppe A 1011 N 0 2Gruppe A 1013 N 0 2Gruppe A 1017 J 1 3Gruppe A 1019 J 0 3Gruppe A 1023 N 1 4Gruppe A 1029 N 0 4Gruppe B 1001 X 1 1Gruppe B 1002 X 0 1Gruppe B 1003 Z 1 2Gruppe B 1005 Z 0 2Gruppe B 1008 Z 0 2Gruppe B 1013 Z 0 2Gruppe B 1021 J 1 3Gruppe B 1034 J 0 3
Zuletzt berechnet die äußere Abfrage die gewünschte Ergebnisspalte seqno mit einer ROW_NUMBER-Funktion, partitioniert nach grp und island und geordnet nach ord. Beachten Sie, dass sich diese Kombination aus Partitionierungs- und Ordnungselementen von derjenigen unterscheidet, die von den vorherigen Fensterfunktionen verwendet wird. Während sich die Berechnung der ersten beiden Fensterfunktionen möglicherweise auf die Indexreihenfolge stützen kann, kann dies bei der letzten nicht der Fall sein.
Abbildung 3 zeigt den Standardplan, den ich für diese Lösung erhalten habe.
Abbildung 3:Parallelplan für bekannte Lösung 2
Wie Sie im Plan sehen können, verwendet die Berechnung der ersten beiden Fensterfunktionen die Strategie „keine Sortierung + parallele Zeilen“ und die Berechnung der letzten die Strategie „Sortierung + parallele Stapelverarbeitung“.
Die Laufzeiten, die ich für diese Lösung erhielt, reichten von 2,57 Sekunden bei 1 Mio. Zeilen bis 46,2 Sekunden bei 10 Mio. Zeilen.
Als ich die serielle Verarbeitung erzwang, erhielt ich den in Abbildung 4 gezeigten Plan.
Abbildung 4:Serienplan für bekannte Lösung 2
Wie erwartet beruhen dieses Mal alle Fensterfunktionsberechnungen auf der Stapelmodusstrategie. Die ersten beiden ohne vorherige Sortierung, die letzten mit. Sowohl der parallele als auch der serielle Plan beinhalteten einen expliziten Sort-Operator. Der serielle Plan schnitt auf meiner Maschine mit den von mir getesteten Eingabegrößen besser ab als der parallele Plan. Die Laufzeiten, die ich für den erzwungenen seriellen Plan erhielt, reichten von 1,75 Sekunden bei 1 Mio. Zeilen bis 21,7 Sekunden bei 10 Mio. Zeilen.
Lösung basierend auf neuer Technik
Als Erland diese Herausforderung in einem privaten Forum vorstellte, war man skeptisch gegenüber der Möglichkeit, sie mit einer planoptimierten Abfrage ohne explizite Sortierung zu lösen. Das war alles, was ich hören musste, um mich zu motivieren. Also, hier ist, was ich mir ausgedacht habe:
WITH C1 AS( SELECT *, ROW_NUMBER() OVER(PARTITION BY grp ORDER BY ord) AS rn, LAG(val) OVER(PARTITION BY grp ORDER BY ord) AS prev FROM dbo.T1),C2 AS( SELECT *, MAX(CASE WHEN val =prev THEN NULL ELSE rn END) OVER(PARTITION BY grp ORDER BY ord ROWS UNBOUNDED PRECEDING) AS firstrn FROM C1)SELECT grp, ord, val, rn - firstrn + 1 AS seqnoFROM C2;Die Lösung verwendet drei Fensterfunktionen:LAG, ROW_NUMBER und MAX. Das Wichtigste hier ist, dass alle drei auf grp-Partitionierung und ord-Reihenfolge basieren, die an der unterstützenden Indexschlüsselreihenfolge ausgerichtet ist.
Die Abfrage, die den CTE C1 definiert, verwendet die ROW_NUMBER-Funktion, um Zeilennummern zu berechnen (rn-Spalte), und die LAG-Funktion, um den vorherigen val-Wert (prev-Spalte) zurückzugeben.
Hier ist die Ausgabe der Abfrage, die C1 definiert:
grp ord val rn prev-------- ----- ---- --- -----Gruppe A 1002 J 1 NULLGruppe A 1003 J 2 JGruppe A 1005 J 3 JGruppe A 1007 N 4 YGruppe A 1011 N 5 NGruppe A 1013 N 6 NGruppe A 1017 Y 7 NGruppe A 1019 Y 8 YGruppe A 1023 N 9 YGruppe A 1029 N 10 NGruppe B 1001 X 1 NULLGruppe B 1002 X 2 XGruppe B 1003 Z 3 XGruppe B 1005 Z 4 ZGruppe B 1008 Z 5 ZGruppe B 1013 Z 6 ZGruppe B 1021 J 7 ZGruppe B 1034 J 8 JBeachten Sie, wenn val und prev gleich sind, ist es nicht die erste Zeile in der Insel, andernfalls.
Basierend auf dieser Logik verwendet die Abfrage, die den CTE C2 definiert, einen CASE-Ausdruck, der rn zurückgibt, wenn die Zeile die erste in einer Insel ist, andernfalls NULL. Der Code wendet dann die MAX-Fensterfunktion auf das Ergebnis des CASE-Ausdrucks an und gibt das erste rn der Insel (firstrn-Spalte) zurück.
Hier ist die Ausgabe der Abfrage, die C2 definiert, einschließlich der Ausgabe des CASE-Ausdrucks:
grp ord val rn prev CASE firstrn-------- ----- ---- --- ----- ----- --------Gruppe A 1002 J 1 NULL 1 1Gruppe A 1003 J 2 J NULL 1Gruppe A 1005 J 3 J NULL 1Gruppe A 1007 N 4 J 4 4Gruppe A 1011 N 5 N NULL 4Gruppe A 1013 N 6 N NULL 4Gruppe A 1017 J 7 N 7 7Gruppe A 1019 Y 8 Y NULL 7Gruppe A 1023 N 9 Y 9 9Gruppe A 1029 N 10 N NULL 9Gruppe B 1001 X 1 NULL 1 1Gruppe B 1002 X 2 X NULL 1Gruppe B 1003 Z 3 X 3 3Gruppe B 1005 Z 4 Z NULL 3Gruppe B 1008 Z 5 Z NULL 3Gruppe B 1013 Z 6 Z NULL 3Gruppe B 1021 J 7 Z 7 7Gruppe B 1034 J 8 J NULL 7Was für die äußere Abfrage übrig bleibt, ist die gewünschte Ergebnisspalte seqno als rn minus firstrn plus 1 zu berechnen.
Abbildung 5 zeigt den standardmäßigen parallelen Plan, den ich für diese Lösung erhalten habe, als ich sie mit einer SELECT INTO-Anweisung getestet und das Ergebnis in eine temporäre Tabelle geschrieben habe.
Abbildung 5:Parallelplan für eine neue Lösung
In diesem Plan gibt es keine expliziten Sortieroperatoren. Alle drei Fensterfunktionen werden jedoch mit der Modusstrategie „keine Sortierung + parallele Zeilen“ berechnet, sodass uns die Vorteile der Stapelverarbeitung entgehen. Die Laufzeiten, die ich für diese Lösung mit dem parallelen Plan erhalten habe, lagen zwischen 2,47 Sekunden bei 1 Million Zeilen und 41,4 Sekunden bei 10 Millionen Zeilen.
Hier besteht eine ziemlich hohe Wahrscheinlichkeit, dass ein serieller Plan mit Stapelverarbeitung deutlich besser abschneidet, insbesondere wenn die Maschine nicht viele CPUs hat. Erinnern Sie sich, dass ich meine Lösungen gegen eine Maschine mit 4 logischen CPUs teste. Abbildung 6 zeigt den Plan, den ich für diese Lösung erhalten habe, wenn ich die serielle Verarbeitung erzwinge.
Abbildung 6:Serienplan für eine neue Lösung
Alle drei Fensterfunktionen verwenden die Stapelmodusstrategie „Keine Sortierung + Seriell“. Und die Ergebnisse können sich durchaus sehen lassen. Die Laufzeiten dieser Lösung lagen zwischen 0,5 Sekunden bei 1 Mio. Zeilen und 5,49 Sekunden bei 10 Mio. Zeilen. Interessant an dieser Lösung ist auch, dass SQL Server beim Testen als normale SELECT-Anweisung (mit verworfenen Ergebnissen) im Gegensatz zu einer SELECT INTO-Anweisung standardmäßig den seriellen Plan wählte. Bei den anderen beiden Lösungen habe ich standardmäßig sowohl mit SELECT als auch mit SELECT INTO einen parallelen Plan erhalten.
Im nächsten Abschnitt finden Sie die vollständigen Leistungstestergebnisse.
Leistungsvergleich
Hier ist der Code, den ich zum Testen der drei Lösungen verwendet habe, wobei ich natürlich den MAXDOP 1-Hinweis zum Testen der seriellen Pläne auskommentiert habe:
-- Test Known Solution 1 DROP TABLE IF EXISTS #Result; WITH C AS( SELECT *, ROW_NUMBER() OVER(PARTITION BY grp ORDER BY ord) - ROW_NUMBER() OVER(PARTITION BY grp, val ORDER BY ord) AS island FROM dbo.T1)SELECT grp, ord, val, ROW_NUMBER( ) OVER(PARTITION BY grp, val, island ORDER BY ord) AS seqnoINTO #ResultFROM C/* OPTION(MAXDOP 1) */; -- Entkommentiere für SerientestGO -- Teste bekannte Lösung 2 DROP TABLE IF EXISTS #Result; WITH C1 AS( SELECT *, CASE WHEN val =LAG(val) OVER(PARTITION BY grp ORDER BY ord) THEN 0 ELSE 1 END AS isstart FROM dbo.T1),C2 AS( SELECT *, SUM(isstart) OVER(PARTITION BY grp ORDER BY ord ROWS UNBOUNDED PRECEDING) AS island FROM C1)SELECT grp, ord, val, ROW_NUMBER() OVER(PARTITION BY grp, island ORDER BY ord) AS seqnoINTO #ResultFROM C2/* OPTION(MAXDOP 1) */; GO -- Neue Lösung testen DROP TABLE IF EXISTS #Result; WITH C1 AS( SELECT *, ROW_NUMBER() OVER(PARTITION BY grp ORDER BY ord) AS rn, LAG(val) OVER(PARTITION BY grp ORDER BY ord) AS prev FROM dbo.T1),C2 AS( SELECT *, MAX (CASE WHEN val =prev THEN NULL ELSE rn END) OVER(PARTITION BY grp ORDER BY ord ROWS UNBOUNDED PRECEDING) AS firstrn FROM C1)SELECT grp, ord, val, rn - firstrn + 1 AS seqnoINTO #ResultFROM C2/* OPTION( MAXDOP 1) */;Abbildung 7 zeigt die Laufzeiten sowohl des parallelen als auch des seriellen Plans für alle Lösungen bei unterschiedlichen Eingabegrößen.
Abbildung 7:Leistungsvergleich
Die neue Lösung mit seriellem Modus ist der klare Gewinner. Es bietet hervorragende Leistung, lineare Skalierung und sofortige Reaktionszeit.
Schlussfolgerung
Inselaufgaben sind im wirklichen Leben durchaus üblich. Viele von ihnen beinhalten sowohl das Identifizieren von Inseln als auch das Gruppieren der Daten nach der Insel. Die Inselherausforderung von Erland, die im Mittelpunkt dieses Artikels stand, ist etwas einzigartiger, da sie keine Gruppierung beinhaltet, sondern stattdessen die Reihen jeder Insel mit Reihennummern aneinanderreiht.
Ich habe zwei Lösungen präsentiert, die auf bekannten Techniken zum Identifizieren von Inseln basieren. Das Problem bei beiden ist, dass sie zu Plänen mit expliziter Sortierung führen, was sich negativ auf die Leistung, Skalierbarkeit und Reaktionszeit der Lösungen auswirkt. Ich habe auch eine neue Technik vorgestellt, die zu einem Plan ohne jegliches Sortieren führte. Der serielle Plan für diese Lösung, der eine Strategie ohne Sortierung + seriellen Stapelmodus verwendet, zeichnet sich durch hervorragende Leistung, lineare Skalierung und sofortige Reaktionszeit aus. Es ist bedauerlich, dass wir zumindest im Moment keine Strategie für den Modus „Keine Sortierung + paralleler Batch“ für die Handhabung von Fensterfunktionen haben können.
