Incremental re-index is `O(changed_files × total_nodes)` — `gbuf.delete_by_file` full-scans the whole node buffer per file; a single day's changes make it slower than a full rebuild

[sreehari83]

Version

codebase-memory-mcp 0.9.0

Platform

Linux (x64)

Install channel

GitHub release archive / install.sh / install.ps1

Binary variant

standard

What happened, and what did you expect?

I run one incremental re-index per day on a large graph (~5M nodes) to pick up that day's commits. On a normal day, ~844 files changed. That single daily incremental takes far longer than a cold full rebuild, because the reconcile phase deletes stale nodes with a linear scan of the entire in-memory node buffer for every changed file — making the delete phase O(changed_files × total_nodes).

This isn't an extreme/high-churn edge case: it's a once-a-day update with a routine number of changed files, and incremental is already non-viable.

Real-world usage

• Cadence: 1 incremental index per day (scheduled).
• Files changed that day: 844 (typical for this branch).
• Result: the daily incremental run is slower than just deleting the project and doing a full re-index (~13 min).

Evidence (from server logs, CBM_LOG_LEVEL=info)

level=info msg=pipeline.route path=incremental stored_hashes=166998
level=info msg=incremental.classify changed=844 unchanged=166515 deleted=4 mode_skipped=19
level=info msg=incremental.reparse files=844
level=info msg=incremental.load_db rc=0 nodes=4966505 edges=17066669 elapsed_ms=67884
level=info msg=incremental.edge_snapshot captured=66821 elapsed_ms=2643
level=info msg=gbuf.delete_by_file file=a/b/c/topo/topo.c   scanned=4966505 deleted=56
level=info msg=gbuf.delete_by_file file=a/b/b/if/d.c scanned=4966505 deleted=212
level=info msg=gbuf.delete_by_file file=a/b/c/if/if.c        scanned=4966505 deleted=31
... (one full 4,966,505-node scan per changed file, ×844)

The key line is scanned=4966505 on every gbuf.delete_by_file: each changed file scans all ~5M nodes to delete a handful.

Cost analysis

• Changed files (one day): 844
• Total nodes: 4,966,505
• Delete-phase comparisons: 844 × 4,966,505 ≈ 4.2 billion
• Plus fixed incremental.load_db = ~68s to load 4.97M nodes / 17M edges.

The original full index of the same repo completed in ~13 min, so incremental is strictly worse even for a single day's changes.

Impact

Incremental indexing is unusable for large monorepos at any realistic daily cadence. A normal day (844/166,998 files ≈ 0.5% changed) already exceeds a full rebuild, forcing users to delete_project + full-reindex daily as a workaround.

Expected behavior

Deleting a changed file's nodes should scale with that file's node count (or an O(log N) lookup), not O(total_nodes). Reconcile should scale with the size of the day's change set, not the size of the graph.

Suggested fix

Maintain a file → node-ids index (a hash map keyed by file path, or bucket/sort the node buffer by file id) so delete_by_file locates a file's nodes directly instead of scanning the whole gbuf. Even one-pass bucketing at load_db time (build map<file_id, [node offsets]> once, then O(1) per-file delete) turns the delete phase from O(changed × N) into O(N + changed).

Environment

• Version: codebase-memory-mcp 0.9.0
• OS/arch: Linux x86_64
• Repo: ~167K files, ~5M nodes / ~17M edges
• Mode: full (filters on; mode_skipped=19)
• Change detection: hash-based (stored_hashes=166998), non-git-root working copy

Repro

1. Index a large repo (multi-million-node graph).
2. Let ~a day's worth of commits change several hundred files.
3. Re-run index_repository with the same name (daily incremental).
4. Observe gbuf.delete_by_file ... scanned=<total_nodes> repeated once per changed file; wall-clock exceeds the original full build.

Reproduction

Environment

• Version: <fill in codebase-memory-mcp --version>
• OS/arch: Linux x86_64
• Repo: ~167K files, ~5M nodes / ~17M edges
• Mode: fast/moderate (filters on; mode_skipped=19)
• Change detection: hash-based (stored_hashes=166998), non-git-root working copy

Repro

1. Index a large repo (multi-million-node graph).
2. Let ~a day's worth of commits change several hundred files.
3. Re-run index_repository with the same name (daily incremental).
4. Observe gbuf.delete_by_file ... scanned=<total_nodes> repeated once per changed file; wall-clock exceeds the original full build.

Logs

Diagnostics trajectory (memory / performance / leak issues)

Project scale (if relevant)

No response

Confirmations

• I searched existing issues and this is not a duplicate.
• My reproduction uses shareable code (a dummy snippet or a public OSS repository), not proprietary code.

[sreehari83]

its is not windows one .. its is on linux

[DeusData]

Thanks for the correction. I removed the incorrect Windows label and classified this as a high-priority stability/performance bug for 0.9.1-rc, linked under #593. The per-file scan logs and roughly 4.2 billion comparisons make the scaling failure concrete.