Table Scan

Introduction

The Table Scan operator is used to read all or most data from a table that has no clustered index (also known as a heap table, or just as a heap). In combination with a Top operator, it can also be used to read just a few rows from a heap table when data order is irrelevant and there is no nonclustered index that covers all required columns.

The basic behavior of a Table Scan operator is very similar to that of the Index Scan operator when it chooses to do an IAM scan, but with a few very important differences. A heap table has no root, intermediate, and leaf level pages; it has data pages only. Each page read from the IAM is a data page and can be processed. But rows on a data page of a heap table can contain forwarding pointers, that cause out of order data access.

Visual appearance in execution plans

Depending on the tool being used, a Table Scan operator is displayed in a graphical execution plan as shown below:

SQL Server Management Studio

Azure Data Studio

Plan Explorer

(version 17.4 and up)

(until version 17.3)

Algorithm

The basic algorithm for the Table Scan operator is as shown below:

Note that this flowchart is a simplification. It doesn’t show that execution stops whenever a row is returned, and resumes where it was upon next being called. It also doesn’t include error handling for concurrency issues when a Table Scan uses READUNCOMMITTED / NOLOCK.

Locate first row / Locate next row

A Table Scan always uses the Index Allocation Map (IAM) to find all pages allocated to the heap table, similar to the “RowStore – Allocation Order Scan” of an Index Scan operator. To locate the first row, internal data structures (which can be seen through the sys.sysindexes view) are used to find the location of the first IAM page. It brings that page into the buffer pool, and then uses the row offset table on that page to find the location of the first row. To locate the next row, the row offset table on the current page is used to find the location of the next row; if the last row on the current page was already processed, it returns to the bitmap on the IAM page to find the next page allocated to this index, brings it into the buffer pool, and then once again uses the row offset table to find and return the first row on the page. Once it reaches the end of the bitmap without finding the next leaf page, it checks the NextPage pointer on the IAM page to find the next IAM page, brings that into the buffer pool, and then continues the process of scanning the bitmap. If no new leaf page is found and the last examined IAM page has a nil pointer in NextPage, then the end of the index data is reached and no row is returned.

Forwarded rows and forwarding pointers

In a heap, whenever existing data is updated and the new data does not fit on the page where the row is stored, the row is moved to a new page. The original location is not cleared completely; it is instead replaced by a so-called “forwarding pointer” – a pointer to the new location of the data. The row in its new location is then also marked as being “forwarded”, with a pointer to its original location added.

If a row that has already been forwarded later again is updated to not fit anymore, it will again move, but now the old location will be freed completely and the forwarding pointer in the original location will be modified to point to the new location. This means that in a heap table, every row is either in its original location, or the original location holds a forwarding pointer to the row’s current location, which itself is marked as forwarded with a pointer back to the original location.

As can be seen in the flowchart above, these markings and pointers are used by the Table Scan operator to read forwarded rows when the scan encounters the original location, and skip the forwarded rows when they are encountered in their current location. This may seem strange, since the Table Scan has no ordering guarantees for the data returned, but it’s needed for concurrency considerations as explained further below.

Predicate matched?

The Table Scan operator supports a Predicate property. When present, the logical test in this property will be applied to each row read, and only rows where the logical test results in True are returned. If no Predicate property is present, then every row is considered a match. The predicate may be pushed into the storage engine. This means that the test is done by the storage engine, after loading the page into the buffer pool but before returning it to the operator. This optimization is not shown in the flowchart above. Whether or not a predicate is pushed depends on the complexity, and is not visible in the execution plan, except when a Bitmap filter is applied. In that case only, when the “probe” internal function used to test the bitmap is enriched with the “IN ROW” parameter, the bitmap probe is pushed into the storage engine. If not, then the probing is done within the operator.

Table Scan and concurrency

As explained above, if a row in a heap table was ever updated and had to move to accommodate length of the new data, it is stored as a combination of a forwarding pointer in the original location and a forwarded row (with back pointer) in the current location. The IAM scan will of course encounter both. In order to have the row once in the results, one might think that Microsoft could have chosen to return the row when the IAM scan encounters the forwarded row, instead of returning it on encountering the forwarding pointer. However, this would introduce a serious risk of skipping rows or returning duplicate rows if a Table Scan operates while concurrent updates are in progress.

The scenarios where a duplicate row would be returned are when a row that is still in its original location is updated and needs to be forwarded, this happens after the scan has processed the original location of the row, but before it processes the new location of the row. Another scenario would be when a row that was already forwarded is updated and needs to move to another location, and that other location has not yet been processed by the scan but the old forwarded location was.

The scenarios where a row would be omitted from the results of the Table Scan would be when a row that is still in its original location is updated and needs to be forwarded, this happens before the scan processes the original location of the row, but the new location of the row is on a page that was already processed. Another scenario would be when a row that was already forwarded is updated and needs to move to another location, the old location is on a page that still has to be processed by the Table Scan, but it is moved to a page that was already processed before the scan gets there.

When a Table Scan operates under readuncommitted isolation level (which includes the NOLOCK hint), or when concurrent updates are impossible (due to either a table level lock or the table being on a read only filegroup), the Table Scan could choose to skip forwarding pointers and process forwarded rows instead. Under readuncommitted isolation level that could still return incorrect data, but the isolation level allows for it. When no concurrent updates are possible, then there is no risk of incorrect results due to forwarded rows moving. However, Microsoft have chosen not to implement this extra logic. Regardless of isolation level and risk of concurrent updates, the Table Scan will always skip forwarded rows and follow forwarding pointers as the IAM scan encounters them.

Specifically under readuncommitted isolation level, there is a (very small) chance that a concurrent update causes a forwarded row to move just at the same time as the Table Scan processes the forwarding pointer in the original location. In this case, a race condition might cause a run-time error, unless Microsoft protects the affected pages with latches during the time it takes to move the forwarded row to its new location and update the forwarding pointer in the original location. Since I have never heard of a case of a readuncommitted Table Scan causing a run-time error under these circumstances, I suspect that these latches are indeed used.

Operator properties

The properties below are specific to the Table Scan operator, or have a specific meaning when appearing on it. For all other properties, see Common properties. Properties that are included on the Common properties page but are also included below for their specific meaning for the Table Scan operator are marked with a *.

Property nameDescription
Defined Values *For a Table Scan, this property lists the columns read from the index and returned to the calling operator. It is therefore the same as the Output List property.
Estimated Number of Rows to be ReadThis is an estimate of the number of rows that will be read by the operator as it is scanning the heap. In most cases this will be equal to the estimated total number of rows in the table, except when there are other operators in the execution plan that can result in this operator not being called anymore before the end of the data is reached.
The difference between this property and the Estimated Number of Rows or Estimated Number of Rows Per Execution property represents the number of rows that is estimated to be read but not returned due to the Predicate property.
Forced IndexThis property is set to true if the use of the heap was forced through an index hint in the query.
ForceScanThis property is set to true if the query used a FORCESCAN hint to force the use of a scan operator even if the optimizer would rather use a seek operator.
IndexKindThis property is always equal to Heap for a Table Scan.
Note that this property is not exposed in the property list of SSMS. If the operator runs in batch mode, SSMS will display “(Heap)” behind the operator name in the graphical execution plan. When running in row mode, this is not the case.
The property can be accessed through the execution plan XML.
NoExpandHintThis property is set to true if the NOEXPAND hint was used in the query to force the optimizer to use indexes on an indexed view.
Number of Rows ReadThis is the number of rows that was read by the operator as it was scanning the heap. In most cases this will be equal to the total number of rows in the table, except when there were other operators in the execution plan that resulted in this operator not being called anymore before the end of the data was reached. In a parallel execution plan, this property shows a breakdown of rows on each individual thread.
The difference between this property and the Actual Number of Rows or Actual Number of Rows for All Executions property represents the number of rows that was read but not returned due to the Predicate property.
Only available in execution plan plus run-time statistics.
ObjectThe Object property names the table that is being scanned by the Table Scan operator, using three part naming (database, schema, table) and optionally followed by a table alias.
OrderedThis property is always set to False for a Table Scan.
PredicateWhen present, this property defines a logical test to be applied to all rows that are read by the Table Scan. Only rows for which the predicate evaluates to True are returned. When possible, the Table Scan operator will push this predicate into the storage engine to prevent extra roundtrips between the operator and the storage engine.
Note that a Predicate on a Table Scan does not reduce the amount of rows that is touched by the operator. The difference between the Actual Number of Rows (for All Executions) and the Number of Rows Read property (or their estimated counterparts) shows how many rows were read but not returned. This can be used to gauge how useful an index would be that supports the predicate.
StorageAlways equal to RowStore for a Table Scan.
Table CardinalityThis property shows the number of rows in the table when the plan was last compiled.

Implicit properties

This table below lists the behavior of the implicit properties for the Table Scan operator.

Property nameDescription
Batch Mode enabledThe Table Scan operator supports both row mode and batch mode execution.
BlockingThe Table Scan operator is non-blocking.
Memory requirementThe Table Scan operator does not have any special memory requirement.
Order-preservingThe Table Scan operator returns data in the order of the pages in the IAM, which for the purpose of the execution plan is considered to be an unreliable order.
Parallelism awareWhen the Table Scan operator is running in a parallel section of an execution plan, it uses the “Parallel Page Supplier” method described here.
Segment awareThe Table Scan operator is not segment aware.
Menu

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close