JunRuiLee opened a new pull request, #106: URL: https://github.com/apache/paimon-vector-index/pull/106
## Summary Part of #97. Adds IVF-SQ **L2** distance range search on top of current `main`, including the already-merged IVF-RQ support from #104. - Support single and batch queries, each with or without a serialized Roaring allow-list, through both the unified and direct SQ readers. - Reuse `DistanceBand`, `VectorRangeSearchParams`, `RangeSearchResult`, and the generic `Collector` scan seam. Membership is decided by the same blocked SQ-estimated squared-L2 values used by the SQ scanner, not original-vector distances or a capped top-K fallback. - Preserve the existing top-K behavior, other metrics, bindings, and on-disk format. Existing RQ range support remains enabled. - Document quantization-induced membership errors, half-open bounds, statistics, and the supported-family matrix. ## Performance - Retain blocked SIMD evaluation and finite-upper-cut early abandonment. - Read each unique probed list once per batch, reuse the existing partition cache, and stream oversized lists in bounded chunks. - Reuse scan scratch and query-owned collectors; large single queries merge once per list rather than once per row. - Build compact, query-local filter masks once per list/chunk and share them across queries. Masks are not retained in the partition cache; fully excluded lists/chunks skip distance evaluation. A local release-mode synthetic check (macOS arm64, Rust 1.95.0, four Rayon threads; 32,768 rows × 128 dimensions; `nlist=16`, `nprobe=8`, batch size 16, warm 64 MiB cache, 10% Roaring filter) compared the initial range path with repeated filter lookups against shared masks: | Band | Repeated filter lookups | Shared masks | Reduction | | --- | ---: | ---: | ---: | | Narrow `[0, 150)` | 1.594 ms/batch | 0.980 ms/batch | 38.5% | | Dense `[0, 10000)` | 1.775 ms/batch | 1.176 ms/batch | 33.7% | | Empty-hit `[0, 1)` | 1.432 ms/batch | 0.755 ms/batch | 47.3% | These are local microbenchmarks, not production or cross-platform guarantees. Result checksums match before/after mask reuse, and the existing top-K comparison showed identical checksums without a material local slowdown. ## Coverage - SQ-estimate oracle across all four entry points and multiple probe widths. - Exact boundary inclusion/exclusion, unbounded and empty bands, no result cap, and a concrete distinction from original-vector membership. - SIMD blocks/tails, query permutation and parallel scans, cache reuse, query-local filtering, partial-probe deduplication, and bounded multi-range reads. - Oversized-list single/batch/filter paths, invalid queries and metrics, non-finite estimates, payload errors, and fallible streaming. - A lookup-count regression test proves that three queries over 1,024 rows perform 1,024 filter lookups instead of 3,072. ## Validation Executed locally after rebasing onto `c2d9436`: - `cargo fmt --all -- --check` - `cargo clippy --all-targets --workspace -- -D warnings` - `cargo test -p paimon-vindex-core --lib`: 551 passed, 1 existing ignored test. - `cargo test -p paimon-vindex-core --test range_search`: 51 passed, including the existing Flat and RQ cases. - `cargo test -p paimon-vindex-core --release --test range_search`: 51 passed. - `cargo test -p paimon-vindex-core --test storage_format_fixtures`: 2 passed, 1 existing ignored fixture printer. The exact CI Clippy invocation also supplies `-A clippy::chunks-exact-to-as-chunks`, which local Rust 1.95.0 does not recognize. The workspace Clippy command above passes without that lint allowance. Linux/x86_64 and full cross-language CI remain for the repository workflows. There is no storage migration or binding change; reverting this additive PR does not require rewriting index files. ## Known review follow-up Independent review found no blocking issues. One non-blocking P2 hardening follow-up remains: SQ range coarse-probe selection uses the existing unchecked centroid ranking, so a non-finite centroid or an overflowed coarse squared distance in an unselected list can escape validation. This is a source-traced corruption/extreme-value case, not a newly reproduced ordinary-input failure. A follow-up should add SQ-range-only checked probe validation and tests for unselected NaN/overflow cases; existing top-K and RQ behavior remain unchanged here. -- 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]
