{"id":609,"date":"2012-01-31T11:00:18","date_gmt":"2012-01-31T16:00:18","guid":{"rendered":"http:\/\/sqlity.net\/en\/?p=609"},"modified":"2014-11-13T14:00:15","modified_gmt":"2014-11-13T19:00:15","slug":"the-performance-impact-of-forwarded-records-on-table-scans","status":"publish","type":"post","link":"https:\/\/sqlity.net\/en\/609\/the-performance-impact-of-forwarded-records-on-table-scans\/","title":{"rendered":"The Performance Impact of Forwarded Records on Table Scans"},"content":{"rendered":"
\n

\nForwarded records are a mechanism that SQL Server employs to reduce the amount of maintenance work for indexes on a table without a clustered index. During an update of a record in a table that does not have a clustered index, an increase in size might prevent the record to fit on its current page. If that happens, a forwarding pointer is created in the current page and the record is moved to a new location.\n<\/p>\n

\nIt is well known that such forwarded records will cause each RID-Lookup operation that encounters one to have to read a second page. If you are doing a filtered index scan followed by an RID-Lookup this can potentially double the amount of work necessary to retrieve all rows.\n<\/p>\n

\nWhat is less well known is the fact, that such forwarded records can significantly impact the performance of a simple table scan as well. In this article I will show you why this happens.\n<\/p>\n

Terminology<\/h3>\n

\nTo explain the way SQL Server handles forwarded records during a table scan, I am first going to rehash some storage basics.\n<\/p>\n

\nSQL Server knows two ways to organize the data in a table on disk. One is the Clustered Index and the other one the Heap. In a Clustered Index data is organized in a B+Tree structure allowing for fast access based on the Clustered Index Key. In a Heap on the other hand the data is not sorted or linked in any way. Any new row is inserted into the table in any free space big enough to hold the row.\n<\/p>\n

\nIn both cases the smallest unit of storage and access is a Page. Every piece of data SQL Server needs to store on disk is organized in blocks called pages. Each page is exactly 8192 Bytes in size. The only exception to this rule are the log files. Log data is stored in a structure called virtual log file and those are not part of today's discussion.\n<\/p>\n

\nIndexes created on a Heap use a physical address to point from the index record to the underlying data record. This address consists of the file number, the number of the page that contains the record within that file and the slot number inside that page.\n<\/p>\n

Forwarded Records<\/h3>\n

\nWhen a record with variable length data type columns is updated, its size might increase. If the page it is stored in is filled already, the updated record might need to be moved to a new page. If that happens, all pointers in any index on that table addressing the moved row now point to the wrong (old) place. There are two ways to handle this situation: Update all indexes with the new location or put a special record in the old place that \"forwards\" to the new location.\n<\/p>\n

\nGoing through all existing indexes can be extensively resource intensive. For that reason SQL Server is using the second option to put a forwarding record in the old place.\n<\/p>\n

\nSuch a forwarding record links to the new physical address of the actual data. The new record also contains a pointer back to the forwarding record. This back-pointer allows the forwarding record to get updated in case the data record has to move again or in case it gets deleted which causes the forwarding record to be deleted as well. Updating the forwarding records in cases of repeated data record moves prevents long forwarding chains. Instead there is always only at max on hop.\n<\/p>\n

\nIn the case of an RID-Lookup SQL Server has to follow those forwarding records to get to the actual data record. This causes an additional (logical) page read for each forwarding record encountered.\n<\/p>\n

\nDuring a table scan on the other hand each page will be read anyway so SQL Server could just ignore all forwarding records. That however could cause reading inconsistencies. Rows that are updated after the scan started and before it finishes could be missed entirely by the scan, if the record gets moved to a page that was scanned already. For that reason SQL Server follows each forwarding record immediately. This not only causes an additional read right there, is also turns the sequential read of all pages in allocation order into a succession of random reads, hurting performance potentially even more.\n<\/p>\n

Demonstration<\/h3>\n

\nTo demonstrate this behavior let us set up two tables dbo.ForwardSmall and dbo.NoForwardSmall as well as a Procedure dbo.ChangeRow to help with the creation of forwarded records:\n<\/p>\n

\n[sql]\nIF OBJECT_ID('dbo.ForwardSmall') IS NOT NULL DROP TABLE dbo.ForwardSmall;
\nCREATE TABLE dbo.ForwardSmall(Id INT ,F VARCHAR(8000))
\nGO
\nIF OBJECT_ID('dbo.NoForwardSmall') IS NOT NULL DROP TABLE dbo.NoForwardSmall;
\nCREATE TABLE dbo.NoForwardSmall(Id INT ,F VARCHAR(8000))
\nGO<\/p>\n

IF OBJECT_ID('dbo.ChangeRow') IS NOT NULL DROP PROCEDURE dbo.ChangeRow;
\nGO
\nCREATE PROCEDURE dbo.ChangeRow
\n@Id INT,
\n@Size INT
\nAS
\nBEGIN
\n SET NOCOUNT ON;
\n MERGE dbo.ForwardSmall fs
\n USING (SELECT @Id,REPLICATE('X',@Size)) x(Id,F)
\n ON fs.Id = x.Id
\n WHEN MATCHED THEN
\n UPDATE SET fs.F = x.F
\n WHEN NOT MATCHED THEN
\n INSERT (Id,F)VALUES(x.Id,x.F);
\nEND
\nGO
\n[\/sql]\n<\/p><\/div>\n

\nThe procedure will take an Id parameter as well as a size parameter. It uses to merge command to either insert or update the record with the given Id value. The F column will be valued with a string of length @Size.\n<\/p>\n

\nThe following script will create 16 rows in the table dbo.ForwardSmall and then update those records to create forwarded records.\n<\/p>\n

\n[sql]\nEXEC dbo.ChangeRow 11,900;
\nEXEC dbo.ChangeRow 12,900;
\nEXEC dbo.ChangeRow 13,900;
\nEXEC dbo.ChangeRow 14,900;
\nEXEC dbo.ChangeRow 15,900;
\nEXEC dbo.ChangeRow 16,900;
\nEXEC dbo.ChangeRow 17,900;
\nEXEC dbo.ChangeRow 18,900;<\/p>\n

EXEC dbo.ChangeRow 21,900;
\nEXEC dbo.ChangeRow 22,900;
\nEXEC dbo.ChangeRow 23,900;
\nEXEC dbo.ChangeRow 24,900;
\nEXEC dbo.ChangeRow 25,900;
\nEXEC dbo.ChangeRow 26,900;
\nEXEC dbo.ChangeRow 27,900;
\nEXEC dbo.ChangeRow 28,900;
\n--------------------------
\nEXEC dbo.ChangeRow 27,0;
\nEXEC dbo.ChangeRow 28,0;
\nEXEC dbo.ChangeRow 18,1800;
\nEXEC dbo.ChangeRow 28,900;
\nEXEC dbo.ChangeRow 18,900;<\/p>\n

EXEC dbo.ChangeRow 26,0;
\nEXEC dbo.ChangeRow 17,1800;
\nEXEC dbo.ChangeRow 27,900;
\nEXEC dbo.ChangeRow 17,900;<\/p>\n

EXEC dbo.ChangeRow 25,0;
\nEXEC dbo.ChangeRow 16,1800;
\nEXEC dbo.ChangeRow 26,900;
\nEXEC dbo.ChangeRow 16,900;<\/p>\n

EXEC dbo.ChangeRow 24,0;
\nEXEC dbo.ChangeRow 15,1800;
\nEXEC dbo.ChangeRow 25,900;
\nEXEC dbo.ChangeRow 15,900;<\/p>\n

EXEC dbo.ChangeRow 23,0;
\nEXEC dbo.ChangeRow 14,1800;
\nEXEC dbo.ChangeRow 24,900;
\nEXEC dbo.ChangeRow 14,900;<\/p>\n

EXEC dbo.ChangeRow 22,0;
\nEXEC dbo.ChangeRow 13,1800;
\nEXEC dbo.ChangeRow 23,900;
\nEXEC dbo.ChangeRow 13,900;<\/p>\n

EXEC dbo.ChangeRow 21,0;
\nEXEC dbo.ChangeRow 12,1800;
\nEXEC dbo.ChangeRow 22,1499;
\nEXEC dbo.ChangeRow 12,780;<\/p>\n

EXEC dbo.ChangeRow 11,910;<\/p>\n

EXEC dbo.ChangeRow 22,900;
\nEXEC dbo.ChangeRow 21,910;
\n[\/sql]\n<\/p><\/div>\n

\nEach record starts out with ~950 bytes, so the 16 records will fit into two pages. From there the records are updated in a way so that each of them ends up on the other page with a forwarding record in its old place.\n<\/p>\n

\nNow lets put the exact same data into the dbo.NoForwardSmall table:\n<\/p>\n

\n[sql]\nINSERT INTO dbo.NoForwardSmall
\nSELECT * FROM dbo.ForwardSmall;
\n[\/sql]\n<\/div>\n

\nThis again requires two pages, but this time no forwarded records are created.\n<\/p>\n

\nTo confirm, we can use the following query using the sys.dm_db_index_physical_stats DMF:\n<\/p>\n

\n[sql]\nSELECT OBJECT_SCHEMA_NAME(object_id)+'.'+OBJECT_NAME(object_id) Tbl,index_type_desc,alloc_unit_type_desc,page_count,record_count,forwarded_record_count
\nFROM sys.dm_db_index_physical_stats(DB_ID(),NULL,NULL,NULL,'detailed') ps
\nWHERE object_id IN (OBJECT_ID('dbo.ForwardSmall'),OBJECT_ID('dbo.NoForwardSmall'));
\n[\/sql]\n<\/div>\n

\nThis query returns the number of pages, the total number of records and the number of forwarded records for each table:\n<\/p>\n

\n