Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I am using SQL server, and I have been looking closely at the concept of key lookups,

http://blog.sqlauthority.com/2009/10/07/sql-server-query-optimization-remove-bookmark-lookup-remove-rid-lookup-remove-key-lookup/

So if you have a key lookup you can create an index with the 'include' columns to cover the non index columns you have in the select statement.

For instance,

SELECT ID, FirstName FROM OneIndex WHERE City = 'Las Vegas'
GO

This index will include a key lookup,

CREATE NONCLUSTERED INDEX [IX_OneIndex_City] ON [dbo].[OneIndex]
(
[City] ASC
) ON [PRIMARY]
GO

But this one will remove the key lookup,

CREATE NONCLUSTERED INDEX [IX_OneIndex_Include] ON [dbo].[OneIndex]
(
City
) INCLUDE (FirstName,ID) ON [PRIMARY]
GO

I mean how much of an impact will this have on performance? The key lookup has an operator cost of 0.295969 (99%), but what does that really mean?

How do you know that you need the second index there, and at what point does it become the case that you are trying to add too many indexes and it is not worth it?

It seems to me that some queries can include index scans, key lookups, and still seem to perform very fast.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

Imagine the phone company has a list of phone numbers, including who the customer is, where they live, what their billing number is, and so on. The Primary Key could be the phone number.

They give you the White Pages. That's like a non-clustered index, which ordered by Name, including columns like the address.

If you want to find all the Farleys in the book, and are interested in their addresses, then the white pages is all you need. You can quickly Seek to the Farleys (finding the Fs, and so on), and then you have all the information you need.

But if you want their billing numbers, then you need to do a lookup. You can quickly find all the phone numbers of the Farleys, but then you need to take each of them (hundreds) and do another Seek (lookup) in the main (clustered) index, the one that's ordered by the phone number. Each of those is roughly the same cost as the seek to find the Farleys, making your query run orders of magnitude worse.

And there's a threshold. At some point, the database will realise that it's quicker just to go through every page of the clustered index, checking every record to see if it's of interest.

Seriously - get rid of Lookups. Your queries might be fast now, but probably won't scale.

share|improve this answer
    
It just seems like you end up with stacks of extra indexes, and we are using the entity framework, so the queries are generated for us, which makes it more difficult. –  peter Dec 13 '11 at 23:07
    
Our database scales quite well at the moment, but with more clients coming on board I expect some issues at some point. –  peter Dec 13 '11 at 23:08
    
How about quantifying the difference? Can you look directly at the reads in profiler? I had a query which went from 5489 -> 2607 reads when removing a key lookup. But does the reads get affected by the cache? –  peter Dec 13 '11 at 23:14
    
@Peter You're looking for an absolute answer along the lines of "do this when x", "do this when y". Indexing is as much art as it is science, it doesn't boil down to a yes/no decision tree. –  Mark Storey-Smith Dec 13 '11 at 23:25
    
Peter - you may end up including many columns, but you don't need lots of different indexes. If one query needs ColD and another wants ColP, then just include both in one index. –  Rob Farley Dec 13 '11 at 23:50
show 2 more comments

In the worst case, a query containing a lookup has to go to physical storage for rows that require column data not covered by the nonclustered index. In the very worst of worst cases, each lookup will require a separate I/O, and plan execution will have to wait for that single row's worth of data to come back before proceeding. This scenario usually has severe performance implications if the lookup has to process a significant number of rows.

And that is why lookups get such a bad press. On the other hand, consider that the ability to do lookups was introduced in SQL Server 2000. In SQL Server 7.0 the query processor could only use a nonclustered index if it contained all the information necessary to satisfy the query; in all other cases, it had to access data via a clustered index (if present, or a heap scan otherwise). If lookups were always so very bad, SQL Server would surely never have introduced it.

