Repository navigation
[EPIC] Native DataSketches: theta, KLL, frequent items and tuple sketches #7397
Description
What is the problem the feature request solves?
Comet accelerates one DataSketches family, HLL, on Spark 4.0+. Spark ships four more families as built-in SQL functions, and today every one of them falls back to the JVM. The Rust datasketches crate provides all of them behind feature flags. Comet only enables hll; KLL is new in crate 0.6.0 and tuple arrived in 0.4.0.
| Family | Spark functions | Spark versions | Crate feature |
|---|---|---|---|
| HLL | hll_sketch_agg, hll_union_agg, hll_sketch_estimate, hll_union |
4.0+ | hll (done) |
| Theta | theta_sketch_agg, theta_union_agg, theta_intersection_agg, theta_sketch_estimate, theta_union, theta_intersection, theta_difference |
4.1+ | theta |
| KLL | kll_sketch_agg_*, kll_merge_agg_*, kll_sketch_get_quantile_*, kll_sketch_get_rank_*, kll_sketch_get_n_*, kll_sketch_merge_*, kll_sketch_to_string_* (bigint, float, double) |
4.1+ | kll |
| Frequent items | approx_top_k, approx_top_k_accumulate, approx_top_k_combine, approx_top_k_estimate |
4.1+ | frequencies |
| Tuple | tuple_sketch_agg, tuple_union_agg, tuple_intersection_agg, tuple_difference, tuple_sketch_estimate/summary/theta, and variants for integer and double summaries |
4.2 | tuple |
Spark 4.1 and 4.2 use DataSketches-Java 6.2.0 and Spark 4.0 uses 6.1.1.
These are exactly the "exact-correctness traps" the expression docs warn about: the sketch bytes cross the JVM/native boundary and can be read by either side, so serialization has to be compatible with DataSketches-Java, input hashing has to match Spark's (including how each input type is widened, and how empty strings and nulls are treated), and the type rules differ per family.
Describe the potential solution
Take one family at a time, in the order below, each as its own issue and PR. For each, the same three steps that worked for HLL:
- Audit the crate against Java: serialize sketches with DataSketches-Java 6.2.0 (and 6.1.1 for 4.0), commit the bytes as fixtures, and check that the crate decodes them and that unions, estimates and bounds match Java's numbers. Check byte-for-byte parity for what Comet writes.
- Implement the serde and native aggregate/scalar functions, with the type and null handling taken from the Spark source for every version Comet supports, behind the usual opt-in until step 1 shows parity.
- Test with SQL file tests, including a Spark-produced sketch column read by Comet and a Comet-produced one read by Spark.
Order, by how much of the HLL work carries over: theta (hash-based, same hashing wrappers), then KLL, then frequent items, then tuple.
Not scored yet for throughput gain over the JVM codegen dispatcher; each family issue should do that first via the suggest-native-expression skill before investing in the implementation.
Additional context
Part of the broader native expression effort in #7300.
Tasks
- Upgrade the datasketches crate to 0.6.0 and drop the HLL decode workarounds #7395 Upgrade the
datasketchescrate to 0.6.0 and drop the HLL decode workarounds - Audit the HLL expressions against Spark on datasketches 0.6.0 and revisit the allowIncompatible opt-in #7396 Audit the HLL expressions on 0.6.0 and revisit the
allowIncompatibleopt-in - Native theta sketch functions (theta_*): audit the crate against Java and implement #7398 Theta sketch functions
- Native KLL sketch functions (kll_*): audit the crate against Java and implement #7399 KLL sketch functions
- Native approx_top_k functions: audit the frequent-items sketch against Java and implement #7400
approx_top_kfunctions - Native tuple sketch functions (tuple_*, Spark 4.2): audit the crate against Java and implement #7401 Tuple sketch functions (Spark 4.2)
Activity