Samstag, 9. Februar 2013

Multi-Column-Indexes – Vor- und Nachteile

In einem sehr interessanten Entwicklungsprojekt bei einem meiner Kunden gab es erhebliche Probleme in der Performance einer bestimmten Abfrage. Es hatte sich letztendlich herausgestellt, dass die Ursache für die schlechte Performance in einem falsch erstellten Index zu finden war. Lesen Sie in diesem Artikel, wie stark die Reihenfolge der Attribute eines Indexes die Performance beinflussen kann.

Problemstellung

Um das Problem des Kunden vereinfacht darzustellen, bediene ich mich der Metapher eines Telefonbuchs

CREATE TABLE dbo.tbl_PhoneBook
(
    Id
          int             NOT NULL    IDENTITY (1, 1),
    LastName
    varchar(100)    NOT NULL,
    FirstName  
varchar(100)    NULL,
    PhoneNumber
varchar(20)     NOT NULL

    CONSTRAINT pk_tbl_PhoneBook PRIMARY KEY CLUSTERED (Id)
);

-- Ein weiterer multi-column-index
CREATE INDEX ix_tbl_PhoneBook_LastName_FirstName
ON dbo.tbl_PhoneBook (LastName ASC, FirstName ASC);

Das obige Script erzeugt eine Relation für die Speicherung von Telefonbuchdaten. Die Relation ist ein Clustered Index und das Schlüsselattribut des Clustered Index ist [Id]. Da aber in einem Telefonbuch nicht nach einem Surrogatschlüssel gesucht wird sondern nach Namen, wird ein zusätzlicher non-clustered Index erstellt, der die Suche nach Namen optimieren soll. Im Beispielscript [Create database and data.sql] finden sich neben der Struktur auch Codezeilen, die Beispieldaten hinzufügen. Wie werden nun welche Indexe bei verschieden Abfragevarianten verwendet?

Ein Blick unter die Motorhaube – wie ist ein non-clustered Index strukturiert

Um die Ergebnisse der Abfragen zu verstehen, müssen wir zunächst einen Blick auf die Strukturen eines Index werfen. Hierzu gibt es zwei Möglichkeiten. Sofern Sie nicht mit SQL Server 2012 arbeiten, können Sie das von mir beschriebene Verfahren einer Zwischentabelle verwenden (diesen Trick habe ich aus einem Lehrvideo von Kimberly L. Tripp entnommen). Ansonsten können Sie die wesentlich komfortablere Systemfunktion sys.dm_db_database_page_allocations verwenden, die ich in meinem Blog bereits beschrieben habe. Das vollständige Script für die nachfolgenden Operationen finden Sie in im Beispielprojekt unter dem Namen  [Index Analysis.sql].

Um eine Analyse der Indexstrukturen zu starten, muß zunächst festgestellt werden, welche Id der Index besitzt. Erst dann kann die eigentliche Analyse beginnen. Die nachfolgende Abbildung zeigt sowohl die Codierung als auch die daraus resultierenden Ergebnisse.

Index structures

Das Ergebnis der neuen Systemview zeigt, dass die Indexdaten auf der Seite 145 beginnen. Der [page_level] definiert die Anzahl der Hierarchien im B-Trees und dem Leaf-Level des Indexes. Die Struktur eines Index beginnt immer in der root page. Der höchste Wert für [page_level] bestimmt diese root-page. Insgesamt sind die Daten des Index auf zwei Seiten aufgeteilt. Sie beginnen auf der Seite 142 und werden auf Seite 146 fortgeführt. Eine solche Seite gilt es nun strukturell zu untersuchen.

Index structure pages

Zunächst wird mittels Traceflag 3604 die Ausgabe von SQL Server Errorlog in SSMS umgeleitet (ansonsten könnten die Inhalte nicht abgebildet werden). Man kann deutlich erkennen, dass der Index gemäß der Definition aufgebaut ist und die Attribute [LastName] und [FirstName] abdeckt. Das Attribut [Id] repräsentiert das Schlüsselattribut des Clustered Index, der – wie Sie nachher sehen werden – von wesentlicher Bedeutung für die Analyse des Indexverhaltens ist. Mit der Kenntnis um die Indexstrukturen können nun die nachfolgenden Abfragen und deren Ausführungspläne auf Schwachstellen untersucht werden.

Analyse der Abfragen

-- Suche nach einem Nachnamen
SELECT Id, LastName, FirstName FROM dbo.tbl_PhoneBook WHERE
LastName = 'Faber'
SELECT * FROM dbo.tbl_PhoneBook WHERE LastName =
'Faber'
SELECT * FROM dbo.tbl_PhoneBook WITH (INDEX (ix_tbl_PhoneBook_LastName_FirstName)) WHERE LastName = 'Faber'

Schaut man sich die Ausführungspläne an, mag man sich wundern, warum – trotz scheinbar identischer Abfrage – unterschiedliche Ergebnisse für die Ausführungspläne geliefert werden.

Query 01 - Execution Plan

Für die erste Abfrage wurde der Index [ix_tbl_PhoneBook_LastName_FirstName verwendet und – was sehr wichtig ist – es wurde ein performanter INDEX SEEK durchgeführt. Die zweite Abfrage dagegen (sie zeigt lediglich die Telefonnummer mit an) ignoriert diesen Index vollständig und führt statt dessen einen CLUSTERED INDEX SCAN durch, der nichts anderes als ein Table Scan ist. Diese Variante ist eindeutig unperformanter wie auch die Kosten in Relation zum Batch belegen (~10% schlechter).

Das für die zweite Abfrage ein Index Scan auf dem Clustered Index verwendet wird, ist der Struktur des – besseren – Index auf Nach- und Vorname geschuldet. Wie weiter oben gesehen, sind lediglich Nachname und Vorname Bestandteil des Index, die Telefonnummer kann nicht aus dem Index entnommen werden. Für eine Verwendung des Index auf Nach- und Vorname müßte also SQL Server für jeden gefundenen Daten jedes Mal im Clustered Index nachschauen, um die Telefonnummer zu ermitteln. Dieses Verfahren nennt sich KeyLookup. In der dritten Variante der Abfrage wird dieses Prinzip sehr deutlich demonstriert. Man kann erkennen, dass diese Abfragestrategie mit Abstand die schlechteste Variante ist und mehr als 50% der gesamten Abfragekosten beansprucht.

SELECT Id, LastName, FirstName FROM dbo.tbl_PhoneBook
WHERE LastName = 'Faber' AND FirstName = 'Klaus'
SELECT * FROM dbo.tbl_PhoneBook
WHERE LastName = 'Faber' AND FirstName = 'Klaus'

Die obigen Abfragen verhalten sich im Ergebnis identisch zu den zuvor ermittelten Ergebnissen, da es bei der geringen Datenmenge keinen Unterschied macht, sowohl nach Nachnamen als auch nach Vornamen zu suchen. Die Selektivität der Datensätze  (Kardinalität) ist nur marginal. Von daher überrascht das Ergebnis des Ausführungsplans nicht.

Query 02 - Execution Plan

Der für beide Abfragen wesentliche Punkt, den es – FÜR ALLE – zu beachten gibt, ist die Frage nach den im Index befindlichen Elementen / Attribute. Die zweite Abfrage ist erneut deutlich unperformanter, weil die Telefonnummer selbst nicht Bestandteil des Index ist. Somit ist ein index-Scan die deutlich beste Wahl; hat aber dennoch einen Nachteil von über 10%.

Neben den oben genannten Punkten ist insbesondere bei einem “Mulit-Column-Index” die Reihenfolge der abzufragenden Attribute das entscheidende Kriterium für eine performante oder desolate Abfragestrategie. Das soll das nachfolgende Beispiel zeigen:

SELECT Id, LastName, FirstName FROM dbo.tbl_PhoneBook WHERE FirstName = 'Sabine';
SELECT * FROM dbo.tbl_PhoneBook WHERE Firstname = 'Sabine';

Führt man die obigen Abfragen aus, wird man überrascht sein, dass beide Abfragen einen desolaten Ausführungsplan besitzen. Ursächlich für den Index-Scan im ersten Beispiel ist die Tatsache, dass SQL Server nach den Vornamen suchen muss. Der Vorname ist jedoch im Index ix_tbl_PhoneBook_LastName_FirstName nur sekundär. Um das Verhalten von SQL Server zu verstehen, adaptieren Sie das Beispiel des Telefonbuchs auf die Realität. Stellen Sie sich vor, Sie kennen nur den Vornamen einer Person, die Sie anrufen möchten. Sie haben keinen Anhaltspunkt, auf welcher Seite des Telefonbuchs Sie mit der Suche beginnen müssen – demzufolge bleibt Ihnen nichts anderes übrig, als das komplette Telefonbuch nach dem gewünschten Vornamen zu durchsuchen; Sie führen also eine Suche über den kompletten Index durch; also einen Index Scan.

Das Ergebnis der zweiten Abfrage war zu erwarten. Da die Telefonnummer nicht Bestandteil des Index ist, wird ein Table Scan über die komplette Relation durchgeführt.

Die nächste – und letzte – Frage, die sich stellt, ist die Frage, wie SQL Server sich verhält, wenn sowohl Vor- als auch Nachname bekannt ist. Dazu soll die Analyse der folgenden Abfragen dienen:

SELECT Id, LastName, FirstName FROM dbo.tbl_PhoneBook WHERE LastName = 'Faber' AND FirstName = 'Sabine';
SELECT Id, LastName, FirstName FROM dbo.tbl_PhoneBook WHERE FirstName = 'Sabine' AND LastName = 'Faber';

Der Ausführungsplan zeigt, dass SQL Server sich in einem solchen Fall nicht überlisten läßt. SQL Server erkennt in beiden Fällen, dass die Attribute in der WHERE-Klausel vollständig durch den Index abgedeckt werden. In solchen Fällen ist die Reihenfolge der abzufragenden Attribute irrelevant.

Query 03 - Execution Plan

Insgesamt gibt es für das obige Beispiel zwei Probleme, die zu einer desolaten Indexstrategie führen:

  • Bei – für die Verwendung dieser Relation – Abfrage der Telefonnummer kann der performantere Index für die Suche nach Vor- und Nachnamen nicht verwendet werden
  • Ausschließliche Suchen nach Vornamen verwenden einen INDEX SCAN statt eines wesentlich performanteren INDEX SEEK

Diese obigen Schwachstellen gilt es zu optimieren. Für beide Fälle ist die bisherige Indexstrategie fehlerhaft. Zunächst gilt es, einen möglichen KeyLookup / Table Scan zu vermeiden, wenn die Telefonnummer mit ausgegeben werden muss. Dazu schaut man sich noch einmal die Struktur des Indexes – wie weiter oben gezeigt – an.

Index structure details

Für das Beispiel nach der Suche aller Personen mit dem Nachnamen Faber ist erkennbar, dass Bestandteil des Indexes nur der Nach – und Vorname ist. Alle anderen Daten befinden sich im Clustered index. Nun wird klar, warum es essentiell ist, dass das Schlüsselattribut des Clustered Index in jedem Index mitgeführt werden muss – wie soll SQL Server sonst wissen, aus welchem Datensatz im Clustered Index die Informationen entnommen werden sollen, die nicht Bestandteil des eigentlichen Index sind.

Die Frage, die sich hier stellt, ist die Sinnhaftigkeit, das Attribut PhoneNumber ebenfalls in den Index aufzunehmen. Diese Option steht nicht zur Debatte, da ja dieses Attribut nicht aktiv gesucht wird. Für solche Fälle hat SQL Server seit der Version 2005 die Option INCLUDE für Indexe eingeführt. Die Besonderheit von eingeschlossenen Attributen ist, dass die Schlüsselattribute auf allen Ebenen des Indexes gespeichert werden, während die Nichtschlüsselattribute (z. B. PhoneNumber) nur im Leaf-Level gespeichert sind.

Optimierung

Vermeidung von KeyLookups oder Auswahl des falschen Index

Nachfolgend werden die einzelnen Schritte beschrieben, die zu performanten Abfragen führen. Zunächst wird der ursprüngliche Index ix_tbl_PhoneBook_LastName_FirstName wie folgt geändert:

CREATE INDEX ix_PhoneBook_LastName_Firstname ON dbo.tbl_PhoneBook
(LastName, FirstName)
INCLUDE (PhoneNumber);

Das Ergebnis es Ausführungsplans zeigt eine signifikante Verbesserung bei der Ausführung der folgenden Abfragen:

SELECT * FROM dbo.tbl_PhoneBook WHERE LastName = 'Faber';
SELECT * FROM dbo.tbl_PhoneBook WHERE LastName = 'Faber' AND FirstName = 'Sabine';

Query 04 - Execution Plan

Nun wird auch bei Ausgabe der Telefonnummer ein INDEX SEEK durchgeführt, da sich die Telefonnummer nun im Leaf-Level (Daten) des Index befindet. Ein kostenintensiver KeyLookup muß nicht mehr durchgeführt werden und der Index kann vollständig verwendet werden

Index structure pages new

Einen – winzigen – Nachteil hat natürlich diese Variante – es bedeutet mehr Speicher für den einzelnen Datensatz im Leaflevel. In den B-Trees werden diese informationen nicht gespeichert!

Suche nach Vornamen

Die Suche nach Vornamen kann weder durch den Clustered Index noch durch den zuvor geänderten Index ix_tbl_PhoneBook_LastName_FirstName performant gestaltet werden; die Gründe wurden weiter oben schon erläutert. Um dennoch auch performant nach Vornamen suchen zu können, muss ein weiterer Index implementiert werden.

CREATE INDEX ix_tbl_PhoneBook_FirstName ON dbo.tbl_PhoneBook
(FirstName) INCLUDE (LastName, PhoneNumber);

Durch den obigen Index kann SQL Server nun gezielt nach Vornamen suchen. Wichtig ist in diesem Fall natürlich auch, die weiteren Attribute nicht zu vergessen, die mit augegeben werden sollen. Ansonsten würde der Index nicht genutzt werden können, da diese Informationen aus dem Clustered Index ermittelt werden müßten. Der Test mit der nachfolgenen Abfrage zeigt nun eine deutliche Verbesserung des Ausführungsverhaltens:

SELECT * FROM dbo.tbl_PhoneBook WHERE FirstName = 'Sabine';

Query 05 - Execution Plan

Weitere Indexe müssen nicht implementiert werden, da alle Ausführungskombinationen abgedeckt wurden. Die Suche ausschließlich nach den Nachnamen wird – wie bereits weiter oben gesehen – durch den Index ix_tbl_PhoneBook_LastName_FirstName abgedeckt.

Fazit

Indexe sind der Schlüssel zu performanten Abfragen. Es gilt, im Vorfeld schon genau zu wissen, welche Abfragen auf Attribute einer Relation ausgeführt werden. Ein Index muss auch immer wieder auf den Prüfstand kommen, da auf Basis von gestiegenem Datenvolumen Ausführungstrategien gewählt werden, die ein sofortiges Eingreifen erforderlich machen.

Das obige Beispiel hat gezeigt, dass bereits durch geringfügige Änderungen an bestehenden Indexen die Performance erheblich gesteigert werden kann. In diesem speziellen Fall ließ sich die Abfrage von ~20 Sekunden auf 0,854 Sekunden reduzieren.

Als Datenbankentwickler ist man meines Erachtens in die Pflicht genommen, sich intensiv mit Indexen und ihrer Arbeitsweise auseinander zu setzen. Indexe sind ein wichtiger und strategischer Baustein im Bauwerk einer schnellen Datenbankanwendung – ihn sinnvoll zu nutzen erwartet der Kunde und Arbeitgeber.

Herzlichen Dank für’s Lesen.

Beispieldatenbankscripte: http://www.db-berater.de/files/blogs/multi-column-indexes.zip
clustered index http://msdn.microsoft.com/de-de/library/ms190639(v=sql.105).aspx
heaps http://technet.microsoft.com/de-de/library/ms188270(v=sql.100).aspx
DBCC IND http://db-berater.blogspot.de/2012/11/optimierung-von-datenbankmodellen_11.html
dm_db_database_page_allocations http://db-berater.blogspot.de/2012/11/neue-dmv-fur-aufteilung-der-pages_25.html
Architektur von Relation und Index http://msdn.microsoft.com/de-de/library/ms180978(v=sql.105).aspx
DBCC TRACEON (3604) http://blogs.msdn.com/b/askjay/archive/2011/01/21/why-do-we-need-trace-flag-3604-for-dbcc-statements.aspx
KeyLookup http://technet.microsoft.com/de-de/library/bb326635(v=sql.105).aspx
Indexing – INCLUDE

http://msdn.microsoft.com/de-de/library/ms190806(v=sql.90).aspx

Keine Kommentare:

Kommentar veröffentlichen