Search for nurse, get a nursery
Someone searches a jobs site for nurse. The first result is a nursery assistant post, the second a hospital porter job that mentions nurses once, and a night-shift post that says only "nursing" never appears. Behind the box is one query:
SELECT * FROM listings WHERE title ILIKE '%nurse%' OR description ILIKE '%nurse%'
Three things are wrong with it. The leading wildcard gives an ordinary B-tree index nothing to seek, so every search reads every listing and slows as the site grows; a PostgreSQL trigram index speeds up the match but fixes nothing else. It matches characters, not words: nursery is in, nursing is out. And nothing orders the 9,000 matches, so the first page is whatever the database read first.
A search engine such as Elasticsearch or OpenSearch answers all three: it turns text into terms, finds the listings that contain them through an inverted index, and ranks them.
A search engine you run, or a hosted search service.
Words, not characters
Before a listing is indexed, each text field passes through an analyzer, a fixed pipeline that turns text into terms. This example's analyzer is configured with three steps:
- Tokenising splits the text on spaces and punctuation: "Night-shift Nurses, Leeds" becomes
Night,shift,Nurses,Leeds. - Normalising makes spellings that should match identical: lowercase, and accents folded so that
Caféandcafeare one term. - Stemming cuts a word back to a common stem: an English stemmer reduces
nursesandnursingtonurs, so a search for either finds both.
With the common English stemmers nursery stays a term of its own, so the nursery post now matches only if its text uses a nurse word. Stemmers follow rules, not a dictionary, and they err: Porter's reduces both universe and university to univers.
The query goes through the same analyzer. The index stores nurs; a query for Nurses that skipped analysis would look up a term no listing contains and find nothing. That is why full-text queries are analysed with the field's analyzer by default, and why changing the analyzer the listings were indexed with means re-indexing every listing.
From terms to matching listings
The terms go into an inverted index: for each term, the listings that contain it, with how often and where (the structure is explained in Data structures behind big systems). A query for paediatric nurse leeds reads three posting lists and either intersects them, when every term must match, or merges them, when any may and more matching terms score higher.
That still leaves 10,000 listings with the nurse stem. Which ten go first is the part the ILIKE query never did.
What a match is worth
A listing that says nurse six times is probably about nursing; the porter job that says it once is not. That count is the term frequency (tf).
Of the 2 million listings, about 400,000 contain senior, 10,000 the nurse stem and 2,000 paediatric, so a match on the rare term says far more. Inverse document frequency (idf) turns that into a weight: the logarithm of the number of listings divided by the number that contain the term. With base-10 logarithms, senior gets about 0.7, the nurse stem 2.3 and paediatric 3.
Multiply tf by idf for each query term and add the results: that is TF-IDF in its plainest form, the classic relevance score. For paediatric nurse, run as a query that accepts listings with either term, a listing with each term once scores 3 + 2.3 = 5.3. One that repeats nurse five times and never says paediatric scores 5 × 2.3 = 11.5 and ranks first, which is not what the searcher asked for.
BM25: diminishing returns, and long listings
This plain TF-IDF lets counts grow without limit, and a long listing collects matches just by having more words. BM25, the default scoring in Lucene and so in Elasticsearch and OpenSearch, computes idf with its own formula, close to this one, and changes how the count is used, with two parameters:
- Saturation (
k1, commonly 1.2): each further occurrence adds less. At average length the count part is tf × (k1 + 1) ÷ (tf + k1): one occurrence gives 1.0, two about 1.4, five about 1.8, twenty about 2.1, and no count reaches 2.2. - Length normalisation (
b, commonly 0.75): thek1in that denominator is scaled to k1 × (1 − b + b × length ÷ average length), so a listing longer than average needs more occurrences to earn the same count part.
Take two listings for nurse, with an average listing of 300 words. A has 200 words and three occurrences; B has 1,200 words and six, so TF-IDF scores B twice as high. Under BM25, A's scaled constant is 1.2 × (0.25 + 0.75 × 200 ÷ 300) = 0.9, giving 3 × 2.2 ÷ 3.9 ≈ 1.69; B's is 1.2 × (0.25 + 0.75 × 4) = 3.9, giving 6 × 2.2 ÷ 9.9 ≈ 1.33. Both are multiplied by the same idf, and the shorter listing now ranks first.
paediatric nurse turns around too: at average length, and keeping the earlier idf values so that only saturation changes, the listing with each term once keeps 3 + 2.3 = 5.3, and the five-times repeater falls to 2.3 × 1.8 ≈ 4.1.
The title counts more than the benefits
A word says more in the title than in the paragraph about pensions. Each field is scored with its own statistics, and a field boost weights them: searching title^3 and description, in Elasticsearch's syntax, triples whatever the title match contributes. A listing titled "Paediatric Nurse" now tends to rank above one that mentions a paediatric ward in passing.
What the text cannot know
Two listings with the same text score the same, though one was posted yesterday and the other five months ago. So the text score is combined with query-independent, or static, signals computed before any query arrives, for example by multiplying it by a freshness factor that halves every 30 days. On the web the best-known static signal is PageRank, computed offline from the links between pages; ranking models learned from clicks, and the feedback loop they create, belong to Recommendation systems: retrieval, ranking & cold start.
Nurese, nurce, nurse
Fuzzy matching accepts indexed terms within a small edit distance of the query term: the number of single-character insertions, deletions and substitutions, and in many engines swaps of neighbouring characters, that turn one into the other. nurese is one deletion from nurse. Elasticsearch's AUTO fuzziness allows no edits for terms of one or two characters, one for three to five, and two for longer ones.
Edit distance knows spelling, not meaning: purse is also one edit from nurse. Each fuzzy term also expands into the indexed terms within reach, up to a configured cap, so a common setup requires the first character or two to match exactly and weights fuzzy matches below exact ones. A "did you mean" line uses the same distance: offer the closest term that is common in the index or in past queries. Suggestions while the searcher is still typing are a different structure, covered in Typeahead & autocomplete.
Some gaps no spelling fix closes: carer does not find "care assistant" unless a synonym list connects them. Matching by meaning, and merging those results with keyword results, is Vector search: embeddings, nearest neighbours & hybrid search.
A copy you can throw away
Employers post and edit in the listings database, the source of truth. The index is a derived copy shaped for search, which can be deleted and rebuilt from the database at any time. Treat the index as the original and a corrupted index takes listings with it.
Employers write to the database; a change feed carries every change to the index, which answers the searches.
The copy has to follow every change. When a listing is filled and nothing tells the index, searchers keep applying to a job that is gone. Polling for changed rows misses rows deleted outright and lags; reading the database's own log of changes is the usual answer, explained in Change data capture. A new analyzer means a new index, built beside the live one, caught up with the changes made during the build, and switched to in one step. At web scale the index is also split across machines (Sharding & partitioning).
A web search engine is this diagram with pages instead of listings, and the Web Search Engine Challenge asks you to "Rank results by relevance using signals like PageRank and TF-IDF". On its Grid the two kinds of signal live in different places: the text score in the query service as it reads the inverted index, PageRank in an offline job over the stored link graph that writes its result into the index. Label the query edge with the fields and boosts it searches, put the fuzzy step for spelling correction on that edge, and keep the indexing pipeline, fed from the document store, as the index's only writer.