THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

Kalen Delaney

Geek City: What's Worse Than a Table Scan?

I have frequently heard SQL Server developers and DBAs gasp when a query plan is indicating that SQL Server is performing a table scan, thinking that is the worst thing that could ever happen to a query. The truth is, it's far from the worst thing and in addition, not all table scans are created equal.

One thing that is far worse that a table scan is to execute a query plan that uses a nonclustered index, and having that plan look up every single row in a table! Although that is a horrible thing to behold, it is not the topic of this post.

Today, I'm going to show you that two different table scans on the same data in a heap can give very different performance.

The behavior has to do with a technique that SQL Server uses when a row in a heap is increased in size so it no longer fits in the original page. This usually occurs when a variable length column is updated to take more space.  If SQL Server just moved the row to another page, any nonclustered indexes would have to be updated to indicate the new page address.  (Remember, if the underlying table is a heap, nonclustered indexes point to the data row using a actual address.) Since there can be up to 249 nonclustered indexes on a single table, that could potentially be a LOT of work. So instead, when a row in a heap has to move, SQL Server leaves behind a forwarding pointer in place of the row that has moved. The nonclustered indexes continue to point to the old location, and then SQL Server just needs one more page lookup to find the new location. For just a few lookups, this expense is minimal and more than made up for my the savings of not having to update all the nonclustered indexes every time a row moves.

However, what happens when there are LOTS of forwarding pointers?

The metadata function sys.dm_db_index_physical_stats has a column that indicates how many forwarded records are in any table. For tables with clustered indexes, this will always be 0.

Let's look at an example. I'll make a copy of the Person.Address table in the AdventureWorks database, and add a new varchar column to it. Initially, the column takes no space.

USE AdventureWorks;
GO
IF EXISTS (SELECT 1 FROM sys.tables
            WHERE name = 'Address2' AND schema_id =1)
        DROP TABLE dbo.Address2;
GO
SELECT *, convert (varchar(500), 'comments') AS comments
   INTO Address2
FROM Person.Address;
GO
-- note that the pages are almost full and there are no forwarded records
SELECT index_type_desc, page_count, avg_page_space_used_in_percent,
     avg_record_size_in_bytes,forwarded_record_count
FROM sys.dm_db_index_physical_stats(db_id('AdventureWorks'),
      
object_id('Address2'),null, null, 'detailed');
GO

Now I'll increase the length of all the new columns and check the physical stats again:

UPDATE Address2
SET comments = replicate('a', 500);
GO
SELECT index_type_desc, page_count, avg_page_space_used_in_percent,
     avg_record_size_in_bytes,forwarded_record_count
FROM sys.dm_db_index_physical_stats(db_id('AdventureWorks'),
      
object_id('Address2'),null, null, 'detailed');
GO

The output shows me I have 1763 pages in the table and 15961 forwarded records.

Let's see what happens when we read every row in the table:

SET STATISTICS IO ON;
SELECT * FROM Address2;
SET STATISTICS IO OFF;

The logical I/O value tells us that instead of just reading through every page, for a total of 1763 reads, SQL Server jumps out of sequence and follows the forwarding pointer for every forwarded record. So the number of logical reads is the sum of the number of pages plus the number of forwarded records:

1763  +  15961= 17724

I was discussing this behavior with my friend and colleague Tibor Karaszi and he proposed an explanation for this behavior. He related it to the same behavior that Itzik Ben-Gan has described for why SQL Server will always follow page pointers when scanning a clustered index if consistent reads are desired. The alternative would be to just read the pages in disk order, or page number order, which can be determined by examining the IAM structures for the object. For clustered tables, we need to follow the page pointers instead of the IAMs  to make sure that if a row is moved due to an update while the scan is occurring, that we don't read the same row twice (if the row is moved to a higher page number) or skip the row altogether (if the row is moved to a lower page number.)

But what about a heap? Are there potential problems scanning a heap while updates are occurring? Could we potentially read the same row twice or skip a row, since there is no 'ordered list' to read? Tibor suggested the following:

I believe that forwarding pointers take care of just that. Because of forwarding pointers, the "root" location for a row is stable. So, even if the row moves during a scan, the "root location"(forwarding stub) is at the same position. We have concluded that the scan uses the forwarding pointers when reading the rows. This means that a scan is not sensitive to row movements during the scan. It cannot "skip" rows that are there, or read the same row twice.

So a few forwarding pointers are not a bad thing, but having lots of them can increase the work done during scans or partial scans by a considerable amount.

So how do you get rid of forwarding pointers? There are 3 ways:

1. If the row is updated, so that its size decreases, AND if there is still room on the page where the row came from, it will be moved back. This is not dependable, so it isn't really recommended as a solution.  When I updated my Address2 table, many of the forwarded records were moved, but not all:

