Skip to content

Vector index: renumber vector ids during the data file rewrite so the id space is dense by construction #5870

Description

@lvca

Follow-up to #5588, which laid the LSM_VECTOR location index out in primitive arrays indexed by vector id.

The residual weakness

The arrays are chunked (CHUNK_SIZE = 128) and a chunk is released as soon as its last live id is tombstoned. That is what keeps residency proportional to the LIVE vectors rather than to the ids handed out, which is the property #5516 exists for: a re-embedding workload hands out 9.3M ids for a 4K live set, and a flat id-indexed array would retain ~190MB where the structure it replaced retained ~360KB.

Chunking degrades well because ids are assigned monotonically and an update tombstones the id it supersedes, so the chunks behind the live region drain wholesale. What it does not solve is the partially drained band trailing the live region: a chunk still holding a single live id retains the whole CHUNK_RETAINED_BYTES (2680 bytes, so ~2.7 KB per live id in the worst case). 128 was chosen over 1024 precisely to bound that - it costs 4% on the dense case and buys 8x on the cliff - but it bounds the cliff rather than removing it.

The structural fix

LSMVectorIndex.rewriteDataFileWithLiveEntries already walks the entire live set, writes every entry to a fresh file and re-assigns every absolute file offset. It is therefore the one moment in the index's life where reissuing the ids costs nothing extra: renumbering them 0..N-1 there would make the id space dense by construction after every compaction, and the partially drained band would disappear rather than being bounded.

VectorLocationIndex's javadoc currently states that ids are preserved across a compaction rather than renumbered, and several places depend on that. This issue is to change it.

Why it is not part of #5588

Ids are not private to the location index. Three things have to move in lockstep with a renumbering, and getting any of them wrong is a silent wrong-answer bug rather than a crash:

  1. ordinalToVectorId - the graph's ordinal map, published alongside the graph by the same rebuild. The pairing of a map with its graph is what findNeighborsFromVector brute-force fallback reads ordinalToVectorId without snapshot #4581 exists to keep intact.
  2. The persisted tombstone set - on-disk entries carry vector ids, and DeletedIds is keyed by them. A renumbering that does not reissue or discard the tombstones lets an old tombstone id collide with a new live one, and the LSM merge-on-read resolves that to "deleted": the new vector is buried by a tombstone meant for a different one.
  3. nextId - the high-water mark, which loadVectorsFromPages derives from max(highest live id + 1, getNextId()) and which is the only thing preventing id reuse on an index where every vector was deleted.

Acceptance

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions