[VOTE] Add index segment_seq to the Lance table format

[jackye1995]

Proposal

Add optional segment_seq metadata to physical index segments, plus a per-logical-index high-water mark, to the Lance table format.

segment_seq is scoped to the index name, starts at 1 for each index name, and increases monotonically each time a new physical segment for that same index name is committed. Different index names have independent sequence domains, so vector_idx and scalar_idx can both have segment sequence 1.

PR: #7048

This thread is both the design discussion and the vote thread. If the design sounds good, a +1 here is enough; we do not need to split this into two separate discussions.

Motivation

Index segments can be added, replaced, and removed over time. Today, clients cannot reliably determine segment chronology from the latest manifest alone. This makes deterministic cache placement difficult.

A concrete example:

• Dataset UUID: 7a42d66e-6b2c-4dd7-9f6a-2c9c2b29e147
• Index name: vector_idx
• Cache nodes: node-a, node-b, node-c, node-d
• Existing segments for vector_idx:
  • s1 = 3af7a8fb-6c5a-4e8d-8c9d-54274d742f20, segment_seq = 1
  • s2 = b7a6f02b-9c1b-47fd-a3d3-943ff9b0cf61, segment_seq = 2
  • s3 = 0d3222d0-4fb6-4b97-9f58-b1d4ac1e1731, segment_seq = 3

We want to assign segment caches deterministically to nodes. There are usually not many index segments, so consistent hashing does not work well here: with only three segments and four nodes, it is common for several segments to land on the same node while other nodes get none.

Instead, we want anchored round robin: hash stable dataset/index information, such as 7a42d66e-6b2c-4dd7-9f6a-2c9c2b29e147:vector_idx, choose an anchor node, and then assign by segment_seq. If the anchor is node-b, the assignment is:

• segment_seq = 1 -> node-b
• segment_seq = 2 -> node-c
• segment_seq = 3 -> node-d
• segment_seq = 4 -> node-a

If s2 has many deletes, we may rebuild s2 plus newly unindexed fragments into s4 = c1e7ed27-739d-4799-9d4c-37dce0c9ec2a. The latest segment list should show s1, s3, and s4, with s4.segment_seq = 4 and s2 removed. Then s3 remains assigned to node-d, and only the new s4 cache goes to node-a.

Without segment_seq, a client that round-robins over the latest segment list [s1, s3, s4] could move s3 into s2's old position on node-c, causing unnecessary cache invalidation.

Format Change

Add to lance.table.IndexMetadata:

optional uint64 segment_seq = 11;

Missing means the segment was written before this feature or is uncommitted metadata that has not reached the commit layer yet.

Add logical index metadata to lance.table.IndexSection:

message LogicalIndexMetadata {
  string index_name = 1;
  optional uint64 max_segment_seq = 2;
}

message IndexSection {
  repeated IndexMetadata indices = 1;
  repeated LogicalIndexMetadata logical_indexes = 2;
}

LogicalIndexMetadata.max_segment_seq is the highest segment_seq that has ever been assigned for that index name. It is preserved even when no physical segment for that index name is currently present.

This is needed so sequence numbers are not reused after deleting the highest-numbered segment. For example, if vector_idx has segments with sequence numbers 1, 2, and 3, and segment 3 is removed, logical_indexes keeps max_segment_seq = 3; the next vector_idx segment receives 4, not 3.

Backwards and Forward Compatibility

Readers are not required to understand the new fields. Older readers may ignore IndexMetadata.segment_seq and LogicalIndexMetadata.max_segment_seq because these fields are only needed for deterministic segment chronology and future writes, not for reading indexed data.

Writers must preserve and continue segment_seq assignment, so this change adds the writer-only feature flag FLAG_INDEX_SEGMENT_SEQ and does not add a reader feature flag. This single writer flag covers both physical IndexMetadata.segment_seq and logical LogicalIndexMetadata.max_segment_seq.

Backward compatibility for existing datasets:

• Existing index segments may not have segment_seq, and existing index sections may not have logical_indexes.
• The next segment commit with a new writer backfills missing segment_seq values for existing physical segments, scoped by index name, using deterministic current manifest order.
• In the same commit, the writer backfills LogicalIndexMetadata.max_segment_seq from the assigned physical segment sequence numbers and from any existing logical high-water marks.
• If physical segments already have segment_seq but logical_indexes is missing, the writer still reconstructs max_segment_seq from the maximum physical segment_seq for each index name.
• The backfill does not claim to reconstruct historical creation order that was never stored. It only creates a deterministic baseline for future monotonic assignment.

Forward compatibility after the feature is enabled:

• Once a manifest contains physical segment_seq or logical max_segment_seq, the writer sets FLAG_INDEX_SEGMENT_SEQ in writer_feature_flags.
• Writers that do not understand this flag must reject writes instead of rewriting the manifest. This prevents an old writer from dropping segment_seq or logical_indexes and reverting the dataset to a state where sequence numbers can be reused.
• New writers read and write the full IndexSection, including logical_indexes, on commit. If a segment is removed, the logical high-water mark remains so the next segment for that index name receives a larger sequence number.
• Concurrent segment commits are rebaseable. The conflict resolver reloads the latest full IndexSection, including logical high-water marks, and recomputes name-scoped sequence numbers before the final manifest write.

Implementation Summary

segment_seq values are assigned in the commit layer. New index build APIs do not require callers to provide sequence numbers. Concurrent CreateIndex commits are rebaseable, and the conflict resolver recomputes name-scoped segment_seq values against the latest manifest before committing.

The commit path reads and writes the full IndexSection, including logical_indexes, so high-water marks survive segment removals and normal manifest rewrites.

Vote

Please vote:

• +1: approve
• 0: abstain
• -1: reject, with justification

[wjones127]

@jackye1995 Is there a design doc or prototype for discussion anywhere? I couldn't find one.

Index segments can be added, replaced, and removed over time. Today, clients cannot reliably determine segment chronology from the latest manifest alone. This makes cache maintenance harder. For example, if segments s1, s2, and s3 exist, and s2 is rebuilt together with newly unindexed fragments into s4, clients should be able to identify s4 as the new segment and s2 as removed by inspecting the latest segment metadata.

Why can't they see this now? They should be able to just compare the table versions a segment is present in and tell immediately from that, right?

Could you give a more concrete example? I think that would help me understand the use case better.

[jackye1995]

Thanks, good point. Code PR: #7048

Also sorry, I am kind of treating this as both a vote thread and a design discussion thread. We can just +1 here if the design sounds good, instead of opening two separate discussions.

A more concrete example is deterministic cache placement for index segments.

Suppose one vector index has these segment UUIDs:

• 11111111-1111-4111-8111-111111111111 (segment_seq = 1)
• 22222222-2222-4222-8222-222222222222 (segment_seq = 2)
• 33333333-3333-4333-8333-333333333333 (segment_seq = 3)

We want to assign these segment caches deterministically across nodes, e.g. node-a, node-b, node-c.

Consistent hashing is not great here because the number of index segments is often small. With only a few segments, it is easy for multiple segments to land on the same node, leaving other nodes unused.

So the approach we want is anchored round robin:

1. Compute an anchor from stable dataset/index identity, for example hash(dataset_uri, dataset_id, index_name) % num_nodes.
2. Sort segments by stable segment chronology.
3. Assign segments round-robin from that anchor.

For example, if the anchor for index vector_idx is node-b, then:

• seq 1 / UUID 11111111-1111-4111-8111-111111111111 -> node-b
• seq 2 / UUID 22222222-2222-4222-8222-222222222222 -> node-c
• seq 3 / UUID 33333333-3333-4333-8333-333333333333 -> node-a

Now suppose segment seq 2 is rebuilt due to deletes and merged with new unindexed fragments, producing:

• 11111111-1111-4111-8111-111111111111 (segment_seq = 1)
• 33333333-3333-4333-8333-333333333333 (segment_seq = 3)
• 44444444-4444-4444-8444-444444444444 (segment_seq = 4)

We want the unchanged segment with UUID 33333333-3333-4333-8333-333333333333 to stay assigned to node-a. Without a stable sequence field, if we only sort the latest segment list by manifest order or UUID, removing seq 2 can shift seq 3 into seq 2's old position, causing it to move from node-a to node-c. That invalidates cache for an unchanged segment.

With segment_seq, the assignment can be based on the segment's stable chronological slot within the index name. Removed segments leave a hole, and unchanged segments keep their placement. Only the new segment 44444444-4444-4444-8444-444444444444 needs a new cache assignment.

Comparing table versions can tell us that a UUID appeared or disappeared if we have the version history available and scan it, but it does not give a stable ordering key in the latest segment list that lets cache placement remain static across segment additions/removals. segment_seq gives us that key directly in the latest metadata.

[wjones127]

How about using the created_at date?

lance/protos/table.proto

Lines 274 to 278 in 1298bba

	// Timestamp when the index was created (UTC timestamp in milliseconds since epoch)
	//
	// This field is optional for backward compatibility. For existing indices created before
	// this field was added, this will be None/null.
	optional uint64 created_at = 8;

[LuQQiu]

The "segment_seq" is not just about "sequence" but also about "deleted segments takes seat" in assignment
For example, we have index segment 1 2 3 4, assign to 4 cache nodes 1 2 3 4

segment 1 - Node 1
segment 2 - Node 2
segment 3 - Node 3
segment 4 - Node 4

then we delete segment 2 and add segment 5

segment 1, segment 5 - Node 1
(segment 2 even though it's deleted, keep the seat) - Node 2
segment 3 - Node 3
segment 4 - Node 4

if we use "created at" which maintains "sequence" but do not maintain "deleted segment take seat"

segment 1 - Node 1
segment 3 - Node 2 (cache moved)
segment 4 - Node 3 (cache moved)
segment 5 - Node 4