In meinen Seminaren zu Microsoft SQL Server werden in Verbindung mit der Optimierung von Ausführungsplänen von Abfragen immer wieder Fragen nach den unterschiedlichen JOIN-Operatoren gestellt und nach welchen Kriterien der Microsoft SQL Server welchen Operator auswählt. In diesem wie den nachfolgenden Artikeln möchte ich diese Operatoren und die Entscheidungswege von Microsoft SQL Server etwas genauer mit Beispielen erläutern.

Ein NESTED LOOP ist eine von mehreren physikalische Operation, die von Microsoft SQL Server verwendet wird, um Datensätze aus der Datenbank zu extrahieren und an die aufrufende Applikation zu senden. Bevor jedoch Microsoft SQL Server irgendeine Operation anwenden kann, muss ein Ausführungsplan erstellt werden.

Nach welchen Kriterien erstellt Microsoft SQL Server seine Ausführungspläne?

Die Ausführungspläne zu Abfragen in Microsoft SQL Server werden durch den “Query Processor” erstellt. Alle Abfragen werden an den Query Processor übergeben, berechnet und mit der Erstellung eines Ausführungsplans abgeschlossen. Dieser Ausführungsplan wird anschließend vom Query Processor ausgeführt und die Daten zum Client übertragen. Wie der Query Processor von Microsoft SQL Server genau arbeitet, ist natürlich eines der bestgehüteten Geheimnisse von Microsoft, wie auch eines jeden anderen Herstellers relationaler Datenbanken. Grundsätzlich werden vier Schritte ausgeführt, bevor ein Ergebnis an den Client gesendet wird. Nachfolgend werden diese Schritte grob beschrieben – wer sich intensiver mit diesem Thema beschäftigen möchte, dem sei das Buch “Inside the SQL Server Optimizer” von Benjamin Nevarez empfohlen.

In der Optimierungsphase entscheidet sich, welche physikalischen Operatoren von Microsoft SQL Server für die Ausführung der Abfrage verwendet werden. Microsoft SQL Server unterscheidet zwischen logischen Operatoren (INNER JOIN, OUTER JOIN, APPLY) und physikalischen Operatoren, die zur Bearbeitung der logischen Operatoren verwendet werden. Grundlage dieser Entscheidung ist – wie bereits oben erwähnt – eine Kostenschätzung. Ein möglicher physikalischer Operator für einen JOIN ist der NESTED LOOP.

Was ist ein NESTED LOOP

Der NESTED LOOP ist ein physikalischer Operator, der von Microsoft SQL Server verwendet wird, um Daten zweier Tabellen, die durch einen logischen Operator (z. B. JOIN) in einer Beziehung stehen, zu verbinden. Ein NESTED LOOP arbeitet nach dem Prinzip, dass zunächst die Daten einer “äußeren” Tabelle ermittelt werden und anschließend die “innere” Tabelle nach identischen Werten in den Verbindungsattributen sucht. In Pseudocode sähe das Verfahren wie folgt aus:

für jeden gefundenen Datensatz in Tabelle A

BEGIN

    Suche in Tabelle B alle Datensätze, in dessen Verbindungsattribut ein

    identischer Wert steht wie im Verbindungsattribut in Tabelle A

END

Welche Tabelle die “äußere” Tabelle bildet, bestimmt Microsoft SQL Server selbst. Bei einem INNER JOIN gilt das Kommutativgesetz. Das Kommutativgesetz ist eine Regel aus der Mathematik, die besagt, das Argumente einer Operation beliebig vertauscht werden können; das Ergebnis ist immer identisch. Ein JOIN zwischen Tabelle [A] und Tabelle [B] ist danach identisch mit einem JOIN zwischen Tabelle [B] und Tabelle [A].

Testumgebung

Für die Demonstration sowie die weiteren Erläuterungen dient eine einfache Struktur mit zwei Tabellen ([dbo].[Projects] und [dbo].[Employees]).

CREATE TABLE dbo.Employees

