Back to Scenarios & Design Questions
Q23Question 23 of 67

How would you design a search service with an inverted index instead of LIKE queries

Key Concepts
  • LIKE with a leading wildcard forces a full table scan, is slow, and runs on the primary transactional database.
  • An inverted index maps each token to a posting list of document IDs for millisecond lookup, not scan.
  • Ranking with BM25 orders results by relevance; LIKE cannot rank at all.
  • Fuzzy matching uses edit distance so typos like 'hoem lon' still find 'home loan'.
  • The relational database stays the source of truth; the index is a derived, denormalized copy.
  • Sync via domain events or CDC (Debezium), accepting eventual consistency (a few seconds of lag).
  • Full reindex into a new index with atomic alias swap gives zero-downtime schema changes.

Definition

Do not scan the primary DB with LIKE; keep a dedicated inverted-index engine updated asynchronously from events, so search is millisecond-fast with ranking and typo tolerance while the DB stays the source of truth.
  • Why not LIKE – A leading wildcard %term% cannot use B-tree indexes and forces a full table scan on the transactional database.
  • Inverted index – Maps each token to a posting list of document IDs; a query is a set intersection, not a scan.
  • Ranking – BM25 scores documents by term frequency and inverse document frequency for relevance ordering.
  • Fuzzy – Edit distance (Levenshtein) so misspelled queries still match within an allowed number of character edits.
  • Sync – Domain events or CDC stream changes to the index asynchronously; eventual consistency is the acceptable trade-off.

National Bank of India has a huge filing room of products. If Rajesh asks "find every record mentioning home loan", a clerk using LIKE reads every single file cover to cover. Instead the bank keeps a separate index card catalog (inverted index) where under the word "loan" there is a card listing exactly which files contain it. A lookup is instant. The master files stay in the vault, and whenever a file changes, a runner updates the catalog shortly after.

Understanding the Concepts

WHERE description LIKE '%home loan%' has a leading wildcard, so no B-tree index can help and the database performs a full table scan. It also runs on the primary transactional database, competing with account updates and transfers.

JAVA
package com.bank.search.antipattern;

public class LikeSearchWrong {

    // WRONG: full table scan on every search query
    public static final String QUERY =
        "SELECT * FROM products WHERE description LIKE '%home loan%'";
    // Problems:
    // 1. Leading wildcard -> no index used -> full table scan
    // 2. Runs on primary DB -> competes with live transactions
    // 3. Cannot rank by relevance
    // 4. Cannot handle typos
    // 5. Gets slower as data grows
}

How does an inverted index work?

The engine tokenizes each document, then builds a map from each term to a posting list of document IDs. A query looks up posting lists and intersects them.

JAVA
package com.bank.search.engine;

import java.util.*;
import java.util.stream.Collectors;

public class SimpleInvertedIndex {

    // term -> set of document IDs
    private final Map<String, Set<String>> index = new HashMap<>();

    public void addDocument(String docId, String text) {
        for (String token : tokenize(text)) {
            index.computeIfAbsent(token, k -> new HashSet<>()).add(docId);
        }
    }

    public Set<String> search(String query) {
        String[] terms = tokenize(query);
        Set<String> result = null;
        for (String term : terms) {
            Set<String> postingList = index.getOrDefault(term, Set.of());
            if (result == null) {
                result = new HashSet<>(postingList);
            } else {
                result.retainAll(postingList); // intersection
            }
        }
        return result != null ? result : Set.of();
    }

    private String[] tokenize(String text) {
        return text.toLowerCase().split("\\s+");
    }

    public static void main(String[] args) {
        SimpleInvertedIndex idx = new SimpleInvertedIndex();
        idx.addDocument("P001", "Home Loan with low interest rate");
        idx.addDocument("P002", "Car Loan for salaried employees");
        idx.addDocument("P003", "Home Insurance plan");

        System.out.println("Search 'home loan': " + idx.search("home loan"));
        System.out.println("Search 'loan': " + idx.search("loan"));
    }
}
TEXT
Search 'home loan': [P001]
Search 'loan': [P001, P002]

How does ranking with BM25 work?

BM25 scores each document by how frequent the query terms are in that document (term frequency) and how rare they are across all documents (inverse document frequency).

JAVA
package com.bank.search.ranking;

public class RelevanceExplanation {
    // Document P001: title = "Home Loan", description = "...home loan..."
    // Document P003: description = "...mentions loan once in passing..."
    // Query: "home loan"
    //
    // P001 scores higher because:
    //   - "home" appears in title (boosted field)
    //   - "loan" appears in title AND description (higher TF)
    // P003 scores lower because:
    //   - "loan" appears once in description only
    //
    // LIKE cannot do this: it returns both as equal matches.
}

How does fuzzy matching handle typos?

Edit distance (Levenshtein) allows a configurable number of character edits so misspelled queries still match.

JAVA
package com.bank.search.fuzzy;

public class LevenshteinDistance {

