Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase «««23456»»

Clustered indexes Expand / Collapse
Author
Message
Posted Friday, May 7, 2010 2:03 AM
SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Today @ 12:40 AM
Points: 2,046, Visits: 370
thanks for this wonderful question
Post #917697
Posted Friday, May 7, 2010 3:22 AM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Friday, September 26, 2014 3:23 PM
Points: 2,116, Visits: 6,439
Paul White NZ (5/6/2010)
On the physical ordering thing, I would just add that individual rows on the page may not be in physical clustered index either - only the page offset array entries are guaranteed to be in logical and physical order.


Paul, could you elaborate a bit more on this? BTW, thanks for the great articles on APPLY and Server-Side Paging.

Hugo, thanks for a great question, learned something new again.


--------------------------------------------------------------------------
A little knowledge is a dangerous thing (Alexander Pope)

In order for us to help you as efficiently as possible, please read this before posting (courtesy of Jeff Moden)
Post #917736
Posted Friday, May 7, 2010 4:03 AM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Today @ 2:33 AM
Points: 6,020, Visits: 8,289
Jan Van der Eecken (5/7/2010)
Paul White NZ (5/6/2010)
On the physical ordering thing, I would just add that individual rows on the page may not be in physical clustered index either - only the page offset array entries are guaranteed to be in logical and physical order.


Paul, could you elaborate a bit more on this? BTW, thanks for the great articles on APPLY and Server-Side Paging.

Hugo, thanks for a great question, learned something new again.

You're welcome!

I'm not Paul, but I can elaborate as well. Suppose that a table has 500-byte rows, and a page is filled with 5 of them, that have been added in sequence of the clustered index key. Examining the page with DBCC PAGE will probably reveal a structure like this (for simplicity, I leave out the various page header fields and start counting bytes at the start of the actual row data).
Bytes 1 - 500: Row #1
Bytes 501 - 1000: Row #2
Bytes 1001 - 1500: Row #3
Bytes 1501 - 2000: Row #4
Bytes 2001 - 2500: Row #5
Bytes 2501 - 8000: unused
Last ten bytes of page: five 2-byte values representing the decimal values 2001, 1501, 1001, 501, 1.

These last 10 bytes are the "Row Offset Array". Reading from last to first, they tell SQL Server the start position of the first, second, third, fourth, and fifth row on the page.

Now I add a new row that, according to clustered index order, sits between #2 and #3 (let's call the now one Row #2.5). Instead of moving 1500 bytes to a different location on the page, SQL Server simply adds the new row in the unused space and moves only the 2-byte locators in the Row Offset Array. The new page layout will be:
Bytes 1 - 500: Row #1
Bytes 501 - 1000: Row #2
Bytes 1001 - 1500: Row #3
Bytes 1501 - 2000: Row #4
Bytes 2001 - 2500: Row #5
Bytes 2501 - 5000: Row #2.5
Bytes 3001 - 8000: unused
Last twelve bytes of page: six 2-byte values representing the decimal values 2001, 1501, 1001, 2501, 501, 1.

Reading the Row Offset Array backwards and locating the row, you get this order:
From position 1: Row #1
From position 501: Row #2
From position 2501: Row #2.5
From position 1001: Row #3
From position 1501: Row #4
From position 2001: Row #5

So the physical order of the Row Offset Array matches the logical order imposed by the clustered index; the physical order of rows in the page does not.

I hope this clarifies your question.

(And Paul - thanks for bringing up this excellent point).



Hugo Kornelis, SQL Server MVP
Visit my SQL Server blog: http://sqlblog.com/blogs/hugo_kornelis
Post #917760
Posted Friday, May 7, 2010 4:31 AM


SSCrazy Eights

SSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy Eights

Group: General Forum Members
Last Login: 2 days ago @ 10:07 PM
Points: 9,926, Visits: 11,183
Jan Van der Eecken (5/7/2010)
Paul, could you elaborate a bit more on this? BTW, thanks for the great articles on APPLY and Server-Side Paging.

Gosh thanks Jan! Haven't seen you around for a while, so good to see you again.

@Hugo: Thank you for elaborating so clearly - saved me quite a lot of typing - win!!!




Paul White
SQL Server MVP
SQLblog.com
@SQL_Kiwi
Post #917778
Posted Friday, May 7, 2010 4:48 AM


SSCrazy

SSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazySSCrazy

Group: General Forum Members
Last Login: Friday, September 26, 2014 3:23 PM
Points: 2,116, Visits: 6,439
Thanks, Hugo, nicely explained.

Paul, I haven't been away, just been sitting quietly on the sidelines observing and learning.


--------------------------------------------------------------------------
A little knowledge is a dangerous thing (Alexander Pope)

In order for us to help you as efficiently as possible, please read this before posting (courtesy of Jeff Moden)
Post #917790
Posted Friday, May 7, 2010 4:49 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Sunday, August 3, 2014 3:41 PM
Points: 1,219, Visits: 1,430
@Hugo

Thanks for that - I managed to follow your explanation - and I'm relieved to find out it has nothing to do with disk fragmentation (which was all I could think of for the physical difference)
Post #917791
Posted Friday, May 7, 2010 7:12 AM


Ten Centuries

Ten CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen CenturiesTen Centuries

Group: General Forum Members
Last Login: Tuesday, September 16, 2014 2:03 PM
Points: 1,334, Visits: 3,069
Good question Hugo! I like these kind of questions that really make us think about our conceptions/misconceptions of how things work in SQL Server due to things we have read straight from BOL. This is an excellent example of that. As you seem to point out, we have to be very careful about taking every thing we read in BOL literally. Even Mickeysoft can mislead us about their own product.

"Technology is a weird thing. It brings you great gifts with one hand, and it stabs you in the back with the other. ..."
Post #917922
Posted Friday, May 7, 2010 9:05 AM
SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Thursday, March 31, 2011 1:40 AM
Points: 1,938, Visits: 208
I believe this explanation is incorrect for the way the question was asked. Your question asked if the rows were physically or logically ordered, not if the pages were physically or logically ordered. All the rows are indeed physically ordered on their pages based on the clustered index.

I answered the question correctly based on your explanation, and other research, because it is a GOOD question, I'm just putting in my 2 cents.

Hugo Kornelis (5/6/2010)
satya11001-1013569 (5/5/2010)
I have a doubt regarding the logical order of rows for Clustered Index.
Main difference between Clustered and Non-Clustered is Clustered is physical arrangement of rows and Non-Clustered is logical arranging of rows .

Hi Satya,

This is not correct. Clustered and non-clustered indexes are built very similar. The only difference is the actual contents of the leaf pages.
For a clustered index, root and intermediate pages contain the index key and a pointer to the lower-level page; leaf pages contain the all the columns (except LOB data, such as varchar(max) or xml).
For a nonclustered index, root and intermediate pages contain the index key and a pointer to the lower-level page; leaf pages contain the index key and a pointer to the data page where the complete row can be found. This pointer is either the clustered index key, or (if the table does not have a clustered index) the RID.

Can you explain a bit more on the arrangement of actual data rows for Clustered and Non-Clustered index.

A sketch of the index structure (here for a clustered index, but as I said: the only difference for a nonclustered index is the actual contents of the leaf pages) can be found on http://msdn.microsoft.com/en-us/library/ms177443.aspx. The blue pointers are the pointers to lower level index pages just mentioned. The black arrows indicate the "next page"" / "previous page" pointers found on every page in an index. These pointer chains are used when an index is processed in its logical order.

The physical arrangement of these pages can be completely different. As an example, let's suppose that an existing table happens to have all its 10,000 leaf pages on the first 10,000 pages in the database file (very unlikely in reality, but work with me). Now an INSERT is executed and the new row should be inserted in the fifth page - but that page is already full, so it has to be split - half the data remains on page 5, half the data goes to a new page that, logicallly, belongs between page 5 and the "old" page 6. SQL Server will not physically move "old" pages 6 through 10,000 up one location - that would really kill performance! Instead, a new page will be allocated "somewhere" in the data file. This new page will have its "previous page" and "next page" pointers pointing to the "old" pages 5 and 6 respectively, and the "next page" pointer on the old page 5 and the "previous page" pointer on the old page 6 will point to the new page. The result is that the pointer chain now still implements the logical order of the index; the physical location of pages however does not.
(And since this same allocation mechanism has been used when the first 10,000 pages were allocated, it is indeed extremely unlikely to find 10,000 data pages allocated consecutively.
Post #918059
Posted Friday, May 7, 2010 9:12 AM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Today @ 2:33 AM
Points: 6,020, Visits: 8,289
dunnjoe (5/7/2010)
I believe this explanation is incorrect for the way the question was asked. Your question asked if the rows were physically or logically ordered, not if the pages were physically or logically ordered. All the rows are indeed physically ordered on their pages based on the clustered index.

Thanks for the feedback, dunnjoe!

However, the question was about the ordering of rows in a table, not rows on a page, so I don't think that part of the question was phrased incorrect.

And even if it had been about rows on a page - not even those are physically ordered; see my reply to Jan, a few posts back (near the top of this page).



Hugo Kornelis, SQL Server MVP
Visit my SQL Server blog: http://sqlblog.com/blogs/hugo_kornelis
Post #918062
Posted Friday, May 7, 2010 9:22 AM
SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

Group: General Forum Members
Last Login: Thursday, March 31, 2011 1:40 AM
Points: 1,938, Visits: 208
Hugo,

Thanks for the response. I stand corrected and will recreate my clustered indexes more frequently

Thanks,

Joe

Hugo Kornelis (5/7/2010)
dunnjoe (5/7/2010)
I believe this explanation is incorrect for the way the question was asked. Your question asked if the rows were physically or logically ordered, not if the pages were physically or logically ordered. All the rows are indeed physically ordered on their pages based on the clustered index.

Thanks for the feedback, dunnjoe!

However, the question was about the ordering of rows in a table, not rows on a page, so I don't think that part of the question was phrased incorrect.

And even if it had been about rows on a page - not even those are physically ordered; see my reply to Jan, a few posts back (near the top of this page).
Post #918068
« Prev Topic | Next Topic »

Add to briefcase «««23456»»

Permissions Expand / Collapse