Step 2 of 16 · 1 min

Why databases are bad at search

Lesson 3.1 showed the first attempt at people search:

SELECT * FROM users WHERE display_name ILIKE '%meera%';

The % at the start means "anything can come before it," so a normal B-tree index (lesson 1.4) can't help; it's sorted by the start of the name. Postgres had to check all 2 million names. And even when it found matches, it couldn't say which were better matches, couldn't forgive typos ("mera"), and didn't know that "running" and "run" are related.

Search needs a different kind of index: one organized by words, not by rows.

Step 3 of 16 · 1 min

The inverted index

A normal index maps from a row to its contents. An inverted index goes the other way: from each word to the list of documents that contain it.

Take three posts:

post 1: "Monsoon in Pune is finally here"
post 2: "Pune traffic is terrible in the monsoon"
post 3: "Finally finished my first marathon"

The inverted index looks like this:

finally   → 1, 3
finished  → 3
here      → 1
marathon  → 3
monsoon   → 1, 2
pune      → 1, 2
terrible  → 2
traffic   → 2
...

Each word's list is called a posting list. Searching for monsoon pune means fetching the posting lists for monsoon and pune and finding the documents in both: posts 1 and 2. Posting lists are kept sorted by document ID, so finding the overlap is a quick walk through both lists in order, the same idea as mutual friends in lesson 3.1.

This is how every full-text search engine works, from Postgres's built-in text search to Elasticsearch, OpenSearch and the search inside your email.

Step 4 of 16 · 1 min

What happens to text before it's indexed

Before a document's words go into the index, they pass through an analyzer, a series of steps that decides what counts as "the same word." The same analyzer runs on search queries, so both sides match.

Typical steps:

• Splitting into words (tokenizing). Easy for English. Much harder for languages written without spaces, and for things like @meera, #cricket and URLs.
• Lowercasing, so Pune and pune match.
• Removing accents, so café matches cafe.
• Removing very common words (stop words) like "the," "is," "in," which appear everywhere and help little. Modern engines often keep them, because phrases like "to be or not to be" are nothing but stop words.
• Stemming, which reduces words to a root, so running, runs and ran might all match run. Each language needs its own rules.
• Synonyms, so bengaluru matches bangalore.

Choosing the analyzer is most of the work of making search good, and it's specific to your users. Chirp's users write in English, Hindi, and very often Hindi in Latin letters ("kal match dekhte hain"), with spelling that varies from person to person. Chirp ended up with separate analyzers for each, and searched all three fields at once.

Partial words and typos

Two needs come up constantly, and the inverted index handles them in clever ways:

Search-as-you-type. For a name search, someone types mee and expects to see Meera. One common approach indexes the beginning of each word in extra pieces (edge n-grams): meera is stored as m, me, mee, meer, meera. Typing mee is now an exact lookup.

Typos. Searching mera should find meera. Engines handle this with fuzzy matching: finding indexed words within one or two edits (an inserted, deleted or swapped letter). Doing this efficiently across millions of words is one of the clever parts of search engines; they don't compare against every word.

Step 5 of 16 · 1 min

Ranking

Finding matching documents is half the job. The other half is putting the best ones first.

Most search engines start from a scoring formula called BM25. You don't need the formula, but its three ideas are intuitive:

• A word that appears more often in a document makes it a better match, with diminishing returns. Five mentions of "monsoon" beats one, but fifty isn't ten times better than five.
• Rare words count for more than common ones. A post matching "marathon" says more than a post matching "today," because far fewer posts contain "marathon." This is called inverse document frequency.
• Matches in short documents count for more than matches in long ones. "Monsoon!" is more about the monsoon than a long post that mentions it once.

Real products mix that text score with their own signals. For Chirp's people search: how many followers someone has, whether you follow people who follow them, whether they're in the city you filtered by. For post search: recency and engagement. Getting this mix right is an ongoing product job, not a one-time setting.

Step 6 of 16 · 1 min

Is Postgres enough?

