Does a clustered index sort the rows within a page
Leave a commentDecember 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;
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
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
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.
SQL Studies 