Kalen Delaney : sort

Geek City: Using a Nonclustered Index to Avoid a Sort

Kalen Delaney — Wed, 03 Dec 2008 03:20:00 GMT

Most of you are probably aware that having a clustered index on the column(s) in an ORDER BY clause means that SQL Server can avoid having to sort your data, because it is already logically stored in order of the clustered index, and SQL Server can just access the data in order to get the sorted data .

For example, consider the SalesOrderHeader table in the AdventureWorks database. The clustered index is on SalesOrderID, so this query doesn't need to do a sort, just a clustered index scan:

SELECT * FROM Sales.SalesOrderHeader
ORDER BY SalesOrderID

But what about a nonclustered index? Its leaf level stores the index key values in order, so it can help avoid a sort if it completely covers the query, i.e. all the data your query needs is in the nonclustered index. The following query is covered by the nonclustered index on CustomerID, because the nonclustered index always includes the clustered key, in this case, SalesOrderID.

SELECT CustomerID, SalesOrderID
FROM Sales.SalesOrderHeader
ORDER BY CustomerID

But what about if the query is not covered? What if we wanted every column returned:

SELECT * FROM Sales.SalesOrderHeader
ORDER BY CustomerID

The default plan for this query will be to perform a sort.

However, the leaf level of the nonclustered index on CustomerID does have all the CustomerID values already sorted, so why can't that index be used? The answer is, it CAN be used, but it just isn't the default. SQL Server's optimizer tries to find the plan that will run to completion in the least amount of time. That sounds good, right? But with the SORT operator in the plan, everything stops while the sorting is taking place, and no data can be returned until all the data is sorted.

However, another alternative would be to scan the nonclustered index, where the CustomerID values are already in order. For each row, SQL Server would have to do a key lookup into the clustered index and the total time to do a key lookup for every row would probably be more than the time required to sort all the data. The first few rows can be returned very quickly. How can we get such a plan? SQL Server provides us with a hint called FASTFIRSTROW that tells the optimizer to come up with a plan that returns the first row in a minimum amount of time. It's a table hint, so it looks like this:

SELECT * FROM Sales.SalesOrderHeader WITH (FASTFIRSTROW)
ORDER BY CustomerID

The plan looks like this:

So you have to decide what is most important to you. Do you want the total processing time to be minimized, or do you want the time to have the first row returned to be minimized? It's up to you. The default is to minimize total processing time, but you can use the FASTFIRSTROW hint if you want to take advantage of the nonclustered index to avoid the sort, and have the first few rows returned quickly.

Be careful if you try to do a cost comparison of queries with and without the FASTFIRSTROW hint. Look at the two plans below:

Comparing the two plans makes it look like the query with the hint is infinitely faster the query without the hint. However, if you look at the details for the nonclustered index scan, as shown in the pop-up properties box, you can see that the way the optimizer comes up with this plan is by assuming only one row will be returned. It optimizes as if only one row will be accessed, which is why the nonclustered index is chosen, but during execution it will retrieve all the rows. So of course a plan for accessing one row will be considered MUCH faster than a plan to access the entire table (31465 rows).

The documentation for this hint can be a little misleading. You might think using the hint indicates that the plan should get the first row quickly, and then get all the rest of rows using perhaps a different access method, so they will ALL come back as quickly as possible (which would then mean a sort), it actually means that the optimizer should just come up with a plan for getting the first row as quickly as possible. Period. (Then whatever plan was chosen for the first row will also be used for all the rest of the rows.)

This FASTFIRSTROW hint is listed in the SQL Server Books Online as a deprecated feature, which means it may be removed in a future version. However, it is still available in SQL Server 2008. Microsoft recommends using the FAST N query hint (in the OPTION clause):

SELECT * FROM Sales.SalesOrderHeader
ORDER BY CustomerID
OPTION (FAST 1)

With this hint, you can specify an value for N, and the optimizer just assumes there are N rows, and comes up with the best plan as if there were that number. As an exercise, you might want to try determining at what value for N the optimizer will switch from using an nonclustered index scan to using a clustered scan plus SORT.

Today, a reader asked me a question about the FASTFIRSTROW hint and wanted to know if we should "use such a hint for large data sets [e.g. OLTP queries]".

Of course, the answer is the usual: It depends.

On the one hand, using this hint to avoid a sort can be a good thing, because sorting a large data set can use a lot of system resources (time and tempdb). But on the other hand, if you're really running OLTP queries, there should only be a few rows you're dealing with in any query, and then the value of this hint might not be as noticeable. So you should run your own tests and see if you like the results. Note that FAST N or FASTFIRSTROW is not the default, and that is probably for a good reason. Try running your queries first with whatever plan the optimizer comes us with, and only if you're not satisfied with the performance, you can try using a hint.

Have fun!

~Kalen

Geek City QUIZ: What happens when you change a column in an index from a key column to an included column?

Kalen Delaney — Mon, 24 Nov 2008 07:15:00 GMT

This quiz is not really a generic question about changing an index key column to be an included column; it's about a behavior noticed by a reader in one particular query. Dejan Nakarada-Kordic from New Zealand sent me a very interesting puzzle. He had a reproducible query for which he thought an existing nonclustered index should be used, and it only ended up being used if the column was defined as an INCLUDED column instead of a key column. Here is the script Dejan sent me:

-- First, create the table
IF EXISTS (SELECT * FROM sys.tables
            WHERE schema_id = 1 and name = 'Table1')
     DROP TABLE dbo.Table1;
GO
CREATE TABLE dbo.Table1(
    Transaction_Serial_No [bigint IDENTITY(1,1) NOT NULL,
    Channel] char(4) NOT NULL,
    Retry_Counter int NOT NULL,
CONSTRAINT PK_Table1 PRIMARY KEY CLUSTERED
       (Transaction_Serial_No));
GO

--populate the table with 10000 rows
SET NOCOUNT ON;
declare @counter int;
set @counter = 0;
while (@counter < 10000)
begin
    set @counter = @counter + 1;
    insert into dbo.Table1(channel, retry_counter)
    values('ch1', 0);
    insert into dbo.Table1(channel, retry_counter)
    values('ch2', 0);
end;

-- Now build a nonclustered index on
IF EXISTS (SELECT * FROM sys.indexes
            WHERE object_id = OBJECT_ID('dbo.Table1') AND name = 'IX_Channel')
    DROP INDEX IX_Channel ON dbo.Table1;
GO
CREATE NONCLUSTERED INDEX IX_Channel ON dbo.Table1 (Channel, Retry_Counter);
GO

-- Examine the query plan for this query:
SELECT TOP(20) Transaction_Serial_No
        FROM dbo.Table1
WHERE Channel = 'ch2'
         AND Retry_Counter <= 10
ORDER BY Transaction_Serial_No;

The plan should show you a Clustered Index Scan being performed, even though the nonclustered index appears to be a covering index.

The query contains all 3 columns used in the query. The columns Channel and Retry_Counter are defined index keys, and because the table has a clustered index, the clustered key Transaction_Serial_No is also part of the index.

If you rebuild the index to use Retry_Counter as an INCLUDED column, the plan changes.

CREATE NONCLUSTERED INDEX IX_Channel ON dbo.Table1 (Channel)
INCLUDE ( Retry_Counter) WITH (DROP_EXISTING = ON);

-- Examine the plan again:

SELECT TOP(20) Transaction_Serial_No
FROM dbo.Table1
WHERE Channel = 'ch2'
AND Retry_Counter <= 10
ORDER BY Transaction_Serial_No;

The plan now shows a nonclustered index seek:

WHY should changing the column from a key column to an INCLUDED column change the plan?

You can try to figure out the answer for yourself, or read on.

