Search Engines & Full-Text Search

Building Your First Search Experience

You’re launching an e-commerce platform with three million products. A customer types “comfortable running shoes for flat feet” and expects relevant results in milliseconds. Your first instinct? Query your PostgreSQL database with:

SELECT * FROM products WHERE description LIKE '%running shoes%' LIMIT 20;

This works fine for thousands of rows. For millions? You’re looking at a sequential scan. Performance tanks. Worse, the query misses synonyms (“sneakers,” “trainers”), typos (“runniing”), and has no concept of relevance—a shoe made of rubber that happens to mention “running shoes” in a review ranks the same as an actual running shoe.

This is the gap that search engines fill. They’re not traditional databases. They’re purpose-built systems for finding needles in massive haystacks, ranking results by relevance, handling typos, and delivering results in milliseconds.

In this chapter, we’ll explore how search engines work, why they’re different from your primary data store, and when (and when not) to use them.

What Full-Text Search Actually Is

Full-text search breaks free from exact matching. Instead of “does this row match this pattern?”, it asks “how relevant is this document to this query?” and ranks results accordingly.

Let’s start with the fundamental data structure: the inverted index. If a normal database indexes by document -> words, an inverted index flips the relationship:

word → [list of documents containing that word]

When you search for “running shoes,” the engine:

Finds all documents containing “running”
Finds all documents containing “shoes”
Combines results (intersection, union, or phrase proximity depending on query type)
Scores and ranks them using relevance algorithms

Before indexing, text goes through analysis:

Tokenization: Split “comfortable running shoes” into tokens: [“comfortable”, “running”, “shoes”]
Lowercasing: Ensure “Running” and “running” are the same token
Stop word removal: Words like “the,” “a,” “for” often don’t add value; skip them
Stemming/Lemmatization: Reduce words to their root form. “Running,” “runs,” “ran” all become “run”

This preprocessing is where search engines handle the quirks that make searching hard.

The Library Card Catalog Analogy

Imagine a library before computers. To find books on gardening, you’d:

Walk to the card catalog
Look up “gardening” -> see cards pointing to shelf locations
Notice the catalog also points you to cards labeled “garden,” “gardens,” “horticulture” (all related)
Pull books from those shelves

You didn’t read every book to find gardening books. You used an index.

An inverted index in a search engine is exactly this. The “cards” are index entries. The “shelves” are document IDs or positions. The catalog’s ability to connect “gardening” and “gardens”? That’s stemming. The cross-references between related terms? That’s synonym expansion.

The key insight: a search engine trades write complexity for read speed. Building that card catalog takes time (indexing). But finding books is instant (querying). In systems with millions of documents, this trade-off is essential.

Inside a Search Engine: Elasticsearch and Friends

Modern search engines like Elasticsearch, OpenSearch, and Apache Solr share common architecture:

The Cluster Model

┌─────────────────────────────────┐
│  Search Cluster                 │
├─────────────────────────────────┤
│  ┌──────────────┐              │
│  │ Node 1       │              │
│  │ ┌──────────┐ │              │
│  │ │ Shard 0  │ │              │
│  │ │ (Primary)│ │              │
│  │ └──────────┘ │              │
│  │ ┌──────────┐ │              │
│  │ │ Shard 2  │ │              │
│  │ │(Replica) │ │              │
│  │ └──────────┘ │              │
│  └──────────────┘              │
│                                 │
│  ┌──────────────┐              │
│  │ Node 2       │              │
│  │ ┌──────────┐ │              │
│  │ │ Shard 1  │ │              │
│  │ │ (Primary)│ │              │
│  │ └──────────┘ │              │
│  │ ┌──────────┐ │              │
│  │ │ Shard 0  │ │              │
│  │ │(Replica) │ │              │
│  │ └──────────┘ │              │
│  └──────────────┘              │
│                                 │
│  ┌──────────────┐              │
│  │ Node 3       │              │
│  │ ┌──────────┐ │              │
│  │ │ Shard 2  │ │              │
│  │ │(Replica) │ │              │
│  │ └──────────┘ │              │
│  │ ┌──────────┐ │              │
│  │ │ Shard 1  │ │              │
│  │ │(Replica) │ │              │
│  │ └──────────┘ │              │
│  └──────────────┘              │
└─────────────────────────────────┘

An index is divided into shards (partitions), each living on different nodes. Replicas provide redundancy. This is the scatter-gather pattern in action: a query hits every shard in parallel, each searches locally, results merge at the coordinator node.

The Indexing Pipeline

When you index a document:

Document (raw JSON)
  ↓
Analyzer (language-specific rules)
  ↓
Tokenizer ("comfortable running shoes" → ["comfortable", "running", "shoes"])
  ↓
