apache / apache/datafusion-comet

Upstream Spark-compatible approx_count_distinct (HyperLogLogPlusPlus) to the datafusion-spark crate

Open
#4,984 0 comments 0 reactions 0 assignees View on GitHub
area:aggregation area:expressions enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.