Before adding a search engine, Chirp tried Postgres's own features, and they went further than expected. It's worth knowing them, because for many apps they're all you need.

Trigram indexes (the pg_trgm extension). A trigram index breaks text into three-letter pieces and indexes those. It makes ILIKE '%meera%' use an index, and supports "similar to" searches that forgive small typos:

CREATE EXTENSION pg_trgm;
CREATE INDEX users_name_trgm ON users USING gin (display_name gin_trgm_ops);

SELECT id, display_name
FROM users
WHERE display_name % 'mera kapor'          -- "similar to"
ORDER BY similarity(display_name, 'mera kapor') DESC
LIMIT 10;

For people search over 2 million names, this ran in a few milliseconds.

Full-text search (tsvector and tsquery). Postgres has a built-in inverted index (a GIN index), language-aware stemming and basic ranking.

So why did Chirp add Elasticsearch anyway? Post search needed things Postgres made hard: Hindi and Hinglish analysis, combining text relevance with engagement and recency in one ranking, highlighting matched words, and room to grow to billions of posts without loading the main database. People search stayed in Postgres with a trigram index. Post search moved to a dedicated engine.

A rough rule: if you need to search one or two fields, in one language, over millions of rows, start with Postgres. If search is a core product feature, with many languages, complicated ranking and large volume, use a search engine.

Step 7 of 16 · 1 min

How a search engine is laid out

Elasticsearch and OpenSearch, the most common choices, work like this:

