SQL Server Storage Engine

Fragmentation (part 3): What are extents?

(Ok - another flight - another blog post. This time its Boston back to Seattle. The three of us who'd come over for the training course upgraded to 1st Class on Alaska for the flight back (great value at $100 for a 6-hour flight) and so there's oodles of room for laptops, newspapers, and long legs)

In the previous posts I explained about database pages - their structure and some page types. Now I'd like to explain how we group pages into units called extents.

An extent is a group of eight physically consecutive pages in a database data file. Extents are always aligned on 64KB boundaries (i.e. 8-page boundaries), starting at the beginning of each data file. Extents, and all their properties, are exactly the same in SQL Server 2000 and 2005.

There are two types of extents: mixed extents and dedicated (or uniform) extents.

Mixed extents

The first 8 pages that are allocated to any IAM chain (either for an index in SQL Server 2000 or allocation unit in SQL Server 2005) are single-page allocations, which we called mixed pages. This means that only a single page is allocated to the IAM chain at a time, rather than a whole extent. The rationale behind this is to allow very small tables to take up the minimum amount of space.

These mixed pages are allocated from mixed extents that are not allocated to any particular IAM chain. The extent is tracked as being allocated globally, so no IAM chain can allocate it.

As the mixed extent is not allocated to any particular IAM chain, this means that it may hold pages allocated to 8 separate IAM chains. IAM pages themselves are always mixed pages, regardless of how many pages have been allocated to an IAM chain. This means a mixed extent may hold a variety of page types too,including IAM, data, index, or text pages.

Two interesting facts:

  • once an IAM chain has passed the 8-page threshold and switched to allocating dedicated extents, it will never go back to allocating mixed pages again.
  • for the purposes of fragmentation, we completely ignore mixed pages and extents as there are so few of them in each IAM chain and it complicates the various algorithms involved.

Dedicated/Uniform extents

Once the magic 8-page threshold is passed, all further allocations are from dedicated extents. This means that an extent at a time is allocated to an IAM chain (and marked as such in one of the IAM pages in the IAM chain). This is also tracked globally.

All pages from a dedicated extent must be allocated to the same IAM chain, and they will all be the same type except in the case of clustered indexes, where there could be a mixture of data pages (from the leaf level) and index pages (from the upper b-tree levels).

Two more interesting facts:

  • just because an extent is allocated to an IAM chain, that doesn't mean that all the pages are. The pages are allocated as needed, so initially only one page will be allocated. There are some exceptions to this rule, including during an offline index build operation, but I'm not going to go into the algorithm details.
  • dedicated extents can be deallocated from an IAM chain if all the pages in the extent become deallocated.

You may ask "how do you know which pages are allocated in an extent?" and "how do you track the global allocation state of extents, especially mixed extents?". The answers are by using the PFS pages, and by using the GAM + SGAM pages respectively. I'll cover these in the next post.

