shyjsarah commented on PR #82: URL: https://github.com/apache/paimon-vector-index/pull/82#issuecomment-5475269621
Follow-up on the latest head (`b00138f`): the wave approach fixes the previously reported high-`nprobe` batch cliff, and replacing stable sorting also fixes the unbudgeted sort scratch. However, applying linear waves to every `nprobe > 1` introduces a larger regression for small probes. At `core/src/kmeans.rs:96-102` and `1333-1354`, any configuration that can fit at least one linear worker enters the wave path, bypassing the parallel bounded-heap path even when `nprobe` is tiny. Reproduction: ```text nq=8, d=8, Rayon threads=32 k=1,048,576, nprobe=1: 1.57 ms k=1,048,576, nprobe=2: 21.74 ms k=1,048,577, nprobe=2: 2.26 ms ``` With `k=1,048,576` and `nprobe=2`, `linear_workers=1`, so all eight queries run as serial linear waves. Increasing `k` by one makes the worker limit zero and falls back to the parallel bounded heap, making it roughly **9.6x faster**. `nprobe=1 -> 2` at the boundary is about a **13.8x latency cliff**. This regression primarily affects **batch query coarse search**, not the IVF-PQ build/add path: construction assigns one nearest centroid through projected assignment or `find_nearest_batch`, while `find_topk_batch` with `nprobe > 1` is used by the IVF-PQ/IVF-Flat/IVF-SQ/IVF-RQ search paths. I suggest enabling linear waves only when `nprobe` is large enough that linear selection is actually preferable; small/moderate `nprobe` should retain the parallel bounded-heap path. All CI checks are currently green and I did not find a correctness issue, but this query-path regression should still be addressed before merge. -- 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]
