h-dv/code-index

Fork 0

perf: cold-index throughput degrades ~5-6x from tier-1 to tier-3 repos (time scales ~refs^1.7) #53

New issue

Open

opened 2026-07-28 22:06:08 +02:00 by buildagent · 1 comment

buildagent commented

2026-07-28 22:06:08 +02:00

Member

Measured by the new tier-3 scale suite (#41) on its first run. v0.8.7.

The data

repo	lang	files	refs	wall	refs/s
rust-ripgrep	rust	231	36 607	1.5s	24 405
ts-zod	ts	558	85 027	3.4s	25 008
rust-analyzer	rust	1778	340 676	77–92s	3 684–4 417
py-django	python	4235	460 978	99–120s	3 836–4 673

Throughput per ref falls by 5–6x between the two tiers, and it is not a language-mix artifact — the cleanest comparison is Rust-to-Rust:

ripgrep        36 607 refs →  1.5s
rust-analyzer 340 676 refs → 77.1s
                9.3x refs  →  51x time     ⇒  time ~ refs^1.73

ts-zod is the useful control: at 85k refs it still runs at 25k refs/s, so the curve is flat through tier-1 and bends somewhere above it.

Why this matters

A 20k-file monorepo extrapolates badly. At refs^1.7, ~2M refs implies roughly 20 minutes for a cold index — which changes the product story for large repos, and the daemon's cold-start behaviour with it.
It is invisible to every existing benchmark: bench_cold_index.rs, bench_find_references.rs and bench_search_symbols.rs all run against 4–14 file fixtures.

What is NOT the problem

Memory is fine. Peak RSS 232–300 MiB on both tier-3 repos — an order of magnitude below the 8 GiB I had guessed when writing the ceiling. No OOM risk; the gate was tightened to 2 GiB.
Query latency is fine. On the 341k-ref graph: find_callers-shaped p50 80µs / p99 321µs, symbol prefix p50 118µs / p99 579µs, FTS trigram p50 1.2ms / p99 4.3ms. The index shape stays queryable at scale.
Not the edge cap. 80 397 and 52 615 edges, far below the daemon's 1M cap.

So this is specifically the cold-index write/resolve path, not the read path.

Where to look first

The three-tier resolver in resolve_ref_targets_in_tx is the prime suspect — it is the stage whose cost is driven by candidate-pool sizes, which grow with the repo rather than with the file being indexed. I025 already hit a superlinear blow-up in this area once (SQLite mis-planned name-joins into the WITHOUT-ROWID qual_groups, 109s → 3.5s after pinning CROSS JOIN order), so a query-plan regression at a new scale is plausible.

Suggested first step: EXPLAIN QUERY PLAN each tier pass against a rust-analyzer-sized DB and compare with the same plans on a tier-1 DB, rather than profiling blind.

Not urgent, not a correctness issue

Every correctness gate is green on these repos. This is a scaling characteristic worth understanding before someone points code-index at a genuinely large monorepo — and worth a baseline in #45 so it cannot silently get worse.

Acceptance

root cause identified (query plan vs algorithmic)
refs/s at tier-3 within ~2x of tier-1, or a written explanation of why the gap is irreducible
tier-3 wall clock recorded in the #45 baseline so regressions are visible
no phantom introduced (precision gate + corpus mutation guard stay at 0)

**Measured by the new tier-3 scale suite (#41) on its first run.** v0.8.7. ## The data | repo | lang | files | refs | wall | **refs/s** | |---|---|---|---|---|---| | rust-ripgrep | rust | 231 | 36 607 | 1.5s | **24 405** | | ts-zod | ts | 558 | 85 027 | 3.4s | **25 008** | | rust-analyzer | rust | 1778 | 340 676 | 77–92s | **3 684–4 417** | | py-django | python | 4235 | 460 978 | 99–120s | **3 836–4 673** | Throughput per ref falls by **5–6x** between the two tiers, and it is not a language-mix artifact — the cleanest comparison is Rust-to-Rust: ``` ripgrep 36 607 refs → 1.5s rust-analyzer 340 676 refs → 77.1s 9.3x refs → 51x time ⇒ time ~ refs^1.73 ``` ts-zod is the useful control: at 85k refs it still runs at 25k refs/s, so the curve is flat through tier-1 and bends somewhere above it. ## Why this matters - A 20k-file monorepo extrapolates badly. At `refs^1.7`, ~2M refs implies roughly 20 minutes for a cold index — which changes the product story for large repos, and the daemon's cold-start behaviour with it. - It is invisible to every existing benchmark: `bench_cold_index.rs`, `bench_find_references.rs` and `bench_search_symbols.rs` all run against 4–14 file fixtures. ## What is NOT the problem - **Memory is fine.** Peak RSS 232–300 MiB on both tier-3 repos — an order of magnitude below the 8 GiB I had guessed when writing the ceiling. No OOM risk; the gate was tightened to 2 GiB. - **Query latency is fine.** On the 341k-ref graph: `find_callers`-shaped p50 80µs / p99 321µs, symbol prefix p50 118µs / p99 579µs, FTS trigram p50 1.2ms / p99 4.3ms. The index shape stays queryable at scale. - **Not the edge cap.** 80 397 and 52 615 edges, far below the daemon's 1M cap. So this is specifically the **cold-index write/resolve path**, not the read path. ## Where to look first The three-tier resolver in `resolve_ref_targets_in_tx` is the prime suspect — it is the stage whose cost is driven by candidate-pool sizes, which grow with the repo rather than with the file being indexed. I025 already hit a superlinear blow-up in this area once (SQLite mis-planned name-joins into the WITHOUT-ROWID `qual_groups`, 109s → 3.5s after pinning `CROSS JOIN` order), so a query-plan regression at a new scale is plausible. Suggested first step: `EXPLAIN QUERY PLAN` each tier pass against a rust-analyzer-sized DB and compare with the same plans on a tier-1 DB, rather than profiling blind. ## Not urgent, not a correctness issue Every correctness gate is green on these repos. This is a scaling characteristic worth understanding before someone points code-index at a genuinely large monorepo — and worth a baseline in #45 so it cannot silently get worse. ## Acceptance - [ ] root cause identified (query plan vs algorithmic) - [ ] refs/s at tier-3 within ~2x of tier-1, or a written explanation of why the gap is irreducible - [ ] tier-3 wall clock recorded in the #45 baseline so regressions are visible - [ ] no phantom introduced (precision gate + corpus mutation guard stay at 0)

buildagent added the

labels

2026-07-28 22:06:12 +02:00

buildagent referenced this issue

2026-07-28 22:06:30 +02:00

test: tier-3 scale ceilings — 20k+ file repos, 1M-edge cap, peak RSS, query p99, FTS growth #41

buildagent commented

2026-07-29 00:57:39 +02:00

Author

Member

Fixed — but two of my earlier claims were wrong, corrected below

Root cause: three missing indexes, not algorithmic cost

The "O(refs × candidates) is irreducible" hypothesis is refuted, with identical output produced for a fraction of the CPU:

symbols had no index on parent_id. Every m.parent_id = par.id AND m.name = ? join (tier 1R identifier decisions, tier 1R self-receiver, tier 1Q parent-anchored candidates) fell back to idx_symbols_file_span and scanned the parent's whole file. Measured on rust-analyzer: 121,234,431 symbol rows visited to emit 6,747 — 86,861 (binding, parent) pairs × ~1,396 symbols/file. That one statement was 37% of a 70s resolve.
temp.symbol_buckets could not be name-joined. Its WITHOUT ROWID PK is (file_id, name, lang, method_only), so tier 3's b.name = st.name AND b.lang = fr.lang had no path and SQLite inverted the plan into SCAN b (33k buckets) × SEARCH fr BY lang (1.5k files) — a cross product. 26s of 70s on rust-analyzer, 66s of 96s on django. This is I025's failure mode recurring: a name-join against a WITHOUT ROWID temp table.
temp.file_keys / temp.file_pkg had no indexes, so SQLite built an AUTOMATIC COVERING INDEX per consuming statement.

The change

m0023_symbols_parent_name_index (persistent symbols(parent_id, name)), plus four temp indexes built inside resolve_ref_targets_in_tx. No re-heal — an index changes no resolution. No ANALYZE: measured, it makes the re-heal 2.8× slower (9.4s → 26.3s) even with the indexes, because sqlite_stat1 pushes the planner back onto worse plans. That dependency is now pinned by a test asserting no sqlite_stat1 is ever generated, rather than living only in a doc comment.

CORRECTION 1 — I overstated the speedup

I reported 91.4s → 25.1s (3.6×) and 105s → 24.4s (4.3×). Those "before" baselines were taken against plain HEAD, which also lacked the #52 fix, so they conflated two changes. Holding #52 constant, the isolated #53 contribution is:

repo	before	after	speedup
rust-analyzer	64.1s	24.6s	2.6× (resolve stage 58.9s → 19.4s)
py-django	87.2s	24.6s	3.5× (resolve stage 79.2s → 17.8s)

Scoped passes — what a watcher actually runs — improve more: rust-analyzer 13,983ms → 5,821ms (2.4×), django 20,123ms → 1,842ms (10.9×).

CORRECTION 2 — "within ~2× between tiers" does NOT hold

That was this issue's acceptance criterion and I claimed it was met. It isn't. Resolve-stage throughput after the change: tier-1 ranges 55k–138k refs/s; tier-3 is rust-analyzer 17.5k and py-django 26.0k. Fastest tier-1 / slowest tier-3 = 7.9×; even the slowest tier-1 (ts-zod) vs rust-analyzer is 3.1×.

A log-log fit of resolve time vs refs across all 9 corpus repos: exponent 1.86 → 1.55. The superlinearity is reduced, not removed.

So this issue should not be closed as "scaling fixed". The indexes were the dominant term and are worth shipping on their own, but a residual super-linear component survives. Remaining known headroom, none of it attempted here:

the import_norm precompute (IMPORT_SEGMENTS recomputes 7 nested REPLACE() per candidate×import probe) — projected the resolve stage to ~14s CPU;
de-duplicating file_pkg to distinct pkg_tail before the GLOB, and driving qual_stem_files off file_keys instead of f.path GLOB;
rebuild_symbol_edges is also superlinear (0.27s → 6.68s, 24.6×) via a correlated enclosing-symbol subquery — ~7% of wall, worth its own issue.

Correctness: verified, not assumed

Matching resolved-ref counts is not proof — the same count could bind to different targets. An adversarial review built two binaries differing only by this change and compared four id-independent projections (refs, symbols, ref_count, symbol_edges, targets rendered path#name@line) across all 9 corpus repos: 1,036,264 ref rows, zero differing rows. Per-tier counters identical. Also verified: 5-step incremental histories converge identically; a deliberate ANALYZE plan-drift stress still yields a byte-identical projection; and 24,394 rows of production read-side SQL are unchanged.

Tie-break safety is proven structurally, not just measured: every ON CONFLICT DO NOTHING insert's conflict-target PK is exactly the GROUP BY of its feeding SELECT, so a within-statement conflict is impossible and cross-statement order is tier order in Rust, not row order.

Costs

idx_symbols_parent_name: +32% on isolated symbol INSERT (0.257s → 0.339s for 35k rows) — ~0.3% of total wall, below noise end-to-end.
DB size +0.9% (rust-analyzer 105.4MB → 106.3MB), peak RSS +2.6% (236.8 → 242.9MB). Both are recorded metrics in target/corpus/scale-*.json, not gates — but they need re-baselining.

Acceptance

root cause identified (query plan, not algorithmic) — with EQP before/after
refs/s at tier-3 within ~2× of tier-1 — NOT met (3.1–7.9×); superlinearity reduced 1.86 → 1.55
tier-3 wall clock recorded in the scale suite
no phantom introduced — workspace suite green, corpus mutation guard 0 rebinds

## Fixed — but two of my earlier claims were wrong, corrected below ### Root cause: three missing indexes, not algorithmic cost The "O(refs × candidates) is irreducible" hypothesis is **refuted**, with identical output produced for a fraction of the CPU: 1. **`symbols` had no index on `parent_id`.** Every `m.parent_id = par.id AND m.name = ?` join (tier 1R identifier decisions, tier 1R self-receiver, tier 1Q parent-anchored candidates) fell back to `idx_symbols_file_span` and scanned the parent's **whole file**. Measured on rust-analyzer: **121,234,431 symbol rows visited to emit 6,747** — 86,861 (binding, parent) pairs × ~1,396 symbols/file. That one statement was 37% of a 70s resolve. 2. **`temp.symbol_buckets` could not be name-joined.** Its `WITHOUT ROWID` PK is `(file_id, name, lang, method_only)`, so tier 3's `b.name = st.name AND b.lang = fr.lang` had no path and SQLite inverted the plan into `SCAN b (33k buckets) × SEARCH fr BY lang (1.5k files)` — a cross product. 26s of 70s on rust-analyzer, **66s of 96s on django**. This is **I025's failure mode recurring**: a name-join against a `WITHOUT ROWID` temp table. 3. **`temp.file_keys` / `temp.file_pkg` had no indexes**, so SQLite built an `AUTOMATIC COVERING INDEX` per consuming statement. ### The change `m0023_symbols_parent_name_index` (persistent `symbols(parent_id, name)`), plus four temp indexes built inside `resolve_ref_targets_in_tx`. No re-heal — an index changes no resolution. **No `ANALYZE`**: measured, it makes the re-heal 2.8× *slower* (9.4s → 26.3s) even with the indexes, because `sqlite_stat1` pushes the planner back onto worse plans. That dependency is now pinned by a test asserting no `sqlite_stat1` is ever generated, rather than living only in a doc comment. ### CORRECTION 1 — I overstated the speedup I reported 91.4s → 25.1s (3.6×) and 105s → 24.4s (4.3×). Those "before" baselines were taken against plain HEAD, which also lacked the #52 fix, so they conflated two changes. Holding #52 constant, the isolated #53 contribution is: | repo | before | after | speedup | |---|---|---|---| | rust-analyzer | 64.1s | 24.6s | **2.6×** (resolve stage 58.9s → 19.4s) | | py-django | 87.2s | 24.6s | **3.5×** (resolve stage 79.2s → 17.8s) | Scoped passes — what a watcher actually runs — improve more: rust-analyzer 13,983ms → 5,821ms (2.4×), django 20,123ms → 1,842ms (10.9×). ### CORRECTION 2 — "within ~2× between tiers" does NOT hold That was this issue's acceptance criterion and I claimed it was met. It isn't. Resolve-stage throughput after the change: tier-1 ranges 55k–138k refs/s; tier-3 is rust-analyzer 17.5k and py-django 26.0k. **Fastest tier-1 / slowest tier-3 = 7.9×**; even the slowest tier-1 (ts-zod) vs rust-analyzer is **3.1×**. A log-log fit of resolve time vs refs across all 9 corpus repos: exponent **1.86 → 1.55**. The superlinearity is **reduced, not removed**. So this issue should **not** be closed as "scaling fixed". The indexes were the dominant term and are worth shipping on their own, but a residual super-linear component survives. Remaining known headroom, none of it attempted here: - the `import_norm` precompute (`IMPORT_SEGMENTS` recomputes 7 nested `REPLACE()` per candidate×import probe) — projected the resolve stage to ~14s CPU; - de-duplicating `file_pkg` to distinct `pkg_tail` before the GLOB, and driving `qual_stem_files` off `file_keys` instead of `f.path GLOB`; - `rebuild_symbol_edges` is *also* superlinear (0.27s → 6.68s, 24.6×) via a correlated enclosing-symbol subquery — ~7% of wall, worth its own issue. ### Correctness: verified, not assumed Matching resolved-ref counts is not proof — the same count could bind to different targets. An adversarial review built two binaries differing **only** by this change and compared four id-independent projections (refs, symbols, `ref_count`, `symbol_edges`, targets rendered `path#name@line`) across all 9 corpus repos: **1,036,264 ref rows, zero differing rows.** Per-tier counters identical. Also verified: 5-step incremental histories converge identically; a deliberate `ANALYZE` plan-drift stress still yields a byte-identical projection; and 24,394 rows of production read-side SQL are unchanged. Tie-break safety is proven structurally, not just measured: every `ON CONFLICT DO NOTHING` insert's conflict-target PK is exactly the `GROUP BY` of its feeding SELECT, so a within-statement conflict is impossible and cross-statement order is tier order in Rust, not row order. ### Costs - `idx_symbols_parent_name`: **+32%** on isolated symbol INSERT (0.257s → 0.339s for 35k rows) — ~0.3% of total wall, below noise end-to-end. - DB size **+0.9%** (rust-analyzer 105.4MB → 106.3MB), peak RSS +2.6% (236.8 → 242.9MB). Both are *recorded* metrics in `target/corpus/scale-*.json`, not gates — but they need re-baselining. ### Acceptance - [x] root cause identified (query plan, not algorithmic) — with EQP before/after - [ ] **refs/s at tier-3 within ~2× of tier-1 — NOT met** (3.1–7.9×); superlinearity reduced 1.86 → 1.55 - [x] tier-3 wall clock recorded in the scale suite - [x] no phantom introduced — workspace suite green, corpus mutation guard 0 rebinds

buildagent referenced this issue

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

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

buildagent referenced this issue

2026-07-29 11:51:58 +02:00

test: wall-clock-bounded resolver tests flake under machine load (10s bound, observed failing at load ~45) #55

buildagent referenced this issue

2026-07-29 17:35:26 +02:00

test: wall-clock-bounded resolver tests flake under machine load (10s bound, observed failing at load ~45) #55