Skip to content

Implement Spark-compatible hll_union_agg #188

Open

Description

@andygrove

Part of #173 and apache/datafusion-comet#7300.

What the function does

hll_union_agg(sketch [, allowDifferentLgConfigK]) is an aggregate that merges Apache DataSketches HLL
sketches stored as BINARY and returns the merged sketch as BINARY. The inputs are typically produced by
hll_sketch_agg or hll_union (see the sibling issues). Spark wraps each non-NULL input with
HllSketch.wrap, so any valid HLL_4/6/8 sketch in compact or updatable layout is accepted. It feeds them
into a DataSketches Union and returns Union.toUpdatableByteArray. That is the union's internal HLL_8
gadget in the updatable layout. Because the output is user-visible bytes that other HLL functions and
external DataSketches readers consume, it must match Spark byte for byte.

  • sketch: BINARY. allowDifferentLgConfigK: BOOLEAN, default false. Spark uses ExpectsInputTypes
    and applies no implicit casts.
  • allowDifferentLgConfigK is evaluated once, with no input row, so it must be a constant in practice. A
    NULL literal unboxes to false.
  • The union's lgMaxK is the lgConfigK of the first sketch seen by that buffer. Merging a sketch with a
    larger K downsamples it, and merging one with a smaller K downsizes the union. The result lgConfigK is
    therefore the minimum over all inputs.
  • Return type is BINARY, never NULL (nullable = false). Available since Spark 3.5.0. It has no
    aliases.

Examples

SELECT hll_sketch_estimate(hll_union_agg(sketch, true))
FROM (SELECT hll_sketch_agg(col) AS sketch FROM VALUES (1) tab(col)
      UNION ALL
      SELECT hll_sketch_agg(col, 20) AS sketch FROM VALUES (1) tab(col));
-- 1
SELECT hll_union_agg(sketch, false)
FROM (SELECT hll_sketch_agg(col, 12) AS sketch FROM VALUES (1) tab(col)
      UNION ALL
      SELECT hll_sketch_agg(col, 20) AS sketch FROM VALUES (1) tab(col));
-- error HLL_UNION_DIFFERENT_LG_K (left 12, right 20, function `hll_union_agg`)
SELECT hll_union_agg(buffer, false) FROM (SELECT CAST('abc' AS BINARY) AS buffer);
-- error HLL_INVALID_INPUT_SKETCH_BUFFER (function `hll_union_agg`)

Spark's DataFrameAggregateSuite ("SPARK-16484") also unions per-group sketches. In that test, df1 has
values a,a,a,b,c,c,d and df2 has a,c,d,d,d,e,e,f. Taking hll_sketch_estimate(hll_union_agg(...)) over
both gives 6 in every case it checks: both inputs at K=12, both at K=20, and K=12 unioned with K=20
using allowDifferentLgConfigK = true.

Edge cases to test

  • Empty input, or all-NULL input: no Union is ever created. eval returns
    new Union().toUpdatableByteArray, an empty union with the default lgConfigK = 12, regardless of the
    K of any sketches elsewhere. The result is not NULL, and its estimate is 0. Capture the exact bytes from
    Spark.
  • A single row: the output is the union's serialization of that sketch, not the input bytes echoed back
    (the layout and HLL type can change, for example HLL_4 in, HLL_8 out).
  • NULL sketches are skipped. A NULL allowDifferentLgConfigK behaves as false.
  • Different K with the flag false raises HLL_UNION_DIFFERENT_LG_K (sqlState 22000). Parameters:
    left is the union's current K, right is the incoming sketch's K, and function is hll_union_agg.
    The check runs both in update and in merge between partial buffers.
  • Invalid bytes (non-sketch data, truncated or empty BINARY) raise HLL_INVALID_INPUT_SKETCH_BUFFER
    (sqlState 22546). In 4.x Spark maps SketchesArgumentException, java.lang.Error and
    ArrayIndexOutOfBoundsException to this condition.
  • Input sketches in HLL_4 and HLL_6, in compact layout, and in each of the LIST, SET and HLL modes.
  • Merge path: partial buffers are serialized with Union.toUpdatableByteArray (an empty buffer becomes a
    zero-length array) and restored with Union.heapify. merge calls
    union.update(input.getResult(HLL_8)). Once in HLL mode, a union sets the out-of-order flag. After that
    the estimate uses the composite estimator instead of HIP, and the bytes depend on the number and order
    of partial merges.
  • DISTINCT over sketch bytes: the estimate is unchanged. The bytes may change.
  • Determinism: the output bytes depend on input order and partitioning.

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. Other malformed-buffer
    exceptions (SketchesArgumentException, ArrayIndexOutOfBoundsException) surfaced as raw exceptions.
    4.0 widened the mapping.
  • The error conditions have no sqlState in 3.5. 4.0 added 22546 and 22000.

Implementation notes

  • Spark source: sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/aggregate/datasketchesAggregates.scala,
    HllUnionAgg (a TypedImperativeAggregate[Option[Union]]). Golden file:
    sql/core/src/test/resources/sql-tests/results/hll.sql.out.
  • DataFusion core has nothing comparable (approx_distinct is a Redis-style HLL with its own format).
  • The Apache datasketches Rust crate (0.6.0, hll feature) has a HllUnion type. However, its
    serialize() writes the compact layout for LIST and SET, and Spark emits updatable bytes. Its union
    must also reproduce Java's Union downsampling and out-of-order handling exactly. Share the sketch,
    union and serializer code with hll_sketch_agg, hll_sketch_estimate and hll_union.
  • Belongs in crates/spark/src/function/aggregate/. Keep the accumulator state as updatable union bytes,
    with the empty buffer as a zero-length binary, to mirror Spark's partial/final behavior.
  • Tests: add crates/sqllogictest/test_files/aggregate/hll_union_agg.slt. Byte goldens must come 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