Diese Frage kam im Zusammenhang mit einem Thread in den Microsoft Foren auf. In der Fragestellung ging es darum, warum Microsoft SQL Server trotz ausreichendem Platz auf einer Datenseite den Platz nicht verwendet hat. Der nachfolgende Artikel beschreibt die Vorgehensweise von Microsoft SQL Server bei der “Suche” nach freiem Speicher in einem HEAP.

Testszenario

Gegeben ist eine Tabelle mit einer einfachen Datenstruktur, in die 3 Datensätze eingefügt werden.

CREATE TABLE dbo.tbl_Heap

(

    Id    int             NOT NULL  IDENTITY (1, 1),

    c1    varchar(2500)   NOT NULL

);

GO

INSERT INTO dbo.tbl_heap(c1) VALUES (REPLICATE('X', 2500));

GO 3

Eine Datenseite in Microsoft SQL Server besteht aus einem Header (96 Bytes) sowie einem Datenbereich (8.060 Bytes). Die Länge eines Datensatzes in der Tabelle [dbo].[tbl_Heap] besitzt eine Länge von 2.508 Bytes + einem Overhead von 8 Bytes für die Zeilenstruktur. Bei einem Datenbereich von 8.060 Bytes sollten also 3 Datensätze ohne Probleme auf eine Seite passen. Das Ergebnis überrascht jedoch:

SELECT    sys.fn_PhysLocFormatter(%%physloc%%) AS Location, * FROM dbo.tbl_heap;

Microsoft SQL Server hat die drei Datensätze auf zwei Datenseiten aufgeteilt obwohl ausreichend Platz für alle Datensätze auf einer Seite vorhanden gewesen wäre. Die Erklärung für dieses sonderbare Verhalten liegt in der Art und Weise, wie Microsoft SQL Server Daten in einem Heap verwaltet.

Begründung

Ein Heap ist eine “ungeordnete” Datenmenge, die willkürlich auf Datenseiten gespeichert wird; wobei der Begriff “ungeordnet” nicht bedeutet, dass Microsoft SQL Server willkürlich Datenseiten alloziert, um die Datensätze zu speichern. Tatsächlich werden die Datensätze in einer neuen Tabelle sequentiell gespeichert jedoch prüft Microsoft SQL Server bei jedem INSERT-Vorgang, ob auf der Datenseite noch ausreichend Platz vorhanden ist.

Genau an dieser Stelle tritt der große Unterschied zu einem CLUSTERED INDEX auf. In einem CLUSTERED INDE müssen die Daten zwingend – nach CLUSTERED KEY– sortiert vorliegen. Bei einem INSERT in einem CLUSTERED INDEX muss Microsoft SQL Server unmittelbar auf der Datenseite überprüfen, ob noch ausreichend Platz für einen neuen Datensatz vorhanden ist. Wenn kein Platz vorhanden ist, muss durch einen PAGE SPLIT neuer Platz geschaffen werden.

In einem HEAP müssen Daten nicht einem Ordnungsschlüssel folgend eingetragen werden; die Daten können/dürfen an willkürlicher Stelle eingetragen werden. In einem solchen Fall muss Microsoft SQL Server also nicht auf jeder Seite überprüfen, ob noch ausreichend Platz vorhanden ist – hier reicht eine Überprüfung auf “höherer” Ebene; es wird die PFS gescannt!

PFS – Page Free Space

PFS (Page Free Space) speichern Informationen über die Allokierung und den “Füllgrad” jeder Seite in einer Datenbank. In einer Datenbank ist die erste PFS immer auf Datenseite 1. Eine PFS speichert diese Informationen für maximal 8.088 Datenseiten (entspricht 64 MB) im jeweiligen Byte der PFS. Alle weiteren 64 MB wird eine neue PFS erstellt, die wiederum für die nächsten 8.088 Datenseiten Füllgrad und Allokierung überwacht. Eine PFS hat aber noch deutlich mehr Aufgaben zu bewältigen, die im Artikel “Under the covers: GAM, SGAM, and PFS pages” von Paul Randal beschrieben werden. Bezüglich des Füllgrads definieren die ersten 3 Bit in einem Byte den Zustand. Hierbei geht Microsoft SQL Server recht grob vor. Je nach Status bedeutet das für den Füllgrad folgenden Wert:

Den von Microsoft SQL Server definierte Füllgrad einer Seite kann man durch einen Blick auf die PFS unmittelbar erkennen.

DBCC TRACEON (3604);

DBCC PAGE ('demo_db', 1, 1, 3);

