Cheat sheet · Data & storage
Full-text search
The problem
A marketplace searches its catalogue with `LIKE '%word%'`. At 4 million products every search reads every row, and it still misses products written with another apostrophe, in Cyrillic or with an Uzbek suffix. We build real full-text search: an inverted index over analysed tokens, BM25 ranking, an index that follows the database's change log, shards with scatter-gather, and typo tolerance.
What you learn
- Why
LIKE '%x%'cannot use an index and reads the whole table - Analysis: lowercase, Cyrillic to Latin, Uzbek apostrophes and suffixes, the same analyzer at index and query time
- The inverted index with postings, and BM25 ranking worked out in numbers
- Keeping the index fresh from the change log, sharding by document, scatter-gather and typo tolerance
Diagram as code
The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.
Mermaid: flowchart
flowchart LR
n_user(["Shop app"])
n_api["Search API"]
n_db[("Products DB")]
n_catalog["Catalog service"]
n_indexer("Indexer")
n_log[["Change log"]]
n_shard1[("Index shard 1")]
n_shard2[("Index shard 2")]
n_user -->|"call"| n_api
n_catalog --> n_db
n_db -->|"async"| n_log
n_indexer --> n_log
n_api --> n_shard1
n_api --> n_shard2
n_indexer --> n_shard1
n_indexer --> n_shard2Mermaid: request sequence
sequenceDiagram
participant n_api as Search API
participant n_db as Products DB
participant n_index as Search index
participant n_user as Shop app
participant n_indexer as Indexer
participant n_log as Change log
participant n_shard2 as Index shard 2
Note over n_api,n_db: Search with LIKE, while the catalogue is small
n_api->>n_db: SELECT id, title, price_minor FROM products
Note over n_api,n_db: 4 million products: every search reads the table
n_api->>n_db: EXPLAIN ANALYZE SELECT ... WHERE lower(title #124;#124; ' ' #124;#124; description) LIKE '%choynak%'#59;
n_db-->>n_api: Seq Scan on products (rows removed by filter: 3 998 160)
Note over n_api,n_index: Turn it around: from word to products
n_api->>n_index: term df postings (doc id: positions)
Note over n_user,n_api: The same word, written four ways
n_user->>n_api: sellers wrote #34;g'ilof#34; (phone case) in 4 ways, 2 170 products
Note over n_indexer,n_index: Decide what a word is, once, for both sides
n_indexer->>n_index: analyze(#34;Telefon GʻILOFLARI, qora#34;)
Note over n_api,n_index: Rank by relevance, not by sales
n_api->>n_index: query #34;elektr choynak#34; N = 4 000 000 avgdl = 12
Note over n_indexer,n_db: A new product is invisible until tomorrow
n_indexer->>n_db: 10:12 seller adds #34;Elektr choynak 2 l#34; id 4120551 -#62; Products DB ok
Note over n_indexer,n_log: Feed the index from the database's change log
n_indexer->>n_log: cdc products op=u id=4120551 lsn 0/7A3F10
Note over n_api,n_shard2: Split by document, ask every shard
n_api->>n_shard2: search q=#34;elektr choynak#34; size=10 -#62; both shards
Note over n_user,n_api: Find #34;choynak#34; when the buyer types #34;choyank#34;
n_user->>n_api: POST /v1/search HTTP/1.1
n_api-->>n_user: HTTP/1.1 200 OKD2
direction: right
n_user: "Shop app" {
shape: rectangle
}
n_api: "Search API" {
shape: rectangle
}
n_db: "Products DB" {
shape: cylinder
}
n_catalog: "Catalog service" {
shape: rectangle
}
n_indexer: "Indexer" {
shape: rectangle
style.multiple: true
}
n_log: "Change log" {
shape: queue
}
n_shard1: "Index shard 1" {
shape: cylinder
}
n_shard2: "Index shard 2" {
shape: cylinder
}
n_user -> n_api: "call"
n_catalog -> n_db
n_db -> n_log: "async"
n_indexer -> n_log
n_api -> n_shard1
n_api -> n_shard2
n_indexer -> n_shard1
n_indexer -> n_shard2PlantUML: request sequence
@startuml
participant "Search API" as n_api
database "Products DB" as n_db
database "Search index" as n_index
participant "Shop app" as n_user
participant "Indexer" as n_indexer
queue "Change log" as n_log
database "Index shard 2" as n_shard2
note over n_api, n_db : Search with LIKE, while the catalogue is small
n_api -> n_db : SELECT id, title, price_minor FROM products
note over n_api, n_db : 4 million products: every search reads the table
n_api -> n_db : EXPLAIN ANALYZE SELECT ... WHERE lower(title || ' ' || description) LIKE '%choynak%';
n_db --> n_api : Seq Scan on products (rows removed by filter: 3 998 160)
note over n_api, n_index : Turn it around: from word to products
n_api -> n_index : term df postings (doc id: positions)
note over n_user, n_api : The same word, written four ways
n_user -> n_api : sellers wrote "g'ilof" (phone case) in 4 ways, 2 170 products
note over n_indexer, n_index : Decide what a word is, once, for both sides
n_indexer -> n_index : analyze("Telefon GʻILOFLARI, qora")
note over n_api, n_index : Rank by relevance, not by sales
n_api -> n_index : query "elektr choynak" N = 4 000 000 avgdl = 12
note over n_indexer, n_db : A new product is invisible until tomorrow
n_indexer -> n_db : 10:12 seller adds "Elektr choynak 2 l" id 4120551 -> Products DB ok
note over n_indexer, n_log : Feed the index from the database's change log
n_indexer -> n_log : cdc products op=u id=4120551 lsn 0/7A3F10
note over n_api, n_shard2 : Split by document, ask every shard
n_api -> n_shard2 : search q="elektr choynak" size=10 -> both shards
note over n_user, n_api : Find "choynak" when the buyer types "choyank"
n_user -> n_api : POST /v1/search HTTP/1.1
n_api --> n_user : HTTP/1.1 200 OK
@endumlPlantUML: components
@startuml
left to right direction
agent "Shop app" as n_user
component "Search API" as n_api
database "Products DB" as n_db
component "Catalog service" as n_catalog
collections "Indexer" as n_indexer
queue "Change log" as n_log
database "Index shard 1" as n_shard1
database "Index shard 2" as n_shard2
n_user --> n_api : call
n_catalog --> n_db
n_db --> n_log : async
n_indexer --> n_log
n_api --> n_shard1
n_api --> n_shard2
n_indexer --> n_shard1
n_indexer --> n_shard2
@endumlRecap
Six rules for full-text search.
1) LIKE '%x%' reads every row; it does not grow past a small table. 2) Decide what a word is with one analyzer, for products and queries alike: lowercase, one alphabet, no apostrophe variants, a careful stemmer. 3) An inverted index maps words to sorted postings; a search reads only those lists. 4) Rank with BM25: rarity counts, repetitions saturate, long texts are discounted. 5) Feed the index from the database's change log and accept near-real-time; prices and stock are re-read from the database. 6) Shard by document and scatter-gather, and tolerate typos with tight limits.
Numbers: at the start and at the end
| Metric | Start | End |
|---|---|---|
| Search p95 | 45 ms | 24 ms |
| Rows read per search | 50 000 | 21 000 |
| Relevant products missed | 37% | 6% |
| Searches with no results | 3% | 2% |
| Write to searchable | 0 s | 2 s |
Steps
- Case Search with LIKE, while the catalogue is small
Sellers add products through the catalogue service, buyers type words into the search box.
- Problem 4 million products: every search reads the table
Three years later the catalogue has 4 million products and 1.2 GB of text.
- Fix Turn it around: from word to products
An inverted index stores, for every word, the list of products that contain it: its postings.
- Problem The same word, written four ways
Fast, but a third of the relevant products are still not found.
- Fix Decide what a word is, once, for both sides
Before a word goes into the index, an analyzer normalizes it: lowercase, Cyrillic to Latin, every apostrophe variant removed, split into tokens, a short list of suffixes cut off.
- Fix Rank by relevance, not by sales
Now 1 840 products match "elektr choynak" and the order matters.
- Problem A new product is invisible until tomorrow
The index is rebuilt every night.
- Fix Feed the index from the database's change log
Each committed change in the products table goes into a change log, through CDC or an outbox.
- Fix Split by document, ask every shard
With descriptions and positions the index reaches 38 GB and no longer fits in one node's memory: p95 creeps up at peak.
- Fix Find "choynak" when the buyer types "choyank"
2% of searches still find nothing, mostly because of typos.
- Recap Recap
Six rules for full-text search.
Terms
- Inverted index
- An index that stores, for every word, the sorted list of documents containing it (its postings). A search reads only the lists for its words and intersects them, never the documents themselves.
- Text analyzer
- The chain of steps that turns text into index tokens: lowercase, one alphabet, apostrophe variants removed, split into tokens, stemming. The very same analyzer must run on the query.
- BM25
- The standard ranking formula of full-text search. Rare words weigh more (idf), repetitions help but saturate (k1), and long texts are discounted (b).
- Near-real-time index
- An index where new writes become searchable not at once but at the next refresh, typically once a second. The more frequent the refresh, the more small segments there are to merge.
- Scatter-gather
- The query is sent to every shard, each returns its own top k, and a coordinator merges them into one list. The answer takes as long as the slowest shard.