SQL Server Clustered Index Btree Traversal

By: Mike Byrd


–Brought to you as a script! Enjoy

--� 2017 | ByrdNest Consulting
--Index B-Tree Analysis

/************************************************************************************

	This script explores clustered, unique-nonclustered, and nonclustered indexes 
	at the page level.  Most likely the page ids used here will change in your 
	database configuration and setup -- mine rarely used same page ids even with 
	repetitive usage.  However, the base data remained the same.  Questions, please email!

	by Mike Byrd
	   Senior Database Engineer
	   ByrdNest Consulting
	   mbyrd@byrdnest-tx.com
	   www.TSQLMentoring.com

**************************************************************************************/
--start with clean copy of AdventureWorkw2012
USE [master]
ALTER DATABASE [AdventureWorks2012] SET SINGLE_USER WITH ROLLBACK IMMEDIATE		--kick off all users except me
RESTORE DATABASE [AdventureWorks2012] 
	FROM  DISK = N'D:\Misc\AdventureWorks2012\AdventureWorks2012.bak' WITH  FILE = 1,
	NOUNLOAD,  REPLACE,  STATS = 20
ALTER DATABASE [AdventureWorks2012] SET MULTI_USER								--set back to multi-user
GO
ALTER AUTHORIZATION ON DATABASE::AdventureWorks2012 TO sa;						--give ownership to sa; not me
GO
USE AdventureWorks2012
GO

--first let's look at  B-Tree for Primary Key, Clustered Index one in the same
SELECT *
	FROM sys.sysindexes
	WHERE [Name] IN ('PK_SalesOrderDetail_SalesOrderID_SalesOrderDetailID');
GO
--indid = 1

SELECT OBJECT_NAME(object_id), index_id, partition_id,allocated_page_page_id, is_iam_page, page_type
		,page_type_desc, page_level,next_page_file_id,next_page_page_id,previous_page_file_id
		,previous_page_page_id, is_page_compressed
	FROM sys.dm_db_database_page_allocations (DB_ID(), OBJECT_ID('Sales.SalesOrderDetail'), 1,1,'Detailed')
	WHERE page_level IS NOT NULL
	ORDER BY (page_level+page_type) DESC,allocated_page_page_id
GO
-- note order, IAM_Page, INDEX_Page (One at Page_Level 2 and 7 at Page_Level 1)
-- Level 2 at page 1431

	--almost same results as above SELECT using
DBCC IND('AdventureWorks2012','Sales.SalesOrderDetail',1)
GO
*/

--first page in index 1 (IAM Page)
DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,810,3) WITH TABLERESULTS		--note row 59 Field 1:24272
GO
DBCC TRACEOFF(3604)
GO
--lots of stuff, but today important row is pointer to first index_level 2 at page 1431 (row 50)


--2nd page in index 1 (Index Page, --1431 (from IAM page)), root level
DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,1431,3) WITH TABLERESULTS		
								--note 2nd result set (intermediate level); Child PageID = 10824
GO
DBCC TRACEOFF(3604)
GO
-- look at 2nd result set; SalesOrderID (key), SalesOrderDetailID (key), KeyHashValue is null
-- for purposes of this traversal we will look at the branch where the keys are null and next
-- boundary is < 50178,30887 (keys); structure like Right Partition boundaries; notice that 
--	ChildPadeIDs are not in sequence.


--3rd page in index 1 (Index Page, --10824 (from DBCC Page 1431)); intermediate level
DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,10824,3) WITH TABLERESULTS		--note 2nd result set (intermediate level); Child PageID = 10672
GO
DBCC TRACEOFF(3604)
GO
--look at 2nd result set, now lower key boundary (NULL,NULL) and upper boundary is now 
--	(43668,85). Result set now has 352 rows.  ChildPageID is now 10672 


--4th page in index 1 (Index Page, --10672 (leaf level); note all data/row here!
DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,10672,3) WITH TABLERESULTS		--
GO
DBCC TRACEOFF(3604)
GO
--now only one result set; note after header info there is full row data.  Note that last 
--	row of data is for PK = (43668,84) {the 84 is one less than the next boundary for 
--	SalesOrderDetailID}; KeyHashValue has data

/****** UNIQUE NON-CLUSTERED INDEX **************/
--now let's create a unique computer column, persist it, and create unique index
ALTER TABLE Sales.SalesOrderDetail ADD uSalesOrderDetail AS (SalesOrderDetailID + 100) Persisted;
GO
CREATE UNIQUE NONCLUSTERED INDEX IDX_SalesOrderDetail_uSalesOrderDetail
	ON Sales.SalesOrderDetail(uSalesOrderDetail)
GO


SELECT ID,Name,Dpages,reserved,used,rowcnt,indid
	FROM sys.sysindexes
	WHERE [Name] IN ('IDX_SalesOrderDetail_uSalesOrderDetail');
--indid = 5
GO

--now let's look at index contents
SELECT OBJECT_NAME(object_id), index_id, partition_id,allocated_page_page_id, is_iam_page, page_type
		,page_type_desc, page_level,next_page_file_id,next_page_page_id,previous_page_file_id
		,previous_page_page_id, is_page_compressed
	FROM sys.dm_db_database_page_allocations (DB_ID(), OBJECT_ID('Sales.SalesOrderDetail'), 5,1,'Detailed')
	WHERE page_level IS NOT NULL
	ORDER BY (page_level+page_type) DESC,allocated_page_page_id
GO
--IAM_Page = 23816; only one intermediate level in index at page 25696; rest of INDEX_Pages
--	at page_level 0

--DBCC IND('AdventureWorks2012','Sales.SalesOrderDetail',5)
--GO


--first page in index 5 (IAM Page)
DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,23816,3) WITH TABLERESULTS		--note row 59 Field 1:25648
GO
DBCC TRACEOFF(3604)
GO
--no useful info (to me)

--let's look at intermediate index page
--1st intermediate page in idex 5 (Index_Page, IndexLevel = 1) 25648; note no NextPageFID
DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,25648,3) WITH TABLERESULTS		
GO
DBCC TRACEOFF(3604)
GO
--look at 2nd result set; note next ChildPageID, no Primary Key columns and KeyHashValue is NULL
--  hence, unique index column(s) do not require PKs in the intermediate levels -- can pack tree
--	level points better -- thus less logical reads.

-- now look at first ChildPageID (lower boundary = NULL)
--1st leaf page in idex 5 (Index_Page) 25472
DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,25472,3) WITH TABLERESULTS		
GO
DBCC TRACEOFF(3604)
GO
--note index contains unique column (uSalesOrderDetail), PKs (SalesOrderID & SalesOrderDetailID) &
--	KeyHashValue at Leaf Level; 449 rows at leaf level
--  appears unique indexes only carry unique key at intermediate level -- thus
--	offerring some logical IO advantage for that index.  


/*************** NON-CLUSTERED INDEX (Covering) ************/
--now let's look at a nonclustered index
CREATE NONCLUSTERED INDEX IDX_SalesOrderDetail_ModifiedDate 
	ON Sales.SalesOrderDetail(ModifiedDate)
	INCLUDE (CarrierTrackingNumber,OrderQty, ProductID)
GO

SELECT ID,Name,Dpages,reserved,used,rowcnt,indid
	FROM sys.sysindexes
	WHERE [Name] IN ('IDX_SalesOrderDetail_ModifiedDate');
GO
--indid = 8


SELECT OBJECT_NAME(object_id), index_id, partition_id,allocated_page_page_id, is_iam_page, page_type
		,page_type_desc, page_level,next_page_file_id,next_page_page_id,previous_page_file_id
		,previous_page_page_id, is_page_compressed
	FROM sys.dm_db_database_page_allocations (DB_ID(), OBJECT_ID('Sales.SalesOrderDetail'), 8,1,'Detailed')
	WHERE page_level IS NOT NULL
	ORDER BY (page_level+page_type) DESC,allocated_page_page_id
GO
--IAM_page = 23818; have one page at level 2 (26304, root) 
--	and 6 intermediate index_pages at level 1; 1456 at level 0


DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,23818,3) WITH TABLERESULTS		--note row 59 Field 1:26304
GO
DBCC TRACEOFF(3604)
GO


--Intermediate Level 2
DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,26304,3) WITH TABLERESULTS		
GO
DBCC TRACEOFF(3604)
GO
--looking at result set 2, we have ModifiedDate + PKs; if we want to traverse the NULL boundary
--	we need to look at ChildPageID = 26568

--Intermediate Level 1 (8 pages)
DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,26568,3) WITH TABLERESULTS		
GO
DBCC TRACEOFF(3604)
GO
--again, looking at result set 2 and staying on the PK NULL,NULL boundary we have ChildPageID = 26344

DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,26344,3) WITH TABLERESULTS		
GO
DBCC TRACEOFF(3604)
GO
--now we are at level 0, have ModifiedDate, PKs, and Included columns and KeyHashValue


/**** Now look at NON-CLUSTERED Covering Index with computed column ****/

CREATE NONCLUSTERED INDEX IDX_SalesOrderDetail_ModifiedDate2 on Sales.SalesOrderDetail(ModifiedDate)
	INCLUDE (CarrierTrackingNumber,OrderQty, ProductID,
			 SpecialOfferID,UnitPrice,UnitPriceDiscount,LineTotal,rowguid)
--	WITH (DROP_EXISTING = ON, ONLINE = ON)
GO

SELECT ID,Name,Dpages,reserved,used,rowcnt,indid
	FROM sys.sysindexes
	WHERE [Name] IN ('IDX_SalesOrderDetail_ModifiedDate2');
GO
--indid = 9


SELECT OBJECT_NAME(object_id), index_id, partition_id,allocated_page_page_id, is_iam_page, page_type
		,page_type_desc, page_level,next_page_file_id,next_page_page_id,previous_page_file_id
		,previous_page_page_id, is_page_compressed
	FROM sys.dm_db_database_page_allocations (DB_ID(), OBJECT_ID('Sales.SalesOrderDetail'), 9,1,'Detailed')
	WHERE page_level IS NOT NULL
	ORDER BY (page_level+page_type) DESC,allocated_page_page_id
GO
--IAM_page = 23819; have one page at level 2 (27680) and 8 index_pages at level 1; 25448 at level 0


--Intermediate Level 2
DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,27680,3) WITH TABLERESULTS		
GO
DBCC TRACEOFF(3604)
GO
--looking at result set 2, we have ModifiedDate + PKs; if we want to traverse the NULL boundary
--	we need to look at ChildPageID = 27976

--Intermediate Level 1 (8 pages)
DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,27976,3) WITH TABLERESULTS		
GO
DBCC TRACEOFF(3604)
GO
--again, looking at result set 2 and staying on the PK NULL,NULL boundary we have ChildPageID = 27848

DBCC TRACEON(3604)
DBCC PAGE('AdventureWorks2012',1,27848,3) WITH TABLERESULTS		
GO
DBCC TRACEOFF(3604)
GO
--now we are at level 0, have ModifiedDate, PKs, and Included columns and KeyHashValue;
--	also have computed column LineTotal persisted.

Trackbacks

Leave a Reply