Incremental Indexing at Repository Scale

A code assistant is only as useful as the picture it holds of your repository, and that picture goes stale the moment you save a file. The naive answer is to re-index on a timer. We tried it, and on a million-line monorepo it cost four minutes of CPU every ten minutes for a change that touched one function.

Files are the wrong unit

Re-indexing a file is cheap. Re-resolving everything that referenced a symbol in that file is not. The index therefore stores a reverse edge for every reference, so a save invalidates a set of symbols rather than a set of files, and the set is usually small: a rename of a private helper touches its own module and nothing else.

The exception that pays for the design

The exception is the widely-used interface, where one edit invalidates thousands of symbols. Those are rare enough to handle by falling back to a full pass on the affected package, and common enough that a design without a fallback would fail on the first day of real use.

The result: a median save costs eleven milliseconds of index work, a package-wide interface change costs about two seconds, and the four-minute pass runs once, when you first open the repository.