Skip to content

Audit the HLL expressions against Spark on datasketches 0.6.0 and revisit the allowIncompatible opt-in #7396

Open

Description

@andygrove

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 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.
  • 0.6.0 adds HllUnion::reset and composite_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 use reset.

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions