Autocomplete with Valkey 9.0 Search

Replace a 14-second SCAN over 8M keys with sub-millisecond prefix search.

Introduction

30 Second Summary

Think about typing a product name into a search bar and waiting 14 seconds for suggestions to appear. That is the reality when an autocomplete system scans 8 million items one by one to find matches.

In this project, you will replace a slow SCAN-based autocomplete with Valkey 9.0 native full-text search, cutting response time from 14 seconds to under 1 millisecond.

What You'll Build

You type a few characters into your autocomplete endpoint and get instant, accurate results back from 8 million items without any full-collection scan.

By the end of this project, you'll have:

A search index over 8M items that auto-updates whenever new items are written. You can add a new product and immediately find it by typing its first few letters.
A prefix query that returns matching items in sub-millisecond latency. You can demo the difference live by comparing the old 14-second response against the new instant result.
An autocomplete endpoint that stays well within API Gateway timeout limits with orders-of-magnitude margin to spare.
Secret Mission: Add pagination and disable stemming artifacts for production-ready autocomplete on high-cardinality prefix matches.

Are there any prerequisites?

This project assumes you already have an ElastiCache cluster running Valkey 9.0 and a Kotlin application with an existing SCAN-based autocomplete implementation.

You also need access to valkey-cli or redis-cli to connect to the cluster. No new tools or services are required.

Before We Start

Before we dive in, let's lock in exactly what performance problem you're solving and why the current approach breaks down at scale.

Connect and Verify Valkey 9.0 Search Support

Before changing any application code, you need to confirm that your ElastiCache cluster actually supports FT.* search commands.

If the search module is not loaded, nothing else in this project works. This step connects you to the cluster and proves that Valkey 9.0 full-text search is available at no additional cost on your node-based cluster.

In this step, get ready to:

Connect to your ElastiCache Valkey 9.0 cluster via the CLI.
Confirm the search module is available by running FT._LIST.
Inspect existing hash keys to identify the key prefix and field name your index will target.

Connect to the ElastiCache Valkey cluster

Your application currently uses a SCAN-based approach that iterates over all 8 million keys to serve autocomplete results. That takes around 14 seconds per request.

Open a terminal session on a machine that has network access to your ElastiCache cluster (for example, an EC2 instance in the same VPC).
Connect to the cluster by running this command:

valkey-cli -h [[CLUSTER_ENDPOINT="your ElastiCache cluster endpoint"]] --tls -p 6379

What does this command do?

-h specifies the hostname of your cluster endpoint (found in the ElastiCache console under your cache details).
--tls enables a secure TLS connection, which ElastiCache requires for in-transit encryption.
-p 6379 sets the default Valkey port.

If your cluster uses AUTH, add -a followed by your auth token. If cluster mode is enabled, add the -c flag before -h so the client follows MOVED and ASK redirections.

You should see a prompt like your-endpoint:6379> confirming you are connected.

Connection refused or timed out?

