Does a clustered index sort the rows within a page

Leave a comment

December 15, 2014 by Kenneth Fisher

This is just something I was curious about. I ran my tests and got an answer and now I thought I would share.

Before I start I want to point out a few things about my tests. I’m using code to create/modify a PRIMARY KEY. PRIMARY KEYs are not necessarily backed by CLUSTERED INDEXes but they are by default and that’s what I’m using here. I could just as easily have created CLUSTERED INDEXes specifically, I just didn’t. I’m also using sys.dm_db_database_page_allocations and DBCC PAGE both of which are undocumented and unsupported. You can follow the links for further information about them but either way I wouldn’t use them on a production box.

-- Setup
CREATE TABLE ClusteredPageTest (Id INT NOT NULL IDENTITY(1,1), varcol varchar(100),
	CONSTRAINT pk_ClusteredPageTest PRIMARY KEY (Id));
GO
INSERT INTO ClusteredPageTest DEFAULT VALUES; 
GO 26

UPDATE ClusteredPageTest SET varcol = REPLICATE(CHAR(91-Id),100);
GO

INSERT INTO ClusteredPageTest DEFAULT VALUES ;
GO 26

UPDATE ClusteredPageTest SET varcol = REPLICATE(CHAR(149-Id),100)
WHERE varcol IS NULL;
GO

SELECT * FROM ClusteredPageTest;

ClusteredPage1

Note that the Id column is in numerical order while varcol is in reverse alphabetical order (once in upper case, once in lower case).

Let’s start by looking at the contents of the data page right now. I would expect it to be in numeric order since not only is the clustered index in that order but the rows were entered in that order.

DBCC TRACEON (3604);

SELECT allocated_page_file_id, allocated_page_page_id, is_iam_page 
FROM sys.dm_db_database_page_allocations (DB_ID(),OBJECT_ID('ClusteredPageTest'),NULL,NULL,NULL);

DECLARE @DB INT = DB_ID();
DBCC PAGE (@DB,1,233,3);
GO

ClusteredPage2

I’m looking at the contents of the only data page (it’s not the IAM page). I’m only going to display a portion of the output (it’s rather long). Specifically I’m going to show the part of the output that shows the first few rows of data.

Slot 0 Offset 0x17e Length 115

Record Type = PRIMARY_RECORD        Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Record Size = 115                   
Memory Dump @0x000000000B6BA17E

0000000000000000:   30000800 01000000 02000001 0073005a 5a5a5a5a  0............s.ZZZZZ
0000000000000014:   5a5a5a5a 5a5a5a5a 5a5a5a5a 5a5a5a5a 5a5a5a5a  ZZZZZZZZZZZZZZZZZZZZ
0000000000000028:   5a5a5a5a 5a5a5a5a 5a5a5a5a 5a5a5a5a 5a5a5a5a  ZZZZZZZZZZZZZZZZZZZZ
000000000000003C:   5a5a5a5a 5a5a5a5a 5a5a5a5a 5a5a5a5a 5a5a5a5a  ZZZZZZZZZZZZZZZZZZZZ
0000000000000050:   5a5a5a5a 5a5a5a5a 5a5a5a5a 5a5a5a5a 5a5a5a5a  ZZZZZZZZZZZZZZZZZZZZ
0000000000000064:   5a5a5a5a 5a5a5a5a 5a5a5a5a 5a5a5a             ZZZZZZZZZZZZZZZ

Slot 0 Column 1 Offset 0x4 Length 4 Length (physical) 4

Id = 1                              

Slot 0 Column 2 Offset 0xf Length 100 Length (physical) 100

varcol = ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ

Slot 0 Offset 0x0 Length 0 Length (physical) 0

KeyHashValue = (8194443284a0)       
Slot 1 Offset 0x1f1 Length 115

Record Type = PRIMARY_RECORD        Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Record Size = 115                   
Memory Dump @0x000000000B6BA1F1

0000000000000000:   30000800 02000000 02000001 00730059 59595959  0............s.YYYYY
0000000000000014:   59595959 59595959 59595959 59595959 59595959  YYYYYYYYYYYYYYYYYYYY
0000000000000028:   59595959 59595959 59595959 59595959 59595959  YYYYYYYYYYYYYYYYYYYY
000000000000003C:   59595959 59595959 59595959 59595959 59595959  YYYYYYYYYYYYYYYYYYYY
0000000000000050:   59595959 59595959 59595959 59595959 59595959  YYYYYYYYYYYYYYYYYYYY
0000000000000064:   59595959 59595959 59595959 595959             YYYYYYYYYYYYYYY

