Skip to content

Implement Spark-compatible hll_sketch_estimate #189

Open

Description

@andygrove

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

What the function does

hll_sketch_estimate(sketch) is a scalar function. It reads a serialized Apache DataSketches HLL sketch
(BINARY) and returns its estimate of the number of distinct values as BIGINT, computed as
Math.round(HllSketch.heapify(bytes).getEstimate()). Typical inputs are the outputs of hll_sketch_agg,
hll_union_agg and hll_union (see the sibling issues). Any valid DataSketches HLL sketch is accepted
(HLL_4/6/8, compact or updatable layout), so values written by other DataSketches libraries work too.

  • Argument: BINARY only. Spark uses ExpectsInputTypes and applies no implicit casts.
  • Returns BIGINT. NULL input gives NULL (null-intolerant).
  • Available since Spark 3.5.0. No aliases.

The estimate depends on the sketch's internal state, not only on its set of coupons.
HllSketch.getEstimate behaves as follows:

  • LIST and SET modes: the coupon-count estimator.
  • HLL mode without the out-of-order flag: the HIP accumulator.
  • HLL mode with the out-of-order flag (set by any Union in HLL mode): the composite estimator.

The kernel must therefore reproduce DataSketches' estimators exactly, including the HIP and kxq fields
read from the bytes. Recounting registers is not enough.

Examples

SELECT hll_sketch_estimate(hll_sketch_agg(col)) FROM VALUES (1), (1), (2), (2), (3) tab(col);
-- 3
SELECT hll_sketch_estimate(hll_sketch_agg(col)) AS result
FROM VALUES (0), (1), (2), (2), (2), (3), (4) tab(col);
-- 5
SELECT hll_sketch_estimate(hll_sketch_agg(col, 12)) FROM VALUES (50), (60), (60), (60), (75), (100) tab(col);
-- 4
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_sketch_estimate(CAST('abc' AS BINARY));
-- error HLL_INVALID_INPUT_SKETCH_BUFFER (function `hll_sketch_estimate`)

Edge cases to test

  • NULL input returns NULL.
  • An empty sketch, such as hll_sketch_agg over an all-NULL group or hll_union_agg over empty input,
    returns 0. A Spark test asserts 0 for an all-NULL group.
  • A zero-length BINARY (X''), random bytes, a truncated sketch, and a sketch with a corrupted preamble
    all raise HLL_INVALID_INPUT_SKETCH_BUFFER. The condition is a SparkRuntimeException with sqlState
    22546 and the message "Invalid call to hll_sketch_estimate; only valid HLL sketch buffers are
    supported as inputs (such as those produced by the hll_sketch_agg function)." Spark maps
    SketchesArgumentException, java.lang.Error and ArrayIndexOutOfBoundsException to it.
  • Sketches in LIST, SET and HLL modes, at lgConfigK 4, 12 and 21, and in HLL_4 and HLL_6 (produced by
    another DataSketches library) as well as HLL_8.
  • Compact versus updatable layout of the same sketch: the estimate is the same.
  • A sketch that went through a union (out-of-order flag set) versus the same values added directly. Both
    estimates must match Spark exactly, including the rounding of .5 (Math.round is floor(x + 0.5)).
  • Column input versus a literal X'...' sketch.
  • STRING input is rejected at analysis with UNEXPECTED_INPUT_TYPE (required "BINARY").

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.
    Estimator code should be compared against the version a consumer targets.
  • In 3.5 only java.lang.Error was mapped to HLL_INVALID_INPUT_SKETCH_BUFFER. Other parse failures
    surfaced as raw exceptions. The sqlState 22546 was added in 4.0.
  • 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,
    HllSketchEstimate. Golden file: sql/core/src/test/resources/sql-tests/results/hll.sql.out.
  • DataFusion core has no DataSketches functions. approx_distinct uses its own HLL format.
  • The Apache datasketches Rust crate (0.6.0, hll feature) has HllSketch::deserialize and
    estimate(), which handle the compact and updatable layouts. Before relying on it, verify that its
    HIP, composite and coupon estimators and its out-of-order handling are numerically identical to Java.
    Share the code with hll_sketch_agg, hll_union_agg and hll_union.
  • Put it in a new sketch module under crates/spark/src/function/ (or misc), next to hll_union.
  • Tests: add crates/sqllogictest/test_files/sketch/hll_sketch_estimate.slt (or under misc/). Include
    literal sketch bytes captured from real Spark 4.2, so the estimate is tested independently of
    hll_sketch_agg. 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