Lance Vector Index: Multi-Segment Final State

[Xuanwo]

1. Problem

Lance's format already defines an index segment model: an index consists of multiple segments, each being a self-contained physical index that describes its data coverage through a fragment_bitmap.

However, the current distributed vector index build does not take advantage of this model. The build works in two phases:

1. Partition fragments across shards, each building a partial index.
2. Finalize by merging all partial indexes into a single final index.

The shard phase scales horizontally, but finalize must converge to a single point and rewrite all shard outputs in full — making it the scalability bottleneck. The root cause: the format already supports segmentation, but the build, transaction, and query semantics are not organized around it.

2. Goals

1. Eliminate the many-to-one finalize bottleneck in distributed build.
2. Let distributed build produce a set of index segments as its final output.
3. Support unified queries across multiple segments.
4. Let transactions precisely express segment additions, removals, and replacements.
5. Reuse the existing format, manifest, cleanup, and GC mechanisms.

3. Design

3.1 Logical Index vs. Physical Segment

Users interact with vector indexes by index name (the logical index). A logical index is composed of a set of physical index segments that:

• Share the same logical index name and target column.
• Are independently stored and queried.
• Satisfy compatibility requirements.

3.2 Distributed Build: Before and After

Current flow:

1. Each shard produces a partial index.
2. Finalize merges all partial indexes into a single index.
3. Commit the index.

Proposed flow:

1. Each shard independently builds a local index.
2. Finalize validates compatibility of shard outputs, determines segment grouping, and produces the final segments.
3. These segments are committed directly as physical members of the logical index.

Finalize shifts from "full merge" to "validate, organize, and commit."

4. Transaction Semantics

4.1 Current Semantics and Limitations

CreateIndex's apply logic works as: delete all indexes with the same name → delete indexes specified by UUID in removed_indices → append new_indices.

This assumes only one index survives per name and does not support long-lived multi-segment coexistence.

4.2 Proposed Semantics

Transactions must evolve from "replace all by name" to "precisely maintain the segment set by UUID":

1. Add multiple new segments.
2. Remove specific segments by UUID.
3. Preserve same-name segments that are not being replaced.

4.3 Concurrency

With long-lived multi-segment coexistence, concurrency control must be defined around segment set mutations. The system must correctly handle:

• Two transactions concurrently adding segments to the same logical index.
• One transaction adding segments while another replaces a subset.
• Distributed build committing concurrently with other index maintenance operations.

5. Query Semantics

5.1 Query Flow

1. Resolve all segments belonging to the logical index by name.
2. Group segments by compatibility.
3. Execute fan-out queries per group.
4. Merge results.

5.2 Phase 1 Trade-offs

Phase 1 accepts the following costs:

• Increased query fan-out.
• Independent partition routing per compatibility group.
• Routing is shared only within compatible segments.

The goal is to establish correct multi-segment query semantics and provide a stable foundation for future optimization.

6. Integration with Existing Systems

6.1 Format / Manifest

Each segment remains a regular IndexMetadata entry. A logical index maps to multiple same-name entries in the manifest. No format-level changes are required.

6.2 Cleanup / GC

Since segments are standard IndexMetadata entries, the existing GC mechanism applies directly: manifest references determine liveness, and dereferenced index_uuids are cleaned up through the existing path.

6.3 Compaction / Remap

Compaction must remain compatible with multi-segment coexistence, continuing to maintain each segment's fragment_bitmap and its relationship to the underlying fragments.

7. Phase 1 Scope

7.1 Index Types

Covered: IVF_FLAT, IVF_PQ, IVF_SQ.

Deferred:

• IVF_HNSW_* — stronger intra-partition semantics make segmented query and maintenance more involved.
• IVF_RQ — on a separate evolution path.

7.2 Minimum Deliverables

1. Transactions support same-name segment coexistence with UUID-level membership management.
2. Distributed build produces final segments directly.
3. Query executes against segment groups with result merging.
4. Cleanup, GC, and remap work correctly under multi-segment coexistence.
5. Compatibility serves as the foundation for segment grouping and routing reuse.

8. Benefits

1. Eliminates the finalize bottleneck — removes the structural many-to-one convergence and avoids full rewrites of shard outputs.
2. Aligns implementation with format — the distributed build's final state lands directly on Lance's existing segment model.
3. Opens optimization space — shared routing, refined compatibility grouping, query fan-out optimization, and independent maintenance scheduling.

[hpvd]

Like this!

Just a thought: is this new architecture really "only" about vector indexes or is this a general topic for all kind of indexes that could grew pretty huge on big data sets?
One recent example is FTS index with positions to enable phrase searches
#6104

[Xuanwo]

