lance-format / lance-format/lance

Missing maximum_nprobes affects performance even when there is no prefilter

Open
#5,637 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

performance
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.