Skip to content

Implement Spark-compatible hll_union #190

Open

Description

@andygrove

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

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.

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