jaideeppyne opened a new issue, #756:
URL: https://github.com/apache/datasketches-java/issues/756
Querying a heap `KllItemsSketch` before serializing it makes the round-trip
return wrong quantiles. The bytes are fine, the flag inside them is not.
```java
KllItemsSketch<String> sk = KllItemsSketch.newHeapInstance(8,
Comparator.naturalOrder(), new ArrayOfStringsSerDe());
sk.update("a"); sk.update("b"); sk.update("c"); sk.update("d");
sk.getQuantile(0.5, INCLUSIVE); // any query is enough
KllItemsSketch<String> rt = KllItemsSketch.heapify(
MemorySegment.ofArray(sk.toByteArray()), Comparator.naturalOrder(),
serDe);
```
```
orig SV = [a, b, c, d]
heapified SV = [a, d, c, b, a, d]
rank=0.50 orig=b heapified=c
rank=0.55 orig=c heapified=b
```
Four items in, a six-element sorted view out, in raw insertion order with
duplicated min and max. `wrap()` behaves the same. Without the query first
there is no difference at all. At n=8, 15 of 21 probed ranks disagree.
`KllItemsSketch.CreateSortedView.getSV()` sorts level 0 and then records
that it did:
```java
final T[] srcQuantiles = getTotalItemsArray();
...
if (!isLevelZeroSorted()) {
Arrays.sort(srcQuantiles, srcLevelsArr[0], srcLevelsArr[1], comparator);
if (!hasMemorySegment()) { setLevelZeroSorted(true); }
}
```
For the heap items variant `getTotalItemsArray()` hands back a defensive
copy (`KllHeapItemsSketch:255-260` does a `System.arraycopy`), so the sort
lands on the copy while the flag is set on the sketch. `KllHelper` then writes
that flag into the serialized image and `heapify`/`wrap` trust it and skip the
sort.
The doubles path does the same thing correctly because
`KllHeapDoublesSketch.getDoubleItemsArray()` returns the live array, which is
what makes the comment at `KllDoublesSketch:562` true:
```java
//we don't sort level0 in MemorySegment, only our copy.
```
So this looks specific to the generic Items variant rather than a design
choice. Floats, Longs, Req and classic quantiles are all unaffected.
Live sketches recover on their own, because `updateItem` re-sorts level 0
and resets the flag, and I could not reproduce it through `merge()` in 30000
cases, so the damage seems confined to serializing a sketch that has been
queried.
Either dropping the `setLevelZeroSorted(true)` here or returning the live
array from `KllHeapItemsSketch.getTotalItemsArray()` would fix it. I did not
send a patch because I have another PR open here (#755) and did not want two at
once, but I am happy to put one up.
Found while fuzzing quantile invariants across the families: about 95000
randomized configurations over KllDoubles/Floats/Longs/Items, ReqSketch and
classic quantiles, heap and direct, heapify and wrap, ten data distributions.
This was the only invariant violation. Related but not the same as the closed
#527, which was about which comparator level 0 is sorted with.
AI disclosure: I used Claude Code for the fuzzing harness and to narrow this
down. I ran and checked the repro myself.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
