andygrove opened a new issue, #187:
URL: https://github.com/apache/datafusion-spark/issues/187
Part of #173 and apache/datafusion-comet#7300.
### What the function does
`hll_sketch_agg(expr [, lgConfigK])` is an aggregate that feeds every
non-NULL value of `expr` into an
Apache DataSketches `HllSketch` and returns the sketch serialized as
`BINARY`. Spark builds the sketch with
`TgtHllType.HLL_8` and serializes it with `HllSketch.toUpdatableByteArray`
(the updatable layout, not the
compact one). The bytes are visible to users: they get stored in tables and
read back later by
`hll_sketch_estimate`, `hll_union` and `hll_union_agg` (see the sibling
issues). They can also be read by
other DataSketches libraries. The output therefore has to match Spark byte
for byte, not just give the same
estimate.
- `expr`: `INT`, `BIGINT`, `STRING` (any collation, including trim
collations from 4.1) or `BINARY`.
Spark uses `ExpectsInputTypes`, so it applies no implicit casts.
`TINYINT`, `SMALLINT`, `DOUBLE`,
`DECIMAL`, dates and so on fail analysis with
`DATATYPE_MISMATCH.UNEXPECTED_INPUT_TYPE`.
- `lgConfigK`: an `INT` constant in `[4, 21]`, default `12`
(`HllSketch.DEFAULT_LG_K`). A `STRING` such as
`'15'` is rejected at analysis. A `BIGINT` literal is rejected too.
- Return type is `BINARY` and is never NULL (`nullable = false`). Available
since Spark 3.5.0. It has no
aliases.
How each type is hashed (DataSketches `update` overloads, MurmurHash3
x64-128, seed 9001):
- `INT` is widened to `long` and goes through `update(long)`, the only
integer overload. So `1` and `1L`
hash identically.
- `BIGINT` uses `update(long)`.
- `BINARY` uses `update(byte[])`. Empty arrays are skipped by DataSketches.
- `STRING` (4.1+): values that are collation-equal to `''` are skipped.
Every other value is hashed with
`update(byte[])` over `collation.sortKeyFunction(str)`. For `UTF8_BINARY`
that key is the raw UTF-8
bytes, invalid sequences included. For `UTF8_LCASE` it is the lowercased
code points. For ICU collations
it is the ICU collation key bytes. Trim collations trim spaces first.
### Examples
```sql
SELECT hll_sketch_estimate(hll_sketch_agg(col, 12)) FROM VALUES (1), (1),
(2), (2), (3) tab(col);
-- 3
SELECT hll_sketch_estimate(hll_sketch_agg(col)) FROM VALUES ('abc'),
('def'), ('abc'), ('ghi'), ('abc') tab(col);
-- 3
-- hll_binary_test holds X'', CAST(' ' AS BINARY), X'e280', X'c1', X'c120'
SELECT hll_sketch_estimate(hll_sketch_agg(bytes)) FROM hll_binary_test;
-- 4 (X'' is ignored)
-- hll_string_test (Spark's hll.sql) holds ''; ' '; CAST(X'C1' AS STRING);
CAST(X'80' AS STRING);
-- '\uFFFD'; 'Å'; 'å'; 'a\u030A'; 'Å '; 'å '; 'a\u030A '
SELECT hll_sketch_estimate(hll_sketch_agg(s)) FROM hll_string_test;
-- 10
SELECT hll_sketch_estimate(hll_sketch_agg(s COLLATE UTF8_LCASE)) FROM
hll_string_test; -- 7
SELECT hll_sketch_estimate(hll_sketch_agg(s COLLATE UNICODE)) FROM
hll_string_test; -- 7
SELECT hll_sketch_estimate(hll_sketch_agg(s COLLATE UNICODE_CI)) FROM
hll_string_test; -- 6
SELECT hll_sketch_estimate(hll_sketch_agg(s COLLATE UTF8_BINARY_RTRIM)) FROM
hll_string_test; -- 6
SELECT hll_sketch_estimate(hll_sketch_agg(s COLLATE UNICODE_CI_RTRIM)) FROM
hll_string_test; -- 2
SELECT hll_sketch_agg(col, 2) FROM VALUES (50), (60), (60) tab(col);
-- error HLL_INVALID_LG_K (function `hll_sketch_agg`, min 4, max 21, value 2)
SELECT hll_sketch_agg(col, CAST(NULL AS INT)) FROM VALUES (15), (16), (17)
tab(col);
-- error HLL_INVALID_LG_K with value 0 (a NULL k is unboxed to 0)
SELECT hll_sketch_agg(col, CAST(col AS INT)) FROM VALUES (15), (16), (17)
tab(col);
-- error HLL_K_MUST_BE_CONSTANT (4.1+)
```
### Edge cases to test
- Empty input (global aggregate) and an all-NULL group: the result is an
empty sketch, not NULL. A Spark
test asserts `hll_sketch_estimate(hll_sketch_agg(value))` is `0` for an
all-NULL group. The exact
serialized bytes of the empty `lgConfigK=12` updatable sketch should be
checked against Spark.
- A single row, and a group that mixes NULLs with values (NULLs are skipped).
- An empty `BINARY` value and an empty `STRING` are skipped. Under trim
collations, strings made only of
spaces are skipped as well.
- Invalid UTF-8 in `STRING` (`X'C1'`, `X'80'`): under `UTF8_BINARY` these
stay distinct from `'\uFFFD'`
(4.1+).
- `lgConfigK` at 4, 21, 3 and 22. NULL `lgConfigK` raises the `value 0`
error shown above. A non-constant
`lgConfigK` raises `HLL_K_MUST_BE_CONSTANT` (sqlState `42K0E`).
- `HLL_INVALID_LG_K` is a `SparkRuntimeException` with sqlState `22546`. It
is raised lazily, when the
aggregate buffer is created, not during analysis.
- Unsupported input types are rejected at analysis with
`UNEXPECTED_INPUT_TYPE`, whose required type is
`("INT" or "BIGINT" or "STRING" or "BINARY")`.
- Byte-exact output across the sketch modes: LIST (few values), SET, and HLL
array (for example 10^5
distinct values at `lgConfigK=12`). Also cover `lgConfigK < 8`, where LIST
promotes straight to HLL.
- Merge path: Spark's `merge` builds `new Union(lgConfigK)`, updates it with
both buffers and returns
`union.getResult(HLL_8)`. Once a sketch reaches HLL mode, the union sets
the out-of-order flag. Estimates
then switch from the HIP estimator to the composite estimator, and the
serialized bytes change. So the
result depends on how many partial buffers were merged. Single-partition
and multi-partition plans are
not interchangeable, so test both. Partial buffers are also serialized
with `toUpdatableByteArray` and
read back with `HllSketch.heapify`.
- In LIST and SET modes the coupon layout depends on insertion order. Byte
identity can only be expected
for the same input order and the same partitioning.
- DISTINCT (`hll_sketch_agg(DISTINCT col)`) gives the same estimate, but the
bytes may differ because the
insertion order differs.
- Determinism: the bytes can depend on row order and partitioning even
though the estimate rarely does.
### Differences across Spark versions
- Not available in 3.4. Added in 3.5.0. Spark 3.5 uses datasketches-java
3.3.0, 4.0 uses 6.1.1, and
4.1/4.2 use 6.2.0. The HLL serialization format is the same across these
releases.
- `STRING` hashing changed:
- 3.5: `update(String)`, which hashes
`UTF8String.toString().getBytes(UTF_8)`. Invalid UTF-8 is replaced
with U+FFFD first, so `X'C1'`, `X'80'` and `'\uFFFD'` all collide.
- 4.0: `update(CollationFactory.getCollationKey(...).toString)`. This is
the same as 3.5 for
`UTF8_BINARY`, but ICU keys are round-tripped through a Java `String`.
- 4.1+: `update(collation.sortKeyFunction(str))` on raw bytes, and
collation-equal-to-empty strings are
skipped. The golden outputs above exist only from 4.1.
- 4.1 added the constant check and `HLL_K_MUST_BE_CONSTANT`. In 3.5 and 4.0
a non-foldable `lgConfigK` is
evaluated without an input row, and no dedicated error condition exists.
- 3.5 passes `value` to `HLL_INVALID_LG_K` as a string. 4.x formats it as an
INT SQL value. sqlStates
were added in 4.0.
- An unsupported type that reaches `update` raises `_LEGACY_ERROR_TEMP_3121`
in 4.x and a plain
`UnsupportedOperationException` in 3.5.
### Implementation notes
- Spark source:
`sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/datasketchesAggregates.scala`,
`HllSketchAgg` (a `TypedImperativeAggregate[HllSketch]`), plus the
`HllSketchAgg.checkLgK` companion.
Golden file: `sql/core/src/test/resources/sql-tests/results/hll.sql.out`.
Suite:
`DataFrameAggregateSuite` ("SPARK-16484").
- DataFusion core has no DataSketches functions. `approx_distinct` uses its
own fixed-precision
(p=14) dense HLL derived from Redis, with a different hash and format. It
cannot be reused.
- The Apache `datasketches` Rust crate (0.6.0, `hll` feature) implements HLL
with Java-compatible hashing
via `hash::value::raw_bytes` and `i64` values. However, its `serialize()`
writes the compact layout for
LIST and SET modes, while Spark writes the updatable layout. An updatable
serializer has to be added
(upstream or locally) to get byte-identical output. Union semantics
(`getResult(HLL_8)`, the
out-of-order flag) also need checking against Java.
- Belongs in `crates/spark/src/function/aggregate/` next to `collect.rs`.
The accumulator state should be
the updatable sketch bytes, so that partial and final aggregation match
Spark's `serialize`/`merge`.
Implement it together with `hll_union_agg`, `hll_sketch_estimate` and
`hll_union`, sharing one
sketch/union helper module.
- Tests: add `crates/sqllogictest/test_files/aggregate/hll_sketch_agg.slt`,
porting `hll.sql`. Byte
goldens (`hex(hll_sketch_agg(...))`) must be captured 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]