1.SQL Server - Index Fragmentation - Understanding Fragmentation

1.SQL Server - Index Fragmentation - Understanding Fragmentation

2.SQL Server: Measuring The Index Fragmentation

When I had a discussion with couple of my friends about index fragmentation, I realized that they have different understanding about index fragmentation. In this post I will try my level best to explain different types of fragmentation.Understanding the concept of index fragmentation is important  for detecting and removing fragmentation efficiently.

What is Fragmentation

Fragmentation can be defined as any condition that cause more than optimal amount of disk I/O to be performed in accessing a table or cause the longer  disk I/O. Optimal performance of SELECT queries occurs when the data pages of tables are contiguous  as possible and pages are fully packed as possible.Fragmentation breaks this rule and reduce the performance of the queries. Fragmentation can happen in two level . One is file system level fragmentation which is called as Logical/Physical Disk Fragmentation and Index level fragmentation. Each of them are described in the below sections.

Logical/Physical  Disk Fragmentation

Logical fragmentation is the fragmentation of database file in the file system itself like any other files.This occurs when the file system is not able allocate contiguous space for database file.As a result, disk head has to move back and forth to read from the database files. SQL server is completely unaware about this kind of fragmentation and it is not possible to measure the logical disk fragmentation using any script. Logical disk fragmentation can happen due to various reason like

• Placing  database file in the same disk where other files( like OS files and other application files)are kept.
• Frequent growth of the database file in smaller chunks.

To remove logical fragmentation we can use the windows fragmentation tool but note that we need to stop the SQL server while running the defragmentation tools.Otherwise the defragmentation tool will skip database file as it is used by the SQL server. 

The best ways to to avoid the logical fragmentation are :

• Keep the database files in a separate disk isolated from other application files and log files.
• While creating new database,estimate the size of database file and allocate enough space to avoid the frequent growth of data files.
• Specify the database growth option to allocate larger chunks rather than small chunks frequently.

Index Level Fragmentation

Index level fragmentation comes in two flavors : Internal Fragmentation and External Fragmentation. If Index level fragmentation is high ,it may prevents optimizer from using the available indexes in optimal way.

Internal Fragmentation

Internal fragmentation is measured in average page fullness of the index(Page density). A page that is 100% full has no internal fragmentation.In other words, internal fragmentation occur when there is empty space in the index page and this can happen due to insert/update/delete DML operation.Every index page can hold a certain number of records based on the size of the index, but that does not guaranteed that the page always hold maximum number records.  Internal fragmentation is normally reported as a percentage of fullness in bytes, not in records. An index page that has internal fragmentation 90% may be full in terms of record. The remaining 10% bytes of the pages may not be enough to hold one more record. In a 8KB  pages,  maximum of  8060 bytes can be used by data.Rest of space are used by page header and row offset array.Let us assume that we have index with fixed size of 100 bytes and the index has 800 entries. So we can can store 8060/100= 80 records per page by leaving 60 bytes empty as it is not enough to hold one more records and this index requires 10 pages to store the entire index structure.If you calculate the average fullness of this index, in ideal scenario it will come as 99.26%. Let us see how it will look like in Fig 1.

Fig 1

Let us assume that we are deleting the half of the entries randomly of this table which reduce the total number of entries in this index to 400.Now the pages will look like as given  in Fig 2 with total of 40600 bytes free space across 10 pages. If you calculate the the average fullness as Total data size*100/Total page size = 4000*100/80600= 49.62% . It clearly says that, half of the spaces are empty and the index has internal fragmentation. 

Fig 2

How Internal Fragmentation will affect the performance of the SQL server ?

1. Internal Fragmentation will increase the I/O. When you run queries that scan part or complete table/index, if you have internal fragmentation on that table/index, it causes additional page reads. In our example, the entire data can be stored in 5 pages. When the query needs to do index scan it has to read 10 pages instead of 5 pages. Which means 50% more I/O.
2. Internal Fragmentation reduce the efficiency of buffer cache.When indexes has internal fragmentation, it need more space to fit in the buffer.In our case this single index will use 5 additional pages to fit into the buffer which should have used to store other index pages. This will reduce the cache hit ratio.  In turn  it will increase the physical I/O. It also increase the logical reads.
3. This also increase the size of the database file. It need more disk space to store the additional pages and reduce the performance of Backup and Restore.

External Fragmentation

