Skip to content

Implement Spark-compatible hll_sketch_agg #187

Open

Description

@andygrove

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

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.

Activity

  1. andygrove commented on Nov 15, 2026

    @andygrove
    MemberAuthor

    Note

    An LLM (Claude Code) wrote this comment. Check the details before you rely on them.

    Apache DataFusion Comet already has a native, Spark-compatible implementation of this, which can be ported here along with its tests. Comet source (at 3878424d9):

    (This was tracked in #157, now closed as a duplicate.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions