In einem Gespräch mit einem Kollegen im aktuellen Projekt wurde behauptet, dass ein INSERT in einem HEAP immer schneller und effizienter sei als in einem Clustered Index, da ja neue Daten grundsätzlich fortlaufend am Ende der Relation (letzte Datenseite) eingefügt werden. Diese Behauptung ist NICHT richtig wie der nachfolgende Artikel demonstriert.

Was ist ein Heap

Unter einem HEAP versteht man eine Relation, die kein Clustered Index ist. Daten werden in einem HEAP nicht nach einer spezifizierten Ordnung gespeichert!

Testumgebung

Für die Beweisführung, dass Daten von Microsoft SQL Server sehr effizient auch in einem HEAP verwaltet werden, dient die folgende Struktur:

 1: CREATE TABLE dbo.tbl_heap

 2: (

 3:     KeyId       uniqueidentifier  NOT NULL    DEFAULT (newid()),

 4:     col1        char(200)         NOT NULL,

 5:     col2        varchar(200)      NOT NULL,

 6:     col3        datetime          NOT NULL    DEFAULT (getdate()),

 7:     InsertPos   int               NOT NULL    Identity (1, 1)

 8: );

Die Relation besitzt keine Indexe. Das Attribut [InsertPos] wird verwendet, um zu demonstrieren, wann und an welcher Position ein Datensatz eingetragen wurde. In die Relation [dbo].[tbl_heap] werden mit dem folgenden Code 1.000 Datensätze eingetragen:

 1: DECLARE    @i int    =    1

 2: WHILE @i <= 1000

 3: BEGIN

 4:     INSERT INTO dbo.tbl_heap(col1, col2)

 5:     SELECT 'This is stuff ' + CAST(@i % 10 AS varchar(2)),

 6:            'This is stuff ' + CAST(@i % 100 AS varchar(3)) + ', too';

 7:  

 8:     SET    @i += 1;

 9: END

Das Ergebnis – insbesondere unter Ausgabe der gespeicherten physikalischen Position – stellt sich wie folgt dar:

 1: SELECT sys.fn_PhysLocFormatter(%%physloc%%) AS Location, * FROM dbo.tbl_heap ORDER BY InsertPos;

Die Abbildung zeigt den logischen und physikalische Speicher nachdem die Daten eingetragen wurden. Auf eine Datenseite passen ungefähr 30 Datensätze. Die ersten 30 Datensätze befinden sich auf der Datenseite 324 (kann bei eigenen Tests abweichen!). Im nächsten Schritt werden die Datensätze mit [InsertPos] BETWEEN 16 AND 30 aus dem HEAP gelöscht und anschließend erneut die Daten abgefragt.

 1: DELETE    dbo.tbl_heap WHERE InsertPos BETWEEN 16 AND 30;

 2: GO

 3:  

 4: SELECT sys.fn_PhysLocFormatter(%%physloc%%) AS Location, * FROM dbo.tbl_heap ORDER BY InsertPos;

Die obige Abbildung zeigt, dass die Datensätze 16 – 30 gelöscht wurden und der “nächste” Datensatz mit der [InsertPos] = 31 auf der Datenseite 326 beginnt.

Inhalt der Datenseite

Die Datenseite 324 gilt es nun – insbesondere im Hinblick auf die Begründung der nachfolgenden Ergebnisse – etwas genauer zu untersuchen. Interessant ist der Pageheader sowie der Slot Array der betroffenen Datenseite

 1: DBCC TRACEON (3604);

 2: DBCC PAGE ('db_demo', 1, 324, 0);

Die obige Abbildung zeigt den Page Header der betroffenen Seite (324). Insgesamt werden 30 Datensätze (m_slotCnt) auf der Datenseite verwaltet. Jedoch hat die Datenseite ein freies Volumen von 4.145 Bytes (m_freeCnt). Der nächste zusammenhängende freie Platz beginnt bei Offset 7.887 (m_freeData). Diese Berechnung scheint irgendwie skurril; einer Datenseite stehen 8.060 Bytes für die Speicherung von Datensätzen zur Verfügung. Sofern 4.145 Bytes noch zur Verfügung stehen, ergibt das Offset von 7.887 keinen rechten Sinn. Aufschluss über diese Kuriosität gibt ein Blick auf den HexDump der Page sowie das Slot Array.

 1: DBCC PAGE ('db_demo', 1, 324, 2);

