Repository navigation
Description
Example
A distinct-user count over a source that declares 5,000,000 distinct user_id values per evaluation, with a relative error target of 0.02 at δ = 0.01. A calibration table (a MeasuredSketchAccuracy, #1372) holds one HLL entry. The numbers below come from the unit test a_measured_entry_supplies_a_guarantee_where_theory_states_no_failure_probability, not from a run on real data; the sample size is my assumption, since the table does not record it:
{ "sketch": {"Hll": {"precision": 13}}, "statistic": "Cardinality",
"accuracy_metric": "Relative", "trials": 1000,
"error_at": [ { "failure_probability": 0.01, "error": 0.02 } ] }Suppose those 1,000 trials each fed the sketch about 10,000 distinct values. By the code, the planner then treats HLL precision 13 as a certified (0.02, 0.01) readout at 5,000,000 distinct values as well. Two things go wrong:
- Without the entry, HLL is pruned (
NoGuarantee) for this source, because the refactor(stage3): constraint (K) per execution and metric; sign-conditioned DDSketch guarantee, classic HLL certificate from the source's distinct bound (#1207 PR 8) #1238 certificate needs a declared bound inside its small-population contract and 5,000,000 is not. With the entry, HLL is plannable at once, although the entry says nothing about 5,000,000 values. - With a declared bound that the certificate does cover (for example 9,000), the entry still wins over the certificate, because it is checked first, even though the certificate is the stronger statement about that regime.
Wanted: the entry is used only where it was measured, and the certificate is preferred where one exists.
Why it happens
MeasuredAccuracyEntry(crates/accuracy/src/measured.rs) is keyed by sketch parameters, statistic and metric only. It records no cardinality regime, though HLL's error depends on it.AccuracyEvidence::measured_guaranteeis consulted before the theoretical guarantee on every edge (crates/accuracy/src/logical_edge/mod.rs, around line 119). The theoretical guarantee, with itsmax_distinct_per_evaluationbound, is computed only when no measured guarantee came back (measured.is_none()).- So a measured entry overrides refactor(stage3): constraint (K) per execution and metric; sign-conditioned DDSketch guarantee, classic HLL certificate from the source's distinct bound (#1207 PR 8) #1238's HLL certificate and makes HLL plannable without a declared distinct bound. feat(accuracy, cost, devtools): measured sketch accuracy table; delete the cost table's provenance and legacy format #1372 records this as decided; this issue is the follow-up.
Proposal
Add max_distinct_measured: Option<u64> to MeasuredAccuracyEntry: the largest distinct count per evaluation the calibration fed the sketch (None for sketches whose error does not depend on it, such as KLL). Then either, or both:
- Use the entry only when the source's declared
max_distinct_per_evaluationis known and at mostmax_distinct_measured; with no declared bound, an entry that hasmax_distinct_measuredis not used. - Prefer the certificate whenever one exists for the edge, and consult the measured entry only when the theoretical failure probability is unknown.
AccuracyEvidence::measured_guarantee would take the declared bound as an argument (it already receives the sketch parameters and statistic), so the lookup in MeasuredSketchAccuracy stays the only place that applies the rule.
Scope and acceptance
- In scope: the field, its validation (when present, it must be positive), the lookup rule, and the table JSON (
deny_unknown_fieldsalready refuses stale tables). - Regression tests that fail today: an HLL entry measured at 10,000 values is not returned for a source declaring 5,000,000 or declaring nothing; it is returned for a declared bound of 9,000; and the certificate wins where both apply.
- Out of scope: measuring entries per cardinality bucket (a later extension of the same field).
Related
- feat(accuracy, cost, devtools): measured sketch accuracy table; delete the cost table's provenance and legacy format #1372 introduces
MeasuredSketchAccuracyand the measured-first rule. - refactor(stage3): constraint (K) per execution and metric; sign-conditioned DDSketch guarantee, classic HLL certificate from the source's distinct bound (#1207 PR 8) #1238 added the HLL certificate that the measured entry overrides.
- HLL is never selected for large distinct counts: its failure probability is unknown outside the classic small-population certificate #1379 is about HLL never being selected at large distinct counts; it is the planning side of the same certificate and is not a duplicate.
Activity