In SQL Server 2000+ then, where we have a nonclustered index that provides useful ordering and/or (most of) the columns required by a query, and where the number of lookups is likely to be relatively small, using the nonclustered index and performing a limited number of lookups on the base table is likely to be the cheapest available access method (though a fully-covering nonclustered index might be cheaper still, of course).

In many cases, it is just not practical to create as many nonclustered indexes as would be needed to avoid scanning the base table for all common queries. One reason might be that INSERT/UPDATE/DELETE/MERGE performance is more important that querying speed (remember that data modification operations also have to maintain all affected nonclustered indexes). Another reason might be space; each nonclustered index represents a copy of a subset of the columns of the base table (or expressions thereon) just sorted differently. More copies of the data means more storage space, and more things competing for space in SQL Server's in-memory data cache.

Other times, we can create just a few extra indexes (perhaps filtered in SQL Server 2008+) with just enough INCLUDE columns to satisfy the vast majority of performance-critical queries, without compromising data modification performance too much, and without using too much extra disk space. Balancing the competing considerations is what makes index tuning more art than science, as Mark mentions in the comments to Rob Farley's answer.

You ask what the 99% cost for the lookup operator really means in the query plan. The costing component of the query optimizer produced an estimated cost for that operation that is 99% of the total estimated for the query. The number itself (0.29) does not mean very much at all; for all practical purposes, you should consider it as a unit-less number used internally by the optimizer when comparing alternative strategies for that specific query.

The estimated cost takes no account of your hardware, configuration, application needs, or very much of anything else. The cost model used by the optimizer includes a significant number of heuristics and simplifying assumptions that happen to produce reasonable plans most of the time, for most queries, on most hardware. That's not to say that there is no correlation between high-cost operators in plans and performance; rather the link is often much weaker than commonly expected. By all means check the reasons for high-estimated-cost plan operators first, but don't treat the information as anything other than a very possibly flawed estimate.

I also want to mention a couple of factors that can ameliorate the impact of lookups. First, I mentioned right at the start that the worst case involves row-by-row physical I/O. This will obviously be avoided if the data pages (clustered index or heap) needed to satisfy the lookups are already in memory (data cache). Where this is the case, the execution time difference between a plan with a lookup versus a covering index may well be immeasurable. Even where physical I/O is required, if the number of reads is small, you still may not care. (How likely data pages for a table are to be in the data cache depends on many factors, and will be specific to your hardware and circumstances).

Where more that a little physical I/O is needed, the impact of the lookups may still be reduced by optimizations present in the query plan. Where SQL Server expects the number of lookups to be significant, it may choose to explicitly Sort the rows entering the nested loops join driving the lookup in order of the non-clustered keys. This reordering promotes sequential reading of the nonclustered index, which may be very much faster than random I/O on your hardware.

With or without an explicit Sort, the nested loops join driving the lookup may have the WithOrderedPrefetch or WithUnorderedPrefetch attributes present. In either case, the query execution engine 'looks ahead' in the index key stream driving the lookups and issues read-ahead reads. The idea is to issue asynchronous read requests to the I/O system for data pages that will be needed soon, so that by the time the lookup needs a data page, it is already present in memory.

Under ideal conditions (low fragmentation, good query plan, high-performance I/O system) the read-ahead mechanism may well be fast enough to prevent even large parallel query plans from ever waiting on I/O to complete. This is especially true in Enterprise Edition, which can issue very large single I/O requests (up to 2MB per request if memory serves). On the other hand, under less than ideal (more normal!) conditions, your query may suffer horribly as it waits on long I/O queues, or fails to drive the I/O system hard enough. The worst case performance of key lookups can be very poor indeed.

In summary, you will generally want to avoid lookups where it makes sense to do so. For small queries (that are going to remain small) you may decide that the overhead of extra indexes (space & maintenance) is not justified, given due weight to the wider needs of the system and its users.

Ultimately this is all part of the art & science that is database development and administration.

Paul

share|improve this answer
2  
Good to see you on this site, Paul. DBA.SE will only benefit from it. –  Matt M Dec 14 '11 at 2:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.