Skip to content

Search Systems

intermediate · 30 min · Last reviewed 31 Oct 2026 · by TheLearningLoop Team

Key takeaways

  • An inverted index maps each word to the documents that contain it, so a query mostly costs the lengths of the lists it reads, not the size of the whole collection.
  • Treat the search index as a derived copy of the database. It lags by seconds and can be rebuilt.
  • Shard the index to scale and replicate it for availability. A query goes to every shard and a coordinator merges the results.

Why you need a search system, and when to use one

Scanning every document for a word is fine for a hundred notes and impossible for a hundred million. Users also expect results to be ranked, forgiving of typos and quick. A search system builds an inverted index ahead of time, so a query looks up words rather than reading documents, then ranks the matches.

It gives you two things interviewers always ask about:

  • Low latency at scale: answers in tens of milliseconds across millions of documents.
  • Relevance: the best matches first, with support for phrases, filters and typo tolerance.

Use it when:

  • Users search text by words, with ranking.
  • You need filters and facets (price range, brand) alongside text.
  • A database LIKE '%word%' query is too slow or too crude.
  • You need autocomplete, typo tolerance or highlighting.

Skip it, or use something else, when:

  • You search by exact keys or ranges: a database index is enough.
  • The data is small: your database's built-in full-text search may be enough.
  • You need strong transactional consistency with the source data. A search index is a derived copy that lags behind.

Try it

Search for a word using a scan and using an index. Then add a new document.

Search Systems

Step 1 of 3 · Press Space to play, arrow keys to step

Search: sharding

Query"sharding"Search methodInverted indexDocuments1000000

Initial state. The system holds 1000000 documents (each toy document stands for 125,000 real ones). A user searches for "sharding".

tick:
0
documents examined:
0
documents found:
0

1 tick = one step of the simulation.

Things to try:

  • Run the Inverted index with a rare word. It examines only the documents that contain it.
  • Run Scan every document with the same query and compare the work.
  • Choose A document was just added and see which method finds it. Search indexes are refreshed on a schedule, so they are near real time, not instant.

What to watch. The simulation uses 8 toy documents, each standing for 125,000 real ones, so 1,000,000 in all:

  • Scan, rare word: 1,000,000 documents examined, 125,000 found.
  • Index, rare word: 125,000 examined. That is 8 times less work.
  • Index, common word "cache": 500,000 examined, only 2 times less than the scan. The advantage shrinks as more documents match.
  • A document was just added: the scan examines 1,125,000 and finds 250,000. The index examines 125,000 and finds 125,000, because the new document is not refreshed into it yet.

Search approaches

ApproachHow it worksGood whenWeakness
Scan all documentsRead each one and look for the wordsTiny datasetsCost grows with data
Database LIKEPattern match in the databaseA few thousand rowsCannot use a normal index for a leading wildcard, no ranking
Database full-text searchBuilt-in inverted index and rankingModerate scale, one databaseFewer features, shares resources with transactions
Dedicated search engineA separate inverted index service, sharded and replicatedLarge scale, rich featuresAnother system to run and keep in sync
Vector searchCompare numeric meaning vectorsSearch by meaning, not exact wordsApproximate, needs embeddings

Scan vs inverted index

  • Scan: cost is proportional to the number of documents, whatever the query.
  • Inverted index: a map from each term to a posting list of the documents containing it. A query looks up each term and combines lists. Cost depends on the number of matches, so rare words are very cheap and very common words cost more. With several words, the engine combines lists, so the work also depends on how long they are, and ranking costs more as more matches must be scored.

An index trades space and build time for query speed.

A small illustrative example, using the eight toy documents from the simulation below (numbered 1 to 8):

TermPosting list (documents containing it)
cachedocs 1, 2, 5, 8
databasedocs 4, 5
shardingdoc 4

A search for "cache database" looks up two lists and keeps the documents in both. Only doc 5 ("cache and database together") is in both, so the engine never reads docs 3, 6 or 7.

How a search works

  1. Indexing: each document is split into words (tokenised), lower-cased, stripped of common words (optional, as many engines keep them and rely on ranking) and reduced to a root form (stemming). The terms are added to the inverted index.
  2. Querying: the query goes through the same steps. For each term, the engine reads its posting list. For "red shoes" it intersects the lists.
  3. Ranking: matches are scored, usually by TF-IDF or BM25: a term counts more when it appears often in a document and rarely in the whole collection. Business signals such as popularity can be mixed in.
  4. Scaling out: the index is split into shards, each holding part of the documents. A query goes to all shards, each returns its best results, and a coordinator merges them. Replicas add read capacity and availability.
  5. Freshness: new documents are added to small in-memory segments that become searchable after a refresh (about a second in many engines), and segments are merged in the background.

Three costs to remember. The shard count is usually fixed when an index is created, so choose it with growth in mind or plan to reindex into a new index. A query waits for its slowest shard, so one overloaded shard slows every search. Deep paging is costly because, for page 10,000, every shard must return all of its top results up to that offset and the coordinator must merge them. Each shard also scores with its own term statistics, so ranking can differ slightly when shards are small or unevenly filled.

Search system vs the alternatives

ConcernSearch engineDatabase full-textDatabase LIKE
Speed at large scaleFastMediumSlow
Ranking and relevanceRichBasicNone
Typos, synonyms, facetsYesLimitedNo
Always up to dateNear real timeYesYes
Extra system to runYesNoNo
Best forSearch-centred productsModerate searchTiny tables

Use the database's search until it hurts, then move to a search engine and keep it in sync.

Avoiding a new single point of failure

  • Source of truth: the database remains the master, and the index is a derived copy that can be rebuilt.
  • Cluster: several shards with replicas, so losing a node loses neither data nor capacity.
  • Sync: feed changes from the database through a queue or change stream, and run a periodic full rebuild to fix drift. Send the document id and a version (for example a last-modified time) with each update, so a retried or out-of-order update cannot overwrite newer data with older data.
  • Fallback: if search is down, show browse pages or a simpler database query.

You accept that search results can lag behind the database by seconds.

Common mistakes

  • Treating the search index as the source of truth. It can be rebuilt, the database cannot.
  • Updating the index inside the user's request. Use a queue so a slow index does not slow writes.
  • Too many shards. Each shard has overhead.
  • Indexing everything. Index only searchable fields, and use filters for exact values.
  • No reindex plan. Changing the analysis needs a rebuild into a new index and a swap.
  • Ignoring deep paging. Fetching page 10,000 is expensive. Use cursors.
  • Applying updates without a version. A retry or a late message can replace a newer document with an older one. Version every update.

How to talk about search in an interview

  • Define what is searched, the scale, and how fresh results must be.
  • Explain the inverted index, tokenising, ranking and sharding with a merge step.
  • Say the database is the source of truth and changes flow to the index through a queue.
  • Name the trade-off: a separate index gives fast, ranked search but is eventually consistent and one more system to operate.

Where you meet search systems in real systems

Shops, documentation sites, log tools and maps all depend on an inverted index. Here are three drawn out, the first with SQL you can run, then more examples.

Example 1: Full-text search with an inverted index

PostgreSQL has a built-in inverted index (GIN) for text. It is a good first step before running a separate search engine. Open the example below to see the picture and the commands.

Config: a full-text index with rankingSetup 1 table and 1 indexCode no code changes
Tokenisewords, lower caseInverted indexword to documentsLookup + combineposting listsRankmost relevant first
Documents are broken into words and added to an inverted index. A query looks up its words, combines the lists and ranks the matches.
CREATE TABLE articles (
  id    bigserial PRIMARY KEY,
  title text NOT NULL,
  body  text NOT NULL,
  -- A generated column holds the searchable form: words reduced to roots, with the title weighted higher.
  tsv   tsvector GENERATED ALWAYS AS (
          setweight(to_tsvector('english', title), 'A') ||
          setweight(to_tsvector('english', body), 'B')
        ) STORED
);

