Nachdem im ersten Beitrag die Datenstruktur auf den Prüfstand kam und bereits Optimierungspotential bei der Auswahl der richtigen Datentypen und Datengrößen bestand, möchte ich mit dem aktuellen Beitrag etwas detaillierter auf Indexe und deren Optimierung eingehen. Der nachfolgende Beitrag beschäftigt sich zunächst einmal mit dem “Clustered Index” der im Beispiel verwendeten Struktur der Relation dbo.tbl_Companies.

Die nachfolgende Tabellenstruktur wird für die Funktionsweise des Clustered Index und seine Analyse verwendet.

CREATE TABLE dbo.tbl_Companies
(
     Id         int           NOT NULL IDENTITY(1,1),
     Name       nvarchar(128) NULL,
     TaxNo      varchar(24)   NULL,
     CostCenter char(7)       NULL,
     UpdateBy   varchar(20)   NULL,

     CONSTRAINT pk_tbl_Companies PRIMARY KEY CLUSTERED (Id)
)
GO

Ich werde nicht im Detail auf die Grundlagen von Indexes eingehen sondern vielmehr unter dem Gesichtspunkt der Optimierung und der Analyse von Indexen die Probleme erläutern. Wie die obige Struktur zeit, liegt auf dem Attribut [Id] der Clustered Index. Dies bedeutet zunächst einmal, dass die Relation basierend auf den Attributen des Indexes Datensätze sortiert und speichert. Pro Tabelle kann immer nur EIN clustered Index verwendet werden, da – das ist nur logisch – Datensätze immer nur nach einer Regel sortiert und gespeichert werden können.

Bei der Wahl der geeigneten Attribute für einen "clustered Index” sollte man sorgfältig überlegen, was genau die Entscheidung bedeutet. Wie bereits oben erwähnt bedeutet der “clustered Index” eine physikalische Sortierung der Daten einer Relation. Dies bedeutet bei INSERT, UPDATE, DELETE des Schlüsselattributes zwangsläufig auch einen durchzuführenden Sortierungsvorgang beim Schreiben der Daten.

Kardinalität der Daten im Schlüsselattribut

Für die Auswahl des geeigneten Schlüsselattributs für einen “Clustered Index” sollte zunächst überlegt werden, wie eindeutig die Schlüsselattribute des Index sind. Würde z. B. in unserer Beispielrelation das Attribut [Name] den “Clustered Index” bilden, ist die Eindeutigkeit zwar recht hoch (hohe Kardinalität); es besteht jedoch die Möglichkeit, dass Schlüsselwerte redundant sind. Für eine Analyse der Datenstruktur habe ich die nachfolgende Abfrage gegen die Datenbank laufen lassen:

SELECT TOP 10
       Name     AS CompanyName,
       COUNT(1) AS Kardinalität
FROM   dbo.tbl_Companies
GROUP BY
       Name
HAVING COUNT(1) != 1
ORDER BY
       COUNT(1) DESC

Das Ergebnis zeigt, dass es Einträge gibt die häufiger als ein Mal vorkommen (Redundanzen)

Die Frage, die sich nun automatisch ergibt: “Wie kann SQL Server bei solchen Datensätzen die Eindeutigkeit gewähren?” Genau hier liegt bei der Definition des “Clustered Index” die Krux. Nehmen wir als Beispiel das Unternehmen “Ernst & Young AG”. Dieser Eintrag kommt in der Relation gem. Abfrage sieben Mal vor. Schauen wir uns zunächst einmal das Ergebnis für einen solchen “Clustered Index” an: 

ALTER TABLE dbo.tbl_Companies
DROP CONSTRAINT pk_tbl_Companies;

ALTER TABLE dbo.tbl_Companies
ADD CONSTRAINT pk_tbl_Companies PRIMARY KEY NONCLUSTERED(Id);

Zunächst wird die vorhandene Einschränkung gelöscht um anschließend die Einschränkung OHNE Clustered Index wieder anzulegen. Somit können wir nun einen neuen Clustered Index anlegen.

CREATE CLUSTERED INDEX ci_tbl_Companies ON dbo.tbl_Companies (Name);

Schauen wir uns das Ergebnis etwas genauer an, indem wir uns die Liste der Indexe für die Relation dbo.tbl_Companies betrachten:

SELECT index_id, name, type_desc, is_unique, is_primary_key
FROM sys.indexes WHERE object_id = OBJECT_ID('dbo.tbl_Companies')

Auffällig ist hier, dass der “Clustered Index” nicht zwingend eindeutig sein muss – er regelt nur die physikalische Sortierung der Daten innerhalb der Relation! Ein wichtiger Hinweis sei genannt: Ein “Clustered Index” hat immer die Index_Id 1! 

Aber wie schafft es SQL Server nun, die Eindeutigkeit eines Datensatzes zu gewährleisten? Hierzu müssen wir etwas tiefer in die Strukturen von Indexen einsteigen. Zunächst gilt das Interesse den Informationen zum “Clustered Index”, die “unter der Motorhaube” liegen. Für die – leichtere – Analyse müssen ein paar Vorbereitungen getroffen werden, die spätere Analysen signifikant erleichtern. Den “Trick” dazu habe während meiner Vorbereitungen zum MCM SQL Server 2008 aus einem der Videos von Kimberly L. Tripp entnommen (http://technet.microsoft.com/en-us/sqlserver/gg508877.aspx).

Der technische Hintergrund für das nun folgende Szenario ist relativ schnell erklärt. Mit Hilfe des nicht dokumentierten Befehls “DBCC IND” ist es möglich, eine Liste aller Pages zu erhalten, die von einem Index verwendet werden. Leider jedoch ist es nicht möglich, diese Ausgabe nach eigenen Kriterien zu sortieren. Gleichwohl muss für eine Analyse DBCC erneut aufgerufen werden, um weitere Informationen zu erhalten. Um diesen Prozess zu verkürzen, lässt man das Ergebnis von DBCC IND mittels EXEC in eine nicht flüchtige Relation umleiten. Diese Relation kann dann beliebig oft abgefragt werden.

Erstellung der Relation für die Zwischenspeicherung von Ergebnissen aus DBCC IND

Um die Tabelle aus jeder Datenbank zu nutzen, wird die Relation für die Speicherung von Ergebnissen zu DBCC IND in der master-Datenbank angelegt. Damit sie unabhängig vom Kontext der aktuellen Datenbank aufgerufen werden kann, erhält die Relation das Präfix sp_. Weiterführende Informationen zu Systemobjekte und ihre Speicherung in master finden sich in den BOL von Microsoft SQL Server.

CREATE TABLE master.dbo.sp_table_pages
(
PageFId bigint,
PagePId bigint,
IAMFId bigint,
IAMPId bigint,
ObjectId bigint,
IndexId bigint,
PartitionNumber bigint,
PartitionId bigint,
iam_chain_type nvarchar(255),
PageType bigint,
IndexLevel bigint NULL,
NextPageFId bigint,
NextPagePId bigint,
PrevPageFId bigint,
PrevPagePId bigint,

CONSTRAINT pk_sp_table_pages PRIMARY KEY CLUSTERED
(
PageFId,
PagePId
)
);
GO

Verwendung der Relation als Speicher für die Ergebnisse von DBCC IND

Nachdem das Objekt erstellt wurde, kann es für die Speicherung von Ergebnissen zu DBCC IND verwendet werden. Dazu wird die Relation vor jedem Aufruf zunächst geleert und anschließend mit dem Ergebnis des Aufrufs gefüllt.

TRUNCATE TABLE sp_table_pages;

INSERT INTO sp_table_pages
EXEC ('DBCC IND (DatenbankName, TabellenName, 1)');

Durch den obigen Aufruf wird das Objekt zunächst geleert um anschließend mit dem Ergebnis von DBCC IND zum Index 1 (Clustered Index) gefüllt zu werden.

Auswertung der Ergebnismenge von DBCC IND

Sobald die Daten in die Relation umgeleitet wurden, kann das Ergebnis genauer untersucht werden. Der Aufruf für die Beispieldatenbank sieht wie folgt aus:

TRUNCATE TABLE sp_table_pages;

INSERT INTO sp_table_pages
EXEC ('DBCC IND (MCM2008_Partial, tbl_Companies, 1)');

SELECT PageFId,
PagePId,
IndexId,
PageType,
IndexLevel,
NextPagePId,
PrevPagePId
FROM sp_table_pages
ORDER BY
IndexLevel DESC,
PrevPagePId;

Bei der Abfrage der Ergebnismenge ist die Sortierung relevant. Jede Indexstruktur beginnt in einem sogenannten Root-Level. Das Root-Level hat bei der Ausgabe von DBCC IND immer den höchsten Wert. Weitere Informationen zu Indexstrukturen finden sich in der Linkliste am Ende dieses Artikels.

Das Rootlevel des “Clustered Index” beginnt im Level 1, somit gibt es keine weiteren B-Tree-Levels mehr, bis so viele Daten in der Relation sind, dass die Informationen nicht mehr komplett auf eine Indexseite passen. Das Root-Level besteht immer nur aus einer Seite, somit gibt es keine “vorherige” Seite (PrevPageId) und keine “nachfolgende “Seite” (NextPagePId). 

Die eigentlichen Daten eines Index befinden sich immer im sogenannten Leaf-Level (IndexLevel = 0). Wie man aus der obigen Abbildung erkennen kann, beginnt der Leaf-Level bei der Seite 400 (PageId) und wird bei Seite 401 fortgesetzt (NextPagePId). In Zeile 3 der Ergebnismenge wird die Seite 401 (PageId) gelistet. Die Daten werden auf Seite weiter geführt (NextPagePId) und die Seite hat als Vorgänger Seite 400 (PrevPageId).

Struktur des Clustered Index bei nicht eindeutigen Daten

Nachdem nun klar ist, wie man die Strukturen eines Index schnell und einfach abrufen kann, geht es einen Schritt weiter und wir analysieren, wie die Indexdaten im Leaf-Level gespeichert sind – wir wissen, dass der Leaf-Level der Bereich des Index ist, in dem die Daten selbst hinterlegt sind. Um sich den Inhalt einer Seite anzuschauen, verwendet man den – ebenfalls nicht dokumentierten – Befehl DBCC PAGE.

Schauen wir uns die Indexwerte zu “Ernst & Young” an, aber wie wissen wir, in welcher Indexseite sich die Informationen dem gesuchten Datensatz befinden? Nun, indem wir es genau so machen, wie es auch der SQL Server selbst macht. Wir beginnen zunächst in der höchsten Ebene (in unserem speziellen Fall das Root-Level. Um detaillierte Informationen zu einer Seite zu erhalten, muss jedoch das Traceflag 3604 aktiviert sein. Durch die Aktivierung des Traceflags 3604 wird die Ausgabe nicht in das Errorlog des SQL Servers geleitet sondern auf der Clientseite ausgegeben. 

DBCC TRACEON (3604);
GO

DBCC PAGE ('MCM2008_Partial', 1, 464, 3)

Das Ergebnis von DBCC PAGE mag zunächst überraschen – man sieht “reale” Daten, wo man ev. mit Hexwerten, Links, kryptische Zeichen, etc. gerechnet hätte. In einem B-Tree werden nur die Informationen zum ERSTEN Eintrag in einer Seite eines Leaf-Levels gespeichert. Wird das berücksichtigt, trifft für die Analyse des obigen Ergebnisses folgende Aussage zu. 

Der Indexwert “Ernst & Young” befindet sich alphabetisch zwischen “Equus Informatica SA” und “Fidus Objects AG” Da “Fidus Objects AG” der erste Eintrag auf der Datenseite 443 ist, kann sich der von uns gesuchte Wert nur auf der Datenseite 442 befinden. Also schauen wir uns im nächsten Schritt die Datenseite 442 etwas genauer an:

DBCC PAGE ('MCM2008_Partial', 1, 443, 3) WITH TABLERESULTS;

Da sich die Abfrage der Seite nun auf dem Leaf-Level befindet, können die vollständigen Datensätze angezeigt werden. Damit das Ergebnis tabellarisch ausgegeben wird, wurde die Option “WITH TABLERESULTS” dem DBCC Command hinzugefügt. Betrachtet man nun einen von SQL Server verwalteten Datensatz in einem “Clustered Index” fällt auf, dass jeder Datensatz ein Attribut enthält, dass kein Bestandteil der eigentlichen Datenstruktur ist. Das Attribut [UNIQUIFIER] wird der Datenstruktur hinzugefügt, um eine Eindeutigkeit zu gewährleisten. Ist das Attribut eines “Clustered Index” nicht eindeutig, fügt SQL Server automatisch einen [UNIQUIFIER] hinzu. Dieses Attribut hat eine Größe von 4 Byte, die ZUSÄTZLICH zum eigentlichen Schlüsselattribut für jeden Datensatz gespeichert werden muss. In der obigen Abbildung sieht man sehr deutlich, dass bei Redundanz des Attributes [Name] der [UNIQUIFIER] entsprechend hochgezählt wird. Auch sehr schön zu erkennen ist die Gesamtgröße des “Clustered Index” pro Datensatz.

Struktur des Clustered Index bei nicht eindeutigen Daten

Unter Berücksichtigung des obigen Ergebnisses wird nun de Struktur der Relation wie folgt geändert:

• Der “Clustered Index” wird gelöscht, so dass das Attribut [Name] nicht mehr für den Clustered Index verwendet wird
• Ein neuer “Clustered Index” unter Berücksichtigung des Attributs [Id] wird erstellt. Dieser “Clustered Index” wird als eindeutiger Index angelegt

DROP INDEX ci_tbl_Companies ON dbo.tbl_Companies;
GO

CREATE UNIQUE CLUSTERED INDEX ci_tbl_Companies ON dbo.tbl_Companies (Id);
GO

Nachdem der “Clustered Index” neu erstellt wurde, wird der Index erneut untersucht. Also werden die Informationen über die Seiten mittels DBCC IND erneut analysiert. Bei der Ausführung der nachfolgenden Abfrage wird folgende Ergebnismenge ausgegeben:

SELECT Id, Name, TaxNo, CostCenter, UpdateBy
FROM dbo.tbl_Companies WHERE Name = 'Ernst & Young AG'

Das Ergebnis der Abfrage zeigt eine eindeutige ID für jeden Datensatz. Das Attribut [Id] ist das Alleinstellungsmerkmal für jeden Datensatz. Nun bildet dieses Attribut den “Clustered Index” und es ist interessant, wie diese Informationen auf den Indexseiten gespeichert werden. Für die nachfolgende Analyse ist der Bereich von 1462 – 1468 interessant. Diese Informationen gilt es im Leaf-Level zu finden. Begonnen wird wieder mit dem Root-Level: 

Das Root-Level beginnt auf Seite 431. Das ist der Einstiegspunkt für die weitere Suche nach den Datensätzen.

DBCC PAGE ('MCM2008_Partial', 1, 431, 3)

Die von uns gesuchten Werte müssen sich auf der Seite 1204 befinden, da der kleinste gespeicherte Wert für ID auf der Seite 1204 bei 1449 beginnt. Auf Seite 1205 beginnt der Wert für ID bei 1530. Somit die gesuchten Werte zwischen 1205 und 1529 auf der Datenseite 1204 lokalisiert werden.

DBCC PAGE (‘MCM2008_Partial’, 1, 1204, 3) WITH TABLERESULTS

Auffällig ist, dass für im Index selbst kein UNIQUIFIER mehr benötigt wird, da das Attribut [Id] die Eindeutigkeit des Datensatzes garantiert. Neben diesem Effekt fällt auf, dass der Index deutlich weniger Speicherplatz benötigt.

Fazit

Bei der Auswahl eines “Clustered Index” ist nach Möglichkeit darauf zu achten, dass das Schlüsselattribut eindeutig ist. Sofern eine Eindeutigkeit nicht gegeben ist, fügt SQL Server automatisch eine interne Versionierung für die Durchsetzung der Eindeutigkeit ein. Dieser “Overhead” wird für JEDEN Datensatz in der Relation mitgeführt und vergrößert die Datengröße um 4 Byte (Integer). Der optimale “Clustered Index” ist möglichst klein (INT / BIGINT) und sollte nur eindeutige Werte beinhalten.

Beachten Sie bei der Definition des “Clustered Index” fortlaufende Werte verwendet, damit bei einem INSERT Verzögerungen vermieden werden.

Herzlichen Dank für’s Lesen
Das Script für die Datenbank und ihr Testdaten können Sie hier herunterladen:
http://www.db-berater.de/files/database-Indexing.zip