SQL Clone
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


Clustered indexes


Clustered indexes

Author
Message
ziangij
ziangij
Hall of Fame
Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)Hall of Fame (3.6K reputation)

Group: General Forum Members
Points: 3608 Visits: 377
thanks for this wonderful question :-)
Jan Van der Eecken
Jan Van der Eecken
Hall of Fame
Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)

Group: General Forum Members
Points: 3273 Visits: 6497
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)
Hugo Kornelis
Hugo Kornelis
SSCoach
SSCoach (18K reputation)SSCoach (18K reputation)SSCoach (18K reputation)SSCoach (18K reputation)SSCoach (18K reputation)SSCoach (18K reputation)SSCoach (18K reputation)SSCoach (18K reputation)

Group: General Forum Members
Points: 18933 Visits: 12426
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
Paul White
Paul White
SSC-Dedicated
SSC-Dedicated (35K reputation)SSC-Dedicated (35K reputation)SSC-Dedicated (35K reputation)SSC-Dedicated (35K reputation)SSC-Dedicated (35K reputation)SSC-Dedicated (35K reputation)SSC-Dedicated (35K reputation)SSC-Dedicated (35K reputation)

Group: General Forum Members
Points: 35976 Visits: 11361
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
SQLPerformance.com
SQLblog.com
@SQL_Kiwi
Jan Van der Eecken
Jan Van der Eecken
Hall of Fame
Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)

Group: General Forum Members
Points: 3273 Visits: 6497
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)
Tom Brown
Tom  Brown
Hall of Fame
Hall of Fame (3.4K reputation)Hall of Fame (3.4K reputation)Hall of Fame (3.4K reputation)Hall of Fame (3.4K reputation)Hall of Fame (3.4K reputation)Hall of Fame (3.4K reputation)Hall of Fame (3.4K reputation)Hall of Fame (3.4K reputation)

Group: General Forum Members
Points: 3380 Visits: 1491
@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)
TravisDBA
TravisDBA
Hall of Fame
Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)Hall of Fame (3.3K reputation)

Group: General Forum Members
Points: 3346 Visits: 3069
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. :-D

"Technology is a weird thing. It brings you great gifts with one hand, and it stabs you in the back with the other. ...:-D"
dunnjoe
dunnjoe
SSCommitted
SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)

Group: General Forum Members
Points: 1966 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.

Hugo Kornelis
Hugo Kornelis
SSCoach
SSCoach (18K reputation)SSCoach (18K reputation)SSCoach (18K reputation)SSCoach (18K reputation)SSCoach (18K reputation)SSCoach (18K reputation)SSCoach (18K reputation)SSCoach (18K reputation)

Group: General Forum Members
Points: 18933 Visits: 12426
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
dunnjoe
dunnjoe
SSCommitted
SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)SSCommitted (2K reputation)

Group: General Forum Members
Points: 1966 Visits: 208
Hugo,

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

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

Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search