03.6 Search — full-text & beyond

Junior · Component

Core idea

Databases are bad at full-text search. A SQL LIKE ‘%keyword%’ does a full table scan. Search engines use inverted indexes to map words to documents — making keyword search O(log N) instead of O(N).

Mental model

A library catalogue: rather than reading every book to find references to ‘distributed systems’, the catalogue lists every word and which books mention it. ‘distributed’ → [Book 1, Book 7, Book 42]. ‘systems’ → [Book 1, Book 3, Book 42]. Intersection → [Book 1, Book 42]. That’s an inverted index.

Why it matters

  • Search is a first-class feature in most products — must be designed for
  • SQL full-text search doesn’t scale past millions of rows
  • A dedicated search engine such as Elasticsearch appears in many designs, so know why it is needed

What to know

  • Inverted index: maps token → list of document IDs (with position, frequency)
  • Tokenization: ‘Hello World’ → [‘hello’, ‘world’] — lowercase, strip punctuation
  • Stemming: ‘running’ → ‘run’, ‘runs’ → ‘run’ — finds related forms
  • TF-IDF: term frequency × inverse document frequency — ranks relevance
  • Elasticsearch: distributed, sharded, replicated search — primary DB for search, not for source of truth
  • Sync pattern: DB is source of truth → write events to Kafka → consumer writes to ES — keep in sync
  • Autocomplete/typeahead: trie or prefix-indexed search — different from full-text

Common traps

  • Using Elasticsearch as your primary database — it’s not ACID, not for source of truth
  • Forgetting to sync: DB update doesn’t automatically update search index — must be explicit
  • Not handling reindex: schema changes require reindex — can take hours on large datasets

Recognise it

Recognition trigger: ‘Search for tweets’, ‘find products’, ‘search users by name’ → separate search service backed by Elasticsearch. Source of truth stays in primary DB. Sync via event stream.

Practice question

How would you implement search for Twitter? Users should find tweets by keyword in near real-time.

Go deeper