Dienstag, 20. August 2013

Umwandlung von Clustered Index in HEAP intern

Durch eine Frage im Microsoft Technet Forum habe ich bemerkt, dass sehr häuft die Vermutung geäußert wird, dass beim Löschen eines Clustered Index die Relation selbst vollständig neu aufgebaut wird. Diese Vermutung ist falsch und der nachfolgende Artikel zeigt, welche Operationen Microsoft SQL Server beim Löschen eines Clustered Index intern durchführt.

Problemstellung

In einer Relation mit mehr als 500 Millionen Datensätzen sollte ein Clustered Index gelöscht werden. Diese Operation wurde als sehr zeit- und ressourcenintensiv beschrieben. Aus dem Zeitverzug leitete man ab, dass Microsoft SQL Server beim Löschen eines Clustered Index die Relation neu aufbaut. Um das genaue – interne – Verfahren zu analysieren, dient das folgende Testszenario:

-- Creation of a relation for demonstration
IF OBJECT_ID('dbo.tbl_demo', 'U') IS NOT NULL
    DROP TABLE dbo.tbl_demo;
    GO

CREATE TABLE dbo.tbl_demo
(
    Id
      int          NOT NULL    IDENTITY (1, 1),
    col1   
char(189)    NOT NULL    DEFAULT ('just stuff'),
    col2   
char(200)    NOT NULL    DEFAULT ('more stuff')
);

-- Filling the table with a few records
SET NOCOUNT ON
GO

INSERT INTO dbo.tbl_demo DEFAULT VALUES
GO 100000

-- create two indexes for demonstration
CREATE UNIQUE CLUSTERED INDEX tbl_demo_Id ON dbo.tbl_demo (Id);
CREATE INDEX tbl_demo_Col1 ON dbo.tbl_demo(Col1);
GO

Der obige Code erzeugt eine Relation mit dem Namen [dbo].[tbl_demo] und fügt 100.000 Datensätze ein. Anschließend werden sowohl ein clustered Index [tbl_demo_id] als auch ein non clustered Index [tbl_demo_col1] angelegt. Nachdem die 100.000 Datensätze eingetragen wurden, ergeben sich für die physikalischen Strukturen beider Indexe folgende Bilder:

-- Check the physical index stats
SELECT  OBJECT_NAME(i.object_id)    AS    object_name,
        i.name,
        i.index_id,
        index_level,
        index_type_desc,
        page_count,
        record_count
FROM    sys.indexes i INNER JOIN sys.dm_db_index_physical_stats(db_id(), OBJECT_ID('dbo.tbl_demo', 'U'), DEFAULT, DEFAULT, 'DETAILED') ps
        ON  (
                i.object_id = ps.object_id AND
                i.index_id = ps.index_id
            )
ORDER BY
        i.index_id ASC,
        ps.index_level ASC;

PHYSICAL_STATS_01

Der Clustered Index besitzt ein ROOT-Level (index_level = 2) sowie ein B-Tree-Level (index_level = 1). Im LEAF-Level (index_level = 0) befinden sich die Daten verteilt auf 5004 Datenseiten. Da der Clustered Index die Relation selbst ist, beinhalten die LEAF-Level ALLE Daten der Relation.

Die interne Struktur des Clustered Index stellt sich wie folgt dar (Auszug aus den ersten Datenseiten):

SELECT  page_type_desc,
        page_level,
        previous_page_page_id,
        allocated_page_page_id,
        next_page_page_id
FROM    sys.dm_db_database_page_allocations
        (
            db_id(),
            OBJECT_ID('dbo.tbl_demo', 'U'),
            1,
            DEFAULT,
           
'DETAILED'
        )
WHERE   is_allocated = 1
ORDER BY
        page_type DESC,
        page_level DESC,
        previous_page_page_id ASC;

PAGE_ALLOCATIONS_01

Ebenfalls Aufschluss über den allokierten Datenspeicher geben die nachfolgenden Abfragen, die mit Hilfe von sys.fn_PhysLocFormatter Informationen über die Position eines Datensatze geben:

-- see the location of each record in the affected index
SELECT sys.fn_PhysLocFormatter(%%physloc%%) AS Location, * FROM dbo.tbl_demo WITH (INDEX (tbl_demo_Id));
SELECT sys.fn_PhysLocFormatter(%%physloc%%) AS Location, * FROM dbo.tbl_demo WITH (INDEX (tbl_demo_Col1));

RECORDSET_01