Slot 1 Column 1 Offset 0x4 Length 4 Length (physical) 4

Id = 2                              

Slot 1 Column 2 Offset 0xf Length 100 Length (physical) 100

varcol = YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY

Slot 1 Offset 0x0 Length 0 Length (physical) 0

KeyHashValue = (61a06abd401c)       
Slot 2 Offset 0x264 Length 115

Record Type = PRIMARY_RECORD        Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Record Size = 115                   
Memory Dump @0x000000000B6BA264

0000000000000000:   30000800 03000000 02000001 00730058 58585858  0............s.XXXXX
0000000000000014:   58585858 58585858 58585858 58585858 58585858  XXXXXXXXXXXXXXXXXXXX
0000000000000028:   58585858 58585858 58585858 58585858 58585858  XXXXXXXXXXXXXXXXXXXX
000000000000003C:   58585858 58585858 58585858 58585858 58585858  XXXXXXXXXXXXXXXXXXXX
0000000000000050:   58585858 58585858 58585858 58585858 58585858  XXXXXXXXXXXXXXXXXXXX
0000000000000064:   58585858 58585858 58585858 585858             XXXXXXXXXXXXXXX

Slot 2 Column 1 Offset 0x4 Length 4 Length (physical) 4

Id = 3                              

Slot 2 Column 2 Offset 0xf Length 100 Length (physical) 100

varcol = XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Slot 2 Offset 0x0 Length 0 Length (physical) 0

KeyHashValue = (98ec012aa510)       
Slot 3 Offset 0x2d7 Length 115

Record Type = PRIMARY_RECORD        Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Record Size = 115                   
Memory Dump @0x000000000B6BA2D7

0000000000000000:   30000800 04000000 02000001 00730057 57575757  0............s.WWWWW
0000000000000014:   57575757 57575757 57575757 57575757 57575757  WWWWWWWWWWWWWWWWWWWW
0000000000000028:   57575757 57575757 57575757 57575757 57575757  WWWWWWWWWWWWWWWWWWWW
000000000000003C:   57575757 57575757 57575757 57575757 57575757  WWWWWWWWWWWWWWWWWWWW
0000000000000050:   57575757 57575757 57575757 57575757 57575757  WWWWWWWWWWWWWWWWWWWW
0000000000000064:   57575757 57575757 57575757 575757             WWWWWWWWWWWWWWW

Slot 3 Column 1 Offset 0x4 Length 4 Length (physical) 4

Id = 4                              

Slot 3 Column 2 Offset 0xf Length 100 Length (physical) 100

varcol = WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

Slot 3 Offset 0x0 Length 0 Length (physical) 0

KeyHashValue = (a0c936a3c965)

And just as expected the rows are in Id order. Next we modify the clustered index to be the varcol.

ALTER TABLE ClusteredPageTest ALTER COLUMN varcol varchar(100) NOT NULL;
ALTER TABLE ClusteredPageTest DROP CONSTRAINT pk_ClusteredPageTest;
ALTER TABLE ClusteredPageTest ADD CONSTRAINT pk_ClusteredPageTest PRIMARY KEY (varcol);
GO

And next we look at the data page again.

SELECT allocated_page_file_id, allocated_page_page_id, is_iam_page 
FROM sys.dm_db_database_page_allocations (DB_ID(),OBJECT_ID('ClusteredPageTest'),NULL,NULL,NULL);

DECLARE @DB INT = DB_ID();
DBCC PAGE (@DB,1,236,3);
GO

ClusteredPage3

Slot 0 Offset 0x60 Length 115

Record Type = PRIMARY_RECORD        Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Record Size = 115                   
Memory Dump @0x000000000B6BA060

0000000000000000:   30000800 1a000000 02000001 00730041 41414141  0............s.AAAAA
0000000000000014:   41414141 41414141 41414141 41414141 41414141  AAAAAAAAAAAAAAAAAAAA
0000000000000028:   41414141 41414141 41414141 41414141 41414141  AAAAAAAAAAAAAAAAAAAA
000000000000003C:   41414141 41414141 41414141 41414141 41414141  AAAAAAAAAAAAAAAAAAAA
0000000000000050:   41414141 41414141 41414141 41414141 41414141  AAAAAAAAAAAAAAAAAAAA
0000000000000064:   41414141 41414141 41414141 414141             AAAAAAAAAAAAAAA

