Index Examples and Tradeoffs

[Craig_Freedman]

First published on MSDN on Jul 13, 2006

The optimizer must choose an appropriate “access path” to read data from each table referenced in a query.  The optimizer considers many factors when deciding which index to use, whether to do a scan or a seek, and whether to do a bookmark lookup.  These factors include:

1. How many I/Os will a seek or scan of the index perform?


2. Are the keys of the index suitable for evaluating a predicate in the query?


3. How selective is the predicate?  (That is, what percentage of the total rows in the table qualifies for this predicate?  The lower this number the better.)


4. Does the index cover all of the necessary columns?

In this post, I’m going to give some examples of how these factors interact.

Schema

I’ll use this schema for all of the following examples:

create table T (a int, b int, c int, d int, x char(200))

create unique clustered index Ta on T(a)

create index Tb on T(b)

create index Tcd on T(c, d)

create index Tdc on T(d, c)

If you want to try the examples, I populated the table using the following script:

set nocount on

declare @i int

set @i = 0

while @i < 100000

begin

insert T values (@i, @i, @i, @i, @i)

set @i = @i + 1

end

I/O example

Consider this query:

select a, b from T

This query has no WHERE clause so we must use a scan.  However, there are two indexes we can scan.  There is the clustered index Ta and there is the non-clustered index Tb.  Both of these indexes cover columns a and b.  However, the clustered index also covers columns c and x.  Because column x is a char(200), the total width of each row in the clustered index is over 200 bytes, fewer than 40 rows fit on each 8K page, and the index requires more than 2,500 pages to store all 100,000 rows.  In contrast, the total width of each row in the non-clustered index, is only 8 bytes plus some overhead, hundreds of rows fit on each page, and the index requires fewer than 250 pages to store all 100,000 rows.  By scanning the non-clustered index, we can execute the query while performing many fewer I/Os.

Thus, the better plan is:

|--Index Scan(OBJECT:([T].[Tb]))

Note that we can use sys.dm_db_index_physical_stats to compare the indexes:

select index_id, page_count

from sys.dm_db_index_physical_stats

(DB_ID('tempdb'), OBJECT_ID('T'), NULL, NULL, NULL)

index_id    page_count
----------- --------------------
1           2858
2           174
3           223
4           223

We can also use stats I/O and index hints to compare the number of I/Os for the two possible plans:

set statistics io on

select a, b from T with (index(Ta))

Table 'T'. Scan count 1, logical reads 2872, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

select a, b from T with (index(Tb))

Table 'T'. Scan count 1, logical reads 176, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Selectivity example

Consider this query:

select a from T

where c > 150 and c < 160 and d > 100 and d < 200

This query has two different predicates that we might use for an index seek.  We can use the predicate on column c with the non-clustered index Tcd or we can use the predicate on column d with the non-clustered index Tdc.  (Refer to my post on seek predicates for an explanation of why we cannot use a single index to satisfy both inequality predicates.)

The optimizer looks at the selectivity of the two predicates to determine which index to use.  The predicate on column c selects only 9 rows while the predicate on column d selects 99 rows.  Thus, it is cheaper to seek using the index Tcd and evaluate a residual predicate on column d for 9 rows than it is to seek using the index Tdc and evaluate a residual predicate on column c for 99 rows.

Here is the plan:

|--Index Seek(OBJECT:([T].[Tcd]), SEEK:([T].[c] > (150) AND [T].[c] < (160)),  WHERE:([T].[d]>(100) AND [T].[d]<(200)) ORDERED FORWARD)

Seek vs. scan example

Consider these two queries:

select a from T where a between 1001 and 9000

select a from T where a between 101 and 90000

As you might expect, for the first query, the optimizer chooses a clustered index seek to satisfy the predicate on column a.  Here is the plan:

|--Clustered Index Seek(OBJECT:([T].[Ta]), SEEK:([T].[a] >= CONVERT_IMPLICIT(int,[@1],0) AND [T].[a] <= CONVERT_IMPLICIT(int,[@2],0)) ORDERED FORWARD)

(Note that the parameters in this plan are due to auto-parameterization.  When we execute this plan, @1 has the value 1001 and @2 has the value 9000.)

For the second query, instead of the clustered index seek, the optimizer chooses an index scan of the non-clustered index Tb and uses a residual predicate for the WHERE clause.  Again, here is the plan:

|--Index Scan(OBJECT:([T].[Tb]),  WHERE:([T].[a]>=(101) AND [T].[a]<=(90000)))

What happened?  The predicate on the first query selects 8,000 out of 100,000 rows; this is about 8% of the table or about 230 pages of the clustered index.  The predicate on the second query selects 89,000 rows; this is nearly 90% of the table and if we were to use the clustered index it would mean touching over 2,500 pages.  By comparison, we can scan the entire non-clustered index Tb and touch only 174 pages.  Thus, the optimizer chooses the plan that requires significantly fewer I/Os.

Seek with bookmark lookup vs. scan example

Consider these two queries:

select x from T where b between 101 and 200

select x from T where b between 1001 and 2000

We again have two plans from which to choose.  We can scan the clustered index directly and apply the predicate on column b as a residual.  Or, we can use the non-clustered index Tb and perform a seek using the predicate on column b then do a bookmark lookup on the clustered index to get the value of column x for each qualifying row.  In my bookmark lookup post , I explained that bookmark lookups perform random I/Os which are very expensive.  Thus, the plan with the bookmark lookup is only a good plan when the seek predicate is very selective.

The first query touches only 100 rows and the optimizer concludes that the bookmark lookup is worthwhile:

|--Nested Loops(Inner Join, OUTER REFERENCES:([T].[a], [Expr1005]) ...)
|--Index Seek(OBJECT:([T].[Tb]), SEEK:([T].[b] >= (101) AND [T].[b] <= (200)) ...)
|--Clustered Index Seek(OBJECT:([T].[Ta]), SEEK:([T].[a]=[T].[a]) LOOKUP ...)

The second query touches 1,000 rows.  Although this is still only 1% of the table, the optimizer concludes that 1,000 random I/Os are more expensive than 2,800 sequential I/Os and opts for the clustered index scan:

|--Clustered Index Scan(OBJECT:([T].[Ta]), WHERE:([T].[b]>=(1001) AND [T].[b]<=(2000)))

Next up … Joins

There are still more topics and issues related to indexes, scans and seeks, and so forth, but I think it’s time to move on to something new so with my next post I’m going to start writing about joins.  As always, I’m interested to hear what you have to say.  If you have any comments or feedback, please let me know.