Full Text Search with IndexedDB

A practical walkthrough of building full-text search on top of IndexedDB for borogove, a web-based chat client that stores message history locally. IndexedDB has no built-in full-text search, so the author (singpolyma) builds one from scratch in two stages: a naive table scan, then an indexed approach that handles a million messages.

Tokenization and stemming

Both approaches start with the same text pipeline. A tokenize() function lowercases input, splits on word boundaries, drops single characters and stopwords. Optionally, a Porter2 stemmer maps inflected forms to roots so "flying" matches "fly." The query and the stored text go through the same pipeline before comparison.

The match condition is set containment: a document matches if its token set is a superset of the query token set. JavaScript's Set.isSupersetOf() handles this directly.

Table scan

The simplest approach: open a cursor over the entire messages store, tokenize each message's text, check if it contains all query terms. This works fine for datasets under about 10,000 messages. Beyond that, iterating every row becomes noticeably slow.

Indexed search with multiEntry

IndexedDB supports a multiEntry: true flag when creating an index on an array field. Instead of indexing the array as a single key, it creates a separate B-tree entry for each element — effectively an inverted-index. When storing a message, you include a terms array (the deduplicated, stemmed tokens), and each term gets its own index entry pointing back to the message.

The search algorithm:

1. Tokenize and stem the query
2. For each query term, ask the index how many messages contain it (index.count())
3. Pick the rarest term — the one with the fewest matches
4. Open a cursor on the index for just that term
5. For each candidate, check if its full term set is a superset of all query terms
6. Sort results by timestamp manually (the index order is by term, not time)

The "probe the rarest term" step is what makes this fast. In a million-message corpus, even common words might match tens of thousands of messages, but the rarest query term typically matches fewer than 10,000. Scanning 10k candidates instead of 1M is the difference between unusable and instant.

No external dependencies

The entire implementation uses only IndexedDB APIs, Set, and a tokenizer. No search library, no WebAssembly SQLite, no server-side index. This matters for offline-first web apps where you want search without adding heavyweight dependencies.

Limitations

The article doesn't cover ranking — results are returned in timestamp order, not relevance order. There's no TF-IDF or BM25 scoring, no phrase matching, and no fuzzy matching beyond stemming. For a chat search box where you just want "show me messages containing these words," that's enough. For a more sophisticated retrieval system, you'd want hybrid-search techniques.

The multiEntry index also means storing the full term list alongside each message, roughly doubling storage per message. The article treats this as an acceptable tradeoff.