apache / apache/datasketches-java
KllItemsSketch: querying before serialization corrupts the round-tripped sorted view
- 主要言語
- Java
- スター
- 958
- フォーク
- 226
- 平均マージ
- 3日 9時間
- マージ済み PR(30日)
- 8
説明
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.
コントリビューションガイド
このリポジトリのコントリビューションガイドは索引されていません
調査の方向性
KllItemsSketch.CreateSortedView.getSV() と KllHeapItemsSketch.getTotalItemsArray() から始め、次に KllHelper が level-zero-sorted フラグをどのようにシリアライズし、heapify/wrap がそれをどのように使用するかを追跡します。wrap() を含め、提示された 4 要素の heap sketch のケースを再現し、元のソート済みビューと round-trip 後のソート済みビュー、および分位点を比較します。シリアライズ前のクエリによって round-trip 後の結果が変わらなくなれば完了です。
索引モデルが issue の本文から書いたものです。
評価
- 技術スタック
- java
- 領域
- data
- issue の種類
- バグ
- 難易度
- 2/5
- 見積もり時間
- 1〜3時間
- 活発さ
- 活発
- 明瞭さ
- 明確に書かれている
- 初心者へのやさしさ
- 76/100