Freitag, 11. Oktober 2013

Neue Daten in einen HEAP eintragen – immer auf der letzten Datenseite?

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: IF OBJECT_ID('dbo.tbl_heap', 'U') IS NOT NULL
   2:     DROP TABLE dbo.tbl_heap;
   3:     GO
   4:  
   5: CREATE TABLE dbo.tbl_heap
   6: (
   7:     KeyId        uniqueidentifier    NOT NULL    DEFAULT (newid()),
   8:     col1        char(200)            NOT NULL,
   9:     col2        varchar(200)        NOT NULL,
  10:     col3        datetime            NOT NULL    DEFAULT (getdate()),
  11:     InsertPos    int                    NOT NULL    Identity (1, 1)
  12: );
  13: GO

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;


RECORDSET_01


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: SELECT sys.fn_PhysLocFormatter(%%physloc%%) AS Location, * FROM dbo.tbl_heap;

RECORDSET_02
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, 1);

DBCC_PAGE_01


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);


DBCC_PAGE_02
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: SELECT sys.fn_PhysLocFormatter(%%physloc%%) AS Location, * FROM dbo.tbl_heap ORDER BY InsertPos DESC;

RECORDSET_03


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.

DBCC_PAGE_03


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;

RECORDSET_04


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:

DBCC_PAGE_04


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.
FN_DBLOG_01


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











Bit


Beschreibung


0 - 2


   0x00: Datenseite ist leer
   0x01: Datenseite ist <= 50% gefüllt
   0x02: Datenseite ist zwischen 51% und 80% gefüllt
   0x03: Datenseite ist bis zu 95% gefüllt
   0x04: Datenseite ist >=96% gefüllt


Definition des zur Verfügung stehenden Speichers auf der Datenseite


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);

DBCC_PAGE_05


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


DBCC_PAGE_06


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!













HEAPShttp://technet.microsoft.com/de-de/library/ms188270(v=sql.105).aspx
PFShttp://technet.microsoft.com/de-de/library/ms175195(v=sql.105).aspx
 http://blogs.msdn.com/b/sqlserverstorageengine/archive/2006/07/08/under-the-covers-gam-sgam-and-pfs-pages.aspx

Kommentare :

  1. Hi Uwe!

    "Für JEDE in einer Datenbank verwendete Datenseite wird der Füllgrad in der PFS gespeichert"
    Das trifft nicht für eine Clustered Table zu.
    Da SQL Server IMMER den Datensatz in der Sortierreihenfolge des Index Keys in die PAGE einfügen muss, ist die PFS Information unwichtig und wird daher aus Performancegründen nicht in die PFS Seite geschrieben.
    Zudem bringen die PFS Füllgradestufen das Problem mit sich:
    Ich habe mal ein Script erstellt das dieses Problem verdeutlicht:

    AntwortenLöschen
    Antworten
    1. Hallo Torsten,

      "Das trifft nicht für eine Clustered Table zu."
      Habe ich doch geschrieben :). GILT NUR FÜR HEAPS.
      Das Problem mit den Füllgraden bei HEAPS habe ich hier bereits sehr ausführlich behandelt...

      http://db-berater.blogspot.de/2013/12/wie-alloziert-microsoft-sql-server.html

      Löschen
    2. Sorry, ich sollte dann genauer lesen!
      Ich entferne mein Script da Du ja schon ein Beispiel hast ;-)
      Danke für Deine Antwort!

      Löschen