mufassall

Cheat sheet · Data & storage

Full-text search

14 min · Intermediate · mufassall.dtwin.uz/en/l/full-text-search/

← Open the lesson

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
Final scene
30%40%

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_shard2

Mermaid: 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 OK

D2

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_shard2

PlantUML: 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
@enduml

PlantUML: 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
@enduml

Recap

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

MetricStartEnd
Search p9545 ms24 ms
Rows read per search50 00021 000
Relevant products missed37%6%
Searches with no results3%2%
Write to searchable0 s2 s

Steps

  1. Case Search with LIKE, while the catalogue is small

    Sellers add products through the catalogue service, buyers type words into the search box.

  2. Problem 4 million products: every search reads the table

    Three years later the catalogue has 4 million products and 1.2 GB of text.

  3. Fix Turn it around: from word to products

    An inverted index stores, for every word, the list of products that contain it: its postings.

  4. Problem The same word, written four ways

    Fast, but a third of the relevant products are still not found.

  5. 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.

  6. Fix Rank by relevance, not by sales

    Now 1 840 products match "elektr choynak" and the order matters.

  7. Problem A new product is invisible until tomorrow

    The index is rebuilt every night.

  8. 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.

  9. 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.

  10. Fix Find "choynak" when the buyer types "choyank"

    2% of searches still find nothing, mostly because of typos.

  11. 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.