Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Summary

Approach Comparison

The chapter surveyed three ways to run inverted-file search in practice. They sit at different points on the quality, latency, and storage tradeoff.

PropertyIn-database FTSLucene libraryDistributed engines
ExamplesPostgreSQL, SQLite FTS5Apache LuceneSolr, Elasticsearch, OpenSearch
Scaleup to a few million documentsone node, up to ~2.1B docs or 20-40 GB before latency-bound10s of billions, sharded and replicated
Default rankingfrequency and proximity, no BM25BM25BM25, plus vector search
Vector searchvia pgvector extensionLucene 9+ (HNSW)native, with hybrid scoring
Extra operationsnone, it is your databaseembed in a JVM applicationrun and operate a cluster
Best fitan app that already has a databasecustom search inside one applicationhigh query volume, high availability, hybrid retrieval

Each tier builds on the same core: postings, merges, and BM25 scoring are present everywhere. What grows from one tier to the next is the surrounding machinery for scale and availability.

Key Takeaways

  1. Scoring every document per query does not scale. The inverted index maps each term to a postings list, so query cost grows with the number of query terms, not with the size of the collection.

  2. Retrieval splits into a retriever that gathers candidates by merging query-term postings and a ranker that scores them. Boolean, BIR, vector space, and BM25 all run over the same index; only the postings content and scoring function differ.

  3. Document-at-a-time evaluation keeps memory bounded and allows pruning; term-at-a-time is simpler but accumulates a potentially large score table and cannot prune early.

  4. Metadata predicates attach through a priori, a posteriori, or inline filtering, and faceted search is the a priori case specialized to categories. Compression via d-gaps and variable-byte encoding keeps postings small so more of the index stays in memory.

  5. Sharding scales data volume and per-query latency; replication scales concurrent-query capacity and availability. A single query is not split across regions, so geo-distribution buys capacity, availability, and proximity, not lower per-query latency.

Key Formulas

Self-Check Questions

  1. (Understand) Explain why an inverted index reads only a fraction L/ML/M of the data a full scan would touch, and what LL and MM stand for.

  2. (Understand) Given the postings cat = 1, 4, 10 and dog = 3, 4, 8, 10, 12, evaluate “cat AND dog”, “cat OR dog”, and “cat AND NOT dog” by streaming merge.

  3. (Analyze) When would you prefer term-at-a-time over document-at-a-time evaluation, and when would you choose a posteriori filtering over a priori filtering?

  4. (Analyze) Why can the same document receive slightly different scores on different shards, and why is that usually acceptable?

  5. (Evaluate) An application with two million documents already stored in PostgreSQL needs search with good relevance ranking. Weigh in-database full-text search against adding a Lucene-based engine, using the quality, latency, and cost tradeoff.

Further Reading

Tools and documentation

Part II: Search Systems
Scaling Out