You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Audit the HLL expressions against Spark on datasketches 0.6.0 and revisit the allowIncompatible opt-in #7396
The four HLL expressions (hll_sketch_agg, hll_union_agg, hll_sketch_estimate, hll_union) are off by default and opt-in per expression through allowIncompatible, because "the point estimate can differ slightly after a merge" (docs/source/user-guide/latest/expressions.md, and the getIncompatibleReasons text in the four CometHll* serdes). That reasoning was written against datasketches 0.3.0.
While preparing the 0.6.0 upgrade (#7395), I compared the crate with DataSketches-Java 6.2.0 (the version Spark 4.1 and 4.2 ship) on HLL_4, HLL_6 and HLL_8 sketches at lgConfigK 12, in compact and updatable form, at 1,000, 100,000 and 2,000,000 distinct longs:
Decoding a Java-serialized sketch and taking its estimate gives Java's value to within 1e-6.
Unioning it with a second Java sketch gives Java's Union estimate to within 1e-6.
Sketches built in Rust with update(i64), round-tripped through bytes, and unioned give the same union estimate as Java.
So at least on these inputs the estimate gap has closed. Nothing has been checked yet for the other lgConfigK values, string and binary inputs, or the bytes Comet writes for LIST and SET mode, where the crate historically emitted a different form from Spark.
Describe the potential solution
Audit the four expressions against Spark and decide whether the opt-in can be dropped, narrowed or kept, with the reason written down either way:
Compare Comet-written sketch bytes with Spark's across the three modes (LIST, SET, HLL array) and a spread of lgConfigK values. The module docs in hll_sketch.rs say bytes differ for small inputs; the 0.4.0 changelog says Set coupon ordering now matches Java.
Compare hll_sketch_estimate and hll_union results with Spark's for strings, binary and every integral width, including nulls and empty strings.
If estimates and bytes match, remove allowIncompatible and the incompat text. If only estimates match, say precisely what still differs.
Generate the Java fixtures with 6.1.1 as well as 6.2.0, since Spark 4.0 ships 6.1.1.
HllSketch::estimated_size() and HllUnion::estimated_size() exist in 0.6.0. The changelog calls them implementation-dependent, so check whether they could replace the hand-rolled layout module or whether that module stays.
The Java fixtures used for #7395 are generated with a small program against datasketches-java 6.2.0 and committed under native/spark-expr/src/agg_funcs/testdata. The same approach extends to the other sketch families.
I compared Comet's four HLL expressions against Spark's behaviour on DataSketches-Java, now that Comet is on the datasketches crate 0.6.0.
Setup
Java side: a small mirror of Spark 4.x HllSketchAgg, HllUnionAgg, HllUnion and HllSketchEstimate, run on DataSketches-Java 6.1.1 (Spark 4.0) and 6.2.0 (Spark 4.1/4.2).
Comet side: the same cases replayed through Comet's own native code (SparkHllSketch, SparkHllUnion, spark_hll_union, spark_hll_sketch_estimate). The aggregate glue follows HllSketchAccumulator and HllUnionAccumulator.
The corpus has 4030 cases:
lgConfigK 4 to 21.
HLL_4, HLL_6 and HLL_8 inputs, in updatable and compact form.
long, int, string and special values.
1 to 16 partitions, merged in forward and reverse order.
Same and different lgConfigK, with and without allowDifferentLgConfigK.
Both Comet commits give identical outputs for every case. DataSketches-Java 6.1.1 and 6.2.0 also give identical estimates and bytes, so the results below hold for Spark 4.0, 4.1 and 4.2.
Results (Comet vs Spark estimate)
expression / case
cases
estimate bits differ
rounded estimate differs
max rel diff
hll_sketch_agg, 1 partition
605
0
0
0
hll_sketch_agg, 2+ partitions
1153
43
30
0.81%
hll_sketch_estimate on Spark-built HLL_4/6/8 sketches
954
0
0
0
hll_union, same lgConfigK
381
0
0
0
hll_union, different lgConfigK (allowDifferentLgConfigK = true)
847
25
5
1.64%
hll_union_agg
90
10
0
~1e-9 (lgConfigK 21 only)
In the table, "rounded estimate" is what hll_sketch_estimate returns, so a difference there is visible to users.
Error behaviour matches in every case, including the different-lgConfigK error when allowDifferentLgConfigK is false.
Where the differences come from
The differences only show up when a union merges a sketch that is still in SET (hash set) mode and the union promotes to HLL partway through.
The HIP estimator accumulates in the order coupons are inserted.
Comet's SET hash-table layout and iteration order differ from DataSketches-Java's, so the final HIP estimate can differ slightly.
Same-lgConfigK unions of sketches that are already HLL, and hll_sketch_estimate itself, are bit-identical.
For scale: Spark's own hll_sketch_agg result for the same input varies by up to 27.9% in this corpus, depending only on the number of partitions and the merge order.
So the Comet differences (max 0.81%) are well inside the variation Spark already shows between runs.
Comet's sketch bytes are not byte-identical to Spark's:
In LIST and SET mode, Comet writes the compact form and Spark writes the updatable form.
HLL-mode headers also differ in some cases.
Each side reads the other's bytes and gets the same estimate. The only exceptions are the cases above, where the estimate itself differs.
So hll_sketch_estimate, hll_union and hll_union_agg work on sketches produced by either engine. A query comparing raw sketch bytes, for example equality or hashing a sketch column, would differ.
Next step
Based on this, I plan to propose narrowing the incompatibility rather than keeping all four expressions behind allowIncompatible. The details and tests will follow in a PR.
Two upstream changes would need this comparison rerun:
The Java side is a mirror of Spark's code, not Spark itself. I checked it line by line against Spark v4.1.1 HllSketchAgg, HllUnionAgg, HllUnion and HllSketchEstimate.
The Comet side calls Comet's own native HLL code, but the aggregate glue copies the HllSketchAccumulator and HllUnionAccumulator logic rather than running a real DataFusion plan.
Partitioning and merge order are simulated (1 to 16 partitions, forward and reverse), not taken from real Spark or Comet query plans.
The SQL tests in the PR will cover the end-to-end path.
The 27.9% Spark self-variation is at lgConfigK 4. On its own, that number overstates how much Spark varies at typical lgConfigK values. Here is the per-lgConfigK view for hll_sketch_agg. At every lgConfigK, the Comet difference is still smaller than Spark's own variation.
lgConfigK
Spark: max variation across partition counts and merge orders
Comet vs Spark: cases with differing estimate bits
Activity
tlfua commentedon Nov 3, 2026
take
tlfua commentedon Nov 7, 2026
I compared Comet's four HLL expressions against Spark's behaviour on DataSketches-Java, now that Comet is on the
datasketchescrate 0.6.0.Setup
HllSketchAgg,HllUnionAgg,HllUnionandHllSketchEstimate, run on DataSketches-Java 6.1.1 (Spark 4.0) and 6.2.0 (Spark 4.1/4.2).SparkHllSketch,SparkHllUnion,spark_hll_union,spark_hll_sketch_estimate). The aggregate glue followsHllSketchAccumulatorandHllUnionAccumulator.allowDifferentLgConfigK.Both Comet commits give identical outputs for every case. DataSketches-Java 6.1.1 and 6.2.0 also give identical estimates and bytes, so the results below hold for Spark 4.0, 4.1 and 4.2.
Results (Comet vs Spark estimate)
hll_sketch_agg, 1 partitionhll_sketch_agg, 2+ partitionshll_sketch_estimateon Spark-built HLL_4/6/8 sketcheshll_union, same lgConfigKhll_union, different lgConfigK (allowDifferentLgConfigK = true)hll_union_aggIn the table, "rounded estimate" is what
hll_sketch_estimatereturns, so a difference there is visible to users.Error behaviour matches in every case, including the different-lgConfigK error when
allowDifferentLgConfigKis false.Where the differences come from
hll_sketch_estimateitself, are bit-identical.hll_sketch_aggresult for the same input varies by up to 27.9% in this corpus, depending only on the number of partitions and the merge order.hll_sketch_agg.sql.Serialized bytes
hll_sketch_estimate,hll_unionandhll_union_aggwork on sketches produced by either engine. A query comparing raw sketch bytes, for example equality or hashing a sketch column, would differ.Next step
Based on this, I plan to propose narrowing the incompatibility rather than keeping all four expressions behind
allowIncompatible. The details and tests will follow in a PR.Two upstream changes would need this comparison rerun:
datasketches0.6.0, which would pick up perf(hll): reduce union copying and defer dense estimator rebuilds datasketches-rust#317.GroupsAccumulatorforhll_sketch_agg, which perf: hll_sketch_agg merge builds a new union for every merged row #7341 still lists.tlfua commentedon Nov 7, 2026
Two caveats on the comparison above:
HllSketchAgg,HllUnionAgg,HllUnionandHllSketchEstimate.HllSketchAccumulatorandHllUnionAccumulatorlogic rather than running a real DataFusion plan.hll_sketch_agg. At every lgConfigK, the Comet difference is still smaller than Spark's own variation.feat: run hll_sketch_estimate natively by default and narrow HLL inco…