Chapter 16: Search Systems

Modern search systems power everything from e-commerce to log analysis. This chapter covers inverted indexes, scoring algorithms, Elasticsearch architecture, and search at scale.

1. Inverted Index

The fundamental data structure for full-text search. Maps terms to document IDs where they appear.

Structure

Component Purpose Example
Term Dictionary Sorted list of all unique terms "elasticsearch", "search", "system"
Posting List Document IDs containing term "search" → [doc1, doc5, doc12]
Term Frequency (TF) Count of term in each doc doc1: 3, doc5: 1, doc12: 7
Positional Index Positions within document doc1: [0, 15, 42] (word positions)
Field Data Per-field indexing title:search vs body:search

Inverted Index Structure

graph TB
    subgraph Documents
        D1["Doc 1: 'quick brown fox'"]
        D2["Doc 2: 'quick blue fox'"]
        D3["Doc 3: 'brown dog'"]
    end

    subgraph "Inverted Index"
        T1["brown → [1,3]"]
        T2["blue → [2]"]
        T3["dog → [3]"]
        T4["fox → [1,2]"]
        T5["quick → [1,2]"]
    end

    subgraph "Posting Lists with TF & Positions"
        P1["brown:
doc1(tf=1, pos=[1])
doc3(tf=1, pos=[0])"]
        P2["quick:
doc1(tf=1, pos=[0])
doc2(tf=1, pos=[0])"]
    end

    D1 --> T1
    D1 --> T4
    D1 --> T5
    D2 --> T2
    D2 --> T4
    D2 --> T5
    D3 --> T1
    D3 --> T3

    T1 --> P1
    T5 --> P2

    style T1 fill:#e3f2fd
    style T5 fill:#e3f2fd
    style P1 fill:#fff3e0
    style P2 fill:#fff3e0

Building an Inverted Index

Step 1: Tokenization "The quick brown fox" → ["the", "quick", "brown", "fox"] Step 2: Normalization Lowercase, stemming, stop words ["quick", "brown", "fox"] Step 3: Create Postings Term → (DocID, Frequency, Positions) quick → (1, 1, [0]) brown → (1, 1, [1]) fox → (1, 1, [2]) Step 4: Merge & Sort Sort by term, compress posting lists
Interview Tip: Explain why inverted indexes are O(1) for term lookup (hash/trie) but O(k) for intersection (k = posting list size). Mention compression techniques like delta encoding and bit packing for posting lists.

2. Scoring Algorithms

Ranking documents by relevance to a query.

TF-IDF (Term Frequency - Inverse Document Frequency)

TF-IDF(t, d) = TF(t, d) × IDF(t) TF(t, d) = count of term t in document d IDF(t) = log(N / df(t)) where N = total documents, df(t) = documents containing term t Example: Query: "elasticsearch performance" Doc1: contains "elasticsearch" 5 times, "performance" 2 times Total docs: 10,000 Docs with "elasticsearch": 500 Docs with "performance": 2000 TF-IDF(elasticsearch, doc1) = 5 × log(10000/500) = 5 × 3 = 15 TF-IDF(performance, doc1) = 2 × log(10000/2000) = 2 × 1.6 = 3.2 Final score = 15 + 3.2 = 18.2

BM25 (Best Match 25)

BM25(d, q) = Σ IDF(qi) × [f(qi,d) × (k1+1)] / [f(qi,d) + k1 × (1 - b + b × |d|/avgdl)] Where: qi = query term i f(qi,d) = frequency of qi in document d |d| = document length avgdl = average document length k1 = term frequency saturation (typically 1.2-2.0) b = length normalization (typically 0.75) Key difference: Diminishing returns for term frequency (saturation)

TF-IDF vs BM25

Aspect TF-IDF BM25
Term Frequency Linear (5x term = 5x score) Saturates (diminishing returns)
Document Length No normalization Normalizes by avg length
Spam Resistance Weak (keyword stuffing works) Strong (saturation prevents)
Performance Faster (simpler math) Slightly slower
Accuracy Good baseline Better for varied doc lengths
Use Case Simple search, logs Web search, e-commerce (default)
Interview Tip: BM25 is the default in Elasticsearch since v5.0. Mention that it handles document length better (short docs not penalized, long docs not favored just for having more words). k1 controls saturation, b controls length normalization.

3. Elasticsearch Architecture

Distributed, RESTful search engine built on Apache Lucene.

Core Components

Component Description Key Points
Cluster One or more nodes with shared cluster name Distributed coordination, master election
Node Single Elasticsearch instance Master, data, ingest, coordinating roles
Index Collection of documents (like database) Settings, mappings, aliases
Shard Lucene index, horizontal partition Primary + replicas, ~50GB max per shard
Segment Immutable file in shard (mini-index) Created on refresh, merged periodically
Document JSON object with _id Indexed, stored, routed to shard

Elasticsearch Cluster Architecture

graph TB
    Client[Client Request]

    subgraph "Elasticsearch Cluster"
        CN[Coordinating Node]
        M[Master Node
Cluster State]

        subgraph "Index: products (3 shards, 1 replica)"
            subgraph "Node 1"
                P0[Primary Shard 0]
                R1[Replica Shard 1]
            end

            subgraph "Node 2"
                P1[Primary Shard 1]
                R2[Replica Shard 2]
            end

            subgraph "Node 3"
                P2[Primary Shard 2]
                R0[Replica Shard 0]
            end
        end
    end

    Client --> CN
    CN --> M
    CN --> P0
    CN --> P1
    CN --> P2

    P0 -.replicate.-> R0
    P1 -.replicate.-> R1
    P2 -.replicate.-> R2

    style M fill:#e1f5e1
    style CN fill:#e3f2fd
    style P0 fill:#fff3e0
    style P1 fill:#fff3e0
    style P2 fill:#fff3e0
    style R0 fill:#f3e5f5
    style R1 fill:#f3e5f5
    style R2 fill:#f3e5f5

Near-Real-Time Search

Operation What Happens Latency
Index Document Written to in-memory buffer + translog ~1ms
Refresh Buffer → new segment (searchable) 1s (default)
Flush Segments → disk, clear translog 30s or 512MB translog
Merge Small segments → large segments Background, throttled
Write Path: 1. Document indexed → in-memory buffer + translog (disk) 2. Refresh (every 1s) → buffer → new segment (searchable, in memory) 3. Flush (every 30s) → segments → disk, translog cleared 4. Merge (background) → segments consolidated Read Path: 1. Query → coordinating node 2. Query phase → broadcast to all shards, score top-K per shard 3. Fetch phase → retrieve full docs for global top-K 4. Return results to client
Interview Tip: Explain the 1-second delay (refresh interval) for near-real-time. Mention that translog ensures durability. Describe scatter-gather: query phase is lightweight (IDs + scores), fetch phase retrieves full docs only for final results.

4. Indexing Pipeline

How documents are processed before storage in the inverted index.

Analysis Chain

graph LR
    Input["Input Text:
'The QUICK Brown Fox!'"]

    subgraph "Analyzer = Tokenizer + Filters"
        Char[Character Filter
HTML strip, mapping]
        Token[Tokenizer
Split into tokens]
        Filter1[Token Filter 1
Lowercase]
        Filter2[Token Filter 2
Stop words]
        Filter3[Token Filter 3
Stemming]
    end

    Output["Tokens:
['quick','brown','fox']"]

    Input --> Char --> Token --> Filter1 --> Filter2 --> Filter3 --> Output

    style Input fill:#e3f2fd
    style Output fill:#e1f5e1
    style Token fill:#fff3e0

Common Analyzers & Filters

Component Examples Purpose
Tokenizer standard, whitespace, ngram, edge_ngram, pattern Split text into tokens
Lowercase Filter Quick → quick Case-insensitive search
Stop Words Remove "the", "a", "is" Reduce index size, noise
Stemming running → run, foxes → fox Match word variations
Synonyms quick → fast, rapid Expand query coverage
ASCII Folding café → cafe, ñ → n Handle accents
Character Filter HTML strip, pattern replace Clean input before tokenization

Mapping (Schema)

{ "mappings": { "properties": { "title": { "type": "text", "analyzer": "english", "fields": { "keyword": { "type": "keyword" }, // exact match "suggest": { "type": "completion" } // autocomplete } }, "price": { "type": "float" }, "published": { "type": "date" }, "category": { "type": "keyword" }, // no analysis, exact "description": { "type": "text", "analyzer": "standard", "search_analyzer": "english" // different for search } } } }

Field Types

Type Indexed Use Case
text Analyzed (tokenized) Full-text search (titles, descriptions)
keyword Not analyzed (exact) Filtering, sorting, aggregations
date Numeric (milliseconds) Time ranges, sorting by date
numeric long, float, double, etc. Range queries, math aggregations
boolean true/false Binary flags
geo_point lat/lon Geospatial search (nearby)
dense_vector Float array Semantic/vector search

Bulk Indexing

POST /_bulk { "index": { "_index": "products", "_id": "1" } } { "title": "Laptop", "price": 999 } { "index": { "_index": "products", "_id": "2" } } { "title": "Mouse", "price": 29 } Best Practices: - Batch 1000-5000 docs per request (5-15MB) - Use multiple threads (parallel bulk requests) - Disable refresh during bulk load (set to -1, re-enable after) - Monitor queue size, indexing rate - Typical: 10k-50k docs/sec per node
Interview Tip: Distinguish text (analyzed, full-text) vs keyword (exact, aggregations). Mention that multi-fields allow indexing the same content multiple ways. For bulk indexing, emphasize batching and disabling refresh for throughput.

5. Query Types

Different query DSL types for various search scenarios.

Query Type Description Use Case Example
term Exact match (no analysis) Keyword fields, IDs, enums { "term": { "status": "active" } }
match Analyzed, full-text search Text fields, user queries { "match": { "title": "quick fox" } }
match_phrase Exact phrase, order matters "machine learning", quotes { "match_phrase": { "text": "brown fox" } }
bool Combine queries (AND/OR/NOT) Complex filters, multi-criteria { "bool": { "must": [...], "filter": [...] } }
fuzzy Levenshtein distance (typos) Spelling mistakes, autocorrect { "fuzzy": { "name": { "value": "quikc" } } }
range Numeric/date ranges Price filters, date ranges { "range": { "price": { "gte": 10, "lte": 100 } } }
wildcard Pattern matching (* and ?) Partial matches, prefixes { "wildcard": { "email": "*@gmail.com" } }
prefix Starts with (optimized) Autocomplete, typeahead { "prefix": { "name": "john" } }
multi_match Search across multiple fields Search title + description { "multi_match": { "query": "laptop", "fields": ["title", "desc"] } }
nested Query nested objects Arrays of objects (comments) { "nested": { "path": "comments", "query": {...} } }

Bool Query Structure

{ "query": { "bool": { "must": [ // AND, affects score { "match": { "title": "laptop" } } ], "filter": [ // AND, no scoring (faster) { "term": { "status": "active" } }, { "range": { "price": { "lte": 1000 } } } ], "should": [ // OR, affects score (boost) { "match": { "brand": "Dell" } } ], "must_not": [ // NOT, excludes { "term": { "category": "refurbished" } } ], "minimum_should_match": 1 // at least 1 should clause must match } } } Query vs Filter Context: - Query: Affects relevance score (expensive) - Filter: Yes/no match, cached (fast) - Use filter for exact matches, ranges, binary flags
Interview Tip: Explain query vs filter context. Filters are cacheable and don't affect scoring, making them much faster for boolean conditions. Use "must" for scoring, "filter" for pure filtering.

6. Relevance Tuning

Techniques to improve search result quality.

Boosting

Query-time Boost: { "query": { "multi_match": { "query": "laptop", "fields": ["title^3", "description"] // title 3x more important } } } Index-time Boost (deprecated, use function_score): Boost documents at index time (now handled at query time)

Function Score

{ "query": { "function_score": { "query": { "match": { "title": "laptop" } }, "functions": [ { "filter": { "term": { "featured": true } }, "weight": 2 // boost featured products 2x }, { "gauss": { // decay function "published_date": { "origin": "now", "scale": "30d", "decay": 0.5 } } }, { "field_value_factor": { // use field value "field": "popularity", "factor": 1.2, "modifier": "log1p" // log(1 + popularity) } } ], "boost_mode": "multiply", // how to combine scores "score_mode": "sum" // how to combine functions } } }

Decay Functions

Function Curve Use Case
linear Straight line decay Simple distance penalty
exp Exponential decay Rapid drop-off (strict recency)
gauss Bell curve Smooth decay (recommended)

Relevance Tuning Strategies

Strategy Technique When to Use
Field Boosting title^3, tags^2 Prioritize certain fields
Recency Boost Gauss decay on date News, blog posts, time-sensitive
Popularity Boost field_value_factor on views/sales E-commerce, content platforms
Geospatial Decay Gauss on geo_point Local search, nearby results
Personalization Boost by user prefs/history Recommendations, personalized search
A/B Testing Compare scoring functions Optimize for click-through rate
Interview Tip: Mention that relevance tuning is iterative. Use Elasticsearch's "explain" API to understand scoring. Common pattern: BM25 baseline + function_score for business logic (popularity, recency, personalization).

7. Search at Scale

Handling billions of documents and thousands of queries per second.

Shard Strategies

Strategy Description Trade-offs
Few Large Shards 5 shards × 200GB each Pro: Less overhead. Con: Harder to rebalance, longer recovery
Many Small Shards 100 shards × 10GB each Pro: Better distribution. Con: Overhead, many segments
Time-based Index per day/month Pro: Easy to delete old data. Con: Many indices
Tenant-based Index per customer Pro: Isolation. Con: Uneven sizes, routing needed
Rollover Auto-create index at size/age Pro: Consistent shard sizes. Con: Complexity

Shard Sizing Guidelines

Rule of thumb: - Shard size: 20-50GB (max ~50GB) - Shards per node: < 20 per GB heap (e.g., 32GB heap → 600 shards max) - Documents per shard: Not a hard limit, depends on doc size Example calculation: 1TB index, 50GB per shard → 20 primary shards 3 nodes, 1 replica → 40 total shards → 13-14 shards per node ✓ Over-sharding symptoms: - High cluster state size (master node pressure) - Slow search (scatter-gather to too many shards) - Many small segments (merge overhead)

Routing

Default routing: shard = hash(_id) % number_of_primary_shards Custom routing: PUT /products/_doc/1?routing=user123 { "title": "Laptop", "user_id": "user123" } Query with same routing: GET /products/_search?routing=user123 Benefits: - Co-locate related docs (reduce scatter-gather) - Single-shard queries (much faster) Risk: - Unbalanced shards (hot spots)

Deep Pagination Problem

Problem with from/size: GET /products/_search { "from": 10000, // Skip 10k results "size": 10 } What happens: - Each shard returns top 10,010 results - Coordinating node sorts 10,010 × num_shards - For 10 shards: sorts 100,100 results, returns 10 (wasteful!) Solution: search_after 1. First query: GET /products/_search { "size": 10, "sort": [{"price": "asc"}] } Returns docs + last sort value [99.99] 2. Next page: GET /products/_search { "size": 10, "search_after": [99.99], "sort": [{"price": "asc"}] } Benefits: - Constant memory (no deep pagination penalty) - Stateless (no scroll context) - Live results (reflects index changes) Limit: - No random page access (can't jump to page 500)

Scatter-Gather Pattern

sequenceDiagram
    participant Client
    participant Coord as Coordinating Node
    participant S1 as Shard 1
    participant S2 as Shard 2
    participant S3 as Shard 3

    Client->>Coord: Search query (top 10)

    Note over Coord,S3: Query Phase (scatter)
    Coord->>S1: Score & return top 10 doc IDs
    Coord->>S2: Score & return top 10 doc IDs
    Coord->>S3: Score & return top 10 doc IDs
    S1-->>Coord: [id1, id5, id9...] + scores
    S2-->>Coord: [id2, id7, id11...] + scores
    S3-->>Coord: [id3, id8, id12...] + scores

    Note over Coord: Merge & sort
global top 10

    Note over Coord,S3: Fetch Phase (gather)
    Coord->>S1: Fetch full doc for id1, id5
    Coord->>S2: Fetch full doc for id2
    Coord->>S3: Fetch full doc for id3, id8
    S1-->>Coord: Full documents
    S2-->>Coord: Full documents
    S3-->>Coord: Full documents

    Coord->>Client: Final top 10 results
Interview Tip: Explain the scatter-gather problem: query phase is lightweight (IDs + scores), but fetch phase retrieves full docs. Deep pagination wastes resources in query phase. search_after solves this by using a cursor instead of offset.

8. Autocomplete

Providing instant search suggestions as users type.

Techniques Comparison

Technique How It Works Pros Cons
Edge N-grams Index prefixes: q, qu, qui, quic, quick Fast, flexible, scores by relevance Large index size
Completion Suggester FST (Finite State Transducer) in memory Extremely fast, low latency No scoring, prefix-only, limited flexibility
Prefix Query Match terms starting with prefix Simple, no special indexing Slower, no mid-word match
Search-as-you-type Combined field type (edge-ngrams + shingles) Handles multi-word, typos Complex setup

Edge N-grams Implementation

Mapping: { "settings": { "analysis": { "analyzer": { "autocomplete": { "tokenizer": "standard", "filter": ["lowercase", "autocomplete_filter"] } }, "filter": { "autocomplete_filter": { "type": "edge_ngram", "min_gram": 2, "max_gram": 10 } } } }, "mappings": { "properties": { "title": { "type": "text", "analyzer": "autocomplete", "search_analyzer": "standard" // no ngrams on query } } } } Indexing "quick": Tokens: [qu, qui, quic, quick] Query "qui": Matches "quick", "quiet", "quite"

Completion Suggester

Mapping: { "mappings": { "properties": { "suggest": { "type": "completion", "contexts": [ { "name": "category", "type": "category" } ] } } } } Index document: { "suggest": { "input": ["laptop", "notebook computer"], "weight": 10, // priority/popularity "contexts": { "category": ["electronics"] } } } Query: { "suggest": { "product-suggest": { "prefix": "lap", "completion": { "field": "suggest", "size": 5, "contexts": { "category": ["electronics"] } } } } } Response time: 1-5ms (in-memory FST)

Autocomplete Best Practices

Aspect Recommendation Why
Latency Target < 50ms Feels instant (user typing ~200ms/char)
Min Characters 2-3 characters Reduce too many matches, server load
Debouncing 100-200ms Don't query every keystroke
Caching Client + server (CDN) Popular prefixes ("a", "the") cached
Popularity Weighting Boost by click rate Show most relevant suggestions first
Context Filtering Category, location, user Personalized, relevant suggestions
Interview Tip: Compare edge n-grams (flexible, scored) vs completion suggester (faster, simpler). Mention that search-as-you-type field type (ES 7.2+) combines edge n-grams and shingles for multi-word autocomplete. Always debounce on client side.

10. Search Alternatives Comparison

Choosing the right search engine for your use case.

Engine Core Strength Architecture Scale Best For
Elasticsearch Full-featured, analytics, logs Lucene, distributed, near-RT Billions of docs, PB scale Enterprise search, logs, APM, complex queries
Solr Mature, stable, XML config Lucene, distributed Billions of docs Enterprise search, libraries, faceting
Meilisearch Fast, typo-tolerant, simple Rust, single-node Millions of docs Website search, small apps, instant results
Typesense Typo-tolerance, instant search C++, clustered Millions-billions of docs E-commerce, autocomplete, geo search
Algolia Hosted, fast, global CDN C++, distributed (SaaS) SaaS limits E-commerce, mobile apps, instant search
OpenSearch Elasticsearch fork (Apache 2.0) Lucene, distributed Billions of docs Same as ES, open-source purists
Vespa Real-time ML, recommendations Yahoo origin, distributed Billions of docs ML-powered search, personalization

Detailed Comparison

Feature Elasticsearch Solr Meilisearch Typesense Algolia
Setup Complexity Medium High Low Low Lowest (SaaS)
Query DSL JSON, powerful XML/JSON, complex Simple REST Simple REST Simple REST
Typo Tolerance Fuzzy queries (manual) Manual Built-in, automatic Built-in, automatic Built-in, automatic
Vector Search Yes (HNSW) Yes (plugin) No (roadmap) Yes (alpha) Limited
Aggregations Extensive Facets, extensive Basic facets Facets, grouping Facets
Real-time Near (1s refresh) Near (soft commit) Instant Instant Instant
Geo Search Yes (geo_point) Yes Yes Yes (strong) Yes (strong)
Multi-tenancy Index per tenant or field Collection per tenant Index per tenant Collection per tenant Index per tenant
Cost Self-hosted (infra) or Elastic Cloud Self-hosted Self-hosted or cloud Self-hosted or cloud Pay per operation (expensive)
Language Java Java Rust C++ C++
License SSPL (v7.11+) / Elastic Apache 2.0 MIT GPL v3 (self-host free) Proprietary (SaaS)

Selection Criteria

Use Case Recommended Why
Log Analytics Elasticsearch / OpenSearch Time-series optimization, Kibana, aggregations
E-commerce Search Typesense / Algolia Fast autocomplete, typo-tolerance, faceting
Enterprise Search Elasticsearch / Solr Complex queries, security, scale
Simple Website Search Meilisearch Easy setup, fast, typo-tolerant, affordable
Mobile App Search Algolia Global CDN, instant results, managed
Semantic/Vector Search Elasticsearch / Vespa HNSW support, hybrid search
Recommendations Vespa ML models, personalization, real-time
Open Source (no restrictions) OpenSearch / Solr / Meilisearch Apache 2.0 / MIT licenses
Interview Tip: For "design a search system" questions, start with requirements (scale, latency, features). Elasticsearch is the safe default for most cases. Mention simpler alternatives for smaller scale or specific needs (e.g., Meilisearch for < 10M docs, Algolia for managed/global). Discuss trade-offs: operational complexity vs features vs cost.

Key Takeaways