Search: tokens, ranking and index lag
Follow a query through an inverted index, reason about lexical ranking, and account for delayed indexing and shard fan-out.
18 min7 steps
By the end you can
- Trace tokenisation and postings lookup in an inverted index
- Explain term frequency, rarity and document-length normalization in ranking
- Explain why committed database changes may not yet appear in search
- Explain sharded query fan-out, result merging and partial failures
Turn terms into document lists
Documents
- D1: red bike
- D2: blue bike
- D3: red boat
Postings
- red → D1, D3
- bike → D1, D2
- boat → D3
The index maps each term to postings: document IDs, often with term frequencies and positions. For an AND query, intersect term lists. For OR, take their union. This avoids reading every document for each query.
Queries and documents must agree on tokens
Tokenisation splits text; filters may lowercase, stem or remove stop words. This analyzer does not stem: bikes and bike remain different terms. Query analysis must be compatible with indexing analysis. Changing an index-time analyzer usually requires rebuilding indexed terms.
A match is not yet an ordering
Term frequency
- More occurrences can help
- BM25 saturates this gain
Inverse document frequency
- Rare terms distinguish documents
- Common terms carry less evidence
Length normalization
- Long documents offer more chances to match
- BM25 adjusts for length
TF-IDF combines term occurrence with corpus rarity. BM25 adds a saturating frequency contribution and document-length normalization. Scores estimate lexical relevance, not truth or business value. Repeating one word endlessly should not produce an unbounded BM25 advantage.
The database commit comes first
t0
Database commits new title
t1
Change event reaches indexer
t2
Indexer applies document update
t3
Refresh makes it searchable
Search often reads a derived index. Delivery delay and refresh delay both contribute to visibility lag. A successful database write does not imply immediate search visibility. Serve authoritative post-write confirmation from the source, or wait for a supported visibility acknowledgment.
Fan out, then merge
A coordinator queries relevant shards and merges candidates. Each shard can search a replica. More shards add coordination and tail-latency exposure; they do not guarantee faster requests. With comparable scores, exact local top-k results suffice for global top-k. Approximate retrieval or inconsistent statistics can change ranking.
Say when a result set is incomplete
Fail the request
- Explicit failure
- No claim of completeness
Return partial results
- Mark missing shards
- May omit the best match
Retry within budget
- May recover completeness
- Costs time and work
Choose a product policy for shard failures. Partial responses can be useful, but must disclose incompleteness. Source deletions and access-control changes also need careful propagation: a delayed index must not become the authority for permissions.
Check your mastery
Mastery
80%
4 of 5 fresh questions
Try a fresh variant, then score at least 80% on the mastery check. Wrong answers link back to the teaching step.
Loading question…
Mastery check
5 questions on fresh variants. One attempt each, no time limit. Score 80% or more to master the lesson.
Answer this step to continue.