Confirm your EC2 instance's security group allows outbound traffic on port 6379 to the ElastiCache security group.
Verify the cluster endpoint is correct in the ElastiCache console (look under your cache's details page).
If you see a TLS handshake error, make sure you included the --tls flag.

Need more help? Help me troubleshoot my valkey-cli connection to ElastiCache

Confirm search module availability

The FT._LIST command lists all existing search indexes on the cluster. If the command succeeds (even with an empty response), the search module is loaded and ready.

Before you run the next command, predict what you expect to see. Will it return results, an empty list, or an error?
Confirm the search module is available by running:

FT._LIST

You should see (empty array) as the response. This means no indexes exist yet, but the search module is loaded and ready to use.

What if I see existing indexes?

If your cluster already has indexes from previous experiments, FT._LIST returns their names instead of an empty array. That is also a success. The key signal is that the command does not return an error.

Seeing ERR unknown command?

If you receive ERR unknown command, your cluster is either not running Valkey 9.0 or the search module is not enabled. Check the engine version in your ElastiCache console. The cluster must be running ElastiCache version 9.0 for Valkey to have search available.

Still stuck? Help me verify my ElastiCache cluster supports FT.* commands

Inspect the existing hash structure

Your search index needs to know two things: the key prefix pattern your hashes use, and the field name that stores the item name. You will discover both by inspecting one of the existing autocomplete items.

Find one of your existing hash keys by running:

SCAN 0 COUNT 1

Note the key that comes back. It will follow a pattern like item:12345 or product:67890. The part before the colon is your key prefix.
Inspect that key's full structure by running:

HGETALL [[SAMPLE_KEY="one of your hash keys, e.g. item:12345"]]

The output shows alternating field names and values. Identify the field that stores the item's display name (for example, name).

What am I looking for?

You need two pieces of information from this output:

Key prefix - the common string before the colon in your key names (e.g. item:). This tells FT.CREATE which keys to index.
Name field - the hash field that holds the searchable text (e.g. name). This is the field you will index as TEXT in the next step.

Write both values down. You will use them in Step 2 when creating the search index.

SCAN returned a key that isn't a hash?

If HGETALL returns an error saying the key is not a hash type, try another key. Your cluster may contain non-hash keys as well. Run SCAN 0 MATCH item:* COUNT 1 (replacing item:* with your expected pattern) to filter for hash keys specifically.

Need help finding your keys? Help me identify the key prefix pattern in my Valkey cluster

Your connection is confirmed and you know exactly which keys and fields to target. Next up, you will create a search index that turns those 8 million hashes into a sub-millisecond prefix-searchable collection.

Create the Search Index with FT.CREATE

Your ElastiCache cluster is confirmed ready with the search module loaded. Now you can tackle the root cause of that 14-second latency.

Right now, every autocomplete query runs a SCAN across all 8M keys. That is O(N) complexity, meaning response time grows linearly with your dataset. FT.CREATE builds an inverted index over a TEXT field, enabling O(log N) prefix lookups. The index auto-backfills existing data and auto-updates on every future mutation.

In this step, get ready to:

Create a full-text search index over your existing hash data.
Verify the index is backfilling your 8M items automatically.

Create the search index targeting your hash prefix

FT.CREATE tells Valkey to build a search index over every hash key matching a prefix pattern. Once created, the index backfills all existing keys and automatically indexes new ones written via HSET.

In your valkey-cli session, create the search index by running this command:

FT.CREATE autocomplete_idx ON HASH PREFIX 1 item: NOSTOPWORDS SCHEMA name TEXT NOSTEM

You should see OK as the response. This confirms the index was created successfully.

What does this command do?

autocomplete_idx is the name you give this index. You will reference it in every future query.
ON HASH PREFIX 1 item: tells Valkey to index only hash keys that start with item:. This scopes the index to your autocomplete data.
NOSTOPWORDS prevents common words like "the" or "a" from being stripped. Product names often contain these words, so you need them searchable.
SCHEMA name TEXT NOSTEM indexes the name field as searchable text. NOSTEM disables stemming so that searching "running" does not match a product named "run".

Adapt to your key pattern

If the key prefix you identified in Step 1 is different from item:, replace it in the command above. Same for the field name if yours is not name.

Seeing an error instead of OK?

If you see an error about an existing index, it means autocomplete_idx already exists. Run FT.DROPINDEX autocomplete_idx first, then retry the FT.CREATE command.
If the error mentions an unknown command, double-check you are connected to the Valkey 9.0 cluster and not an older Redis instance.

Why is my FT.CREATE failing on ElastiCache Valkey 9.0?

Monitor the backfill progress

When you create an index, Valkey immediately starts backfilling all existing keys that match the prefix. For 8M items, this takes a few minutes depending on cluster size. Queries work during the backfill but return partial results until it completes.

Before you run the next command, what do you think the num_docs field will show? Will it already be at 8M, or still climbing?

Check the index status by running this command:

FT.INFO autocomplete_idx

You should see a large output with metadata about your index. Look for the num_docs field. If you ran this within seconds of creating the index, it will still be climbing toward 8M as the backfill progresses.

What does FT.INFO tell you?

num_docs shows how many hash keys have been indexed so far. This number increases until it reaches your total item count.
The index does not block queries during backfill. You can start searching immediately, but results will be partial until backfill completes.

Wait a minute, then run FT.INFO autocomplete_idx again to confirm num_docs has increased.

num_docs stuck at zero?

Verify the prefix in your FT.CREATE command matches the actual key pattern of your items. Run SCAN 0 MATCH item:* COUNT 5 to confirm keys exist with that prefix.
Confirm your items are hashes and not strings. Run TYPE on one of your keys. It should return hash.

Why is my Valkey search index not backfilling any documents?

Your search index is live and backfilling millions of items. Next up, you will run prefix queries against it and see the sub-millisecond response time that replaces your 14-second SCAN.

Test Prefix Search via CLI

Your search index is built and backfilling is complete. Before changing any application code, you need to prove the new approach actually delivers the sub-millisecond response it promises.

Running FT.SEARCH manually in the CLI shows you the exact behavior and response format your Kotlin code will consume. If the query is fast here, it will be fast in production.

In this step, get ready to:

Run a prefix query against your search index and confirm matching results.
Measure the response time and compare it to the old SCAN approach.
Test edge cases to confirm the index handles varying prefix selectivity.

Run your first prefix query

The core of the new autocomplete approach is a single FT.SEARCH command with a wildcard suffix. This is the O(log N) operation that replaces the O(N) SCAN.

In your valkey-cli session, run this prefix query to search for items starting with "Omeg":

FT.SEARCH autocomplete_idx "Omeg*" LIMIT 0 10

What does this command do?

This searches the autocomplete_idx index for any document whose name field starts with "Omeg". The * wildcard enables prefix matching at the index level.

The LIMIT 0 10 clause returns at most 10 results starting from offset 0. This is the default behavior, but stating it explicitly makes your intent clear.

You should see a response that starts with an integer (the total number of matching documents), followed by alternating key names and field-value arrays.

Getting an empty result or error?

If you see (integer) 0 with no results, the backfill may still be in progress. Run FT.INFO autocomplete_idx and check that num_docs is close to 8M.
If you get an unknown command error, confirm you are connected to the correct Valkey 9.0 cluster endpoint.
Try a different prefix that you know exists in your data (check with HGETALL on a known key).

help me troubleshoot my FT.SEARCH query returning no results

Compare timing against SCAN

The whole point of this migration is the speed difference. You need to quantify that the new approach is orders of magnitude faster than the 14-second SCAN.

Check the per-command execution statistics by running:

INFO commandstats

Look for the cmdstat_ft.search line. The usec_per_call value shows the average execution time in microseconds for your FT.SEARCH commands.

Run several more prefix queries with varying selectivity to build up the stats:

FT.SEARCH autocomplete_idx "Omeg*" LIMIT 0 10
FT.SEARCH autocomplete_idx "Alpha*" LIMIT 0 10
FT.SEARCH autocomplete_idx "Pro*" LIMIT 0 10

Run INFO commandstats again and check the updated usec_per_call value for ft.search.

What should I see?

The usec_per_call value should be in the hundreds of microseconds or lower. AWS benchmarks show P50 latency of 0.135ms and P99 of 0.279ms for prefix queries on comparable datasets. Compare this to the 14 seconds (14,000,000 microseconds) your SCAN takes today.

The FT.SEARCH response itself should feel instantaneous in the CLI. There is no visible wait between pressing Enter and seeing results.

Test edge cases for robustness

Your autocomplete endpoint will receive all kinds of input. You need to confirm the index handles short prefixes, impossible matches, and full-name queries gracefully.

Test a single-character prefix (high cardinality) by running:

FT.SEARCH autocomplete_idx "O*" LIMIT 0 10

This matches many items but still returns only 10 thanks to the LIMIT clause. The total count (first element) shows how many documents match overall.

Test a prefix that matches nothing:

FT.SEARCH autocomplete_idx "zzzzz*" LIMIT 0 10

You should see (integer) 0 with no results. This confirms the index handles misses cleanly without errors.

Test a full name match to confirm exact-prefix behavior:

FT.SEARCH autocomplete_idx "OmegaWear*" LIMIT 0 10

Why test these edge cases?

Single-character prefixes like "O*" could match hundreds of thousands of items. Without the LIMIT clause, FT.SEARCH defaults to returning at most 10 results. Your application code must handle the total count separately from the returned page.

The empty-result case confirms your API won't error when users type something that does not exist. The full-name case proves the prefix query narrows correctly as the user types more characters.

Before you move on, do you think the response format will need special parsing in your Kotlin code, or does it map directly to a list of names?

Look at the full response from any of your queries above. Notice the structure: the first element is the total count (a Long), followed by pairs of key name and field-value array.

Your Kotlin code will need to parse this alternating structure to extract the name values. Each result is a pair: the hash key (e.g. item:12345) followed by an array like ["name", "OmegaWear Pro"].

Seeing unexpected results?

If results contain items that don't seem to start with your prefix, remember that TEXT fields tokenize on whitespace. A search for "Pro*" matches any item where ANY word in the name starts with "Pro" (e.g. "Ultra ProMax").
If you need the prefix to match only the beginning of the full field value, you would need a TAG field type instead. For most autocomplete UX, the TOKEN-level prefix matching from TEXT fields is the correct behavior.

help me understand FT.SEARCH prefix matching behavior on TEXT fields

You have confirmed that FT.SEARCH delivers sub-millisecond prefix queries over 8M items. The response format is clear and the edge cases behave predictably. Next up, you will replace the SCAN-based code in your Kotlin application with this exact FT.SEARCH call.

Replace SCAN with FT.SEARCH in Kotlin

You proved in the CLI that FT.SEARCH delivers sub-millisecond prefix results over 8 million items. The index works. The query syntax works. Now it is time to bring that performance into your actual application code.

In this step, you will replace the SCAN-based autocomplete function in your Kotlin codebase with an FT.SEARCH call. This is the change that eliminates the 14-second response time and keeps your endpoint safely within the API Gateway timeout limit.

In this step, get ready to:

Replace the SCAN logic with an FT.SEARCH command call.
Parse the FT.SEARCH response into your existing response DTO.
Deploy and confirm the endpoint responds under 1 second.

Replace the SCAN logic with FT.SEARCH

Your current autocomplete function iterates through keys using SCAN with a match pattern. This is O(N) over the entire keyspace. The replacement sends a single FT.SEARCH command that leverages the inverted index you created.

Locate the function in your Kotlin codebase that implements autocomplete using the SCAN command with a filter.
Replace the SCAN loop with a call to ftSearch. The command your client sends translates to:

FT.SEARCH autocomplete_idx "<userInput>*" LIMIT 0 <maxResults> RETURN 1 name

Using Jedis (or any JVM client that wraps it), the Kotlin call looks like this:

// Replace the SCAN-based loop with a single FT.SEARCH call
val result = jedis.ftSearch(
    "autocomplete_idx",
    "${userInput}*",
    FTSearchParams.searchParams()
        .returnFields("name")
        .limit(0, maxResults)
)

What does this code do?

The ftSearch call sends an FT.SEARCH command to Valkey. The query "${userInput}*" performs a prefix match on the indexed name field.

The RETURN 1 name clause (expressed as .returnFields("name")) ensures only the name field comes back, minimizing network payload. The LIMIT 0 <maxResults> caps the number of results returned.

Why Jedis and not a raw command?

Jedis, Lettuce, Valkey GLIDE, and valkey-java all support FT.* commands. Jedis provides a native ftSearch method with typed parameters. If you use a different client, send the command as a raw string array or use that client's custom-command API.

Parse the FT.SEARCH response

The Jedis SearchResult object gives you a typed response. You need to extract the name values and map them into your existing autocomplete response DTO.

Add the response parsing logic after the ftSearch call:

// Extract name values from the search result
val totalCount = result.totalResults
val names = result.documents.map { doc ->
    doc.get("name") as String
}

// Return names in your existing response DTO
return AutocompleteResponse(names)

What does this code do?

result.totalResults gives you the total number of matching documents (useful for pagination later).
result.documents returns a list of Document objects, each representing a matching hash key.
doc.get("name") extracts the name field you requested via RETURN 1 name.

Using a raw command client instead?

If your client returns the raw response array, the format is: first element is the total count (Long), followed by alternating key names (String) and field-value arrays. Parse by stepping through the array in pairs starting from index 1.

Save your changes and rebuild the project.

Deploy and test the updated endpoint

The code change is done. Now you need to confirm that the endpoint returns correct results at the speed you expect.

Deploy the updated application to your environment.
Before you call the endpoint, predict: do you expect the response time to be closer to 14 seconds (the old SCAN time) or under 1 second?
Call your autocomplete endpoint with a test prefix. For example:

curl -w "\nTime: %{time_total}s\n" "https://your-api-endpoint/autocomplete?q=Omeg&limit=10"

You should see correct matching results returned in under 1 second. The time_total value confirms the latency has dropped from 14 seconds to sub-second.

Test with multiple prefixes to confirm consistency: try a selective prefix like "Omeg", a broad single-character prefix like "O", and an empty-result query like "zzzzz".
Verify the results match what the old SCAN-based endpoint returned for the same prefixes.

Why does this stay within API Gateway limits?

API Gateway REST APIs have a maximum integration timeout of 29 seconds. Your old SCAN approach at 14 seconds was dangerously close and would breach the limit as data grew. The FT.SEARCH approach responds in milliseconds, leaving orders-of-magnitude margin.

Endpoint still slow or returning errors?

Confirm your application is actually calling ftSearch and not falling through to the old SCAN code path. Add a log line before the ftSearch call to verify it is reached.
Check that the index name autocomplete_idx in your Kotlin code matches the index you created in the CLI exactly.
If you see an error about an unknown command, ensure your Jedis (or other client) version supports FT.* commands and is connecting to the correct Valkey 9.0 endpoint.

Help me debug why my FT.SEARCH call is not working from Kotlin.

Your autocomplete endpoint now responds in under a second instead of 14. The FT.SEARCH index handles the heavy lifting at O(log N), and the RETURN 1 name clause keeps the response payload minimal. Next up, you will add pagination and verify stemming behavior for production-grade autocomplete.

Secret mission

Add Pagination and Disable Stemming Artifacts

In production with 8M items, a short prefix like "A*" could match millions of results. Without pagination, FT.SEARCH returns only the default 10. Your API consumers need controlled pagination, and you need to ensure stemming does not produce unexpected matches. Can you add offset/limit parameters and verify stemming-free exact prefix matching?

Clean Up Your Resources

Decide whether to keep the search index running, revert it, or remove it entirely. This project uses your existing ElastiCache infrastructure, so there are no ongoing costs beyond what you already pay for the cluster.

Resources you used:

Search index autocomplete_idx on your ElastiCache Valkey 9.0 cluster.
Kotlin autocomplete endpoint code changes (FT.SEARCH replacing SCAN).

Keep everything running

No action needed. Choose this if you are still actively building on the autocomplete feature or want to keep the performance improvement in place.

The autocomplete_idx index stays active and auto-updates whenever you write new hashes with the item: prefix.
Your Kotlin endpoint continues serving sub-millisecond autocomplete results.
No additional cost. The search index runs on the same ElastiCache nodes you already pay for.

Pause - I'll come back to this later

Keep the index definition but revert your application code so the endpoint stops using FT.SEARCH while you work on other things.

Revert the Kotlin autocomplete function to the previous SCAN-based implementation using your version control (e.g. git checkout or git revert).
Leave the autocomplete_idx index in place. It consumes memory on the cluster but incurs no separate billing.
When you return, re-deploy the FT.SEARCH-based code and the index will already be up to date.

Delete - I don't want to use this again

Remove the search index and revert your code changes to start fresh.

Drop the search index by running this command in valkey-cli:

FT.DROPINDEX autocomplete_idx

What happens to my data?

Dropping the index only removes the index definition and its internal data structures. Your underlying hash keys (the 8M items) are unaffected.

Confirm the index is gone by running:

FT._LIST

You should see an empty array or a list that no longer includes autocomplete_idx.

Revert the Kotlin autocomplete function to the previous SCAN-based implementation using your version control (e.g. git revert on the commit that introduced FT.SEARCH).
Re-deploy the reverted application code.

Nice Work!

You just transformed a 14-second autocomplete endpoint into a sub-millisecond query by replacing a full-collection SCAN with Valkey 9.0 native full-text search. Your 8 million items are now instantly searchable without a single extra service or dollar of infrastructure cost.

You've learned how to:

Replace an O(N) SCAN over 8M keys with an O(log N) FT.SEARCH prefix query that responds in under 1ms.
Create a Valkey 9.0 search index with FT.CREATE that auto-syncs with existing hash data on every mutation.
Eliminate API Gateway timeout failures by bringing autocomplete latency from 14 seconds down to sub-millisecond.
Secret Mission: Added paginated results with LIMIT and SORTBY, and verified NOSTEM prevents stemming artifacts for production-ready exact prefix matching.

Ready to quiz yourself?