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

   Part of #173 and apache/datafusion-comet#7300.
   
   ### What the function does
   
   `hll_union(first, second [, allowDifferentLgConfigK])` is a scalar function 
that merges two serialized
   Apache DataSketches HLL sketches (`BINARY`) and returns the merged sketch as 
`BINARY`. The inputs are
   typically produced by `hll_sketch_agg`, `hll_union_agg`, or an earlier 
`hll_union` (see the sibling
   issues). Spark's algorithm:
   
   1. Heapify both inputs.
   2. If `allowDifferentLgConfigK` is false and the two `lgConfigK` values 
differ, raise
      `HLL_UNION_DIFFERENT_LG_K`.
   3. Build `new Union(min(k1, k2))`, update it with sketch 1 and then sketch 2.
   4. Return `union.getResult(TgtHllType.HLL_8).toUpdatableByteArray`.
   
   The output bytes are user-visible and must match Spark exactly.
   
   - Arguments: `BINARY`, `BINARY`, `BOOLEAN` (default `false`). Spark uses 
`ExpectsInputTypes` and applies no
     implicit casts, so `hll_union(1, 2)` fails analysis with 
`UNEXPECTED_INPUT_TYPE`.
   - `allowDifferentLgConfigK` is an ordinary argument, not required to be a 
constant, and is evaluated per
     row.
   - Returns `BINARY`. If any of the three arguments is NULL, the result is 
NULL. This includes the flag,
     because the function is a null-intolerant `TernaryExpression`.
   - Available since Spark 3.5.0. No aliases.
   
   ### Examples
   
   ```sql
   SELECT hll_sketch_estimate(hll_union(hll_sketch_agg(col1), 
hll_sketch_agg(col2)))
   FROM VALUES (1, 4), (1, 4), (2, 5), (2, 5), (3, 6) tab(col1, col2);
   -- 6
   SELECT hll_union(hll_sketch_agg(col1, 12), hll_sketch_agg(col2, 13))
   FROM VALUES (1, 4), (1, 4), (2, 5), (2, 5), (3, 6) tab(col1, col2);
   -- error HLL_UNION_DIFFERENT_LG_K (left 12, right 13, function `hll_union`)
   SELECT hll_union(CAST('abc' AS BINARY), CAST('def' AS BINARY));
   -- error HLL_INVALID_INPUT_SKETCH_BUFFER (function `hll_union`)
   SELECT hll_union(1, 2);
   -- error DATATYPE_MISMATCH.UNEXPECTED_INPUT_TYPE (paramIndex first, 
requiredType "BINARY")
   ```
   
   In Spark's `DataFrameAggregateSuite` ("SPARK-16484"), df1 has values 
a,a,a,b,c,c,d and df2 has
   a,c,d,d,d,e,e,f. `hll_union` of their per-group sketches estimates `6`. That 
holds at K=12, at K=20, and
   for K=12 with K=20 under `allowDifferentLgConfigK = true`.
   
   ### Edge cases to test
   
   - NULL in each of the three arguments returns NULL. The NULL flag case can 
only be reached as a column or
     with `NullPropagation` excluded, because the optimizer folds a literal 
NULL away.
   - Two empty sketches, and one empty with one non-empty.
   - Same K, and different K with the flag true. The result has `lgConfigK = 
min(k1, k2)`, and the larger
     sketch is downsampled. With the flag false the call raises 
`HLL_UNION_DIFFERENT_LG_K` (sqlState
     `22000`), with `left` = first's K and `right` = second's K.
   - Invalid bytes in either argument raise `HLL_INVALID_INPUT_SKETCH_BUFFER` 
(sqlState `22546`). The first
     argument is checked first.
   - Input sketches in HLL_4 and HLL_6 or compact layout: the output is always 
HLL_8 in the updatable layout.
   - Mode combinations: LIST+LIST, LIST+HLL, HLL+HLL. Once in HLL mode, the 
result carries the out-of-order
     flag, so `hll_sketch_estimate` uses the composite estimator. The bytes and 
the estimate can therefore
     differ from building one sketch over the combined input directly.
   - Argument order: `hll_union(a, b)` and `hll_union(b, a)` may produce 
different bytes in LIST and SET
     modes, because coupon insertion order differs.
   - Scalar (literal sketch bytes) versus column arguments, and a per-row 
non-constant flag.
   
   ### 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`. 4.0 also maps
     `SketchesArgumentException` and `ArrayIndexOutOfBoundsException`, and adds 
sqlStates.
   - The docs group changed from `misc_funcs` to `sketch_funcs` in 4.2. This 
does not change behavior.
   
   ### Implementation notes
   
   - Spark source: 
`sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/datasketchesExpressions.scala`,
     `HllUnion`. Golden file: 
`sql/core/src/test/resources/sql-tests/results/hll.sql.out`.
   - Note the difference from `hll_union_agg`. That aggregate returns 
`Union.toUpdatableByteArray`, the union
     gadget itself, and takes the union's K from the first sketch. `hll_union` 
returns
     `getResult(HLL_8).toUpdatableByteArray` from a union sized `min(k1, k2)`. 
Both are HLL_8 and updatable,
     but they are separate code paths.
   - DataFusion core has no equivalent. The Apache `datasketches` Rust crate 
(0.6.0) has `HllUnion`, but its
     `serialize()` writes the compact layout for LIST and SET, and Spark writes 
the updatable layout. Share
     the union and serializer code with `hll_sketch_agg`, `hll_union_agg` and 
`hll_sketch_estimate`.
   - Put it in a new `sketch` module under `crates/spark/src/function/` (or 
`misc`), next to
     `hll_sketch_estimate`.
   - Tests: add `crates/sqllogictest/test_files/sketch/hll_union.slt` (or under 
`misc/`), with byte goldens
     (`hex(hll_union(...))`) 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