Search Systems: Elasticsearch & Inverted Index

TL;DR

Search systems use inverted indexes—data structures that map terms to document IDs—to enable fast full-text search across millions of documents. Instead of scanning every document for query terms, the inverted index provides instant lookups, with relevance scoring algorithms like TF-IDF and BM25 ranking results by importance. Production search systems balance indexing latency (building the index) against query performance (sub-100ms response times) through distributed architectures and careful optimization.

Cheat Sheet: Inverted index = term → [doc IDs]. TF-IDF = term frequency × inverse document frequency. BM25 improves on TF-IDF with saturation. Indexing pipeline: tokenize → analyze → build posting lists. Query: parse → lookup → score → rank.

Background

The inverted index emerged from library science in the 1950s, where cataloging systems needed efficient ways to find books by subject. When computing arrived, the same problem appeared at scale: how do you search millions of documents without reading each one? Early search engines like Altavista (1995) and Google (1998) built their competitive advantage on superior inverted index implementations that could crawl and index the growing web.

The fundamental problem is simple: given a query like “distributed systems design”, find all documents containing these terms in under 100 milliseconds. A naive approach—scanning every document—scales as O(N×M) where N is document count and M is average document length. With billions of documents, this is impossibly slow. The inverted index flips the problem: instead of asking “what words are in this document?”, it asks “which documents contain this word?” This transforms search from O(N×M) to O(Q) where Q is the number of query terms, typically 2-5 words.

Modern search systems like Elasticsearch, Solr, and proprietary engines at Google and Twitter process billions of queries daily using inverted indexes. The core data structure hasn’t changed much since the 1960s, but the engineering around it—distributed indexing, real-time updates, relevance scoring, and query optimization—has become extraordinarily sophisticated. Understanding inverted indexes is essential because they’re the foundation of every search system, from e-commerce product search to log analysis to document retrieval.

Architecture

A production search system consists of three major components: the indexing pipeline, the inverted index storage layer, and the query processing engine. These work together to transform raw documents into searchable data structures and serve queries at scale.

The indexing pipeline ingests documents and transforms them into index entries. Documents arrive from various sources—databases, message queues, file systems—and flow through several stages. First, tokenization breaks text into individual terms (“distributed systems” becomes [“distributed”, “systems”]). Then analysis applies transformations: lowercasing, stemming (“running” → “run”), stopword removal (“the”, “a”), and synonym expansion. The output is a stream of normalized tokens ready for indexing. At Twitter, this pipeline processes millions of tweets per day, with indexing latency under 10 seconds for real-time search.

The inverted index itself is a mapping from terms to posting lists. Each term (like “distributed”) points to a list of document IDs where it appears, along with metadata like term frequency and positions. For example: "distributed" → [(doc1, freq=3, pos=[5,12,89]), (doc5, freq=1, pos=[23]), ...]. This structure enables instant lookups: given a query term, retrieve its posting list in O(1) time using a hash table or B-tree. The posting lists are typically stored sorted by document ID, enabling efficient intersection operations for multi-term queries.

The query processing engine handles incoming search requests. It parses the query using the same tokenization and analysis rules as indexing, looks up each term’s posting list, computes the intersection or union of document sets (depending on AND/OR logic), scores each candidate document using relevance algorithms, and returns the top-K results sorted by score. Google’s search infrastructure processes over 99,000 queries per second with median latency under 200ms by distributing both the index and query processing across thousands of machines.

Distributed search systems shard the index across multiple nodes. Each shard holds a subset of documents and can process queries independently. A coordinator node receives queries, fans them out to all shards in parallel, collects results, and performs a global merge-sort to return the top results. This architecture scales horizontally: adding more shards increases both indexing throughput and query capacity.

Search System Architecture: Indexing Pipeline to Query Processing

