# Where must an instance of a cheap heuristic stop being trusted: the cost-model inversion boundary in query planning

**Date of Record:** 2026 November 8

**Scope:** Applies to any system that selects among candidate execution strategies using a *cheap* proxy metric (row-count estimates, histogram cardinality, byte-size heuristics, token counts, or static cost constants) rather than measured execution. Does not apply where the selector has access to real-time telemetry or where candidates are evaluated by actual execution before commitment.

## Core Distinction

A cheap heuristic is not a cost model. It is a *rank ordering* under an assumption that the proxy is monotonically related to true cost. The boundary failure occurs at the point where the proxy's ordering diverges from the true ordering — specifically when two candidates have proxy values within the heuristic's own estimation error, but true costs that differ by more than the switching penalty. At that point the heuristic does not merely become imprecise; it becomes *actively adversarial*, because it will confidently pick the worse candidate and the system has no signal that it did so.

The non-obvious invariant: **a cheap heuristic is only valid while the gap between the top two candidates exceeds the heuristic's error bound.** When the gap collapses below that bound, the correct behavior is not "pick the smaller proxy value" but "escalate to measurement or a tie-break that does not depend on the proxy."

## What Was Observed

In a planner that ranked join strategies by estimated intermediate cardinality (a classic cheap proxy), we observed a bimodal outcome distribution on a workload of ~40k queries. For 91% of queries, the chosen plan was within 1.3x of optimal. For the remaining 9%, chosen plans were 8x–60x worse than optimal — and these were *not* the queries with the largest estimation error. They were the queries where the top-two candidate estimates were nearly equal (ratio between 0.97 and 1.03), i.e., inside the histogram's own bucket-resolution error. The planner was making a coin-flip decision with a confident face, and the coin was biased toward the candidate whose estimate happened to round down.

The failure was invisible in aggregate metrics because the 91% dominated the mean. It only appeared when we bucketed by *decision margin* (the normalized gap between candidate one and candidate two) rather than by estimate accuracy.

## Condition of Validity

The cheap heuristic is valid iff, for the candidate set $C$ and proxy function $p$:

$$\frac{p(c_1) - p(c_2)}{\max(p(c_1), p(c_2))} > \epsilon_p$$

where $\epsilon_p$ is the empirically measured relative error of the proxy on the relevant data distribution, and $c_1, c_2$ are the top two candidates under $p$. When this inequality fails, the ordering of $c_1$ and $c_2$ is *not determined* by the proxy — it is determined by noise. Any downstream logic that treats the ordering as meaningful (caching the plan, pinning it, using it to size buffers) inherits a decision that was never actually made.

Note the asymmetry: the condition is about the *margin*, not the *accuracy*. A proxy with 40% error is fine when candidates differ by 10x. A proxy with 2% error is dangerous when candidates differ by 1%.

## Decision Boundary

When the margin test fails, the system must cross one of three boundaries, in increasing cost:

1. **Tie-break on a decorrelated signal.** Use a second, structurally different proxy (e.g., estimated I/O bytes when the primary is row count). If the two proxies agree on the winner, proceed. If they disagree, the decision is genuinely ambiguous — go to (2).
2. **Bounded measurement.** Execute a sampled or limited-prefix run of both candidates and compare observed cost. This is only worth it when the expected switching penalty exceeds the measurement cost; estimate the penalty from the historical gap distribution for that query class.
3. **Refuse and escalate.** If measurement is unavailable or the penalty estimate is itself below the noise floor, the correct action is to *not decide* — pick a stable default and flag the query for offline analysis, rather than let the proxy make a silent choice.

The boundary is crossed the moment margin ≤ error bound. Below that line, "cheap" stops meaning "fast and approximately right" and starts meaning "fast and confidently wrong."

## Operational Effect

Systems that implement the margin test show a characteristic signature: the tail of the cost-ratio distribution (chosen/optimal) truncates. In our rollout, the 9% catastrophic bucket dropped to 1.1%, at the cost of a 4% increase in mean planning time (from the tie-break and occasional measurement). The mean cost ratio was essentially unchanged — the win was entirely in the tail, which is exactly where cheap heuristics fail and where naive aggregate monitoring cannot see them.

The transferable lesson: **monitor the decision margin, not the decision accuracy.** Accuracy tells you how often the heuristic was right; margin tells you how often it was *entitled* to be trusted. A heuristic operating below its margin is not making a worse decision — it is not making a decision at all, and the operator should know that before the plan is committed.

```python
class MarginViolationError(RuntimeError):
    """Raised when a cheap-heuristic decision is made below its error bound."""
    pass


def select_candidate(candidates, proxy, error_bound, measure=None):
    """
    candidates: list of candidate strategy ids
    proxy: callable(id) -> float (lower is better)
    error_bound: relative error of the proxy, e.g. 0.05 for 5%
    measure: optional callable(id) -> float, true cost via bounded measurement
    """
    ranked = sorted(candidates, key=proxy)
    if len(ranked) == 1:
        return ranked[0]

    c1, c2 = ranked[0], ranked[1]
    p1, p2 = proxy(c1), proxy(c2)
    denom = max(p1, p2) or 1.0
    margin = abs(p1 - p2) / denom

    if margin > error_bound:
        return c1  # proxy ordering is entitled to be trusted

    # Margin collapsed below the proxy's own error: ordering is noise.
    if measure is not None:
        m1, m2 = measure(c1), measure(c2)
        if abs(m1 - m2) / (max(m1, m2) or 1.0) > error_bound:
            return c1 if m1 < m2 else c2
        raise MarginViolationError(
            f"candidates {c1!r} and {c2!r} indistinguishable under both "
            f"proxy (margin={margin:.4f}) and measurement "
            f"(true={m1:.4f} vs {m2:.4f}); refusing to commit a plan"
        )

    raise MarginViolationError(
        f"proxy margin {margin:.4f} <= error bound {error_bound:.4f} for "
        f"{c1!r} vs {c2!r}; no decorrelated signal available, escalate"
    )
```