Kalen Delaney : pages

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

Kalen Delaney — Sun, 25 May 2008 20:59:00 GMT

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

Geek City: Nonclustered Index Keys

Kalen Delaney — Mon, 17 Mar 2008 01:53:00 GMT

I recently received a question about the storage of nonclustered index keys. I am assuming you are aware of the fact that if your table has a clustered index, SQL Server uses the clustered index key (all of its columns, if it is a composite index) as a 'bookmark' in your nonclustered indexes, to allow your nonclustered indexes to uniquely identify the row that the index is pointing to.

In particular, this question was about a couple of statements in Inside SQL Server 2005: Query Tuning and Optimization, Chapter 3. Now, I didn't write Chapter 3, but I thought I knew all about how index keys were stored. But (you may want to be sitting down for this) I WAS WRONG.

Here are the statements:

“…when you create a nonunique nonclustered index on a table with a clustered index, we append the clustered index keys to the nonclustered index keys if they are not explicitly part of the nonclustered index keys”

And then a bit later on, there is another quote discussing this same effect:

“Note that the key columns for each of the nonclustered indexes on T_clu include the clustered index key column a with the exception of T_clu_f, which is a unique index.”

Although I had read this chapter when we were putting the book together, I must have read this last sentence too fast. The first quoted sentence is basically what I said in my lead-in paragraph. But the second sentence now seemed wrong. I thought it was saying that if your nonclustered index is UNIQUE, the clustered key columns are not stored in the index at all. I knew that wasn't true, so I contacted the author of Chapter 3. It turns out he was using a very specific definition of key.

KEY COLUMN: a column that is stored in the leaf pages and the interior (node, or non-leaf) pages of the B-tree and that you can use in an index seek.

He also uses another term in some of the related sections of the chapter:

COVERED COLUMN: a column that can be returned by the index without performing a bookmark lookup; it may or may not be a key column but it is stored in the leaf pages of the B-tree.

The definition of an index key includes the the property that it is stored at all levels of an index, not just the leaf level. Covered columns are in the leaf, so we have the potential of a covering index, and the possibility of retrieving the data we need without accessing the table itself. But not all covered columns are key columns.

This was news to me. I assumed that the fact that the clustered index key was in the nonclustered index meant that it was part of the key. And all my previous testing seemed to bear that out; I must never have tested at this level of detail with a unique nonclustered index. What this means is that I have been wrong in the following claim: "Explicitly declaring your clustered key columns as part of your nonclustered indexes does not make any difference in the storage of the index." That statement is true for nonunique indexes, but not true for unique.

What does this really mean?

Consider a TabA with a clustered index on col1. These two index definitions are identical:

CREATE INDEX nc_index ON TabA(col2)
CREATE INDEX nc_index ON TabA(col2, col1)

For a nonunique, nonclustered index (which the above index is), the clustered key col1 is automatically included at the leaf, and at all other levels, just as if we explicitly declared col1 to be part of the nonclustered index key.

However, these two index definitions are not exactly the same:

CREATE UNIQUE INDEX nc_index ON TabA(col2)
CREATE UNIQUE INDEX nc_index ON TabA(col2, col1)

The first index definition will create a nonclustered index on col2, and add col1 only at the leaf. The second index definition will also create an nonclustered index on col2, but it will add col1 as a true key column and it will be stored at all index levels.

Here's a specific example

Let's look at a specific example. I will be demonstrating the contents of the index rows using DBCC PAGE, and determine the index pages I am interested in by using DBCC IND. For more information about these two undocumented commands, one of the best places to look is at a couple of blog posts by Paul Randal:

http://www.sqlskills.com/blogs/paul/2007/10/01/InsideTheStorageEngineUsingDBCCPAGEAndDBCCINDToFindOutIfPageSplitsEverRollBack.aspx

http://blogs.msdn.com/sqlserverstorageengine/archive/2006/12/13/More-undocumented-fun_3A00_-DBCC-IND_2C00_-DBCC-PAGE_2C00_-and-off_2D00_row-columns.aspx

DBCC IND returns one row for every page of a table or index. The rows contain values indicating what type of page is listed (2 is an index page), what index the page belongs to, what level of an index the page is at (0 is the leaf), and then the file ID and page number. These last two values are then used in DBCC PAGE to get the contents of the page. The output also includes the file ID and page number for the next and previous pages in logical order. A page with no previous page is the first page in order.

When running DBCC IND on a large table, you can get lots of rows returned, and it can be tricky to find the exact rows you're interested in. For this reason, I usually take the output of DBCC IND and save it to a table, and then I can query the table. I can included the script to build a table called sp_index_info in the master database. Because of the sp_ prefix, this table can be accessed from any database.

I'm going to use a table that I copy from the AdventureWorks database into a test database. You can use any database you like to run this code on your own server.

USE testdb
GO
IF EXISTS (SELECT name FROM sys.tables WHERE name = 'Sales')
DROP TABLE Sales;
GO
SELECT * INTO Sales
FROM AdventureWorks.Sales.SalesOrderDetail;
GO

Now build a clustered index on SalesOrderID and three similar nonclustered indexes on SalesOrderDetailID, which is unique.