graph LR
    subgraph Data Sources
        DB[("Database")]
        Queue["Message Queue<br/><i>Kafka</i>"]
        Files["File System"]
    end
    
    subgraph Indexing Pipeline
        Ingest["Document Ingestion"]
        Token["Tokenization<br/><i>text → tokens</i>"]
        Analyze["Analysis<br/><i>lowercase, stem, stopwords</i>"]
        Build["Index Builder<br/><i>create posting lists</i>"]
    end
    
    subgraph Storage Layer
        MemIndex["In-Memory Index<br/><i>recent docs</i>"]
        DiskIndex[("On-Disk Index<br/><i>bulk docs</i>")]
    end
    
    subgraph Query Processing
        Parser["Query Parser<br/><i>tokenize query</i>"]
        Lookup["Term Lookup<br/><i>retrieve posting lists</i>"]
        Score["Scoring Engine<br/><i>BM25 calculation</i>"]
        Rank["Result Ranker<br/><i>top-K heap</i>"]
    end
    
    User["User"] --"1. Submit query"--> Parser
    Parser --"2. Parse terms"--> Lookup
    Lookup --"3. Fetch from memory"--> MemIndex
    Lookup --"4. Fetch from disk"--> DiskIndex
    MemIndex & DiskIndex --"5. Return posting lists"--> Score
    Score --"6. Calculate relevance"--> Rank
    Rank --"7. Top results"--> User
    
    DB & Queue & Files --"Continuous feed"--> Ingest
    Ingest --> Token --> Analyze --> Build
    Build --"Real-time writes"--> MemIndex
    Build --"Batch writes"--> DiskIndex

A production search system separates indexing (left flow) from querying (right flow). Documents flow through tokenization and analysis before building posting lists stored in a two-tier architecture: in-memory for real-time updates and on-disk for bulk storage. Queries execute in parallel against both tiers and merge results.

Distributed Search: Sharding and Query Fan-out Architecture

graph TB
    User["User Query<br/>'distributed systems'"]
    
    subgraph Query Coordinator
        Router["Query Router<br/><i>parse & route</i>"]
        Merger["Result Merger<br/><i>global top-K</i>"]
    end
    
    subgraph Shard 1: docs 0-333K
        S1Query["Local Query Processor"]
        S1Index[("Inverted Index<br/>Segment 1")]
        S1Results["Local Top-100<br/><i>sorted by score</i>"]
    end
    
    subgraph Shard 2: docs 333K-666K
        S2Query["Local Query Processor"]
        S2Index[("Inverted Index<br/>Segment 2")]
        S2Results["Local Top-100<br/><i>sorted by score</i>"]
    end
    
    subgraph Shard 3: docs 666K-1M
        S3Query["Local Query Processor"]
        S3Index[("Inverted Index<br/>Segment 3")]
        S3Results["Local Top-100<br/><i>sorted by score</i>"]
    end
    
    User --"1. Submit query"--> Router
    Router --"2. Fan-out (parallel)"--> S1Query & S2Query & S3Query
    
    S1Query --"3. Search local index"--> S1Index
    S2Query --"3. Search local index"--> S2Index
    S3Query --"3. Search local index"--> S3Index
    
    S1Index --"4. Score & rank"--> S1Results
    S2Index --"4. Score & rank"--> S2Results
    S3Index --"4. Score & rank"--> S3Results
    
    S1Results & S2Results & S3Results --"5. Return local results"--> Merger
    Merger --"6. Merge-sort (global top-10)"--> User

Distributed search systems shard the index across multiple nodes, with each shard holding a subset of documents. The query coordinator fans out queries to all shards in parallel, collects local top-K results, and performs a global merge-sort to return the final top results. This architecture scales query throughput linearly with shard count.

Internals

The inverted index data structure is deceptively simple but highly optimized in production systems. At its core, it’s a dictionary mapping terms to posting lists, but the devil is in the implementation details that make it fast and space-efficient.

Posting List Structure: Each posting list contains document IDs and associated metadata. The simplest form is just a list of IDs: "search" → [1, 5, 23, 47, ...]. But production systems store much more: term frequency (how many times the term appears in each document), field information (title vs. body), and positional data (exact word positions for phrase queries). A full posting entry might look like: (docID=47, tf=3, field=body, positions=[12, 45, 89]). These lists are compressed using techniques like delta encoding (store differences between consecutive IDs) and variable-byte encoding, achieving 4-5x compression ratios.

Relevance Scoring with TF-IDF: The classic relevance algorithm is TF-IDF (Term Frequency-Inverse Document Frequency). For a term T in document D: TF-IDF(T,D) = TF(T,D) × IDF(T) where TF(T,D) = count(T in D) / total_terms(D) and IDF(T) = log(total_docs / docs_containing(T)). The intuition: terms that appear frequently in a document (high TF) but rarely across all documents (high IDF) are most distinctive and relevant. For example, “distributed” in a systems design document has high TF, but “the” has low IDF because it appears everywhere. A document’s final score for a multi-term query is the sum of TF-IDF scores for each query term.

