Compose exact operators with summary plans across explicit update/readout boundaries

[zzylol]

Design status (updated)

This issue defines a required planning capability, not a settled post-ASAP IR design. The implementation on the feat/exact-composition-planner family of branches is a prototype for evaluation and has not been merged into main. Its ExactTransform / ExactPostProcess vocabulary must not be treated as the accepted architecture.

The semantic requirement is:

ASAPPlanner must be able to represent, validate, cost, and select plans that compose exact computation with summary computation without hiding an independently realizable summary subtree inside an opaque fallback.

In particular, rate, irate, and increase are exact functions. They should not be collectively named deriv, because PromQL already has a distinct deriv() function, and they should not be classified as “transforms” as a semantic identity. Function semantics and execution placement are separate concerns: an exact function may have update-time, query-time, or multiple legal physical implementations, and the planner should compare those alternatives rather than encode one phase into the function name.

Any proposed design must satisfy these implementation requirements:

• Extensible: adding another exact function, aggregate, or relational operation must not require another pair of phase-specific IR variants or a new one-off planner path.
• General: the representation and selection mechanism must cover the general exact/summary composition problem in either nesting direction, rather than only the example queries that exposed this issue.
• No issue-specific special nodes: do not introduce a special node solely to handle rate, max over quantile, or any other single reproducer. Nodes must represent stable semantic or physical concepts with invariants that apply across operators.
• Open to downstream extension: deployments must be able to register capabilities, costs, and legal execution modes without changing the core IR for every new exact function.
• Conservative and compositional: unsupported combinations must retain an explicit fallback without swallowing independently selectable child candidates.

Any proposed design should therefore evaluate at least these options before choosing an IR:

• an ExactFunction / ExactAggregate semantic vocabulary with execution phase represented separately;
• a general exact-operation node with independently selected physical execution modes;
• expressing the composition only in a lower physical/stage DAG rather than adding specialized post-ASAP logical nodes; and
• retaining multiple legal placements for cost-based selection instead of assigning functions such as rate permanently to the update path.

The existing branch is useful as a prototype and source of tests, especially for phase legality, shared-child selection, conservative fallback, and cost accounting. It is not evidence that its node names or architectural boundary are final. Acceptance of this issue requires an explicit design decision followed by an implementation merged into main.

---

Context

Same migration as issues #150/#151 (ASAPQuery-backend's control_plane adopting asap_plan::bind::implement_tree_in_with for L3→L4 binding, replacing its own locally-defined L4 IR).

We hit a real coverage gap that shows up in both nesting orders of "mix an exact computation with a summary/sketch computation in the same query": an outer exact op wrapping an inner realized summary, and an outer summary op wrapping an inner exact computation. Neither direction has an L4 representation today.

Direction 1 — outer exact fold over an inner realized summary

max by (zone) (quantile_over_time(0.99, http_latency_ms[5m]))
avg by (zone) (quantile_over_time(0.99, http_latency_ms[5m]))

Structurally this is two nested Aggregate nodes: an outer AggIntent::Max/Avg whose child is itself an Aggregate carrying an inner, independently-realizable AggIntent::Quantile. Semantically, the query wants: read the inner quantile's per-zone answer (from whatever summary/accumulator actually answers it), then fold same-zone rows by max/avg. It is not asking for a real, independently-materialized "max" or "avg" accumulator over raw samples — in our deployment this shape is typically the identity fold (the inner summary already emits one row per zone), but it can be a real multi-row fold too (e.g. the inner summary is keyed more granularly than the outer by).

crates/plan/src/boundary.rs's implementation_for_with has no representation for this composition:

AggIntent::Min { .. } | AggIntent::Max { .. } => {
    accumulator(intent, SummaryKind::MinMax, SummaryParams::MinMax)
}
// ...
AggIntent::Avg { .. } | AggIntent::StdDev { .. } | AggIntent::Variance { .. } => {
    Implementation::PassThrough
}

