google / google/zetasketch

[Estimation Bug] sparse mode destructively consumes other sketch's sparse data, making it unreadable after merge

Open
#17 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
169
Forks
23
PR merge metrics
No merged PRs in 30d

Description

When merging two HLL++ sketches in sparse mode, the source sketch's `sparseData` position cursor is advanced to the limit during iteration in `sortedIterator()`. This makes the source sketch appear empty after the merge, causing incorrect estimates.

**Steps to reproduce:**

```java
package io.github.bareboneslib.hll_benchmarks;

import com.google.zetasketch.HyperLogLogPlusPlus;

public class Test {
public static void main(String[] args) {
int p = 12;
HyperLogLogPlusPlus hll1 = new HyperLogLogPlusPlus.Builder().sparsePrecision(p + 4).normalPrecision(p).buildForStrings();
HyperLogLogPlusPlus hll2 = new HyperLogLogPlusPlus.Builder().sparsePrecision(p + 4).normalPrecision(p).buildForStrings();
for(long i =0;i<2000; i++) {
hll1.add(i + "");
}
byte[] tmp = hll1.serializeToByteArray();
System.err.println(tmp.length);
hll1.add("hi");
hll2.merge(hll1);

System.out.println(hll1.result());
System.out.println(hll2.result());
}
}
```

**Expected behavior:**
`hll1.result()` should return ~2000 after being merged into `hll2`.

**Actual behavior:**
`hll1.result()` returns ~1 after the merge. The source sketch is silently mutated as a side effect of being the merge source.

**Root cause:**
`dataIterator()` and `bufferIterator()` iterate directly over the source's `ByteSlice`/`GrowingByteSlice` using relative cursor reads (`getNextVarInt()`), advancing `position` to `limit` without resetting it afterwards.

**Suggested fix:**
Introduce a `sortedIteratorForMerge()` that iterates over `ByteSlice.copyOnWrite()` snapshots of `sparseData` and `buffer`, leaving the source sketch's cursors untouched.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.