apache / apache/datafusion-comet
Upstream Spark-compatible approx_count_distinct (HyperLogLogPlusPlus) to the datafusion-spark crate
- Dominant language
- Scala
- Stars
- 1.3k
- Forks
- 373
- Avg merge
- 2d 6h
- Merged PRs (30d)
- 190
Description
## Is your feature request related to a problem or challenge?
PR #4819 added a native Spark-compatible `approx_count_distinct` (a faithful port of Spark's `HyperLogLogPlusPlus` / `HyperLogLogPlusPlusHelper`) as a Comet-only aggregate in `native/spark-expr/src/agg_funcs/hll_plus_plus.rs`, along with the bias-correction tables in `hll_plus_plus_const.rs`.
This is a natural fit for the upstream `datafusion-spark` crate (`datafusion/datafusion/spark/src/function/aggregate/`, which already carries `avg`, `try_sum`, `collect`), so the algorithm and the Spark bias-correction tables could be shared rather than living only in Comet.
DataFusion's own `approx_distinct` cannot be reused: it implements the 2017 Ertl variant (closed-form estimator, no lookup tables, fixed precision `HLL_P = 14`, one `u8` per register, foldhash seed 0), whereas Spark uses the 2013 Google HLL++ variant (xxhash64 seed 42, `p` derived from `relativeSD`, 6-bit registers packed 10 per long, empirical bias-correction plus linear-counting tables). Every compatibility-critical axis differs.
## Describe the solution you'd like
Move the HLL++ algorithm and bias-correction tables into the `datafusion-spark` crate so they can be shared.
The main coupling to unwind is the hashing: the Comet implementation reuses Comet's `create_xxhash64_hashes` (Spark's `XxHash64`, seed 42, with `NormalizeNaNAndZero` applied to floats first). Upstreaming needs a Spark-compatible xxhash64 available in `datafusion-spark`, or the port parameterized over the hash function.
## Additional context
Follow-up to PR #4819 (part of #4098). Landing in Comet first is the expected path; this issue tracks the eventual upstreaming.
Contributor guide
Research direction
Start by reading native/spark-expr/src/agg_funcs/hll_plus_plus.rs and hll_plus_plus_const.rs, then compare them with datafusion/datafusion/spark/src/function/aggregate/, including its existing avg, try_sum, and collect implementations. Review PR #4819 and trace the Comet create_xxhash64_hashes coupling. Done means the Spark-compatible HLL++ algorithm and bias-correction tables are shared upstream with the hashing dependency addressed.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data-engineering
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100