Allocation maps - from top to bottom

Chronicles of SQL Server's Storage Internals - Part 7

I mentioned them in previous SQL-related article, but they deserve a bit more attention.

Namely, we agreed that Allocation Maps are an accounting technique that allows SQL Server to know which data is stored where. Because, if you think about it, having a huge binary file full of zeros and ones without some kind of map makes it ... well, just a bunch of zeros and ones, right? You need a dictionary; or, you know, a map! 🗺

We talked about THREE important types of allocation maps and then briefly mentioned IAM. This one will shine a bit more light on IAM and then in the following articles you will get to see why and how it's used.

You can think of allocation maps in hierarchical terms.

On the top would be the map of the world. Highly abstract but gives you a clue what can be found where. As in - where's the land, where's the sea, where actually America is, etc. That's 𝑮𝒍𝒐𝒃𝒂𝒍 𝑨𝒍𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 𝑴𝒂𝒑 (GAM).

GAM tells you where the land is (occupied extents) and where the sea is (free floating space). And that's it. Since it stores really brief info (land or sea) it can store tons of data (e.g. 1 means it's a land, 0 means it's a sea).

If we go one level deeper, we have 𝑺𝒉𝒂𝒓𝒆𝒅 𝑮𝒍𝒐𝒃𝒂𝒍 𝑨𝒍𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 𝑴𝒂𝒑 (SGAM) and 𝑷𝒂𝒈𝒆 𝑭𝒓𝒆𝒆 𝑺𝒑𝒂𝒄𝒆 (PFS). You can think of them as a Map of a single Country. They are a bit more detailed, and they give you an overview of how the land is filled, but still they won't help you find Dunkin Donuts or Starbucks (you'll need IAM for that).

SGAM tracks which Extents are Uniform and which are Mixed ones. As a reminder - 𝑼𝒏𝒊𝒇𝒐𝒓𝒎 𝑬𝒙𝒕𝒆𝒏𝒕𝒔 are extents that contain 8 pages of SINGLE ENTITY DATA (e.g. data from single table), whereas 𝑴𝒊𝒙𝒆𝒅 𝑬𝒙𝒕𝒆𝒏𝒕𝒔 are the exact opposite.

PFS is more like a topological map. It shows you where the highs and lows are. As in - where's the mountain and where's the valley. Except that they track how Space is allocated - as in how filled-up each page is, as in - where the flat (empty) ones are and where are the hills (i.e. almost filled up pages).

Finally, we get to the city map. The most detailed ones that shows you where the coffee shops and markets are, where you can find parties and where libraries (anyone still looking for those, or?). That's what 𝑰𝒏𝒅𝒆𝒙 𝑨𝒍𝒍𝒐𝒄𝒂𝒕𝒊𝒐𝒏 𝑴𝒂𝒑𝒔 (IAM) are.

They exist for EACH table (as in - each table gets it's own set of IAM pages) and they track which Extents contain which data from the table (e.g. where the IN_ROW and OVERFLOW_DATA is). Since we haven't discussed the types of Data yet, that's something for the next article, but for now, do remember that IAM is your most detailed map that.

And that's it. It really IS simple :)