lance-format / lance-format/lance
Missing maximum_nprobes affects performance even when there is no prefilter
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 7.1k
- Forks
- 852
- Avg merge
- 3d 18h
- Merged PRs (30d)
- 272
Description
The docs state:
/// Configures the maximum number of partitions to search in the vector index.
///
/// These partitions will only be searched if we have not found `k` results after
/// searching the minimum number of partitions. Setting this to None (the default)
/// will search all partitions if needed.
///
/// This setting only takes effect when a prefilter is in place. In that case we
/// can spend more effort to try and find results when the filter is highly selective.
///
/// If there is no prefilter, or the results are not highly selective, this value will
/// have no effect.
However, I have the following search:
dataset
.scan()
.nearest("vector", q.as_ref(), K)
.unwrap()
.minimum_nprobes(NPROBES)
.maximum_nprobes(NPROBES)
.refine(REFINE_FACTOR)
.project(&["vector", "_distance"])
.unwrap()
If I drop the maximum_nprobes(NPROBES) then the search is 5x slower. Given there are NPROBES * 5 total partitions in the index I'm guessing it is searching all partitions. It should only do this if it needs to search the extra partitions to find the K results. Since there is no prefilter it should be finding the K results immediately and should not need the extra search.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start from the nearest, minimum_nprobes, and maximum_nprobes entry points shown in the search chain and trace how partition limits are applied without a prefilter. Reproduce the difference with and without maximum_nprobes, then add a regression test demonstrating that an unfiltered search does not scan unnecessary extra partitions.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- performance, search
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100