support build IVF_FLAT/PQ/SQ vector index distributedly

[chenghao-guo]

Sub-issue of: #4155

• We recently added support for FTS indexes in:
  • Core: feat: support build FTS index distributedly #4578
  • Ray connector: feat: support lance-ray distributed fts indexing building lance-ray#45
• It’s also great to see the distributed B-tree index PR under review by @xloya:
  • feat: support create btree index distributedly #4667
• Given this momentum, additional scalar index types may follow soon.

Proposal: Distributed Vector Index (CPU-based IVF)

• Question: Is there ongoing or existing work on a distributed vector index building?
• Context:
  • Current vector index builds rely on CUDA for acceleration.
  • Single-node index builds still have high resource requirements (e.g., transient disk usage during build), which may also impact distributed scenarios.
• Plan:
  • I intend to begin with a distributed IVF index implementation targeted at CPU-only nodes.
  • The design will draw on approaches from OpenSearch’s KNN and other disk-based ANN systems for building and managing IVF in a distributed setting.

Next steps

• @yanghua and I will conduct research and begin a prototype over the next few months.
• We will share design notes and open a PR once we have a concrete proposal or initial implementation for community feedback.

[yanghua]

big +1, thanks @chenghao-guo for kicking off this issue.

Vector searching is an advanced feature and key point for some users who want to choose Lance for their adoption.

The single-node mode can not maximally release the advantage of this feature. It would be better to speed it up with a distributed mean.

[LuQQiu]

@BubbleCal @wjones127 FYI

[jackye1995]

+1. I think we probably want to do that in platforms like lance-ray, and expose the functions that are necessary to do the distributed indexing.

[chenghao-guo]

+1. I think we probably want to do that in platforms like lance-ray, and expose the functions that are necessary to do the distributed indexing.

Yes— definitely we’ll expose a user-friendly API in lance-ray.

The main challenge is in lance itself: enabling parallel vector index training/building. I’m still in the process of exploring distributed IVF/KMeans (e.g., centroid broadcast/aggregation/update across machines) while avoiding breaking changes. I’ll share an update once I have clearer guidance.

[jackye1995]

@BubbleCal any thoughts on this?

[BubbleCal]

exposing IvfIndexBuilder to python may be a good start

[jackye1995]

@chenghao-guo we just published the full current vector index spec v3: https://lancedb.github.io/lance/format/table/index/vector/

Hopefully that helps with the design.

@BubbleCal currently we only have 2 files. For enabling distributed building, does that mean it might be better to start split them to multiple files?

[westonpace]

@BubbleCal currently we only have 2 files. For enabling distributed building, does that mean it might be better to start split them to multiple files?

I think, for distributed building, we build partial files and then merge them at the end. So the final result still just has two files.

[jackye1995]

then merge them at the end

Yeah I am just thinking would that be inefficient because we essentially have to do a full rewrite to produce the file in the end.

If we want to keep a single file, it might be cool to leverage features like this https://aws.amazon.com/about-aws/whats-new/2024/11/amazon-s3-express-one-zone-append-data-object/. For normal S3, we can also treat them as multipart and then do a commit in the end. But I don't know if the current IO framework would allow that.

[westonpace]

Yeah I am just thinking would that be inefficient because we essentially have to do a full rewrite to produce the file in the end.

At high scales (where we want to distribute) the final write of the index is a small fraction of the total work. So I'm not too worried. In fact, today, we already do a two-pass write so that we don't explode RAM, so this is not more work than what we do today.

[chenghao-guo]

@chenghao-guo we just published the full current vector index spec v3: https://lancedb.github.io/lance/format/table/index/vector/

Hopefully that helps with the design.

@BubbleCal currently we only have 2 files. For enabling distributed building, does that mean it might be better to start split them to multiple files?

Thanks @jackye1995! This article https://lancedb.github.io/lance/format/table/index/vector/ is clear and highly informative. Incorporating its guidance, my current plan is as follows. Additional implementation details may need to be addressed.

IVF (distributed)

• Parallel part: IVF partition. Different partitions are assigned to different nodes/processes for processing.
• Build strategy: Each partition completes index construction locally (IVF_FLAT or IVF_PQ; for IVF-HNSW, only the HNSW sub-index is built locally within the shard).
• Merge phase: A unified IVF merger combines the auxiliary.idx files from all shards into a single file, while writing consistent metadata (IVF_METADATA_KEY, STORAGE_METADATA_KEY, DISTANCE_TYPE_KEY).

HNSW localized construction (non-distributed)

• For the IVF-HNSW type, the HNSW graph is built locally within the shard as a sub-index of the partition; there is no cross-shard graph merging and no cross-shard edges.
• Distributed parallelism occurs only in the IVF stage (centroid training, partition assignment, shard write-out); the merge phase aggregates only the IVF auxiliary files and metadata.

I’ll be on vacation for a regional festival and will continue the work upon my return. I plan to submit a draft PR before the end of October.

[HaochengLIU]

Hey, I ran across this post and find it enlightening. Could anyone guide if there is any ongoing discussion on support building scalar index distributedly? Happy to create one if there is none. I would like to make use of my remaining spare time to expand the scalar index integration with Ray/other engines.

[chenghao-guo]

Hey, I ran across this post and find it enlightening. Could anyone guide if there is any ongoing discussion on support building scalar index distributedly? Happy to create one if there is none. I would like to make use of my remaining spare time to expand the scalar index integration with Ray/other engines.

Hi @HaochengLIU This post is only for vector Index: I am working on this in this draft PR #5117 ,there are still problems and not ready yet.

For distributed scalar index, the FTS and Btree have already been supported. You can call them in ray and daft. Check the following examples in test case
Ray: https://github.com/lancedb/lance-ray/blob/main/tests/test_distributed_indexing.py.
Daft: Eventual-Inc/Daft#5236
The other scalar index types like Ngram,ZONEMAP,BITMAP,BLOOMFILTER are not ready for distributed building. Please feel free to contribute if you have time. We can use this original issue to track #4155

[artemru]

creating vectorial index is typically much more compute intensive and requires more time than other indexes, so thanks for deblocking that indexing case for large scale datasets! cannot wait to try it!

[chenghao-guo]

creating vectorial index is typically much more compute intensive and requires more time than other indexes, so thanks for deblocking that indexing case for large scale datasets! cannot wait to try it!

Many thanks for your patience. I’ve been occupied with other commitments lately; however, I’ll make my best effort to complete this PR #5117 within a month.