UPDATE Address2
SET comments = '';
GO
SELECT index_type_desc, page_count, avg_page_space_used_in_percent,
     avg_record_size_in_bytes,forwarded_record_count
FROM sys.dm_db_index_physical_stats(db_id('AdventureWorks'),
      
object_id('Address2'),null, null, 'detailed');
GO

My results showed that I am still left with 1080 forwarded records. This is a great improvement over 15961, but it's still more forwarded records than there are pages in the table.

2. Forwarded records will be cleaned up when you shrink the data file. This is definitely NOT recommended as a solution; I am only mentioning it for completeness. SQL Server does so much moving of data and updating nonclustered index pointers when shrinking a file, that updating the forwarded records is not very much extra work at all.

3. Since forwarded records only exist in heaps, the best solution is to make the table not a heap. Build a clustered index, and all the forwarded records will go away. If you really don't want the clustered index, you can then drop it.

Hopefully, this information will be useful to you.

~Kalen

Published Sunday, May 25, 2008 2:59 PM by Kalen Delaney

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

James Luetkehoelter said:

I love this angle on table scans and the example. One thing I frequently find though (in the moderate to initiate level) is that people jump on a table scan (or clustered index scan) when they see it in an execution plan without regarding the size of the table. I've seen people waste hours of time trying to force a query to use a non-clustered index even though the table has 100 rows. Scans in some situation is still the fastest way for SQL to retrieve 1 out of those 100 rows (especially if those 100 rows are on 1 or 2 data pages).

May 25, 2008 7:24 PM
 

Kalen Delaney said:

Well, a table scan on only a few hundred rows might still be a bad thing if every one of those rows is forwarded!

May 26, 2008 12:59 AM
 

Alejandro Mesa said:

Hi Kalen,

Very interesting article, as always.

While reading the article, I thought about a dbcc command that reclaims space from dropped variable-length columns in tables or indexed views, DBCC CLEANTABLE. I know we are not dropping any variable-lenght column, but still gave it a try.

UPDATE Address2 SET comments = '';

GO

SELECT index_type_desc, page_count, avg_page_space_used_in_percent,

    avg_record_size_in_bytes,forwarded_record_count

FROM sys.dm_db_index_physical_stats(db_id('AdventureWorks'),

      object_id('dbo.Address2'),null, null, 'detailed');

GO

DBCC CLEANTABLE ('AdventureWorks','dbo.Address2');

go

SELECT index_type_desc, page_count, avg_page_space_used_in_percent,

    avg_record_size_in_bytes,forwarded_record_count

FROM sys.dm_db_index_physical_stats(db_id('AdventureWorks'),

      object_id('dbo.Address2'),null, null, 'detailed');

GO

Result:

forwarded_record_count: 15

Can you help us to find out, if this command could really help us to get rid of forwarding pointers, after decreasing the size of a variable-length column, if the table is a heap?

Thanks in advance,

AMB

May 26, 2008 10:19 AM
 

Kalen Delaney said:

Very interesting... I never would have guessed that DBCC CLEANTABLE would help this. I'll see what I can find out.

Thanks

Kalen

May 26, 2008 12:55 PM
 

Denis Gobo said:

I remember a person on tek-tips asking how to get a index seek on a gender column index. Of course this index only had 2 possible values and had a couple of million rows

so he wanted a seek with a query like this

select * from Table

where gender = 'M'

May 27, 2008 10:39 AM
 

Paul Randal said:

Kalen pinged me on this... DBCC CLEANTABLE will not cleanup forwarded records if that is the only thing 'wrong' with the record. It will reclaim space from records that have dropped variable-length, SLOB, or LOB columns.

If you have a heap where some records are forwarded *and* have one of the situations above, it may seem like DBCC CLEANTABLE is removing forwarded records too, but it's really just an artifact of the way DBCC CLEANTABLE removes the dropped column space.

Thanks

May 29, 2008 11:08 AM
 

Rajan John said:

As a reply to Paul's comments; I could see that even without dropping the variable length column, DBCC CLEANTABLE reduced the number of forwarded records count. After dropping the column, it further reduced the count. Do we know why this is so?

June 26, 2008 9:25 AM
 

Kalen Delaney said:

I know it's been a while since I had a technical post, and I've got 3 of them started and saved as drafts.

November 11, 2009 8:31 PM
 

Kalen Delaney said:

I know it's been a while since I had a technical post, and I've got 3 of them started and saved as drafts.

November 11, 2009 8:33 PM
 

Mohiuddin said:

Very interesting article

March 11, 2010 9:34 AM
 

Tibor Karaszi said:

Never? You are not alone. None of the maintenance solutions I use includes functionality to rebuild a

March 6, 2014 6:57 AM

Leave a Comment

(required) 
(required) 
Submit

This Blog

Syndication

Favorite Non-technical Sites or Blogs

Powered by Community Server (Commercial Edition), by Telligent Systems
  Privacy Statement