perf: search_symbols ranks by per-row correlated COUNT(*) over the full prefix match set #19

New issue

Closed

opened 2026-07-07 13:49:37 +02:00 by buildagent · 1 comment

buildagent commented

2026-07-07 13:49:37 +02:00

Member

Summary

search_symbols ranks results by a correlated ref_count subquery evaluated for every symbol matching the prefix, before LIMIT. For a short/broad prefix ("a", "get") on a large repo this fires O(prefix_matches) index-count subqueries plus a full in-memory sort — cost scales with prefix breadth, not the requested limit.

Where

crates/daemon/src/local_index.rs:552 (ranked-page query) — (SELECT COUNT(*) FROM refs r WHERE r.target_id = s.id) AS ref_count, then ORDER BY ref_count DESC (line 559), LIMIT/OFFSET (563). No minimum-prefix guard: pattern is format!("{query}%") (461) and the MCP handler only clamps limit to 1..100 (crates/mcp-server/src/server.rs:2246).

Severity

Medium. idx_refs_target (m0001) makes each COUNT a cheap index range-count, not a scan, so it's a latency spike for broad short prefixes on large indexes rather than a severe cost. Runs under the connection checkout.

Fix options

Materialize ref_count as a maintained column on symbols (updated during resolve, or refreshed per batch) with an index, so ranking reads a stored integer. Requires a new migration (m0012) + writer maintenance — migrations m0001–m0011 are frozen, so this is additive.
Minimum-prefix / bounded top-K: require a minimum prefix length, or rank a bounded candidate set by a cheaper proxy first.

Prefer (1) for a permanent fix. Surfaced by the v0.5.8 ultradeep review (performance dimension, CONFIRMED).

Acceptance

Broad short-prefix search_symbols no longer evaluates a per-row subquery over the whole candidate set.
Ranking order (by usefulness/ref_count) preserved; existing bench_search_symbols + smoke tests stay green.
If a migration is added, it is frozen once shipped and unit-tested for on-upgrade correctness like m0011.

## Summary `search_symbols` ranks results by a correlated `ref_count` subquery evaluated for **every** symbol matching the prefix, before `LIMIT`. For a short/broad prefix (`"a"`, `"get"`) on a large repo this fires O(prefix_matches) index-count subqueries plus a full in-memory sort — cost scales with prefix breadth, not the requested `limit`. ## Where `crates/daemon/src/local_index.rs:552` (ranked-page query) — `(SELECT COUNT(*) FROM refs r WHERE r.target_id = s.id) AS ref_count`, then `ORDER BY ref_count DESC` (line 559), `LIMIT/OFFSET` (563). No minimum-prefix guard: pattern is `format!("{query}%")` (461) and the MCP handler only clamps `limit` to 1..100 (`crates/mcp-server/src/server.rs:2246`). ## Severity Medium. `idx_refs_target` (m0001) makes each COUNT a cheap index range-count, not a scan, so it's a latency spike for broad short prefixes on large indexes rather than a severe cost. Runs under the connection checkout. ## Fix options 1. **Materialize `ref_count`** as a maintained column on `symbols` (updated during resolve, or refreshed per batch) with an index, so ranking reads a stored integer. Requires a **new migration (m0012)** + writer maintenance — migrations m0001–m0011 are frozen, so this is additive. 2. **Minimum-prefix / bounded top-K**: require a minimum prefix length, or rank a bounded candidate set by a cheaper proxy first. Prefer (1) for a permanent fix. Surfaced by the v0.5.8 ultradeep review (performance dimension, CONFIRMED). ## Acceptance - Broad short-prefix `search_symbols` no longer evaluates a per-row subquery over the whole candidate set. - Ranking order (by usefulness/ref_count) preserved; existing `bench_search_symbols` + smoke tests stay green. - If a migration is added, it is frozen once shipped and unit-tested for on-upgrade correctness like m0011.

buildagent added this to the v0.5.9 milestone

2026-07-07 13:50:17 +02:00

buildagent commented

2026-07-07 16:13:43 +02:00

Author

Member

Implemented on fix/ultradeep-review-findings (commit 3bfd136), via fix option 1 (materialized column).

search_symbols no longer evaluates the per-row correlated (SELECT COUNT(*) FROM refs WHERE target_id = s.id) over the whole prefix-match set. A stored symbols.ref_count column (migration m0012) is read directly by the three ranking sites (search_symbols page, repo_map empty-graph degrade, changed_symbols select).

The indexer keeps it current in recompute_ref_counts, called in the same transaction as resolve_ref_targets (the only place target_ids change), via a single aggregate pass — GROUP BY target_id on idx_refs_target, UPDATE...FROM joined to symbols by PK — O(refs), not per-symbol. A reader never sees stale counts.

m0012 backfills existing DBs with the same aggregate; CURRENT_VERSION → 12 (frozen once shipped).

Acceptance: ranking order preserved (s.id ASC tiebreak unchanged); bench_search_symbols + smoke tests stay green. Tests: m0012_backfills_ref_count_from_resolved_refs (upgrade backfill, NULL targets excluded) + search_symbols_ranks_by_materialized_ref_count (e2e: a called symbol outranks its never-called same-prefix sibling through real indexing). Closing.

Implemented on `fix/ultradeep-review-findings` (commit `3bfd136`), via **fix option 1** (materialized column). `search_symbols` no longer evaluates the per-row correlated `(SELECT COUNT(*) FROM refs WHERE target_id = s.id)` over the whole prefix-match set. A stored `symbols.ref_count` column (migration **m0012**) is read directly by the three ranking sites (search_symbols page, repo_map empty-graph degrade, changed_symbols select). The indexer keeps it current in `recompute_ref_counts`, called in the **same transaction** as `resolve_ref_targets` (the only place `target_id`s change), via a single aggregate pass — `GROUP BY target_id` on `idx_refs_target`, `UPDATE...FROM` joined to `symbols` by PK — **O(refs)**, not per-symbol. A reader never sees stale counts. m0012 backfills existing DBs with the same aggregate; `CURRENT_VERSION → 12` (frozen once shipped). **Acceptance:** ranking order preserved (`s.id ASC` tiebreak unchanged); `bench_search_symbols` + smoke tests stay green. Tests: `m0012_backfills_ref_count_from_resolved_refs` (upgrade backfill, NULL targets excluded) + `search_symbols_ranks_by_materialized_ref_count` (e2e: a called symbol outranks its never-called same-prefix sibling through real indexing). Closing.

buildagent referenced this issue

2026-07-07 16:13:51 +02:00

perf: repo_map edge cache is globally invalidated by any file reindex #20

buildagent closed this issue

2026-07-07 16:14:12 +02:00