SP-9: AST-aware hierarchical stage assignment (edge collector → leaf nodes, precompute engine → upper AST)

[zzylol]

Background

SP-3 (Stage Assignment) currently assigns a single flat sketch type to every pipeline stage. The planner in rules.rs receives only Vec<AggType> — the full SketchExpr tree built by the query parser is discarded in analyzer.rs before it reaches the planner.

For compositional queries like TopK(Partition(Window(Agg(Source)))), this means:

• The precompute engine receives a hardcoded quantile_over_time(0.99, ...) template regardless of the actual query structure.
• There is no mechanism to assign leaf-level operations (sketch insertion, windowing) to the OTel Collector and upper-level operations (TopK, Merge, Partition) to the ASAPQuery Precompute Engine.

Proposed subproblem: SP-9

Split the optimized SketchExpr tree across pipeline stages:

SketchExpr node	Stage
Source, Filter, Window, Agg	Agent OTel Collector
Partition, Merge, Dedup	Backend OTel Collector
TopK	ASAPQuery Precompute Engine
ExactAgg	DB-side query

The full spec is in docs/controller-optimization-problem.md under SP-9.

Implementation gaps

1. analyzer.rs — thread SketchExpr through QueryWorkload instead of flattening to Vec<AggType>.
2. planner/ — add split_expr_by_stage() that walks the tree and emits per-stage sub-plans.
3. config/precompute.rs — replace hardcoded build_query_expr() template with serialization of the upper sub-tree.
4. types.rs / CollectionPlan — extend to carry a per-stage sub-expression so agent.rs and backend.rs emit the right processor chain.

Files involved

• controller/src/analyzer.rs
• controller/src/query_parser/mod.rs, sketch_algebra.rs
• controller/src/planner/rules.rs
• controller/src/config/precompute.rs, agent.rs, backend.rs
• controller/src/types.rs

Relation to existing subproblems

SP-9 is a refinement of SP-3, not a replacement. The flat SP-3 assignment remains as the fallback for single-aggregation queries. SP-6 can score both plans (flat vs. AST-split) and select the cheaper option.

[zzylol]

In addition to AST-aware stage assignment, the optimization should also account for the fact that each data lifecycle stage operates under different computation resource constraints:

• Agent OTel Collector (edge): runs on the same host as the instrumented service, so CPU and memory budgets are tight. Sketch insertion and windowing must be lightweight.
• Backend OTel Collector: has more headroom but is still shared infrastructure; operations like Partition/Merge/Dedup should be bounded by the available collector fleet capacity.
• ASAPQuery Precompute Engine: purpose-built for heavier computation (TopK, cross-series merges), but still subject to its own memory and CPU quotas.
• DB-side (ExactAgg): query cost is dominated by I/O and storage, not compute.

The split_expr_by_stage() planner should therefore not only respect the AST topology but also enforce per-stage resource budgets — e.g. reject or re-route an assignment if the estimated sketch memory or CPU cost at a given stage exceeds its limit. SP-6's Pareto scorer can be extended to take these per-stage caps as hard constraints alongside the existing bandwidth/accuracy objectives.

[zzylol]

Overflow / deferral policy: if a stage exceeds its resource limit, the computation is not dropped — it is deferred to the next stage in the data lifecycle:

SDK → Agent OTel Collector → Backend OTel Collector → ASAPQuery Precompute Engine

In the worst case, no precomputation is performed at the SDK or edge collector at all, and all sketch construction and aggregation is handled entirely by the ASAPQuery Precompute Engine on the backend. This is the degenerate-but-valid fallback: it matches the current flat SP-3 behaviour and ensures the query is always answerable, at the cost of higher bandwidth and backend load.

The split_expr_by_stage() planner should model this deferral chain explicitly, so that SP-6 can score the full spectrum from maximally-distributed (each stage does its share) to fully-centralised (backend does everything) and pick the cheapest plan that satisfies all per-stage resource caps.