Christian Buettner-167247 (10/5/2010)
I am not satisfied with the answer, indeed I find it very misleading.
I have to disagree. I am completely satisfiied with the answer, as it is 100% correct. I find the explanation lacking, but definitely not misleading.
As data is inserted or the clustering key values are updated, SQL Server only preserves logical ordering of the data. It would require far too many resources to preserve physical ordering of the data.
What you are referring to is the physical order within a page.
I don't think so. In fact, the cost of changing the physical order within a page is not that much; the page is in cache anyway, it is alwayys read and written as a whole, so the only cost is that of moving at most 8,000 bytes around in a memory block. Measured in fractions of a microsecond.
The prohibitive use of resources would come when a page overflows. If physical order has to be preserved and the free space between rows runs out, all rows have to be physically moved. Just think for a while what would happen if you have a 10-billion row table, and you need to insert a row somewhere halfway in the table? Do you reallly expect SQL Server to physically relocate 5 billion rows, to make place for the new row? It does not. It allocates a new page, somewhere, and changes the pointer chain to preserve the logical order.
What you have left out here, is the fact that rows are indeed sorted in physical order accross pages.
So if you have 2 records on one page, and a new record that logically belongs between them does not fit on the same page anymore, the logically last row of the existing records will be moved to a new page, and the new record will be stored on the existing page to preserve physical order.
This would only preserve physical order if SQL Server allocated the new page "between" the two old pages. It does not. (I have some repro code down below).
Here is some more background information which I think is necessary to really understand the discussed concepts:
Clustered indexes are not a good choice for:
Columns that undergo frequent changes
This results in the entire row moving (because SQL Server must keep the data values of a row in physical order). This is an important consideration in high-volume transaction processing systems where data tends to be volatile.
http://blogs.msdn.com/b/sqlserverstorageengine/archive/2006/06/26/647005.aspx
A change in a clustered index value can indeed result in the row moving to another page. But the use of the words "physical order" in this quote is sloppy - not up to Pauls normal standard.
It's a very common misconception that records within a page are always stored in logical order.
http://www.sqlskills.com/blogs/paul/2007/10/03/InsideTheStorageEngineAnatomyOfAPage.aspx
(Again - note that this is referring to order within a page only)
Though I don't think this is what Robert intended with his question, it does further support the correct answer. Within a single page, the rows can physically be stored out of order. The slot array is used to represent the logical order.
To demonstrate that the physical order of pages is not equal to the logical order, run the script below and check the output. Here is an explanation of what happens.
I first create a new database, then a table with a large data column so don't need lots of rows to fill a few pages. I then fill the row with data in ascending clustered index order. If the database files are not fragmented, all free space is continuous, the database files do not reside on SAN or RAID, and nobody else is using the database at the same time, then it is likely (though I won't vow for it) that the pages allocated will actually be in physical order.
I then insert a single extra row that logically goes in the beginning of the table. There are four rows per page, so the row to be added goes to the second page (with key values 9, 11, 13, and 15). This page can't accomodate a fifth row, so it has to be split. The first two rows remain on their page, the other two are moved to a new page. This new page is not squeezed in between the second page and the "old" third page, but just allocated where there is place - probably right after the last page allocated to this table (assuming no other activity in the database). Pointers are used to preserve logical order.
Then, I run a simple query. Watch the TABLOCK hint - either that or a NOLOCK hint is required to get the intended results. That is because only a full table lock or no locking at all allows SQL Server to use the "IAM scan" - a scan that uses the index allocation map to see what pages are allocated to the table and then process those pages in their physical allocation order. When the table exceeds a certain size, the cost of this kind of scan is lower than a scan that follows the pointers that define the logical order. (This size threshold is the reason I had to add 500 rows).
If you run the query, you will see that the results are "almost" ordered - the only "disorder" is the gap between values 12 and 17; the rows with key values 13 and 15 are not missing; they appear at the very end of the results, after the vallue 999. This is what the physical order of the tablle looks like after we forced a page split.
CREATE DATABASE Demo;
go
USE Demo;
go
CREATE TABLE Demo
(KeyCol int NOT NULL PRIMARY KEY,
DataCol char(2000));
go
DECLARE @i int;
SET @i = 1
WHILE @i < 1000
BEGIN;
INSERT INTO Demo (KeyCol, DataCol)
VALUES (@i, 'Some data');
SET @i = @i + 2;
END;
go
INSERT INTO Demo (KeyCol, DataCol)
SELECT 12, 'Added later';
go
SELECT *
FROM Demo WITH (TABLOCK);
go
USE master;
go
DROP DATABASE Demo;
go