Notesstorage🌱 seedling

Full-Text Search

Also: Full Text Search · FTS · Keyword Search · Lexical Search · BM25

Finding documents that contain the words of a query, then ranking them by relevance. It is built on an [[Inverted Index]] plus a scoring function, BM25 by default in Lucene-based engines.

Why it exists

Users ask in words, not keys. They want the best matches first, tolerant of plurals, case and typos, over millions of documents.

How it works

  • Match: analyse the query, look up postings, combine them (AND, OR, phrase, proximity, fuzzy).
  • Rank with BM25: a term scores higher when it is rare in the collection (IDF), frequent in the document with diminishing returns (k₁, default 1.2), and the document is short relative to average (b, default 0.75).
  • Near real-time: Lucene buffers documents in memory and makes them searchable when a refresh writes an immutable segment (every second by default in Elasticsearch); segments merge in the background.
  • Hybrid search fuses keyword and Vector Search rankings, commonly with reciprocal rank fusion: score = Σ 1/(k + rank), k = 60 by default in Elasticsearch.

Trade-offs

Dedicated engine (Elasticsearch, OpenSearch) In the database (Postgres tsvector + GIN)
rich relevance, analyzers, aggregations, scale-out one system, transactional consistency
a second copy of the data to keep in sync simpler ranking; scaling is the database's problem
refresh lag: not read-your-writes visible at commit

In practice

  • Discord indexes trillions of messages in 40 Elasticsearch clusters grouped into cells, after very large clusters became impossible to upgrade.
  • Instacart moved product search from Elasticsearch into sharded Postgres (GIN, a modified ts_rank, pg_trgm) to stop syncing a denormalized copy, reporting a 10× drop in write load.

Pitfalls

  • A search index is Derived Data: if the sync pipeline drops updates, results silently go stale.
  • Lucene caps an index at about 2 billion documents; big tenants need more shards.

Recall

These cards are also in your review deck, scheduled with spaced repetition.