Die obige Abbildung zeigt, dass auf der Datenseite noch “Reste” der alten Datensätze vorhanden sind. Ein Blick auf das Slot Array jedoch zeigt, dass eine tatsächliche Belegung nur bis Slot(s) 14 vorliegt. Obwohl sich noch “Daten” auf der Datenseite befinden, werden sie nicht mehr verwendet – alle Slot Arrays >= 15 haben eine Länge von 0 (unbelegt). Aus Performancegründen werden die Daten von Microsoft SQL Server bei einem Löschvorgang nicht gelöscht sondern es werden nur die Slotzuweisungen entfernt. Dadurch wird der Löschvorgang selbst optimiert und erst beim Einfügen neuer Daten werden die “Altbestände” überschrieben.

Einfügen eines neuen Datensatzes

Träfe die Behauptung des Kollegen zu, sollte – wenn ein neuer Datensatz eingetragen wird – dieser Datensatz auf der letzten Datenseite eingetragen werden. Die Analyse der physikalischen Position sowie der Datenseiten zeigt jedoch, dass diese Annahme falsch ist:

 1: INSERT INTO dbo.tbl_Heap (col1, col2, col3)

 2: VALUES ('Donald', 'Daisy', '19640218')

 3:  

 4: -- Output by order of insertion

 5: SELECT sys.fn_PhysLocFormatter(%%physloc%%) AS Location, * FROM dbo.tbl_heap ORDER BY InsertPos DESC;

Wie die obige Abbildung deutlich zeigt, wurde der neue Datensatz als 1.001 Datensatz eingetragen. Statt jedoch – wie ursprünglich vermutet – auf der letzten Datenseite befindet sich der neue Datensatz tatsächlich auf der ersten belegten Datenseite. Ein Blick auf die Datenseite selbst zeigt die physikalische Speicherung.

Der neue Datensatz aus Slot(s) 15 wurde bei Offset 7.887 gespeichert. Schaut man sich noch einmal die Abbildung des Page Headers weiter oben an, erkennt man die Zusammenhänge; Microsoft SQL Server hat erkannt, dass der neue Datensatz auf die Seite 324 passt. Aus dem Pageheader wurde das Offset ausgelesen, an dem der neue Datensatz beginnen kann. Durch dieses Verfahren kann die Speicherung sehr schnell durchgeführt werden, da keine Daten “verschoben” werden müssen.

Nun wird ein weiterer Datensatz eingetragen und das Ergebnis betrachtet:

 1: INSERT INTO dbo.tbl_Heap (col1, col2, col3)

 2: VALUES ('Mickey', 'Minnie', '19920323')

 3:  

 4: SELECT sys.fn_PhysLocFormatter(%%physloc%%) AS Location, * FROM dbo.tbl_heap ORDER BY InsertPos DESC;

Auch dieser Datensatz wurde auf der ersten Datenseite gespeichert – insgesamt stand immer noch ausreichend Platz zur Verfügung, um den Datensatz zu speichern. Interessant ist jedoch die Organisation der Slots wie die nachfolgende Abbildung zeigt:

Während der zuvor eingefügte Datensatz noch vollständig an das Ende der Datenseite gepasst hat, war es beim zweiten INSERT nicht mehr möglich. Da jedoch ausreichend Platz auf der Datenseite vorhanden gewesen ist, hat Microsoft SQL Server die Daten auf der Datenseite neu angeordnet und – wie die Abbildung deutlich zeigt – den zuvor eingetragenen Datensatz unmittelbar hinter den letzten nicht gelöschten Datensatz positioniert (siehe Offset) um den zuletzt eingetragenen Datensatz am Ende einzutragen.

Die beiden markierten Transaktionen zeigen die unterschiedlichen Operationen, die während der Einfügevorgänge vorgenommen wurden. Nachdem – beim ersten Einfügevorgang – der Datensatz in den HEAP eingetragen wurde, hat sich der Füllgrad der Datenseite verändert und die PFS (Page Free Space) wurde entsprechend aktualisiert [LOP_SET_FREE_SPACE].

PFS – Page Free Space