    public static int distance(String a, String b) {
        int[][] dp = new int[a.length() + 1][b.length() + 1];
        for (int i = 0; i <= a.length(); i++) dp[i][0] = i;
        for (int j = 0; j <= b.length(); j++) dp[0][j] = j;
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                int cost = a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1;
                dp[i][j] = Math.min(dp[i - 1][j] + 1,
                    Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost));
            }
        }
        return dp[a.length()][b.length()];
    }

    public static void main(String[] args) {
        System.out.println(distance("hoem", "home")); // 1 (swap e and m)
        System.out.println(distance("lon", "loan"));   // 1 (insert a)
        // Elasticsearch fuzziness=1 would match both
    }
}
TEXT
1
1

How do you keep the index in sync with the database?

The database stays the source of truth. Sync via domain events or CDC, accepting eventual consistency.

JAVA
package com.bank.search.sync;

public class ProductIndexer {

    private final ElasticsearchClient esClient;

    public ProductIndexer(ElasticsearchClient esClient) {
        this.esClient = esClient;
    }

    // Event-driven: consume ProductUpdated events from Kafka
    public void onProductUpdated(ProductUpdatedEvent event) {
        esClient.index("products", event.getProductId(), event.toDocument());
    }

    // CDC: Debezium reads the DB transaction log and streams changes
    // No application code changes needed, never misses a write
}

How do you handle reindexing?

Index into a new index and atomically swap an alias for zero-downtime reindexing.

JAVA
package com.bank.search.reindex;

public class ZeroDowntimeReindex {

    public void reindex() {
        // 1. Create new index: products-v2
        // 2. Bulk index all products from DB into products-v2
        // 3. Atomically swap alias: products -> products-v2
        // 4. Delete old index: products-v1
        // Clients always query the "products" alias, never a version.
    }
}

What are common mistakes?

Using LIKE on the primary database for user-facing search is the most common. The second is writing only to the index and not keeping the database as the source of truth.

JAVA
package com.bank.search.antipattern;

// WRONG: writing to Elasticsearch without a database backup
// If the index is corrupted, you lose data.
// The DB must be the source of truth; the index is a derived copy.

What are common interview follow-up questions?

How would you handle multi-language search? How do you implement search-as-you-type (autocomplete)? What is the difference between Elasticsearch and Solr? How do you handle a search index that is hours stale? How would you implement faceted search (e.g., filter by interest rate range)?

Visual Overview

DIAGRAM
┌──────────────────────────────────────────────────────────┐
│              SEARCH SERVICE ARCHITECTURE                  │
├──────────────────────────────────────────────────────────┤
│                                                          │
│  Write Path:                                             │
│  Product Service ──▶ PostgreSQL (source of truth)        │
│                        │                                 │
│              ┌─────────▼──────────┐                      │
│              │ Domain Event /     │                      │
│              │ CDC (Debezium)     │                      │
│              └─────────┬──────────┘                      │
│                        │ async                           │
│              ┌─────────▼──────────┐                      │
│              │ Elasticsearch      │                      │
│              │ (inverted index)   │                      │
│              └────────────────────┘                      │
│                                                          │
│  Read Path:                                              │
│  Rajesh types "home loan"                                │
│         │                                                │
│  ┌──────▼──────────────────────────┐                     │
│  │ Elasticsearch query:            │                     │
│  │ - Tokenize: [home, loan]        │                     │
│  │ - Lookup posting lists          │                     │
│  │ - Intersect                     │                     │
│  │ - Rank by BM25                  │                     │
│  │ - Apply filters (rate < 9%)     │                     │
│  │ - Return top 10, page 1         │                     │
│  └──────┬──────────────────────────┘                     │
│         │ < 10ms                                         │
│         ▼                                                │
│  Results: [P001: Home Loan (score 9.2), ...]             │
└──────────────────────────────────────────────────────────┘

Key Takeaway

At National Bank of India, product searches using LIKE on the primary database slowed live transfers during a campaign because the full table scans competed for the same CPU and IO. Pankaj moved search to Elasticsearch, a dedicated engine built on an inverted index that maps each token to a posting list of document IDs. Instead of scanning every row, a query looks up posting lists and intersects them in milliseconds.

Elasticsearch also gives BM25 relevance ranking so an exact title match for "home loan" ranks above a passing mention, fuzzy matching so Rajesh's typo "hoem lon" still finds the right product, and rich filtering, sorting, and pagination natively. None of this is possible with LIKE. The database stays the source of truth, and the index is a derived, denormalized copy synced asynchronously through domain events or CDC.

The eventual consistency (a few seconds of lag) is perfectly acceptable for catalog search and far cheaper than synchronous dual-write. For schema changes, Pankaj indexes into a new index and atomically swaps an alias for zero-downtime reindexing. Failed index updates retry into a dead-letter queue, and a full reindex from the database is always possible as a recovery path.

Remember one sentence: Keep search off the primary database on a dedicated inverted-index engine for millisecond ranked, fuzzy, filtered results, sync the index asynchronously from events or CDC, and accept eventual consistency because the database stays the source of truth.

---

Share
Use ← → arrow keys to navigate