How It Works: Online Index Rebuild - Can Cause Increased Fragmentation

SQL Server Books Online alludes to the fragmentation possibility but does not fully explain that the Online Index rebuilding may increase fragmentation when it is allowed to run with MAX DOP > 1 and ALLOW_PAGE_LOCKS = OFF directives .

The process of building an online index involves maintaining the active connection activity with that of the online building operation(s).   This is done by updating data modification plans to maintain both indexes during the online index building.

There are a few objectives an index rebuild can accomplish:

  • Generate new statistics
  • Change the number of pages used by the index (fill factor)
  • Reorganize the data on database pages in relative proximity to each other

ALTER INDEX MAXDOP Option

The MAXDOP option caps the number of workers which can participate in the alter action.  For example the following tells SQL Server to use no more than 8 workers during the alter index operation.  You can't force the maxdop it is only a suggested cap directive.

Alter Index all On test2 Rebuild With (Online = On, maxdop = 8)

 

MAXDOP = 1 (Serial)

The following FIGURE depicts a serialized alter index operation.   The new rowset maintains an allocation cache that is used when allocating the new pages to move data onto.   When the cache is empty 1 or more extents are allocated, as close to the last extent allocated as possible. 

 

image

This process allows the data to be packed onto pages near each other.  Reducing the number of pages, if the fill factor so indicates, and placing the rows in sorted order near one another.

MAXDOP > 1 (Parallel) using ALLOW_PAGE_LOCKS = OFF

When running in parallel a decision is made as to how the allocation cache will be utilized.  In the case of ALLOW_PAGE_LOCKS = OFF the logic is to share a single allocation cache. 

Take special note: The logic can use statistical operations to divide the workload among the workers.

image

 

This can lead to a leap frog style of allocation and increase fragmentation.   The pages of the index may be very contiguous allocations … 100, 101, 102, 103, … but the data on the pages is 100 (from 1st partition), 101 (from 2nd partition), 102 (1st partition) so when scanning the IAM in page order the page fragmentation level can climb.

image

Actions such as the fill factor adjustments and statistics gathering process as expected.

MAXDOP > 1 (Parallel) using ALLOW_PAGE_LOCKS = ON (Default is ON for ALTER INDEX COMMAND)

When ALTER INDEX is able to use page or table (rowset level) locking the allocation patterns are optimized for bulk operations.  Without attempting to write a novel about how this works I have drawn a very high level picture in the figure shown below.

 

image

 

When bulk operations are enabled, an additional caching layer is instituted for each of the workers to use.   The Bulk Allocation Cache is sized based on the work load expected for the given partition, etc...   This allows each partition to allocate 1 or more extents at a time and then use those pages to store the data they are processing.   This provides a critical level of separation necessary to reduce the leap frogging effect and reduces fragmentation by at least a factor of 8 pages per extent.

Note: The fragmentation level will not be reduced as much as a MAXDOP=1 alteration, but it can reduce the fragmentation within percentage points of MAXDOP=1 in many instances.

Recap

  • MAXDOP is a key factor for determining the amount of work each worker is targeted to perform.
  • The type of allocation caching used determines the possible fragmentation impact
  • None of these options controls the fill factor maintenance
  • None of these options controls the statistics gathering

Bob Dorr - Principal SQL Server Escalation Engineer