Every vector search reads every chunk in the knowledge base

[roycegeo]

documents::vector_search orders by distance with nothing underneath it:

// crates/utopia-store/src/documents.rs:1255
"SELECT id FROM chunks c
 WHERE c.kb_id = $1 AND c.embedding IS NOT NULL AND {live}
   AND vector_dims(c.embedding) = vector_dims($2)
 ORDER BY c.embedding <=> $2
 LIMIT $3"

grep -rn 'hnsw\|ivfflat' migrations/ returns nothing. Across 37 migrations there is no vector index of any kind, so every hybrid query computes cosine distance against every embedded chunk in the knowledge base and sorts the lot to take ten.

This is not news. 0002_ingest.sql:123 says so in as many words:

The dimension varies with the chosen embedding model. P1 scans sequentially; at volume, build an HNSW index for the configured dimension.

This issue is that note coming due. The ontology-side scans in ontology.rs are a different case and should stay as they are — 0003_graph.sql:22 argues that thousands of rows do not need an index, and it is right. chunks is the table that grows without bound.

Why it cannot just be added

The column is dimensionless. embedding vector with no (N). pgvector cannot build HNSW on a column of unknown dimension, and the dimension here follows the workspace's configured embedding model, which is not known when the migration runs. The P1 decision was correct; it just left the index unbuildable without a second step.

The query is filtered, and HNSW post-filters. {live} expands via record_axis::chunk_live_at to

c.created_at <= coalesce($4, now())
AND (c.superseded_at IS NULL OR c.superseded_at > coalesce($4, now()))

on top of kb_id, embedding IS NOT NULL and the dimension guard. pgvector walks the index for ef_search candidates and then applies the WHERE, so a selective filter returns fewer than LIMIT rows. In a table keyed by kb_id across tenants that is the ordinary case, not a corner: a small knowledge base sharing a table with a large one can get zero hits from a perfectly good index.

The running container is pgvector/pgvector:pg16 at extension version 0.8.6 (checked, not assumed), so hnsw.iterative_scan is available. That is the mechanism for exactly this failure — it keeps pulling from the index until LIMIT is satisfied or hnsw.max_scan_tuples is reached. Any fix that adds the index without setting it will look correct in a single-tenant test and silently under-return in a real deployment.

The dimension guard is not indexable. vector_dims(c.embedding) = vector_dims($2) on line 1258 is evaluated per candidate row and cannot narrow anything. It needs to become part of the index predicate or move.

What to build

• Record the embedding dimension a knowledge base's chunks were written at, so the index has a number to be built for.
• A partial HNSW index per dimension in use, vector_cosine_ops to match the <=> operator, built CONCURRENTLY or the migration takes an ACCESS EXCLUSIVE lock on chunks for the length of the build.
• IF NOT EXISTS, because the migrations CI job replays every migration twice.
• hnsw.iterative_scan = relaxed_order on the retrieval path, with max_scan_tuples chosen deliberately and commented with the reasoning.
• Migration 0038_, after checking the latest number on dev — two branches each adding an 0038_ merge cleanly and then neither runs.
• Decide in the same change whether entities.profile_embedding gets the same treatment. It has the same shape and, per the type-resolution issue, worse caller pressure.

Not this

ivfflat. It needs a representative sample at build time to pick its lists, and a corpus that grows past the sample degrades recall quietly — no error, just worse answers. For a system whose claim is traceable evidence, silent recall loss is the wrong failure mode.

Dropping the record-axis filter so the index applies cleanly. Replay is the product (0019). The index accommodates the filter, not the other way round.

Unit tests

From the SME's side the index is invisible. The contract is recall and the record axis, so every test here must fail if the index changes answers and stay quiet if it only changes plans. Each test is run twice — once with enable_indexscan = off to force the exact scan, once with the index live — and the two must agree.

crates/utopia-store/tests/a_search_reads_the_base_as_it_was.rs already pins the record axis on the vector path and is the primary guard. It must pass unchanged with the index present. If it needs editing, the index changed semantics and the change is wrong.

New, in crates/utopia-store/tests/the_nearest_chunk_is_found_however_it_is_reached.rs:

• the_nearest_neighbour_is_returned_whatever_the_plan — seed chunks with hand-built vectors and one unambiguously nearest. Exact and indexed paths return the same first row.
• a_filtered_search_still_fills_its_limit — the rule that actually matters. One knowledge base holding a single matching chunk beside another holding many thousand; LIMIT 10 returns the one. This is the post-filter failure, and without iterative_scan it returns nothing.
• a_search_never_crosses_a_knowledge_base — tenancy, not performance. The ANN path must not leak a neighbouring base's chunk in.
• chunks_of_another_dimension_are_not_candidates — a workspace that changed embedding model leaves two dimensions in one table. The guard holds and the operator does not error.
• a_superseded_chunk_is_not_a_hit — a reparse displaces a chunk; the indexed path agrees with the exact one.
• a_search_with_a_moment_sees_what_was_alive_then — 0019 restated directly against the index.

All of these are database-gated. Use test_db::url(), never the env var directly, and run them with UTOPIA_TEST_REQUIRE_DB=1 — without it they return ok while doing nothing, which on this change would be worse than no test at all.

Acceptance testing