BM25: The Modern Standard: BM25 (Best Matching 25) improves on TF-IDF by adding saturation and document length normalization. The formula is: BM25(T,D) = IDF(T) × (TF(T,D) × (k1 + 1)) / (TF(T,D) + k1 × (1 - b + b × (|D| / avgDocLen))) where k1 (typically 1.2-2.0) controls term frequency saturation and b (typically 0.75) controls length normalization. The key insight: after a term appears 5-10 times in a document, additional occurrences add diminishing relevance. BM25 prevents long documents from dominating results simply by repeating terms. Elasticsearch and Solr use BM25 as their default scoring algorithm.

Query Processing: When a query like “distributed systems design” arrives, the engine: (1) tokenizes and analyzes it into [“distribut”, “system”, “design”] (stemmed), (2) retrieves posting lists for each term, (3) computes the intersection of document sets (for AND queries) or union (for OR queries), (4) scores each candidate document using BM25, and (5) returns the top-K results using a min-heap. For a query with 3 terms across an index with 1M documents, this typically examines only 1000-10000 candidates rather than all 1M documents.

Index Updates: Real-time search systems face a challenge: how to make new documents searchable immediately without rebuilding the entire index. The solution is a two-tier architecture: a small in-memory buffer index for recent documents (updated in real-time) and a large on-disk index for older documents (updated periodically). Queries search both and merge results. Elasticsearch uses this approach with “refresh intervals” (default 1 second) to make new documents searchable. Twitter’s search system achieves sub-10-second indexing latency using this technique, critical for trending topics and breaking news.

Inverted Index Structure: Term to Posting List Mapping

graph LR
    subgraph Documents
        D1["Doc 1: 'distributed systems design'"]
        D2["Doc 2: 'search systems architecture'"]
        D3["Doc 3: 'distributed search implementation'"]
    end
    
    subgraph Inverted Index
        T1["Term: 'distributed'"]
        T2["Term: 'systems'"]
        T3["Term: 'design'"]
        T4["Term: 'search'"]
        T5["Term: 'architecture'"]
        T6["Term: 'implementation'"]
        
        P1["Posting List<br/>(doc1, tf=1, pos=[0])<br/>(doc3, tf=1, pos=[0])"]
        P2["Posting List<br/>(doc1, tf=1, pos=[1])<br/>(doc2, tf=1, pos=[1])"]
        P3["Posting List<br/>(doc1, tf=1, pos=[2])"]
        P4["Posting List<br/>(doc2, tf=1, pos=[0])<br/>(doc3, tf=1, pos=[1])"]
        P5["Posting List<br/>(doc2, tf=1, pos=[2])"]
        P6["Posting List<br/>(doc3, tf=1, pos=[2])"]
    end
    
    T1 --> P1
    T2 --> P2
    T3 --> P3
    T4 --> P4
    T5 --> P5
    T6 --> P6
    
    D1 -."tokenize & analyze".-> T1 & T2 & T3
    D2 -."tokenize & analyze".-> T4 & T2 & T5
    D3 -."tokenize & analyze".-> T1 & T4 & T6

The inverted index flips the document-to-terms relationship: instead of storing which terms appear in each document, it maps each term to a posting list containing document IDs, term frequencies (tf), and positions. This enables O(1) term lookup instead of O(N) document scanning.

BM25 Scoring Flow: From Query Terms to Ranked Results

sequenceDiagram
    participant User
    participant Parser
    participant Index
    participant Scorer
    participant Ranker
    
    User->>Parser: Query: "distributed systems"<br/>(2 terms)
    Parser->>Parser: Tokenize & analyze<br/>→ ["distribut", "system"]
    
    Parser->>Index: Lookup "distribut"
    Index-->>Parser: Posting list: [doc1, doc3, doc5]<br/>with tf values
    
    Parser->>Index: Lookup "system"
    Index-->>Parser: Posting list: [doc1, doc2, doc5]<br/>with tf values
    
    Parser->>Scorer: Compute intersection<br/>→ [doc1, doc5]
    
    Scorer->>Scorer: For doc1:<br/>IDF(distribut) = log(N/df)<br/>IDF(system) = log(N/df)
    
    Scorer->>Scorer: BM25(distribut, doc1) =<br/>IDF × (tf × (k1+1)) / (tf + k1 × length_norm)
    
    Scorer->>Scorer: BM25(system, doc1) =<br/>IDF × (tf × (k1+1)) / (tf + k1 × length_norm)
    
    Scorer->>Scorer: Total score(doc1) =<br/>BM25(distribut) + BM25(system)
    
    Scorer->>Scorer: Repeat for doc5...
    
    Scorer->>Ranker: Candidate scores:<br/>doc1: 8.7, doc5: 6.2
    
    Ranker->>Ranker: Sort by score (desc)<br/>using min-heap
    
    Ranker-->>User: Top results:<br/>1. doc1 (score: 8.7)<br/>2. doc5 (score: 6.2)

