25. Search Systems: Inverted Index, Elasticsearch

"Find documents matching this query, ranked by relevance" is a deceptively complex problem. The inverted index is the foundational data structure; modern search systems layer ranking, filtering, and faceting on top.

25.1 The inverted index

The core idea: for each term (word, token), store the list of documents containing it.

Documents:
  d1: "the cat sat on the mat"
  d2: "the dog barked"

Inverted index:
  "the"    → [d1, d2]
  "cat"    → [d1]
  "sat"    → [d1]
  "on"     → [d1]
  "mat"    → [d1]
  "dog"    → [d2]
  "barked" → [d2]

Query "cat dog" → intersect([d1], [d2]) = []. Query "cat" OR "dog" → union = [d1, d2].

The lists are called postings lists. Often sorted by document ID for fast intersection.

Augmenting postings

Each posting often stores more than doc ID:

• Position(s) of the term in the document → enables phrase queries ("cat sat").
• Term frequency → enables relevance scoring.
• Field info (title vs body) → field-weighted scoring.

25.2 Tokenization

Turning raw text into terms. Surprisingly hard.

• Whitespace split (basic).
• Lowercasing.
• Stop word removal ("the," "a," "and"). Optional; modern engines often keep them but weight low.
• Stemming: reduce inflections ("running" → "run"). Porter, Snowball.
• Lemmatization: dictionary-based, more accurate than stemming, slower.
• N-grams: split into character or word n-grams. Used for typo tolerance, language ID, autocomplete.
• Synonyms: "car" ≡ "automobile". Maintained in synonym dictionaries.
• Language-specific: Chinese has no spaces; needs ICU tokenizer or custom.

Different fields can have different analyzers (e.g., title: phrase + ngram, body: standard).

25.3 Relevance scoring

Just "does the doc contain the term" isn't enough. We need ranking.

TF-IDF

• TF (term frequency): how often term appears in doc. Higher = more relevant.
• IDF (inverse doc frequency): log(N / df), where df is docs containing the term. Common terms ("the") get low IDF; rare terms get high.
• TF-IDF score = TF × IDF.

BM25

Modern improvement; the default in Lucene/Elasticsearch.

• Saturates TF (extra repetitions matter less).
• Normalizes by document length.
• Tunable parameters (k1, b).

Field weighting

Title match scores more than body match. Boost factors per field.

Custom signals

• Recency: boost recent docs.
• Popularity: clicks, ratings, in-links.
• User signals: personalization features.
• Editorial boost: pin specific results.

In real search systems (Google, Bing), BM25 is one of hundreds of signals fed into a learned model.

25.4 Vector / semantic search

Embeddings (from BERT, sentence-transformers, OpenAI ada) → high-dimensional vectors. Similarity = cosine of vector dot product.

• "find documents similar in meaning to this query."
• Works across paraphrases ("how do I cancel" vs "subscription cancellation").

Approximate Nearest Neighbor (ANN)

Brute-force similarity is O(N×D). At scale, use ANN:

• HNSW (Hierarchical Navigable Small World): graph-based; current SOTA on speed/recall trade-off.
• IVF (Inverted File Index): cluster vectors; search nearest clusters.
• PQ (Product Quantization): compress vectors for memory.

Tools: Pinecone, Weaviate, Milvus, Qdrant, pgvector, Vespa, Elasticsearch with k-NN, Lucene 9+ vector support.

Hybrid search

Combine BM25 (lexical) + vector (semantic) for best results. Most modern search products (RAG systems, Notion AI, Algolia) do this.

25.5 Elasticsearch / OpenSearch

The dominant search engine in industry. Built on Lucene (the underlying inverted index library).

Architecture

• Cluster: many nodes.
• Node roles: master (coordinates), data (holds shards), client/coordinating, ingest.
• Index: a logical search index. Partitioned into shards. Each shard is a Lucene index.
• Replicas: copies of shards for redundancy and read scale.

Sharding

• Documents hash to shards by routing key (default: _id).
• Number of primary shards is fixed at index creation. Plan capacity carefully.
• Reindex (with new shard count) is the way to "reshard."

Querying

• Query DSL: JSON-based query language. Match, term, range, bool, function_score.
• Multi-search: batch many queries.
• Aggregations: faceted search, histograms, stats.

Updates

