andygrove opened a new issue, #188:
URL: https://github.com/apache/datafusion-spark/issues/188

   Part of #173 and apache/datafusion-comet#7300.
   
   ### What the function does
   
   `hll_union_agg(sketch [, allowDifferentLgConfigK])` is an aggregate that 
merges Apache DataSketches HLL
   sketches stored as `BINARY` and returns the merged sketch as `BINARY`. The 
inputs are typically produced by
   `hll_sketch_agg` or `hll_union` (see the sibling issues). Spark wraps each 
non-NULL input with
   `HllSketch.wrap`, so any valid HLL_4/6/8 sketch in compact or updatable 
layout is accepted. It feeds them
   into a DataSketches `Union` and returns `Union.toUpdatableByteArray`. That 
is the union's internal HLL_8
   gadget in the updatable layout. Because the output is user-visible bytes 
that other HLL functions and
   external DataSketches readers consume, it must match Spark byte for byte.
   
   - `sketch`: `BINARY`. `allowDifferentLgConfigK`: `BOOLEAN`, default `false`. 
Spark uses `ExpectsInputTypes`
     and applies no implicit casts.
   - `allowDifferentLgConfigK` is evaluated once, with no input row, so it must 
be a constant in practice. A
     NULL literal unboxes to `false`.
   - The union's `lgMaxK` is the `lgConfigK` of the first sketch seen by that 
buffer. Merging a sketch with a
     larger K downsamples it, and merging one with a smaller K downsizes the 
union. The result `lgConfigK` is
     therefore the minimum over all inputs.
   - Return type is `BINARY`, never NULL (`nullable = false`). Available since 
Spark 3.5.0. It has no
     aliases.
   
   ### Examples
   
   ```sql
   SELECT hll_sketch_estimate(hll_union_agg(sketch, true))
   FROM (SELECT hll_sketch_agg(col) AS sketch FROM VALUES (1) tab(col)
         UNION ALL
         SELECT hll_sketch_agg(col, 20) AS sketch FROM VALUES (1) tab(col));
   -- 1
   SELECT hll_union_agg(sketch, false)
   FROM (SELECT hll_sketch_agg(col, 12) AS sketch FROM VALUES (1) tab(col)
         UNION ALL
         SELECT hll_sketch_agg(col, 20) AS sketch FROM VALUES (1) tab(col));
   -- error HLL_UNION_DIFFERENT_LG_K (left 12, right 20, function 
`hll_union_agg`)
   SELECT hll_union_agg(buffer, false) FROM (SELECT CAST('abc' AS BINARY) AS 
buffer);
   -- error HLL_INVALID_INPUT_SKETCH_BUFFER (function `hll_union_agg`)
   ```
   
   Spark's `DataFrameAggregateSuite` ("SPARK-16484") also unions per-group 
sketches. In that test, df1 has
   values a,a,a,b,c,c,d and df2 has a,c,d,d,d,e,e,f. Taking 
`hll_sketch_estimate(hll_union_agg(...))` over
   both gives `6` in every case it checks: both inputs at K=12, both at K=20, 
and K=12 unioned with K=20
   using `allowDifferentLgConfigK = true`.
   
   ### Edge cases to test
   
   - Empty input, or all-NULL input: no `Union` is ever created. `eval` returns
     `new Union().toUpdatableByteArray`, an empty union with the default 
`lgConfigK = 12`, regardless of the
     K of any sketches elsewhere. The result is not NULL, and its estimate is 
0. Capture the exact bytes from
     Spark.
   - A single row: the output is the union's serialization of that sketch, not 
the input bytes echoed back
     (the layout and HLL type can change, for example HLL_4 in, HLL_8 out).
   - NULL sketches are skipped. A NULL `allowDifferentLgConfigK` behaves as 
`false`.
   - Different K with the flag `false` raises `HLL_UNION_DIFFERENT_LG_K` 
(sqlState `22000`). Parameters:
     `left` is the union's current K, `right` is the incoming sketch's K, and 
`function` is `hll_union_agg`.
     The check runs both in `update` and in `merge` between partial buffers.
   - Invalid bytes (non-sketch data, truncated or empty `BINARY`) raise 
`HLL_INVALID_INPUT_SKETCH_BUFFER`
     (sqlState `22546`). In 4.x Spark maps `SketchesArgumentException`, 
`java.lang.Error` and
     `ArrayIndexOutOfBoundsException` to this condition.
   - Input sketches in HLL_4 and HLL_6, in compact layout, and in each of the 
LIST, SET and HLL modes.
   - Merge path: partial buffers are serialized with 
`Union.toUpdatableByteArray` (an empty buffer becomes a
     zero-length array) and restored with `Union.heapify`. `merge` calls
     `union.update(input.getResult(HLL_8))`. Once in HLL mode, a union sets the 
out-of-order flag. After that
     the estimate uses the composite estimator instead of HIP, and the bytes 
depend on the number and order
     of partial merges.
   - DISTINCT over sketch bytes: the estimate is unchanged. The bytes may 
change.
   - Determinism: the output bytes depend on input order and partitioning.
   
   ### Differences across Spark versions
   
   - Not available in 3.4. Added in 3.5.0 (datasketches-java 3.3.0). 4.0 uses 
6.1.1, and 4.1/4.2 use 6.2.0.
   - In 3.5, only `java.lang.Error` was mapped to 
`HLL_INVALID_INPUT_SKETCH_BUFFER`. Other malformed-buffer
     exceptions (`SketchesArgumentException`, `ArrayIndexOutOfBoundsException`) 
surfaced as raw exceptions.
     4.0 widened the mapping.
   - The error conditions have no sqlState in 3.5. 4.0 added `22546` and 
`22000`.
   
   ### Implementation notes
   
   - Spark source: 
`sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/datasketchesAggregates.scala`,
     `HllUnionAgg` (a `TypedImperativeAggregate[Option[Union]]`). Golden file:
     `sql/core/src/test/resources/sql-tests/results/hll.sql.out`.
   - DataFusion core has nothing comparable (`approx_distinct` is a Redis-style 
HLL with its own format).
   - The Apache `datasketches` Rust crate (0.6.0, `hll` feature) has a 
`HllUnion` type. However, its
     `serialize()` writes the compact layout for LIST and SET, and Spark emits 
updatable bytes. Its union
     must also reproduce Java's `Union` downsampling and out-of-order handling 
exactly. Share the sketch,
     union and serializer code with `hll_sketch_agg`, `hll_sketch_estimate` and 
`hll_union`.
   - Belongs in `crates/spark/src/function/aggregate/`. Keep the accumulator 
state as updatable union bytes,
     with the empty buffer as a zero-length binary, to mirror Spark's 
partial/final behavior.
   - Tests: add `crates/sqllogictest/test_files/aggregate/hll_union_agg.slt`. 
Byte goldens must come from
     real Spark 4.2. Document with `#[user_doc]`.
   
   ---
   _This issue was generated by an LLM (Claude) from the Apache Spark source 
code and tests. Examples come from Spark's `ExpressionDescription` examples, 
test suites and `.sql.out` golden files, but please verify them against Spark 
before relying on them._


-- 
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]

Reply via email to