Thank you @hpvd for raising the issue at #6104. It's an interesting idea to design a general layout for that. However, vector and FTS are quite different in both their construction and query patterns. Therefore, I think it is better not to include FTS in this design for now.

[hpvd]

great to see lance is going a unified route for all kinds of indexes now
#6309

[westonpace]

max_segment_bytes — target upper bound for a single segment, defined in bytes rather than rows
max_segments — maximum number of searchable segments under a single logical index

Does the user specify one or both? How can max_segments be guaranteed? Wouldn't I possibly have to exceed max_segment_bytes to provide the max_segments request?

Is max_segment_bytes a max or a target? Are we guaranteeing we don't go beyond this point or just saying this is roughly where we will create a new index? I think it'll probably be easiest as a target because it can be hard to guess up front how much data we will add to an index. If we happen to go over I don't want to have to back off and retry as a new index. We do the "target" strategy with fragments too because it's simpler to just write to it until we've passed the limit rather than write to it until we're about to pass the limit.

The following remain for later work:
...
5. A new logical index container format

What is this?

Two lifecycle states are defined initially:

active
sealed

I don't really have a problem with this if we want to go this route but it seems redundant. The manifest has a list of UUIDs. Wouldn't the most recent UUID in the manifest be the "active" UUID? Then we just look at it and see if it has space, if it does, we add to it, if it doesn't, we make a new index?

[Xuanwo]

Does the user specify one or both? How can max_segments be guaranteed? Wouldn't I possibly have to exceed max_segment_bytes to provide the max_segments request?

Ah, yes. We can just expose max_segment_bytes.

What is this?

another design that we have a shared metadata object that stores segment-level shared state. Let me just remove it from design doc now. It just adds the confusion.

Wouldn't the most recent UUID in the manifest be the "active" UUID?

In the current design, for a given index, there can be either one or zero "active" index segments. For distributed index building, I expect there will be no "active" index segment present. Therefore, if we use the most recent UUID in the manifest as the "active" UUID, it could be confusing and difficult to distinguish. We may need a place to store has_active or active_segment.

I am also considering concurrent append and distributed index building. In this scenario, distributed index building will generate new "sealed" segments, but the "active" segment should not be changed. I think it is possible to always place the active segment as the latest one, but that approach seems a bit fragile to me.

Another consideration is that this adds a requirement for the order of index segments in the manifest. However, this is not a major issue.

[wjones127]

Instead of treating "base index" and "delta index" as two separate long-lived objects, the new design unifies them under a single concept: the index segment.

If you read https://lance.org/format/table/index/#basic-concepts, you'll find we already define the idea of index segments. So this isn't new.

Could you describe more why we need a sealed and an active tag on segments? We don't have those for fragments?

Does a sealed segment ever become active? Say I have a segment that covers fragments 0..100 and is sealed. Then fragments 50..100 are updated via data replacements, and invalidate that part of the index segment. And then fragments 25..50 are deleted. Now there's only fragments 0..25 active in this index, but it's no longer meeting the max_segment_bytes. What do we do with the segment then?

[wjones127]

5. A multi-segment end state in place of the monolithic final merge

I think if you are going to build multiple segments, I'd actually recommend just running those as independent jobs. There's no need to commit them together. You can if you want, of course.

A while ago, when we were thinking about large scale indexes, we were thinking we might compact / merge indexes together with fragments.

For example, you could imagine we receive batches of data continuously. For each fragment, we have an index. When compact fragments and indices together as we reach various levels: every time we find 8x 10k row segments, we make a 80k row segments. And keep compacting from there. And then eventually we might get segments to a size where we don't compact any more. That makes the sealed. But, of course, if there are enough deletions or invalidations, we might need to compact or rewrite.

[wjones127]

All this is to say, I'm skeptical we need to make any actual format changes. I think what we need to do is update some of the implementation to make it possible to commit multiple segments concurrently. And then we need to design better indexing schedulers. But I think the format itself technically has everything we need.

[Xuanwo]

Thank you @wjones127. I've thought about this over the weekend, and you are right.

After digging further into Lance's transaction model, I no longer think active / sealed is the right direction here.

For distributed index build, what we actually need is much simpler:

• allow multiple compatible index segments with the same logical index name to coexist
• query them together
• avoid the final many-to-one merge

Since segments are immutable anyway, an active segment would not actually be writable. It would only mean "the next segment we may choose to rewrite", which is scheduler policy, not a core index concept.

So I think we should drop active / sealed entirely from this design and keep the proposal focused on multi-segment coexistence, query fan-out, and transaction semantics.

I will update the design doc.

[Xuanwo]

Thank you @hpvd @westonpace @wjones127 for the review! I have rewrite the design doc, PTAL.

Additionally, this new design doc eliminates the need for changes to the table format. As a result, a formal vote is no longer required.