apache / apache/datasketches-java

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

Offen Anfängerfreundlich
#756 1 Kommentar 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen
Vorherrschende Sprache
Java
Sterne
958
Forks
226
Ø Merge
3 T. 9 Std.
Gemergte PRs (30 T.)
8

Beschreibung

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

Beitragsleitfaden

Für dieses Repository ist kein Beitragsleitfaden indexiert

Rechercherichtung

Beginnen Sie mit KllItemsSketch.CreateSortedView.getSV() und KllHeapItemsSketch.getTotalItemsArray(), und verfolgen Sie dann, wie KllHelper das level-zero-sorted-Flag serialisiert und wie heapify/wrap es verwenden. Reproduzieren Sie den bereitgestellten Fall eines vier Elemente umfassenden Heap-Sketches, einschließlich wrap(), und vergleichen Sie die ursprünglichen und nach dem Roundtrip erhaltenen sortierten Ansichten und Quantile. Die Aufgabe ist abgeschlossen, wenn Abfragen vor der Serialisierung die Ergebnisse nach dem Roundtrip nicht mehr verändern.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Bewertung

Tech-Stack
java
Bereich
data
Issue-Typ
Bug
Schwierigkeit
2/5
Geschätzter Aufwand
1-3 Stunden
Aktivitätsstatus
Aktiv
Klarheit
Klar beschrieben
Anfängerfreundlichkeit
76/100

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.