BM25 scoring processes each query term independently, computing IDF (inverse document frequency) and term frequency with saturation. The final document score is the sum of per-term BM25 scores, with length normalization preventing long documents from dominating results simply by repeating terms.

Performance Characteristics

Search system performance is measured across three dimensions: indexing throughput, query latency, and index size. Production systems must balance all three, as optimizing one often degrades the others.

Indexing Throughput: A single-node Elasticsearch instance can index 10,000-50,000 documents per second depending on document size and analysis complexity. Twitter’s distributed search system indexes millions of tweets per day across hundreds of nodes. The bottleneck is typically CPU (for tokenization and analysis) or disk I/O (for writing index segments). Batch indexing is 5-10x faster than real-time indexing because it can build larger segments and avoid frequent merges.

Query Latency: Sub-100ms query latency is the gold standard for user-facing search. Google’s median query latency is under 200ms despite searching billions of pages. Elasticsearch typically achieves 10-50ms latency for simple queries on warm indexes (data in OS page cache). Latency increases with: (1) result set size (top-10 is faster than top-1000), (2) query complexity (phrase queries require positional lookups), (3) index size (more shards to query), and (4) scoring complexity (BM25 is faster than machine learning models).

Index Size: Inverted indexes are typically 20-40% of the original document size after compression. A 1TB document collection becomes a 200-400GB index. Elasticsearch stores additional data structures (doc values for sorting, stored fields for retrieval), pushing total storage to 50-80% of original size. The index-to-document ratio depends heavily on analysis: aggressive stemming and stopword removal reduce index size, while n-gram indexing for fuzzy search can triple it.

Scalability: Search systems scale horizontally by sharding. Each shard is an independent index handling a subset of documents. Query throughput scales linearly with shard count (10 shards = 10x throughput) because queries execute in parallel. However, latency doesn’t improve beyond a certain point—the slowest shard determines overall latency. Large-scale systems like Google use thousands of shards with sophisticated load balancing and failover. The practical limit is typically 50-100 shards per cluster before coordination overhead dominates.

Real Numbers: Elasticsearch benchmarks show: (1) indexing 10M documents (1KB each) takes ~30 minutes on a 3-node cluster, (2) simple term queries execute in 5-20ms, (3) complex aggregations can take 100-500ms, and (4) index size is ~30% of source data with default settings. These numbers vary widely based on hardware, schema design, and query patterns.

Trade-offs

Search systems make fundamental trade-offs between indexing speed, query performance, storage efficiency, and result relevance. Understanding these trade-offs is critical for system design decisions.

Indexing Latency vs. Query Performance: Building a highly optimized index takes time. Aggressive analysis (stemming, synonym expansion, n-grams) improves search quality but slows indexing by 2-5x. Real-time systems like Twitter prioritize indexing speed, using simpler analysis and accepting slightly lower relevance. Batch systems like Google’s web index prioritize query performance, spending hours building optimized indexes. The choice depends on whether users need instant searchability or can tolerate indexing delays.

Storage vs. Functionality: Storing positional information enables phrase queries (“distributed systems” as an exact phrase) but doubles index size. Storing original documents enables result highlighting but adds 50-100% overhead. Production systems carefully choose what to store based on requirements. E-commerce search might skip positions (users rarely search exact phrases) but store prices and categories for filtering.

Relevance vs. Speed: Simple scoring algorithms like TF-IDF are fast (microseconds per document) but less accurate than machine learning models. Modern systems use a two-stage approach: BM25 for initial retrieval (top-1000 candidates in 10ms), then ML models for re-ranking (top-100 in 50ms). This balances speed and relevance. Google’s search uses dozens of ranking signals but applies expensive ones only to top candidates.

