[Design] Add an estimator-aware HLL failure-probability model #459

Problem and why now

The default HLL accuracy model currently supplies an RSE magnitude but leaves failure probability unknown. In DefaultAccuracyModel::sketch_guarantee at 2ec3fc80, SketchParams::Hll { precision } produces:

metric = Cardinality
bound = 1.04 / sqrt(2^precision)
failure_probability = Unknown("hll_estimator_failure_probability")

After #455, retaining an HLL candidate is distinct from certifying it for selection/deployment. Backend integration in ProjectASAP/ASAPQuery-backend#768 confirms that distinct_over_time(distinct_values{job="api"}[5s]) with an approximate accuracy target retains exact execution under the current model. Previously the process test expected an installed HLL without a confidence proof.

This is a missing confidence model, not a claim that HLL cannot provide probabilistic guarantees. RSE alone must not be interpreted as an epsilon/delta tail bound. Related: #454, #172, #350; backend evidence/costing work: ProjectASAP/ASAPQuery-backend#761.

Intended users and MVP

Planner/backend users should be able to select HLL when a supported estimator and explicit assumptions establish the requested cardinality accuracy and failure probability. Unsupported cases remain visible with unknown guarantees and retain exact execution when available.

MVP: support one identified HLL estimator with a documented confidence model and end-to-end selection coverage. Do not assume every HLL implementation, bias correction, cardinality regime or merge configuration shares that contract.

Inputs, outputs, and end-to-end outcome

Inputs: HLL precision/register count, requested epsilon/delta, estimator implementation/version and the assumptions or calibration metadata required by the selected model.

Output: a cardinality ResultGuarantee whose bound and failure probability describe the same event relative to true cardinality, with model provenance and applicability. Parameter sizing and selection must use that same contract.

Outcome: a costed, executable HLL candidate can satisfy an applicable target; an unsupported or insufficiently evidenced candidate cannot silently acquire a probability.

Simplest viable approach

1. Identify the actual supported estimator and applicable theoretical bound or documented calibration method.
2. Implement its confidence conversion through the accuracy-model boundary and align HLL parameter sizing with it.
3. Preserve unknown probability outside that model's supported domain; keep cost evidence independent from accuracy evidence.

Do not invent delta from the precision parameter alone. A normal approximation must be labelled with its assumptions and applicable domain. A Chebyshev-style conversion needs a justified variance/MSE or bias-aware bound; the generic asymptotic RSE expression alone is not a universal finite-sample certificate. ERP observed maximum error across a few trials likewise is not a population tail guarantee.

New concepts or interfaces requiring decisions

Decide whether the selected contract belongs in the default model or an implementation-specific accuracy provider, and what estimator identity/applicability information it needs. Distinguish analytical bounds from empirical confidence calibration in provenance. No legacy selection bypass is needed.

Alternatives and quality attributes

Keeping Unknown is a safe interim behavior but prevents normal certified HLL selection. Assigning a fixed delta without a matching bound would overstate accuracy. Prefer a narrow, auditable model over an unrestricted HLL guarantee.

Acceptance behavior

• A supported HLL configuration produces finite epsilon/delta for the same error event, with estimator/model provenance.
• A candidate with sufficient precision and valid cost/support evidence is selectable for a feasible target; a stricter infeasible target is rejected or sized appropriately.
• Missing, mismatched or out-of-domain estimator/calibration inputs remain unknown or are explicitly rejected.
• Boundary tests cover the chosen model's precision/cardinality domain and any bias-correction/merge assumptions it claims to support.
• Frontend-to-selection tests cover distinct_over_time (and SQL distinct cardinality where supported), including both HLL selection and exact fallback.
• Backend process coverage can again test a genuinely certified HLL path, while preserving unknown-guarantee rejection coverage.
• Documentation separates RSE, epsilon/delta guarantees and empirical measurements. Statistical experiments may validate the implementation but are not presented as proof by themselves.

Human decisions required

• Select the estimator and confidence contract for the MVP.
• Decide the acceptable analytical/calibrated model and its applicability domain.
• Confirm ownership of implementation-specific metadata across Planner and backend.