Key lookups and the tipping point

In one line: when a nonclustered index finds the rows but lacks some of the columns, each row costs a key lookup into the clustered index. Past a certain number of rows, the optimizer decides one scan of the whole table is cheaper. That point is about pages, not a percentage of rows.

Run it yourself: the scripts that reproduce everything on this page are in sqlserver-demos/tipping-point on GitHub.

What you’ll see

  • A query that seeks for small date ranges or customers and suddenly scans the whole table for slightly bigger ones.
  • Thousands of key lookups in a plan, about 3 reads per row in the demo.
  • “The optimizer chose a scan, but when I force the index it’s faster.”

Why it happens

A seek plus lookups costs roughly the clustered index’s depth for every row. A scan costs the table’s page count, however many rows match. The optimizer switches close to where the two cross. In the demo that was 10% past the crossing on one table and 14% short on the other.

Because it’s a page count, the same rows tip at different percentages. A narrow table flipped to a scan at 0.26% of its rows, and a wide one at 1.08%. The “about 0.5%” rule of thumb is the wrong unit.

The optimizer also prices lookups as random reads from disk. On a warm cache, at the point it switched to the scan, the lookups were 8 to 13 times cheaper on CPU. That makes the choice conservative, which is the safe way to be wrong, and it’s why forcing the seek on a warm development box looks faster.

What to do

  • Cover the query. Add the missing columns as INCLUDEs, and there are no lookups and nothing to tip. In the demo, one INCLUDE column turned a 40,150-read scan into a 115-read seek.
  • Fix the estimate. A query whose row estimate is wrong lands on the wrong side of the tipping point. See the ascending-key problem.

What doesn’t help

  • Index hints to force the seek. They lock in a plan that’s terrible when the row count grows. Cover the query instead.
  • Reasoning in percentages of the table. Row width moves the tipping point by a factor of four.

Check your server

-- Cached plans with key lookups, costliest first.
-- Shredding plan XML is expensive on a large cache: run it off-peak.
WITH XMLNAMESPACES (DEFAULT 'http://schemas.microsoft.com/sqlserver/2004/07/showplan')
SELECT TOP (20)
       qs.execution_count,
       AvgReads = qs.total_logical_reads / NULLIF(qs.execution_count, 0),
       st.text
FROM sys.dm_exec_query_stats AS qs
CROSS APPLY sys.dm_exec_sql_text(qs.sql_handle)    AS st
CROSS APPLY sys.dm_exec_query_plan(qs.plan_handle) AS qp
WHERE qp.query_plan.exist('//IndexScan[@Lookup="1"]') = 1
ORDER BY qs.total_logical_reads DESC;

See it happen

The tipping-point demo sweeps from 1,000 to 50,000 rows on a narrow and a wide table with the same rows. It bisects the exact flip point to within 50 rows, compares warm-cache CPU, and shows the covering index.

Related: the ascending-key problem · missing-index suggestions · deadlock patterns

Measured on SQL Server 2022 CU25 (16.0.4255.1), 8 schedulers. Your numbers will differ; the behaviour shouldn’t.

Part of SQL Server Demos: short explanations of SQL Server problems, each backed by a runnable demo in MarlonRibunal/sqlserver-demos on GitHub. Written with the help of AI; every number comes from running the demo on SQL Server. How this was made.

Verified by MonsterInsights