• An index (roughly, a table) is split into shards, each a self-contained inverted index. Shards spread across machines, so the index can grow beyond one server, and a query runs on all shards at once and merges the results.
• Each shard has replicas on other machines, for availability and to share query load (lesson 2.5's ideas again).
• New documents aren't searchable instantly. They become visible at the next refresh, every second by default. This is called near-real-time search. It's fast enough that users rarely notice, but it means "I just posted, why can't I search for it?" has a one-second answer.

The most important property, though, is this: the search index is a copy. The posts live in Postgres. The search index is a rearranged copy of some of their fields, optimized for finding them. Lesson 3.3's rules apply in full: it's derived data, it's a reference (it should track the original), and it needs a reliable way to stay correct.

Step 8 of 16 · 3 min

Keeping the index in sync

Dual writes: what went wrong

Chirp's first version did what most first versions do. In the code that saved a post:

db.execute("INSERT INTO posts ...")
db.commit()
search.index(post)          # second, separate write

This is called a dual write: the application writes to two systems, one after the other. It looks fine, and it's broken in at least three ways:

• The second write can fail after the first succeeded. A timeout, a busy search cluster, a server restarting mid-deploy. The post exists in Postgres and not in search. That was the 2% of missing posts.
• Writes can arrive out of order. Priya edits a post twice, quickly. Two app servers handle the two edits. Both update Postgres in the right order, but their search updates arrive the other way round. The index now has the older text, permanently. That was the posts with old text.
• Not every change goes through that code. Deletes from an admin tool, a script that fixed some data, a database trigger. None of them knew about search. That was the deleted post with the street name.

Change data capture

The fix was to stop having the application tell search about changes, and instead read the changes straight from the database.

Lesson 1.4 showed that every change Postgres makes is first recorded in its write-ahead log. Lesson 2.5 showed replicas reading that log to stay in sync. Change data capture (CDC) uses the same log for another purpose: a separate process reads it and turns each change into an event, like "post 9001 updated, here are its new values," or "post 8812 deleted."

In Postgres, this uses logical decoding: the database turns its internal log into a stream of row-level changes, and keeps a replication slot that remembers how far each reader has got. Tools like Debezium read that stream and publish the changes (usually into a message log, which Part 4 covers) for other systems to consume.

Chirp's new pipeline:

1. The app writes to Postgres. Only to Postgres.
2. A CDC process reads the change stream from the database.
3. An indexer process receives each change and updates the search index: an upsert for creates and updates, a delete for deletes.

This fixes all three problems:

• Nothing can be skipped. Every committed change is in the log, whichever code made it: the app, an admin tool, a script, a manual fix. If the indexer is down, changes wait in the stream until it comes back.
• Order is preserved. The log records changes in the order they committed, so two edits to the same post arrive in the right order.
• Retries are safe, if the indexer is written carefully (next section).

The cost is that search is now always a little behind the database, typically under a second plus the refresh interval. For search, that's fine.

Making the indexer safe to retry

The change stream delivers each change at least once. If the indexer crashes after updating search but before recording that it had, it will see that change again when it restarts. So applying a change twice must be harmless (lesson 1.5's idempotency, again):

• Use the post ID as the search document's ID, so indexing post 9001 twice replaces the same document instead of creating two.
• Include a version, such as the post's updated_at or the log position of the change, and have the search engine reject anything older than what it already has. Elasticsearch supports this directly (external versioning). Then even if an old change somehow arrives late, it can't overwrite newer data.
• Deletes are deletes. And for anything with privacy implications, like a deleted post, it's worth also hiding it at query time: when search results come back, check the post still exists and is visible before showing it. Lesson 4.4 makes the same point about feeds: copies are for speed, while the database decides what people are allowed to see.

One thing to watch

A replication slot makes Postgres keep the log until the reader has consumed it. That's what guarantees nothing is lost. It also means that if the CDC process stops for a long time, Postgres keeps every bit of log since then, and the database's disk slowly fills up. More than one company has had its main database run out of disk because a forgotten CDC slot was still holding log.

Two precautions: alert on how far behind each slot is, and set a limit on how much log a slot may hold (Postgres 13 and later have a setting for this, max_slot_wal_keep_size). If the limit is hit, the slot is invalidated and you'll need to rebuild the index, but the database stays up.

Step 9 of 16 · 1 min

Rebuilding the index

Sooner or later you have to rebuild the whole search index. You changed the analyzer, added a field, changed how shards are laid out, or the index got corrupted. Search can't go down while you do it.

The standard way uses an alias: a name that points to an index, which the app queries instead of the index directly.

1. The app searches posts, which is an alias currently pointing to the index posts_v3.
2. Create a new, empty index posts_v4 with the new settings.
3. Note the current position in the change stream, then copy every post from Postgres into posts_v4, in batches. This is the backfill.
4. Replay the change stream from the noted position into posts_v4, so it catches up with everything that changed during the backfill. Thanks to versioning, applying a change that the backfill already included does no harm.
5. Once posts_v4 is caught up, switch the alias to point at it. This is a single, atomic operation; searches move over instantly.
6. Keep posts_v3 for a day in case you need to switch back, then delete it.

Chirp rebuilt its post index three times in the first two months, as the Hindi and Hinglish analyzers improved. Nobody outside the team noticed any of them.

Step 10 of 16 · 1 min

From the real world: what Jepsen found in search clusters

This lesson says to keep the database as the source of truth and treat the search index as a copy. There's a real-world reason beyond tidiness: search clusters have historically been weak at keeping writes during network failures.

In 2014, Kyle Kingsbury's Jepsen project tested Elasticsearch: write documents to a cluster while cutting the network between nodes in various ways, then check which acknowledged writes survived. The results were stark. In several kinds of network partition, a cluster could end up with two nodes both acting as the primary for the same shard, each accepting and acknowledging writes. When the network healed, one side's history won and the other's acknowledged writes were discarded. Even with the recommended settings, some partitions lost writes.

Elastic took it seriously and improved cluster coordination over several major versions, including a new consensus-based cluster coordination system in version 7.0 (2019), and published a page tracking resilience problems and their fixes. Modern versions are far better.

But the design lesson stands for any search engine: don't make the search index the only copy of anything. If Chirp's index lost writes, or got corrupted, or needed a new mapping, the reindex pipeline from this lesson rebuilds it from Postgres. That's only possible because the database is the source of truth.

Step 11 of 16 · 1 min

Going deeper: segments, and why updates are expensive

This lesson's layout section said new documents become searchable at the next refresh. Here's what that means inside one shard, and why it makes some workloads much more expensive than others.

A search shard (a Lucene index, in Elasticsearch and OpenSearch) is a set of segments. Each segment is a complete, small inverted index, and once written, it never changes. New documents go into an in-memory buffer. Every second, by default, a refresh turns the buffer into a new segment, and from then on the documents are searchable. A query searches all segments and combines the results. In the background, merges combine small segments into bigger ones, so there aren't hundreds to search.

Because segments never change, an update is a delete plus a new document. The old copy is only marked as deleted in a small per-segment bitmap; it still takes space and is skipped at query time. It's physically removed only when its segment is merged.

That shapes how you should use a search index:

• Keep fast-changing numbers out. If like counts are in the index for ranking, every like rewrites the whole post document. A popular post liked 1,000 times a minute creates 1,000 deleted copies a minute, and merges run constantly to clean them up, competing with queries for disk and CPU. Instead, update counts in batches (every few minutes), or keep them outside the index and combine at query time.
• Bulk loads want a longer refresh interval. During a full reindex, set refresh_interval to 30 seconds or turn it off, then restore it. Fewer, larger segments are much cheaper to build.
• Deletes don't free space immediately. An index with heavy deletes can be much larger on disk than its live documents. Watch the deleted-documents ratio.

Step 12 of 16 · 1 min

What Chirp changed

• People search stayed in Postgres, with a trigram index on display names and a separate one on cities.
• Post search moved to OpenSearch, with English, Hindi and Hinglish analyzers and ranking that mixes text relevance with recency and engagement.
• Replaced dual writes with change data capture: Postgres → change stream → indexer → search.
• The indexer uses post IDs as document IDs and the change's log position as the version.
• Search results are checked against the database for visibility before being shown.
• Added alerts on CDC lag and a cap on how much log a slot can hold.
• Index changes ship through aliases: backfill, catch up, switch.

The street-name post was removed from the index within an hour of the report. With CDC in place, the next deletion of that kind reached search in under two seconds.

Step 13 of 16 · 1 min

In the simulation

Stage 2's search feature lets you choose between a LIKE query, a database text index, and a separate search engine, and then between keeping it in sync with dual writes or CDC. The simulation includes failed writes, out-of-order edits and deletions made outside the app. With dual writes, you'll see the drift accumulate on the dashboard.

Open the simulation →

Step 14 of 16 · 1 min

If you're here for an interview

Search comes up in almost every product design (users, posts, products, places). Strong answers cover:

• The inverted index, and that the database stays the source of truth.
• Analysis: at least lowercasing, stemming and partial-word matching for autocomplete.
• Sync through CDC rather than dual writes, and why dual writes drift.
• Idempotent, versioned indexing, so retries and reordering are harmless.
• Rebuilding with aliases, if the interviewer asks about changing the index later.

Mentioning that deleted or private content should also be filtered at query time shows you've thought about the failure that actually hurts users.

Step 15 of 16 · 2 min

Try these yourself

Step 16 of 16 · 1 min

Further reading

• Martin Kleppmann, Designing Data-Intensive Applications, Chapter 3 (full-text search indexes) and Chapter 11 (change data capture, and why dual writes go wrong).
• Introduction to Information Retrieval by Manning, Raghavan and Schütze. Free online; chapters 1, 2 and 6 cover inverted indexes, text processing and scoring.
• PostgreSQL documentation on pg_trgm, full-text search, and logical decoding and replication slots.
• Elasticsearch or OpenSearch documentation on analyzers, index aliases and external versioning.
• Debezium documentation, for how a production CDC pipeline is put together.
• Kyle Kingsbury, "Jepsen: Elasticsearch" (2014) and "Elasticsearch 1.5.0" (2015), aphyr.com.
• Elastic, "Resiliency status" page, and the 7.0 release notes on the new cluster coordination subsystem.
• Lucene and Elasticsearch documentation on segments, refresh and merging; Michael McCandless's blog posts on Lucene segment merging.