andygrove opened a new pull request, #4819:
URL: https://github.com/apache/datafusion-comet/pull/4819
## Which issue does this PR close?
Part of #4098.
## Rationale for this change
`approx_count_distinct` (Spark's `HyperLogLogPlusPlus`) was unsupported, so
any query using it fell back to Spark. Neither DataFusion nor the
`datafusion-spark` crate provides a Spark-compatible HyperLogLog++, and
DataFusion's own `approx_distinct` uses a different hash and algorithm, so its
estimates would not match Spark. This PR ports Spark's `HyperLogLogPlusPlus`
exactly so the result is bit-identical.
Note: Spark's `approx_count_distinct` uses the legacy `HyperLogLogPlusPlus`,
which is a different algorithm from the Apache DataSketches `hll_sketch_agg`
family. They are not interchangeable, so this does not reuse the DataSketches
sketch.
## What changes are included in this PR?
- A native `HllPlusPlus` aggregate
(`native/spark-expr/src/agg_funcs/hll_plus_plus.rs`) porting
`HyperLogLogPlusPlusHelper`:
- Hashes each non-null input with Comet's existing Spark-compatible
`xxhash64` (seed 42), normalizing floats (`-0.0 -> 0.0`, canonical `NaN`)
first, exactly as Spark's `NormalizeNaNAndZero` does before hashing.
- Stores registers in Spark's identical packed-`Long` buffer layout (10
six-bit registers per 64-bit word), so the partial-aggregation state matches
Spark's `aggBufferSchema` (`numWords` `Long` columns).
- Estimates cardinality with linear counting for small inputs and
bias-corrected HLL otherwise, using the bias-correction tables ported verbatim
from Spark (`hll_plus_plus_const.rs`, generated from the Spark source).
- Provides both a scalar `Accumulator` and a vectorized
`GroupsAccumulator`.
- `HllPlusPlus` protobuf message (child + precision) and wiring in
`planner.rs`.
- `CometApproxCountDistinct` serde, which computes the precision `p` from
`relativeSD` with Spark's exact formula and passes it through the protobuf.
Restricts inputs to the atomic types Comet's `xxhash64` hashes identically to
Spark; other types fall back.
- Benchmark coverage in `CometAggregateExpressionBenchmark`.
- Documentation updates (expression support status, expression audit notes).
The 2-argument `HyperLogLogPlusPlus` implementation (algorithm and tables)
is identical across Spark 3.4.3, 3.5.8, 4.0.1, and 4.1.1, so no version shim is
needed.
This implementation was scaffolded with the `implement-comet-expression`
project skill.
## How are these changes tested?
- A SQL file test
`spark/src/test/resources/sql-tests/expressions/aggregate/approx_count_distinct.sql`
that runs each query through both Spark and Comet and asserts equal results
and native execution. It covers a range of cardinalities from a few up to 50000
distinct (exercising linear counting, bias correction, and plain HLL), the
`relativeSD` argument, grouped and global aggregation, all supported input
types, NULL handling, the empty-table (returns 0) case, and float `-0.0`/`NaN`
normalization. Equality passing confirms the port is bit-identical to Spark.
- Rust unit tests in `hll_plus_plus.rs` covering exact small-cardinality
counts, NULL handling, string inputs, precision derivation, merge equivalence,
grouped-vs-scalar agreement, and large-cardinality accuracy.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