-- A GIN index is an inverted index: each word points to the rows that contain it.
CREATE INDEX articles_tsv ON articles USING GIN (tsv);

INSERT INTO articles (title, body) VALUES
  ('Caching basics', 'A cache speeds up reads by keeping hot data in memory.'),
  ('Sharding a database', 'Sharding splits data across machines. A cache helps too.'),
  ('Queues', 'A queue holds work until a worker is ready.');

-- Search for articles about "cache" and "database" and rank the best matches first.
SELECT id, title, ts_rank(tsv, q) AS score
FROM articles, to_tsquery('english', 'cache & database') AS q
WHERE tsv @@ q
ORDER BY score DESC;

The SQL was run against a real PostgreSQL 16 server: it created the index, and the search returned the article that mentions both words. The Python script was run with Python 3 and returned the one article that contains both words.

Example 2: A sharded search cluster

The index is split into shards. A query goes to every shard, and a coordinator merges the best results.

QueryCoordinatorShard 1Shard 2Shard 3
The coordinator sends the query to each shard. Every shard returns its top results, and the coordinator merges them into one ranked list.

Example 3: Keeping the index in sync

Changes in the database are sent to the index through a queue, so a slow index never slows the main application. Each message carries the document id and a version, so retries and out-of-order delivery are safe.

Write to databasesource of truthPublish changequeue or change streamWorker updates indexretries on failureSearchableafter a refresh
A change is saved in the database, published to a queue, and applied to the index by a worker. If the worker falls behind, search lags but the application is unaffected.

More real-world scenarios

Scenarios 4 to 10 are common patterns, not accounts of one company's system.

4. Product search

Text queries combine with filters on price, brand and availability, and ranking mixes text relevance with sales and ratings.

5. Documentation and help centres

Pages are indexed with titles weighted more than body text, and popular queries are tuned by hand.

6. Log and event search

Machine data is indexed so engineers can find an error across millions of lines. Old indexes are rolled over and deleted.

7. Email and chat search

Each user's messages are searched within their own data, so the index is partitioned by user. One illustrative design choice is to route a user's documents to the same shard, so a query touches one shard instead of all of them, at the cost of uneven shards for very large mailboxes.

8. Map and place search

Text is combined with location, so results near the user rank higher.

9. Job and listing sites

Faceted navigation lets users narrow by location, salary and type, each facet counted from the index.

10. Semantic search

Text is converted to vectors, and nearest-neighbour search finds items that mean the same even without shared words.

Tools and managed services

KindNameNotes
Search engineElasticsearch, OpenSearch, Apache SolrDistributed inverted index with ranking
LibraryApache LuceneThe index library inside many search engines
Database featurePostgreSQL full-text search, MySQL full-textGood first step
ManagedAmazon OpenSearch Service, Elastic CloudHosted clusters
Light enginesMeilisearch, TypesenseSimple search-as-you-type engines

The takeaway

Whenever users search text at scale, build an inverted index ahead of time, treat it as a derived copy of the database, and accept that it lags a little.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

  1. 1.

    Why can a search engine find documents in milliseconds among millions?

    easy
  2. 2.

    Your products live in a database but you search them in Elasticsearch. How do you keep them in sync?

    medium
  3. 3.

    How are search results ranked?

    medium
  4. 4.

    The index no longer fits on one machine. What do you do?

    medium
  5. 5.

    A user publishes a post and searches for it a second later. It is missing. Why, and what can you do?

    hard
  6. 6.

    You must change how text is analysed, for example to add synonyms. How do you do it without downtime?

    hard
  7. 7.

    Users can jump to page 10,000 of the results. Why is that a problem, and what do you do?

    medium

Finished this lesson?

Progress is saved on this device. Create a free account to keep it everywhere.

← Previous
Blob and Object Storage
Next →
Batch and Stream Processing
Topics:SearchInverted indexElasticsearchFull text searchBm25RankingSharding

↑ Back to top

Next lesson