(

    Id          int IDENTITY(1,1)  NOT NULL,

    FirstName   varchar(64)        NOT NULL,

    LastName    varchar(64)        NOT NULL,

    HiredAt     date               NOT NULL,

    Manager_Id  int                NOT NULL,

    CONSTRAINT pk_Employees_Id PRIMARY KEY CLUSTERED(Id)

);

GO

CREATE TABLE dbo.Projects

(

    Id             int         NOT NULL  IDENTITY(1,1),

    ProjectName    varchar(64) NOT NULL,

    ProjectStart   date        NOT NULL,

    ProjectFinish  date        NULL,

    ProjectLead    int         NOT NULL,

    CONSTRAINT pk_Projects_Id PRIMARY KEY CLUSTERED (Id),

    CONSTRAINT fk_Projects_ProjectLead FOREIGN KEY(ProjectLead)

    REFERENCES dbo.Employees (Id)

)

GO

Beide Tabellen besitzen einen Clustered Index auf dem Attribut [Id]. In der Tabelle [dbo].[Projects] speichert das Attribut [ProjectLead] die [Id] eines vorhandenen Datensatzes aus [dbo].[Employees]. Damit keine ungültigen [Id] verwendet werden, besteht eine Fremdschlüsselbeziehung zwischen beiden Tabellen. Die Tabelle [dbo].[Projects] enthält 100 Datensätze; die Tabelle [dbo].[Employees] enthält 270 Datensätze.

Abfrageanalyse

Die erste Abfrage, in der beide Tabellen durch einen INNER JOIN als logischen Operator miteinander verbunden sind, verwendet einen physikalischen NESTED LOOP für die Ausgabe, wie der Ausführungsplan (kann mit [STRG] + [M]) aktiviert werden) zeigt. Damit sowohl I/O als auch die einzelnen Operationen sichtbar werden, werden sie mit SET STATISTICS aktiviert.

SET STATISTICS IO ON;

SET STATISTICS PROFILE ON;

GO

SELECT  p.Id,

        p.ProjectName,

        p.ProjectStart,

        e.LastName,

        e.FirstName,

        e.HiredAt

FROM    dbo.Projects p INNER JOIN dbo.Employees e

        ON (p.ProjectLead = e.Id)

WHERE   p.Id <= 10;

Das Ergebnis der der Abfrage liefert 10 Projektdatensätze, zu denen die Vor- und Zunamen der Projektleiter angezeigt werden.

Der Ausführungsplan zeigt, dass der Query Optimizer [dbo].[Projects] als “äußere” Tabelle verwendet. Für jeden gefundenen Datensatz aus [dbo].[Projects] muss Microsoft SQL Server innerhalb der Tabelle [dbo].[Employees] nach dem Datensatz mit der Id des Mitarbeiters suchen, der das Projekt leitet. Viel genauer werden die einzelnen Schritte in der Ausgabe des Ausführungsprofils sichtbar wie die nächste Abbildung zeigt.

Ein unmittelbarer Vergleich des Ausführungsprofils mit dem vorherigen Ausführungsplan zeigt in Zeile 2 die physikalische Operation NESTED LOOP bei der [dbo].[Projects] als äußere Tabelle dient. Über das Attribut [ProjectLead] wird der JOIN durchgeführt. Somit ist dieses Attribut die OUTER REFERENCE für den NESTED LOOP.

Zeile 3 des Ausführungsprofils zeigt, dass Microsoft SQL Server ein Mal mittels INDEX SEEK die Tabelle [dbo].[Projects] nach Projekten durchsucht, deren [Id] <= 10 ist. Insgesamt werden durch diesen einen INDEX SEEK 10 Datensätze gefunden.