Consistency vs. Availability: Distributed search systems face CAP theorem constraints. Elasticsearch prioritizes availability: queries return results even if some shards are down, accepting incomplete results. Google’s index prioritizes consistency: all shards must respond or the query fails. The choice depends on whether partial results are acceptable.

Limitations: Inverted indexes excel at exact term matching but struggle with: (1) semantic search (“car” doesn’t match “automobile” without synonyms), (2) typo tolerance (requires fuzzy matching or n-grams, which bloat indexes), (3) numeric range queries (requires separate data structures like BKD trees), and (4) complex boolean logic (deeply nested AND/OR queries become expensive). These limitations drive adoption of complementary technologies like vector search for semantic matching.

Search System Trade-offs: Indexing vs Query Performance vs Storage

graph TB
    Start["Search System Design Decisions"]
    
    subgraph Indexing Speed
        FastIndex["Fast Indexing<br/><i>Simple analysis</i>"]
        FastIndexPro["+Real-time updates<br/>+Low latency<br/>+High throughput"]
        FastIndexCon["-Lower relevance<br/>-Fewer features<br/>-Basic scoring"]
        
        SlowIndex["Optimized Indexing<br/><i>Complex analysis</i>"]
        SlowIndexPro["+Better relevance<br/>+Rich features<br/>+Advanced scoring"]
        SlowIndexCon["-Slower updates<br/>-Higher CPU cost<br/>-Batch processing"]
    end
    
    subgraph Storage Efficiency
        Compact["Compact Index<br/><i>Minimal metadata</i>"]
        CompactPro["+20-30% of source<br/>+Lower storage cost<br/>+Faster I/O"]
        CompactCon["-No phrase queries<br/>-No highlighting<br/>-Limited filtering"]
        
        Rich["Rich Index<br/><i>Full metadata</i>"]
        RichPro["+Phrase queries<br/>+Highlighting<br/>+Complex filters"]
        RichCon["-50-80% of source<br/>-Higher storage cost<br/>-Slower I/O"]
    end
    
    subgraph Query Performance
        Simple["Simple Scoring<br/><i>TF-IDF/BM25</i>"]
        SimplePro["+Sub-10ms latency<br/>+High throughput<br/>+Predictable cost"]
        SimpleCon["-Basic relevance<br/>-No personalization<br/>-Static ranking"]
        
        Advanced["Advanced Scoring<br/><i>ML models</i>"]
        AdvancedPro["+Better relevance<br/>+Personalization<br/>+Dynamic ranking"]
        AdvancedCon["-50-200ms latency<br/>-Lower throughput<br/>-High GPU cost"]
    end
    
    Start --> FastIndex & SlowIndex
    Start --> Compact & Rich
    Start --> Simple & Advanced
    
    FastIndex --> FastIndexPro & FastIndexCon
    SlowIndex --> SlowIndexPro & SlowIndexCon
    Compact --> CompactPro & CompactCon
    Rich --> RichPro & RichCon
    Simple --> SimplePro & SimpleCon
    Advanced --> AdvancedPro & AdvancedCon

Search systems require careful trade-offs between three competing dimensions: indexing speed (how fast documents become searchable), storage efficiency (index size vs. functionality), and query performance (latency vs. relevance quality). Real-time systems like Twitter prioritize fast indexing with simple scoring, while batch systems like Google prioritize query performance with complex ranking.

When to Use (and When Not To)

Choose inverted index-based search systems when you need fast, scalable full-text search across large document collections. They’re the right tool when exact term matching and keyword-based relevance are sufficient, and when you need to support complex queries with filtering, sorting, and aggregations.

Use search systems when: (1) You have millions+ documents to search (e-commerce catalogs, log files, document repositories), (2) Users expect sub-100ms query latency, (3) You need full-text search with relevance ranking, not just exact matches, (4) Your queries involve multiple terms with boolean logic (AND/OR/NOT), (5) You need to filter and aggregate results (faceted search, analytics), and (6) Your data is primarily text-based with structured metadata.

Specific use cases: E-commerce product search (Amazon, eBay), log analysis and monitoring (Splunk, Datadog), document management (Confluence, SharePoint), social media search (Twitter, Reddit), job boards (LinkedIn, Indeed), and knowledge bases (Stack Overflow, Wikipedia). These all share characteristics: large text corpora, keyword-based queries, and need for fast, relevant results.

