tlfua commented on issue #7396:
URL:
https://github.com/apache/datafusion-comet/issues/7396#issuecomment-6703600973
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`.
- Code:
https://github.com/tlfua/datafusion-comet/tree/tlfua/exp/7396-hll-compare
- Runs:
- Comet at 644a870:
https://github.com/tlfua/datafusion-comet/actions/runs/41701715680
- Comet at 8fc24a7, after #7345:
https://github.com/tlfua/datafusion-comet/actions/runs/42348769378
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.
- #7345 already accepts this with a 1% tolerance in `hll_sketch_agg.sql`.
**Serialized bytes**
- 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:
- A Comet bump past `datasketches` 0.6.0, which would pick up
apache/datasketches-rust#317.
- A `GroupsAccumulator` for `hll_sketch_agg`, which #7341 still lists.
--
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]