-------------------------------------------------------------------------------------------------------------------------

It turns out that there are two extra factors to consider.

1) Although covering indexes are a great thing, and the optimizer will choose them over other possible indexes most of the time, the cost of sorting can sometimes outweigh the benefit of a covering index.

2) When a column is an INCLUDED column in an index, it comes after all the key columns and after the clustered index key that is always part of a nonclustered index on a table that has a clustered index.

So, the original index on (Channel, Retry_Counter) is the same as an index on (Channel, Retry_Counter, Transaction_Serial_No), but moving Retry_Counter to be an INCLUDED column changes the index to be on the columns (Channel, Transaction_Serial_No), with Retry_Counter in last place, and unsorted.

The query wants the data sorted on Transaction_Serial_No, and scanning the clustered index gives us the data in Transaction_Serial_No order. The first nonclustered index is sorted first by Channel, then by Retry_Counter, then by Transaction_Serial_No so that index is not useful for the sort.

The second nonclustered index is sorted first by Channel, then by Transaction_Serial_No. BUT the query has limited the data to only data with the Channel value equal to 'ch2', so since the first column values we're retrieving are all the same, returning data in the nonclustered index order will return the data in Transaction_Serial_No order and no sorting needs to be done.

You might notice in this data set that all the values for Retry_Counter are also identical, so you might then think we should be able to use the first nonclustered index to avoid having to sort the data, but the optimizer cannot be sure that the Retry_Counter values are all identical. The statistics might indicate that all the values are the same, but the optimizer can't be sure the statistics are 100% up to date.

Here are some things to try:

1) If you remove the ORDER BY, you will see that the first index, with no INCLUDED column, is used.

2) If you change the second condition to searching for a constant (AND Retry_Counter = 0), the first index can be used. If both of the first two index columns are constants in the retrieved data, it will be sorted by the third column (Transaction_Serial_No).

3) If you force the query to use the nonclustered index when Retry_Counter is a key, you'll see that SQL Server has to do a sort:

DROP INDEX IX_Channel ON dbo.Table1;
GO
CREATE NONCLUSTERED INDEX IX_Channel ON dbo.Table1 (Channel, Retry_Counter);
GO
SELECT TOP(20) Transaction_Serial_No
        FROM dbo.Table1 WITH (index = ix_channel)
    WHERE Channel = 'ch2'
        AND Retry_Counter <= 10
ORDER BY Transaction_Serial_No;
GO

Notice that the SORT operation is estimated to be 95% of the total query cost, so SQL Server would definitely like to avoid that if possible.

So the issue wasn't really because of INCLUDED columns, it was because of the order the columns appeared in the index, and the fact that SQL Server wants to try to avoid sorting whenever possible.

Have fun!

~Kalen

Did You Know? Forcing a nonclustered index scan to avoid sorting

Kalen Delaney — Sun, 22 Jul 2007 17:13:00 GMT

Hopefully, if you know enough about SQL Server to understand most of my posts here, you're aware of the fact that using a nonclustered index is not always an optimal choice for accessing data, particularly if there are thousands (or more) rows of data you need to retrieve. However, we should never say 'never'.

In general, if you have a query that is sorting on a column that has a nonclustered index, and needs to retrieve columns that are not part of the index, the optimizer will choose to scan the table (or clustered index, which is the same thing) and sort the data. The optimizer usually estimates that the time needed to scan the table plus the time to sort is going to be less than the time to follow each bookmark individually from the nonclustered index. And in some cases it might be right.

In other cases, it might not be, and the only way to verify that is to force SQL Server to use the nonclustered index, with a Lookup into the table or clustered index for each row. However, if you try to force this behavior with an INDEX hint, you might be surprised. Using a hint that tells the optimizer what index to use does not tell the optimizer HOW to use that index. It might perform a scan with lookup for every single row, or it might scan the nonclustered index, sort the index rows in the order of the clustered index and then access the clustered index using the sorted data. I've seen other plans as well and in this post, I'm not going to what the different plans actually mean.

