Full-Text Search and the Inverted Index

Full-text search finds documents containing words, ranks them by relevance, and does it in milliseconds over millions of documents. A database LIKE '%shoe%' query can't do this: it scans every row and has no notion of relevance. Search engines like Elasticsearch, OpenSearch and Solr (built on Lucene) are built around one data structure, the inverted index.

The LIKE problem

Product descriptions, blog posts and reviews all need text search. SQL offers LIKE:

SELECT * FROM products WHERE description LIKE '%wireless%headphones%';

The database checks every row's description against the pattern: a full table scan. On a 10-million-row products table that takes seconds. The leading wildcard is what kills it: a B-tree index helps a prefix match like LIKE 'apple%' (sorted keys can be range-scanned), but LIKE '%apple%' could match anywhere, so every row must be read. E-commerce sites need sub-second search, and LIKE can't deliver it. Full-text search engines solve this.

The inverted index

A book's table of contents maps pages to topics; its index at the back maps topics to pages. An inverted index does the second: it maps each term to the documents that contain it. Take four documents:

Tokenize each document into terms and record which documents each term appears in:

Documents containing "cat"? Look up cat and return 1 and 4, with no scan and a lookup cost that doesn't grow with the number of documents. "cat AND dog" intersects two lists: document 4. The index can also store metadata: term frequencies for ranking, term positions for phrase queries, timestamps for recency sorting.

from collections import defaultdict

docs = {1: "The cat is black", 2: "The dog is brown",
        3: "The mouse is grey", 4: "The cat and the dog are friends"}

index = defaultdict(lambda: defaultdict(list))        # term -> doc_id -> positions
for doc_id, text in docs.items():
    for pos, term in enumerate(text.lower().split()):
        index[term][doc_id].append(pos)

def search(*terms):                                   # AND query: intersect postings
    sets = [set(index[t.lower()]) for t in terms]
    return sorted(set.intersection(*sets)) if sets else []

print(dict(index["cat"]))       # {1: [1], 4: [1]}
print(search("cat", "dog"))     # [4]

A normal (forward) index maps a document to its words; real engines store, for each term, a postings list of documents with positions and frequencies:

A query for running shoe looks up two short lists and intersects them (doc1 and doc3), instead of reading every document. Positions make phrase queries ("running shoe") possible.

From text to terms: analysis

Before indexing, text goes through an analyzer, and the same analysis is applied to queries so they match:

1. Tokenize: split "Trail-Running Shoes!" into Trail, Running, Shoes.
2. Normalize: lowercase, strip accents.
3. Remove stop words (optional): drop very common words like "the".
4. Stem or lemmatize: running → run, shoes → shoe, so different forms match.
5. Synonyms and n-grams (optional): sneaker ↔ shoe; edge n-grams (sh, sho, shoe) for search-as-you-type.

Ranking: why some results come first

Lucene-based engines score documents with BM25, which rewards:

• Term frequency: the term appears often in this document, with diminishing returns.
• Inverse document frequency: the term is rare across all documents ("waterproof" matters more than "shoe").
• Field length normalisation: a match in a short title counts more than in a long description.

Real products then add business signals (popularity, recency, price, personalisation), field boosts (title over body), and often a machine-learned re-ranking step over the top results. Semantic search adds vector embeddings so "warm jacket" can match "insulated parka" without shared words, frequently combined with BM25 in hybrid search.

Architecture: keeping search in sync

The search index is almost never the source of truth. Data lives in a database and is copied into the search engine:

• Use change data capture or an outbox rather than dual writes from the app, so the index can't silently miss changes.
• Support a full reindex from the source of truth (into a new index, then switch an alias) for mapping changes and recovery.
• Search clusters scale by sharding the index (each query fans out to all shards and merges top results) and replicating shards for read throughput and availability.
• Accept that search is eventually consistent: a just-created item may take a second to appear.

Database full-text search vs a search engine

Popular full-text search engines

Demo: product search with Elasticsearch

A realistic e-commerce search: an index with a mapping (text fields for matching, a keyword field for exact filters, a number for sorting), then a query with pagination, sorting and filtering. Run Elasticsearch locally (docker run -p 9200:9200 -e discovery.type=single-node -e xpack.security.enabled=false docker.elastic.co/elasticsearch/elasticsearch:8.15.0) and pip install elasticsearch.

from elasticsearch import Elasticsearch

es = Elasticsearch("http://localhost:9200")

# Mapping: "text" fields are analyzed for full-text search, "keyword" is matched exactly
es.indices.create(index="products", mappings={"properties": {
    "name": {"type": "text"},
    "description": {"type": "text"},
    "price": {"type": "double"},
    "category": {"type": "keyword"},
}})

