KllItemsSketch: querying before serialization corrupts the round-tripped sorted view

[jaideeppyne]

Querying a heap KllItemsSketch before serializing it makes the round-trip return wrong quantiles. The bytes are fine, the flag inside them is not.

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:

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:

//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.