Slot 0 Column 2 Offset 0xf Length 100 Length (physical) 100

varcol = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Slot 0 Column 1 Offset 0x4 Length 4 Length (physical) 4

Id = 26                             

Slot 0 Offset 0x0 Length 0 Length (physical) 0

KeyHashValue = (b23afdcbd03a)       
Slot 1 Offset 0xd3 Length 115

Record Type = PRIMARY_RECORD        Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Record Size = 115                   
Memory Dump @0x000000000B6BA0D3

0000000000000000:   30000800 34000000 02000001 00730061 61616161  0...4........s.aaaaa
0000000000000014:   61616161 61616161 61616161 61616161 61616161  aaaaaaaaaaaaaaaaaaaa
0000000000000028:   61616161 61616161 61616161 61616161 61616161  aaaaaaaaaaaaaaaaaaaa
000000000000003C:   61616161 61616161 61616161 61616161 61616161  aaaaaaaaaaaaaaaaaaaa
0000000000000050:   61616161 61616161 61616161 61616161 61616161  aaaaaaaaaaaaaaaaaaaa
0000000000000064:   61616161 61616161 61616161 616161             aaaaaaaaaaaaaaa

Slot 1 Column 2 Offset 0xf Length 100 Length (physical) 100

varcol = aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Slot 1 Column 1 Offset 0x4 Length 4 Length (physical) 4

Id = 52                             

Slot 1 Offset 0x0 Length 0 Length (physical) 0

KeyHashValue = (966d052b3c2e)       
Slot 2 Offset 0x146 Length 115

Record Type = PRIMARY_RECORD        Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Record Size = 115                   
Memory Dump @0x000000000B6BA146

0000000000000000:   30000800 19000000 02000001 00730042 42424242  0............s.BBBBB
0000000000000014:   42424242 42424242 42424242 42424242 42424242  BBBBBBBBBBBBBBBBBBBB
0000000000000028:   42424242 42424242 42424242 42424242 42424242  BBBBBBBBBBBBBBBBBBBB
000000000000003C:   42424242 42424242 42424242 42424242 42424242  BBBBBBBBBBBBBBBBBBBB
0000000000000050:   42424242 42424242 42424242 42424242 42424242  BBBBBBBBBBBBBBBBBBBB
0000000000000064:   42424242 42424242 42424242 424242             BBBBBBBBBBBBBBB

Slot 2 Column 2 Offset 0xf Length 100 Length (physical) 100

varcol = BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

Slot 2 Column 1 Offset 0x4 Length 4 Length (physical) 4

Id = 25                             

Slot 2 Offset 0x0 Length 0 Length (physical) 0

KeyHashValue = (f6f518f4b665)       
Slot 3 Offset 0x1b9 Length 115

Record Type = PRIMARY_RECORD        Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Record Size = 115                   
Memory Dump @0x000000000B6BA1B9

0000000000000000:   30000800 33000000 02000001 00730062 62626262  0...3........s.bbbbb
0000000000000014:   62626262 62626262 62626262 62626262 62626262  bbbbbbbbbbbbbbbbbbbb
0000000000000028:   62626262 62626262 62626262 62626262 62626262  bbbbbbbbbbbbbbbbbbbb
000000000000003C:   62626262 62626262 62626262 62626262 62626262  bbbbbbbbbbbbbbbbbbbb
0000000000000050:   62626262 62626262 62626262 62626262 62626262  bbbbbbbbbbbbbbbbbbbb
0000000000000064:   62626262 62626262 62626262 626262             bbbbbbbbbbbbbbb

Slot 3 Column 2 Offset 0xf Length 100 Length (physical) 100

varcol = bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb

Slot 3 Column 1 Offset 0x4 Length 4 Length (physical) 4

Id = 51                             

Slot 3 Offset 0x0 Length 0 Length (physical) 0

KeyHashValue = (d2a2e0145a71)

And there you go. The order of the rows within the page has actually changed. To be fair this isn’t terribly surprising since that’s the whole point of the CLUSTERED INDEX (the physical order of the rows). However it’s still a lot of fun to test things out. In fact let’s do one last test. Let’s insert a row and see if it ends up at the end of the page or in the middle.

INSERT INTO ClusteredPageTest VALUES ('B');

And look at the page again.

