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