CREATE CLUSTERED INDEX Sales_ID_Index ON Sales(SalesOrderID);
GO
-- The first index is not declared as a unique index
CREATE INDEX Sales_DetailID_Index1 ON Sales(SalesOrderDetailID);
GO
-- The second index is declared as a unique index
CREATE UNIQUE INDEX Sales_DetailID_Index2 ON Sales(SalesOrderDetailID);
GO
-- The third index is declared as a unique index and explicitly includes the clustered index key
CREATE UNIQUE INDEX Sales_DetailID_Index3 ON Sales(SalesOrderDetailID, SalesOrderID);
GO

Now, populate the sp_index_info table with the results of DBCC IND

TRUNCATE TABLE sp_index_info
INSERT INTO sp_index_info
EXEC ('DBCC IND ( testdb, Sales, -1)' );
GO

Find the first leaf page from each index, by looking for pages with no previous page, and with an IndexLevel value of 0.

SELECT PageFID, PagePID, IndexID
FROM sp_index_info
WHERE PageType = 2 AND IndexLevel = 0
AND PrevPagePID = 0
ORDER BY IndexID;
GO

Here's my output:

PageFID PagePID     IndexID
------- ----------- -------
1       3416        2
1       1248        3
1       1680        4

To look at the actual rows, we need to use DBCC PAGE. An option value of 3 is very useful for index pages, as it gives us tabular output showing each individual index row. I'll take each of the file and page numbers and use them in DBCC PAGE, and of course you'll have to substitute whatever page numbers you get.

DBCC TRACEON (3604);
DBCC PAGE(testdb, 1, 3416, 3);
DBCC PAGE(testdb, 1, 1248, 3);
DBCC PAGE(testdb, 1, 1680, 3);

Here are my results:

The results shown are for the leaf level. Note that because my clustered index is not unique, it includes a uniqueifier for every row. The uniqueifier is never visible using SELECT statements, but is a hidden column stored within the row to make sure each row in the clustered index is unique. This uniqueifier column is always considered part of the clustered key internally, so every nonunique clustered index is really a composite index.

There is the exact same data in the leaf for all three nonclustered indexes (except for page numbers of course; all three indexes have their own pages). The same index keys are in each row of the first leaf level index page. However, you might note a couple of differences int the column headers. Just as the nonunique clustered index includes a uniqueifier, SQL Server has to have some way to make sure each nonclustered index row is unique. The column headers actually index which columns of my nonclustered indexes make up the key. For the nonunique index, SQL Server has to consider the entire clustered key as part of the nonclustered key. It knows the clustered key is unique, so adding it to the nonclustered guarantees uniqueness. You can see that all 3 columns are labeled as (key): SalesOrderDetailID, SalesOrderID (the clustered key) and the clustered index uniqueifier.

For the second index, which was declared as unique, but did not explicitly include the clustered key, the only key the nonclustered index needs is the key the index was built on. Because that single key was declared as unique, no further information is needed to be part of the key. However, the clustered key stored in the leaf level rows, because SQL Server needs that to be able to find the row in the table data.

The third index explicitly declared the clustered key to be part of the nonclustered index key. So the column labels indicate that both the column SalesOrderDetailID and SalesOrderID are key columns. Since the index was declared to be unique, only the explicitly declared key columns are part of the key. The uniqueifier is there, because as part of the clustered key is must be in the leaf level pages, but it is not marked as part of the nonclustered key.

So how are these indexes different?

The indexes differ in the upper levels. The table sp_index_info still contains the output of DBCC IND, so we can find an upper level page for each index.

At the level above the leaf the IndexLevel is 1. I don't want to see the rows for the upper level pages of the clustered index, so I filter them out.

SELECT PageFID, PagePID, IndexID
FROM sp_index_info
WHERE PageType = 2 AND IndexLevel > 0 and IndexID > 1
AND PrevPagePID = 0
ORDER BY IndexID;

Here are my results:

PageFID PagePID     IndexID
------- ----------- -------
1       3520        2
1       1360        3
1       1744        4

And then I use those results to look at the pages:

DBCC TRACEON (3604);
DBCC PAGE(testdb, 1, 3520, 3);
DBCC PAGE(testdb, 1, 1360, 3);
DBCC PAGE(testdb, 1, 1744, 3);

Here are my results:

Now you should see something different. The first index, nonunique, still has all three columns in the upper level page: the nonclustered key SalesOrderDetailID, and the two columns of the clustered key: SalesOrderID and the uniqueifier.

The second index is the unique nonclustered on a single column, and only has SalesOrderDetailID in the upper level page.

The third index is unique and composite, so both of the declared keys are in the upper level.

What other possibilities are there?

One additional question you might have is what happens if the clustered index is also unique. How do the nonclustered index rows look different? I think with the tools and examples presented here, you should be able to figure that out for yourself!

Have fun!

~Kalen

http://DVD.KalenDelaney.com

www.SQLCommunity.com

------------------------------Script to create a table to hold DBCC IND output--------------------------------------------------------

-- Create a table to hold the output of DBCC IND
USE master
GO
IF EXISTS (SELECT name FROM sys.tables
WHERE name = 'sp_index_info')
DROP TABLE sp_index_info;

GO
CREATE TABLE sp_index_info
(PageFID tinyint,
PagePID int,
IAMFID   tinyint,
IAMPID int,
ObjectID int,
IndexID tinyint,
PartitionNumber tinyint,
PartitionID bigint,
iam_chain_type varchar(30),
PageType tinyint,
IndexLevel tinyint,
NextPageFID tinyint,
NextPagePID int,
PrevPageFID tinyint,
PrevPagePID int,
Primary Key (PageFID, PagePID));