Vector Search hard
An e-commerce search service holds 50M product vectors in an HNSW index. A common query applies the filter `in_stock AND region=EU AND category=X`, which matches about 0.2% of the corpus. The service asks the ANN index for the top 100 and then applies the filter, and it often returns 0 to 3 products. Which design fixes this most reliably?
- A Oversample by raising k to 1,000 before filtering; a 10x oversample leaves plenty of matches for a 0.2% filter.
- B Rebuild the HNSW graph with a higher M so each node has more edges, raising recall and surfacing more matches.
- C Pre-filter or use filter-aware traversal, with an exact flat scan when the match set is small.
- D Retry the ANN query with exponentially larger k until at least 10 filtered matches come back, then return those.
Answer: C. Pre-filter or use filter-aware traversal, with an exact flat scan when the match set is small.
**Post-filtering** keeps only 0.2% of candidates, so even k=1,000 yields about 2 expected matches. The filter has to shape the search itself. The matching subset is about 100K vectors, so an exact **flat scan** of it is cheap, and **filter-aware traversal** handles moderately selective filters. Oversampling followed by a post-filter is the right call only when the filter is permissive (say, half the corpus matches), because then it stays simple and fast.
One system design question a day, with spaced repetition so the ones you miss come back.
Get the appRelated questions
- You are building an IVF index on 20 million vectors. A teammate asks why the build needs a 'training' step before any vectors can be added. What is the reason?
- An HNSW index serves a marketplace where about 30% of listings are updated or removed each week. Each update is applied as a delete plus an insert, and deletes mark tombstones. Over a month, recall@10 drifts from 97% to 89% and p99 latency rises at the same ef_search. What is happening, and what should you do?
- Users delete documents in your primary database, but the deleted documents keep appearing in vector search results for hours. The vector index is rebuilt nightly. What is the best fix?
- Your embedding model outputs unnormalized vectors whose magnitudes vary widely. A teammate wants to switch the index from cosine similarity to dot product because it is cheaper to compute. What is the consequence?
- You are setting an SLO for a new ANN-backed recommendation search over 50 million vectors. A product manager asks for 100% recall@10 with single-digit millisecond latency. What is a realistic response?
- A B2B SaaS app serves 500 customers, and every query searches only one customer's documents. One large customer runs heavy batch queries that slow down search for everyone. Which sharding approach fits best?