Wie die Abbildung zeigt, besitzt die Datenseite 150 einen Füllgrad von 80% während auf Datenseite 163 offensichtlich noch 50% des Datenvolumens zur Verfügung stehen. Ein Blick auf die betroffene Datenseite selbst zeigt neben dem Füllgrad noch ein paar weitere Informationen über das zur Verfügung stehende Datenvolumen.

DBCC TRACEON (3604);

DBCC PAGE ('demo_db', 1, 150, 0);

Die Ausgabe der Seiteninformationen zeigt folgende wichtige Informationen:

Insgesamt befinden sich 2 Datensätze auf der Datenseite (m_SlotCnt) und es stehen noch 3.062 Bytes auf der Datenseite für neue Datensätze zur Verfügung (m_freeCnt). Sollte ein neuer Datensatz eingetragen werden, so kann er bei Offset 5.126 eingetragen werden (m_freeData). Und zu guter Letzt wird der Füllgrad aus der PFS ebenfalls abgebildet; die Datenseite ist gem. Definition mit BIS ZU  80% der möglichen Kapazität mit Daten gefüllt.

Die Informationen aus der Datenseite selbst würden ausreichend sein, um Microsoft SQL Server zu veranlagen, den 3. Datensatz ebenfalls auf dieser Datenseite zu speichern, da er ja nur 2508 Bytes lang ist. Das für den Datensatz eine neue Datenseite erstellt wurde, deutet darauf hin, dass die Informationen über den Füllgrad der Datenseite nicht aus dem Header selbst gelesen werden sondern aus der PFS.

In der PFS ist hinterlegt, dass die Datenseite 150 einen Füllgrad von 80% besitzt. 80% von 8.192 Bytes entspricht 6.554 Bytes. Somit verbleiben noch 20% des möglichen Datenvolumens zur Speicherung von Daten (entspricht 1.638 Bytes). Da der zu speichernde Datensatz weit über die Länge von 1.638 Bytes hinaus geht, wird eine neue Datenseite für den zu speichernden Datensatz in der Datenbank alloziert. Das exakt dieses Verfahren angewendet wird, kann man auch recht gut im Transaktionsprotokoll “nachlesen”.

SELECT  [Current LSN],

        Operation,

        Context,

        AllocUnitId,

        AllocUnitName,

        [Page ID],

        [Slot ID]        

FROM    sys.fn_dblog(NULL, NULL)

WHERE   AllocUnitName = 'dbo.tbl_Heap' OR

        Context = 'LCX_PFS'

ORDER BY

        [Current LSN];

Zunächst wird ein neuer Datensatz in die Tabelle [dbo].[tbl_Heap] in Slot_ID 0 eingetragen (Zeile 7). Unmittelbar nachdem der Datensatz eingetragen wurde, wird die PFS aktualisiert (Zeile 8). Anschließend wird der zweite Datensatz in die Tabelle eingetragen (Zeile 9) dessen Abschluss erneut die Aktualisierung der PFS ist (Zeile 10).

Bevor die 3. Datenzeile eingetragen wird, legt Microsoft SQL Server eine neue Datenseite in der Datenbank an. Die Informationen über die Allokation der Datenseite werden sofort in die PFS und die IAM (Index Allocation Map) geschrieben (Zeile 11 und 12). Nachdem die neue Seite formatiert wurde (Zeile 13), kann der 3. Datensatz auf die Seite 163 in Slot_ID 0 eingetragen werden (Zeile 14). Auch diese Aktion wird erneut mit einer Aktualisierung der PFS beendet.

Zusammenfassung

Heaps verfolgen einen vollständig anderen Ansatz zur Speicherung von Datensätzen. Da ein Heap ungeordnet ist, kann Microsoft SQL Server deutlich effizientere Möglichkeiten für die Speicherung von Datensätzen anwenden. Insbesondere muss Microsoft SQL Server nicht jede Seite explizit inspizieren, um festzustellen, ob auf der Datenseite noch ausreichend Platz vorhanden ist. Ein einfacher “Scan” der PFS-Seite findet deutlich schneller einen freien Platz in der Datenbank. Ich persönlich halte die Skalierung – insbesondere bei langen Datenstrukturen – für zu “grob”, da 3 Bit verwendet werden können, wäre eine deutlich feinere Justierung wünschenswert (7 Abstufungen statt nur 4 Abstufungen)

Wie immer gibt es da, wo es Licht gibt, natürlich auch Schatten – durch das oben beschriebene Verfahren kann es bei langen Datensätzen leicht dazu kommen, dass eine Datenseite nur schlecht gefüllt wird (Density) und somit beim Lesen der Datenseite in den Buffer Pool deutlich mehr RAM ungenutzt verwendet wird, als bei einem CLUSTERED INDEX.

Herzlichen Dank fürs Lesen!