Zeile 4 des Ausführungsprofils demonstriert die Arbeitsweise eines NESTED LOOP. Nachdem die 10 Projekt-Datensätze ermittelt wurden, muss für JEDEN Projektdatensatz explizit ein INDEX SEEK in der Tabelle [dbo].[Employees] durchgeführt werden. Besondere Beachtung gilt der Spalte [Executes] im Ausführungsprofil. Man kann sehr deutlich erkennen, dass Microsoft SQL Server 10 Mal einen INDEX SEEK durchführen musste. Insgesamt (!) wurden 10 Zeilen durch diese Operationen zurück geliefert. Pro Ausführung wurde jeweils 1 Datensatz in [dbo].[Employees] gefunden.

Zu Guter Letzt zeigt ein Blick auf die I/O-Statistiken, wie häufig Microsoft SQL Server Daten aus dem Buffer Pool lesen musste, um die Daten an den Client zu liefern.

Employees-Tabelle. Scananzahl 0, logische Lesevorgänge 20, ...
Projects-Tabelle. Scananzahl 1, logische Lesevorgänge 2, ...

Aus der Tabelle [dbo].[Employees] wurden 20 Datenseiten gelesen. Wird dieser Wert durch 10 geteilt (insgesamt musste der INDEX SEEK 10 Mal durchgeführt werden!) ergibt sich pro Operation ein I/O von 2 Datenseiten. Die Daten der Projekte wurden mit 2 Leseoperationen ermittelt.

Was passiert, wenn die Datenmenge größer wird?

Wie zu Beginn des Artikels beschrieben, arbeitet der Query Optimizer des Microsoft SQL Server auf Basis von Kostenanalysen. Wie schaut der Ausführungsplan aus, wenn die Datenmenge zunimmt? Die nächste Abfrage liefert für ALLE Projekte (100) und die zugehörigen Projektleiter.

SELECT  p.Id,

        p.ProjectName,

        p.ProjectStart,

        e.LastName,

        e.FirstName,

        e.HiredAt

FROM    dbo.Projects p INNER JOIN dbo.Employees e

        ON (p.ProjectLead = e.Id)

Da keine WHERE-Klausel verwendet wird, müssen alle Projekte aus [dbo].[Projekte] angezeigt werden. Da es zu jedem Projekt einen Projektleiter in [dbo].[Employees] gibt, wird auch die Menge der Daten, die aus dieser Tabelle geholt werden muss, höher sein. Der Ausführungsplan zeigt, welche physikalische Operation Microsoft SQL Server dazu verwendet.

Statt eines NESTED LOOP verwendet Microsoft SQL Server einen MERGE JOIN. Die Operation selbst soll hier nicht weiter beschrieben werden – vielmehr gilt es zu untersuchen, warum Microsoft SQL Server die Strategie ändert. Hierzu gilt der erste Blick den I/O-Statistiken der Abfrage:

Projects-Tabelle. Scananzahl 1, logische Lesevorgänge 2, ...
Employees-Tabelle. Scananzahl 1, logische Lesevorgänge 5, ...

WOW – tatsächlich wird deutlich weniger I/O generiert. Ein zweiter Blick auf die Statistiken regt aber zu der Frage an, warum deutlich mehr Daten signifikant weniger I/O produzieren. Weiter oben wurden für 10 Datensätze insgesamt 22 I/O’s generiert während für 100 Datensätze nur 6 I/O produziert wurden. Warum hat sich Microsoft SQL Server dann also bei der ersten Abfrage für einen NESTED LOOP entschieden und nicht für einen MERGE JOIN? Scheinbar muss der Query Optimizer also trotz höherem I/O weniger Kosten bei einer NESTED LOOP Operation ermittelt haben. Aufschluss kann ein Blick IN die Arbeit des Query Optimizer geben. Die nachfolgende Abfrage zeigt die Kosten, die der Query Optimizer bei der Auswahl von 10 Datensätzen mit einer NESTED LOOP Operation ermittelt hat.

-- Ausgabe der Informationen des Query Optimizers aktivieren

DBCC TRACEON (3604);

-- Ausgabe der Daten mit einem erzwungenen NESTED LOOP

-- unter Ausgabe der geschätzten Kosten für die Ausführung

SELECT  p.Id,

        p.ProjectName,

        p.ProjectStart,

        e.LastName,

        e.FirstName,

        e.HiredAt