DECLARE @DB INT = DB_ID();
DBCC PAGE (@DB,1,236,3);
GO
Slot 0 Offset 0x60 Length 115

Record Type = PRIMARY_RECORD        Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Record Size = 115                   
Memory Dump @0x0000000008C0A060

0000000000000000:   30000800 1a000000 02000001 00730041 41414141  0............s.AAAAA
0000000000000014:   41414141 41414141 41414141 41414141 41414141  AAAAAAAAAAAAAAAAAAAA
0000000000000028:   41414141 41414141 41414141 41414141 41414141  AAAAAAAAAAAAAAAAAAAA
000000000000003C:   41414141 41414141 41414141 41414141 41414141  AAAAAAAAAAAAAAAAAAAA
0000000000000050:   41414141 41414141 41414141 41414141 41414141  AAAAAAAAAAAAAAAAAAAA
0000000000000064:   41414141 41414141 41414141 414141             AAAAAAAAAAAAAAA

Slot 0 Column 2 Offset 0xf Length 100 Length (physical) 100

varcol = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Slot 0 Column 1 Offset 0x4 Length 4 Length (physical) 4

Id = 26                             

Slot 0 Offset 0x0 Length 0 Length (physical) 0

KeyHashValue = (b23afdcbd03a)       
Slot 1 Offset 0xd3 Length 115

Record Type = PRIMARY_RECORD        Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Record Size = 115                   
Memory Dump @0x0000000008C0A0D3

0000000000000000:   30000800 34000000 02000001 00730061 61616161  0...4........s.aaaaa
0000000000000014:   61616161 61616161 61616161 61616161 61616161  aaaaaaaaaaaaaaaaaaaa
0000000000000028:   61616161 61616161 61616161 61616161 61616161  aaaaaaaaaaaaaaaaaaaa
000000000000003C:   61616161 61616161 61616161 61616161 61616161  aaaaaaaaaaaaaaaaaaaa
0000000000000050:   61616161 61616161 61616161 61616161 61616161  aaaaaaaaaaaaaaaaaaaa
0000000000000064:   61616161 61616161 61616161 616161             aaaaaaaaaaaaaaa

Slot 1 Column 2 Offset 0xf Length 100 Length (physical) 100

varcol = aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Slot 1 Column 1 Offset 0x4 Length 4 Length (physical) 4

Id = 52                             

Slot 1 Offset 0x0 Length 0 Length (physical) 0

KeyHashValue = (966d052b3c2e)       
Slot 2 Offset 0x17bc Length 16

Record Type = PRIMARY_RECORD        Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Record Size = 16                    
Memory Dump @0x0000000008C0B7BC

0000000000000000:   30000800 35000000 02000001 00100042           0...5..........B

Slot 2 Column 2 Offset 0xf Length 1 Length (physical) 1

varcol = B                          

Slot 2 Column 1 Offset 0x4 Length 4 Length (physical) 4

Id = 53                             

Slot 2 Offset 0x0 Length 0 Length (physical) 0

KeyHashValue = (e427f1f93d77)       
Slot 3 Offset 0x146 Length 115

Record Type = PRIMARY_RECORD        Record Attributes =  NULL_BITMAP VARIABLE_COLUMNS
Record Size = 115                   
Memory Dump @0x0000000008C0A146

0000000000000000:   30000800 19000000 02000001 00730042 42424242  0............s.BBBBB
0000000000000014:   42424242 42424242 42424242 42424242 42424242  BBBBBBBBBBBBBBBBBBBB
0000000000000028:   42424242 42424242 42424242 42424242 42424242  BBBBBBBBBBBBBBBBBBBB
000000000000003C:   42424242 42424242 42424242 42424242 42424242  BBBBBBBBBBBBBBBBBBBB
0000000000000050:   42424242 42424242 42424242 42424242 42424242  BBBBBBBBBBBBBBBBBBBB
0000000000000064:   42424242 42424242 42424242 424242             BBBBBBBBBBBBBBB

Slot 3 Column 2 Offset 0xf Length 100 Length (physical) 100

varcol = BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

Slot 3 Column 1 Offset 0x4 Length 4 Length (physical) 4

Id = 25                             

Slot 3 Offset 0x0 Length 0 Length (physical) 0

KeyHashValue = (f6f518f4b665)

And the new row is in the middle of the page right where you would expect it to be.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 1,682 other followers

Follow me on Twitter

ToadWorld Pro of the Month November 2013
%d bloggers like this: