Quaere Verum - Clustered Index Scans - Part II

Question: Which access methods are available to SQL Server to fully scan the table’s data when an ORDER BY clause is not specified?

Related: Quaere Verum - Clustered Index Scans - Part I

1. Ordered Clustered Index Scan

Follow the linked list at the leaf level of the clustered index from head to tail. The performance of this access method varies depending on the level of logical fragmentation of the clustered index. The higher the fragmentation is the slower is the access method. Later I will demonstrate this.

2. Unordered Clustered Index Scan / Table Scan

The linked list at the leaf level of the clustered index is one mechanism by which SQL Server can locate the table’s data. But there’s another system that SQL Server uses to map data called IAM (short for Index Allocation Map). I will not provide the gory details about IAM rather just focus on the essentials required for my discussion. IAM pages are bitmaps that map extents belonging to an index or a heap (a table without a clustered index) by their file order.

SQL Server maintains one or more IAM pages to map/keep track of the extents that reside at the leaf level of a  clustered index by their file order. An IAM page has a bit per extent in the file, and the bit is set to 1 if the extent it represents belongs to the object owning the IAM page and to 0 otherwise. Each IAM page maps 4 GB of space in the file.

When in need to fully scan the table’s data, technically SQL Server can tell which pages/extents belong to the table by examining the IAM pages owned by the table. By using IAM pages, the scan is performed by file order (as opposed to linked list order). The efficiency of such a scan depends on the file system fragmentation, but as I mentioned earlier, I’m going to assume a simplified scenario where there’s only one data file with no file system fragmentation. In such a case, clearly an unordered clustered index scan / table scan would seem like a better choice than an ordered clustered index scan. With no logical fragmentation the performance of the two access methods should be similar. But while logical fragmentation degrades the performance of an ordered scan, it has no effect on an unordered scan.

This is true with both a heap and a clustered table, and in fact with a scan of the leaf level of nonclustered indexes as well. With a heap, IAM is the only mechanism that is currently available to fully scan the table’s data (unordered scan). With a clustered table (or any index), there are two options: using the linked list (ordered scan) or using IAM pages (unordered scan).

Note though that when the execution plan shows an unordered index scan (Ordered: False), it doesn’t necessarily mean that SQL Server will use IAM pages to scan the data, rather it means that SQL Server DOESN’T HAVE to scan the data in linked list order.

3. Advanced Scanning

Here’s a snippet from Books Online that explains Advanced Scanning:

“One part of the SQL Server Enterprise Edition advanced scan feature allows multiple tasks to share full table scans. If the execution plan of a Transact-SQL statement requires a scan of the data pages in a table and the relational  Database Engine detects that the table is already being scanned for another execution plan, the Database Engine joins the second scan to the first, at the current location of the second scan. The Database Engine reads each page one time and passes the rows from each page to both execution plans. This continues until the end of the table is reached.

At that point, the first execution plan has the complete results of a scan, but the second execution plan must still  retrieve the data pages that occur before the point at which it joined the in-progress scan. The scan for second  execution plan then wraps back to the first data page of the table and scans forward to the point at which it joined  the first scan. Any number of scans can be combined like this. The Database Engine will keep looping through the data pages until it has completed all the scans. This mechanism is sometimes known as "merry-go-round scanning" and is the reason that the order of results from a SELECT statement without a predicate to sort on cannot be  guaranteed.”

With the fundamentals out of the way, I’ll proceed to the main points I wanted to discuss…

Recent Revelations / Eye-Opener
Back to my original question: given a table T1 with a clustered index on col1, is the following query guaranteed to  return the data in clustered index order?

SELECT * FROM T1;

Being familiar with the fundamentals described so far, and backed by ANSI SQL, for years I believed that the answer was a simple no. The standard allows SQL Server to return the data in any order. With a heap, clearly there’s only  one reasonable way to scan the data—unordered scan based on IAM pages. With a clustered table, though SQL Server can rely on either the linked list or on IAM pages, it seemed natural to believe that it would always go for the
latter since it’s more efficient. So until recently I never bothered to verify whether such was the truth…

I want to stress that I still firmly believe that the working-premise should be that such a query is not guaranteed to  return the data in clustered index order. But next I will demonstrate that things are not as simple as they might  seem.

The moment of truth arrived recently when I tried to demonstrate that the above query returns unordered data. As  an afterthought I wrote similar code to the one I provided earlier to create the table T1 and populate it with random values, and issued a SELECT * without an ORDER BY clause. On the tip of my tong was the sentence “notice that the data is returned unordered as SQL Server used IAM pages to locate the data.” But to my surprise, I kept getting the data back in clustered index order:

col1        filler----------- -------5           a11          a13          a14          a15          a21          a22          a30          a31          a32          a33          a34          a36          a45          a50          a…

The textual execution plan shows:

  |--Clustered Index Scan(OBJECT:([testdb].[dbo].[T1].[idx_cl_col1]))

Without any mention that it was an ordered operation (ORDERED FORWARD or ORDERED BACKWARD). The graphical execution plan shows a Clustered Index Scan with Ordered: False. So far I believed that an Index Scan with Ordered: False simply meant an unordered scan based on IAM pages. But the result set of the query was returned in order. I checked fragmentation, used DBCC IND and DBCC PAGE, all of which indicated that the data resides in the file in a different order than in the linked list.

I tried many tests with different ways to populate the table, with varying numbers of rows, fragmentation levels, etc.; but in all of my tests the data kept coming back in order. Until I tried specifying the NOLOCK hint (read uncommitted isolation level):

SELECT * FROM dbo.T1 WITH (NOLOCK);

And suddenly the data came back unordered:

col1        filler----------- -------5           a11          a13          a14          a484         a484         a358         a359         a366         a845         a846         a854         a858         a210         a214         a…

Investigation with DBCC IND and DBCC PAGE verified that now SQL Server used IAM pages (allocation order) to scan the data. Not being able to explain the discrepancy, I turned for help. Lubor my mentor and Srikumar from the Storage Engine team explained.

Apparently allocation order scans (using IAM pages) are used to read data in two cases: when NOLOCK or TABLCOK  are specified. So the following query also returns the data in allocation order:

SELECT * FROM dbo.T1 WITH (TABLOCK);col1        filler----------- -------5           a11          a13          a14          a484         a484         a358         a359         a366         a845         a846         a854         a858         a210         a214         a…

However, the original query without any hints is run in read committed isolation level and without locking the whole table to begin with.

* Disclaimer, the explanations below are not in the direct words of Lubor and Srikumar rather partially my  interpretations, so if there are any inaccuracies they are mine alone.

In a heap, neither inserts nor updates can cause page splits or data movement. SQL Server looks for the first free space large enough to host a new row using bitmaps called PFS (page free space), and if no free space exists it allocates a new page. When a dynamic column is updated to a longer value due to an update, and there’s not
enough space in the original page to host the expanded row, SQL Server moves it to a new location but keeps a forwarding pointer in the original page. That’s why in a heap it’s “safe” to read the data by performing allocation order scans.

However, with data in an index things are different. Data can move within the index due to page splits, updating a key, or updating a dynamic column value to a longer value. Allocation order scans cannot tolerate data movement (due to updates from the same or other concurrent transaction). SQL Server may lose the scan position or return the same row twice due to splits.

Hence, to guarantee consistency, in all cases besides when NOLOCK or TABLOCK are specified, SQL Server scans the data in index order by following the linked list.

Continues in Part III...