How It Works: MAX DOP Level and Parallel Index Builds

Published Jan 15 2019 04:27 PM 251 Views
Microsoft
First published on MSDN on Mar 02, 2015

I have been working on an issue where rebuilding an index leads to additional fragmentation.   Using XEvents I debugged the page allocations and writes and was able to narrow in on the behavior.

There are lots of factors to take into account when rebuilding the index. I was able to break down the behavior to the worst possible case using a single file database, single heap table,  SORT IN TEMPDB and packing of the heap data to the beginning of the database file when create clustered index is issued.

When the index is build a portion of the data (range) is assigned to each of the parallel workers.  The diagram below shows a MAX DOP = 2 scenario.

Each parallel worker is assigned its own CBulkAllocator when saving the final index pages.   This means Worker 1 gets an extent and starts to fill pages from TEMPDB for Worker 1’s given key range.   Worker 2 is executing in parallel and has its own CBulkAllocator.  Worker 2 acquires the next extent and starts to spool the assigned key range.

Looking at the database a leap frog behavior of values, across extents occurs as the workers copy the final keys into place.

The diagram below shows the leap frog behavior from a MAX DOP = 4 index creation.   The saw tooth line represents the offsets in the file as read during an index order scan.  The horizontal access is the event sequence and the vertical access is the offset in the database file.  As you can see the leap frog behavior places key values all over the file.

Key 1 is at a low offset but Key 2 is at an offset higher than Key 9 as shown in the example above.  Each of the workers spreads 1/4th of the data across the entire file instead of packing the key values together in a specific segment of the file.

In comparison the a serial index build shows the desired layout across the drive.   Smaller offsets have the 1st set of keys and larger offsets always have higher key values.

This mattered to my customer because after a parallel index build an index ordered scan takes longer than a serial index build.  The chart below shows the difference in read size and IOPS requirements.

sele ct count_big(*) from tblTest (NOLOCK)

Serial Built

Parallel Built

Avg Read Size

508K

160K

Duration

00:01:20

00:01:50

# Reads

15,000

52,000

SQL Server reads up to 512K in a chuck for read ahead behavior.   When doing an index order scan we read the necessary extents to cover the key range.  Since the key range is leap frogged, during the parallel build, the fragmentation limits SQL Server’s I/O size to 160K instead of 508K and drives the number of I/O requests much higher.  The same data in a serial built index maximizes the read ahead capabilities of SQL Server.

The testing above was conducted using: select count_big(*) from tblTest with (NOLOCK)

Hint: You don’t have to rebuild the index in serial to determine how much a performance gain it may provide.   Using WITH(NOLOCK, INDEX=0) forces an allocation order scan, ignoring the key placement and scanning the object from first IAM to last IAM order.  Leveraging the statistics I/O, XEvents and virtual file statistics output you are able to determine the behaviors.

Workarounds
The obvious question is that a serial index rebuild can take a long time so what should I do to leverage parallel index builds and reduce the fragmentation possibilities?

1. Partition the table on separate files matching the DOP you are using to build the index.  This allows better alignment of parallel workers to specific partitions, avoiding the leap frog behavior.

2. For a non-partitioned table aligning the number of files with the DOP may be helpful.   With reasonably even distribution of free space in each file the allocation behavior is such that alike keys will be placed near each other.

3. For single partition rebuild operations consider serial index building behaviors to minimize fragmentation behaviors.

Future
I am working with the development team to evaluate the CBulkAllocator behavior.   Testing is needed but it could be that the CBulkAllocator attempts to acquire 9 (64K) extents to align with the read ahead (512K) chunk size.   Something like this idea could reduce the fragmentation by a factor of 8.

Bob Dorr - Principal SQL Server Escalation Engineer

