Skip to content

HLL is never selected for large distinct counts: its failure probability is unknown outside the classic small-population certificate #1379

Open

Description

@zzylol

Example

A daily distinct-user count over the synthetic clicks table (2,000,000 rows/s, user_id declared with 5,000,000 distinct values), every 60 s:

SELECT COUNT(DISTINCT user_id) FROM clicks
WHERE ts >= now() - INTERVAL '86400 seconds'

On main 2f3664d1f, with the sketch-heavy study's planning driver (default deployment and cost model), every HLL candidate is pruned with NoGuarantee, and KMV is selected. The table varies the target and the source's declared max_distinct_per_evaluation:

Target max_distinct_per_evaluation Selected Cost /s HLL prune causes
relative 0.02, no δ (the workload as written) not declared KMV k = 1,118 184.12 NoGuarantee × 4
relative 0.05, δ 0.01 not declared KMV k = 4,323 201.04 NoGuarantee × 4
relative 0.05, δ 0.01 5,000,000 KMV k = 4,323 201.04 NoGuarantee × 4
relative 0.05, δ 0.01 9,000 HLL precision 18 196.72 NoGuarantee × 1, BelowRequiredAccuracy × 2
relative 0.05, no δ 9,000 HLL precision 17 169.97 NoGuarantee × 1, BelowRequiredAccuracy × 1

So HLL is selected only when the source declares a bound small enough for the classic certificate. A real distinct count (millions of users) never gets HLL, whatever its precision. The workload is tools/dag-viewer/workloads/sketch-heavy/blocked-sql-distinct-users-no-delta-hll-shape__2000000rps-86400s-every60s-releps0.02.json, added by #1388. The other rows are the same file with the target or the bound changed.

Why it happens

  • Without a usable bound, the failure probability is unknown. guarantee::hll::guarantee (accuracy/src/guarantee/hll/mod.rs:19-38) returns classic HLL's certified guarantee only when the source declares max_distinct_per_evaluation and the bound is inside the certificate's contract (classic_guarantee_at, line 54). Otherwise it returns the relative standard error 1.04 / √m with ProbabilityExpr::Unknown { statistic: "hll_estimator_failure_probability" }.
  • Pass 2 rejects an unknown failure probability. Pass 2's edge rule (accuracy/src/logical_edge/mod.rs:136-149) rejects a readout whose failure probability does not evaluate: NoGuarantee. It does so even when the target sets no δ.
  • The certificate covers only small populations. It comes from HLL's linear-counting branch. At precision 18 and δ = 0.01, a bound of 9,636 certifies a relative error just under 0.05, and a bound of 1,000,000 certifies none (the doc example on classic_guarantee_at). Distinct counts in the millions are outside it at every listed precision.
  • What already works. The max_distinct_per_evaluation certificate path exists and works, as the last two rows show.

Proposal

Whichever path lands, the NoGuarantee rule stays for HLL configurations that neither covers.

Scope and acceptance

Related

Activity

  1. added
    accuracyAccuracy requirements, guarantees, and propagation
    enhancementNew feature or request
    sqlSQL front-end lowering (DataFusion → L2)
    on Nov 16, 2026
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

    accuracyAccuracy requirements, guarantees, and propagationenhancementNew feature or requesterror-estimationsqlSQL front-end lowering (DataFusion → L2)

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions