Managing Extent Allocations and Free Space
The Microsoft® SQL Server™ 2000 data structures that track free space have a relatively simple structure. This has two benefits:
- The free space information is densely packed, so there are relatively few pages containing this information.
This increases speed by reducing the amount of disk reads necessary to retrieve allocation information, and increasing the chance the allocation pages will remain in memory, eliminating even more reads.
- Most of the allocation information is not chained together, which simplifies the maintenance of the allocation information.
Each page allocation or deallocation can be performed quickly, decreasing the contention between concurrent tasks needing to allocate or free pages.
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 nearly 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 what extents are currently used as mixed extents and have at least one unused page. Each SGAM covers 64,000 extents, or nearly 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 free pages; if the bit is 0, the extent is not used as a mixed extent, or it is a mixed extent whose pages are all in use.
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 in use | 1 | 0 |
| Uniform extent, or full mixed extent | 0 | 0 |
| Mixed extent with free pages | 0 | 1 |
This results in simple extent management algorithms. To allocate a uniform extent, SQL Server searches the GAM for a 1 bit and sets it to 0. To find a mixed extent with free pages, SQL Server searches the SGAM for a 1 bit. To allocate a mixed extent, SQL Server searches the GAM for a 1 bit, sets it to 0, and then also sets the corresponding bit in the SGAM to 1. To free an extent, SQL Server ensures the GAM bit is set to 1 and the SGAM bit is set to 0. The algorithms actually used internally by SQL Server are more sophisticated than what is stated here (SQL Server distributes data evenly in a database), but even the real algorithms are simplified by not having to manage chains of extent allocation information.
Page Free Space (PFS) pages record whether an individual page in a heap or an ntext, text, or image column has been allocated, and the amount of space free on each page. Each PFS page covers approximately 8,000 pages. For each page, the PFS has a bitmap recording whether the page is empty, 1-50% full, 51-80% full, 81-95% full, or 96-100% full.
After an extent has been allocated to an object, SQL Server uses the PFS pages to record which pages in the extent are allocated or free, and how much free space is available for use. This information is used when SQL Server has to allocate a new page, or when it needs to find a page with free space available to hold a newly inserted row.
A PFS page is the first page after the file header page in a data file (with page number 1). Next comes a GAM (with page number 2) followed by an SGAM (page 3). There is a PFS page approximately 8,000 pages after the first. There is another GAM each 64,000 extents after the first GAM on page 2, and another SGAM each 64,000 extents after the first SGAM on page 3.
