What is incremental HNSW indexing, and why does it matter for upsert-heavy workloads?

Incremental HNSW indexing means adding new points to an existing graph without rebuilding the entire graph from scratch. In Qdrant this is achieved structurally through the segment model: new points are appended to a small, mutable segment, and when that segment reaches the indexing threshold the optimizer builds a graph over it. Existing segments are left alone, so their graphs are never rebuilt just because new points arrived. Over time the optimizer merges several small segments into a larger one, which does involve building a new graph over the merged data, but that is a consolidation step, not a per-write rebuild. The effect is that an upsert only costs a WAL append and an in-memory insert; the expensive graph construction is amortized over batches and done in the background.

The reason this matters for upsert-heavy workloads is that the naive alternative - inserting each new point directly into a single global HNSW graph - scales badly. Every insert would run a graph search and rewire edges, and as the graph grows the insert cost grows with it, so a sustained write rate would eventually be limited by the graph insertion throughput rather than by disk or CPU. With the segment model, the write path stays cheap regardless of total collection size, and the indexing work is decoupled from the write acknowledgement. That is what allows Qdrant to sustain high write rates on large collections. There is a second dimension to incremental indexing that is less visible: when a point is updated (same ID, new vector), the old version is tombstoned in its segment and the new version is written to the current mutable segment. This means a single logical point can temporarily exist in two segments, and the coordinator has to resolve which version is current during a query. The optimizer's vacuum step is what eventually removes the tombstoned version and reclaims the space.