h-dv/code-index

Fork 0

perf: rebuild_symbol_edges is superlinear — correlated enclosing-symbol subquery per resolved ref (0.27s -> 6.68s, 24.6x) #54

New issue

Closed

opened 2026-07-29 11:40:15 +02:00 by buildagent · 2 comments

buildagent commented

2026-07-29 11:40:15 +02:00

Member

Split out of the #53 investigation, which measured it but scoped it out. Filed so it does not get rediscovered as "#53 came back".

The measurement

rebuild_symbol_edges (crates/indexer/src/index.rs:408-424) runs after every non-skipped resolve pass, inside the same IMMEDIATE transaction as resolution.

repo	refs	rebuild_symbol_edges
rust-ripgrep	36 607	0.27s
rust-analyzer	340 676	6.68s

9.3× the refs for 24.6× the time. Same superlinear shape as the resolver statements fixed in #53, and it survives that fix — it was ~7% of wall before, and is a larger share now that the resolver itself is 2.6–3.5× faster.

Suspected cause

SYMBOL_EDGES_SELECT derives each edge's source by finding the smallest-span symbol covering the ref's start line, as a correlated subquery evaluated once per resolved ref. On rust-analyzer that is 115 997 evaluations against files averaging ~1 396 symbols.

idx_symbols_file_span exists and is what the subquery uses, so this is not the missing-index shape that #53 turned out to be — it is a per-row correlated lookup whose cost grows with symbols-per-file. Worth confirming with EXPLAIN QUERY PLAN before optimising, exactly as #53 did rather than profiling blind.

Why it matters more than 7% suggests

It is inside the resolve transaction, so it extends the window in which the write lock is held. #52's review found the CLI's Deferred policy has no busy-retry, so a code-index index concurrent with a daemon resolve hard-fails SQLITE_BUSY against a 5s busy_timeout. Anything that lengthens that window makes an existing hazard more likely.

Suggested direction

Compute enclosing symbols set-wise once per pass — e.g. a temp table of (file_id, ref_line) -> smallest covering symbol built with a single windowed/grouped query — instead of a correlated subquery per ref. That is the same set-oriented rewrite I020 applied to the resolver itself.

Acceptance

