Home » Blog » The Index Allocation Map (IAM)

The Index Allocation Map (IAM)

2014-04-02 - General, Series, SQL Server Internals, Storage Wednesday

Introduction

Last Storage Wednesday we talked about allocation units. An allocation unit is basically a container for pages that make up (a partition of) an index. In this article I am going to look at, how SQL Server keeps track of the pages that belong to an allocation unit.

The Index Allocation Map

To catalog all the pages that belong to a single allocation unit, SQL Server utilizes a special type of pages, the Index Allocation Map or IAM pages. Each allocation unit has at least one IAM Page; depending on the size of the table there might be many. The page type of an IAM page is 10.

Like every other page, an IAM page has a 96-byte header. The page header is followed by a special index allocation map header. That header contains a base page address. It points to the first page that this allocation map covers. For small databases this is usually page 1:0, the first page in the first database file. The IAM header also contains eight slots for mixed extent page allocations. Remember, the first eight pages of a table, as the table is growing, are taken from mixed extents. Each slot is 6 bytes in size and points to one of those mixed extent pages. If an allocation unit has more than one IAM page, only the first one will ever have values in those slots. There are a few other values in the IAM header, but they are not well documented and mostly unused, so I am not going to go into more detail.

Following the IAM header is an 8000-byte bit-map. Each bit is linked to one extent in the file, indicating with a value of 1 that that extend is allocated to this allocation unit. The first bit of this bit-map covers the extent containing the page pointed to by the first page pointer in the IAM header. The next bit covers the directly following extent. With 8000 bytes or 64000 bits, this bit-map covers about four GB worth of extents in the file (4194304000 bytes). Each 64000 extent section of a database file is called a GAM-interval. Note that an IAM page does not need to be located in the same GAM-interval that it is covering. In fact, it does not even have to be in the same database file.

If an allocation unit has pages in more than one GAM-interval, it has to have more than one IAM page as well. In that case, the IAM pages are linked through the previous and next page pointers in their headers. The linked list of index allocation maps that belong to one allocation unit is called an IAM Chain.

Example IAM Page

To show you an example, I created a table dbo.tst that contains exactly 16 data pages. DBCC IND returns 17 rows, one for the index allocation map itself and the remaining ones for the 16 data pages:

The first eight pages are non-contiguous. They are mixed extent pages. The remaining eight pages are from a single uniform extent. The table has only a single index and a single partition and does not require any of the LOB stores, so there is only a single allocation unit. The IAM page for this allocation unit looks like this:

The complete DBCC PAGE output is below:

[sourcecode]

PAGE: (1:308)

BUFFER:

BUF @0x0000000004D89B40

bpage = 0x00000001F28DE000 bhash = 0x0000000000000000 bpageno = (1:308)
bdbid = 16 breferences = 0 bcputicks = 0
bsampleCount = 0 bUse1 = 9651 bstat = 0x10b
blog = 0x5acccccc bnext = 0x0000000000000000

PAGE HEADER:

Page @0x00000001F28DE000

m_pageId = (1:308) m_headerVersion = 1 m_type = 10
m_typeFlagBits = 0x0 m_level = 0 m_flagBits = 0x0
m_objId (AllocUnitId.idObj) = 248 m_indexId (AllocUnitId.idInd) = 256
Metadata: AllocUnitId = 72057594054180864
Metadata: PartitionId = 72057594040614912 Metadata: IndexId = 1
Metadata: ObjectId = 987150562 m_prevPage = (0:0) m_nextPage = (0:0)
pminlen = 90 m_slotCnt = 2 m_freeCnt = 6
m_freeData = 8182 m_reservedCnt = 0 m_lsn = (110:421:72)
m_xactReserved = 0 m_xdesId = (0:0) m_ghostRecCnt = 0
m_tornBits = 0 DB Frag ID = 1

Allocation Status

GAM (1:2) = ALLOCATED SGAM (1:3) = NOT ALLOCATED
PFS (1:1) = 0x70 IAM_PG MIXED_EXT ALLOCATED 0_PCT_FULL DIFF (1:6) = CHANGED
ML (1:7) = NOT MIN_LOGGED

IAM: Header @0x00000000726DA064 Slot 0, Offset 96

sequenceNumber = 0 status = 0x0 objectId = 0
indexId = 0 page_count = 0 start_pg = (1:0)

IAM: Single Page Allocations @0x00000000726DA08E

Slot 0 = (1:307) Slot 1 = (1:309) Slot 2 = (1:310)
Slot 3 = (1:311) Slot 4 = (1:282) Slot 5 = (1:283)
Slot 6 = (1:284) Slot 7 = (1:285)

IAM: Extent Alloc Status Slot 1 @0x00000000726DA0C2

(1:0) - (1:576) = NOT ALLOCATED
(1:584) - = ALLOCATED
(1:592) - (1:1024) = NOT ALLOCATED

DBCC execution completed. If DBCC printed error messages, contact your system administrator.
[/sourcecode]

The output shows the eight slots for mixed extent allocation in the Single Page Allocations section. The output of the following allocation bit-map is translated into ranges. The ranges from page 0 to page 583 and page 592 to the end of the file are not allocated to this allocation unit. The eight pages of the extent that starts at page 584 are allocated. That means in the 64000 bit bit-map there is only a single bit set.

Summary

SQL Server uses index allocation maps to track which pages have been allocated to which allocation unit. They are stored in special IAM pages. Each IAM page covers an area of 64000 extents in a file, a so-called GAM-interval. If multiple IAM pages are needed for a single allocation unit, the form a double linked list, the IAM chain.