Repository navigation
Description
Example
A p99 latency over the last hour, evaluated every 60 s over one series sampled at 10 Hz, with a per-value rank-error target of 0.005 at δ = 0.01:
quantile_over_time(0.99, latency_seconds[1h])
The unrestricted plan builds KLL sketches with k = 547 in tumbling windows at ingestion, stores them, and merges the windows that cover the hour at query time.
Now hand this plan to a data plane that has no KLL, or that can build a sketch and read it once but cannot keep sketch state and merge it across windows. A column store with incremental materialized views and a time-series engine with stream aggregation are both like this. The plan cannot be deployed there. The planner has no way to learn that: DeploymentCapabilities can say "no KLL" (supported_summaries), but not "no state merged across windows". So the planner still selects the plan, and it fails only when someone tries to install it.
| Today | Wanted | |
|---|---|---|
| Target with every capability (the ASAP executor) | KLL k = 547 in stored tumbling windows, merged at query time | same |
| Target without KLL | same plan if supported_summaries is set; no way to also say what replaces it |
the cheapest plan the target can run, e.g. another family it does have, or exact |
| Target that cannot merge sketch state across windows | the same KLL plan; installing it fails | a plan that builds and finalizes within one evaluation, or exact |
A second example comes from counter semantics. sum by (job) (rate(requests_total[1h])) is often planned as exact Rate windows: each built at ingestion and stored, then merged at query time with TimeRange + SummaryMerge. Some targets lack the counter semantics this needs:
- A mergeable counter-delta state that adds 0 at a counter reset, where PromQL adds the post-reset value.
- A
ratethat is never extrapolated to the window edges.
This is the most common blocker. In a coverage analysis of 211 selected plans (PromQL and SQL workloads, planner main 79d99326e), stored Rate windows blocked 54 workloads on each of the two capability-limited targets above. That was more than any sketch family (DDSketch 20, KLL 12, KMV 2).
Why this happens
DeploymentCapabilities (crates/types/src/deployment_capabilities.rs) has three fields today:
| Field | Read by | Says |
|---|---|---|
supported_summaries |
Stage 1 Pass 1 | which sketch families and readouts the executor builds |
raw_data_retained |
Stage 3 | whether a query-time raw scan is allowed |
query_time_results_retained |
Stage 2 | whether a query-time result may be kept across evaluations |
It cannot say any of the following:
- Parameter ranges. For example, a fixed-size KMV with k = 4,096 only, where the plan wants k = 26,656.
- Guarantee kind per family. Whether the target's version of a family keeps the planner's error bound or has no known bound. For example, a quantile sketch that uses a different rank rule.
- Timing. Ingestion versus query time. This is the request in DeploymentCapabilities: allow forbidding ingestion-time materialization #1279.
- Mergeability. Whether a family's state can be merged across windows, or only built and finalized within one evaluation.
- Window forms. Tumbling versus sliding, and pane chains.
- Operators. Which operators the target runs.
- Query-time aggregate measures. For example, a query-time
Aggregate[rate]. - Counter semantics. Reset handling and extrapolation.
The measurement harness's design adds a separate Stage 3 option, CandidateExclusion { timing, operator, per_entity_aggregate, summary_family } (harness PR P1, see #1317). It is meant for forcing sweep alternatives. The coverage analysis found two cases it cannot express:
- A query-time
Aggregate's measure. Without it, the planner rebuilds an excluded query-timerateas anAggregate[rate]. - Rate state merged across windows versus built and finalized in one evaluation. Only the merged form is missing on one target, so matching on the family alone excludes too much.
Two separate restriction mechanisms would also drift apart.
Proposal: a generic capability description, used as a deployment input
Extend DeploymentCapabilities into a description of what a target data plane can run, with no names of particular systems:
| Capability | Example value | Meaning |
|---|---|---|
| summary families, with parameter ranges | Kll { k: 26..=2863 }, Kmv { k: 4096..=4096 }, DDSketch { alpha: .. } |
which families the target builds, and which parameters |
| guarantee kind per family | KnownBound / None |
whether the planner's error bound holds for the target's version; None makes the family usable only without an accuracy target |
| computation timing | {Ingestion, QueryTime} |
where computation may run; subsumes #1279 |
| state mergeability per family | MergeableAcrossWindows / FinalizedWithinEvaluation |
whether stored state can be merged at query time, or only built and read within one evaluation |
| window forms | {Tumbling, Sliding, PaneChain} |
which window shapes can be stored and read |
| operators | OperatorKind set |
which physical operators the target runs |
| query-time aggregate measures | {Sum, Count, Min, Max, Avg, Quantile, ...} |
which measures a query-time Aggregate may compute |
| counter semantics | { resets: Handled / NotHandled, extrapolation: true / false } |
whether Rate/Increase/IRate match the query language's definition |
Default: everything allowed. DeploymentCapabilities::default() keeps today's behaviour, and no plan changes.
One filter, unified with CandidateExclusion. Capabilities expand into a list of restrictions, DeploymentCapabilities::restrictions() -> Vec<CandidateExclusion>. One filter applies them. The harness's sweep exclusions are just a hand-written list of the same type. CandidateExclusion gains the two missing fields: the query-time aggregate measure, and state mergeability.
Where it is applied:
- Stage 1 prunes candidates that use a disallowed family, parameter, guarantee kind, operator, measure or counter semantics. Pass 1 already does this for
supported_summaries. - Stage 2 prunes reuse edges that need mergeability across windows, or a window form the target lacks. For example, a pane chain merged at query time over a family that is
FinalizedWithinEvaluation. - Stage 3 rechecks the selected plan as a defence. If a query has no deployable candidate left, it returns a typed error that names the query and the missing capabilities, instead of today's untyped
NoValidCandidatewith anInfeasiblereason string:
ErrorSelectingPlan::NoDeployablePlan { query: QueryId, missing: Vec<Capability> }Scope
- In scope: the capability description, its JSON form for
asap_planner --deployment-capabilities, the shared restriction filter, the Stage 1/2/3 checks and the typed error. - Out of scope: per-target calibrated costs. A capability-limited target also has different unit costs, for example a fixed overhead per request. These will be filed as a follow-up issue that feeds per-target
CostInputsfrom the harness's calibration. This issue keeps one cost model. - Out of scope: describing any particular target. Profiles for specific engines live in the benchmark repo (Engine capability profiles with conformance tests sketch-bench#252).
Acceptance
-
The restricted-planning numbers from the coverage analysis can be reproduced through the real API (
asap_planner --deployment-capabilities), without an out-of-repo driver. The analysis emulated the restriction by dropping marked Stage 2 candidates before Stage 3.Capability set Workloads Planned Same cost as unrestricted Changed cost column store with incremental views (exact families + HLL; no stored counter state; no DDSketch, KLL, KMV) 211 211 132 79: 1.08–21×; one range-heavy set 60,000–70,000× time-series engine with stream aggregation (no sketches; no Rate/Increase/IRate; no SQL)211 126 115 11 -
Each restricted plan uses only allowed capabilities.
-
With every capability allowed, every plan and cost is unchanged (a test over the showcase suite).
-
A workload with
rate(...)planned against a target without counter extrapolation fails withNoDeployablePlannaming that query and the counter capability.
Related
- [Design] asap_run: one binary to execute plans, calibrate measured unit costs per machine, and bench predicted vs measured #1317: the measurement harness design; its PR P1 adds
CandidateExclusion, which this issue extends and reuses. - DeploymentCapabilities: allow forbidding ingestion-time materialization #1279: forbidding ingestion-time materialization becomes the timing capability here.
- Plans whose operators have no executor kernel (KMV, IRate) count as valid in Stage 2/3 #701: plans with operators that have no executor kernel; the executor's own capability set becomes one instance of this description.
- Deployment inputs: one bundle for cost model, accuracy model and capabilities — after #511 #525: deployment inputs as one bundle.
- Engine capability profiles with conformance tests sketch-bench#252: capability profiles per external engine, with conformance tests; they are instances of this description.
- Translate an InstallablePlan into each engine's deployment form sketch-bench#253: translating a selected plan into each external engine's deployment form.
Activity
zzylol commentedon Nov 16, 2026
Tests for this (tests only, implementation pending approval): #1374. It unifies
CandidateExclusionwithDeploymentCapabilitiesas one Stage 2 filter and covers the query-time aggregate measure, state merged across windows versus built within one evaluation, and counter reset handling and extrapolation.zzylol commentedon Nov 16, 2026
Follow-ups: #1380 (plan with each target's calibrated costs) and ProjectASAP/sketch-bench#257 (bench-external, three comparison modes).