FROM    dbo.Projects p INNER JOIN dbo.Employees e

        ON (p.ProjectLead = e.Id)

WHERE   p.Id <= 10

OPTION  (QUERYTRACEON 8675, LOOP JOIN, RECOMPILE);

Die obige Abfrage zeigt erneut alle Projekte, deren [Id] <= 10 ist. Mittels OPTION wird die Abfrage manuell beeinflusst. Mit der Option QUERYTRACEON können Ausführungspläne beeinflusst werden; weitere Details zu dieser Option finden sich hier: http://support.microsoft.com/kb/2801413/en-us!

BITTE NICHT IN EINEM PRODUKTIONSSYSTEM DURCHFÜHREN, DA DAS TRACEFLAG 8675 NICHT OFFIZIELL DOKUMENTIERT IST!

Mit der Option LOOP JOIN wird der Query Optimizer von Microsoft SQL Server angewiesen, auf jeden Fall diesen physikalischen Operator zu verwenden. Letztendlich wird durch die Option RECOMPILE eine Neukompilierung des Ausführungsplans erzwungen.

End of simplification, time: 0 net: 0 total: 0 net: 0
end exploration, tasks: 79 no total cost time: 0 net: 0 total: 0.001 net: 0.001
end search(1),  cost: 0.0140122 tasks: 117 time: 0 net: 0 total: 0.001 net: 0.001
End of post optimization rewrite, time: 0 net: 0 total: 0.001 net: 0.001
End of query plan compilation, time: 0 net: 0 total: 0.001 net: 0.001

Das obige Ergebnis zeigt die vom Query Optimizer ermittelten Kosten für alle Schritte der Optimierung. Wie bereits vorher gesehen ergab die Ausführung dieser Abfrage ein I/O von insgesamt 22 I/O. Nun wird die gleiche Abfrage mit einem erzwungenen MERGE JOIN ausgeführt und anschließend die Kosten untersucht.

SELECT  p.Id,

        p.ProjectName,

        p.ProjectStart,

        e.LastName,

        e.FirstName,

        e.HiredAt

FROM    dbo.Projects p INNER JOIN dbo.Employees e

        ON (p.ProjectLead = e.Id)

WHERE   p.Id <= 10

OPTION  (QUERYTRACEON 8675, MERGE JOIN, RECOMPILE);

Eine Untersuchung des Ausführungsplans zeigt bereits, dass ein teurer Sortiervorgang verwendet werden muss. Dieses Kosten spiegeln sich auch im Ergebnis der durch den Query Optimizer analysierten Kosten wider:

End of simplification, time: 0 net: 0 total: 0 net: 0
end exploration, tasks: 77 no total cost time: 0 net: 0 total: 0.001 net: 0.001
end search(1),  cost: 0.0259682 tasks: 141 time: 0 net: 0 total: 0.001 net: 0.001
End of post optimization rewrite, time: 0 net: 0 total: 0.002 net: 0.002
End of query plan compilation, time: 0 net: 0 total: 0.002 net: 0.002

Obwohl bei der Verwendung eines MERGE JOIN deutlich weniger I/O generiert würde, werden diese Vorteile wieder durch einen teuren SORT relativiert. Microsoft SQL Server hat – unter Berücksichtigung der Gesamtkosten – also den deutlich besseren Weg gewählt.

Zusammenfassung

Ein NESTED LOOP ist eine vom Query Optimizer bevorzugte Lösung, wenn die Datenmengen nicht zu groß sind. Für eine Verwendung des NESTED LOOP Operators spricht, dass die Schlüsselattribute der inneren Tabelle nicht sortiert vorliegen müssen. Ist das Indexattribut der inneren Tabelle indiziert, können performante INDEX SEEK-Operationen verwendet werden. Grundsätzlich sollte man dem Query Optimizer von Microsoft SQL Server vertrauen – in den seltensten Fällen sind eigene Abfragehinweise optimaler!

Herzlichen Dank fürs Lesen!