Fragmentation (part 2): What are pages?

[SQL-Server-Team]

First published on MSDN on Jun 25, 2006

(Boston continues its reputation - with me at least - for great seafood - calamari and pan-seared fresh halibut this evening. Yum! I was tempted to get on the T - Boston's subway system - and see what's happening downtown but with no jacket I'd get wet. So, instead I'll be boring and geeky and write another blog post - you guys are spoiled today.)

Hopefully I'm getting close to resolving the chicken-and-egg problem of being able to discuss topics without having to promise further posts to explain terms.

In the previous post in this series I explained what records are. Pages exist to store records. A database page is an 8192-byte (8KB) chunk of a database data file. They are aligned on 8KB boundaries within the data files, starting at byte-offset 0 in the file.

A page has a structure as shown below (all pages have the same basic structure):

Page header

The 96-byte page header is the same for every page. You can see an example of the fields that are stored within a page header in the last post on DBCC PAGE . When considering fragmentation, the most important fields are:

• Next page pointer
  
  
  
  • The pages in each level of the index are joined in a doubly-linked list according to the logical order (as defined by the index keys) of the index. The next page pointer does not necessarily point to the immediately adjacent physical page in the file (fragmentation...
    
  • As these are doubly-linked lists, there is also a previous page pointer.
  
  
• Page level
  
  
  
  • The various algorithms I'll describe later have to know whether the page being examined is from the leaf-level of the index or not (i.e. page level = 0). Page level increases from the leaf-level to the root page at the top of the b-tree (except in clustered indexes in SQL Server 2000 where there are two level=0 levels - the leaf-level and the level above it - this is just for simplicity :) How do you tell them apart? You need to look at the page type too - data pages are at the leaf-level, index pages in the level above)
  
  
• Free space count
  
  
  
  • This shows how much free space is available in the page. This is used to calculate the average page density - the less free space, the higher the page density.

Other interesting fields in the page header are:

• object ID and index ID
  
  
  
  • in SQL Server 2000, these correspond to the actual relationl object ID and index ID to which the page is allocated.
    
  • in SQL Server 2005, this mapping no longer exists. The two IDs on each page correspond (through a calculation) to the allocation unit ID of the allocation unit the page is allocated to. A series of metadata lookups are necessary to determine the parent object and index.
  
  
• page type
  
  
  
  • There are a bunch of different page types, most of which I'll be explaining more about in subsequent posts over the next few weeks. Some interesting ones are (well, interesting to me anyway):
    
    
    
    • data page (holds data records)
      
    • index page (holds non-clustered index leaf records and non-leaf records from clustered and non-clustered indexes)
      
    • IAM page (holds allocation information about extents within a fixed 4GB GAM interval that are allocated to an index or allocation unit, in SQL Server 2000 and 2005 respectively. IAM = Index Allocation Map.)
      
    • GAM and SGAM pages (holds global allocation information about extents in a GAM interval. GAM = Global Allocation Map. SGAM = Shared GAM.)
      
    • PFS page (holds allocation and free space information about pages within a PFS interval - approx 64MB. PFS = Page Free Space.)
      
    • text page (actually two types that hold leaf and intermediates nodes in text trees)
      
    • sort page (holds sort records being used in active sort operations)
      
    • differential bitmap page (holds information about which extents in a GAM interval have changed since the last full or differential backup)
      
    • bulk-changed map page (holds information about which extents in a GAM interval have changed while in bulklogged mode since the last backup. This is what allows you to switch to bulk-logged mode for bulk-loads and index rebuilds without worrying about breaking a backup chain.)
      
    • boot page (holds information about the database - one page used per database)
      
    • fileheader page (holds information about the file - one page per file)
  
  
• slot count
  
  
  
  • This lists the number of occupied record slots on the page (including ghost records).
    
  • It can also be described as giving the number of entries in the slot array.
  
  
• ghost record count
  
  
  
  • self-explanatory
  
  
• page ID
  
  
  
  • a page's ID is made up of the file ID and the page position within the file and is always written as (file:page)

Slot array

It is a very common misconception that records within a page are always stored in logical order. This is not true. There is another misconception that all the free-space in a page is always maintained in one contiguous chunk. This also is not true. (Yes, the image above shows the free space in one chunk and that very often is the case for pages that are being filled gradually.)

If a record is deleted from a page, everything remaining on the page is not suddenly compacted - inserters pay the cost of compaction when its necessary, not deleters.

Consider a completely full page - this means that record deletions cause free space holes within the page. If a new record needs to be inserted onto the page, and one of the holes is big enough to squeeze the record into, why go to the bother of comapcting it? Just stick the record in and carry on.

Ah - but hold on a minute, what if the record should logically have come at the end of all other records on the page, but we've just inserted it in the middle - doesn't that screw things up somewhat?

No, because the slot array is ordered and get reshuffled as records are inserted and deleted from pages. As long as the first slot array entry points to the logically first record on the page, everythings fine. Each slot entry is just a two-byte pointer into the page - so its far more efficient to manipulate the slot array than it is to manipulate a bunch of records on the page. Only when we know there's enough free space contained within the page to fit in a record, but its spread about the page do we compact the records on the page to make the free space into a contiguous chunk.

One interesting fact is that the slot array grows backwards from the end of the page, so the free space is squeezed from the top by new rows, and from the bottom by the slot array.

Records

You know what these are already - we talked about them last time!

IO

Pages are the basic unit of IO that SQL server uses. The buffer pool maps individual pages and torn-page protection and page checksums are implemented per-page. Fragmentation is mostly concerned with pages, and the efficiency of being able to read them in logical order (as defined by their next page pointers).

They can be allocated individually or in extents, which we'll cover next time...