EQP captured for SYMBOL_EDGES_SELECT at tier-1 and tier-3 scale, confirming the cause before changing anything
symbol_edges output byte-identical on all 9 corpus repos (id-independent projection: from/to rendered as path#name@line, plus weight) — the standard set by #53's review
rebuild time scales close to linearly in resolved refs
no phantom introduced; corpus mutation guard stays at 0 rebinds

Not urgent

Correctness is unaffected — this is purely how long a correct answer takes. Same measured-first discipline as #53: do not assume the correlated subquery is the cost until the query plan says so.

Split out of the #53 investigation, which measured it but scoped it out. Filed so it does not get rediscovered as "#53 came back". ## The measurement `rebuild_symbol_edges` (`crates/indexer/src/index.rs:408-424`) runs after every non-skipped resolve pass, inside the same IMMEDIATE transaction as resolution. | repo | refs | rebuild_symbol_edges | |---|---|---| | rust-ripgrep | 36 607 | 0.27s | | rust-analyzer | 340 676 | **6.68s** | 9.3× the refs for **24.6×** the time. Same superlinear shape as the resolver statements fixed in #53, and it survives that fix — it was ~7% of wall before, and is a larger share now that the resolver itself is 2.6–3.5× faster. ## Suspected cause `SYMBOL_EDGES_SELECT` derives each edge's source by finding the **smallest-span symbol covering the ref's start line**, as a correlated subquery evaluated once per resolved ref. On rust-analyzer that is 115 997 evaluations against files averaging ~1 396 symbols. `idx_symbols_file_span` exists and is what the subquery uses, so this is not the missing-index shape that #53 turned out to be — it is a per-row correlated lookup whose cost grows with symbols-per-file. Worth confirming with `EXPLAIN QUERY PLAN` before optimising, exactly as #53 did rather than profiling blind. ## Why it matters more than 7% suggests It is inside the resolve transaction, so it extends the window in which the write lock is held. #52's review found the CLI's `Deferred` policy has no busy-retry, so a `code-index index` concurrent with a daemon resolve hard-fails `SQLITE_BUSY` against a 5s `busy_timeout`. Anything that lengthens that window makes an existing hazard more likely. ## Suggested direction Compute enclosing symbols **set-wise** once per pass — e.g. a temp table of `(file_id, ref_line) -> smallest covering symbol` built with a single windowed/grouped query — instead of a correlated subquery per ref. That is the same set-oriented rewrite I020 applied to the resolver itself. ## Acceptance - [ ] EQP captured for `SYMBOL_EDGES_SELECT` at tier-1 and tier-3 scale, confirming the cause before changing anything - [ ] `symbol_edges` output **byte-identical** on all 9 corpus repos (id-independent projection: `from`/`to` rendered as `path#name@line`, plus `weight`) — the standard set by #53's review - [ ] rebuild time scales close to linearly in resolved refs - [ ] no phantom introduced; corpus mutation guard stays at 0 rebinds ## Not urgent Correctness is unaffected — this is purely how long a correct answer takes. Same measured-first discipline as #53: do not assume the correlated subquery is the cost until the query plan says so.

buildagent added the

labels

2026-07-29 11:40:39 +02:00

buildagent commented

2026-07-29 18:18:59 +02:00

Author

Member

Fixed in `4510063`

Cause confirmed by EQP before changing anything

|--SCAN r
|--CORRELATED SCALAR SUBQUERY 1
|  |--SEARCH s USING COVERING INDEX idx_symbols_file_span (file_id=? AND start_line<?)
|  `--USE TEMP B-TREE FOR ORDER BY        <-- one sort PER REF

The index was being used; the cost was the ORDER BY ... LIMIT 1 inside the correlated subquery — a temp b-tree built 116k times on rust-analyzer.

The change

Resolve the enclosing symbol set-wise, once per distinct (file_id, line), with a single window-function sort into an indexed temp table. On rust-analyzer that is 89 267 evaluations instead of 115 997 — but the real win is one sort instead of 89k.

	before	after
isolated SQL (median of 3)	5.79s	1.35s (4.3×)
end-to-end wall, rust-analyzer	25.7s	21.4s

Output equality proven, not inferred from counts

The issue's acceptance asked for byte-identical edges on all 9 repos. Done two ways:

Symmetric difference of the full edge set (from_id, to_id, weight) between old and new SQL on the same DB — zero on all nine repos. Both sides are GROUP BY results so (from_id, to_id) is unique, meaning EXCEPT cannot mask a duplicate.
End-to-end, the fully-rendered projection (both endpoints as path#name@line, plus weight) is md5-identical on rust-analyzer, py-django, rust-ripgrep, cs-dapper, ts-zod.

Independent confirmation: corpus_ratchet passes unchanged, which pins exact edges counts for all 7 tier-1 repos, and the mutation guard still reports 0 rebinds / 7 056 sites.

One thing I tried that was WORSE — recorded so nobody repeats it

To keep SYMBOL_EDGES_SELECT as a single self-contained statement I tried MATERIALIZED CTEs. Measured 19.9s — 3.4× slower than the correlated form it was meant to replace — because an unindexed CTE join gets probed once per ref, which is the very shape that made the original slow. The temp index is load-bearing. The doc comment says so, with the number, so a future tidy-up re-measures instead of regressing.

Consequences

SYMBOL_EDGES_SELECT is gone (no longer expressible as one SELECT). The daemon's test helper now calls the production rebuild_symbol_edges directly — one implementation, so the two cannot drift, same reasoning as sharing TEST_MODULE_CONTAINS_REF.
m0013's inline copy is deliberately untouched: migrations are frozen history, it is a one-time seed, and runtime rebuilds overwrite it from this function with provably identical output.

Acceptance

EQP captured at both scales, cause confirmed before changing anything
symbol_edges byte-identical on all 9 corpus repos
rebuild scales far closer to linearly (4.3× less work at tier-3; the remaining shape is one sort over distinct lines)
no phantom introduced — workspace green, mutation guard 0 rebinds, ratchet unchanged

## Fixed in `4510063` ### Cause confirmed by EQP before changing anything ``` |--SCAN r |--CORRELATED SCALAR SUBQUERY 1 | |--SEARCH s USING COVERING INDEX idx_symbols_file_span (file_id=? AND start_line<?) | `--USE TEMP B-TREE FOR ORDER BY <-- one sort PER REF ``` The index was being used; the cost was the `ORDER BY ... LIMIT 1` **inside** the correlated subquery — a temp b-tree built 116k times on rust-analyzer. ### The change Resolve the enclosing symbol **set-wise**, once per distinct `(file_id, line)`, with a single window-function sort into an indexed temp table. On rust-analyzer that is 89 267 evaluations instead of 115 997 — but the real win is one sort instead of 89k. | | before | after | |---|---|---| | isolated SQL (median of 3) | 5.79s | **1.35s** (4.3×) | | end-to-end wall, rust-analyzer | 25.7s | **21.4s** | ### Output equality proven, not inferred from counts The issue's acceptance asked for byte-identical edges on all 9 repos. Done two ways: 1. **Symmetric difference of the full edge set** `(from_id, to_id, weight)` between old and new SQL on the same DB — **zero** on all nine repos. Both sides are `GROUP BY` results so `(from_id, to_id)` is unique, meaning `EXCEPT` cannot mask a duplicate. 2. **End-to-end**, the fully-rendered projection (both endpoints as `path#name@line`, plus weight) is md5-identical on rust-analyzer, py-django, rust-ripgrep, cs-dapper, ts-zod. Independent confirmation: `corpus_ratchet` passes unchanged, which pins exact `edges` counts for all 7 tier-1 repos, and the mutation guard still reports 0 rebinds / 7 056 sites. ### One thing I tried that was WORSE — recorded so nobody repeats it To keep `SYMBOL_EDGES_SELECT` as a single self-contained statement I tried `MATERIALIZED` CTEs. Measured **19.9s** — 3.4× *slower* than the correlated form it was meant to replace — because an unindexed CTE join gets probed once per ref, which is the very shape that made the original slow. **The temp index is load-bearing.** The doc comment says so, with the number, so a future tidy-up re-measures instead of regressing. ### Consequences - `SYMBOL_EDGES_SELECT` is gone (no longer expressible as one SELECT). The daemon's test helper now calls the production `rebuild_symbol_edges` directly — one implementation, so the two cannot drift, same reasoning as sharing `TEST_MODULE_CONTAINS_REF`. - **m0013's inline copy is deliberately untouched**: migrations are frozen history, it is a one-time seed, and runtime rebuilds overwrite it from this function with provably identical output. ### Acceptance - [x] EQP captured at both scales, cause confirmed before changing anything - [x] `symbol_edges` byte-identical on all 9 corpus repos - [x] rebuild scales far closer to linearly (4.3× less work at tier-3; the remaining shape is one sort over distinct lines) - [x] no phantom introduced — workspace green, mutation guard 0 rebinds, ratchet unchanged

dhoyer referenced this issue from a commit

2026-07-29 21:25:54 +02:00

perf: resolve enclosing symbols set-wise in rebuild_symbol_edges (#54)

buildagent referenced this issue

2026-07-29 21:26:30 +02:00

I039: OSS corpus test system + the four defects it found (v0.9.0, schema v25) #58

buildagent referenced this issue from a commit

2026-08-03 14:06:57 +02:00

I039: OSS corpus test system + resolver fixes (v0.9.0, schema v25) (#58)

buildagent commented

2026-08-05 10:15:12 +02:00

Author

Member

Fixed and released in v0.9.0.

rebuild_symbol_edges computed each ref's enclosing symbol with a correlated subquery; it is now set-wise via a window function into an indexed temp table. 5.79s → 1.35s, and the resulting edge set is byte-identical on all 9 pinned corpus repos — verified rather than assumed, since a "faster" rewrite that changes the graph would be a silent correctness regression.

Related index work landed alongside under #53 (ix_symbol_buckets_name, ix_file_keys_file/key, ix_file_pkg_file/root, plus m0023_symbols_parent_name_index).

Fixed and released in **v0.9.0**. `rebuild_symbol_edges` computed each ref's enclosing symbol with a correlated subquery; it is now set-wise via a window function into an indexed temp table. **5.79s → 1.35s**, and the resulting edge set is byte-identical on all 9 pinned corpus repos — verified rather than assumed, since a "faster" rewrite that changes the graph would be a silent correctness regression. Related index work landed alongside under #53 (`ix_symbol_buckets_name`, `ix_file_keys_file/key`, `ix_file_pkg_file/root`, plus `m0023_symbols_parent_name_index`).

buildagent closed this issue

2026-08-05 10:15:37 +02:00

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

h-dv/code-index#54

No description provided.

Rows
Columns

perf: rebuild_symbol_edges is superlinear — correlated enclosing-symbol subquery per resolved ref (0.27s -> 6.68s, 24.6x) #54

The measurement

Suspected cause

Why it matters more than 7% suggests

Suggested direction

Acceptance

Not urgent

Fixed in 4510063

Cause confirmed by EQP before changing anything

The change

Output equality proven, not inferred from counts

One thing I tried that was WORSE — recorded so nobody repeats it

Consequences

Acceptance

Fixed in `4510063`