Selective Context can return 0 results for a user with a small share of a large collection (HNSW post-filter)

[bygadd]

With Selective Context (a scoped provider), retrieval can return 0 documents for a user whose indexed chunks are only a small fraction of a large collection; users with small corpora are fine.

Cause: VectorDB._similarity_search runs roughly ... WHERE id IN (<chunk_ids>) ORDER BY embedding <=> :q LIMIT k. For a large IN list the planner can pick an HNSW index scan: it finds the globally-nearest ~hnsw.ef_search vectors first, then post-filters by id. If none of the user's chunks are among the global-nearest, the result is empty.

Two ways to address:

• pgvector ≥ 0.8.0 native: SET hnsw.iterative_scan = relaxed_order (off by default) — HNSW keeps scanning until enough rows pass the filter. Simplest where available.
• App-side (what we used on 5.3.x): a MATERIALIZED CTE that pre-filters by id (btree) before computing similarity, so the HNSW plan is never chosen — deterministic and exact.

Note: the plan choice is cost-dependent — in a re-test the planner used the btree id index and returned correct rows, so the 0-result plan isn't guaranteed; it's a latent risk under certain id-list sizes/stats rather than a constant failure.

(Disclosure: investigated with AI assistance; verified against the source and on a live deployment.)

[bygadd]

Follow-up from running this on a larger deployment (pgvector 0.8.0, ~10.4M-chunk collection):

When Selective Context is scoped to a whole provider for a user with a large corpus, doc_search enumerates all of the user's in-scope chunk_ids (we saw ~2.46M). With the id-filtered ORDER BY embedding <=> q LIMIT k, the planner can pick an HNSW scan that post-filters down to 0 rows (the case in this issue) — or fall back to a brute-force sort over the whole filtered set.

On pgvector ≥ 0.8 the one-line native fix works well and is behaviour-preserving — it keeps the existing exhaustive batched logic (full/exact results) and just lets an HNSW plan keep scanning past the first ef_search batch instead of post-filtering to 0:

session.execute(sa.text('SET LOCAL hnsw.iterative_scan = strict_order'))

strict_order preserves exact distance order (relaxed_order trades order for speed). On our deployment a whole-files-provider scope (~2.46M in-scope chunks) then returns full, relevant results with no 0-result and no timeout.

(Disclosure: investigated and verified on a live deployment, with AI assistance.)

[kyteinsky]

hi, thanks for the report.
would you mind following the bug report or the feature request template, and using your own words to write the issue matter?
see https://github.com/nextcloud/context_chat_backend/blob/master/.github/AI_POLICY.md#human-written-communication
it is kind of hard to parse the AI written text.

When Selective Context is scoped to a whole provider (e.g. the entire files provider) for a user with a large corpus, doc_search enumerates all of the user's in-scope chunk_ids (we observed ~2.46M — a ~93 MB bound array). The CTE then brute-forces the distance over the whole filtered set — O(n) — and exceeds statement_timeout, surfacing as DbException: Error: performing doc search in vectordb. (Stock batching at PG_BATCH_SIZE does ~50 sequential brute-force scans instead — no error, but on the order of minutes.)

please post the logs from the context_chat_backend container and the vector db, if possible the auto-explain logs from the db, which might have the details we need in this issue. See this for an example:

context_chat_backend/.github/workflows/integration-test.yml

Lines 99 to 132 in 9c525e5

	- name: Enable PostgreSQL slow query logging and auto_explain
	run: |
	docker exec postgres bash -c "\
	cat >> /var/lib/postgresql/data/postgresql.conf <<EOF
	# slow query logging
	log_min_duration_statement = 20
	# auto_explain for slow queries
	session_preload_libraries = 'auto_explain'
	auto_explain.log_min_duration = '20ms'
	auto_explain.log_analyze = on
	auto_explain.log_buffers = on
	auto_explain.log_nested_statements = on
	auto_explain.log_verbose = on
	# file-based logging
	logging_collector = on
	log_directory = '/var/log/pg_log'
	log_filename = 'postgresql.log'
	log_file_mode = 0644
	EOF"
	# create the log directory and set ownership for postgres user (logging_collector needs it)
	docker exec postgres bash -c "mkdir -p /var/log/pg_log && chown -R postgres:postgres /var/log/pg_log"
	# logging_collector requires a restart to take effect
	docker restart postgres
	# wait for postgres to be ready again (max 60 seconds)
	timeout 60 bash -c 'until docker exec postgres pg_isready -U root; do sleep 1; done' || { echo "Error: PostgreSQL did not become ready within 60 seconds"; docker logs postgres --tail 50; exit 1; }
	# verify the config has been loaded
	docker exec postgres psql -U root -d nextcloud -c "SHOW log_min_duration_statement;"
	docker exec postgres psql -U root -d nextcloud -c "SHOW session_preload_libraries;"

