Make the deferred KxQ rebuild canonical, stop HIP drifting after a merge, set the compact flag for HLL_6/HLL_8

Four defects in the HLL union's deferred rebuild and the flags it writes.

1. checkRebuildCurMinNumKxQ stores the true minimum register value and the
count at that minimum, while Hll8Array.updateSlotWithKxQ maintains a different
representation, the one its own comment describes as "interpret numAtCurMin as
num Zeros", decrementing only when oldValue == 0. When the merged array has no
zero register the rebuild leaves curMin > 0 and numAtCurMin is never
maintained again, so it freezes and drifts away from the registers. Because
the rebuild is triggered lazily by accessors this is directly observable:
calling getEstimate() changes the bytes a later getResult() produces. At
lgMaxK 7, 8 and 9 the peeked and unpeeked images of the same content differ,
with the unpeeked one correct. Estimates and bounds are unaffected because
both consumers of numAtCurMin branch on curMin == 0. Emit the canonical form
instead, so the rebuilt state is indistinguishable from the incrementally
maintained state and the timing of the rebuild is not observable.

2. putOutOfOrder(true) zeroes hipAccum, but hipAndKxQIncrementalUpdate adds to
it unconditionally, so every coupon applied after a merge keeps accumulating
into a field that is dead once out-of-order is set. The value reached is not a
function of the content either: while the rebuild flag is pending the
increment is computed against the empty-sketch KxQ defaults, giving 131328 or
396579 for the same sketch depending only on whether an estimate was read.
This is also what makes a union result's byte image merge-order dependent.
Guard the accumulation on the out-of-order flag.

3. HllArray.toCompactByteArray() returned toUpdatableByteArray(), so the
compact flag was never set for HLL_6 and HLL_8, while LIST, SET and HLL_4 all
set it. The flag means both that the data is compacted where possible and that
the image is immutable; the second applies to every target type. Set it for
those two types as well, on the heap and direct paths, both of which operate
on a copy so a wrapped segment is never modified.

4. The two relative-error constants were computed with Math.log, which is
specified only to within 1 ulp and may use a platform intrinsic. Pin them to
the literals Double.toString prints for the computed values, so neither
implementation computes a shared constant at runtime.

This changes serialized bytes: union results carry different curMin,
numAtCurMin and hipAccum, and HLL_6 and HLL_8 compact images differ by the
flag bit. Reading is unaffected. One behavioural change beyond the bytes: a
compact image is treated as immutable, so writableWrap now rejects an HLL_6 or
HLL_8 image produced by toCompactByteArray(), where it previously succeeded.
Callers needing a writable wrap should use toUpdatableByteArray().

HllSketchTest.checkCompactFlag is updated: all five modes now follow the
toByteArray request. Adds HllKxqRebuildTest; four of its five cases fail
without this change, the fifth guards the constants against re-rounding.

With the companion datasketches-cpp changes, a 1041 record corpus spanning
lgK 4..21, all three target types, 17 sizes across LIST/SET/HLL, round trips
and 80 union scenarios goes from 428 differing records to 0, comparing every
serialized byte, estimate, composite estimate and bound as raw IEEE bits.

Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
7 files changed
tree: 2c77a76c1ccac46f1f146ddd11343da7f2f15387
  1. .github/
  2. .mvn/
  3. src/
  4. tools/
  5. .asf.yaml
  6. .gitattributes
  7. .gitignore
  8. LICENSE
  9. NOTICE
  10. pom.xml
  11. README.md
README.md

Maven Central Coverage Status


Apache® DataSketches™ Core Java Library Component

This is the core Java component of the DataSketches library. It contains all of the sketching algorithms and can be accessed directly from user applications.

This component is also a dependency of other components of the library that create adaptors for target systems, such as the Apache Pig adaptor, the Apache Hive adaptor, and others.

Note that we have parallel core library components for C++, Python, GO, and Rust implementations of many of the same sketch algorithms:

Please visit the main DataSketches website for more information.

If you are interested in making contributions to this site, please see our Community page for how to contact us.

Build & Runtime Dependencies

Installation Directory Path

NOTE: This component accesses resource files for testing. As a result, the directory elements of the full absolute path of the target installation directory must qualify as Java identifiers. In other words, the directory elements must not have any space characters (or non-Java identifier characters) in any of the path elements. This is required by the Oracle Java Specification in order to ensure location-independent access to resources: See Oracle Location-Independent Access to Resources

OpenJDK Version 25

At minimum, an OpenJDK-compatible build of Java 25, provided by one of the Open-Source JVM providers, such as Azul Systems, Red Hat, SAP, Eclipse Temurin, etc, is required. All of the testing of this release has been performed with the Eclipse Temurin build.

Compilation and Test using Maven

This DataSketches component is structured as a Maven project and Maven is the recommended tool for compile and test.

A Toolchain is required

  • You must have a JDK type toolchain defined in location ~/.m2/toolchains.xml that specifies where to find a locally installed OpenJDK-compatible version 25.
  • Your default $JAVA_HOME compiler must be OpenJDK compatible, specified in the toolchain, and may be a version greater than 25. Note that if your $JAVA_HOME is set to a Java version greater than 25, Maven will automatically use the Java 25 version specified in the toolchain instead. The pom.xml specifies any necessary JVM flags, if required, so no further action is needed.
  • Note that the paths specified in the toolchain must be fully qualified direct paths to the OpenJDK version locations. Using environment variables will not work.

To run normal unit tests:

$ mvn clean test

To install jars built from the downloaded source:

$ mvn clean install -DskipTests=true

This will create the following jars:

  • datasketches-java-X.Y.Z.jar The compiled main class files.
  • datasketches-java-X.Y.Z-tests.jar The compiled test class files.
  • datasketches-java-X.Y.Z-sources.jar The main source files.
  • datasketches-java-X.Y.Z-test-sources.jar The test source files
  • datasketches-java-X.Y.Z-javadoc.jar The compressed Javadocs.

Known Issues

SpotBugs

  • Make sure you configure SpotBugs with the /tools/FindBugsExcludeFilter.xml file. Otherwise, you may get a lot of false positive or low risk issues that we have examined and eliminated with this exclusion file.

Checkstyle

  • At the time of this writing, Checkstyle had not been upgraded to handle Java 25 features.