Dies ist Teil einer Reihe problematischer Operatoren zu SQL Server Internals. Um den ersten Beitrag zu lesen, klicken Sie hier.
SQL Server gibt es seit über 30 Jahren und ich arbeite fast genauso lange mit SQL Server. Ich habe im Laufe der Jahre (und Jahrzehnte!) und Versionen dieses unglaublichen Produkts viele Veränderungen gesehen. In diesen Beiträgen werde ich mit Ihnen teilen, wie ich einige der Funktionen oder Aspekte von SQL Server betrachte, manchmal zusammen mit einem kleinen historischen Blickwinkel.
Letztes Mal habe ich über einen Scan-Vorgang in einem SQL Server-Abfrageplan als potenziell problematischen Operator in SQL Server-Diagnosen gesprochen. Obwohl Scans häufig nur verwendet werden, weil es keinen nützlichen Index gibt, gibt es Zeiten, in denen der Scan tatsächlich die bessere Wahl ist als eine Indexsuchoperation.
In diesem Artikel erzähle ich Ihnen von einer anderen Familie von Operatoren, die gelegentlich als problematisch angesehen wird:Hashing. Hashing ist ein sehr bekannter Datenverarbeitungsalgorithmus, der seit vielen Jahrzehnten existiert. Ich habe es in meinem Datenstrukturunterricht vor langer Zeit studiert, als ich an der Universität zum ersten Mal Informatik studierte. Wenn Sie Hintergrundinformationen zu Hashing und Hash-Funktionen wünschen, können Sie diesen Artikel auf Wikipedia lesen. Allerdings hat SQL Server Hashing erst mit SQL Server 7 zu seinem Repertoire an Abfrageverarbeitungsoptionen hinzugefügt. (Nebenbei möchte ich erwähnen, dass SQL Server Hashing in einigen seiner eigenen internen Suchalgorithmen verwendet hat. Wie der Wikipedia-Artikel erwähnt verwendet Hashing eine spezielle Funktion, um Daten beliebiger Größe Daten einer festen Größe zuzuordnen. SQL verwendete Hashing als Suchtechnik, um jede Seite aus einer Datenbank beliebiger Größe einem Puffer im Speicher zuzuordnen, der eine feste Größe hat. Tatsächlich , gab es früher eine Option für sp_configure sogenannte „Hash-Buckets“, mit denen Sie die Anzahl der Buckets steuern konnten, die für das Hashing von Datenbankseiten in Speicherpuffer verwendet werden.)
Was ist Hashing?
Hashing ist eine Suchtechnik, bei der die Daten nicht geordnet werden müssen. SQL Server kann es für JOIN-Vorgänge, Aggregationsvorgänge (DISTINCT oder GROUP BY) oder UNION-Vorgänge verwenden. Was diese drei Operationen gemeinsam haben, ist, dass die Abfrage-Engine während der Ausführung nach übereinstimmenden Werten sucht. In einem JOIN wollen wir Zeilen in einer Tabelle (oder einem Rowset) finden, die übereinstimmende Werte mit Zeilen in einer anderen haben. (Und ja, ich kenne Joins, die Zeilen nicht basierend auf Gleichheit vergleichen, aber diese Nicht-Equijoins sind für diese Diskussion irrelevant.) Für GROUP BY finden wir übereinstimmende Werte, die in dieselbe Gruppe aufgenommen werden sollen, und für UNION und DISTINCT suchen wir nach übereinstimmenden Werten, um sie auszuschließen. (Ja, ich weiß, UNION ALL ist eine Ausnahme.)
Vor SQL Server 7 konnten diese Operationen übereinstimmende Werte nur finden, wenn die Daten sortiert waren. Wenn es also keinen vorhandenen Index gibt, der die Daten in sortierter Reihenfolge verwaltet, fügt der Abfrageplan dem Plan eine SORT-Operation hinzu. Hashing organisiert Ihre Daten für eine effiziente Suche, indem alle Zeilen, die das gleiche Ergebnis aus der internen Hash-Funktion haben, in denselben „Hash-Bucket“ gestellt werden.
Eine ausführlichere Erläuterung der Hash-JOIN-Operation von SQL Server, einschließlich Diagrammen, finden Sie in diesem Blogbeitrag von SQL Shack.
Als Hashing zu einer Option wurde, hat SQL Server die Möglichkeit, Daten vor dem Zusammenführen oder Aggregation zu sortieren, nicht vollständig außer Acht gelassen, sondern es wurde einfach eine Möglichkeit, die der Optimierer in Betracht ziehen sollte. Wenn Sie jedoch versuchen, unsortierte Daten zusammenzuführen, zu aggregieren oder UNION durchzuführen, wählt der Optimierer im Allgemeinen normalerweise eine Hash-Operation. So viele Leute gehen davon aus, dass ein HASH JOIN (oder eine andere HASH-Operation) in einem Plan bedeutet, dass Sie keine geeigneten Indizes haben und dass Sie geeignete Indizes erstellen sollten, um die Hash-Operation zu vermeiden.
Schauen wir uns ein Beispiel an. Ich erstelle zuerst zwei nicht indizierte Tabellen.
USE AdventureWorks2016 GO DROP TABLE IF EXISTS Details;
GO
SELECT * INTO Details FROM Sales.SalesOrderDetail;
GO
DROP TABLE IF EXISTS Headers;
GO
SELECT * INTO Headers FROM Sales.SalesOrderHeader;
GO
Now, I’ll join these two tables together and filter the rows in the Details table:
SELECT *
FROM Details d JOIN Headers h
ON d.SalesOrderID = h.SalesOrderID
WHERE SalesOrderDetailID < 100;
Das Quest Spotlight Tuning Pack scheint den Hash-Join nicht als Problem anzuzeigen. Es hebt nur die beiden Tabellenscans hervor.
Die Vorschläge empfehlen, einen Index für jede Tabelle zu erstellen, der jede einzelne Nicht-Schlüsselspalte als INCLUDED-Spalte enthält. Ich nehme diese Empfehlungen selten an (wie ich in meinem vorherigen Beitrag erwähnt habe). Ich baue nur den Index auf den Details auf Tabelle, in der Join-Spalte und keine eingeschlossenen Spalten haben.
CREATE INDEX Header_index on Headers(SalesOrderID);
Sobald dieser Index erstellt ist, verschwindet der HASH JOIN. Der Index sortiert die Daten in den Headern Tabelle und ermöglicht es SQL Server, die übereinstimmenden Zeilen in der inneren Tabelle anhand der Sortierreihenfolge des Indexes zu finden. Der teuerste Teil des Plans ist nun der Scan des äußeren Tisches (Details ), die durch den Aufbau eines Indexes auf der SalesOrderID reduziert werden könnte Spalte in dieser Tabelle. Ich überlasse das dem Leser als Übung.
Ein Plan mit einem HASH JOIN ist jedoch nicht immer eine schlechte Sache. Der alternative Operator (außer in Sonderfällen) ist ein NESTED LOOPS JOIN, und das ist normalerweise die Wahl, wenn gute Indizes vorhanden sind. Eine NESTED-Schleifenoperation erfordert jedoch mehrere Suchvorgänge in der inneren Tabelle. Der folgende Pseudocode zeigt den Nested-Loops-Join-Algorithmus:
for each row R1 in the outer table
for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)
Wie der Name schon sagt, wird ein NESTED LOOP JOIN als verschachtelte Schleife ausgeführt. Die Suche in der inneren Tabelle wird normalerweise mehrmals durchgeführt, einmal für jede qualifizierte Zeile in der äußeren Tabelle. Selbst wenn nur ein paar Prozent der Zeilen qualifiziert sind, müssen bei einer sehr großen Tabelle (vielleicht Hunderte von Millionen oder Milliarden oder Zeilen) viele Zeilen gelesen werden. In einem E/A-gebundenen System können diese Millionen oder Milliarden von Lesevorgängen ein echter Engpass sein.
Ein HASH JOIN hingegen führt keine mehrfachen Lesevorgänge von beiden Tabellen durch. Es liest die äußere Tabelle einmal, um die Hash-Buckets zu erstellen, und dann liest es die innere Tabelle einmal und überprüft die Hash-Buckets, um zu sehen, ob es eine übereinstimmende Zeile gibt. Wir haben eine Obergrenze von einem einzigen Durchgang durch jede Tabelle. Ja, es werden CPU-Ressourcen benötigt, um die Hash-Funktion zu berechnen und den Inhalt der Buckets zu verwalten. Es werden Speicherressourcen benötigt, um die gehashten Informationen zu speichern. Wenn Sie jedoch ein I/O-gebundenes System haben, haben Sie möglicherweise Speicher- und CPU-Ressourcen übrig. HASH JOIN kann eine vernünftige Wahl für den Optimierer in Situationen sein, in denen Ihre E/A-Ressourcen begrenzt sind und Sie sehr große Tabellen verknüpfen.
Hier ist Pseudocode für den Hash-Join-Algorithmus:
for each row R1 in the build table
begin
calculate hash value on R1 join key(s)
insert R1 into the appropriate hash bucket
end
for each row R2 in the probe table
begin
calculate hash value on R2 join key(s)
for each row R1 in the corresponding hash bucket
if R1 joins with R2
output (R1, R2)
end
Wie bereits erwähnt, kann Hashing auch für Aggregationsoperationen (sowie für UNION-Operationen) verwendet werden. Wenn es einen nützlichen Index gibt, in dem die Daten bereits sortiert sind, kann das Gruppieren der Daten sehr effizient erfolgen. Es gibt jedoch auch viele Situationen, in denen Hashing überhaupt kein schlechter Operator ist. Stellen Sie sich eine Abfrage wie die folgende vor, die die Daten in den Details gruppiert Tabelle (oben erstellt) durch die ProductID Säule. Es gibt 121.317 Zeilen in der Tabelle und nur 266 verschiedene ProductID Werte.
SELECT ProductID, count(*)
FROM Details
GROUP BY ProductID;
GO
Hashing-Vorgänge verwenden
Um Hashing zu verwenden, muss SQL Server nur 266 Buckets erstellen und verwalten, was nicht viel ist. Tatsächlich zeigt das Quest Spotlight Tuning Pack nicht an, dass es Probleme mit dieser Abfrage gibt. 
Ja, es muss ein Tabellenscan durchgeführt werden, aber das liegt daran, dass wir jede Zeile in der Tabelle untersuchen müssen und wir wissen, dass Scans nicht immer eine schlechte Sache sind. Ein Index würde nur beim Vorsortieren der Daten helfen, aber die Verwendung der Hash-Aggregation für eine so kleine Anzahl von Gruppen liefert normalerweise immer noch eine angemessene Leistung, selbst wenn kein nützlicher Index verfügbar ist.
Wie Tabellen-Scans werden Hash-Operationen häufig als „schlechter“ Operator angesehen, den man in einem Plan haben sollte. Es gibt Fälle, in denen Sie die Leistung erheblich verbessern können, indem Sie nützliche Indizes hinzufügen, um die Hash-Operationen zu entfernen, aber das ist nicht immer der Fall. Und wenn Sie versuchen, die Anzahl der Indizes für stark aktualisierte Tabellen zu begrenzen, sollten Sie sich darüber im Klaren sein, dass Hash-Operationen nicht immer etwas sind, das „korrigiert“ werden muss. Daher kann es sinnvoll sein, die Abfrage zu verlassen, um einen Hash zu verwenden machen. Darüber hinaus kann Hashing bei bestimmten Abfragen für große Tabellen, die auf E/A-gebundenen Systemen ausgeführt werden, aufgrund der begrenzten Anzahl von Lesevorgängen, die ausgeführt werden müssen, tatsächlich eine bessere Leistung als alternative Algorithmen bieten. Der einzige Weg, um sicher zu sein, ist es, verschiedene Möglichkeiten auf Ihrem System zu testen, mit Ihren Anfragen und Ihren Daten.
Im folgenden Beitrag dieser Serie werde ich Sie über andere problematische Operatoren informieren, die möglicherweise in Ihren Abfrageplänen auftauchen, also schauen Sie bald wieder vorbei!
