Seek or scan?

One very common question that I see on the forums is on index seeks and index scans. A query is resulting in a table/clustered index scan, even though there’s an index on one or more of the columns been searched on.

One of the more common reasons that this happens is because the index in question is not covering, and SQL has determined that the cost of doing the lookups to fetch the extra columns is higher than the cost of scanning the entire table.

If an index does not cover a query, then bookmark lookups are required to get the additional columns, bookmark lookups are run one row at a time, and are seeks on the clustered index. Hence it’s clear that bookmark lookups on a large number of rows are exceedingly expensive and that is why SQL will switch to a clustered index/table scan when lookups are required on a significant percentage of the rows in the table.

So, what constitutes a significant percentage of the rows in the table? 50%? 20%? 10%?

The answer’s often surprising. It’s under 1% of the total rows in the table.

Here’s some test code to demonstrate that.

Setup code:

CREATE TABLE dbo.SeekOrScan(
 ID int IDENTITY(1,1) NOT NULL primary key,
 SomeNumber int,
 padding char(100)
)

CREATE NONCLUSTERED INDEX idx_SeekOrScan ON dbo.SeekOrScan (SomeNumber)

Test code:

insert into SeekOrScan (SomeNumber)
select top 1000000 0
from master..spt_values a cross join master..spt_values b
where a.name is null and b.name is null

update SeekOrScan set SomeNumber = ID -- just so we've got sequential numbers for the between
GO

dbcc freeproccache

select * from SeekOrScan
where somenumber between 1 and 100000 -- 10% of table
-- Clustered index scan

dbcc freeproccache

select * from SeekOrScan
where somenumber between 1 and 50000 -- 5% of table
-- Clustered index scan

dbcc freeproccache

select * from [SeekOrScan]
where somenumber between 1 and 10000 -- 1%
-- Clustered index scan

dbcc freeproccache

select * from [SeekOrScan]
where somenumber between 1 and 5000  -- 0.5% of table
-- clustered index scan

dbcc freeproccache

select * from [SeekOrScan]
where somenumber between 1 and 3000  -- 0.3% of table
-- nonclustered index seek

So somewhere around 0.4% of the table, the index seek with key lookup became more expensive than a table scan.

12 Responses to “Seek or scan?”

  1. Another reason to make sure you create covering indexes

    Jack D Corbett said this on January 9th, 2009 at 00:09

  2. [...] Seek or Scan? Gail provides some insight as to why you might be seeing an index scan instead of an index seek and why you should be using covering indexes. [...]

    Links for the week of 2009-01-09 | facility9 said this on January 9th, 2009 at 14:03

  3. Jack: True, though, while the INCLUDE means that all queries can be covered, IMHO not all queries should be covered. Sometimes the size or number of indexes required to cover *everything* means it’s just not worth it.

    Gail said this on January 10th, 2009 at 11:01

  4. I tested the above code and noticed that I either get Clustered index scans or a an index seek joined onto a Clustered index seek. I didn’t see any bookmarks or key lookups? Have I missed something or was the intention to show that a scan can be better than two seeks?

    Christopher Stobbs said this on January 23rd, 2009 at 17:36

  5. Let me guess, SQL 2005 RTM or SP1?

    The operator was called a bookmark lookup in SQL 2000 and before. In SQL 2005 SP2 and later it was a key lookup.

    In SQL 2005 RTM and SP1 it appeared as a clustered index seek, and hence often went unnoticed (because clustered index seeks are good)

    Gail said this on January 23rd, 2009 at 18:26

  6. he he he Yip SP1, I’ve tried it on another machine and it all seems good :-) thanks for that

    Christopher Stobbs said this on January 26th, 2009 at 11:10

  7. [...] Seek or scan? – how does SQL Server determine when to pick one over the other? [...]

    Now syndicating Gail Shaw and Kendal Van Dyke | Brent Ozar - SQL Server DBA said this on February 11th, 2009 at 01:11

  8. Even creating a covering index in this instance will still yield a clustered index scan if the columns on which the covering index are defined is not part explicitly stated in the SELECT clause ,until the point where the ratio of rows like Gail illustrated above is reached.

    If we changed one of the statements above to :

    select somenumber from [SeekOrScan]
    where somenumber between 1 and 50000

    Then we see a non clustered index seek

    Cedric said this on March 18th, 2009 at 14:14

  9. Cedric, are you saying that if I create an index (SomeNumber) INCLUDE (id, padding) and then run “select * from [SeekOrScan] where somenumber between 1 and 50000″ that I’ll still get a clustered index scan?

    Sure, if you just specify the indexes column in the select it will be an index seek, because no bookmark lookup is required, the index alone can satisfy the query. It’s only when there’s a bookmark lookup that there’s a ‘tipping point’

    Gail said this on March 18th, 2009 at 16:41

  10. Sorry I should have specifically mentioned that I was refering to the index defined as : CREATE NonCLUSTERED INDEX [idx_SeekOrScan] ON [dbo].[SeekOrScan] (SomeNumber) my tiping point seems to different than yours.I need more information in this regard.I will do some more investigation .

    Agreed that if you add the INCLUDE (id, padding) that a non clustered index seek will be used.

    I should have maybe worded my post differently . If I include the SomeNumber field explicitly in my select list as the only field then the non clustered index seems to be covering even if I add the ID field it still used the non clustered index seek ,but as soon as I add the padding field the query plan swings around to a clustered index scan

    Does all this mean that depeinding on your select list that the tipping point can potentially be different if you explicitly state your field list ?

    Cedric said this on April 16th, 2009 at 01:56

  11. No. It’s because the ID column is part of that nonclustered index. ID is the clustered index key and hence is part of all nonclustered indexes because it’s the row’s address. (see – http://sqlinthewild.co.za/index.php/2009/02/09/all-indexes-are-unique/)

    So your query with ID and SomeNumber was reading a covering nonclustered index.

    Gail said this on April 16th, 2009 at 10:10

  12. Any thoughts on this related post on Stack Overflow? Mike M. referenced this article, but at this time of writing, we’re still a little confused …

    http://stackoverflow.com/questions/3056321/sql-2005-indexed-queries-slower-than-unindexed-queries

    Jason said this on June 16th, 2010 at 23:49

Leave a Reply