tisonkun opened a new issue, #219: URL: https://github.com/apache/datasketches-rust/issues/219
## Description `Compactor::merge` appends the other compactor's items and marks the result as unsorted. This is safe only while the in-memory `is_sorted` flag is preserved. The REQ wire format stores that flag for level 0 only, and `ReqSketch::deserialize` assumes every higher level is sorted. As a result, serializing and deserializing a merged sketch can silently change rank results: higher-level items remain physically unsorted, but the restored sketch binary-searches them as if they were sorted. Images produced by Rust may also be interpreted incorrectly by the Java and C++ implementations, whose merge paths preserve sorted higher levels. Relevant code: - [`Compactor::merge` appends items and sets `is_sorted = false`](https://github.com/apache/datasketches-rust/blob/bcb83e629ae86eb8619bb7eb0a372a172c94b79c/datasketches/src/req/compactor.rs#L119-L129) - [`ReqSketch::deserialize` marks all levels above level 0 as sorted](https://github.com/apache/datasketches-rust/blob/bcb83e629ae86eb8619bb7eb0a372a172c94b79c/datasketches/src/req/sketch.rs#L672-L676) ## Reproduction ```rust use datasketches::req::{ReqSketch, SearchCriteria}; let mut high = ReqSketch::<f64>::new(); let mut low = ReqSketch::<f64>::new(); for value in 1000..=1072 { high.update(value as f64); } for value in 0..=72 { low.update(value as f64); } high.merge(&low).unwrap(); let restored = ReqSketch::<f64>::deserialize(&high.serialize()).unwrap(); let view = restored.sorted_view(); for value in 0..=1072 { let value = value as f64; assert_eq!( restored.rank(&value, SearchCriteria::Inclusive).unwrap(), view.rank(&value, SearchCriteria::Inclusive).unwrap(), ); } ``` On current `main`, one run reported `0.0958904109589041` from `ReqSketch::rank` and `0.0136986301369863` from `SortedView::rank` for the same query after the round trip. ## Expected fix - Make `Compactor::merge` preserve the ordering invariant required by the wire format. Sorting unsorted inputs and performing an ordered merge, as the Java and C++ implementations do, is one possible approach. - Check or assert that the two compactors have the same `lg_weight` before merging them. - Add a regression test that merges sketches containing reverse, disjoint ranges, serializes and deserializes the result, and verifies that direct ranks equal sorted-view ranks across representative queries. - Keep serialization-related coverage in `datasketches/tests/serde_tests/req.rs`, following `CONTRIBUTING.md`. Introduced with the REQ implementation in #204. -- 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]
