Designing a Repo-Scale Code Index That Updates Incrementally

The expensive mistake in a code index is treating it as one artefact that is rebuilt. It is four stores with four different lifetimes, and separating them is what makes an update cost proportional to the change rather than to the repository.

Four stores, not one

A working repository index has these pieces, and conflating any two of them is the reason rebuilds get expensive.

• A file table: path → content hash → commit last seen. Small, one row per file, and the thing every freshness check reads.
• A chunk table: chunk id → owning file, byte range, symbol name, language, text. This is where retrieval results become something you can display, and it is the only store that knows where a hit lives.
• A vector index: chunk id → embedding. The expensive one to hold in memory and the awkward one to mutate.
• A symbol table: qualified name → defining chunk, plus the references extracted from the parse. Exact, not approximate, and it is what makes “go to definition” queries answerable without a model at all.

The symbol table is the piece most embedding-first designs omit, and it does more work than its size suggests. A very large fraction of real developer queries are name lookups wearing a natural-language costume. “Where is the retry logic” is a semantic query; “where is RetryPolicy defined” is not, and routing it through a vector index gives a worse answer more slowly. Combining a lexical and a dense retriever is the general treatment of that split.

Content-addressing the chunk

Here is the single decision that determines whether incremental updates are possible: the primary key of an embedding must be a hash of the exact bytes that were embedded, not a path and not a line range.

chunk_id = sha256(
    model_id  + "\x00" +      # changing model invalidates everything
    chunker_version + "\x00" +  # changing boundaries invalidates everything
    language + "\x00" +
    chunk_text
).hexdigest()

With that key, re-embedding becomes a cache lookup. A file moves from src/util.py to src/common/util.py and every chunk id is unchanged, so the update is a row rewrite in the file table and the chunk table and zero embedding calls. A commit that reformats 4,000 files with a code formatter changes almost every chunk id, and it should — the bytes really are different. But a commit that adds one function to a 900-line file changes the id of the chunks that moved and no others, if your chunker splits on syntactic boundaries rather than fixed byte offsets.

That last clause is the catch, and it is why chunk boundaries and index economics are the same subject. A fixed 1,500-byte window over a file shifts every downstream boundary when you insert a line at the top, so a one-line change invalidates the entire file. Splitting at function definitions confines the damage to the function that changed. Including the model id and chunker version in the hash means a model upgrade is a full re-embed by construction, which is correct and which you want to be able to see coming.

What a commit actually invalidates

Git already computed the answer. git diff-tree -r --name-status between two commits gives added, modified, deleted and renamed paths, with rename detection, and that set is normally a few dozen files out of hundreds of thousands. Everything the index does should key off that set.

There is one class of change git does not describe and it catches people out: a change to something a chunk depends on without changing the chunk. If your chunk text includes the file’s import block as context — a reasonable choice, because a bare function body often does not say which library it is calling — then editing an import invalidates every chunk in that file. That is correct behaviour and it is fine, as long as you did not assume otherwise when sizing the job. If your chunks include a summary of callers or callees pulled from the dependency graph, the blast radius of a change grows to the graph neighbourhood, and at that point the cheap-update property is gone. It is a real trade-off and it should be made deliberately.

Full versus incremental, worked

The comparison is worth doing with your own numbers because the answer is less obvious than it sounds. Take a repository of 180,000 source files and an active team producing 900 changed files a day — half a percent, which is high for a mature codebase.

inputs (assumptions — substitute your own)
  files in repo                 180,000
  changed files per day             900   (0.5%)
  mean chunks per file                3
  embedding calls, full re-index  540,000 chunks
  embedding calls, one day incr.    2,700 chunks

ratio  540,000 / 2,700 = 200x fewer embedding calls per day

but: a full re-index also rebuilds the ANN graph in one pass,
     while incremental performs 2,700 inserts + 2,700 deletes
     into a live graph, every day, forever.

The embedding arithmetic overwhelmingly favours incremental, and the absolute figures are smaller than most people expect. The graph arithmetic does not. Deletion in a graph-based ANN index is usually implemented as a tombstone rather than a true removal, because unlinking a node can disconnect the graph. Tombstones accumulate: after a year at 900 deletes a day you are carrying roughly 330,000 dead entries against 540,000 live ones, and both recall and latency degrade because search traverses them before discarding them.

So the real architecture is neither: incremental updates continuously, plus a scheduled full rebuild that compacts the tombstones out. Pick the rebuild cadence from the tombstone ratio, not from the calendar — rebuild when dead entries pass some fraction of live ones, say 20%, which the file table can tell you at any moment.

Deletions and the branch problem

Deleted files are where indexes rot, because deletion is the one event with no positive signal. An added file arrives with content to embed; a deleted file arrives as an absence, and any pipeline built around “walk the working tree and embed what you find” will never notice it. That produces the specific failure of search returning code that no longer exists, and it is the most common bug in home-grown code indexes.

Branches make it worse. If the indexer runs on whatever is checked out, a developer switching from a feature branch to main silently mixes two versions of the same file into one index, and neither is identifiable afterwards. Two defensible designs exist. Index exactly one ref — usually the default branch — and accept that uncommitted and branch-local work is invisible; this is simple and predictable. Or store the ref alongside every chunk and filter at query time, which is honest but multiplies storage by the number of active branches. What does not work is indexing whatever happens to be on disk. Whichever you choose, record the commit sha you indexed in the file table: it is the only thing that lets a later process prove the index and the repository agree.