Hacktoberfest 2026 : les issues que les mainteneurs ont marquées pour octobre, ouvertes et accessibles aux débutants. Parcourir les issues Hacktoberfest

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

Fermée Adaptée aux débutants
  • Quelque chose ne va pas ?
#756 1 commentaire 0 réactions 0 personnes assignées Voir sur GitHub

Les mainteneurs répondent en général sous 1 jour

Personne n'a encore pris cette issue.

Évaluation

Difficulté
2/5
Temps estimé
1-3 heures
Accessibilité débutants
76/100
Type d'issue
Bug
Clarté
Clairement spécifiée
Activité
Active
Stack technique
java
Domaine
data

Piste de recherche

Commencez par KllItemsSketch.CreateSortedView.getSV() et KllHeapItemsSketch.getTotalItemsArray(), puis suivez la manière dont KllHelper sérialise le flag level-zero-sorted et dont heapify/wrap le consomment. Reproduisez le cas fourni d’un heap sketch à quatre éléments, y compris wrap(), et comparez les vues triées et les quantiles d’origine avec ceux obtenus après le round-trip. C’est terminé lorsque les requêtes effectuées avant la sérialisation ne modifient plus les résultats après le round-trip.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

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.

Langage dominant
Java
Étoiles
958
Forks
226
Merge moyen
2 j 5 h
PR mergées (30 j)
15

Préparer son environnement

Ce projet ne fournit ni conteneur de développement, ni Dockerfile, ni guide de contribution : l'installation est à votre charge. Commencez par son README, et consultez notre guide de la première contribution pour les étapes générales.

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de apache/datasketches-java

Toutes les issues de apache/datasketches-java

Issues similaires

Plus d'issues Java

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.