Evaluate AHA-style sparse-subpopulation strategy vs. maintaining full hierarchical sub-population summaries

[zzylol]

Context

Kamarthi et al., “AHA: Alternative History Analytics for Operational Timeseries” (KDD 2026; ACM, arXiv), evaluate storing sparse, fine-grained decomposable state and constructing requested parent cohorts on read.

ASAPPlanner does not currently materialize every node of a complete group-by lattice by default. Existing physical candidates include per-observed-subpopulation instances, shared multi-subpopulation/Hydra structures, selected roll-ups, and CSE-based shared maintenance.

This issue evaluates an additional physical candidate:

ingest -> sparse leaf-state store
query  -> on-demand grouping/roll-up over leaf states

The first deliverable is an ADR and costed experimental design. Selection must remain capability-gated until a downstream runtime can execute the representation.

Eligibility and correctness

The candidate is legal only when:

• the required statistic has a declared decomposable/mergeable representation;
• the leaf dimensions and grouping semantics are known;
• the selected runtime advertises the required sparse leaf-state and on-read grouping capability.

Exact equivalence applies only to supported exact decomposable features, for example sum, count, and avg represented as sum + count. Mergeable sketches remain approximate according to their existing accuracy contract. Exact quantiles and computations requiring raw records are not eligible unless a separate exact representation is provided.

Cost model

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

For a maintained summary/hierarchy candidate:

maintained_cost_rate =
    update_rate * maintained_update_cost
  + evaluation_rate * maintained_read_cost

For sparse leaf-state plus on-demand aggregation:

sparse_leaf_cost_rate =
    update_rate * leaf_update_cost
  + evaluation_rate * (
        leaf_lookup_cost
      + active_leaf_count_scanned * combine_cost_per_leaf
    )

For all repeating consumers sharing the physical state:

evaluation_rate = sum(1 / query_interval_i)

State estimates:

maintained_state_bytes = maintained_summary_count * bytes_per_summary
sparse_leaf_state_bytes = active_leaf_count * bytes_per_leaf_state
sparsity = active_leaf_count / theoretical_leaf_count

If a finite comparison includes one-shot work, use an explicit horizon H:

total_cost(H) = recurring_cost_rate * H + one_shot_cost

Every estimate must carry units, input provenance, and cost-model version. Unknown cardinality or runtime cost must be represented as unknown, not fabricated as zero.

Required model inputs

• active and theoretical leaf cardinality;
• grouping dimensionality and attribute cardinalities;
• update rate;
• per-consumer evaluation interval;
• requested grouping sets;
• bytes per leaf/maintained summary;
• update, lookup, read, and combine costs;
• runtime capability metadata.

Scope

• Write an ADR comparing current maintained-summary candidates with sparse leaf-state plus on-demand aggregation.
• Survey existing exact summaries and sketches for decomposability/mergeability.
• Define a deployment-neutral post-ASAP representation for the new candidate.
• Define runtime capability gating and explicit unsupported cases.
• Add an experimental replacement/physical-layout candidate only after the representation and cost contract are approved.
• Treat Recurrence-aware optimization: cost shared maintenance by query repetition #287 recurrence metadata as an orthogonal cost input, not as a prerequisite for the ADR.

Acceptance criteria

• Sparse, high-cardinality, ad-hoc grouping fixtures select sparse leaf-state/on-demand aggregation under a deterministic cost model.
• Dense or frequently queried stable hierarchies select a maintained-summary candidate when its modeled rate is lower.
• sum and count produce results identical to raw execution; avg is validated through sum + count if included.
• Non-decomposable reductions do not generate the candidate.
• The candidate is absent when runtime capability is absent.
• Post-ASAP IR/DAG explicitly represents leaf-state maintenance and on-read aggregation; the viewer does not infer it.
• Tests verify both selection directions, unit consistency, unknown-statistics behavior, and no double counting across shared consumers.
• Benchmarks publish all model inputs and compare predicted versus measured ingest rate, query cost, and state bytes.

Non-goals

• Claiming exactness for sketches or raw-record-dependent algorithms.
• Assuming the complete hierarchy is ASAPPlanner's current default.
• Adding protocol-specific query scheduling concepts to ASAPPlanner.

[zzylol]

Related open work

• Extends the physical-strategy degrees of freedom tracked by Tracking issue for "degree of freedom" we should add when converting from L3 to L4 #152 and the structured-summary work in Multi-dimensional / structured summary kinds (e.g. QTree-style range trees, Hydra-style sketch composition) #173.
• Uses recurrence-aware cost inputs from Recurrence-aware optimization: cost shared maintenance by query repetition #287 when available, but its ADR does not depend on that implementation.
• Cost and benchmark evidence should be exported through (dev-tools) Export and visualize planner cost/benefit annotations #286.
• Accuracy composition for roll-ups remains tracked separately by Support accuracy-aware approximate Count roll-ups #278.