Execution plans and the statistics behind them

The optimizer turns a query into a plan: a tree of physical operators. It picks the plan with the lowest estimated cost, and every cost starts from an estimate of how many rows each operator will produce. When a query is slow, the first question is usually where that estimate went wrong.

Getting a plan

• Estimated plan — compiled, not run. SET SHOWPLAN_XML ON (alone in its batch) or Ctrl+L in SSMS.
• Actual plan — the same plan plus what happened at run time: actual rows, executions, memory grants, warnings. SET STATISTICS XML ON or Ctrl+M in SSMS.
• Query Store — keeps plans and run-time statistics per database over time, so you can see that a query got a new plan on Tuesday.

Reading one

Data flows from right to left: the leaf operators on the right read tables and indexes, and rows move left towards the SELECT node. A thicker arrow means more rows. The percentages next to each operator are estimated costs, even in an actual plan.

Operators worth recognising:

• Index Seek / Index Scan / Clustered Index Scan / Table Scan — how a table or index was read.
• Key Lookup (with a Nested Loops join) — fetching missing columns per row from the clustered index; the fix is often INCLUDE.
• Nested Loops, Merge Join, Hash Match — the three join algorithms: for small outer inputs, for two inputs sorted on the join key, and for large unsorted inputs.
• Sort, Hash Match (Aggregate), Stream Aggregate — ordering and grouping. A Sort or Hash that spills to tempdb shows a warning.
• Parallelism (Gather Streams and friends) — the plan runs on several threads.

The single most useful comparison is Estimated Number of Rows against Actual Number of Rows on each operator. When they differ by an order of magnitude, the operators to its left were probably chosen for a different number of rows than they received.

Where estimates come from: statistics

Each index, and each column the optimizer has needed, has a statistics object: a header, a density vector, and a histogram over the leading column of up to 200 steps. Each step has:

• RANGE_HI_KEY — the upper bound value of the step;
• EQ_ROWS — rows equal to that value;
• RANGE_ROWS — rows strictly between the previous step's key and this one;
• DISTINCT_RANGE_ROWS and AVG_RANGE_ROWS — distinct values in that range, and rows per distinct value.

For col = value, the optimizer uses EQ_ROWS if the value is a step key, and roughly AVG_RANGE_ROWS if it falls inside a step's range. A range such as col < value is estimated by adding up steps: all the steps below the boundary, plus some or all of the step it falls in.

With more distinct values than 200, most values do not get a step of their own. They are summarised inside a step's range, and the estimate for any one of them is the range's average, which is only right if the values in that range are evenly spread.

Statistics are updated automatically after enough rows change, which on a large table can be long after the data has drifted. Values newer than the histogram's last step (yesterday's orders, the next identity range) are the classic case of a wrong estimate.

Common mistakes

• Reading a plan left to right and blaming the SELECT operator.
• Trusting the cost percentages as measurements. They are estimates; compare estimated and actual rows instead.
• Treating every scan or Key Lookup as the problem. A lookup for three rows is cheap; for three hundred thousand it is not.
• Ignoring stale statistics. A plan built for 10 rows that meets 100,000 rows keeps its Nested Loops anyway (only a batch-mode Adaptive Join can switch strategy at run time).

What interviewers ask

• Estimated versus actual plan? Same shape; the actual plan adds what happened at run time, most importantly actual row counts.
• What would you look for first in a slow plan? Large gaps between estimated and actual rows, then expensive lookups, sorts and spills.
• Where do row estimates come from? Statistics: the histogram for the leading column and the density vector for combinations.