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.
Connections
- Part of
- Storage
- Learn first
- Inverted Index
- Contrasts with
- Vector Search
- Related
- Derived Data
- In real systems
- ElasticsearchPostgreSQL
Recall
These cards are also in your review deck, scheduled with spaced repetition.