Search and Secondary Indexes

Why a B-tree cannot do this

A B-tree index on a title column answers 'titles equal to X' and 'titles starting with X', because both map to one contiguous range of the sorted keys. 'Titles containing the word socks somewhere' does not — the matches are scattered across the whole sort order, so the database falls back to reading every row.

Full-text search also wants things exact matching never offered: 'Running' should match 'run', 'colour' might match 'color', and the results should come back ranked by relevance rather than in table order.

The inverted index

Before indexing, text goes through an analysis pipeline: split into tokens, lower-case them, optionally drop very common words, and optionally reduce words to a stem so 'running' and 'runs' share an entry. The same pipeline runs on the query, which is the whole trick — query and documents are normalised the same way, so they meet in the middle.

Ranking then scores each match. The common family of scoring functions rewards a term that appears often in this document but rarely across the corpus — 'wool' is more informative than 'red' if most products are red — and normalises for document length so long documents do not win by volume alone.

Search is a second store

A dedicated search engine is usually a separate system from the primary database. That makes it the textbook case of the second-store problem from the Data section: two systems holding related data, which will disagree, and one of which must be declared the truth. The database is the truth. The index is derived, may lag, and must be rebuildable from scratch.

Why not just write to both?

Dual writes — the API writes the database, then writes the index — look simpler and drift forever. The second write fails after the first succeeds; two concurrent updates reach the two systems in opposite orders; a retry re-sends an old version after a newer one landed. Each case leaves the index permanently wrong with no record that it is.

• Outbox: in the same transaction as the business write, insert a row into an outbox table. A relay publishes outbox rows to the queue. Either both happened or neither did.
• Change data capture: read the database's own replication log and turn it into events. No application change, but you consume the database's internal format.
• Either way, make the indexer idempotent and version-aware, so a replayed or reordered event cannot overwrite newer data.

Secondary indexes in a partitioned store

Once data is sharded by a primary key, a secondary index has to be partitioned too, and there are two ways to do it.

Worked illustration: with 32 shards, a local-index query for 'orders with status = refunded' becomes 32 parallel requests, and its latency is the slowest of the 32. A global index answers from one partition, but an order refunded a moment ago might not appear yet.

Recognising it

• Requirements mention 'search', 'contains', typo tolerance, relevance or facets: inverted index.
• Queries filter by an attribute other than the shard key: secondary index, local or global.
• The same data must be queryable two very different ways: a derived store, fed from the source of truth.