products = [
    {"id": 1, "name": "Apple iPhone 13", "description": "Latest iPhone model with a 120Hz display.", "price": 999.0, "category": "smartphones"},
    {"id": 2, "name": "Samsung Galaxy S22", "description": "Flagship Samsung smartphone with a versatile camera system.", "price": 899.0, "category": "smartphones"},
    {"id": 3, "name": "Google Pixel 6", "description": "Google's newest smartphone with stock Android experience.", "price": 799.0, "category": "smartphones"},
    {"id": 4, "name": "Apple MacBook Pro", "description": "High-performance laptop with Apple's M1 Pro chip.", "price": 2499.0, "category": "laptops"},
]
for p in products:
    es.index(index="products", id=p["id"], document=p)
es.indices.refresh(index="products")          # make new documents searchable now

user_input = "smartphone"
response = es.search(
    index="products",
    from_=0, size=10,                                         # pagination
    query={"bool": {
        "must":   {"multi_match": {"query": user_input, "fields": ["name^2", "description"]}},
        "filter": {"term": {"category": "smartphones"}},     # exact filter, not scored
    }},
    sort=[{"price": {"order": "asc"}}],                       # cheapest first
)
for hit in response["hits"]["hits"]:
    print(hit["_source"]["name"], hit["_source"]["price"])
# Google Pixel 6 799.0
# Samsung Galaxy S22 899.0

The iPhone doesn't match because none of its text contains "smartphone"; an analyzer with stemming and synonyms (phone ↔ smartphone) would fix that, which is exactly the tuning search teams do. Elastic's official demo gallery has a fuller example.

Where full-text search is used

Almost every search box is backed by full-text search:

• E-commerce (Amazon, eBay): keyword product search ranked by relevance, price and reviews; typo tolerance finds "wireles headphones" despite the misspelling.
• Social media (Twitter/X, Facebook): search posts, profiles and hashtags ranked by recency, relevance and engagement, with real-time indexing so new content appears immediately.
• Document management (Dropbox, Google Drive): search file names and the text inside PDFs and documents, with metadata filters for file type and modified date.
• Forums and Q&A (Stack Overflow, Reddit): search keywords, phrases or tags, ranked by recency, relevance and votes, so answers to common questions surface first.

Elasticsearch and OpenSearch, end to end

Picture Amazon with 100 million products such as { "id": 101, "name": "Apple iPhone 17 Pro", "brand": "Apple", "description": "Latest Apple smartphone with titanium body", "price": 90000 }. A customer types iphone. A plain database would check every product for the word; at 100 million products that's far too slow. Elasticsearch builds an inverted index instead, like a textbook index ("Docker → pages 18, 42, 91"), so it jumps straight to matches.

• Searching: apple returns products 1 and 3 straight from the index; apple iphone intersects {1, 3} and {1} → product 1. Normal storage is product → words; an inverted index is word → products.
• New data: when "Boat Bluetooth Speaker" (product 4) arrives, only its terms are added: boat → 4, bluetooth → 4, speaker → 4.
• Understanding text: analyzers lowercase and stem (Running → running → run), so run, runs, running and runner can match each other.
• Typo tolerance: iphne is close enough to iphone (fuzzy matching by edit distance) to still find the right products.
• Relevance ranking: for Apple Charger, Apple iPhone and Apple Cover, scores weigh term frequency, where the terms appear (title vs description), field boosts and other signals, giving iPhone, then Charger, then Cover.
• Autocomplete: typing iph suggests iPhone, iPhone Charger, iPhone Cover (completion suggesters or edge n-grams; see typeahead).
• Filters: combine text with structured conditions (price < 100000, brand = Apple, color = Black) efficiently in one query.

Is it a database? It stores the documents as well as the indexes, so it's both a document store and a search engine, but not a good primary database. Buying a product must reduce inventory, create an order, charge payment and update loyalty points together, and transactional databases (MySQL, PostgreSQL, DynamoDB) are built for that; Elasticsearch is built for search. The usual architecture: the app writes to the source-of-truth database, and changes flow asynchronously via CDC, streams or events into Elasticsearch/OpenSearch, which customers search.

Elasticsearch vs OpenSearch: after Elastic changed Elasticsearch's license in 2021, AWS created OpenSearch, an open-source fork now maintained by AWS and the community. For the concepts that matter (documents, indexes, inverted indexes, full-text search, filters, aggregations, distributed shards and replicas) they're nearly identical. Think of either as Google for your own data: the primary database keeps the official records, and the search engine keeps a copy optimized for full-text search, typo correction, autocomplete, ranking, complex filters and very fast queries over millions or billions of documents.