PATTERN Cited by 1 source

Plan-cost-times-k estimator¶

Pattern¶

To make a pre-execution admission-control decision about a database query — before any rows are read, any locks are taken, or any CPU is spent on execution — use the database's own query planner as a free pre-execution cost oracle, then calibrate its dimensionless output into a wall-clock-time estimate via a per-(query-pattern × host) exponential-moving-average ratio k updated on every query completion.

estimated_wallclock(q)  =  planner_cost(q)  ×  k(pattern(q), host)

where  k = EMA_wallclock / EMA_cost   (per query pattern, per host)

Admit/reject the query based on estimated_wallclock(q) vs. the configured budget; update both EMAs when the query finishes.

Why this works¶

Pre-execution admission control needs a wall-clock-time estimate. Three approaches exist:

Approach	Pre-execution cost	Accuracy
Static analysis of query text	Low	Poor — misses data-dependent costs
Full query compilation + cost model from scratch	High	Poor — duplicates planner work
Reuse the database's planner + per-pattern calibration	Low (planner runs anyway)	Good — uses actual observed history

The key insight: the planner is already running before execution. The cost number is a free byproduct. The only missing piece is converting its dimensionless output to seconds — which is exactly what the per-pattern EMA learns.

Instance: PlanetScale Traffic Control¶

From sources/2026-04-21-planetscale-behind-the-scenes-how-database-traffic-control-works:

"Traffic Control implements a hash table on each host, mapping query patterns to two averages: CPU time and planner cost estimates. Both are exponential moving averages, heavily weighting recent queries. Every time a query completes, we update both of those averages. The magical not-quite-constant k is the ratio of the two. Each time a query comes in, Traffic Control multiplies the planner's estimated cost by k to guess how much CPU and/or wall-clock time the query will take. Based on that estimate, Traffic Control decides if the query can be allowed to begin. If it does, then at the end of query execution, Traffic Control updates the two averages for that query pattern so the k value will be more recent and more precise for the next query that arrives."

The estimator feeds two of Traffic Control's four pre-execution checks:

Per-query limit: planner_cost × k > budget.per_query_limit → block.
Cumulative-cost: planner_cost × k credited to the budget's reverse leaky bucket — if that would overflow, block.

Data flow¶

query arrives
    ↓
Postgres planner emits plan + cost (q.plan_cost)
    ↓
pre-execution hook reads q.pattern, looks up EMA_cost[pattern], EMA_time[pattern]
    ↓
estimated_wallclock = q.plan_cost × (EMA_time[pattern] / EMA_cost[pattern])
    ↓
admission decision (block or proceed)
    ↓
if proceed: execute query, measure actual wallclock and confirm plan_cost
    ↓
post-execution hook updates EMA_cost[pattern], EMA_time[pattern]

Both EMAs are updated lazily — no separate "calibration phase." The estimator is self-improving.

Why EMA, not fixed window¶

EMA weights recent queries heavily, tracks workload drift fast.
Fixed window / running average treats old samples equally, lags workload drift, needs periodic recomputation.

The workload-drift case is load-bearing: table sizes change, cache temperature changes, and a plan that was cheap yesterday may be expensive today. EMA follows drift without operator intervention.

When to apply¶

Any admission-control mechanism gating by estimated query cost.
Any resource-budget accounting that needs a pre-execution estimate.
Any system with an existing planner/optimiser that emits dimensionless cost (Postgres, MySQL, Vitess, Spark, BigQuery, etc.).

When not to apply¶

Queries with no meaningful plan-cost signal (e.g. trivial single-row inserts where k is dominated by fixed per-query overhead).
Workloads where the first arrival of a new query pattern must not be mis-estimated — cold-start for k is a known weakness.
Adversarial workloads that deliberately exercise plan-cost / wall-clock divergence to evade admission control.

Caveats¶

Cold start. A never-seen pattern has no EMA. The source doesn't specify the default-k policy; either admit unconditionally or use a global-average k fallback.
Pattern grouping error. If two queries sharing a pattern fingerprint have genuinely different cost-to-time relationships (e.g. due to data skew), the shared EMA averages over them and admits/rejects incorrectly for both. Mitigated by finer-grained fingerprints.
Estimator bias under saturation. During a load spike, the EMA trails reality — queries admitted at the beginning of the spike under-estimate wall-clock, get admitted, then contribute to the spike they were supposed to dampen. EMA half-life is the tuning knob.
Planner bugs become admission bugs. A planner that mis-estimates cost by 10× produces an estimator that mis-admits by 10× until the EMA catches up.