Don’t use search systems when: (1) You need semantic understanding (“car” matching “automobile”)—use vector databases instead, (2) Your queries are primarily structured (SQL-style joins and aggregations)—use relational databases, (3) You need real-time analytics on time-series data—use specialized OLAP systems, (4) Your data is primarily numeric or geospatial—use specialized indexes, or (5) You have fewer than 10,000 documents—a relational database with full-text indexes is simpler.

Technology selection: Choose Elasticsearch for general-purpose search with strong ecosystem and operational tooling. Choose Solr for complex enterprise search with advanced text analysis. Choose proprietary engines (Algolia, Typesense) for managed services with minimal operational overhead. Build custom search systems only at massive scale (Google, Twitter) where off-the-shelf solutions can’t meet performance or cost requirements.

Hybrid approaches: Many systems combine search with other technologies. Use search for initial retrieval, then vector search for semantic re-ranking. Use search for text, relational databases for structured data, and join results at the application layer. This hybrid approach leverages each technology’s strengths while avoiding their weaknesses.

Real-World Examples

company: Twitter system: Real-time Tweet Search (Earlybird) how_used: Twitter’s Earlybird search system indexes millions of tweets per day with sub-10-second latency, making new tweets searchable almost instantly. The system uses a distributed inverted index sharded by time (recent tweets in memory, older tweets on disk) with custom optimizations for Twitter’s unique characteristics: short documents (280 characters), high write volume, and temporal query patterns (users search recent tweets more than old ones). Each shard holds ~1 week of tweets and serves queries independently. interesting_detail: Twitter’s index stores tweet text, hashtags, mentions, and engagement metrics (likes, retweets) in the same posting list, enabling complex queries like ‘find popular tweets about #systemdesign from verified users in the last hour’ with single-pass scoring. The system processes 500,000+ queries per second during peak events like elections or sports games, with p99 latency under 100ms. The key innovation is temporal sharding: new tweets go to hot shards with aggressive caching, while old tweets live on cold shards with higher latency but lower cost.

company: Google system: Web Search Index how_used: Google’s web search index is the largest inverted index in the world, covering hundreds of billions of web pages. The index is distributed across thousands of data centers with multiple replicas for redundancy. Google’s indexing pipeline crawls the web continuously, processes pages through analysis (language detection, spam filtering, entity extraction), and builds optimized index segments. The index stores not just terms but also page structure (headings, links), metadata (page rank, freshness), and hundreds of ranking signals. interesting_detail: Google’s index uses a multi-tier architecture: a small ‘fresh index’ for recently crawled pages (updated hourly) and a large ‘main index’ for the full web (updated daily). Queries search both and merge results, ensuring new content appears quickly while maintaining comprehensive coverage. The index is so large that even with aggressive compression, it requires petabytes of storage. Google’s innovation is in distributed query processing: each query fans out to thousands of shards in parallel, with sophisticated load balancing to handle uneven query distributions (popular terms hit more shards). The system achieves 99,000+ queries per second with median latency under 200ms despite searching an index 100,000x larger than most enterprise search systems.

---

Interview Essentials

Mid-Level

At the mid-level, interviewers expect you to explain inverted index basics and demonstrate understanding of search system architecture. You should be able to describe how an inverted index maps terms to documents, explain the difference between indexing and querying, and discuss basic relevance scoring. Be prepared to design a simple search system for a specific use case (e.g., product search for an e-commerce site) and explain the indexing pipeline: tokenization, analysis, and index building. You should understand TF-IDF conceptually and be able to explain why term frequency and inverse document frequency matter for relevance. Common questions include: ‘How would you implement autocomplete?’ (prefix matching using n-grams or tries), ‘How do you handle typos?’ (fuzzy matching with edit distance or phonetic algorithms), and ‘How do you make search results more relevant?’ (better tokenization, synonyms, boosting certain fields). Red flags: not knowing what an inverted index is, confusing indexing with querying, or suggesting scanning all documents for every query.

Senior