Die obere Ergebnismenge zeigt die Datensätze 1-7 des Clustered Index, die auf Datenseite 20.256 beginnen. Die Daten des non clustered Index [tbl_demo_col1] beginnen auf der Datenseite 25.632. Nun wird der Clustered Index gelöscht und aus der Relation wird automatisch ein HEAP. An diesem Punkt setzt die eigentliche Untersuchung an. Die Vermutung einiger Foristen war, dass Ursache für die lange Ausführungszeit der Neuaufbau der Relation selbst sowie möglicher vorhandener non clustered Indexe ist. Um die Transaktion später gezielt aus dem Transaktionsprotokoll zu filtern, wird eine benannte Transaktion für das Löschen des Clustered Index verwendet! Anschließend wird erneut die Information über den allokierten Datenspeicher in Verbindung mit den vorhandenen Daten ausgegeben. Ist die Annahme der Foristen korrekt, muss sich für jeden Datensatz im Clustered Index die allokierte Datenseite geändert haben, da ein REBUILD immer Daten aus den bereits allokierten Datenseiten in neue Datenseiten verschiebt!

-- drop the clustered index which will turn the relation into a HEAP
BEGIN TRANSACTION DropClusteredIndex
DROP INDEX tbl_demo_Id ON dbo.tbl_demo;
COMMIT TRANSACTION DropClusteredIndex
GO

-- see the location of each record in the affected index
SELECT sys.fn_PhysLocFormatter(%%physloc%%) AS Location, * FROM dbo.tbl_demo ORDER BY Id;
SELECT sys.fn_PhysLocFormatter(%%physloc%%) AS Location, * FROM dbo.tbl_demo WITH (INDEX (tbl_demo_Col1))
ORDER BY Id;

RECORDSET_02

Das Ergebnis für die – nun zu einem Heap gewandelten – Tabelle ist überraschend. Die allokierten Datenseiten haben sich NICHT verändert. Die Datensätze sind auch weiterhin auf den zuvor allokierten Datenseiten gespeichert; die Datenseiten des non clustered Index haben sich jedoch geändert – dieser Index wurde also neu aufgebaut! Das Transaktionsprotokoll zeigt auch deutlich, warum sich an den Datenzuordnungen für den Clustered Index nichts geändert hat:

SELECT Operation, Context, AllocUnitId, AllocUnitName, [Lock Information]
FROM sys.fn_dblog(NULL, NULL)
WHERE [Transaction ID] IN
(
  
SELECT [Transaction ID]
  
FROM   sys.fn_dblog(NULL, NULL)
  
WHERE  [Transaction Name] = 'DropClusteredIndex'
);

FN_DBLOG_01

Die Abbildung zeigt einen verkürzten Auszug des Inhalts des Transaktionsprotokolls für die einzelnen Operationen, die während des Löschens des Clustered Index protokolliert wurden. Insgesamt sind es weit über 150 Einzeloperationen, von denen einige für die technische Begründung wichtig sind. Man kann deutlich erkennen, dass Microsoft SQL Server nicht die Daten selbst verändert sondern die Datenseiten für die Speicherung der Metadaten eines Objekts manipuliert:

PFS Page Free Space Informationen über allokierten und freien Speicher auf den Datenseiten
GAM / SGAM Global Allocation Map
Shared Global Allocation Map
Informationen, ob Extents (8 Datenseiten = 1 Extent) allokiert oder verfügbar sind.
IAM Index Allocation Map Informationen über Extents, die von einem Clustered Index oder einem non clustered Index allokiert werden.

Die Funktionsweise jedes einzelnen Datenseiten-Typs würde den Rahmen dieses Artikels sprengen. Wer mehr über die Struktur einer Datenbank / Datenseite / Record erfahren möchte, dem sei z. B. der folgende Artikel von Paul S. Randal empfohlen:

Inside the Storage Engine: GAM, SGAM, PFS and other allocation maps”. Alternativ zum World Wide Web sei das Buch “Microsoft SQL Server 2012 Internals” von Kalen Delany ans Herz gelegt – ein Buch, dass in keiner gut sortierten Bibliothek eines SQL Server Experten fehlen darf. Dort finden sich im Kapitel “Databases Under the Hood” sehr detaillierte Informationen zu den einzelnen Seitentypen!

Aus dem Transaktionsprotokoll wird ersichtlich, dass ausschließlich Datenseiten zur Speicherung von Metadaten geändert werden. Die Daten selbst werden nicht geändert. Da nur die Strukturen der Datenseiten untereinander geändert wurden (ein HEAP hat z. B. keinen Intermediate Level (B-Tree) sondern ist eine vollkommen flache Struktur), werden keine Bewegungen der Daten selbst durchgeführt – sie verbleiben auf den ursprünglichen Datenseiten.

Als Beispiel für die Manipulation von Metadaten schauen wir etwas genauer auf die Zeile 11 des Transaktionsprotokolls. Dort insbesondere auf die [Lock Information]. Man kann erkennen, dass eine exklusive Sperre in Datenbank 19 (das ist meine Beispieldatenbank) – File 1 – Page 178 – Slot 5 gesetzt wurde, um einen Datensatz zu modifizieren. Schaut man sich noch einmal die Abbildung der “internen” Struktur (siehe oben) an, stellt man fest, dass die Datenseite 178 als IAM_PAGE allokiert wurde. Eine IAM-Datenseite speichert Informationen über Extents, die von einem Index allokiert werden. Ein Blick in die Datenseite selbst zeigt, dass einzelne Datenseiten nicht allokiert sind:

