Search results matching tag 'nonclustered index'

Geek City: Join With Me!

Kalen Delaney — Thu, 14 Feb 2013 22:16:00 GMT

I remember one of the most surprising changes in SQL Server ~~2000~~ 2005 was how the graphical plans showed the use of a nonclustered index to seek, and the plan included something that looked like a JOIN to find rows in the base table. Here’s an example. Although I used SQL Server 2008R2, the graphical plan will be pretty similar to what it looked like back in SQL Server ~~2000~~ 2005. My code will make a copy of a table in the AdventureWorks2008 database, and then build an index on one of the columns.

USE AdventureWorks2008;
GO
IF object_id('dbo.Sales') IS NOT NULL
DROP TABLE dbo.Sales;
GO
SELECT * INTO dbo.Sales FROM Sales.SalesOrderHeader;
GO
CREATE INDEX Sales_SalesPersonID_index on dbo.Sales(SalesPersonID);
GO

Now look at the estimated graphical execution plan for this query, that searches for a particular value for the SalesPersonID column:

SELECT * FROM dbo.Sales
WHERE SalesPersonID = 280;
GO

You should see something like this:

It shows a JOIN even though there is only one table involved! What’s with that? It took me a few minutes to figure out what I was seeing, and I must admit that over the years since then I have come to appreciate this graphical representation. You’ll have a problem if you think of a JOIN as only finding matching rows between two tables, but can be solved if you realize that a JOIN can be used when finding matches between any two ROWSETS, i.e. any two sets of rows. There is a set of rows in the nonclustered index on SalesPersonID, and a set of rows in the table. The index seek finds all the index rows with a SalesPersonID value of 280, but those index rows only contain an index key value and a row pointer (RowID or RID). Because the query is requesting all the columns in the table, not just the SalesPersonID value, SQL Server must find the rows in the dbo.Sales table that have a matching value for the RowID. Internally, it is doing a join, even though there is only one table. It is joining index rows with table rows.

If the table had a clustered index, the plan would look almost exactly the same, with one difference. In SQL Server, if a table has a clustered index, nonclustered index rows do not contain RowIDs, they contain the clustered key value to be used a pointer to the row. SQL Server can take this clustered key from the nonclustered index row and look up in the clustered index to find the desired row. So I create a clustered index on SalesOrderNumber:

CREATE UNIQUE CLUSTERED INDEX Sales_ident on dbo.Sales(SalesOrderNumber);
GO

Now when I run the same query as above, I get the following plan:

The only difference in the two plans above is the icon for the lookup into the base table. One is looking up into a heap using a RowID, which is an address containing the File ID, the page number and the slot or row number on the page. The other icon represents taking a key value from the nonclustered index row and looking it up by seeking through the clustered index. If you look again at these two icons, which one looks like a picture of directly addressing a row, and which looks like a picture of following another index into the table itself?

The icon on the left is used for a RID lookup, and the icon on the right is used for a clustered index key lookup. I know that nobody asked me, but I think they got these backwards.

But wait, there’s more…

Prior to SQL Server 7, there was basically a rule of thumb with query plans that SQL Server would use one index (at most) per table per query. It could never (well, hardly ever) use two indexes on the same table in a single query. That changed in SQL Server 7 when a new algorithm called Index Intersection was introduced.

I’m going to build another index on SalesOrderDate:

CREATE INDEX Sales_OrderDate_index on dbo.Sales(OrderDate);
GO

This index will be used if I look for all orders place on July 1, 2002. The query plan for the following query is shown:

SELECT * FROM dbo.Sales
WHERE OrderDate = '2002-07-01';

We saw that the index on SalesPersonID is useful when looking for the value 280, and the index on SalesOrderDate is useful when looking for '2002-07-01'. But what if one query looks for rows that satisfy both conditions?

SELECT * FROM dbo.Sales
WHERE OrderDate = '2002-07-01'
AND SalesPersonID = 280

Here’s the plan:

We see two JOINs ! First, SQL Server finds the sets of index rows meeting each of the WHERE filter conditions and those two index row sets are joined together, using the clustered key value as the join column. Then only after SQL Server finds rows that meets both conditions, it takes the common clustered index key and uses it to find the row in the underlying table.

But wait, there’s more!

Both of these queries use a table scan, because the filter conditions are not selective enough. There are way more rows with a SalesPersonID value of 289 than there were for a value of 280, and there are more rows with an OrderDate of March 1, 2004 than there are with an OrderDate of July 1, 2002.

SELECT * FROM dbo.Sales
WHERE OrderDate = '2004-03-01' ;
GO

SELECT * FROM dbo.Sales
WHERE SalesPersonID = 289;
GO

Both of the above queries show the same plan. Because the table now has a clustered index, the plan shows a clustered index scan, but it is exactly the same work as a table scan:

However, if you look at the plan for a query that uses both filter conditions, we don’t get a clustered index scan.

SELECT * FROM dbo.Sales
WHERE OrderDate = '2004-03-01'
AND SalesPersonID = 289;

Even though each filter alone is not very restrictive, they can both be used for index intersection. The reason SQL Server usually doesn’t choose index seeks on non-restrictive filters is because the cost of then accessing the base table for all the qualifying rows can be very high. But even though each individual index returns a lot of rows, the optimizer’s estimate of the number of rows that meet BOTH conditions is very small, and therefore the number of lookups into the base table is quite small and affordable.

