Evaluate range-queryable structured summaries (QTree-style)

[zzylol]

Context

Split from #173 after its multi-subpopulation/Hydra portion landed. ASAPPlanner now represents shared multi-subpopulation frequency-sketch state through Hydra grouping candidates, but it still has no first-class range-queryable structured summary comparable to Algebird's QTree:

• state is organized over non-overlapping value ranges;
• each range carries decomposable/mergeable inner state;
• readout asks about a sub-range and may return lower/upper bounds rather than one scalar point estimate.

This issue evaluates and, if justified, models that remaining structured-summary capability. It does not reopen the already implemented Hydra grouping work.

Required semantics

• Define range-shaped readout operations such as bounded range count/sum and range quantile.
• Define whether inner state is a closed core vocabulary or a recursively referenced mergeable summary family.
• State merge, compaction, and range-query legality must be explicit.
• Exact and approximate inner states must retain their existing accuracy contract; nesting a sketch does not make it exact.
• Runtime capability must gate candidate generation until a downstream implementation exists.

Cost model

Compare alternatives in cost units per second, with state size reported independently in bytes.

For maintained structured range state:

structured_cost_rate =
    update_rate * structured_update_cost
  + evaluation_rate * structured_range_read_cost

For recomputation from the pre-ASAP/raw path:

raw_recompute_cost_rate =
    evaluation_rate * raw_range_scan_cost

For several repeating consumers sharing the same structured state:

evaluation_rate = sum(1 / query_interval_i)

If one-shot and recurring work are compared over a finite horizon H:

total_cost(H) = recurring_cost_rate * H + one_shot_cost

State accounting:

structured_state_bytes = retained_range_nodes * bytes_per_range_node

Every cost must include units, input provenance, and model version. Unknown runtime/cardinality inputs remain unknown rather than being encoded as zero.

Scope

1. Write an ADR defining the readout vocabulary, inner-state composition, accuracy semantics, and runtime contract.
2. Decide whether the capability belongs in core post-ASAP IR or behind the deployment extension interface.
3. If first-class core support is justified, add the representation and an experimental capability-gated replacement strategy.
4. Export the selected physical representation and explicit cost/provenance metadata for DAG visualization.

Acceptance criteria

• ADR compares a first-class structured-summary type with deployment extension and ordinary raw recomputation.
• At least one range count or range sum fixture has a lossless readout representation.
• Unsupported/non-mergeable inner state does not produce a candidate.
• A deterministic cost model selects structured state for a high-frequency range workload and raw recomputation for a sufficiently cold workload.
• Tests verify evaluation_rate = sum(1 / query_interval_i) for shared consumers and prevent shared-state double counting.
• Accuracy targets and returned bound semantics survive representation, merge, serialization, and DAG export.
• Candidate generation is absent without runtime capability.

Related

• Split from Multi-dimensional / structured summary kinds (e.g. QTree-style range trees, Hydra-style sketch composition) #173.
• General physical degrees of freedom are tracked by Tracking issue for "degree of freedom" we should add when converting from L3 to L4 #152.
• Nested exact and approximate composition are Compose exact operators with summary plans across explicit update/readout boundaries #171 and Propagate end-to-end accuracy guarantees for approximate-over-approximate plans #172.
• Candidate-plan search is implemented by closed asap-aware-mapping: Cascades/Volcano-style candidate-plan search engine over ReplacementStrategy #252.
• Cost annotations are tracked by (dev-tools) Export and visualize planner cost/benefit annotations #286.