Senior engineers must demonstrate deep understanding of search internals and the ability to make informed trade-off decisions. You should explain BM25 scoring in detail, including why it improves on TF-IDF (saturation and length normalization). Be prepared to discuss distributed search architecture: sharding strategies (by document ID, by time, by geography), query routing, and result merging. You should understand performance optimization: posting list compression, query caching, index warming, and shard allocation. Expect questions about scaling: ‘How would you design search for 1 billion documents with 10,000 queries per second?’ (horizontal sharding, replication, caching, query optimization). You should discuss real-time indexing challenges: how to make new documents searchable quickly without rebuilding the entire index (segment-based architecture, refresh intervals). Be ready to compare search technologies (Elasticsearch vs. Solr vs. custom solutions) and explain when to choose each. Red flags: not understanding BM25, inability to explain distributed search architecture, or suggesting naive approaches that don’t scale.

Staff+

Staff+ engineers must demonstrate mastery of search system design at scale and the ability to make strategic technology decisions. You should explain advanced topics: multi-stage ranking (retrieval → scoring → re-ranking), machine learning integration (learning-to-rank models, embeddings), and hybrid search (combining keyword and vector search). Be prepared to discuss operational challenges: index corruption and recovery, zero-downtime reindexing, cross-datacenter replication, and cost optimization (hot/cold storage tiers). You should understand search quality metrics (precision, recall, NDCG, MRR) and how to measure and improve them. Expect questions about architectural decisions: ‘When would you build a custom search system vs. using Elasticsearch?’ (at Google/Twitter scale, or for specialized requirements like sub-millisecond latency). You should discuss emerging trends: vector search for semantic matching, real-time personalization, and federated search across multiple indexes. Be ready to explain how search systems interact with other components: caching layers, recommendation systems, and analytics pipelines. Red flags: inability to discuss trade-offs at scale, lack of operational experience, or not understanding when off-the-shelf solutions are sufficient vs. when custom solutions are needed.

Common Interview Questions

Explain how an inverted index works and why it’s faster than scanning documents. (Answer: Maps terms to document IDs for O(1) lookup vs. O(N) scan. Enables instant retrieval of candidate documents.)

How would you implement search for an e-commerce site with 10M products? (Answer: Elasticsearch with sharding, BM25 scoring, field boosting for title/brand, faceted search for filters, autocomplete with n-grams.)

What’s the difference between TF-IDF and BM25? (Answer: BM25 adds term frequency saturation and document length normalization, preventing long documents from dominating results.)

How do you make new documents searchable in real-time? (Answer: Two-tier architecture with in-memory buffer index for recent docs and on-disk index for older docs, merged at query time.)

How would you handle typos in search queries? (Answer: Fuzzy matching with edit distance, phonetic algorithms like Soundex, or n-gram indexing for substring matching.)

Design a distributed search system for 1B documents. (Answer: Horizontal sharding by document ID, replicas for availability, query coordinator for fan-out/merge, caching for hot queries.)

Red Flags to Avoid

Not knowing what an inverted index is or how it differs from a forward index

Suggesting scanning all documents for every query without understanding the performance implications

Confusing indexing (building the index) with querying (searching the index)

Not understanding basic relevance scoring (TF-IDF or BM25) or why it matters

Inability to explain how distributed search systems shard and merge results

Not considering trade-offs between indexing latency, query performance, and storage

Suggesting building a custom search system when Elasticsearch would suffice

Not understanding when to use search vs. vector databases vs. relational databases

---

Key Takeaways

Inverted indexes map terms to document IDs, enabling O(1) lookup instead of O(N) document scans. This fundamental data structure powers all modern search systems, from Google to Elasticsearch, by transforming search from ‘scan every document’ to ‘lookup posting lists and merge’.

BM25 is the modern relevance scoring standard, improving on TF-IDF with term frequency saturation and document length normalization. It prevents long documents from dominating results simply by repeating terms, and is the default algorithm in Elasticsearch and Solr.

Search systems balance three competing goals: indexing throughput (how fast you can add documents), query latency (how fast you can search), and storage efficiency (how much disk space you need). Optimizing one often degrades the others, requiring careful trade-offs based on use case requirements.

Distributed search scales horizontally through sharding, with each shard holding a subset of documents and processing queries independently. Query throughput scales linearly with shard count, but latency is limited by the slowest shard, requiring sophisticated load balancing at scale.

Real-time search uses two-tier architecture: a small in-memory index for recent documents (updated in real-time) and a large on-disk index for older documents (updated periodically). Queries search both and merge results, enabling sub-second indexing latency while maintaining query performance.

---