Managing Extent Allocations and Free Space
The SQL Server data structures that manage extent allocations and track free space have a relatively simple structure. This has the following benefits:
The free space information is densely packed, so relatively few pages contain this information.
This increases speed by reducing the amount of disk reads that are required to retrieve allocation information. This also increases the chance that the allocation pages will remain in memory and not require more reads.
Most of the allocation information is not chained together. This simplifies the maintenance of the allocation information.
Each page allocation or deallocation can be performed quickly. This decreases the contention between concurrent tasks having to allocate or deallocate pages.
Managing Extent Allocations
SQL Server uses two types of allocation maps to record the allocation of extents:
Global Allocation Map (GAM)
GAM pages record what extents have been allocated. Each GAM covers 64,000 extents, or almost 4 GB of data. The GAM has one bit for each extent in the interval it covers. If the bit is 1, the extent is free; if the bit is 0, the extent is allocated.
Shared Global Allocation Map (SGAM)
SGAM pages record which extents are currently being used as mixed extents and also have at least one unused page. Each SGAM covers 64,000 extents, or almost 4 GB of data. The SGAM has one bit for each extent in the interval it covers. If the bit is 1, the extent is being used as a mixed extent and has a free page. If the bit is 0, the extent is not used as a mixed extent, or it is a mixed extent and all its pages are being used.
Each extent has the following bit patterns set in the GAM and SGAM, based on its current use.
Current use of extent |
GAM bit setting |
SGAM bit setting |
|---|---|---|
Free, not being used |
1 |
0 |
Uniform extent, or full mixed extent |
0 |
0 |
Mixed extent with free pages |
0 |
1 |
This causes simple extent management algorithms. To allocate a uniform extent, the Database Engine searches the GAM for a 1 bit and sets it to 0. To find a mixed extent with free pages, the Database Engine searches the SGAM for a 1 bit. To allocate a mixed extent, the Database Engine searches the GAM for a 1 bit, sets it to 0, and then also sets the corresponding bit in the SGAM to 1. To deallocate an extent, the Database Engine makes sure that the GAM bit is set to 1 and the SGAM bit is set to 0. The algorithms that are actually used internally by the Database Engine are more sophisticated than what is described in this topic, because the Database Engine distributes data evenly in a database. However, even the real algorithms are simplified by not having to manage chains of extent allocation information.
Tracking Free Space
Page Free Space (PFS) pages record the allocation status of each page, whether an individual page has been allocated, and the amount of free space on each page. The PFS has one byte for each page, recording whether the page is allocated, and if so, whether it is empty, 1 to 50 percent full, 51 to 80 percent full, 81 to 95 percent full, or 96 to 100 percent full.
After an extent has been allocated to an object, the Database Engine uses the PFS pages to record which pages in the extent are allocated or free. This information is used when the Database Engine has to allocate a new page. The amount of free space in a page is only maintained for heap and Text/Image pages. It is used when the Database Engine has to find a page with free space available to hold a newly inserted row. Indexes do not require that the page free space be tracked, because the point at which to insert a new row is set by the index key values.
A PFS page is the first page after the file header page in a data file (page number 1). This is followed by a GAM page (page number 2), and then an SGAM page (page 3). There is a PFS page approximately 8,000 pages in size after the first PFS page. There is another GAM page 64,000 extents after the first GAM page on page 2, and another SGAM page 64,000 extents after the first SGAM page on page 3. The following illustration shows the sequence of pages used by the Database Engine to allocate and manage extents.
.gif "Pages used to allocate and manage extents")