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]

Reply via email to