What I want to tell you now is a way to force SQL Server to perform a scan of the nonclustered index and then a bookmark lookup for every row. You can do that with a table hint called FASTFIRSTROW. This hint tells the optimizer to choose a plan that returns the first row as quickly as possible. The default plan has to sort the entire table before any rows are returned at all. However, the nonclustered index already has the nonclustered key values sorted, and if that is the column used in the ORDER BY, following the leaf level of the nonclustered index should give us the rows already in correct sorted order. Yes, in some cases it might take longer to get ALL the rows in the table, following the bookmark for each row, but the first row will always be available fast.

It turns out that there are some cases where the FASTFIRSTROW hint can actually return all the rows more quickly than the default SORT. If you have lots of rows in your table (hundreds of thousands, or millions) you might find the FASTFIRSTROW hint ends up being faster. The only way to know for sure is to test it with your data.

Itzik Ben-Gan did some testing with different ways of getting sorted data, and if you are a subscriber to SQL Server Magazine, you can read about his tests here:

http://www.sqlmag.com/Articles/Index.cfm?ArticleID=94775&DisplayTab=Article

If you want to run some tests of your own, here is some code to get you started.

-- First, make a copy of the Sales.SalesOrderDetail table in the AdventureWorks database

USE AdventureWorks
GO
IF OBJECT_ID('dbo.details', 'U') IS NOT NULL
DROP TABLE dbo.details
GO
CREATE TABLE details (
[SalesOrderID] [int] NOT NULL,
[SalesOrderDetailID] [int] NOT NULL,
[CarrierTrackingNumber] [nvarchar](25) NULL,
[OrderQty] [smallint] NOT NULL,
[ProductID] [int] NOT NULL,
[SpecialOfferID] [int] NOT NULL,
[UnitPrice] [money] NOT NULL,
[UnitPriceDiscount] [money] NOT NULL CONSTRAINT [DF_SalesOrderDetail_UnitPriceDiscount] DEFAULT ((0.0)),
[LineTotal] AS (isnull(([UnitPrice]*((1.0)-[UnitPriceDiscount]))*[OrderQty],(0.0))),
[rowguid] [uniqueidentifier] ROWGUIDCOL NOT NULL CONSTRAINT [DF_SalesOrderDetail_rowguid] DEFAULT (newid()),
[ModifiedDate] [datetime] NOT NULL CONSTRAINT [DF_SalesOrderDetail_ModifiedDate] DEFAULT (getdate()),
)
GO

-- Next, insert data into the new table

INSERT INTO details
(SalesOrderID, SalesOrderDetailID, CarrierTrackingNumber, OrderQty, ProductID, SpecialOfferID,
UnitPrice, UnitPriceDiscount, rowguid, ModifiedDate)
        SELECT SalesOrderID, SalesOrderDetailID, CarrierTrackingNumber, OrderQty, ProductID, SpecialOfferID,
             UnitPrice, UnitPriceDiscount, rowguid, ModifiedDate
        FROM Sales.SalesOrderDetail
GO

-- Now create a clustered and nonclustered index on the new details table

CREATE CLUSTERED INDEX
idx_cl_col1 ON dbo.details(SalesOrderID);
CREATE NONCLUSTERED INDEX
idx_nc_col2 ON dbo.details(ProductID);
GO

-- First look at the plan with no hints

SELECT * FROM dbo.details
ORDER BY ProductID

-- Now look at the plans with the two different index hints.

SELECT * FROM dbo.details
WITH (FASTFIRSTROW)
ORDER BY ProductID

SELECT * FROM dbo.details
WITH (INDEX (idx_nc_col2))
ORDER BY ProductID

-- As you add more rows to your table, the plan for the query using the INDEX hint might change.
-- You can add more rows by just rerunning the INSERT statement from above, as many times as you would like.

Have fun!

~Kalen