Which is better: Bookmark/Key Lookup or Index Scan

Question

I know that an index seek is better than an index scan, but which is preferable in SQL Server explain plans: Index seek or Key Lookup (Bookmark in SQL Server 2000)?

Please tell me they didn't change the name again for SQL Server 2008...

Solution 1

Index seek, every time.

Lookups are expensive, so this is covering indexes and especially the INCLUDE clause was added to make them better.

Saying that if you expect exactly one row, for example, a seek followed a lookup can be better than trying to cover a query. We rely on this to avoid yet another index in certain situations.

Edit: Simple talk article: Using Covering Indexes to Improve Query Performance

Edit, Aug 2012

Lookups happen per row which is why they scale badly. Eventually, the optimiser will choose a clustered index scan instead of a seek+lookup because it's more efficient than many lookups.

Solution 2

Key lookup is very similar to a clustered index seek (pre 2005 SP2 was named 'seek with lookup'). I think the only difference is that the Key Lookup may specify an additional PRE-FETCH argument instructing the execution engine to prefetch more keys in the cluster (ie. do a clustered index seek followed by scan).

Seeing a Key Lookup should not scare you. Is the normal operator used in Nested Loops, and Nested Loops is the run-of-the-mill join operator. If you want to improve a plan, try improving on the join and see if it can use a merge join instead (ie. both sides of join can provide rows on the same key order, fastest join) or a hash-join (have enough memory for the QO to consider a hash join, or reduce the cardinality by filtering rows before the join rather than after).

Solution 3

This SO question mentions that key lookups are something to avoid. An index seek is going to definitely be the better performing operation.

Comments

[Raven]

the content of he question asks one thing and the title a different thing....

[ZygD]

are you sure... a key lookup is a bookmark lookup = expensive, no?

[Remus Rusanu]

afaik is exactly as expensive as a seek, it translates to the same physical operation. The presence of look-ups though indicate potential problems like slonon-covering indexes. Note that with joins a lookup may better than a seek because lookups can specify pre-fetch.

[Remus Rusanu]

slonon-convering indexes => slow joins or non-covering indexes (typo)

[Remus Rusanu]

btw of course that a seek + a lookup is more expensive than just one seek, so if you can convert reduce the seek+lookup to a single seek (ie. covering index) by all means yes, is better. My point is that is nto the look-up that is the expensive vs. a seek, but why is the QO choosing a to use a lookup (ie. needs to cover the projected columns)

[ZygD]

Fair enough, I understand what you're saying. However, so you ever see a singleton key lookup? Or is alway linked to another seek/scan? Also, if the first seek/scan gives a 1000 rows, it's likely you have an intermediate sort or 1000 discrete non-contiguous lookups

[Remus Rusanu]

I think lookups are always folowing some other access operation that feeds the lookup the RID or key to look up. If the key would come straigh from the query arguments, the lookup would always be a seek afaik.

[Remus Rusanu]

To summ up, if you change a plan somehow that it replaces one lookup with one seek, nothing is gained actually. The real solution has to eliminate the cause of the lookup and produce a plan that, for instance, has one single seek where previously would use a seek and a lookup.

[ZygD]

So, we agree that lookups are bad then...? :-)

[Remus Rusanu]

Cover blanket statements are always dangerous :) but yes, lookups are a sign of problems.

[marc_s]

+1 for covering indices and the Simple-Talk link (excellent stuff)

[Brain2000]

I have found them to be suddenly introduce in some situations when a TOP statement is added, causing a query that normally took less than one second to skyrocket to about 100 seconds, especially when there are less rows than the TOP statement asked for.