So, what can you learn? Just because you think an column might not be selective enough to build a nonclustered index on, don’t discount it. If that column will frequently be used in queries with multiple conditions, it just might turn out to be more useful than you thought!

So make sure you test many possible choices of indexes and combinations of indexes before you know what the best choices are.

Have fun!

~Kalen

Geek City: Too Many Indexes!

Kalen Delaney — Sun, 18 Jan 2009 20:37:00 GMT

I wrote about "Too Many Columns" last September, and along with changes in SQL Server 2008 that allow lots of columns, there is also the ability to create more than the old maximum of 249 nonclustered indexes on a table. I knew this fact, but somehow I overlooked it when updating the chapter on table structures in my new book. My omission also got past all the editors, and I just realized my mistake when reviewing the Indexes chapter, which was being updated for SQL 2008 by Kimberly Tripp.

I found that Books Online has not been completely updated (and I have filed a doc bug on this already). This page still says the limit is 249 nonclustered indexes per table:

http://msdn.microsoft.com/en-us/library/ms190197.aspx

However, the page for CREATE TABLE at http://msdn.microsoft.com/en-us/library/ms174979.aspx does say:

Each table can contain a maximum of 999 nonclustered indexes, and 1 clustered index. These include the indexes generated to support any PRIMARY KEY and UNIQUE constraints defined for the table.

You can take my script to create a table with lots of columns, and edit it to create a UNIQUE constraint on every column.

DECLARE @create varchar(max);
DECLARE @tabname sysname;
DECLARE @numcols int;
DECLARE @col int;
SELECT @numcols = 900;
SELECT @tabname = 'wide' + CONVERT(varchar, @numcols);

SELECT @create = 'CREATE TABLE ' + @tabname +
' (ID int IDENTITY, ';

SELECT @col = 1;
WHILE @col < @numcols BEGIN
    IF (@col % 3) = 0
       SELECT @create = @create + 'col' + CONVERT(varchar, @col) +
           ' int UNIQUE,';
    IF (@col % 3) = 1
            SELECT @create = @create + 'col' + CONVERT(varchar, @col) +
             ' char(5) UNIQUE,';
     IF (@col % 3) = 2
            SELECT @create = @create + 'col' + CONVERT(varchar, @col) +
             ' varchar(25) UNIQUE,';
SELECT @col = @col + 1;
END;
SELECT @create = @create + 'col' + CONVERT(varchar, @col) +
           ' int default 0);'
PRINT @create
EXECUTE (@create)

After the table is created, you can examine sys.indexes:

SELECT name, index_id, type_desc
FROM sys.indexes
WHERE object_id = object_id('wide900');

You'll definitely see more than 249 indexes! In addition, you might note that there is a gap in the index_id values. The values 251 - 255 are not used, and this is for backward compatibility. In much older versions, index_id (or indid) 255 was reserved for the LOB data belonging to a table, and the values from 251 - 254 were reserved. So that range is still not used. But you can see that I have index_id values from 256 - 905 in this table.

So, thanks Kim~

One more place that Books Online could use a little tweaking is in the section on Programmability Enhancements:

http://msdn.microsoft.com/en-us/library/cc645577.aspx

The section on "Wide Tables" seems to imply that you need to have an XML column set in order to get 1000 indexes. It doesn't actually say that, so it's not really a bug, but it does seem to imply it:

Wide tables are tables that contain one or more column sets. A wide table can contain up to 30000 columns, 1000 indexes, and 30000 statistics.

Because you can only reach the 30000 column limit with a wide table, it seems to imply that the 1000 index limit is only for wide tables. But as my script shows, it is not. You can have up to 1024 columns in a non-wide table, and you can now have indexes on every one of those columns.

But do you want that many? That's for another post, another time...

Have fun!

~Kalen

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: String Statistics

Kalen Delaney — Wed, 13 Feb 2008 22:18:00 GMT

If you’ve ever run DBCC SHOW_STATISTICS, you know you get 3 sections of information back. The first section is basic information about the last time the statistics were updated, the number of rows, the number of steps, etc. The second section is density information for each left-based subset of columns. The third section is the histogram for the first column in the statistics. I won't be going into detail on what any of these things mean (i.e. steps, density, histogram), but you can get lots more information from this whitepaper:

Statistics Used by the Query Optimizer in Microsoft SQL Server 2005

What you might not know is that you can get each of the three sections independently by adding an option to the DBCC command:

DBCC SHOW_STATISTICS ('AdventureWorks.Person.Contact',
'IX_Contact_EmailAddress') WITH STAT_HEADER;

DBCC SHOW_STATISTICS ('AdventureWorks.Person.Contact',
'IX_Contact_EmailAddress') WITH DENSITY_VECTOR;

DBCC SHOW_STATISTICS ('AdventureWorks.Person.Contact',
'IX_Contact_EmailAddress') WITH HISTOGRAM;

These options are documented as part of the DBCC SHOW_STATISTICS command for SQL Server 2005. These options were actually available in SQL Server 2000, but they just aren’t documented.

In SQL Server 2005, the first section contains a column of output called "String Index", which I like to call "String Statistics". I just wrote an article for www.SQLCommunity.com about what these string statistics do for you.

http://www.sqlcommunity.com/default.aspx?tabid=77&id=178

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