JingsongLi opened a new pull request, #128: URL: https://github.com/apache/paimon-vector-index/pull/128
Partial Roaring filters previously scanned every matching PQ code. Broad, cluster-correlated filters also need a reliable scan when graph navigation cannot supply enough eligible candidates, and compact indexes with a 64 MiB Reader budget can amplify adjacency I/O. This change selects a matching-PQ scan or bounded graph traversal using matching cardinality, sampled local filter density, estimated/observed graph work, and storage/cache costs. Unsuccessful graph attempts retain the complete matching-node scan. Large compact batches combine deferred scans into query tiles, including broad filters and sources that cannot clone their Reader, while restoring original query order before returning results. Compact local-storage searches validate a complete adjacency page on first access, then read bounded records, coalesce nearby required ranges, and share a temporary BFS prefix during large high-match batches. The prefix borrows released adjacency/raw-cache allowances and is dropped before rerank; guards restore cache capacities on errors and unwinding. The index format and top-K APIs remain unchanged, and the upstream range-search and unified-statistics integration is preserved. The benchmarks now cover radial vector-correlated filters, count graph/probe/scan PQ work and logical read rounds/ranges/bytes, and use synchronous native DiskANN reads to avoid nested Rayon/cache-wait deadlocks. ### Validation - Two review rounds, with a failing-then-passing regression for tiled graph fallback. The regression covers 257/1027 queries, mixed graph success/fallback, chunk boundaries, result ordering, exact PQ accounting, and cloneable/noncloneable Readers. - Rebased onto `apache/main` at `ffea751`; `cargo test --release --workspace`: **761 passed, 2 ignored, 0 failed**. - `cargo clippy --all-targets --workspace -- -D warnings`, `cargo fmt --all -- --check`, ASF license headers, and `git diff --check` pass. - SIFT1M acceptance rerun on the rebased commit: **384 cells**, using 1,000 queries, Top-10, L=200, PQ32x8, and 12 threads. Configurations: F32/64 MiB, F16/64 MiB, and F32/4 GiB. Each covers random/radial-cluster filters at 0.01%, 0.1%, 1%, 10%, 25%, 50%, 90%, and 100%, with scan/adaptive, local/remote, and cold/warm cases. Maximum Recall@10 loss versus matching-PQ scan is **0.08 percentage points**, within the existing 1-point gate. For 90% clustered filtering under 64 MiB, both F32 and F16 retain 80 full-scan fallbacks per 1,000 queries: | Metric | Forced PQ scan | Adaptive | | --- | ---: | ---: | | Recall@10 | 0.9954 | 0.9948 | | PQ distance evaluations | 900,000,000 | 77,711,961 | | PQ code loads | 225,000,000 | 23,711,961 | Compared with the intermediate per-query fallback implementation, deferred tiling reduces PQ code loads from 77,711,961 to 23,711,961 (**69.5%**), retaining Recall, PQ evaluation count, and the 64 MiB warm-cache logical I/O counts. Cold-cache requested bytes differ by less than 0.02%. Full matrices record latency as well; these single-run timings do not establish a paired speedup. I/O counters measure logical adapter requests, cold/warm describe Reader query caches, and remote cases use a local file with zero injected RTT. Reproduce the filtered matrix with a retained compact index (repeat with F16 and a 4 GiB budget): ```bash RAYON_NUM_THREADS=12 \ DISKANN_BASE_FVECS=/path/to/sift1m_base.fvecs \ DISKANN_QUERY_FVECS=/path/to/sift1m_query.fvecs \ DISKANN_GROUND_TRUTH_IVECS=/path/to/sift1m_ground_truth.ivecs \ DISKANN_BENCH_INPUT_INDEX=/path/to/compact.index.dann \ DISKANN_BENCH_FILTERED_ONLY=1 \ DISKANN_BENCH_READER_MEMORY_BUDGET_BYTES=67108864 \ DISKANN_BENCH_SIMULATED_RTT_MS=0 \ DISKANN_BENCH_ACCEPTANCE=1 \ cargo bench --offline -p paimon-vindex-core --bench diskann_bench ``` -- 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]
