Hi All,
It has being quite some time since I added a new post since off late I am not spending much of time on research. But I have started my research again and in this post I will be talking about Fragmentation of Index which occurs due to split of root node of an index.
We all know that in Sql server, Index is organized in the form of B-tree structure wherein the data lies on the leaf level (also called leaf nodes) followed by intermediate node and finally root node at the top.
Indexes are performance boosters for Select queries however the same indexes are overhead for DML operations. Also as data is inserted/updated and deleted the index tend to get Fragmented.
In Sql Server we have 2 types of Fragmention viz Logical Fragmentation and Extent Fragmentation.
Logical Fragmentation happens when the index goes out of shape i.e Balanced Tree structure is distorted while Extent Fragmentation is caused due to page splits when the new pages are allocated in the new extent which might be different area of the datafile or even different datafile of a filegroup.
Fragmentation is mainly caused due to Page Splits which occurs either at the leaf node or intermediate node or root node. Fragmentation at the leaf nodes can be fixed using reorganize of Index however page splits at intermediate node or root node causes depth of the index to increase which is more detrimental from the point of view performance. Since every access path to the leaf node of index goes through root and intermediate node.
So in the following script I have tried to demo how root node of index splits and in order to fix the fragmentation we have rebuild the index because reorganize of index operate s at leaf level but does not operate at root level and intermediate.
Note: In Sql 2000 fragmentation of the index is monitored using DBCC SHOWCONTIG while starting sql 2005 fragmentation is monitored using a DMV sys.dm_db_index_physical_stats
create table test(a int, b char(3950))
go
–truncate table test
declare @i int
set @i = 0
while @i < 100000
begin
insert into test(a,b) values(@i, ‘test’)
set @i= @i+1;
end
create clustered index test_idx on test(a)
go
——Find the first root page of the index
select first_page, CONVERT (INT, SUBSTRING (root_page, 4, 1) + SUBSTRING (root_page, 3, 1) + SUBSTRING (root_page, 2, 1) + SUBSTRING (root_page, 1, 1)) AS ‘rootPage’,data_pages from sys.system_internals_allocation_units inner join sys.partitions on container_id = partition_id where object_id = OBJECT_ID(‘test’)
—– See the fragmentation, page count and index _ depth on the clustered index initially
select * from sys.dm_db_index_physical_stats(1,OBJECT_ID(‘test’),1,1,NULL)
index_type_desc index_depth index_level avg_fragmentation_in_percent fragment_count avg_fragment_size_in_pages page_count
—————— ———– ———– —————————- ——————– ————————– ———
CLUSTERED INDEX 3 0 0.01 675 74.0755555555556 50001
———- DBCC PAGE on the root page shows that points to 114 intermediate pages
dbcc TRACEON(3604)
DBCC PAGE(1,1,50978,3) — root page giving pointers to next intermediate level
1 root page + 114 intermediate page
FileId PageId Row Level ChildFileId ChildPageId a (key) UNIQUIFIER (key) KeyHashValue
—— ———– —— —— ———– ———– ———– —————- —————-
1 50978 0 2 1 50976 NULL NULL NULL
1 50978 1 2 1 50977 1010 0 NULL
1 50978 2 2 1 50979 2020 0 NULL
1 50978 3 2 1 50980 3030 0 NULL
1 50978 4 2 1 50981 4040 0 NULL
1 50978 5 2 1 50982 5050 0 NULL
1 50978 6 2 1 50983 6060 0 NULL
1 50978 7 2 1 50984 7070 0 NULL
1 50978 8 2 1 50985 8080 0 NULL
—- insert few more rows to introduce fragmentation
declare @i int
declare @j int
set @i = 0
set @j = 4
while @i < 110000
begin
insert into test(a,b) values(4, ‘test’)
set @i= @i+1;
end
—- check fragmentation, page_count and depth of the index again
select * from sys.dm_db_index_physical_stats(1,OBJECT_ID(‘test’),1,1,NULL),index_type_desc index_depth index_level avg_fragmentation_in_percent fragment_count avg_fragment_size_in_pages page_count
—————————– ———– —————————- ——————– ————————– ———
CLUSTERED INDEX 4 0 0.368175124088653 1095 100.458447488584 111915
—Depth of the index is now 4
— Letz check the root_page again for the table
select first_page, CONVERT (INT, SUBSTRING (root_page, 4, 1) + SUBSTRING (root_page, 3, 1) + SUBSTRING (root_page, 2, 1) + SUBSTRING (root_page, 1, 1)) AS ‘rootPage’,data_pages from sys.system_internals_allocation_units inner join sys.partitions on container_id = partition_id where object_id = OBJECT_ID(‘test’)
— Root Page is changed since it was split and hence we got new depth in the index. The previous root page is now at Level 2 and new root page at Level 3
DBCC PAGE(1,1,141458,3) — root page giving pointers to next 2 intermediate page which is inturn giving pointers to another pages
156 intermediate pages(Level 1) + 2 intermediate page (Level 1)+ 1 root page
dbcc ind(master,test,1)
PageFID PagePID IAMFID IAMPID ObjectID IndexID PartitionNumber PartitionID iam_chain_type PageType IndexLevel NextPageFID NextPagePID PrevPageFID PrevPagePID
——- ———– —— ———– ———– ———– ————- ——————– ——————-
1 620 NULL NULL 1403152044 1 1 7.20576E+16 In-row data 10 NULL 0 0 0 0
1 42050 1 620 1403152044 1 1 7.20576E+16 In-row data 2 2 1 141459 0 0
1 141458 1 620 1403152044 1 1 7.20576E+16 In-row data 2 3 0 0 0 0
1 141459 1 620 1403152044 1 1 7.20576E+16 In-row data 2 2 0 0 1 42050
— Let us observe the changes in Fragmentation after reorganizing the index
ALTER INDEX test_idx On TEST REORGANIZE
— No change observed in depth of the index or Fragmentation percent but only page is reduced in the total page_count
select * from sys.dm_db_index_physical_stats(1,OBJECT_ID(‘test’),1,1,NULL)
index_type_desc index_depth index_level avg_fragmentation_in_percent fragment_count avg_fragment_size_in_pages page_count
—————– ———– ———– —————————- ——————– ————————– ————-
CLUSTERED INDEX 4 0 0.322569115570885 378 296.068783068783 111914
— We checked the root page and number of intermediate pages . Those remain the same.
DBCC PAGE(1,1,141458,3) — root page giving pointers to next 2 intermediate page which is inturn giving pointers to another pages
156 intermediate pages(Level 1) + 2 intermediate page (Level 1)+ 1 root page
— Let us observe the changes in the Fragmentation after rebuilding the index
ALTER INDEX test_idx ON TEST REBUILD
— The depth of the index is reduced to 3 and Fragmentation on the index is almost reduced to 0
index_type_desc index_depth index_level avg_fragmentation_in_percent fragment_count avg_fragment_size_in_pages page_count
—————- ———– ———– —————————- ——————– ————————– ———–
CLUSTERED INDEX 3 0 0.01 1477 75.77048070413 111913
–ROOT PAGE IS NOW CHANGED again to a new value and resides at Level 2 while there are
DBCC PAGE(1,1,156138 ,3)
277 intermediate pages (Level 1) + 1 root pages
Hope this clarifies how Fragmentation occurs in sql server!!!
Regards
Parikshit