apache / apache/datafusion-comet

feat: support Spark HyperLogLog sketch functions (hll_sketch_agg, hll_union_agg, hll_sketch_estimate, hll_union)

Open
#5,814 0 comments 0 reactions 0 assignees View on GitHub
enhancement requires-triage
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.