Repository navigation
Audit the HLL expressions against Spark on datasketches 0.6.0 and revisit the allowIncompatible opt-in #7396
Description
What is the problem the feature request solves?
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
Unionestimate 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.rssay bytes differ for small inputs; the 0.4.0 changelog says Set coupon ordering now matches Java. - Compare
hll_sketch_estimateandhll_unionresults with Spark's for strings, binary and every integral width, including nulls and empty strings. - If estimates and bytes match, remove
allowIncompatibleand 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()andHllUnion::estimated_size()exist in 0.6.0. The changelog calls them implementation-dependent, so check whether they could replace the hand-rolledlayoutmodule or whether that module stays.- 0.6.0 adds
HllUnion::resetandcomposite_estimate. perf: hll_sketch_agg merge builds a new union for every merged row #7341 (a union built for every merged row) may be able to usereset.
Additional context
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.
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…