Adaptive Plans: Choosing the Join Algorithm After Execution Starts

A plan is a commitment made before any row has been read. The cardinality estimates behind it come from statistics that describe the table at some earlier time, applied to predicates whose joint distribution no model captures exactly, and the compounding described in join cardinality and the containment assumption means the final number can be wrong by orders of magnitude. Adaptive planning is the response: keep the decision open past the start of execution, and resolve it using rows that have actually been counted.

The mechanism is narrower than it sounds. It does not re-plan the whole query at an arbitrary moment, and it does not replace the optimizer. It places a small decision point at a specific node, defers one or two choices that depend on a single cardinality, and commits once enough rows have passed to distinguish the cases. Everything outside that decision is fixed exactly as it was.

The statistics collector and the inflection point

The core component is a row counter inserted into the plan at a join, with a buffer in front of it. In Oracle’s adaptive joins the default plan is a hash join, and the collector sits on the input that supplies the hash table, which is also the table that would drive a nested loop if the plan switched. Rows from that input pass through the buffer and are counted. When the count crosses a threshold derived from the two candidate plans’ cost curves, the plan switches to the other shape.

The threshold is not a guess made at runtime. Both candidate subplans were costed during planning, and the point at which one becomes cheaper than the other is computable from those two cost functions. Planning therefore produces not just a plan but a set of subplans plus a crossover point, and execution watches for the crossover. This is why an adaptive plan can be described in advance: the decision rule is fixed at planning time even though the outcome is not.

The buffered rows serve whichever branch is taken. If the count stays below the threshold the join becomes a nested loop, and the buffer is the driving row source, so the rows already read are not lost. If the count crosses the threshold the plan stays a hash join and the same buffered rows are consumed to build the hash table. The buffer’s size is bounded by the threshold, which is what keeps the memory cost of the arrangement finite.

What the switch cannot fix

Adaptive joins resolve one cardinality: the number of rows on the input the collector watches. They do not reorder joins, they do not change access paths, and they do not revise the estimates used by operators above them. A plan whose join order was chosen from a wildly wrong intermediate cardinality remains wrong in its order, and an adaptive join inside a badly ordered tree improves a node that should not have existed in that position.

The second limitation is that the decision is local. Two joins, each adaptive, decide independently, and their decisions may be jointly suboptimal: the first chooses a shape that produces many rows, and the second’s threshold was computed assuming the first produced few. Nothing coordinates the two, because coordination would require re-costing the whole tree at runtime.

The third limitation is the buffering. The buffer must hold every row counted before the decision is made, so its size is proportional to the threshold, and a threshold large in row terms is a large buffer competing with the rest of the plan for memory. Implementations keep the threshold modest for that reason, which confines the mechanism to the regime where the estimate is off by a factor of ten or so rather than a factor of a thousand: an estimate that is wrong by three orders of magnitude crosses any small threshold immediately, so the decision degenerates into a choice made on the first few hundred rows.

Re-planning at a point where the cardinality is known

A different family of mechanisms attacks the compounding problem directly. When execution reaches a point where an intermediate result has been fully materialised, its cardinality is known exactly, and the remainder of the plan can be re-optimized with the measured value substituted for the estimate.

SQL Server’s interleaved execution applies this to multi-statement table-valued functions: the function’s body is executed first, its actual row count is reported back to the optimizer, and the plan for the statement that references it is compiled with that measured count in place of the fixed guess that a table-valued function would otherwise contribute. The mechanism is a pause in compilation rather than a mid-execution patch, which matters: the second planning pass sees real numbers, and every subsequent decision in that subtree, including join order within it, is made with them.

The precondition is a point in the plan where an intermediate cardinality becomes final, and that is a real constraint. A fully pipelined chain of joins has no such point: every operator is still producing rows while the one above it consumes them, so there is nothing to measure and nothing to re-plan. Interleaved execution gets its measurement from a function boundary, which is a natural stopping place because the function’s result set is materialised before the outer statement continues. Stage-boundary re-optimization gets it from a blocking operator, which in practice means a sort, a spool, or an exchange, so queries with ORDER BY, GROUP BY, or a parallel branch qualify and a pure chain of joins does not.

The cost is the second compilation, which is planning work paid at execution time and charged to the first execution of each such statement. Caching the recompiled portion across executions would defeat the purpose, since the measured cardinality is specific to the parameters of this execution.

Re-optimization as a loop, and its stability problem

A more aggressive form re-plans repeatedly, using the actual cardinalities observed so far to revise the plan for the remaining work. This is what several analytical engines do between stages of a query, and it handles the case where the first estimate was wrong by a factor of a thousand rather than ten. Each stage boundary is a synchronization point where all intermediate results are materialised, so the row counts are exact.

The difficulty is convergence. Each re-plan produces a plan that is optimal given the numbers seen so far, and the numbers seen so far were produced by the previous plan. A plan that produced a huge intermediate because it chose the wrong join order leads to a re-plan that chooses a different order for the remaining stages, which may produce a different distribution of rows, which changes the next re-plan. The process can oscillate, and implementations damp it by re-planning only at selected boundaries and by falling back to the original plan when a new one is not materially cheaper.

A second difficulty is that the executor’s state is shaped by the plan. A hash table built by the previous plan is discarded when the plan changes, and the work spent building it is lost. The trade is between the accuracy of a revised plan and the sunk cost of the abandoned one, and it is resolved by requiring that the new plan’s estimated saving exceed the cost of rebuilding.

Why the estimates remain the thing to fix

Every mechanism in this family is a way of paying at execution time for information that planning did not have. They convert a planning-time uncertainty into a runtime measurement, and they work when the measurement arrives early enough and cheaply enough to change a decision that has not yet been made.

None of them removes the need for good statistics. An adaptive join whose threshold is computed from two cost curves inherits any error in those curves; a re-optimized subtree inherits the errors in its own base estimates; a stage-wise re-plan cannot revise the statistics it reads, only the plan it builds from them. When a query is consistently mis-planned, the durable fix is the statistic, the extended statistic, or the predicate form, and the adaptive machinery is a safety net for the cases where that fix is unavailable.

There is also a cost that is easy to overlook: a plan whose shape depends on data is a plan whose performance cannot be predicted from its text. Two executions of the same statement produce different plans, and the plan in the cache is not the plan that ran. Diagnostics that compare a captured plan against a current one must account for this, and the buffered rows mean the switch point itself appears in execution statistics rather than in the plan.

The interaction with caching is direct and is the reason the two mechanisms are usually documented together. A cached generic plan, as described in plan caching and generic plans, is a commitment to a shape for all parameter values; an adaptive plan is a commitment to a decision rule for one execution. The first is cheaper to start and wrong across a range of values; the second is more expensive per execution and right more often within one.