Sunday, June 24, 2007 5:29 PM tonyrogerson

Row fragmentation (Hopscotch) - Heap v Clustered and IO cost

Thankfully in my travels I see less and less heaps (a table without a clustered index), frankly they should be banned, taken out of the engine and a clustered index made mandatory. In this post I look at row hopscotch (row fragmentation) and the effects it has on application performance (IO’s and concurrency), you also see stark evidence at just why you should always have a clustered index.

A database is made up of a series of 8KB pages; a group of 8 pages is called an extent.

A heap is a table without a clustered index, the data is inserted anywhere in the page chain, so if you are deleting rows, those free ‘slots’ can be reused (this is where row hopscotch occurs).

A table with a clustered index has its data stored in the order of the clustering key so any inserts are placed in order, any page free space from deletes can only be used if the inserted row clustering key values fit within the range of values already on the page, for instance, if the page contains the rows 1, 2, 3, [FREE SLOT], 5, 6 and there is only room for 1 row then you can insert the id 4 but not 7, 8.

Let’s look at some SQL, first the HEAP...

create table somedata (

    id  int not null identity primary key nonclustered,

    somestuff   char(250)   not null

)

go

Notice that we have a primary key that is nonclustered, this puts a nonclustered index on the table to enforce the uniqueness.

Let’s populate the table, note the @i % 5 simply yields true on every 5th row inserted into the table, I’m doing a random delete to force some free space somewhere in the table allocation.

set nocount on

declare @i int

set @i = 1

 

while @i <= 40000

begin

    if @i % 5 = 0

        delete somedata

        where id = ( select top 1 id

                     from somedata

                     order by newid() )

 

    insert somedata ( somestuff ) values ( '>>>>>' + cast( @i as varchar(10) ) + '<<<<<' )

 

    set @i = @i + 1

 

end

go

 

Let’s try our query, this causes a ‘Table Scan’ because we are doing the DISTINCT somestuff and the number of rows we are doing it against SQL Server decided it is cheaper to Table Scan rather than a seek and look up.

set statistics io on

 

select count( distinct somestuff )

from somedata

where id between 1 and 10000

 

set statistics io off

go

This yields the following IO stats...

Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'somedata'. Scan count 1, logical reads 1146, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

We can use the index to see how expensive that is too...

select max( somestuff )

from somedata

where id between 1 and 500


Table
'somedata'. Scan count 1, logical reads 142, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

 

At this point, we should take a look at a page of data to find out what the on-disk storage of rows looks like, we do this using the DBCC EXTENTINFO command and pick out the first non-mixed extent.

dbcc extentinfo( 0 )

Run down the output looking for your object (object_id( ‘somedata’) ), you want the first entry where pg_alloc = 8 and index_id = 0, make a note of the page_id and then view that page by using DBCC PAGE...

dbcc traceon( 3604 )

dbcc page( {your db name}, 1, {page_id}, 3 )


You will get a rather large output, what you are really interested in is the slots, I’ve reduced the output to make it readable, you’ll see something like this...

Slot 0 Column 0 Offset 0x4 Length 4

id = 278                            

 

Slot 1 Column 0 Offset 0x4 Length 4

id = 11556                           

 

Slot 3 Column 0 Offset 0x4 Length 4

id = 281                            

 

Slot 4 Column 0 Offset 0x4 Length 4

id = 23562                          

 

Slot 5 Column 0 Offset 0x4 Length 4

id = 38845                          

 

Slot 6 Column 0 Offset 0x4 Length 4

id = 284                            

 

Slot 7 Column 0 Offset 0x4 Length 4

id = 285                            

 

Slot 8 Column 0 Offset 0x4 Length 4

id = 24888                          


Note, ‘id’ is your data and is the id we inserted (in order!) - you can see the row hopscotch here, the high id rows you see are because we deleted rows for instance 282 and 283 and SQL Server has re-used these slots on the page for other rows being inserted. Now, take a moment and visualise this across our 32,000 row table; for the heap the rows are literally anywhere so if you do a query like BETWEEN 100 and 1000 then literally the rows at worse case could be located on every single allocated page to the table. Also, this is why SQL Server often chooses not to use an index for looking up, because seek op is fine – it’s just the secondary lookup back to the data that costs the resource.

I suppose one last thing to look at and its where the heap approach does benefit, it provides better space utilisation (that said, there is a major bug to do with open objects and how new extents get allocated that has caused a lot of hassle and performance degradation for my clients with a particular third party database, but I won’t mention it’s Sage).

This is the output from DBCC SHOWCONTIG...

- Pages Scanned................................: 1147

- Extents Scanned..............................: 147

- Extent Switches..............................: 146

- Avg. Pages per Extent........................: 7.8

- Scan Density [Best Count:Actual Count].......: 97.96% [144:147]

- Extent Scan Fragmentation ...................: 14.29%

- Avg. Bytes Free per Page.....................: 362.4

- Avg. Page Density (full).....................: 95.52%

 

Now, let’s look at why the Clustered Index approach is superior...

drop table somedata

go

 

create table somedata (

    id  int not null identity primary key clustered,

    somestuff   char(250)   not null

)

go

 

set nocount on

declare @i int

set @i = 1

 

while @i <= 40000

begin

    if @i % 5 = 0

        delete somedata

        where id = ( select top 1 id

                     from somedata

                     order by newid() )

 

    insert somedata ( somestuff ) values ( '>>>>>' + cast( @i as varchar(10) ) + '<<<<<' )

 

    set @i = @i + 1

 

end

go

 

set statistics io on

 

select count( distinct somestuff )

from somedata

where id between 1 and 10000

 

select max( somestuff )

from somedata

where id between 1 and 500

 

set statistics io off

go


