Skip to content

Support accuracy-aware approximate Count roll-ups #278

Description

@zzylol

Context

Follow-up to #262.

A fine-to-coarse roll-up can derive an exact coarse count by summing exact finer counts. The same rewrite is not automatically valid for approximate counts: summing finalized finer-group estimates composes their errors and may fail the coarse query's own AccuracyTarget.

PR #262 therefore conservatively permits Count -> Sum only when accuracy == AccuracyTarget::Exact. This issue tracks safely admitting approximate roll-up candidates rather than rejecting all of them.

Required semantics

Treat the finer and coarser accuracy requirements separately. Equality of the two AggIntent::Count values is neither necessary nor sufficient.

An approximate roll-up is legal only when the planner can prove that the composed candidate satisfies the coarse query's requested accuracy:

composed_error(finer implementation/state, fanout, error model)
    <= coarse AccuracyTarget

For finalized estimates, a conservative absolute-error composition is sum(e_i); probabilistic guarantees also need failure-probability composition. The number of finer groups per coarse group may be unknown at planning time, so simply using the same epsilon on both levels is not sufficient.

Prefer merging compatible sketch/summary state and querying the merged state where the algebra permits it, instead of summing finalized estimates. If estimate summation is supported, it must use a known fanout/error bound or a posterior error check.

Scope

  • Define how AccuracyTarget composes from finer groups to a coarse group.
  • Distinguish exact values, finalized approximate estimates, and mergeable sketch state.
  • Extend roll-up legality to compare the composed error against the coarse target.
  • Preserve the coarse target in the candidate representation; do not erase it by rewriting directly to an unannotated Sum.
  • Integrate with the existing query-time error-estimation/cost model where appropriate.
  • Cover epsilon-only and epsilon/delta targets, unknown fanout, and multiple finer groups.

Acceptance criteria

  • Exact Count -> Sum behavior from feat(asap-aware-mapping): add workload-aware fine-to-coarse rollups #262 remains unchanged.
  • Approximate roll-up is proposed when a proof or supported state merge satisfies the coarse target.
  • It is rejected when the composed bound exceeds the coarse target or cannot be established.
  • Tests demonstrate that identical finer/coarse epsilon values are not assumed safe without composition.
  • Tests cover at least one valid approximate roll-up and one invalid approximate roll-up.

Metadata

Metadata

Assignees

No one assigned

    Labels

    accuracyAccuracy requirements, guarantees, and propagationenhancementNew feature or requesterror-estimationreplacement-strategyASAP replacement candidates and physical strategiesrollupFine-to-coarse aggregation and summary reuse

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions