Design Semantic Search for a Product Catalog

An online marketplace lists 200 million products from thousands of sellers. Its keyword search handles "XR-200 boots" well but fails on queries like "rainproof shoes for mountain walks" or "gift for a coffee lover under $40", because the words in the query do not appear in the listing.

Design a search service that understands meaning using embeddings, keeps the precision of keyword search for brands, model numbers and exact phrases, applies hard filters such as price, category, delivery region and stock exactly, and reranks the best candidates. Prices and stock change constantly and new listings arrive all day, so results must stay fresh.

In 45 minutes, size the indexes, design the query path and the indexing path, and go deep on fusing the two retrieval methods, filtering inside nearest-neighbour search, freshness, and reranking within the latency budget.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · AI & ML Systems · problem 45 of 70

Ask before you design. Try answering each yourself, then compare.

1. How big is the catalogue and how fast does it change?
   Typical answer

   200 M products; ~5 M price or stock updates and ~1 M new listings per day.

2. What traffic and latency?
   Typical answer

   ~10 k queries/s average, 30 k/s at peak; p99 under 200 ms end to end, with ~60 ms for retrieval.

3. Are filters hard or soft?
   Typical answer

   Hard: a result outside the price range, out of stock or not deliverable to the user must never appear.

4. How fresh must results be?
   Typical answer

   Price and stock within seconds; new listings searchable within 10 minutes.

5. Which languages?
   Typical answer

   English first; multilingual later.

6. Is personalisation in scope?
   Typical answer

   Only light signals in the reranker; no full recommendation system.

7. How is quality measured?
   Typical answer

   Offline NDCG on human-judged queries, then online A/B tests on clicks and purchases.

Requirements

Functional

• Search by free text with hybrid keyword and semantic retrieval.
• Apply exact hard filters (price, category, stock, ship-to region) and sorting options.
• Rerank the top candidates using relevance and business signals.
• Reflect price and stock changes within seconds and new listings within minutes.
• Log queries, impressions and clicks for evaluation and ranker training.

Non-functional

• p99 < 200 ms end to end, retrieval < 60 ms.
• 30 k queries/s at peak, 99.95% availability.
• Zero filter violations in results.
• Embedding model upgrades without downtime.

Out of scope

• Ads and sponsored placement.
• Autocomplete.
• Image search.

Back-of-the-envelope estimates

• Vectors: 200 M × 768 dims × 4 bytes ≈ 614 GB raw. With product quantization to ~96 bytes per vector that is ~19 GB, plus ~26 GB of graph links: ~45 GB per full copy. Full-precision vectors stay on SSD for rescoring.
• Sharding: 8 shards by product ID → ~6 GB of index per shard in memory. 30 k queries/s × 8 shards = 240 k shard queries/s; at ~2 k per replica, ~120 vector replicas.
• Keyword index: ~1 KB of text per product → an inverted index of roughly 80 GB, sharded the same way.
• Query encoding: 30 k/s through a small encoder on GPUs with micro-batching; a cache of head queries absorbs ~40%.
• Reranking: a cross-encoder on 100 candidates × 30 k/s = 3 M pairs/s, too costly. A distilled reranker on the top 50 at ~20 k pairs/s per GPU still needs ~75 GPUs, which makes reranking depth the main cost dial.
• Updates: 5 M price/stock changes/day is only ~60/s on average: small, but must bypass re-embedding.

API

GET /v1/search?q=rainproof+mountain+boots&price_max=150&category=footwear
              &ship_to=US&in_stock=true&page_token=...
  -> {query_id, results:[{product_id, title, price, score}], next_page_token}
POST /v1/catalog/events {product_id, op: upsert|delete, fields, version}   # internal

Every response returns a query_id that the client sends back with clicks and purchases; those logs are the raw material for evaluating and training the ranker, so the ID is part of the contract.

Data model

Catalogue (source of truth, relational): products, sellers, prices, inventory. Changes leave through change data capture.

Search document built by the indexer: (product_id, title, description, attributes, category, embedding, popularity, version).

Vector index: graph-based approximate nearest-neighbour index with quantized vectors, sharded by product ID hash, with a filter bitmap per common attribute value.

Keyword index: inverted index over text fields, sharded the same way so both retrievers can filter on the same attributes.