DBCC TRACEON (3604);
DBCC PAGE (19, 1, 178, 3);

DBCC_PAGE_01

Insgesamt sind folgende Bereiche “frei”, die mit den zuvor durch den B-Tree und Root-Level des Clustered Index allokierten Seiten abgeglichen wird:

Nicht allokiert Datenseiten im Root-Level oder Intermediate Level des Clustered Index
0 - 19960 179, 180, 410 – 414,
20464 - 20472 20464, 20465
24312 - 24319 24312
24464 - 24480 24472, 24473,
24976 - 24984 24976

Bei allen in der Tabelle genannten Datenseiten handelt es sich um die Root- und B-Tree-Datenseiten des Indexes. Es sind also tatsächlich keine Daten selbst gelöscht/verschoben worden sondern es wurden die Strukturen, die einen Index ausmachen, vollständig aufgehoben. Damit entspricht die Datenstruktur einer flachen Struktur mit einer Datenebene – ein HEAP!

Warum wurden die Datenseiten des non clustered Index neu organisiert?

Tatsächlich stellt sich – auf den ersten Blick – die Frage, warum ausgerechnet die Daten des non clustered Index neu organisiert wurden; dieser Index wurde doch durch die Anweisung, den Clustered Index zu löschen, nicht unmittelbar nicht betroffen. Das ein non clustered Index bei der Reorganisation einer Relation (HEAP / Clustered Index) direkt betroffen ist, hängt mit den eng verbundenen Strukturen zwischen Relation (Clustered Index / HEAP) und einem non clustered Index zusammen.

Jeder non clustered Index führt neben den eigenen Indexattributen IMMER den eindeutigen Schlüssel der Relation selbst mit. Bei einem Clustered Index ist dies immer der Clustered Key. Ist der Clustered Index nicht eindeutig, führt Microsoft SQL Server für die Eindeutigkeit des Datensatzes zusätzlich einen UNIQUIFIER mit. Dieser UNIQUIFIER in Verbindung mit dem Clustered Key sorgt für die Eindeutigkeit eines Datensatzes.

Besitzt ein Clustered Index einen Clustered Key als Referenzwert, kann ein HEAP nicht von solchen Strukturen profitieren. Ein HEAP definiert sich dadurch, dass es keine eindeutigen Kriterien für einen Datensatz gibt. In einem solchen Fall legt Microsoft SQL Server für die “interne” Eindeutigkeit einen eigenen “Schlüssel” – den sogenannten RID (RowLocator ID).

Nun versteht sich, warum der non clustered Index neu aufgebaut werden musste. Bevor der Clustered Index gelöscht wurde, wurde der Clustered Key ([Id]) der Relation als Pointer für den Zugriff auf die Daten verwendet wie die nachfolgende Abbildung zeigt:

DBCC_PAGE_02

Zu jedem Eintrag im non clustered Index wird der zugehörige Clustered Key als Pointer zu den eigentlichen Daten gespeichert. Durch dieses Verfahren kann Microsoft SQL Server alle erforderlichen Daten der Relation, die sich nicht auf den Indexseiten des non clustered Index befinden, unmittelbar mittels KeyLookup aus dem LEAF-Level des Clustered Index beziehen.

Der identische non clustered Index OHNE einen Clustered Index (HEAP) hat die folgende “Struktur”:

DBCC_PAGE_03

Man kann deutlich erkennen, dass nun neue Datenseiten allokiert wurden und die Länge eines Datensatzes verändert ist. Waren es mit dem Clustered Key (int) nur 4 Bytes, die pro Datensatz im Index gespeichert wurden, müssen nun 8 Bytes für den RID gespeichert werden.

Fazit

Das Löschen eines Clustered Index führt nicht dazu, dass die Relation selbst neu aufgebaut wird. Da beim Löschen eines Clustered Index ausschließlich die Strukturen geändert werden, ist eine Neuorganisation der Relation selbst nicht notwendig. Beim Löschen eines Clustered Index müssen aber ALLE non clustered Indexe vollständig neu aufgebaut werden, da kein Clustered Key mehr vorhanden ist, der eine Referenz / Pointer zu den Datenseiten selbst bildet. Statt eines Clustered Keys verwendet Microsoft SQL Server für einen HEAP eine eigene Methode für die Eindeutigkeit eines Datensatzes – den RowLocator (RID). Jeder non clustered Index benötigt diese neue “Referenz” und muss deswegen neu aufgebaut werden.

Herzlichen Dank fürs Lesen!

HEAP-Strukturen http://technet.microsoft.com/en-us/library/ms188270(v=sql.105).aspx
Clustered Index http://technet.microsoft.com/en-us/library/ms177443(v=sql.105).aspx
Nonclustered Index: http://technet.microsoft.com/en-us/library/ms177484(v=sql.105).aspx

Keine Kommentare :

Kommentar veröffentlichen