App-side (what we used on 5.3.x)

it would be nicer if the logs are from 5.4.0 so the lines can be co-related easily.
there were a lot of changes in the app in this new version.

With Selective Context (a scoped provider), retrieval can return 0 documents for a user whose indexed chunks are only a small fraction of a large collection; users with small corpora are fine.

we do a filter on user_id so the chunks searched on are all from the same user, not sure I get the issue or the finding method, maybe the docs in question were not indexed at all?

[bygadd]

hey, thanks for taking a look.

about the user_id filter — yes, it does limit the search to a single user, but in our case that still isn’t a small set. one user can have around 2.34M indexed file chunks. this is one account, files provider only; the full collection is around 10.4M chunks.

the docs themselves are indexed correctly. when the right row is actually reached, the right document comes back — for example, a specific invoice. the setup is:

ccb 5.4.0
pgvector 0.8.0
postgres 17

the issue seems to be only the vector-search step when the scope is a very large single-user set.

doc_search collects all ~2.34M in-scope chunk ids and then _similarity_search runs the query in batches of PG_BATCH_SIZE 50k:

where collection_id = :c
  and id = any(:batch_ids)
order by embedding <=> :q
limit :k

we spent most of today trying to find a way to keep this exact, but also make it fast enough at this size. all three attempts below are variations on how that batched query in _similarity_search runs (patches in our fork, in case it’s useful).

first, we forced the id filtering through the primary-key btree before calculating distance, using a materialized CTE (patch). that avoids the planner picking the lossy HNSW + post-filter plan. this is exact, and it works fine for smaller scopes — around 6k ids was about 720ms here. but at ~2.34M ids it becomes a brute-force distance scan over the filtered set, so it runs into statement_timeout, then QueryCanceled, then the doc search error from vectordb (Error: performing doc search in vectordb). so it’s correct, but not usable for this kind of user size.

next we tried using HNSW and filtering in the app (patch). for large scopes, we drop the SQL id filter, run a plain vector search with HNSW, then keep only ids that are in the user scope and take the nearest k. performance is much better — top 200 was around 79ms, top 10000 around 757ms — but it’s only approximate. it only sees the global top N results, so if the relevant in-scope document is below that cutoff, it gets missed.

we also tried hnsw.iterative_scan = strict_order (patch), which is the cleanest-looking change. it lets us keep the original batched logic, and at first glance it looked like exactly what we wanted. but it broke a real query for us: a files-scoped “last invoice from X” question that the other approaches answered correctly started returning “i don’t know”.

from what I can tell, when the batch plan uses HNSW, iterative scan still only visits around max_scan_tuples global-nearest rows before applying the id-list filter. with the default 20000 and a small in-scope fraction, the invoice chunk can simply be outside that window. so it ends up having the same approximation problem, just through the planner instead of through app-side filtering. and bumping max_scan_tuples doesn’t really save it — to be reliable for a small in-scope fraction it has to visit most of the index, which just puts us back in the slow O(n) case.

for now we went back to a mixed approach:

exact materialized CTE up to around 50k ids
HNSW + app-side filtering above that

that’s the only version we found that doesn’t time out for users with millions of chunks. it does mean accepting approximation for huge scopes, but the invoice query that regressed with iterative scan returns the right document again.

my take is that with the current chunk-id-list filter, we can’t really get both exact and fast for a huge single-user scope. exact search means scanning the whole in-scope set, which is O(n). anything HNSW-based ranks globally first and filters afterwards, so it can miss relevant scoped results when the scope is only a small fraction of the collection.

the proper fix is probably to put the scope directly on the embedding table — provider, user, access scope, or something similar — so HNSW can filter during the scan instead of us passing millions of ids and post-filtering. bigger change, but it should avoid both the zero-result cases and the timeouts.

wdyt?

I can attach the 5.4.0 container log and db auto_explain output if that helps. just let me know what user size / query shape would be useful for a repro.

(Disclosure: investigated and verified on a live deployment, with AI assistance.)

[kyteinsky]

I thought I had replied, sorry for the delay.
I don't have such a large corpora at hand so yes, would be nice to look at the container logs and auto_explain queires to see when exactly the scan switches and how the planning takes place.

the proper fix is probably to put the scope directly on the embedding table — provider, user, access scope, or something similar

it's a little out of our hands since that table is mananged by langchain-postgres but maybe we would need to take over the management to improve performance here at some point.
let's first have a look at the logs before we can settle on a particular fix and tradeoff.