Price/stock store: key-value by product_id, read at query time so fast-changing fields never wait for an index rebuild.

High-level design

Query path. The shopper’s request reaches the search API, then query understanding, which fixes spelling, extracts structured filters ("under $150" becomes price_max), and sends the text to the query encoder on GPUs for an embedding (or reads it from a cache for popular queries). The hybrid retriever fans out in parallel to all shards of the vector index and the keyword index, each applying the same hard filters and returning ~200 candidates. It merges the two lists with rank fusion, checks current price and stock in the price/stock store and drops anything that no longer qualifies, then sends the top 100 to the reranker, which scores query-product pairs with a cross-encoder plus business features. The API returns the top results with a query ID.

Indexing path. Changes in the catalogue DB flow through the catalogue changes stream to the indexer. For new or edited text it calls the document embedder, then upserts into both indexes. Price and stock changes go only to the price/stock store and the filter attributes, without re-embedding.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

Fusing keyword and vector retrieval

Keyword search wins on exact tokens: brand names, model numbers, sizes. Embeddings win on intent and paraphrase. Run both in parallel and merge. Raw BM25 scores and cosine similarities live on different scales, so reciprocal rank fusion, which sums 1/(k + rank) across lists, is a robust default that needs no calibration. Later, replace it with a learned blend trained on click logs. A lightweight query classifier can shift the weight: a query that looks like a SKU leans on keywords, a long descriptive query leans on vectors. Deduplicate variants of the same product before reranking.

Filters inside nearest-neighbour search

Filtering after retrieval fails for selective filters: if only 0.5% of products match "size 13, wide, in stock, ships to Alaska", the top 200 neighbours may contain none of them. Instead, pass a filter bitmap into the graph traversal so it only collects matching nodes while still walking through non-matching ones. When the filtered set is small, say under 50 k products, skip the graph entirely and do an exact scan over that subset, which is cheap and precise. For very common filters such as top-level category, keep separate sub-indexes. The planner chooses among these by estimating filter selectivity from attribute counts.

Freshness and model upgrades

Price and stock are late-bound: stored in a key-value store and checked after retrieval, and mirrored into filter bitmaps within seconds. New and edited listings are embedded and written to a small fresh segment per shard that is searched by brute force alongside the main graph and merged into it hourly. Deletes use a tombstone bitmap until the next merge. Changing the embedding model changes every vector, and query and document vectors must come from the same model. Re-embed everything into a new index side by side (200 M documents at ~5 k/s per GPU on 20 GPUs is about 35 minutes), compare offline, then switch traffic per experiment before retiring the old index.

Reranking within budget, and evaluation

Retrieval optimises recall; the reranker optimises the order of the top results. A cross-encoder reads query and product together and is much more accurate, but costs one model call per pair, so limit it to the top 50-100 and use a distilled model. Feed its score with price, rating, return rate and click-through into a gradient-boosted ranker for the final order. If the reranker misses its deadline, return the fused order. Measure offline with NDCG@10 on human-judged queries, especially tail queries, and online with interleaving or A/B tests on add-to-cart and purchase.

Failure modes

• If the query encoder is unavailable, the retriever runs keyword-only and logs the degraded mode.
• If a vector shard is slow, the retriever returns after its deadline with results from the remaining shards plus the keyword list.
• If the reranker times out, return the fused retrieval order.
• If the indexer falls behind, the fresh segment and late-bound price/stock still keep filters correct; only new listings are delayed.

Core algorithm in code

import math
import re
from collections import Counter

CATALOG = [
    {"id": "P1", "title": "Waterproof hiking boot wide fit", "price": 129, "in_stock": True},
    {"id": "P2", "title": "Trail running shoe breathable mesh", "price": 95, "in_stock": True},
    {"id": "P3", "title": "Leather oxford dress shoe", "price": 140, "in_stock": True},
    {"id": "P4", "title": "Rain jacket waterproof shell", "price": 110, "in_stock": True},
    {"id": "P5", "title": "XR-200 hiking boots", "price": 149, "in_stock": True},
    {"id": "P6", "title": "Non-stick frying pan", "price": 35, "in_stock": True},
    {"id": "P7", "title": "Waterproof trail boot", "price": 180, "in_stock": True},
]