(Passing over Montana now at 8pm - pretty clear skies and the sun's at an angle to throw the landscape into sharp relief - very cool. First class is great - actual crockery rather than plastic plates, cups and food...)


Published Wednesday, June 28, 2006 6:52 PM by Paul Randal - MSFT

Comments

 

rhunt said:

Paul, I'm not sure where this will fit in, but I was wondering if you could discuss the mixture of page types for clustered Index/tables on extents.  I've heard before that leaf and intermediate level pages for clustered indexes often coexist on the same extents - this makes single row or small group lookups very fast because the leaf level pages are often on the same extent already paged-in to perform the CI seek.

However, it seems to be that this would have a negative impact on range queries.  One of the benefits of ranges on CI's is that SQL is supposed to be able to traverse the intermediate index pages until locating the first occurrence of "true" based on the selection predicate, and then jump down to the leaf level to finish off selection (until leaf level keys result in selection predicate = false).  At least this is what I think it does...

With intermediate and leaf pages on the same extents, it seems that the I/O load would be increased when intending to scan only the leaf level (I/O wise - wouldn't you also be scanning the intermediate level of the index as well??).

Thanks. Ryan
July 3, 2006 10:29 AM
 

Paul Randal - MSFT said:

Hi Ryan,

I'm going to cover all of this in later posts but here are some simplified snippets to (hopefully) satisfy you in the meantime:
- yes, index and data pages can coexist, but as the fanout size increases, the odds of hitting such an extent decreases.
- What you've heard is incorrect though. The whole extent is not read into memory when a single page is read, unless the read is being driven by range-scan readahead. Also, the upper levels of a well-used index with a decent fanout are typically memory resident and so do not incur IO costs - the IO cost comes from reading the leaf-level page.
- having interleaved index and data pages in extents will impact the ability of the readahead code to generate multi-page contiguous IOs, but again, that's a negligible cause compared to page fragmentation
- readahead is driven from the level above the leaf level - I'm not going to explain it all now

Hope this helps in the short-term.
July 7, 2006 6:01 PM
 

jccondor said:

Paul, could you touch the physical and logical structure of clustered indexes and how there navigated.

My main concern is that (from what I knew or thought I knew SQL 2000) Indexes had the following structure: multi-column indexes the first only the first column was used to construct the tree-nodes. Leafs had the remaining columns. (BOL for 2005 now state differently we now have INCLUDE for adding columns to the leaf nodes and tree nodes contain all columns). I imagine though that the order is still important when navigating them ! ?

My doubt has all ways been the following regarding clustered indexes. ( suppose a table with a US-STATE column (non-unique), id (primary key) filed ) now it's clear that sql server will order data by us-state and within each state by id.

Select * from table where us-state='MA' is efficient because of the clustered index having us-state first.

select * from table where id=@id: will probably require looking at primary key index then fetching us-state and then looking at the clustered index by state,id. HOW IS THIS ACHIVED (how can SQL make this efficient, is it doing a partial region scan on us-state and looking for the id?)

B/W grate articles.
July 11, 2006 12:42 PM
 

Paul Randal - MSFT said:

Hi jccondor,

Apologies for the delay in replying - I missed this comment when it was posted.

I'll go into detail on clustered indexes in a later post but I'll address some of your concerns here:
- multi column indexes have all index key columns in the tree-nodes, otherwise building a b-tree would be impossible.
- INCLUDEd columns are not index keys and so do not have to be in the tree nodes
- in the example you give, the 'id' column will come first in the clustered index because its the primary key, unless you specify non-clustered. You'll need to post the actual index schema you're working with.

Thanks
July 28, 2006 7:40 PM
 

SSQA- Users & SQL tools said:

On day-to-day basis a DBA might come across with the issues on the fragmentation on the database, it

April 23, 2007 5:42 AM
 

SQL Server Storage Engine Fragmentation part 3 What are extents | Uniform Stores said:

PingBack from http://uniformstores.info/story.php?id=19080

June 1, 2009 4:31 PM
 

SQL Server Storage Engine Fragmentation part 3 What are extents | Toe Nail Fungus said:

PingBack from http://toenailfungusite.info/story.php?id=4805

June 9, 2009 2:11 AM
 

SQL Server Storage Engine Fragmentation part 3 What are extents | storage bench said:

PingBack from http://thestoragebench.info/story.php?id=4137

June 19, 2009 4:06 AM
Anonymous comments are disabled

About Paul Randal - MSFT

Paul started in the industry in 1994 working for DEC on the VMS file system and check/repair tools. In 1999 he moved to Microsoft to work on SQL Server, specifically on DBCC. For SQL Server 2000, he concentrated on index fragmentation (writing DBCC INDEXDEFRAG and DBCC SHOWCONTIG) plus various algorithms in DBCC CHECKDB. During SQL Server 2005 development Paul was the lead developer/manager of one the core dev teams in the Storage Engine, responsible for data access and storage (DBCC, allocation, indexes & heaps, pages/records, text/LOB storage, snapshot isolation, etc). He also spent several years rewriting DBCC CHECKDB and repair. For SQL Server 2008, Paul managed the Program Management team for the core Storage Engine to become more focused on customer/partner engagement and feature set definition. In 2007, after 8.5 years on the SQL Server team, Paul left Microsoft to join his wife, Kimberly Tripp, running SQLskills.com and pursuing his passion for presenting and consulting. Paul regularly presents at conferences and user groups around the world on high-availability, disaster recovery and Storage Engine internals. His popular blog is at http://www.sqlskills.com/blogs/paul/.

This Blog

Syndication

© 2009 Microsoft Corporation. All rights reserved. Terms of Use  |  Trademarks  |  Privacy Statement
Microsoft
Page view tracker