Table
'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Table 'somedata'. Scan count 1, logical reads 350, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

/

Table 'somedata'. Scan count 1, logical reads 21, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

 

As you can see from the IO stats the cost of the query has dramatically dropped even on this small 11MByte table – imagine the benefits as the table grows! Because with the clustered index approach the data is ordered and such is held closer together on a smaller number of pages there are two major benefits 1) more likelihood that the page will be in cache thereby reducing the number of physical reads from disk and 2) because you are reading less pages there is less likelihood of colliding with somebody updating data and having the page locked, I know it drops to row lock but consider the overhead required if an update or insert causes a page split. Also, each logical read is 8KB which needs to go through the CPU, so the less reads the less CPU usage there will be on the box.

Looking at the DBCC PAGE output for the clustered index you can see that ‘like’ rows, our clustered index is on ‘id’, are grouped together...

Memory Dump @0x06CCC286

 

Slot 0 Column 0 Offset 0x4 Length 4

id = 182                            

 

Slot 1 Column 0 Offset 0x4 Length 4

id = 184                             

 

Slot 2 Column 0 Offset 0x4 Length 4

id = 190                            

 

Slot 3 Column 0 Offset 0x4 Length 4

id = 191                            

 

Slot 4 Column 0 Offset 0x4 Length 4

id = 193                            

 

Slot 5 Column 0 Offset 0x4 Length 4

id = 194                            

 

Slot 6 Column 0 Offset 0x4 Length 4

id = 206                            

 

Slot 7 Column 0 Offset 0x4 Length 4

id = 208               

Because of this ordering of rows, space usage isn’t as good...

- Pages Scanned................................: 1380

- Extents Scanned..............................: 175

- Extent Switches..............................: 175

- Avg. Pages per Extent........................: 7.9

- Scan Density [Best Count:Actual Count].......: 98.30% [173:176]

- Logical Scan Fragmentation ..................: 0.43%

- Extent Scan Fragmentation ...................: 1.14%

- Avg. Bytes Free per Page.....................: 1672.8

- Avg. Page Density (full).....................: 79.33%

However, one of the benefits of a clustered index is that you can actually defragment it, so running DBCC INDEXDEFRAG...

dbcc indexdefrag( 0, somedata )


We get 1128 pages moved and 249 removed and our showcontig is now...

 

- Pages Scanned................................: 1130

- Extents Scanned..............................: 144

- Extent Switches..............................: 143

- Avg. Pages per Extent........................: 7.8

- Scan Density [Best Count:Actual Count].......: 98.61% [142:144]

- Logical Scan Fragmentation ..................: 0.44%

- Extent Scan Fragmentation ...................: 21.53%

- Avg. Bytes Free per Page.....................: 251.8

- Avg. Page Density (full).....................: 96.89%

You do need to be careful when using DBCC INDEXDEFRAG because it uses a lot of log because of the nature of how it works, this can be overcome by using Bulk Logged recovery model which still allows you to keep an unbroken log chain, however – that recovery model cannot be used on a mirrored database.

So, to summarise; if you are just inserting into a table then these problems are not really going to hit you, but, if like most systems you are doing deletes or updates then you will likely have this problem.

Anyway, no brainer for me – use a clustered index.

There is a lot more I can write on this, showing a scalability test to see the dramatic performance difference, also – blocking etc... but alas, out of time.

Filed under:

Comments

# re: Row fragmentation (Hopscotch) - Heap v Clustered and IO cost

Monday, June 25, 2007 10:22 AM by ACALVETT

Heaps are evil! :) Having said that i did deliberately put one into a DB a long time ago but thats because the table never gets any deletes or updates and insert performance was critical.

I was rather pleased to see a new Best Practices article posted last month comparing tables  organised with clustered indexes versus heaps. Its a good read and covers all the scalability bits you did not have time for. Its at http://www.microsoft.com/technet/prodtechnol/sql/bestpractice/clusivsh.mspx

Also confirms the only time to consider them is when the table only gets inserts. I now like to use the document to "educate" devs.....

# re: Row fragmentation (Hopscotch) - Heap v Clustered and IO cost

Monday, June 25, 2007 4:20 PM by ipfeifer

I'm with you on heaps for the most part, however, sometimes they're a necessary evil.  

In our environment we have a process during which hundreds of clients simultaneously write to a single table with a clustered IDENTITY column, and we noticed a lot of PAGEIOLATCH waits because all these INSERTs were hitting the same page and waiting for the next ID to be created.  I believe converting to a heap should be faster, because the INSERTs will be free to create new pages instead of waiting for the previous row to be written.  Then the clustered index can be created after the fact.  A member of Microsoft's SQL CAT agreed with me, but this is as yet untested, so we'll see.

Of course, the ideal solution would be to have them all write into separate tables and then combine them, but that's a bigger architecture change.

# re: Row fragmentation (Hopscotch) - Heap v Clustered and IO cost

Monday, June 25, 2007 5:47 PM by tonyrogerson

Hi,

If there are any indexes on the table then you'll have a problem with contention while that gets updated.

But yes, multiple tables and a partition key is a better approach.

You should also watch out for ISAM (think its that - too lazy to look it up :)), basically you'll get locks as new extents are created, so - use multiple files on your database.

Tony

# re: Row fragmentation (Hopscotch) - Heap v Clustered and IO cost

Thursday, July 5, 2007 10:26 PM by bertcord

# ALTER TABLE DROP COLUMN does not reclaim the space the column took - it's a meta data change only

Monday, August 27, 2007 8:55 AM by Tony Rogerson's ramblings on SQL Server

When using ALTER TABLE &lt;x&gt; DROP COLUMN &lt;z&gt; SQL Server does not actually remove the data,