Why is this key lookup required?

Question

I have an admittedly-complex query that I'm optimizing and I'm stuck on the next step. I have pinpointed the bulk of my problem to one part of my query that's doing the following Key Lookup but I'm confused both as to why it's doing this and what it's so slow. I'm not even referencing the PK in that table. I'm doing:

WHERE EXISTS
  (SELECT 1 FROM tblPriceTierQuantities [Extent8]
   INNER JOIN xxxx ON xxx=Extent8.AccountRateScheduleID
   WHERE Extent8.PriceTierID=tblPriceTiers.oid)

The details on the execution plan show as this:

That shows up as the only thing taking significant time to execute. Indeed, if I simply comment out that WHERE Extent8.PriceTierID=tblPriceTiers.oid clause, then the query is as speedy as I want it to be. The thing is, this lookup seems to be pointing to Extent8's oid and not tblPriceTier's oid field.

I'm confused why it's hitting the clustered index on that table because of this query. Nothing else in this query hits that table at all. Can you explain why this clustered lookup exists and also why it might be so slow? The ONLY columns ever referenced on this tblPriceTierQuantities table are AccountRateScheduleID and PriceTierID, NEVER oid which is the only column in this clustered index.

Answer 1

Have you updated statistics lately? Estimated Number Of Rows is 1 while Actual Number Of Rows is 10,259,536... Dated stats can lead to bad query plans (insufficient memory allocated for joins and sorts, bad join algorithm choices...).

When Auto Update Statistics is set to true on the database, SQL Server will automatically update statistics based on a percentage (around 20%) of changed rows in the statistic. This works well when tables are small but stats can get dated on bigger tables. A statistic in a table with 10000 records will automatically be updated when around 2000 of it's records get changed (and life is good). For a table with 10000000 records however, the auto update will still occur at 20% or 2000000 changed records (resulting in some very bad plans and long gaps between stat updates).

With the release of SQL Server 2008 R2 SP1 (and all future versions) the threshold can be set to a dynamic value by using trace flag 2371. This addresses the big table problem. You can read more about it here: Link

Answer 2

If you remove WHERE Extent8.PriceTierID=tblPriceTiers.oid, you're left with this:

WHERE EXISTS
  (SELECT 1 FROM tblPriceTierQuantities [Extent8]
   INNER JOIN xxxx ON xxx=Extent8.AccountRateScheduleID)

Which does not correlate to the rest of the query. SQL Server can very quickly determine a SINGLE match between [Extent8] and [xxxx] and resolve the EXISTS clause.

However, your full query is not as easy - it has a dependency on tblPriceTiers.oid, hence it is much slower. The full operation should include these steps, based on the statistics shown:

JOIN (xxx=Extent8.AccountRateScheduleID)
output: Extent8.oid (clustered key reference)

Then, using Extent8.oid, the part you showed:
Key Lookup: Extent8.oid using (above output) output: Extent8.PriceTierID

This output is then used to satisfy the correlation
Extent8.PriceTierID=tblPriceTiers.oid

If you want a better answer, you should have posted the full execution plan.