Token Filters (lowercase, remove stop words, stem)
  ├→ "comfortable" (pass through)
  ├→ "running" → "run" (stemmed)
  └→ "shoes" → "shoe" (stemmed)
  ↓
Inverted Index
  {
    "comfortable": [doc_1, doc_5, ...],
    "run": [doc_1, doc_2, doc_3, ...],
    "shoe": [doc_1, doc_2, doc_4, ...]
  }

This happens once at index time. Search is fast because we’re working with pre-processed data.

Relevance Scoring: TF-IDF and BM25

Two algorithms dominate relevance scoring:

TF-IDF (Term Frequency x Inverse Document Frequency):

Score(doc, term) = TF(term in doc) x IDF(term in collection)

Where:
TF = how often the term appears in this document
IDF = log(total documents / documents containing term)

If “running” appears 10 times in a product and in 50% of all products, TF-IDF would be:

TF: 10 (or normalized: 10/total_words_in_doc)
IDF: log(1,000,000 / 500,000) ≈ 0.7
Score: ~7 (normalized)

Common words have low IDF (they’re in half of all docs), so they contribute less. Rare words have high IDF.

BM25 (used by Elasticsearch by default) improves on TF-IDF:

Score(doc, term) = IDF(term) x (
  (TF(term) x (k1 + 1)) / (TF(term) + k1 x (1 - b + b x (doc_length / avg_doc_length)))
)

Where:
k1 ≈ 1.2 (saturation parameter—diminishing returns after a point)
b ≈ 0.75 (length normalization)

Why the complexity? Because in real data, term frequency doesn’t scale linearly. If “running shoes” appears 1 time, it’s important. If it appears 100 times, we shouldn’t boost the score 100x—that’s diminishing returns. BM25 bakes this in.

Pro Tip: Field boosting lets you say “matches in the product name count 10x more than matches in the description.” You’d configure: "name": { "type": "text", "boost": 10 }.

Query Types

Elasticsearch supports multiple query types:

// Match query: "running shoes" (flexible matching)
{
  "query": {
    "match": {
      "description": {
        "query": "running shoes",
        "operator": "and",
        "fuzziness": "AUTO"
      }
    }
  }
}

// Phrase query: exact phrase in order
{
  "query": {
    "match_phrase": {
      "description": "comfortable running shoes"
    }
  }
}

// Boolean query: combine multiple conditions
{
  "query": {
    "bool": {
      "must": [
        { "match": { "description": "running shoes" } }
      ],
      "filter": [
        { "range": { "price": { "lte": 150 } } },
        { "term": { "in_stock": true } }
      ],
      "should": [
        { "match": { "brand": "Nike" } }
      ],
      "minimum_should_match": 0
    }
  }
}

// Fuzzy query: handles typos
{
  "query": {
    "fuzzy": {
      "product_name": {
        "value": "runniing",
        "fuzziness": "1"
      }
    }
  }
}

The bool query is powerful: must clauses must match (AND), should clauses boost if matched (OR), filter clauses must match but don’t affect scoring, and must_not excludes results.

Near-Real-Time Search

Elasticsearch doesn’t index documents instantly. Every few seconds (default: 1 second), it refreshes: segments of the inverted index become searchable. This trade-off—eventual consistency for throughput—is fundamental.

You can force immediate visibility with a flush, but that’s expensive. Most use cases accept the slight lag.

Search Engine Comparison

Aspect	Elasticsearch	OpenSearch	Apache Solr	Meilisearch	Typesense
Setup Complexity	Moderate	Moderate	High	Low	Low
Scaling Model	Horizontal (shards/replicas)	Horizontal	Horizontal	Limited	Limited
Query Language	JSON DSL	JSON DSL	Lucene syntax	Simple JSON	Simple JSON
Relevance Tuning	Advanced (BM25, field boost, function score)	Advanced	Advanced	Limited	Good
Full-Text Features	Excellent	Excellent	Excellent	Good	Good
Typo Tolerance	Yes (fuzzy)	Yes	Yes	Native	Native
Autocomplete	Via prefix queries	Via prefix queries	Via edge-gram filter	Native	Native
Cost at Scale	High (memory-intensive)	High	Moderate	Low	Low
Operational Overhead	High	High	High	Low	Low
Best For	Enterprise, complex search	Enterprise (Elasticsearch alternative)	Complex search, Lucene fans	Simple SAAS	Real-time, hosted

Real-World Example: E-Commerce Product Search

Your index might look like:

{
  "settings": {
    "number_of_shards": 5,
    "number_of_replicas": 1,
    "analysis": {
      "analyzer": {
        "product_analyzer": {
          "type": "custom",
          "tokenizer": "standard",
          "filter": ["lowercase", "stop", "snowball"]
        }
      }
    }
  },
  "mappings": {
    "properties": {
      "product_name": {
        "type": "text",
        "analyzer": "product_analyzer",
        "boost": 10
      },
      "description": {
        "type": "text",
        "analyzer": "product_analyzer"
      },
      "brand": {
        "type": "keyword"
      },
      "category": {
        "type": "keyword"
      },
      "price": {
        "type": "float"
      },
      "in_stock": {
        "type": "boolean"
      },
      "rating": {
        "type": "float"
      },
      "created_at": {
        "type": "date"
      }
    }
  }
}

Notice: product_name is boosted 10x (matches there matter more), brand and category are keywords (exact matching, used for filtering, not scoring), numeric fields enable range filters.

A complex query:

{
  "query": {
    "bool": {
      "must": [
        {
          "multi_match": {
            "query": "comfortable running shoes",
            "fields": ["product_name^10", "description", "brand"],
            "type": "best_fields"
          }
        }
      ],
      "filter": [
        { "range": { "price": { "lte": 150 } } },
        { "term": { "in_stock": true } },
        { "terms": { "category": ["athletic", "footwear"] } }
      ],
      "should": [
        { "range": { "rating": { "gte": 4 } } }
      ]
    }
  },
  "aggs": {
    "brands": {
      "terms": { "field": "brand", "size": 10 }
    },
    "price_ranges": {
      "range": {
        "field": "price",
        "ranges": [
          { "to": 50 },
          { "from": 50, "to": 100 },
          { "from": 100, "to": 150 }
        ]
      }
    }
  }
}

This query finds products matching the search terms, filters by price and availability, boosts highly-rated products, and returns facets (aggregations) for filtering.

Handling Typos: Fuzzy Matching and Edit Distance

Users type “runniing” instead of “running.” How do we still find relevant results?

Edit distance (Levenshtein distance) measures how many single-character edits (insertions, deletions, substitutions) are needed to transform one word into another:

"running" -> "runniing" = 1 insertion = distance 1
"nike" -> "nike" = 0 = distance 0
"shoe" -> "shoe" = 0 = distance 0
"comfort" -> "comfert" = 1 substitution = distance 1

Elasticsearch allows fuzziness: 1 or fuzziness: 2 for typo tolerance. Higher values match more, but slower and less relevant.

For autocomplete, consider edge-grams: index substrings.

"running shoes" ->
Tokens: ["r", "ru", "run", "runn", "runni", "runnin", "running", "s", "sh", "sho", "shoe", "shoes"]

User types “runn” -> instantly matches edge-gram, returns “running shoes” as top result.

Distributed Search: The Scatter-Gather Pattern

When a query arrives:

Query Request
  ↓
Coordinator Node
  ├→ Send query to Shard 0 (on Node 1)
  ├→ Send query to Shard 1 (on Node 2)
  ├→ Send query to Shard 2 (on Node 3)
  ↓
Each shard searches locally, returns top-K results
  ↓
Coordinator merges and re-ranks results
  ↓
Return top results to client

This is embarrassingly parallel—each shard is independent. With 5 shards, a query touching all of them runs in parallel, achieving single-digit millisecond latency even across millions of documents.

The Cost of Change: Updates and Deletes

Search engines don’t delete documents instantly. Elasticsearch uses soft deletes and segment merging:

When you delete a document, it’s marked as deleted (not removed)
Search queries skip deleted documents (they have a filter applied)
Periodically, segments merge, physically removing deleted documents
This process (garbage collection) frees disk space

Did You Know? If you have a high update rate (say, millions of updates per day), the garbage collection overhead can become significant. Some teams run nightly reindex jobs to rebuild the index from a source-of-truth database.

PostgreSQL Full-Text Search: A Simpler Alternative

For smaller datasets or simpler requirements, PostgreSQL’s built-in tsvector and tsquery might suffice:

-- Create a full-text search column
ALTER TABLE products ADD COLUMN search_index tsvector;

-- Populate it with tokenized text
UPDATE products SET search_index =
  to_tsvector('english', product_name || ' ' || description);

-- Create a GiST index for faster searches
CREATE INDEX idx_search ON products USING GiST (search_index);

-- Query
SELECT * FROM products
WHERE search_index @@ to_tsquery('english', 'running & shoes')
ORDER BY ts_rank(search_index, query) DESC;

Pros: No external dependency, transactional consistency, simple. Cons: Limited to single node (no sharding), slower on millions of documents, weaker relevance tuning.

Key Takeaways

Inverted indexes flip the lookup: word -> documents, enabling fast full-text search at scale.
Analysis (tokenization, stemming, lowercasing) handles language complexity before indexing.
BM25 scoring balances term frequency and rarity, outperforming simpler TF-IDF in real data.
Sharding and replicas let you scale searches horizontally across a cluster.
Near-real-time indexing (refresh intervals) trades immediate consistency for throughput.

