Incremental external IVF-PQ index build (delta-segment / LSM append)

[sezruby]

Goal

Support adding a new parquet file to an already-built external IVF-PQ index (the
"external-over-parquet" / Path C build in DistributedExternalIndexBuild) without
re-sampling, re-training, or rewriting the whole index.

Today any file-set change forces a full rebuild: the build cache keys on a SHA-256 of
(sorted filePaths, vectorColumn, params) (ExternalIndexLifecycle.scala:150-172), so adding
one file → new hash → rebuild under a fresh dir. There is no incremental/append/optimize path
in the external module today (greps confirm; only a test-only pretrained param at
build.rs:353-379 proves model-reuse works).

TL;DR — recommended approach

Reuse the trained model, encode only the new file, append it as a new immutable index
segment (LSM-style). Do not re-sample on an add — re-sampling → new centroids → every
existing file's vector→partition assignments change → re-encode the whole corpus (= a full
rebuild, not incremental). The centroids are exactly the thing you hold fixed to keep adds cheap.

LSM = Log-Structured Merge-tree (the RocksDB/Cassandra pattern): appends go to a new small
immutable segment; reads union across segments; a periodic compaction folds segments back into
one. It maps almost exactly onto this index:

LSM concept	our external index
base segment	the current unified index.idx
new immutable segment per write	a delta index.idx-N per appended file, encoded vs the existing centroids
read = union across segments	query = union across base + delta segments
compaction merges segments	the existing full merge_shards rewrite, run periodically
— (no LSM analog)	retrain — re-sample new centroids when they go stale

The one place the analogy breaks: a classic LSM never retrains (its sorted-key structure is
inherent). IVF's structure (centroids) is learned, so on top of append/compact you also need
an occasional full re-sample + retrain when the distribution drifts.

Per-phase behavior on an incremental add

phase	initial build	incremental add
train (sample → IVF centroids + PQ codebook)	full	skip — reload persisted model
encode (buildShard: assign + PQ-encode)	all files	only the new file (one buildShard)
merge	unify all shards → one index.idx	append as a delta segment

buildShard(payload, files, vc, offset, uri, params) is already a pure function of (that file,
the payload) — encoding a new file needs only the saved payload + the new file + a fresh global
offset, nothing about existing files.

Code seams (grounded — lance fork branch indexed-merge-scalar-index)

Repos: Scala orchestration lance-spark-knn_2.12/src/main/scala/org/lance/spark/knn/internal/;
Rust external module lance/rust/lance/src/index/vector/external/; JNI
lance/java/lance-jni/src/external_index.rs; Java facade
lance/java/src/main/java/org/lance/index/external/ExternalIvfPqIndex.java.

seam	size	notes
(a) reload model → BroadcastPayload	small	Model is already persisted in index.idx and reloaded on open (open.rs:86-87, decode_pb_index); SQ8 rerank bounds are in the manifest (manifest.rs:75-77). Inverse encoders PbIvf/PbPq::try_from already exist (distributed.rs:181-182). Only missing bit: a fn that assembles a payload from an opened index instead of from training.
(b) write the delta	small (reuse)	A delta segment = mergeShards run over the one new shard with the reloaded payload → a standalone index.idx-N. The writer write_ivf_pq_file_external (distributed.rs:582) already takes the model as input and does not retrain. No new append-writer needed.
(c) query-side multi-segment union	medium — the one real new piece	Today open_index opens exactly one index.idx (open.rs:71-72) and search probes that one model (search.rs:118-165). Because every delta reuses the same centroids, all segments share an identical partition structure → find_partitions once (shared model), then for each probed part_id read that partition's posting list from each segment and merge candidates. Changes: OpenedExternalIndex holds Vec<reader>; search/search_batch loop the partition read; the refine path (search.rs:242) resolves file_id against the concatenated file list. Bounded — not research.
(d) manifest segment list + offsets	small	Offsets chain for free: global row base = prefix-sum of files[*].num_rows recomputed at open (manifest.rs:179-189, search.rs:242); rid = `(file_id << 32)
compaction	free	The existing full O(total) merge_shards (distributed.rs:563-593) is the compactor — run periodically to fold deltas back into one index.idx.

Bottom line: the only substantial new code is (c) query-side multi-segment read. (a)/(b)/(d)
are small or pure reuse, and compaction comes free from the existing merge.

When to full-rebuild (re-sample + retrain) instead of append

Reusing centroids assumes appended data is in-distribution. Escalate to a full rebuild on:

• Growth ratio — nlist is sized ~√N; once the corpus grows ~2–4× beyond what the model was
  trained for, partitions fatten and recall/latency degrade.
• Distribution drift — new languages/domains/embedding model → the old centroids stop
  balancing the space (some partitions huge, others empty). Classic IVF staleness.
• Recall drop — track recall on a held-out query set; rebuild when it crosses a threshold
  (the honest signal that subsumes the two above).
• SQ8 rerank-bounds clipping — the rerank store reuses stored bounds_min/max
  (manifest.rs:75-77); a delta with values outside those bounds clips. Detect by comparing the
  delta's min/max to stored bounds; widening bounds forces a rerank re-encode, so treat an
  out-of-bounds delta as a retrain signal too.

Alignment with native lance

Same shape as native lance's incremental path: create_index_uncommitted(fragment_ids=...) /
build_distributed_vector_index(fragment_filter, precomputed_centroids) encode only specified
fragments against fixed centroids, and optimize_indices is the compaction. lance-spark lance-format#605
orchestrates the native version. So this fork design stays convergent with lance-format#605 — if lance-format#605 lands,
the orchestration is the same append / compact / retrain loop.

---

Recorded for later. Design conversation grounded via a read-only trace of the read/open/merge
path; all file:line refs are on the lance fork branch indexed-merge-scalar-index.