• Documents are immutable in Lucene. "Update" = mark old as deleted + insert new.
• Periodic merge consolidates segments and physically removes deletions.
• Refresh interval (default 1 sec) controls how soon writes are visible to search. Tune up for write-heavy workloads.

Indexing pipeline

• Ingest pipeline: enrichment, transformation.
• Mapping: schema (field types, analyzers).
• Bulk API for high-throughput inserts.

Real-world ops

• Plan shard count (each shard 10-50 GB target).
• Hot-warm-cold tiers: recent data on fast SSDs (hot), older on cheaper disks (warm), archive in object storage (cold). Index Lifecycle Management (ILM) handles transitions.
• JVM heap: 50% of RAM, capped at 32 GB (compressed oops).
• Watch for "red" cluster (missing shards), "yellow" (replicas missing).

Other options

• OpenSearch: AWS fork after Elastic license change.
• Solr: older Lucene-based, still in use.
• Vespa (Yahoo, now open source): big-data ranking + ML.
• Meilisearch / Typesense: lightweight, fast for medium scale.
• Algolia: hosted, blazing fast, expensive.

25.6 Index update patterns

Sync from source DB

• App updates DB; same code updates ES. Risk: dual-write inconsistency.
• Better: outbox pattern → CDC → indexer → ES.

Reindexing

• Periodic full rebuild (nightly).
• Or build new index alongside, alias-swap when ready (zero-downtime reindex).

Streaming updates

• Real-time CDC (Debezium → Kafka → ES Sink Connector).
• Lag of seconds.

25.7 Autocomplete / typeahead

(See chapter 39.) Common implementations:

• Prefix tree (trie) in memory: each node has children for next char + popular completions.
• Edge n-gram tokenizer: index every prefix as a token in ES.
• Completion suggester (ES feature): FST-based, very fast.

Hot terms cached aggressively; debounce client-side to avoid query per keystroke.

25.8 Faceted search

"Filter by category, brand, price range, with counts per facet."

• Terms aggregation (count docs per category).
• Range aggregation (count per price band).
• Filter context (cheap; doesn't affect score).

The faceted search experience is a big part of e-commerce UX.

25.9 Geosearch

(Also chapter 35, 40.)

• Geo-point field type: lat/lon.
• geo_distance query: within R of a point.
• geo_bounding_box query: within a rectangle.
• geohash grid aggregation: cluster on a map.

Underlying: Lucene uses geohash + R-tree variants.

25.10 Ranking pipelines

Production search has stages:

1. Retrieve candidates (1000s) via BM25 + vector + filters.
2. Re-rank (top 100) with a heavier model (neural, learning-to-rank).
3. Personalize (top 10) with user features.
4. Diversify (avoid showing 10 versions of same item).
5. Apply business rules (sponsored, editorial pin).

This pipeline is the heart of Google Search, YouTube recommendations, Amazon search.

25.11 Search at Google scale

Google's index: trillions of docs, refreshed continuously.

• Caffeine: real-time indexing pipeline (replaced batch in 2010).
• Spanner / Bigtable: storage layers.
• MapReduce / Borg / Flume: processing.
• PageRank + ~200 ranking signals + ML.
• Tensor Processing Units (TPUs): serve heavy neural rankers.

Not the kind of system you build in an interview. But you'll be expected to talk about: inverted index, ranking, sharding, query latency budgets, freshness pipelines.

25.12 Designing a search system in interview

Key sections:

1. Functional requirements: what queries? What facets? Real-time freshness?
2. Index storage: sharding strategy, replicas.
3. Indexing pipeline: source → outbox → Kafka → indexer → ES.
4. Query path: API → ES coordinator → shards → merge → return.
5. Ranking: lexical + semantic + business signals.
6. Latency budget: P99 < 200 ms typically.
7. Caching: query-result cache, autocomplete cache.

25.13 Common pitfalls

• Single shard for everything: hot shard, can't scale.
• No replicas: index goes red on node failure.
• Indexing in the request path: write spike crashes ES.
• No analyzers tuned for the domain: search quality bad.
• Over-faceting: too many facets crash aggregation.
• Trying to use ES as a primary DB: it's a search index, not a source of truth.

Key takeaways

• Inverted index = foundation: term → postings list.
• BM25 = modern relevance baseline.
• Vector search complements lexical for semantic understanding.
• Elasticsearch / OpenSearch for production search at scale.
• Plan shards before launch; reindex is painful.
• Real search has retrieve → rerank → personalize → diversify pipelines.