%3CLINGO-SUB%20id%3D%22lingo-sub-318517%22%20slang%3D%22en-US%22%3EHow%20It%20Works%3A%20MAX%20DOP%20Level%20and%20Parallel%20Index%20Builds%3C%2FLINGO-SUB%3E%3CLINGO-BODY%20id%3D%22lingo-body-318517%22%20slang%3D%22en-US%22%3E%0A%20%26lt%3Bmeta%20http-equiv%3D%22Content-Type%22%20content%3D%22text%2Fhtml%3B%20charset%3DUTF-8%22%20%2F%26gt%3B%3CSTRONG%3E%20First%20published%20on%20MSDN%20on%20Mar%2002%2C%202015%20%3C%2FSTRONG%3E%20%3CBR%20%2F%3E%3CP%3EI%20have%20been%20working%20on%20an%20issue%20where%20rebuilding%20an%20index%20leads%20to%20additional%20fragmentation.%26nbsp%3B%26nbsp%3B%20Using%20XEvents%20I%20debugged%20the%20page%20allocations%20and%20writes%20and%20was%20able%20to%20narrow%20in%20on%20the%20behavior.%3C%2FP%3E%0A%20%20%3CP%3E%3CSTRONG%3E%20There%20are%20lots%20of%20factors%20to%20take%20into%20account%20when%20rebuilding%20the%20index.%20%3C%2FSTRONG%3E%20I%20was%20able%20to%20break%20down%20the%20behavior%20to%20the%20worst%20possible%20case%20using%20a%20single%20file%20database%2C%20single%20heap%20table%2C%26nbsp%3B%20SORT%20IN%20TEMPDB%20and%20packing%20of%20the%20heap%20data%20to%20the%20beginning%20of%20the%20database%20file%20when%20create%20clustered%20index%20is%20issued.%3C%2FP%3E%0A%20%20%3CP%3EWhen%20the%20index%20is%20build%20a%20portion%20of%20the%20data%20(range)%20is%20assigned%20to%20each%20of%20the%20parallel%20workers.%26nbsp%3B%20The%20diagram%20below%20shows%20a%20MAX%20DOP%20%3D%202%20scenario.%3C%2FP%3E%0A%20%20%3CP%3E%3CIMG%20src%3D%22https%3A%2F%2Ftechcommunity.microsoft.com%2Ft5%2Fimage%2Fserverpage%2Fimage-id%2F68273iCD71B2D9AD525B76%22%20%2F%3E%20Each%20parallel%20worker%20is%20assigned%20its%20own%20CBulkAllocator%20when%20saving%20the%20final%20index%20pages.%26nbsp%3B%26nbsp%3B%20This%20means%20Worker%201%20gets%20an%20extent%20and%20starts%20to%20fill%20pages%20from%20TEMPDB%20for%20Worker%201%E2%80%99s%20given%20key%20range.%26nbsp%3B%26nbsp%3B%20Worker%202%20is%20executing%20in%20parallel%20and%20has%20its%20own%20CBulkAllocator.%26nbsp%3B%20Worker%202%20acquires%20the%20next%20extent%20and%20starts%20to%20spool%20the%20assigned%20key%20range.%3C%2FP%3E%0A%20%20%3CP%3ELooking%20at%20the%20database%20a%20leap%20frog%20behavior%20of%20values%2C%20across%20extents%20occurs%20as%20the%20workers%20copy%20the%20final%20keys%20into%20place.%3C%2FP%3E%0A%20%20%3CP%3EThe%20diagram%20below%20shows%20the%20leap%20frog%20behavior%20from%20a%20MAX%20DOP%20%3D%204%20index%20creation.%26nbsp%3B%26nbsp%3B%20The%20saw%20tooth%20line%20represents%20the%20offsets%20in%20the%20file%20as%20read%20during%20an%20index%20order%20scan.%26nbsp%3B%20The%20horizontal%20access%20is%20the%20event%20sequence%20and%20the%20vertical%20access%20is%20the%20offset%20in%20the%20database%20file.%26nbsp%3B%20As%20you%20can%20see%20the%20leap%20frog%20behavior%20places%20key%20values%20all%20over%20the%20file.%3C%2FP%3E%0A%20%20%3CP%3EKey%201%20is%20at%20a%20low%20offset%20but%20Key%202%20is%20at%20an%20offset%20higher%20than%20Key%209%20as%20shown%20in%20the%20example%20above.%26nbsp%3B%20Each%20of%20the%20workers%20spreads%201%2F4th%20of%20the%20data%20across%20the%20entire%20file%20instead%20of%20packing%20the%20key%20values%20together%20in%20a%20specific%20segment%20of%20the%20file.%3C%2FP%3E%0A%20%20%3CP%3E%3CIMG%20src%3D%22https%3A%2F%2Ftechcommunity.microsoft.com%2Ft5%2Fimage%2Fserverpage%2Fimage-id%2F68274i505E0696B644ABE6%22%20%2F%3E%3C%2FP%3E%0A%20%20%3CP%3EIn%20comparison%20the%20a%20serial%20index%20build%20shows%20the%20desired%20layout%20across%20the%20drive.%26nbsp%3B%26nbsp%3B%20Smaller%20offsets%20have%20the%201st%20set%20of%20keys%20and%20larger%20offsets%20always%20have%20higher%20key%20values.%3C%2FP%3E%0A%20%20%3CP%3E%3CIMG%20src%3D%22https%3A%2F%2Ftechcommunity.microsoft.com%2Ft5%2Fimage%2Fserverpage%2Fimage-id%2F68275i23590D11458B0A29%22%20%2F%3E%3C%2FP%3E%0A%20%20%3CP%3EThis%20mattered%20to%20my%20customer%20because%20after%20a%20parallel%20index%20build%20an%20index%20ordered%20scan%20takes%20longer%20than%20a%20serial%20index%20build.%26nbsp%3B%20The%20chart%20below%20shows%20the%20difference%20in%20read%20size%20and%20IOPS%20requirements.%3C%2FP%3E%0A%20%20%3CP%3Esele%20%3CEM%3E%20ct%20count_big(*)%20from%20tblTest%20(NOLOCK)%3C%2FEM%3E%3C%2FP%3E%0A%20%20%3CP%3E%3C%2FP%3E%0A%20%20%3CTABLE%3E%0A%20%20%20%3CTBODY%3E%3CTR%3E%0A%20%20%20%20%3CTD%3E%3CP%3E%3CB%3E%20%3C%2FB%3E%3C%2FP%3E%0A%20%20%20%20%3C%2FTD%3E%0A%20%20%20%20%3CTD%3E%3CP%3E%3CB%3E%20Serial%20Built%20%3C%2FB%3E%3C%2FP%3E%0A%20%20%20%20%3C%2FTD%3E%0A%20%20%20%20%3CTD%3E%3CP%3E%3CB%3E%20Parallel%20Built%20%3C%2FB%3E%3C%2FP%3E%0A%20%20%20%20%3C%2FTD%3E%0A%20%20%20%3C%2FTR%3E%0A%20%20%20%3CTR%3E%0A%20%20%20%20%3CTD%3E%3CP%3E%3CB%3E%20Avg%20Read%20Size%20%3C%2FB%3E%3C%2FP%3E%0A%20%20%20%20%3C%2FTD%3E%0A%20%20%20%20%3CTD%3E%3CP%3E%3CB%3E%20508K%20%3C%2FB%3E%3C%2FP%3E%0A%20%20%20%20%3C%2FTD%3E%0A%20%20%20%20%3CTD%3E%3CP%3E%3CB%3E%20160K%20%3C%2FB%3E%3C%2FP%3E%0A%20%20%20%20%3C%2FTD%3E%0A%20%20%20%3C%2FTR%3E%0A%20%20%20%3CTR%3E%0A%20%20%20%20%3CTD%3E%3CP%3E%3CB%3E%20Duration%20%3C%2FB%3E%3C%2FP%3E%0A%20%20%20%20%3C%2FTD%3E%0A%20%20%20%20%3CTD%3E%3CP%3E00%3A01%3A20%3C%2FP%3E%0A%20%20%20%20%3C%2FTD%3E%0A%20%20%20%20%3CTD%3E%3CP%3E00%3A01%3A50%3C%2FP%3E%0A%20%20%20%20%3C%2FTD%3E%0A%20%20%20%3C%2FTR%3E%0A%20%20%20%3CTR%3E%0A%20%20%20%20%3CTD%3E%3CP%3E%3CB%3E%20%23%20Reads%20%3C%2FB%3E%3C%2FP%3E%0A%20%20%20%20%3C%2FTD%3E%0A%20%20%20%20%3CTD%3E%3CP%3E%3CB%3E%2015%2C000%20%3C%2FB%3E%3C%2FP%3E%0A%20%20%20%20%3C%2FTD%3E%0A%20%20%20%20%3CTD%3E%3CP%3E%3CB%3E%2052%2C000%20%3C%2FB%3E%3C%2FP%3E%0A%20%20%20%20%3C%2FTD%3E%0A%20%20%20%3C%2FTR%3E%0A%20%20%3C%2FTBODY%3E%3C%2FTABLE%3E%0A%20%20%3CP%3E%3C%2FP%3E%0A%20%20%3CP%3ESQL%20Server%20reads%20up%20to%20512K%20in%20a%20chuck%20for%20read%20ahead%20behavior.%26nbsp%3B%26nbsp%3B%20When%20doing%20an%20index%20order%20scan%20we%20read%20the%20necessary%20extents%20to%20cover%20the%20key%20range.%26nbsp%3B%20Since%20the%20key%20range%20is%20leap%20frogged%2C%20during%20the%20parallel%20build%2C%20the%20fragmentation%20limits%20SQL%20Server%E2%80%99s%20I%2FO%20size%20to%20160K%20instead%20of%20508K%20and%20drives%20the%20number%20of%20I%2FO%20requests%20much%20higher.%26nbsp%3B%20The%20same%20data%20in%20a%20serial%20built%20index%20maximizes%20the%20read%20ahead%20capabilities%20of%20SQL%20Server.%3C%2FP%3E%0A%20%20%3CP%3EThe%20testing%20above%20was%20conducted%20using%3A%20%3CEM%3E%20select%20count_big(*)%20from%20tblTest%20with%20(NOLOCK)%3C%2FEM%3E%3C%2FP%3E%0A%20%20%3CP%3E%3CSTRONG%3EHint%3A%20%3C%2FSTRONG%3E%20You%20don%E2%80%99t%20have%20to%20rebuild%20the%20index%20in%20serial%20to%20determine%20how%20much%20a%20performance%20gain%20it%20may%20provide.%26nbsp%3B%26nbsp%3B%20Using%20WITH(NOLOCK%2C%20INDEX%3D0)%20forces%20an%20allocation%20order%20scan%2C%20ignoring%20the%20key%20placement%20and%20scanning%20the%20object%20from%20first%20IAM%20to%20last%20IAM%20order.%26nbsp%3B%20Leveraging%20the%20statistics%20I%2FO%2C%20XEvents%20and%20virtual%20file%20statistics%20output%20you%20are%20able%20to%20determine%20the%20behaviors.%3C%2FP%3E%0A%20%20%3CP%3E%3CSTRONG%3EWorkarounds%20%3CBR%20%2F%3E%20%3C%2FSTRONG%3E%20The%20obvious%20question%20is%20that%20a%20serial%20index%20rebuild%20can%20take%20a%20long%20time%20so%20what%20should%20I%20do%20to%20leverage%20parallel%20index%20builds%20and%20reduce%20the%20fragmentation%20possibilities%3F%3C%2FP%3E%0A%20%20%3CP%3E%3CSTRONG%3E%201.%20%3C%2FSTRONG%3E%20Partition%20the%20table%20on%20separate%20files%20matching%20the%20DOP%20you%20are%20using%20to%20build%20the%20index.%26nbsp%3B%20This%20allows%20better%20alignment%20of%20parallel%20workers%20to%20specific%20partitions%2C%20avoiding%20the%20leap%20frog%20behavior.%20%3CBR%20%2F%3E%20%3CBR%20%2F%3E%20%3CSTRONG%3E%202.%20%3C%2FSTRONG%3E%20For%20a%20non-partitioned%20table%20aligning%20the%20number%20of%20files%20with%20the%20DOP%20may%20be%20helpful.%26nbsp%3B%26nbsp%3B%20With%20reasonably%20even%20distribution%20of%20free%20space%20in%20each%20file%20the%20allocation%20behavior%20is%20such%20that%20alike%20keys%20will%20be%20placed%20near%20each%20other.%3C%2FP%3E%0A%20%20%3CP%3E%3CSTRONG%3E%203.%20%3C%2FSTRONG%3E%20For%20single%20partition%20rebuild%20operations%20consider%20serial%20index%20building%20behaviors%20to%20minimize%20fragmentation%20behaviors.%3C%2FP%3E%0A%20%20%3CP%3E%3CSTRONG%3EFuture%20%3CBR%20%2F%3E%20%3C%2FSTRONG%3E%20I%20am%20working%20with%20the%20development%20team%20to%20evaluate%20the%20CBulkAllocator%20behavior.%26nbsp%3B%26nbsp%3B%20Testing%20is%20needed%20but%20it%20could%20be%20that%20the%20CBulkAllocator%20attempts%20to%20acquire%209%20(64K)%20extents%20to%20align%20with%20the%20read%20ahead%20(512K)%20chunk%20size.%26nbsp%3B%26nbsp%3B%20Something%20like%20this%20idea%20could%20reduce%20the%20fragmentation%20by%20a%20factor%20of%208.%3C%2FP%3E%0A%20%20%3CP%3EBob%20Dorr%20-%20Principal%20SQL%20Server%20Escalation%20Engineer%3C%2FP%3E%0A%20%0A%3C%2FLINGO-BODY%3E%3CLINGO-TEASER%20id%3D%22lingo-teaser-318517%22%20slang%3D%22en-US%22%3EFirst%20published%20on%20MSDN%20on%20Mar%2002%2C%202015%20I%20have%20been%20working%20on%20an%20issue%20where%20rebuilding%20an%20index%20leads%20to%20additional%20fragmentation.%3C%2FLINGO-TEASER%3E%3CLINGO-LABS%20id%3D%22lingo-labs-318517%22%20slang%3D%22en-US%22%3E%3CLINGO-LABEL%3EPerformance%3C%2FLINGO-LABEL%3E%3CLINGO-LABEL%3ESQL%20OS%3C%2FLINGO-LABEL%3E%3C%2FLINGO-LABS%3E
Version history
Last update:
‎Jan 15 2019 04:27 PM
Updated by: