Serverless search: an inverted index in DynamoDB

In the first article in this series I set out a problem that most substantial web applications eventually meet: a large collection of records - let's say a million - a user who needs to find the ones mentioning a particular string, and a strong preference for not paying for a search cluster around the clock to make that possible. This article works through the first of the five strategies, which is to build the search index ourselves, inside DynamoDB.

DynamoDB might seem a strange place to start, because it has no full-text search capability of any kind. What it does have is a talent that no other AWS service can match: given a key, it will return the items stored under that key in single-digit milliseconds, at any scale, priced per request. That one strength turns out to be all we need, provided we're willing to arrange our data around it.

Why not just scan the table?

The tempting first answer is a Scan with a filter expression, and it's worth understanding exactly why that doesn't work before building something better. A DynamoDB scan reads every item in the table and applies your filter afterwards, which means you are billed for reading every item whether it matches or not, and the results arrive in 1 MB pages, so a million small items means around a thousand sequential round trips before you have an answer. Parallel scans spread those reads across workers, but they spend exactly the same read units, just faster. At current on-demand prices the reads for one scan of a table this size come to a few cents, so at this scale the cost alone won't frighten anyone; the trouble is that a search taking tens of seconds is no use behind a search box, that both the time and the cost grow linearly as the table grows, and that every concurrent user multiplies both. We need the answer to come from a key lookup instead.

Turning the documents inside out

The arrangement that makes "which documents contain this word?" answerable with a single key lookup is called an inverted index, and it's the structure every serious search engine, Elasticsearch included, is built upon. The idea is to store a list of documents against each word, rather than storing words inside each document, so that the word itself becomes the key you query.

Building one starts with tokenisation. When a document is written, we break its text into words, lowercase them, strip the punctuation, and drop the stopwords - "the", "and", "of" and the other small words that appear in every document and help nobody find anything. Search engines often apply stemming at this stage too, reducing "running", "runs" and "ran" to a shared root so they all match one another. What remains is the document's set of distinct terms, and for each of those terms we write one item into the index, an item traditionally called a posting. That's one item for each distinct term rather than one for every word, which is a distinction worth pausing on. If document doc42 contains the text "the cat sat on the cat mat", tokenisation leaves the terms "cat", "sat" and "mat", and we write three postings, not seven:

term      docId      count    positions
"cat"     "doc42"    2        [1, 5]
"sat"     "doc42"    1        [2]
"mat"     "doc42"    1        [6]

The repeated "cat" hasn't produced a second item; it has become a count of 2 inside the single "cat" posting, along with the positions where it appeared, and both of those attributes will earn their keep when we come to ranking. A simple tokeniser needs very little code:

const STOPWORDS = new Set(["the", "a", "an", "and", "of", "on", "in", "to", "is"]);

function tokenise(text) {
    const postings = new Map();
    const words = text.toLowerCase().replace(/[^a-z0-9\s]/g, " ").split(/\s+/);

    words.forEach((word, position) => {
        if (word === "" || STOPWORDS.has(word)) return;
        if (!postings.has(word)) {
            postings.set(word, { count: 0, positions: [] });
        }
        const posting = postings.get(word);
        posting.count += 1;
        posting.positions.push(position);
    });

    return postings;
}

The table design

The index table has a partition key of term and a sort key of docId, with the count and positions carried as ordinary attributes. Indexing a document means running its text through the tokeniser and writing the resulting postings, which BatchWriteItem will take twenty-five at a time. The consequence of this layout is the whole point of the exercise: every document that mentions "cat" writes its own posting under the same partition key, so the postings for any given term sit together in one item collection, and retrieving all of them is a single Query.

const { DynamoDBClient } = require("@aws-sdk/client-dynamodb");
const { DynamoDBDocumentClient, QueryCommand } = require("@aws-sdk/lib-dynamodb");

const client = DynamoDBDocumentClient.from(new DynamoDBClient({}));

const result = await client.send(new QueryCommand({
    TableName: "search-index",
    KeyConditionExpression: "#term = :term",
    ExpressionAttributeNames: { "#term": "term" },
    ExpressionAttributeValues: { ":term": "cat" },
}));

// result.Items now holds a posting for every document containing "cat"

Searching a million documents for "cat" has become a point lookup that returns exactly the matching document IDs, in a handful of milliseconds, having read only the postings for that one term. The million documents that don't mention cats cost us nothing at all.

Searching with more than one word

A real search is usually a phrase like "cat mat", and the index handles this with one query per term - fired in parallel with Promise.all - followed by an intersection of the document IDs in your Lambda function, since a document matching both terms appears in both result sets. The counts give you a serviceable ranking, as a document mentioning "cat" five times is probably a better result than one mentioning it once, and the positions allow genuine phrase matching: if "cat" appears at position 5 and "mat" at position 6 in the same document, the exact phrase "cat mat" is present. This is a long way from the sophisticated relevance scoring of a dedicated engine, but for finding records in your own application it goes a surprisingly long way.

Autocomplete and fuzzier matching

Two extensions are worth knowing about. The first is autocomplete, which needs a bit of thought, because our partition key only matches whole terms and you can't query "every term beginning with ca" against it. The usual answer is a second, much smaller item collection alongside the postings: one item per distinct term in the whole index, stored under a partition key of the term's first letter or two and a sort key of the full term, so that a Query with begins_with(term, "ca") returns the completion candidates for a search box as the user types.

The second extension is fuzzy matching. If you tokenise each term further into trigrams - overlapping three-letter fragments, so "cat" and "cart" share "car" and "art" via their fragments - and index those fragments as terms in their own right, then a misspelt search still lands on most of the right fragments, and the documents sharing the most fragments with the query rise to the top. Trigram indexing multiplies the size of the index considerably, so I'd reach for it only when the search box genuinely needs to forgive typos.

Keeping the index fresh

An index you have to rebuild by hand is an index that will quietly rot, so the last piece of the design is DynamoDB Streams, which turns the maintenance into an event-driven side effect. With a stream enabled on the documents table and a Lambda function subscribed to it, every insert, update and delete arrives as an event carrying the old and new versions of the record. On an insert, the function tokenises the new text and writes its postings; on an update, it tokenises both versions, diffs the two term sets, deletes the postings that no longer apply and writes the new ones; on a delete, it removes the document's postings altogether. The writes are naturally idempotent, since putting the same posting twice leaves the same item, which makes the inevitable Lambda retries harmless. Nobody has to remember to reindex anything, and the index follows the data within moments of every change.

The honest trade-offs

Now for the parts that deserve scrutiny before you build one of these. The first is scale: a million documents averaging a hundred distinct terms each means up to a hundred million postings. DynamoDB handles that volume without complaint, but you pay to create it. At current on-demand pricing of $0.625 per million writes, indexing the full corpus costs around $62, once, and at roughly 100 bytes per posting the index occupies about 10 GB, which costs around $2.50 a month to store. Each search after that consumes a few read units - fractions of a thousandth of a cent, even for a term with a thousand matching documents. Compare that with the Athena approach from part one, where the same corpus cost around fifty cents for every single search, and the shape of the bargain is clear: you pay once to structure the data, and searching it afterwards is close to free.

The second consideration is hot partitions. A term that appears in most of your documents accumulates an enormous item collection under one partition key, and DynamoDB limits how much traffic a single key can sustain, so your most popular search term becomes your slowest. Stopword removal takes out the worst offenders before they ever reach the index, and for legitimately common terms the standard remedy is to shard the key - writing postings under "cat#0" through "cat#15" round-robin, and querying all sixteen shards in parallel when a search comes in.

The third is what you give up compared with a real search engine. Proper relevance scoring such as BM25, high-quality stemming across languages, typo tolerance, proximity scoring and faceted navigation are all things Elasticsearch provides out of the box, and every one of them can be approximated on this design, but each is a project of its own. My view is that this pattern is ample for the search box over your own application's records, and the moment search itself becomes the product - when users expect Google-quality ranking over messy text - you've outgrown it, and a managed engine earns its standing cost.

In summary

DynamoDB has no search feature, and it doesn't need one for this job: an inverted index laid out across its partitions gives a serverless application fast, effectively free text search, at the price of some up-front structure and a pipeline to maintain it. Along the way you end up understanding precisely what products like Elasticsearch are doing beneath their APIs, which I found to be worth the exercise on its own. The next article in the series takes the opposite philosophy entirely: no index, no preparation, just the raw text in S3 and a fleet of parallel Lambda functions tearing through it - and some interesting problems around byte ranges and Bloom filters when we do. If you're weighing up an approach like this for your own application, I'm always happy to talk it through.