Plan Caching, Generic Plans, and the Parameter Sensitivity Problem

A prepared statement is parsed, bound, and planned once, and then executed many times with different parameter values. The saving is obvious: parsing and planning cost real time, and a query executed a thousand times a second should not be planned a thousand times. The problem is equally obvious once stated: the plan was chosen for the values supplied at planning time, and the next execution may supply values that select a hundred thousand rows where the first selected one.

The cost model has no way to represent this. It prices a plan for a specific set of constants, and a cached plan is a decision made under one assignment of those constants, applied to all others. Every system that caches plans therefore has to choose between two policies, and every policy is wrong for some workload. The engineering is in deciding which wrongness is cheaper.

What the cache actually stores

The cache entry holds more than the final plan tree. It holds the parsed statement, the bound query tree with parameter placeholders, the chosen plan, and any state the executor needs to start quickly, such as a preallocated memory context. The plan’s access path decisions, join order, and join algorithms are all frozen at the moment of planning, because re-deriving them is precisely the cost the cache exists to avoid.

Estimates, however, were computed from the parameter values present at planning time. A predicate WHERE id = $1 is estimated by looking up the selectivity for the constant that was passed. If the column has a most-common-value list and $1 happened to be a listed value, the estimate is that value’s frequency. If it was not, the estimate comes from the residual-distinct formula. Those two numbers can differ by orders of magnitude, and the plan chosen for one of them is then reused for the other.

The cache is keyed by the statement’s text plus the session’s search path and a set of type-resolution outcomes, because a plan built against one schema or one set of operator bindings is not valid against another. A change to the schema invalidates entries that depend on it, which is one of the reasons DDL takes a lock that conflicts with active queries.

Custom plans, generic plans, and the switching rule

The simplest policy is to plan for the actual parameter values on every execution and never reuse. That is a custom plan, and it is what an unprepared statement gets. It is optimal per execution and pays the planning cost each time.

The other extreme is a generic plan: plan once, with the parameter values unknown, using an average selectivity for each parameter. The average is computed from the column’s statistics, which means a predicate on a skewed column is priced as if it matched the average frequency rather than the frequency of any particular value. A generic plan is stable and cheap to reuse, and it is systematically wrong for every value that is not average. Because the selectivity enters the cost as a linear factor, the error maps directly onto the choice between access paths, which is the arithmetic of the planner cost model.

PostgreSQL’s policy is a hybrid. A prepared statement is planned afresh for each of its first five executions, so the optimizer sees the actual parameters. From the sixth execution it compares the average cost of those custom plans against the cost of a generic plan, and adopts the generic plan if the generic is not estimated to be more expensive. The reasoning is that a generic plan which costs about the same as the average custom plan is worth adopting for the saved planning time, while one that costs materially more is not.

The rule fails in a specific and common way. If the first five executions all pass the same parameter value, the average of the custom plans reflects that value, and the comparison is between a plan for that value and a plan for the average of all values. A workload that runs a report with one parameter on Monday and a different one on Tuesday may find that the plan adopted on Monday is the one Tuesday inherits. Because the decision is made once and the plan persists for the session, the failure is not self-correcting within that session.

Some systems expose the policy as a session setting, with values that force custom or generic planning unconditionally. That escape hatch exists because the automatic rule cannot know the workload’s shape. A short transaction that runs a statement once should never pay for a generic plan; a long-lived connection that runs the same statement a million times should almost always have one.

Parameter sniffing and the plans it produces

Planning with the actual values, which is what a custom plan does and what many systems do for stored procedures on first execution, is called parameter sniffing. It produces excellent plans for the sniffed values and potentially terrible plans for others.

The canonical shape of the failure is a range predicate. A stored procedure with WHERE created_at BETWEEN @start AND @end is planned when the range covers one day, producing an index seek and a nested loop into a detail table. It is then executed with a range covering a year, and the same plan performs millions of nested-loop iterations through an index that was priced for a handful of rows. The reverse also occurs: a procedure planned with a wide range uses a hash join and a scan, and the narrow-range execution pays for both.

Systems have attacked this from three directions. The first is to re-plan when the parameter values differ enough from those the plan was built for, which requires tracking what the plan was built for and comparing; Oracle’s adaptive cursor sharing does this by monitoring execution statistics per cursor and marking a cursor for re-examination when its actual row counts diverge from the estimate. The second is to compile a variant of the plan for a small number of distinct value ranges, so that a skewed column gets a plan for each of its common values. The third is to force a recompile, which is a per-statement directive in several products and is the blunt instrument of choice when a single statement’s plan is known to be value-dependent.

Each has a cost. Monitoring per-cursor statistics adds executor overhead to every execution. Multiple plan variants multiply the planning work and the cache footprint. Forced recompiles give up the entire benefit of caching for the statement they apply to.

Why the generic estimate is worse than it looks

A generic plan’s selectivity for col = $1 cannot use the most-common-value list, because the value is unknown. The estimator falls back to one of two approximations: the average frequency over all values, or the frequency of a typical non-listed value. Neither is a good model of a distribution with a long tail, and the choice between them changes the estimate by the ratio of the table’s row count to its distinct count.

The effect is amplified for range predicates. A generic plan for created_at > $1 has to assume something about where $1 falls, and the only defensible assumption is the middle of the distribution, which selects half the table. A plan built for that assumption is a sequential scan, and it is a reasonable plan for the average range and a wasteful one for a range covering the last hour.

There is a further subtlety in the cost comparison itself. The generic plan’s cost is computed with the average selectivity, and the custom plans’ costs are computed with their actual selectivities. Comparing an average-cost plan against the average of individual costs is comparing two different quantities, and the comparison is only meaningful when the distribution is not heavily skewed. On a skewed column the generic plan’s estimated cost can look lower than the average custom plan’s cost while every actual execution is worse, because the generic plan is priced at the average and the average is dominated by the common values.

What this means for the shape of a workload

The practical rule is that plan caching wants statements whose cost is insensitive to their parameters. A primary-key lookup, an insert, an update by unique key: all are priced almost identically for every value, and a generic plan is as good as a custom one. A statement whose predicate ranges over a skewed column, or whose parameter selects a variable number of rows through a join, is the opposite, and it needs either per-value planning or a plan whose cost stays flat across the range.

That flatness is sometimes achievable by changing the statement rather than the cache policy. Splitting a procedure into a narrow case and a wide case, with the caller choosing, gives each a plan built for its own shape. A recompile hint on the statement, where the product supports one, moves the decision to execution time at the cost of planning on every call. Neither is free, and both are preferable to a cached plan that silently performs the wrong access path for a year.

The deeper problem is that plan caching turns a per-query decision into a per-session state, and the session outlives the query. The mechanisms that re-plan during execution, described in adaptive re-optimization during execution, exist because the cache cannot solve this by choosing better at planning time: the information needed to choose is only available after the plan has started running.