PFS-Seiten (Page Free Space) zeichnen den Zuordnungsstatus der einzelnen Seiten auf, ob eine einzelne Seite zugeordnet wurde und die Menge des freien Speicherplatzes auf den einzelnen Seiten. Der PFS verfügt über ein Byte pro Seite und zeichnet auf, ob die Seite zugeordnet ist, und sofern dies der Fall ist, ob sie leer, 1 bis 50 Prozent voll, 51 bis 80 Prozent voll, 81 bis 95 Prozent voll oder 96 bis 100 Prozent voll ist. Der Status JEDER Datenseite wird durch eine Byte-Map verwaltet. Bits 0 – 2 bestimmen den Füllgrad der betroffenen Seite

Eine PFS-Seite ist nach der Dateiheaderseite die erste Seite in einer Datendatei (Seitennummer 1). Auf diese folgt eine GAM-Seite (Seitennummer 2) und anschließend eine SGAM-Seite (Seite 3). Alle 8.088 Seiten nach der ersten PFS-Seite folgt eine weitere PFS-Seite.

Nachdem die Hälfte der Datensätze von der Seite gelöscht wurde (siehe oben), musste der Status der – zu diesem Zeitpunkt – zu 100% gefüllten Datenseite in PFS aktualisiert werden. Bevor neue Datensätze eingetragen wurden, war die Datenseite zu maximal 50% gefüllt.

 1: -- Look into the page

 2: DBCC TRACEON (3604);

 3: DBCC PAGE ('db_demo', 1, 1, 3);

Nachdem der ersten Datensatz eingetragen wurde, sah das Speichervolumen der Datenseite wie folgt aus:

Bereits jetzt ist erkennbar, wie effektiv Microsoft SQL Server das Speichermanagement der Datenseiten organisiert. Wird in einem HEAP ein neuer Datensatz eingetragen, “scannt” Microsoft SQL Server zunächst die PFS für alle Datenseiten, die durch den HEAP belegt werden. Trifft Microsoft SQL Server auf eine Datenseite, die ausreichend Platz zur Verfügung stellt, kann der Datensatz schnell und effektiv gespeichert werden. Auf Grund der Informationen im Datenheader steht die Information bezüglich des Offsets für den Speichervorgang schnell und effektiv zur Verfügung.

Die Speicherung des ersten Datensatzes wurde am Ende der Datenseite vorgenommen, ein weiterer Datensatz passt nicht mehr an das unmittelbare Ende der Datenseite. Dennoch stehen zwischen 51% und 80% der Datenseite für weitere Speichervorgänge zur Verfügung.

Beim zweiten Speichervorgang organisiert Microsoft SQL Server die Datenseite neu um zukünftige Datensätze wieder am Ende einfügen zu können. Diese Reorganisation ist deutlich performanter als die Berechnung des freien Speichervolumens, um einen vollständigen Datensatz zwischen existierenden Datensätzen speichern zu können. Nachdem die Datensätze auf der Seite hintereinander gespeichert werden, können weitere Datensätze ans Ende angefügt werden.

Fazit

Microsoft SQL Server kann auf Grund eines effektiven Speichermanagements freigegebene Speicherbereiche auf Datenseiten von HEAPS jederzeit wiederverwenden. Hierzu bedient sich Microsoft SQL Server der Informationen, die auf der PFS gespeichert werden. Für JEDE in einer Datenbank verwendete Datenseite wird der Füllgrad in der PFS gespeichert. Dadurch ist Microsoft SQL Server in der Lage, schnell und effektiv den Speicherzustand jeder Datenseite zu ermitteln, die ein Objekt belegt. Findet Microsoft SQL Server eine Datenseite des Objekts, die den vollständigen Datensatz speichern kann, KANN es sein, das Microsoft SQL Server die Allokation auf dieser Datenseite vornimmt.

WICHTIG: Dieses Verfahren gilt nur für HEAPS, da in einem HEAP keine logisch geordnete Struktur vorhanden ist! Wer mehr Informationen zu diesem Thema wünscht: Am 05.11.2013 werde ich in Stockholm auch dieses Thema ausführlich mit Beispielen unterlegt behandeln.

http://db-berater.blogspot.de/2013/09/sqlrally-nordic-2013-sprecher-in.html

Herzlichen Dank fürs Lesen!