1. docker compose up -d db, then run the migrations twice. A CONCURRENTLY index that is not IF NOT EXISTS fails the second pass, and that is the CI job's whole point.
2. Seed a corpus large enough for the question to mean anything — at least tens of thousands of embedded chunks in one base, with a second small base alongside it to exercise the filter.
3. EXPLAIN (ANALYZE, BUFFERS) on the retrieval query before and after, both pasted into the PR. Seq Scan on chunks must become an index scan, with the wall-clock figures beside it.
4. Recall@10 measured and stated. Take 200 real queries, compute exact top-10 with enable_indexscan = off, compute top-10 with the index, report the overlap. This repository has agreed no thresholds — there is no docs/engineering-standards.md — so the PR proposes a bar and the reasoning for it rather than quietly adopting one.
5. bash scripts/smoke.sh against a throwaway deployment. Register, upload, ingest, search still works end to end. Point it at a database you can discard: the first account registered becomes the administrator.
6. Ask five questions in the chat before and after and confirm each answer still cites the sentence its fact came from. An index that improves latency and loses a citation has failed.
7. cargo test --workspace with UTOPIA_DATABASE_URL and UTOPIA_TEST_REQUIRE_DB=1 both set.

[roycegeo]

Sequencing: #514 is the other caller of an unindexed vector column (entities.profile_embedding), and it has the same dimensionless-column obstacle. Decide there or here whether both indexes land in the same migration — if they do, the recall measurement in this issue's acceptance section should cover the entity side too.

#515 is the other half of the retrieval path. The two are independent and can land in either order, but measuring query latency for one while the other is in flight will produce numbers nobody can attribute.

[WaylandYang]

Measured this on a scratch database before deciding anything: 60,020 chunks of 1024 dims across three bases (50,000 / 10,000 / 20), random vectors, pgvector 0.8.6.

Today's query, base of 50k	seq scan, 195 ms
Today's query, base of 10k	chunks_kb_idx + sort, 39 ms
Expression HNSW index, serial build over 60k rows	87 s, 469 MB
Rewritten query, base of 50k	4.5 ms
HNSW forced on the 10k base, iterative_scan = off	3 rows of the 24 asked for
same, relaxed_order	24 rows, 7.9 ms
recall@24 vs exact, ef_search 40 / 200 / 1000	16 / 16 / 22

So the cost today is about 4 ms per thousand chunks in the base being searched, per query. Nobody feels it at hundreds of chunks; a base of 100k pays ~0.4 s per question on this leg.

The diagnosis holds: dimensionless column, post-filtering that empties a small base, iterative_scan as the fix, the dimension guard not indexable. Three things the measurement added:

1. The dimension has to be a literal in the SQL. With vector_dims(embedding) = $2 bound as a parameter the custom plan uses the partial index and the generic plan falls back to a seq scan. sqlx's prepared statements switch to a generic plan after five executions, so the index would silently stop being used on the sixth query. format! the integer in.
2. The planner already routes small and mid bases to the exact path. With chunks_kb_idx present it chose index-plus-sort for the 20-row and the 10k-row base on its own and HNSW only for the 50k one, so no application-side threshold is needed. relaxed_order still has to be set: it is what saves the case where HNSW is chosen and the base is a fraction of the table, and it costs nothing on the full-base case.
3. This is not a numbered migration. The dimension is only known when vectors are written, and CREATE INDEX CONCURRENTLY cannot run inside the transaction sqlx wraps migrations in. The shape that fits is a job: when the ingest pipeline writes vectors of a dimension that has no index yet, it queues one build, which runs CONCURRENTLY IF NOT EXISTS outside a transaction. One more deployment note: a parallel build wants shared memory and Docker's default 64 MB /dev/shm fails it, so the build is serial or compose gets shm_size.

On recall: random vectors are the worst case for ANN, so 16/24 says nothing about real embeddings, but it does make the acceptance item you wrote, 200 real queries against the exact top-k, the gate for turning this on rather than a nice-to-have. Raising ef_search from 40 to 200 cost 10 ms here and is likely worth it.

Sequencing: after #515, in the same cut as #514, since entities.profile_embedding takes the same mechanism.

[WaylandYang]

#566 builds it, as a job rather than a migration, and decision record 0035 says why. Measuring on real embeddings before opening it added three things to the numbers above.

The build wants memory. At the default maintenance_work_mem of 64 MB the graph stops fitting after 13,930 rows of 1024 dims and a serial build over 50k rows took 4 min 20 s; at 512 MB, 61 s for a 394 MB index. The job sets it for its session.

The setting that stops an iterative scan short is hnsw.scan_mem_multiplier, and max_scan_tuples is not. With the index forced (the kb_id index dropped on the copy) beside a synthetic tenant of 50,000 chunks, 522 real queries on bases that are each about 1% of the index came back short on 154 lists at the default multiplier, recall@10 0.705 at 32 ms a query; raising max_scan_tuples to 100,000 changed nothing; a multiplier of 4 filled every list, recall 1.0 at 74 ms a query. Without relaxed_order at all it was 0.075, so your diagnosis of the post-filter failure holds exactly. The read path sets all three.

The planner routes small bases to the exact path on its own once chunks_kb_idx exists. The same 229-chunk base beside the 50k took the kb index and a sort in 1.5 ms while the 50k base took the HNSW path in 3.8 ms, so no application-side threshold. Before and after on the 50k base: 378.6 ms to 6.0 ms; both EXPLAIN (ANALYZE, BUFFERS) outputs are in the PR. Recall@10 on 200 real entity profiles with the index forced is 0.997 by distance, the rest being ties at the tenth place.

The bar the PR proposes is recall@10 of 0.99 against the exact top ten on real embeddings with the index forced, and both tables pass it once the scan memory is raised. Your test list is what the new tests do, plus the entity side for #514, and the record notes the one case still unmeasured: two large tenants of different subject matter on one deployment.