apache / apache/datafusion

approx_distinct: make HLL register precision configurable

Open
#23,815 0 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Rust
Stars
9.3k
Forks
2.4k
Avg merge
3d 7h
Merged PRs (30d)
344

Description

### Is your feature request related to a problem or challenge?

`approx_distinct` / `HyperLogLog` hardcodes precision at `p=14` (16384 registers, 16 KiB per sketch). There is currently no way for callers to trade accuracy for lower memory or smaller partial-aggregate state on the wire.

### Describe the solution you'd like

Request is to add `HyperLogLog::with_precision(p)` and `ApproxDistinct::with_hll_precision(p)` so that integrators can request a smaller sketch (e.g. p=12 → 4 KiB, ~1.6% error) without changing the default behaviour.

**Note**: This does not affects non-approx paths which use bitmap for exact distinct count.

### Describe alternatives you've considered

_No response_

### Additional context

_No response_

Contributor guide

Open the contributing guide

Research direction

Start by locating the HyperLogLog and ApproxDistinct implementations and their existing approx_distinct tests. Trace how precision is fixed at p=14 and how partial aggregate state is represented. Define and test with_precision(p) and with_hll_precision(p), preserving default behavior and leaving exact bitmap paths unchanged.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
58/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.