Skip to content
AI Engineer Guide.

concept · concepts · intermediate · concept 55 of 57

Incremental indexing

0 of 57 complete

Why it matters

Rebuilding an index over a large corpus is slow, expensive and unnecessary when a handful of documents changed. Incremental indexing narrows the work to changed content, but it introduces the harder problem of knowing what changed. Sources differ in how they report modifications, deletions often go unreported, and a missed event leaves a stale chunk that no query will ever flag.

Mental model

Incremental indexing is editing a printed encyclopaedia by replacing only the revised pages. The metaphor breaks because a replaced page must also update every cross-reference to it, and a removed page leaves a gap that the binder does not report.

How it works

Stale versions, a tombstone and a mergeInteractive
12/16 slots occupiedlivefree

Step · 1 of 10

Twelve chunks, four free slots

Document A has eight chunks and document B has four; all twelve are live in a sixteen-slot segment. Each chunk stores a content hash beside its vector, and four slots are free.

Next: One edit re-embeds one chunk

Live chunks
12
Resident slots
12
Stale + tomb
0
Re-embedded
0
Step 1/10 · Twelve chunks, four free slots

Figure. Sixteen chunk slots in one index segment. Each chunk carries a content hash and a version; an edit writes a new chunk rather than overwriting the old one, a delete writes a tombstone, and a merge drops both before the space can be reused. Counts are synthetic; the segment is a zoom, not the whole index.

What to notice. The expired version is the cost of writing once: until a merge, the old chunk still occupies a slot, so a second edit and a delete leave only one free slot at step 5. The merge at step 6 is what returns capacity, and it moves stored vectors without calling the embedding model. Step 8 shows at-least-once delivery absorbed by the content hash, and step 9 shows a delete the change feed never delivered, found by comparing id sets. Tombstones and stale versions are different: one hides a deleted document, the other is a superseded copy.

Text version

A 16-slot index segment. Step 1: eight A chunks and four B chunks are live, 12 resident, 4 free. Step 2: A3 edited; new A3 v2 takes slot 12, old A3 is stale; 13 resident, 12 live, 1 stale. Step 3: a second edit writes A3 v3 to slot 13, leaving two stale versions; 14 resident, 12 live. Step 4: B2 deleted and replaced by a tombstone; 11 live, 2 stale, 1 tombstone, 14 resident. Step 5: A4 edited into slot 14; 11 live, 3 stale, 1 tombstone, 15 resident, 1 free. Step 6: a merge moves 11 live chunks into slots 0 to 10 and drops the stale versions and the tombstone; 11 resident, 5 free, no re-embed. Step 7: document C's four chunks take slots 11 to 14; 15 live, 1 free. Step 8: a duplicate A4 event finds the same hash and writes nothing; 15 live. Step 9: reconciliation tombstones B4, which is missing at the source; 14 live, 1 tombstone, 15 resident. Step 10: a merge drops the tombstone; 14 live, 14 resident, 2 free. Counters show live 12, 12, 12, 11, 11, 11, 15, 15, 14, 14; resident 12, 13, 14, 14, 15, 11, 15, 15, 15, 14; stale plus tombstone 0, 1, 2, 3, 4, 0, 0, 0, 1, 0; re-embedded 0, 1, 2, 2, 3, 3, 3, 3, 3, 3.

  1. Establish a change feed: source revision timestamps, a change-data-capture stream, or webhooks, and record its watermark.
  2. Hash each chunk's content and store the hash with its vector, so unchanged chunks can be skipped.
  3. On update, diff old and new chunk sets, then insert, update and delete only the difference.
  4. Handle deletions explicitly through tombstones or by comparing the full id set on a slower schedule.
  5. Write the new chunks and the watermark in one transaction so a crash cannot advance past unwritten data.
  6. Run a periodic full rebuild or a sampled reconciliation to detect chunks the incremental path missed.

Trade-offs

ChoiceGood forCostFails when
Change-data-captureLow latency and complete event streamInfrastructure and schema couplingThe source has no replication log
Polling modified timestampsSimple and portableMisses deletes and clock skewDocuments are removed or renamed
Chunk-level diffMinimal re-embeddingHashing and diff bookkeepingChunk boundaries shift on every edit
Full rebuildGuaranteed consistencyCost and durationThe corpus is large and changes hourly
Trade-off mapInteractive

Good for

Low latency and complete event stream

Cost

Infrastructure and schema coupling

Fails when

The source has no replication log

  1. The source has no replication log
  2. Documents are removed or renamed
  3. Chunk boundaries shift on every edit
  4. The corpus is large and changes hourly

Figure. Each choice with what it buys, what it costs, and the case where it loses.

What to notice. The fourth column is the decision: if the losing case describes your situation, the choice is wrong.

Text version

Four trade-offs: Change-data-capture is good for Low latency and complete event stream, costs Infrastructure and schema coupling, and fails when The source has no replication log. Polling modified timestamps is good for Simple and portable, costs Misses deletes and clock skew, and fails when Documents are removed or renamed. Chunk-level diff is good for Minimal re-embedding, costs Hashing and diff bookkeeping, and fails when Chunk boundaries shift on every edit. Full rebuild is good for Guaranteed consistency, costs Cost and duration, and fails when The corpus is large and changes hourly

Failure modes

  • Missed deletion. A removed document keeps answering queries indefinitely. Debug: compare the index id set with the source listing on a schedule and report ids that no longer exist.
  • Watermark advanced before write. A crash after the watermark update skips a batch permanently. Debug: verify that the watermark and the chunk writes commit in the same transaction.
  • Chunk boundary instability. A one-line edit shifts every subsequent boundary and re-embeds the whole document. Debug: diff chunk ids between two versions of a lightly edited document.

In production

Monitor lag between source modification time and index time, and the delete count per run. Alert on a watermark that has not moved, and reconcile id sets weekly.

Common misconceptions

People think: Incremental indexing is just an upsert.

Actually: Upserts handle inserts and updates; deletions and missed events are the parts that break.

People think: A full rebuild is never needed once incremental works.

Actually: It is the only check that catches events the incremental path never received.

Interview angle

Name the change feed, the watermark transaction and delete handling, then describe the reconciliation that catches misses. Mention chunk-level hashing. Upserting changed rows, with no discussion of deletions or drift, is the answer that leaves stale documents answering queries.

Sources