Fast typeahead search with Milvus

Website visitors and application owners alike expect near-instant feedback, especially when typing in a search bar and receiving recommendations. Type "iph" into a big retailer's search box and you'll see "iphone 17", "iphone case" and "iphone charger" before you've lifted your finger. The suggestions tend to be the popular ones, and they arrive between keystrokes. If they don't, the user has typed another character and your response is already stale.

A team I work with runs typeahead on a dedicated search engine today, alongside Milvus for vector search. Their target is under 50ms from keystroke to suggestions. They asked a fair question: can Milvus do the typeahead too, and save them running a second engine?

Milvus is best known as a vector database, but it also has scalar indexes, text analysers, BM25 and, as of 3.0, ORDER BY in plain queries. That gives you several plausible ways to build typeahead. I tested them all on Milvus 3.0.2 running in Zilliz Cloud to find out which ones return the right answer and at what speed.

TL;DR: keep a lowercased copy of each suggestion in a VARCHAR field with an NGRAM index. Query it with LIKE "prefix%" and sort by a popularity field. That returned exactly the right top 10 every time, with a p95 of about 4ms measured at the client. That's under 1ms slower than fetching a single row by primary key, and a single 1 CU performance-optimised cluster held that up to about 1,600 requests per second.

What typeahead actually needsPermalink to this heading#

Search engineers will recognise the requirements, but it's worth being explicit because they rule out a lot of options:

• Prefix matching. "sam" should match "samsung tv". Most full-text machinery matches whole tokens, so "sam" matches nothing.
• Word-start matching (sometimes). "tv" matching "samsung tv" is useful. Whether it's required depends on the product.
• Ranking by something other than relevance. Every candidate matches the prefix equally well. What decides the top 10 is popularity: query frequency, clicks or sales.
• Case and accent insensitivity. People type "IPH", "iph" and "Iph".
• Speed. The budget is tens of milliseconds end to end, including network and browser time.

Dedicated engines solve this with completion suggesters or edge n-gram analysers. Milvus doesn't have a completion suggester so the question becomes which of Milvus's other building blocks can stand in.

The candidatesPermalink to this heading#

I gave each approach its field and index in a single collection:

Filter-only approaches used query() with order_by_fields=["popularity:desc"] and limit=10, so no vector search is involved at all.

Correctness firstPermalink to this heading#

There's no point benchmarking a query that returns the wrong rows, so the first pass was a capability test. I ran ten deliberately awkward probe terms ("iPhone 15 Pro Max", "Sony WH-1000XM5", "Crème brûlée torch", "耳机 蓝牙" and so on) against 36 combinations of approach and query. Then I compared the results with ground truth computed in Python.

The analysed-text approaches fell at the first hurdle. text_match, phrase_match and BM25 tokenise the stored text into whole words, so "iph" never matches "iphone". They only returned the right rows when the typed characters happened to be a complete word, such as "usb" or "15". Fuzzy matching doesn't rescue this: it corrects a typo within a whole token, it doesn't complete a partial one.

Everything that matches on characters rather than tokens passed: every LIKE "p%" variant, the client-side edge n-grams and the prefix array. Two details matter:

• LIKE is case-sensitive. Store a normalised copy of the text (lowercased, Unicode-normalised, whitespace collapsed) and apply the same normalisation to what the user types. Among the approaches that passed, only the edge n-gram field with a lowercase filter in its analyser was case-insensitive without client-side normalisation.
• Typo tolerance is weak at typeahead lengths. Fuzzy matching on edge n-grams recovered swapped characters, but at 3 characters it also returned plenty of noise. It only became reliable from about 5 characters.

LatencyPermalink to this heading#

For the benchmark I loaded 10,000 realistic e-commerce search terms and a simulated 'popularity' numeric field:

• Cluster: Milvus 3.0.2 on a single 1 CU Zilliz Cloud cluster.
• Queries: prefixes of 3 to 6 characters, sampled by popularity so common prefixes come up often, as they do in real traffic.
• Load: a steady 20 requests per second, open loop, so queueing shows up as latency.
• Client: an EC2 instance in the same AWS region as the cluster, with a TCP round trip of about 1.6ms.
• Duration: 60 seconds per configuration after a warm-up, 180,000 requests in total.

For a floor, I measured the minimum round-trip latency by fetching a single row by primary key at the same rate: 3.1ms at p50 and 3.5ms at p95.

Nearly every approach lands within a millisecond of that floor, whichever index it uses and however many characters are typed. The NGRAM field with LIKE "p%" had a p95 of 3.7 to 4.0ms, and the edge n-gram field was 3.8 to 3.9ms. BM25 search took about half a millisecond longer. Vector ranking with a LIKE filter was the slowest at 4.7 to 5.8ms, still far inside the budget. There were no errors across all 180,000 requests.

Speed is easy, the right top 10 is harderPermalink to this heading#

If latency were the only criterion, you could pick almost anything. So I also checked every response against the expected top 10: every term matching the prefix, sorted by popularity. This is where the approaches separate.

• LIKE "p%" with ORDER BY returned exactly the right top 10, in the right order, on 100% of requests, on every index type.
• Word-start matching was also 100% correct with the NGRAM field (LIKE "p%" or LIKE "% p%"), the edge n-gram field and the prefix array. The edge n-grams only do word starts, though. Typing "tv" returns anything with a word starting "tv", so against a strict whole-string expectation they scored lower.
• Infix LIKE "%p%" matches the middle of words ("pho" finds "headphones"). That's usually not what someone typing expects.
• BM25 ranks by term statistics, not popularity, so it almost never produced the expected top 10. Fetching 100 results and re-sorting by popularity only got about half of them right.
• Vector ranking was right 89 to 96% of the time. The search is approximate, so neighbouring popularities occasionally swap places.

What I'd recommendPermalink to this heading#

For most catalogues, one normalised VARCHAR field with an NGRAM index covers both whole-string and word-start completion. Create the collection like this:

from pymilvus import MilvusClient, DataType

client = MilvusClient(uri=ZILLIZ_URI, token=ZILLIZ_TOKEN)

schema = client.create_schema(auto_id=False, enable_dynamic_field=False)
schema.add_field("id", DataType.INT64, is_primary=True)
schema.add_field("suggestion", DataType.VARCHAR, max_length=512)    # shown to the user
schema.add_field("suggest_norm", DataType.VARCHAR, max_length=512)  # normalised copy for matching
schema.add_field("popularity", DataType.INT64)                      # what decides the top 10
schema.add_field("placeholder_vec", DataType.FLOAT_VECTOR, dim=2, nullable=True)  # Milvus requires one

index_params = client.prepare_index_params()
index_params.add_index(field_name="suggest_norm", index_type="NGRAM", min_gram=2, max_gram=3)
index_params.add_index(field_name="popularity", index_type="STL_SORT")
index_params.add_index(field_name="placeholder_vec", index_type="AUTOINDEX", metric_type="IP")

client.create_collection("typeahead", schema=schema, index_params=index_params)

Then query it on each keystroke, after normalising the input the same way as the stored text:

hits = client.query(
    "typeahead",
    filter=f'suggest_norm like "{prefix}%"',
    # word starts too: f'suggest_norm like "{prefix}%" or suggest_norm like "% {prefix}%"'
    limit=10,
    order_by_fields=["popularity:desc"],
    output_fields=["suggestion"],
    consistency_level="Bounded",
)

Escape %, _ and \ in the user's input before building the filter, as you would for any LIKE. Also note that the NGRAM index is only used when the typed text is at least min_gram characters long. Shorter input falls back to a full scan, so either start querying at 2 or 3 characters or set min_gram to match.

If you need matching to ignore case on the server, or want every typed word to match ("sony wh" → "sony wh-1000xm5"), use the client-side edge n-gram field instead. Its analyser is {"tokenizer": "whitespace", "filter": ["lowercase"]}, and you AND one text_match per typed word. You pay for it with a larger field and some extra work at write time.

Ties need a tiebreaker. Popularity scores repeat, especially in the long tail, and Milvus breaks ties in no particular order. In an earlier 100,000-term run, 0.7% of responses listed tied suggestions in a different order from my ground truth. The results were still correct, just not stable between calls. Add a second sort key if the order must be stable: order_by_fields=["popularity:desc", "id:asc"].

No popularity signal? You still need an ORDER BY. Without one, Milvus returns matches in storage order, which is arbitrary and can change after compaction. Sorting by an integer length field and then alphabetically (order_by_fields=["term_len:asc", "suggest_norm:asc"]) puts "iphone" ahead of "iphone 15 pro max case", which is a reasonable default. Deriving popularity from search logs is better still.

How far does 1 CU go?Permalink to this heading#

A few milliseconds at 20 requests per second says nothing about capacity. So I loaded 100,000 terms and ramped the recommended query from 100 QPS, adding 100 QPS every minute, up to 2,000 QPS. It ran on the same 1 CU cluster, with 7 load-generating processes on an in-region c7i.2xlarge.

All 1.26 million requests succeeded, and every step sustained its target rate, up to 2,000 QPS. But the shape of the curve matters more than the pass mark:

• Up to about 1,600 QPS, latency is improves with throughput. p50 sits around 3ms and p99 stays under 5ms.
• From 1,700 QPS the tail climbs. p99 latency increases to almost 50ms at 2,000 QPS, at this point we're still within budget but the cluster is queueing requests and it's probably time to scale up for the demand.
• The client wasn't the limit. The test machine CPU peaked at 15% and requests were submitted on schedule to within 1ms at p99.

So for this query shape, one CU serves roughly 1,500 QPS with a p99 under 5ms. That's a lot of typeahead: at a request per keystroke, it's hundreds of people typing at the same moment.

CaveatsPermalink to this heading#

• 100,000 rows is still modest. Correctness doesn't change with scale, but latency and capacity can. ORDER BY sorts every match before taking the top 10, so a broad three-character prefix on a catalogue of millions will cost more than it does here. Test at your real size.
• The capacity figure is for one query shape. The ramp used whole-string prefixes of 3 to 6 characters, weighted towards popular terms. Word-start queries, bigger result sets or concurrent writes would all need further benchmarking.

Nothing here needed a vector search, a second engine or an exotic index. If Milvus is already in your stack for vectors, the typeahead can live next to them, in the same collection, answering in a few milliseconds.

ReproducePermalink to this heading#

I've open sourced the benchmarking methodology on GitHub so you can try it yourself.