apache / apache/datafusion-comet
feat: support Spark HyperLogLog sketch functions (hll_sketch_agg, hll_union_agg, hll_sketch_estimate, hll_union)
- Dominant language
- Scala
- Stars
- 1.3k
- Forks
- 373
- Avg merge
- 2d 4h
- Merged PRs (30d)
- 198
Description
## What is the problem the feature request solves?
Spark 3.5+ exposes the Apache DataSketches HyperLogLog functions, which give approximate distinct counting with a sketch that can be persisted and merged later:
- `hll_sketch_agg`
- `hll_union_agg`
- `hll_sketch_estimate`
- `hll_union`
Comet falls back to Spark for all four, so any query that builds or reads an HLL sketch column loses native execution for that part of the plan.
`docs/source/user-guide/latest/expressions.md` listed the `hll_*` family under **Not currently planned**, alongside a note that the families there "may be reconsidered based on demand". This issue is that reconsideration: unlike the other sketch families, the HLL sketch has a pure-Rust Apache DataSketches implementation available, which removes the main cost objection.
## Describe the potential solution
Implement all four natively for Spark 4.0+, backed by the pure-Rust `datasketches` crate so that no C++ toolchain enters the build.
Cross-engine compatibility is the interesting constraint here, because a sketch column is data a user persists and reads back. The crate uses MurmurHash3-x64-128 with the standard DataSketches update seed (9001) and hashes input bytes the same way datasketches-java does, so the sketches are mutually readable: Spark can read a Comet-produced sketch and vice versa. For a high-cardinality HLL-array sketch the serialized bytes are identical.
The point estimate is not bit-identical, though. After a partial/final merge the sketch is flagged out-of-order and estimated with a composite estimator whose interpolation and bias tables differ slightly between the Rust crate and datasketches-java — around 0.7% observed, well inside HLL's ~1.6% standard error at the default `lgConfigK`. So the functions should be reported as `Incompatible`: Comet falls back to Spark for exact results by default, and users opt in per expression with `spark.comet.expression..allowIncompatible=true` to accept the small difference in exchange for native execution.
Scoping to Spark 4.0+ keeps the shared serde tree compiling on 3.4, where the functions do not exist.
## Additional context
Implemented in https://github.com/apache/datafusion-comet/pull/4802.
Contributor guide
Research direction
Start by reading pull request 4802 and the existing entry for the hll_* family in docs/source/user-guide/latest/expressions.md. Done means all four functions have native Spark 4.0+ support backed by the Rust datasketches implementation, with cross-engine sketch compatibility and incompatible-result fallback behavior preserved.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust, scala, spark
- Domain
- backend, data-engineering
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 20/100