Practice Scenarios

Scenario 1: Autocomplete at Scale You need to autocomplete product searches while users type. 10 million products, 1,000 QPS, latency under 50ms. Design the indexing strategy (edge-grams vs. prefix queries) and query execution (single-node coordinator vs. distributed).

Scenario 2: Multi-Language Search Your platform operates in 8 languages. Users search for products in any language, expecting relevant results even for synonyms and typos. Design the analyzer configuration and index structure.

Search engines excel at full-text, but struggle with relationships. Next chapter, we’ll explore graph databases to model and query interconnected data efficiently.

⚡

Revision Mode Active Condensed for 5-minute review. Focused on 30-second pitches, mental anchors, and high-frequency interview traps.

⚡ 30-Second Elevator Pitch

“Search Engines (Elasticsearch, OpenSearch, Apache Solr) accelerate unstructured text queries using an Inverted Index—a mapping of normalized tokens (stems) to document IDs. Instead of expensive $O(N)$ SQL LIKE '%term%' full table scans, search engines execute $O(1)$ token lookups across Lucene index segments, scoring documents by relevance using the Okapi BM25 algorithm (balancing Term Frequency and Inverse Document Frequency).”

🧠 Under The Hood & Mental Model

The Inverted Index Data Structure:
- Forward Index (RDBMS): DocID -> [Term1, Term2, Term3].
- Inverted Index (Search Engine): Term -> [Doc1, Doc3, Doc9] + Term Frequency + Byte Positions.
The Text Analysis Pipeline:
1. Character Filter: Strips HTML tags (<b> $\rightarrow$ plain text).
2. Tokenizer: Splits text stream into individual word tokens on whitespace/punctuation.
3. Token Filters: Lowercases, removes Stop Words (the, is, at), applies Stemming (reduces running, runs $\rightarrow$ run).
Okapi BM25 Relevance Scoring:
- Compares Term Frequency (TF) (how often a word appears in a doc) against Inverse Document Frequency (IDF) (how rare the word is across the whole index). Implements non-linear TF saturation to prevent keyword-stuffing gaming.
Near-Real-Time (NRT) Indexing & Lucene Segments:
- Writes buffer in memory (RAM buffer) and flush to immutable disk Lucene Segments every second (refresh_interval). Soft-deleted documents remain on disk until background Segment Merging cleans them.

💻 High-Yield Code & Gotcha

// Elasticsearch Compound Bool Query with Field Boosting & Filtering
GET /products/_search
{
  "query": {
    "bool": {
      "must": [
        {
          "multi_match": {
            "query": "running shoes",
            "fields": ["product_name^5", "description"], 
            "fuzziness": "AUTO"
          }
        }
      ],
      "filter": [
        { "term": { "status": "active" } },
        { "range": { "price": { "lte": 120 } } }
      ]
    }
  }
}

⚠️ GOTCHA: Using Text Fields for Exact Grouping/Sorting (Fielddata RAM Explosion)

// ❌ Error: Anti-Pattern (Aggregating or sorting directly on an analyzed "text" field)
// Forces Elasticsearch to build in-memory Fielddata data structures, consuming gigabytes of heap RAM!

// ✅ Safe: Idiomatic Pattern (Use multi-fields: "text" for full-text search, "keyword" for exact sorting)
"mappings": {
  "properties": {
    "brand": {
      "type": "text",
      "fields": { "raw": { "type": "keyword" } }
    }
  }
}
// Sort by brand.raw instead!

⚖️ Trade-Offs & Comparison

Metric / Aspect	Relational DB (`LIKE '%term%'`)	Search Engine (Elasticsearch / OpenSearch)
Primary Data Structure	B-Tree / Heap Page	Inverted Index (Lucene Segments)
Search Mechanism	Full Table Sequential Scan ($O(N)$)	Token Inverted Index Lookup ($O(1)$)
Relevance & Scoring	None (Binary Match: Yes/No)	Okapi BM25 / TF-IDF Vector Relevance
Typo Tolerance & Stemming	Manual (`ILIKE` regex)	Native Fuzzy Levenshtein Distance & Stemmers
Write / Update Overhead	Low (Single row write)	High (NRT Segment Refresh & Segment Merging)

🌟 My Experience (STAR Anchor)

“Engineered the catalog search engine for a retail platform with 5M SKUs. Replacing SQL LIKE queries with an Elasticsearch cluster utilizing custom analyzers, edge-ngram tokenizers for instant autocomplete, and BM25 field boosting (name^5, category^2) reduced P99 search latency from 4.2s to 18ms while boosting conversion rates by 22% via instant typo-tolerant search results.”

System Design Fundamentals