lance-format / lance-format/lance
Add row id / partition index structure to IVF/PQ index to help with highly selective prefilters
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 7.1k
- Forks
- 852
- Avg merge
- 3d 18h
- Merged PRs (30d)
- 272
Description
When an IVF/PQ index is searched with a high selective prefilter it is often the case that the partitions we pick are not the best partitions. This is because we pick the partitions closest to the query vector but these partitions don't necessarily have any rows that match the prefilter.
Instead, we should store a bloom filter (based on the row id) with each IVF partition. If we detect the prefilter search is highly selective then we can switch to a mode where we probe the bloom filter to prefilter IVF partitions. This would provide much better results when the prefilter is highly selective.
However, this will add some to the overall size of the IVF partitions, and this size penalty will get worse as the overall scale of the dataset increases. These bloom filters could be stored / cached separately so they are only loaded if a highly selective prefilter is detected, or we could just keep it simple and include them as part of the IVF storage.
For example, given 1Bi rows, if we divide these into 32Ki partitions with 32Ki rows per partition then the IVF storage is only ~3-6KB per partition (IVF storage is just one full resolution vector per partition). The corresponding bloom filter, however, would require ~40KB per partition.
With 16Mi rows the consequence is less dire. The size of the bloom filter would be more or less the same as the size of the IVF storage so we would be doubling storage.
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 by locating the IVF/PQ index implementation, IVF partition storage, and the highly selective prefilter search path. The issue leaves the row-id structure, bloom-filter placement, detection criteria, and validation approach open; done would require a decided design and evidence that selective-prefilter searches choose matching partitions without an unacceptable storage increase.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data, machine-learning, search
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100