Data building blocks
Search systems
How inverted indexes, analyzers and BM25 scoring work, and how to run Elasticsearch-style search at scale with sharding, indexing pipelines and hybrid vector retrieval.
A relational database can answer WHERE title = 'Running Shoes'. It cannot sensibly answer "running shoe for wide feet, under $100", ranked by how well each product matches, tolerant of a typo in "runing", with brand counts in the sidebar, across 50 million products in 50 ms. That is information retrieval, and it needs a different data structure.
Search engines such as Elasticsearch, OpenSearch and Solr are built on the Lucene library. Newer engines include Vespa, Typesense and Meilisearch. They power product search, log search and document search, and increasingly the retrieval step of RAG. They are almost never the source of truth. They are a derived, query-optimized copy of your data.
The core idea
Search has two jobs: find the documents that match, then rank them. Matching is done with an inverted index, which maps each word to the documents that contain it. Ranking is done with a scoring function such as BM25, which rewards rare words and penalizes padding. Both jobs run on a cluster that splits the index across machines.
Concepts in this topic
| Step | Concept | What it answers |
|---|---|---|
| 1 | Inverted index | How do you find documents that contain a word? |
| 2 | Text analysis | Which forms of a word should match each other? |
| 3 | BM25 ranking | Which matching document is the best answer? |
| 4 | Distributed search | How does one query visit many shards and merge results? |
| 5 | Search indexing pipeline | How does the index stay in sync with the database? |
| 6 | Hybrid search | How do keyword and meaning-based results combine? |
Filters, facets and typos
Filters such as brand = Nike or price < 100 narrow results without changing scores. Put them in a filter clause. Engines skip scoring for them and cache the results, so they are much cheaper than scored clauses.
Facets are the counts in a sidebar, such as "Nike (1,204)". They are aggregations over the matching set, computed per shard and merged. They read columnar doc values stored on disk, not the inverted index. Counts on high-cardinality fields are approximate across shards, so raise the shard size when accuracy matters.
Autocomplete on a search index can use edge n-grams, a completion suggester, or a prefix field. At very high scale, a precomputed top-k store wins. See the search autocomplete case study.
Typos use fuzzy queries based on edit distance. fuzziness: AUTO allows no edits for very short terms, one edit for medium terms, and two edits for long ones. Engines use an automaton to match terms efficiently instead of comparing every term.
Operational pitfalls
- Mapping explosion. With dynamic mapping, each new JSON key becomes a field for the whole cluster. Use
dynamic: strict, or theflattenedfield type for arbitrary keys. Elasticsearch caps fields at 1,000 per index by default. - Deep pagination.
from: 10000makes every shard produce its top 10,010 results. Usesearch_afterwith a point-in-time for deep paging. - Split brain in old clusters. Before Elasticsearch 7.0, operators set a minimum number of master-eligible nodes by hand. Run three dedicated master-eligible nodes, never two.
- Heap and GC pressure. Keep the JVM heap at no more than about half of RAM, and under about 31 GB, to leave room for the OS page cache that Lucene relies on.
- Treating search as a database. It has no multi-document transactions and only near-real-time visibility. Keep the source of truth elsewhere and make the index rebuildable.
Common mistakes
- Mixing analyzers. Index and query must use the same analysis, or matches silently disappear.
- Ranking by hand without a test set. Keep a set of judged queries and measure every change against it.
- Changing the shard count in place. It is fixed at index creation. Plan a reindex.
Key takeaways
- An inverted index maps analyzed terms to sorted lists of documents.
- Analyzers run at index time and query time. Changing one means reindexing.
- BM25 rewards rare terms and caps repeated ones, with length normalization.
- Queries fan out to every shard and merge the top results, so latency follows the slowest shard.
- Keep the source of truth in your database, feed the index through change data capture, and rebuild behind an alias.
Further learning
Introduction to Information Retrieval (Manning, Raghavan, Schütze)Introduction to Information Retrievalnlp.stanford.edu Elasticsearch guideElastic Docs | Elasticelastic.co
Related
Case study: search autocomplete
Typeahead under 100 ms: tries with cached top-k, offline query-log aggregation, prefix sharding and client debouncing.
Inverted index
Map every word to the sorted list of documents that contain it, so a search becomes a few list lookups and a merge instead of a scan of every document.
Text analysis: tokens, stems and synonyms
Before a word enters the index, an analyzer splits, lowercases, filters and stems it. The same analyzer must run on queries, and changing it means reindexing everything.
BM25 ranking
How BM25 scores a document for a query, using term frequency with saturation, a rare-word weight and length normalization, worked by hand and in code.
Distributed search: query then fetch
How a search index split into shards answers one query. Each shard scores its own documents, the coordinator merges the top hits, and then only the winning documents are fetched.
Search indexing pipeline
How a search index stays in sync with its source database using change data capture, idempotent versioned writes and zero-downtime reindexing behind an alias.
Hybrid search with reciprocal rank fusion
Combine keyword ranking with vector similarity. Reciprocal rank fusion merges the two lists using only ranks, so you never compare their raw scores.
Advanced RAG
Hybrid search, reranking, query rewriting, contextual retrieval and measuring retrieval quality.
Ranking and learning to rank
Second-stage ranking for search, feeds and ads. Learning to rank, ranking metrics, LambdaMART, CTR models, position bias and calibration. Start here for the map.