Skip to content

Family-capability table: infer "has heaps" from an explicit column, not from any Approximate readout #750

Open

Description

@zzylol

Problem, by example

FamilyCapability::merged_error answers "what is the error of this statistic read from a merged state" from the family-capability table. For a statistic a family does not list, it falls back to a default, and the default for top-k and entropy depends on whether the family "has heaps". It decides that from whether any listed readout is Approximate:

// crates/types/src/ir/schema/family_capability.rs, FamilyCapability::merged_error
let has_heaps = self
    .readouts
    .iter()
    .any(|&(_, error)| error == MergedError::Approximate);
match statistic.kind() {
    _ if self.readouts.is_empty() => MergedError::Exact,
    StatisticKind::TopK | StatisticKind::FrequencyEntropy if has_heaps => MergedError::Approximate,
    _ => MergedError::AsIfBuiltOverUnion,
}

Today UnivMon's row is

S::UnivMon => (Some(Disjoint), &[
    (Total, Union), (Distinct, Union), (FrequencyL2, Union),
    (FrequencyEntropy, Approximate),
]),

so merged_error(&TopK { k: 5 }) on a merged UnivMon is Approximate (the test merged_error_depends_on_the_readout in crates/types/tests/summary_merge_structure.rs pins it). That answer is right, but only because the entropy readout happens to be Approximate. UnivMon's heaps are why its top-k is approximate after a merge; entropy is a different readout.

Once merged entropy is certified (planned: UnivMon's distinct and entropy bounds certified upstream), the row becomes (FrequencyEntropy, Union), no entry is Approximate, and merged_error(&TopK { k: 5 }) silently turns into AsIfBuiltOverUnion: a merged UnivMon's top-k would claim the guarantee of one build over the union, although each part's heap still drops items that are heavy only over the whole window.

Change to the UnivMon row merged_error(TopK) today Should be
none Approximate Approximate
entropy certified: (FrequencyEntropy, Union) AsIfBuiltOverUnion Approximate (its heaps still lose heavy items)

(Derived from reading the code at 20d2923; the second row is what the expression above evaluates to with that entry changed.)

Why it happens

The table has no column that says a family keeps heaps. merged_error infers it from another readout's error, so the top-k default is coupled to an unrelated entry.

Proposal

  • Add a field to FamilyCapability, e.g. keeps_heavy_item_heaps: bool ("each state keeps a bounded heap of its own heavy items, which a merge cannot complete"), set for CmsWithHeap, CountSketchWithHeap and UnivMon in FamilyCapability::of.
  • merged_error reads that field instead of scanning readouts.
  • Alternative: drop the default for top-k and entropy and list every readout each family can serve explicitly (UnivMon (TopK, Approximate) even though Pass 1 does not offer it), so nothing is inferred.

Scope and acceptance

  • In scope: the table field, merged_error, and its tests.
  • Acceptance: a test that builds UnivMon's capability with entropy marked Union and still gets Approximate for TopK, plus the existing merged_error_depends_on_the_readout unchanged.

Status and related work

Raised as a review note on the family-capability table change (#724). Not urgent today (every current row gives the right answer), but it becomes a wrong guarantee the moment the UnivMon entropy row changes.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    CSEaccuracyAccuracy requirements, guarantees, and propagationenhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions