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
-