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]