External Fragmentation happens when the logical order of the pages does not match the physical order of the pages. External fragmentation refers to the lack of correlation between the logical sequence of an index and its physical sequence. It is  measured as the percentage of out-of-order pages in the leaf pages of an index. An out-of-order page is a page for which the next physical page allocated to the index is not the page pointed to by the next-page pointer in the current leaf page.Let us see the Fig 3 below. It is representation of index with three pages.Data is stored in sequential page. In other terms logical order and physical order are same and it store the index keys from 1 to 16 a. All pages are completely full except the Page 3

Fig 3

Let us see what will happen if we insert the value 4 to the underlying table in the Fig 4.

Fig 4

While inserting the value 4 into the table it has to place in the Page 1 between value 3 and 5 but unfortunately Page 1 does not have any free space to occupy one more record. The only option is perform a page split by dividing the Page 1 evenly by leaving half of the data in Page 1 and moving half of the data to new  page (Page 4). From Fig 4 we can understand that the logical order of the Page 4 is not matching with the physical order. External Fragmentation can happen due to various reasons:

1. While allocating pages for new table , SQL server allocate pages from mixed extend till it reaches the 8 pages. There is possibility of having the first 8 pages from 8 different extents. 
2. When all records are deleted from a page, the page will be de-allocated from the index(The de-allocation  of pages will not happen immediately) which create gap and increase the fragmentation.
3. Once object reached 8 pages size, SQL server will start allocating uniform extent to the objects.While allocation uniform extent to an index, next sequential extent to the current extent might be already allocated to other objects/indexes.

How External Fragmentation will affect the performance of the SQL server ?

While reading individual rows, external fragmentation will not affect the performance as it directly go to the page and fetch the data.Unordered scans also will not affected by the external fragmentation as it use the IAM pages to find which extents need to be fetched. In the case of ordered index scan ,external fragmentation might become a degrading factor for performance. The degradation of the performance is because the disk drive's heads have to jump around on the physical disk, rather than performing just contiguous read operations.Also note that external fragmentation will not affect the performance once the pages are loaded into the buffer pool.

SQL Server: Measuring The Index Fragmentation

In my earlier , I have explained about the different types of fragmentation and how it will affect the query performance. In this post we will discuss about measuring the index fragmentation.

Measuring Internal Fragmentation 

Internal fragmentation  is all about the fullness of the page and it is measured using the        sys.dm_db_index_physical_stats function with DETAILED mode. The avg_page_space_used_in_percent column in the output gives the internal fragmentation of the index. Below query list all the indexes which have more than 10 pages and page fullness is less than 85 percent.



EXEC sp_configure 'show advanced options',1 GO RECONFIGURE WITH OVERRIDE GO DECLARE @DefaultFillFactor INT DECLARE @Fillfactor TABLE(Name VARCHAR(100),Minimum INT ,Maximum INT,config_value INT ,run_value INT) INSERT INTO @Fillfactor EXEC sp_configure 'fill factor (%)'      SELECT @DefaultFillFactor  = CASE WHEN run_value=0 THEN 100 ELSE  run_value  END  FROM @Fillfactor  SELECTDB_NAME() AS DBname,QUOTENAME(s.name) AS CchemaName,QUOTENAME(o.name) AS TableName,i.name AS IndexName,stats.Index_type_desc AS IndexType,stats.page_count AS [PageCount],stats.partition_number AS PartitionNumber,CASE WHEN i.fill_factor>0 THEN i.fill_factor ELSE @DefaultFillFactor END  AS [Fill Factor],   stats.avg_page_space_used_in_percent,   CASE WHEN stats.index_level =0 THEN 'Leaf Level' ELSE 'Nonleaf Level' END AS IndexLevelFROM         sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL , NULL, 'DETAILED') AS stats,         sys.objects AS o,         sys.schemas AS s,         sys.indexes AS iWHERE         o.OBJECT_ID = stats.OBJECT_ID AND s.schema_id = o.schema_id       AND     i.OBJECT_ID = stats.OBJECT_ID ANDi.index_id = stats.index_idAND     stats.avg_page_space_used_in_percent<= 85 AND stats.page_count >= 10 AND        stats.index_id > 0 ORDER BY  stats.avg_page_space_used_in_percent ASC, stats.page_count DESC

I have used the where condition to fetch  only the indexes which  have more than 10 pages  and page fullness is less than 85 percentage. This is  based on   my environment and some best practices documentations.Low values for avg_page_space_used_in_percent and higher  value for PageCount together will affect the performance of the system. The value of avg_page_space_used_in_percent will be  low due to various reasons

