CONCEPT Cited by 1 source
Incremental vector index¶
Definition¶
An incremental vector index is an ANN index that absorbs point mutations — inserts, updates, deletes — continuously, without periodic full rebuilds, and without losing recall or query latency over time.
Why it's a distinct category¶
Most mainstream ANN indices were published as read-heavy structures with a "build once, query many" operating model. Incremental extensions are bolted on later, typically with degraded quality or cost:
- HNSW extends via insert but requires periodic full rebuilds to maintain recall as the graph evolves.
- DiskANN (via FreshDiskANN and follow-ups) supports incremental updates but PlanetScale names them "not particularly efficient".
- SPANN as published reorganises offline.
The 2024-10-22 PlanetScale announcement crisply states the operational reason this matters: "HNSW indexes cannot be updated incrementally, so they require periodically re-building the index with the underlying vector data. This is just not a good fit for a relational database." (Source: sources/2024-10-22-planetscale-planetscale-vectors-public-beta.)
Canonical production instance: SPFresh¶
SPFresh (Microsoft Research, SOSP 2023) is the closest academic realisation of the property — it extends SPANN with concurrent background maintenance ops (split, merge, rebalance, centroid reassignment) that run continuously to absorb mutations without rebuilds or recall loss.
PlanetScale's 2024-10-22 vector-beta announcement builds on SPFresh: continuous updates flow through the SPFresh background-maintenance substrate, integrated into InnoDB with transactional semantics (see concepts/transactional-vector-index).
Why this matters for databases¶
OLTP tables have continuous per-row write cadence. Any index whose maintenance model is "periodic full rebuild" falls out of sync with the table between rebuilds, increasing staleness that's hard to reason about at the application layer. Incrementally-updatable indexes — B+tree, LSM, SPFresh — keep index and table in lockstep.
Seen in¶
- sources/2024-10-22-planetscale-planetscale-vectors-public-beta — canonical wiki statement of incremental-updatability as a requirement for a database-hosted vector index. Names the shortcomings of HNSW (rebuild-required) and DiskANN (incremental-update inefficient) on this axis.