Impact traversal is 2–3x slower since #3125: incoming edges are fetched with a 12-kind IN list #3248

Edited 2026-11-05: corrected the cause. Most of the slowdown comes from the query's LIMIT, not only its kind list: see Cause and the split under Measurements. The first suggested change (an unfiltered read) is replaced by #3249.

What happens

Since #3125 (cc863616, merged 2026-10-31, not yet released), getImpactRadius takes 2–3x as long and returns the same subgraph. Every caller of getImpactRadius pays for it. In the viewer, /api/node/<id> for the engine's two busiest symbols went from 87–93 ms to 126–145 ms.

The cause is the incoming-edge read in getImpactRecursive (src/graph/traversal.ts#L697, SQL built in src/db/queries.ts#L2777), which the walk runs once per visited node:

const fetched = this.queries.getIncomingEdges(nodeId, IMPACT_INCOMING_KINDS, remaining + 1);
// SELECT * FROM edges WHERE target = ? AND kind IN (?, ?, … 12 kinds) ORDER BY kind, source, line, col LIMIT ?

Two parts of it slow each read down, and the LIMIT costs more than the kind list:

• The LIMIT. Under this ORDER BY (which needs a temp B-tree in both plans), the same query with a LIMIT was markedly slower than without one, even when the limit was never reached.
• The kind list. SQLite searches idx_edges_target_kind once per kind (SEARCH … (target=? AND kind=?)) instead of once (SEARCH … (target=?)). That costs most on the many small nodes a walk visits.

Before #3125 the read was one unlimited search on target, with contains dropped in JS (b6ea6179 src/graph/traversal.ts#L676).

Measurements

codegraph's own source indexed by each build (1,571 files). Each figure is the best of 5 calls, and the range covers 3 rounds with the builds interleaved. Linux (WSL2, 12 cores), Node 22.23.2.

getImpactRadius(id), default depth. Every build returned the same subgraph: init 805 nodes / 2,556 edges, getNode 890 nodes / 4,381 edges, truncated false.

GET /api/node/<id> (viewer API):

The commit was found with git bisect over f4c4dae9..f72c9d2e. Good steps measured 85–92 ms and bad steps 124–129 ms on /api/node for init.

Which part costs what: getImpactRadius for init, best of 5, 5 rounds interleaved on the same index. The machine was loaded (load average 8–15), so compare the rows with each other, not with the tables above. Every variant returned the same subgraph.

Reproduce

git checkout b6ea6179   # then repeat from cc863616
npm ci && npm run build
node dist/bin/codegraph.js init . && node dist/bin/codegraph.js index .
node impact.cjs . .

impact.cjs:

const CodeGraph = require(process.argv[2] + '/dist/index.js').default;
(async () => {
  const cg = await CodeGraph.open(process.argv[3]);
  for (const name of ['init', 'getNode']) {
    const n = cg.searchNodes(name, { limit: 50 }).map((r) => r.node ?? r)
      .find((x) => x.name === name && x.kind === 'method' && x.filePath.endsWith('src/index.ts'));
    cg.getImpactRadius(n.id); // warm
    let best = Infinity, sg;
    for (let i = 0; i < 5; i++) {
      const t = performance.now();
      sg = cg.getImpactRadius(n.id);
      best = Math.min(best, performance.now() - t);
    }
    console.log(name, `nodes=${sg.nodes.size} edges=${sg.edges.length} best=${best.toFixed(0)}ms`);
  }
})();

Fix

#3249 reads WHERE target = ? AND kind != 'contains' with no LIMIT, through a cached statement, and applies the edge budget by slicing as before. The output equals main's: the same nodes, edges, order and truncated on 20,000 random graphs and 500 traversals of codegraph's own index.

The trade-off: one node's incoming rows are read in full before the slice, as before #3125. The node and edge budgets still bound what the walk keeps and how far it goes. A bounded read would need a different way to cap it than LIMIT under this ORDER BY.

Why the test suite didn't catch it

ui-server-api.test.ts › "the engine's own busiest symbol" times exactly this request against 100 ms. But it targets LRUCache.get, and the test asserts fanIn > 300. On main that fan-in is 33 (13 distinct callers), so the test fails there before it reaches the timing check. It also only runs in a checkout that has indexed itself.

If the test targets CodeGraph.init instead (614 distinct callers, capped at 300), with every original assertion kept, it fails on f72c9d2e (expected 176.1 to be less than 100, then 144.7). With the fix it passes on a quiet machine, but at 83–95 ms the margin is thin: under load it reached 101.9 ms once. So #3249 doesn't change that test; it adds a deterministic one in graph.test.ts instead. #2646 relaxes the same assertion to fanIn > 0. That makes the test pass, but it no longer exercises the cap or the timing on a real hub. Details are in a comment there.