• Due to Page split and deleting records: In this scenario we have to REBUILD or REORGANIZE  the indexes. If the fragmentation is reported in the non leaf level , REBUILD is required to reduce the fragmentation.
• Due to fill factor setting : A wrong setting  of fill factor value of the index might cause the internal fragmentation.If the internal fragmentation is due the fill factor setting, we have to REBUILD the index with new fill factor value.
• Due to record size : Some time size of the record might account for internal fragmentation. For example let us assume that size of one record is 3000 bytes and page can hold only two record. The third record can not be fitted into a page as the remaining free space in the page is less than 3000 bytes. In this scenario each page will have empty space of 2060 bytes. To get rid of the fragmentation due to the size of the record , we might need to redesign the table or has to do a vertical partitioning of the table.

Measuring External Fragmentation 

External fragmentation also measured using the sys.dm_db_index_physical_stats function with LIMITED mode ,but we will be using the avg_fragmentation_in_percent from the result to measure the external fragmentation. With LIMITED mode it will give the fragmentation of the leaf level. To get the fragmentation of non leaf level, it  should be executed  with DETAILED or SAMPLE mode. A fragment is a continuous allocation of pages.For example if an index has 150 pages and pages are allocated from 1 to 50, 55 to 60 ,65 to 120 and 140 to 180.Each of these sequences are called as fragment and we can say that this index has four fragment.




EXEC sp_configure 'show advanced options',1 GO RECONFIGURE WITH OVERRIDE G ODECLARE @DefaultFillFactor INT DECLARE @Fillfactor TABLE(Name VARCHAR(100),Minimum INT ,Maximum INT,config_value INT ,run_value INT) INSERT INTO @Fillfactor EXEC sp_configure 'fill factor (%)'      SELECT @DefaultFillFactor  = CASE WHEN run_value=0 THEN 100 ELSE  run_value END  FROM @Fillfactor  SELECTDB_NAME() AS DBname,QUOTENAME(s.name) AS CchemaName,QUOTENAME(o.name) AS TableName,i.name AS IndexName,stats.Index_type_desc AS IndexType,stats.page_count AS [PageCount],stats.partition_number AS PartitionNumber,CASE WHEN i.fill_factor>0 THEN i.fill_factor ELSE @DefaultFillFactor END  AS [Fill Factor],   stats.avg_fragmentation_in_percent,stats.fragment_count,   CASE WHEN stats.index_level =0 THEN 'Leaf Level' ELSE 'Nonleaf Level' END AS IndexLevelFROM         sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL , NULL, 'LIMITED') AS stats,         sys.objects AS o,         sys.schemas AS s,         sys.indexes AS iWHERE         o.OBJECT_ID = stats.OBJECT_ID AND s.schema_id = o.schema_id       AND     i.OBJECT_ID = stats.OBJECT_ID ANDi.index_id = stats.index_idAND     stats.avg_fragmentation_in_percent>= 20 AND stats.page_count >= 1000ORDER BY  stats.avg_fragmentation_in_percent DESC,stats.page_count DESC




In this query ,  I have used a where condition to fetch indexes which have fragmentation  greater than 20 percent and have minimum of 1000 pages.  

avg_fragmentation_in_percent can have higher value due to various reasons :

• SQL server storage engine allocates pages from mixed extent to a table or index till the page count reaches eight.Once the page count reaches to eight SQL server storage engine starts assigning full uniform extents to the index. So there is a possibility of having higher fragmentation for small table and rebuilding indexes might increase the fragmentation.For example, let us assume that an index has 7 pages and these pages are allocated from two mixed extent, while rebuilding the index there is possibility of allocating pages from more than 2 extents and maximum of seven extents which in turn increase the fragmentation. 
• Even the pages are allocated from uniform extent , there is possibility of fragmentation. When the size of index grow , it need more pages in the non leaf level also.If last page allocated to leaf level is 250 and to accommodate more row in the leaf lever index structure might need a page in index level 1, then SQL server storage engine allocate page 251 to the index level 1 which create fragment in the leaf level.
• Other common reason  is the page split  due to the DML operations . This I have explained well in my previous post.Rebuild/Reorganize  index may not be effective to fix fragmentation happened due to the fist two reason, but it can reduce the fragmentation caused by the page split or delete operation. 
• In our environment we follow the index maintenance  as given below:
• 20 to 40 percentage of fragmentation is handled with reorganizing the index.
• All index which has more 40 percentage fragmentation will considered for rebuild
• Index which has less than 1000 pages will be ignored by the index maintenance logic.
• Index which has more than 50K pages and fragmentation between 10 and 20 will also be considered for Reorganize.