Share via

Fragmentation (part 3): What are extents?

  • Article

(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...)

Comments

  • Anonymous
    July 03, 2006
    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

  • Anonymous
    July 07, 2006
    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.

  • Anonymous
    July 11, 2006
    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.

  • Anonymous
    July 28, 2006
    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

  • Anonymous
    April 22, 2007
    On day-to-day basis a DBA might come across with the issues on the fragmentation on the database, it

  • Anonymous
    June 01, 2009
    PingBack from http://uniformstores.info/story.php?id=19080

  • Anonymous
    June 08, 2009
    PingBack from http://toenailfungusite.info/story.php?id=4805

  • Anonymous
    June 18, 2009
    PingBack from http://thestoragebench.info/story.php?id=4137