Feb
29
2016

Clustered index row order

One of the basic (and well used during interviews) questions about SQL Server internals is how you call a table without a clustered index, and that in SQL Server is called a HEAP.

Also you might be asked what differences are between a HEAP table and a Clustered (index) table, which at the most basic level you can say that in a clustered index rows are physically stored following the order of the clustering key as opposite to the HEAP where rows are stored as they come with no specific order.

Till here the basics… now if you’re ready, I will show you the truth…

It’s not that what I said before is not true, but it’s easily misunderstood. A clustered index is a physical structure called B-Tree or balanced tree (like a pyramid), where the levels at the bottom (leaf levels) contain the data and the upper levels contain, lets say, the path to find an individual row based on the clustering key.

Hence we can say that a range of clustering keys are perfectly identified in the upper levels so if we need any specific key we know exactly in which page we will find it (or not if it doesn’t exist) minimizing the number of pages read to reach it.

The fact that we know a range of keys is in one single page and that a clustered index sorts the data, does not imply that physically the records will be stored that way.

Please see the following example and you will understand what I’m talking about.

USE master
GO
IF DB_ID('row_order') IS NOT NULL BEGIN
    ALTER DATABASE [row_order] SET SINGLE_USER WITH ROLLBACK IMMEDIATE
    DROP DATABASE [row_order]
END
GO     
 
CREATE DATABASE [row_order]
GO
 
USE [row_order]
GO
  
IF OBJECT_ID('dbo.table_clustered') IS NOT NULL DROP TABLE dbo.table_clustered
GO
  
CREATE TABLE dbo.table_clustered(
    Id      INT NOT NULL PRIMARY KEY,
    Col2    VARCHAR(100) NOT NULL DEFAULT 'A',
)
GO
  
INSERT INTO dbo.table_clustered VALUES(2, DEFAULT)
GO

SELECT * FROM table_clustered
 
-- See list of pages allocated to the clustered index of the table
DBCC IND('row_order', 'dbo.table_clustered', 1)
GO
  
DBCC TRACEON(3604,1)
  
-- Use first page with PageType = 1 from DBCC IND()
DBCC PAGE('row_order', 1, xxx, 1)
GO

So far you can see that the only row inside our table, starts immediately after the page header (96 bytes) so that is its offset in the ‘slot array’.

/*
DATA:


Slot 0, Offset 0x60, Length 16, DumpStyle BYTE

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

0000000000000000:   30000800 02000000 02000001 00100041           0..............A

OFFSET TABLE:

Row - Offset                        
0 (0x0) - 96 (0x60)                 

*/

But this row has Id=2 and our table (records) must be sorted by that key, so what if I insert Id=1, will this go before Id=2 and ‘push’ it to the back, as we might expect?

USE [row_order]
GO

INSERT INTO dbo.table_clustered VALUES(1, DEFAULT)
GO

-- Use first page with PageType = 1 from DBCC IND()
DBCC PAGE('row_order', 1, xxx, 1)
GO
-- See row Id=1 has been physically placed after Id=2, but the important is the place it takes in the slot array. (end of the page)

Not so much, moving record with Id=2 to make room for Id=1 will be a very expensive operation, so as far as there is enough free space in that page to accommodate the new row, it does not matter where in the page is physically written down, because the SQL Storage Engine will look at the slot array to see in which order has to read them.

/*
DATA:


Slot 0, Offset 0x70, Length 16, DumpStyle BYTE

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

0000000000000000:   30000800 01000000 02000001 00100041           0..............A

Slot 1, Offset 0x60, Length 16, DumpStyle BYTE

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

0000000000000000:   30000800 02000000 02000001 00100041           0..............A

OFFSET TABLE:

Row - Offset                        
1 (0x1) - 96 (0x60)                 
0 (0x0) - 112 (0x70)                

*/

You can see that now, the slot 0 (for Id=1) is after slot 1 (Id=2), so physically is stored after it. Obviously that is not important at all since the important is how the records are sorted inside the slot array.

Hope you enjoy reading and feel free to comment or post any question you may have.

 

One comment

Leave a Reply

Your email address will not be published. Required fields are marked *