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

Similar Posts

Leave a Reply

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