• Max/Min unconditionally commit to SummaryKind::MinMax — this requires a real, independently-registered MinMax-family sid to exist for the metric. One never does for this shape (there's no reason to plan/register a MinMax accumulator alongside a Quantile sketch just so an outer max by (...) can wrap it) — so find_candidates (our SummaryExecutor impl) always returns no candidates for the outer node, and the whole tree fails to execute even though the inner Quantile would answer fine on its own.
• Avg/StdDev/Variance go straight to PassThrough — per implement_tree_in_with's conservative-fallback behavior (a logical parent above a bindable aggregate subsumes it unbound), this wraps the entire tree, including the otherwise-realizable inner Quantile, as one opaque Logical blob.

Either way, the outer wrapper poisons an inner sub-tree that would otherwise realize correctly on its own.

Direction 2 — outer summary op over an inner exact computation

The mirror image: rate(...)/irate(...) are themselves exact, per-sample computations over raw counter data (counter-reset-aware delta ÷ time). A query can wrap one in an operator that would otherwise be summary-realizable, e.g.

sum_over_time(rate(metric[5m])[10m:])

or stack a top-k summary on top of an exact rate, e.g. our own already-excluded

topk(5, sum by (zone) (rate(metric[5m])))

Here the inner rate(...) is the exact computation, and the outer sum_over_time/topk is the one that could in principle be answered from a summary (CMS-with-heap for the top-k case) — but there's no way to express "realize the outer as a summary over the OUTPUT of an inner exact per-sample transform" either. This deployment doesn't currently attempt this composition at all: any query containing rate(...)/irate(...) anywhere in its tree is unconditionally excluded from our SummaryExecutor binding before we ever try (see "What we did instead" below) — direction 2 is why.

Both directions are the same underlying gap, just which side of the composition is exact vs. summary-realized.

The composition should consider when a query DAG, part of the DAG computes from raw data, part of the DAG computes from summaries as well.

Request

Is there room in the L4 model for a third answer shape, alongside "realized as a summary/accumulator" and "opaque Logical, compute from raw data": an L4 node that composes an exact computation with a nested realized summary, in either nesting order — outer-exact-over-inner-summary (direction 1) or outer-summary-over-inner-exact (direction 2)? Concretely, something like the L4Node DAG carrying an explicit "apply this function to the child's per-group output, independent of whether the child bound as a summary or stayed exact" node, so implement_tree_in_with can commit whichever sub-tree can realize independently, and let the caller (or a CostModel-style hook) apply the outer/inner composition at readout — instead of one side either requiring its own unrelated accumulator/summary sid or poisoning the other side's binding.

We don't have a strong opinion on the right shape for this (a new L4Node/SummaryExpr variant vs. a CostModel hook similar to realize_extension/readout_extension vs. something else) — flagging the gap for discussion rather than proposing a specific API.

What we did instead (for now)

Nothing routed around locally for direction 1 yet. We're treating it the same way we treat #151's TopK { accuracy: Exact } gap: a known, accepted "falls over to the exact/archive tier" limitation for now, rather than forking implement_tree_in_with's tree walk to special-case it in control_plane.

For direction 2, we already have a standing local exclusion: any candidate whose PromQL contains rate(...)/irate(...) anywhere in its tree is excluded from our SummaryExecutor binding before it's ever attempted (a RateShape skip in our serving-time lowering), and topk(K, sum by (...) (rate(...))) is excluded the same way. We hadn't connected these to direction 1 until writing this up — they're the same gap.

If a CostModel-reachable hook (or a new IR shape) lands upstream for either direction, we'd rather adopt that than build a parallel local mechanism for either one.

References

• crates/plan/src/boundary.rs — implementation_for_with's AggIntent::{Min,Max} / AggIntent::{Avg,StdDev,Variance} arms (direction 1), and the Rate/Increase accumulator arms (direction 2)
• ASAPController#151 — same "deployment wants a different answer than core's default realization for one intent shape" pattern, one layer over (ranking within an already-offered candidate set, vs. no candidate set being offered at all here)
• ASAPController#150 — the CostModel-style extension-point precedent (realize_extension/readout_extension) this request is loosely modeled after

[zzylol]

Related open work

• Paired with approximate error propagation in Propagate end-to-end accuracy guarantees for approximate-over-approximate plans #172.
• Expands the L3-to-L4 degrees of freedom in Tracking issue for "degree of freedom" we should add when converting from L3 to L4 #152 and the structured-summary representation work in Multi-dimensional / structured summary kinds (e.g. QTree-style range trees, Hydra-style sketch composition) #173.

[zzylol]

Proposed PR design (current-code audit)

The original issue predates the current per-node replacement search and is partly resolved already:

• construct_summary_agg recursively calls realize_child;
• SummaryAgg can therefore already consume another realized SummaryNode;
• nested_aggregates_realize_per_node proves an outer KLL over an inner exact Sum accumulator;
• exact Rate/Increase and mergeable exact folds already have ExactAggregate representations.

The remaining gap is not “nested summaries” generally. It is the lack of an explicit mixed-execution boundary for exact operators that are not maintained summary state:

1. an exact transform executed before a maintained summary; and
2. an exact residual/post-process executed after summary readout.

KeepPreAsap cannot solve this because it owns an opaque whole pre-ASAP subtree and has no post-ASAP children. A logical/exact parent therefore still swallows an otherwise realizable descendant.

Design rule: execution phase must be explicit

A single generic ExactOp { child } is insufficient. It could accidentally place a query-time residual underneath a maintained summary. Represent the two phases separately:

enum SummaryExpr {
    // Existing variants ...

    /// Exact plain-row transformation executed on the update/ingest path.
    /// Its output may feed SummaryAgg maintenance.
    ExactTransform {
        child: Rc<SummaryNode>,
        op: ExactOperator,
    },

    /// Exact operation executed after child summaries have been read out.
    /// It produces final plain query results and cannot feed maintained state.
    ExactPostProcess {
        child: Rc<SummaryNode>,
        op: ExactOperator,
    },
}

Start with the operator payload required by this issue, rather than cloning every QueryExpr variant:

#[non_exhaustive]
enum ExactOperator {
    Aggregate {
        reduction: Reduction,
        measures: Vec<AggIntent>,
        output_names: Vec<String>,
        having: Option<Predicate>,
    },
}

Future PRs can add Filter, Project, BinaryOp, Sort, or Limit payloads when a concrete mixed plan needs them. Do not embed an intact QueryExpr subtree in ExactOperator: its children would still point to pre-ASAP nodes and recreate the opaque-boundary problem.

Edge/stage contract

Add an explicit availability contract to SummaryNode or an equivalent validated derivation:

enum ExecutionAvailability {
    UpdateValue,   // plain rows available while maintaining downstream state
    SummaryState,  // partial/mergeable state, not directly readable
    ReadoutValue,  // plain values available at query evaluation
}

Required validation:

• SummaryAgg.child accepts UpdateValue (and an explicitly supported state-composition input), never ReadoutValue.
• SummaryEstimate consumes SummaryState and produces ReadoutValue.
• ExactTransform consumes and produces UpdateValue.
• ExactPostProcess consumes ReadoutValue and produces ReadoutValue.
• KeepPreAsap must declare whether it is an update-path raw computation or a query-time fallback; it must not remain phase-ambiguous when used in a mixed plan.
• SummarySchema continues to enforce Plain versus summary-family state types. Phase validation is additional; it does not replace schema validation.

For this PR, validate plans at construction and return a typed ImplementError; do not rely on runtime failure.

Strategy

Add a dedicated ExactCompositionStrategy, registered in default_strategies():

struct ExactCompositionStrategy;

It proposes candidates only when all of these hold:

• the target is a single-measure exact aggregate not already adequately represented by a maintained ExactAggregate, or both alternatives should be costed;
• its child has a selected/legal summary readout candidate for post-processing, or a legal update-time exact transform for pre-summary composition;
• grouping columns exist in the child output schema;
• the exact operator consumes only Plain values at its declared phase;
• the downstream runtime advertises the corresponding mixed-execution capability.

Candidate generation must preserve provenance:

target aggregate
  -> selected ExactTransform/ExactPostProcess candidate
  -> child target(s) and selected summary decision(s)

Do not select a child candidate independently inside the strategy. It should reference candidates already present in PlanSpace; global_selection must commit the compatible parent/child combination so shared Rc identity and workload-wide costs remain correct.

Direction-specific lowering

Outer exact over inner summary

Example:

max by (zone) (quantile_over_time(0.99, latency[5m]))

Candidate:

ExactPostProcess(Aggregate Max by zone)       [ReadoutValue]
└─ SummaryEstimate(Quantile 0.99)             [ReadoutValue]
   └─ SummaryAgg(KLL, latency, per entity)     [SummaryState]
      └─ update/raw input

avg uses the same exact post-process representation unless the existing AvgToSumOverCountStrategy yields a cheaper compatible plan. Both are candidates; the cost model selects rather than hard-coding one.

Outer summary over inner exact

Existing mergeable exact accumulators remain directly nestable:

SummaryAgg(outer family)
└─ SummaryAgg(ExactAggregate Rate/Sum/...)

For a non-accumulator exact row transformation, use:

SummaryAgg(outer family)                       [SummaryState]
└─ ExactTransform(exact operation)             [UpdateValue]
   └─ update/raw input                         [UpdateValue]

Never use ExactPostProcess below SummaryAgg.

Cost model

All recurring alternatives use cost units per second.

Outer exact post-process over maintained summary:

postprocess_plan_cost_rate =
    update_rate * summary_maintenance_cost_per_update
  + evaluation_rate * (
        summary_read_cost
      + output_rows_per_eval * exact_postprocess_cost_per_row
    )

Outer maintained summary over an exact update-time transform:

pretransform_plan_cost_rate =
    update_rate * (
        exact_transform_cost_per_input_row
      + summary_maintenance_cost_per_update
    )
  + evaluation_rate * summary_read_cost

Raw/pre-ASAP fallback baseline:

raw_recompute_cost_rate =
    evaluation_rate * raw_recompute_cost

For a shared plan serving repeating consumers:

evaluation_rate = sum(1 / query_interval_i)

For a finite horizon H containing one-shot work:

total_cost(H) = recurring_cost_rate * H + one_shot_cost

Required CostModel hooks may be grouped in one structured method, but must expose equivalent inputs:

• exact transform/post-process per-row cost;
• expected input/output rows;
• summary maintenance and read cost;
• update and evaluation rate;
• unit and provenance/model version.

Unknown values remain unknown; they must not be represented as zero. Missing statistics should preserve the conservative KeepPreAsap behavior unless a deployment model explicitly supplies defaults.

PR implementation sequence

1. Pin current behavior

   • retain the existing nested KLL-over-exact-Sum test;
   • add a passing test for every already-supported exact-accumulator nesting;
   • add failing/current-fallback fixtures for outer max/avg over inner quantile and for a non-accumulator exact transform below a summary.

2. Add phase-aware post-ASAP types

   • ExactOperator, ExactTransform, ExactPostProcess;
   • execution-availability derivation/validation;
   • schema derivation and typed invalid-stage errors;
   • CSE/DAG-export traversal for the new child edges.

3. Add ExactCompositionStrategy

   • generate legal candidates with explicit provenance;
   • register it in default_strategies();
   • integrate compatible parent/child commitment with global_selection rather than privately selecting children.

4. Add cost hooks and explanations

   • implement the formulas above;
   • include units, inputs, baseline, and provenance;
   • export explicit replacement/strategy metadata for (dev-tools) Export and visualize planner cost/benefit annotations #286; the viewer must not infer composition from signatures.

5. Integration tests

   • both nesting directions;
   • grouped fine-to-coarse outer fold;
   • identity-fold and genuine multi-row-fold cases;
   • shared inner summary used by multiple queries;
   • illegal readout-under-maintenance rejection;
   • missing runtime capability and missing cost statistics;
   • pre/post-ASAP DAG schemas and shared Rc identity.

Acceptance criteria

• Outer exact aggregate over an inner summary readout retains the inner summary candidate instead of collapsing the whole tree into KeepPreAsap.
• An outer summary can consume a supported exact update-time transform without phase ambiguity.
• Existing exact-accumulator nesting remains unchanged.
• ExactPostProcess can never appear below a maintained SummaryAgg.
• Unsupported exact operators still fall back conservatively without hiding an independently selectable child candidate in PlanSpace.
• Global selection compares mixed and raw fallback plans with the formulas above and counts shared state once.
• JSON/DAG export carries explicit stage, strategy, target-to-decision provenance, cost units, and schema.
• No Prometheus scheduling/rule-group concepts enter ASAPPlanner.

Non-goals

• Approximate-over-approximate error propagation; that remains Propagate end-to-end accuracy guarantees for approximate-over-approximate plans #172.
• Adding every relational QueryExpr variant to ExactOperator in the first PR.
• Executing the physical plan inside ASAPPlanner; runtimes consume the explicit post-ASAP representation.
• A protocol-specific raw/archive fallback policy.