# Stand-in for a learned encoder: words map onto shared concept dimensions.
CONCEPTS = {"water": "waterproof rain rainproof water wet", "outdoor": "hiking trail hike mountain outdoor",
            "footwear": "boot boots shoe shoes sneaker oxford", "apparel": "jacket shell coat",
            "formal": "dress leather oxford", "kitchen": "pan frying kitchen cook"}
WORD2C = {w: c for c, ws in CONCEPTS.items() for w in ws.split()}


def tokens(text):
    return re.findall(r"[a-z0-9]+(?:-[a-z0-9]+)*", text.lower())


def embed(text):
    v = Counter(WORD2C[t] for t in tokens(text) if t in WORD2C)
    n = math.sqrt(sum(x * x for x in v.values())) or 1.0
    return {k: x / n for k, x in v.items()}


DOCS = {p["id"]: tokens(p["title"]) for p in CATALOG}
VECS = {p["id"]: embed(p["title"]) for p in CATALOG}
AVGDL = sum(len(d) for d in DOCS.values()) / len(DOCS)


def bm25(query, ids, k1=1.2, b=0.75):
    out = {}
    for pid in ids:
        doc, tf, s = DOCS[pid], Counter(DOCS[pid]), 0.0
        for t in set(tokens(query)):
            df = sum(t in d for d in DOCS.values())
            if tf[t]:
                idf = math.log(1 + (len(DOCS) - df + 0.5) / (df + 0.5))
                s += idf * tf[t] * (k1 + 1) / (tf[t] + k1 * (1 - b + b * len(doc) / AVGDL))
        if s > 0:
            out[pid] = s
    return sorted(out, key=out.get, reverse=True)


def vector(query, ids, min_sim=0.3):
    q = embed(query)
    sims = {pid: sum(q.get(k, 0) * x for k, x in VECS[pid].items()) for pid in ids}
    return sorted((p for p in sims if sims[p] >= min_sim), key=sims.get, reverse=True)


def rrf(*rankings, k=60):
    """Reciprocal rank fusion: needs only ranks, so BM25 and cosine never need calibrating."""
    score = Counter()
    for r in rankings:
        for rank, pid in enumerate(r):
            score[pid] += 1 / (k + rank + 1)
    return [p for p, _ in score.most_common()]


def search(query, max_price=None):
    ids = [p["id"] for p in CATALOG if p["in_stock"] and (max_price is None or p["price"] <= max_price)]
    lex, vec = bm25(query, ids), vector(query, ids)   # filters applied inside each retriever
    return lex, vec, rrf(lex, vec)


for q, mp in [("rainproof mountain boots", 150), ("XR-200", None), ("waterproof boot", 150)]:
    lex, vec, fused = search(q, mp)
    print(f"query={q!r} max_price={mp}")
    print("   keyword:", lex, "\n   vector: ", vec, "\n   fused:  ", fused[:4])

Trade-offs

• Product quantization cuts index memory roughly 30× but costs some recall, recovered by rescoring with full vectors from SSD.
• Rank fusion needs no score calibration but costs the ability to weight a very confident retriever more.
• Late-binding price and stock keeps results exact but costs an extra key-value lookup per query.
• A deeper reranking window improves relevance but costs GPUs linearly and adds tail latency.
• Sharding by product ID balances load evenly but costs a fan-out to every shard per query.

What a strong answer shows

• Justifies hybrid retrieval with concrete query examples.
• Sizes the vector index and uses compression and sharding sensibly.
• Handles filtered nearest-neighbour search correctly.
• Separates fast-changing attributes from embeddings for freshness.
• Budgets reranking cost and latency with numbers.
• Defines offline and online evaluation.

Mistakes to avoid

• Replacing keyword search entirely with embeddings and breaking SKU and brand queries.
• Post-filtering nearest-neighbour results and returning empty pages.
• Re-embedding a product on every price change.
• Mixing vectors from two embedding model versions in one index.
• Running a cross-encoder over thousands of candidates per query.

Follow-ups to expect

• How would you add multilingual search? (A multilingual encoder for vectors plus per-language analysers for keywords.)
• How would you use an LLM here? (Offline: enrich listings and generate judged queries; online: only for rewriting rare long queries, cached.)
• How would you personalise lightly? (User features in the reranker, such as preferred brands and price band.)
• How do you handle zero-result queries? (Relax soft constraints in order and show what was relaxed.)

Practice next