Chapter

Full-Text Search and Relevance

Part G · From Records to Insight|3,773 words|about 16 min read|Volume G

44.0 What this chapter gives you#

Looking up an exact order ID and finding a useful document are different tasks. Text search must decide how to split language, which expressions match and how to order several plausible results.
You will build an inverted index by hand, distinguish word presence from phrases, inspect a ranking rule and evaluate results against explicit information needs. You will also see why a search result is not proof that the retrieved statement is correct.
The companion examples use a small invented English corpus and basic SQLite FTS5 where the runtime supports it. They do not claim multilingual search quality, a complete search service or the live KedByte website’s search implementation.

44.1 Words and documents#

44.1.1 PLAIN — in simple words#

A document is the unit a search system returns or indexes: a page, chapter, product description or smaller passage. Choosing that unit changes what the search result means.
A query expresses an information need, but the words typed may only approximate it. Someone asking about a pen repair may not benefit from every product page containing the word pen.
Search begins by defining the searchable collection and who may see each document. A relevant private result is still inappropriate for a reader who lacks permission to access it.

44.1.2 PLAIN — a picture in your head#

Mira labels six cards and lets Dev search their descriptions. Each result points to a particular card, not to an unexplained sentence detached from its source.
If a long manual is split into passages, each passage should still identify the manual, section and edition so the reader can recover context.
Where the comparison breaks: digital systems can index many overlapping fragments automatically. Without stable document and passage identity, updates and deletions can leave stale or duplicate search results.

44.1.3 PLAIN — a worked example#

Our synthetic corpus contains D1 blue pen, D2 blue notebook, D3 red pen, D4 pen repair guide, D5 notebook backup guide and D6 pen blue.
A query for documents containing both blue and pen should return D1 and D6 under a simple word-presence rule. A query for the exact phrase blue pen should return only D1.
A person asking how to repair a pen has a different need. In this deliberately tiny labelled example, D4 is the relevant answer even though several other cards contain pen.
These cards are invented teaching text. They are not claims about actual products, repair procedures or the content of any published KedByte chapter.

44.1.4 PLAIN — what is really happening inside#

The indexing pipeline chooses document boundaries, extracts text and attaches metadata such as title, language, source version and access scope.
Retrieval identifies candidates according to the query model. Ranking then orders those candidates using a selected scoring rule.
The display layer should expose enough source context to help the reader judge usefulness. Search snippets are shortcuts into documents, not independent verification of their claims.

44.1.5 TECHNICAL — the engineer’s version#

Full-text retrieval operates over a defined document collection and query representation. PostgreSQL separates document normalization into tsvector values and query representation into tsquery values. [S174]
Document identity, passage boundaries and versioning are application decisions. Record them so indexing updates can replace or remove the intended material without leaving ambiguous fragments.
Apply access restrictions to all exposed information, including result counts, titles and snippets where those reveal protected content. A later click-time authorization check does not undo an earlier disclosure in search results.

44.1.6 WORDS — remember these#

Document: the searchable unit — an identified body of content, potentially a whole page or a bounded passage. Information need: what the reader is trying to learn — the task that a query attempts to express. Candidate retrieval: finding possible answers — selecting documents for further scoring and verification under a query model.

44.2 Tokenisation#

44.2.1 PLAIN — in simple words#

A tokenizer decides which pieces of text count as searchable units. Splitting on spaces is one possible rule, but it is not sufficient for every language or identifier.
Normalization decides which differences to ignore. Case, accents, punctuation and word endings can help or hinder matching depending on the task.
The query and documents must be interpreted compatibly. Searching a normalized query against differently normalized content can hide documents that a reader reasonably expects to find.

44.2.2 PLAIN — a picture in your head#

Dev cuts each card into word labels before sorting them. If he treats blue-pen as one label in documents but two labels in queries, some matches disappear.
If he removes every mark from an order code, two distinct codes can become indistinguishable. A rule useful for ordinary prose may be unsafe for exact identifiers.
Where the comparison breaks: natural languages differ in writing systems, morphology and segmentation. One English classroom tokenizer is not a universal language processor.

44.2.3 PLAIN — a worked example#

The toy tokenizer lowercases the six ASCII-English cards and extracts runs of letters or digits. Blue pen and blue PEN therefore produce the same two tokens.
blue-pen becomes blue and pen under this declared rule. An exact identifier search for O-1042, however, should use its own identifier-aware path rather than assume prose tokenization preserves the full key.
Removing accents might make some users’ queries easier to match, but it can also collapse distinctions. A system should state whether it preserves or removes those differences and test the languages it actually serves.
A stemmer might map related English endings to a common form. That can increase matches, but it may also combine words whose meanings differ in a particular technical context.

44.2.4 PLAIN — what is really happening inside#

Text extraction and Unicode normalization occur before or alongside tokenization. The pipeline then may apply case folding, stop-word removal, stemming or language-specific dictionaries.
Position information records where tokens occur. Removing tokens or changing token boundaries affects phrase matching and snippets, so these operations must follow the engine’s documented conventions.
Language detection is itself fallible. Mixed-language documents, code examples and product identifiers may need different analyzers or retained original text for exact matching.

44.2.5 TECHNICAL — the engineer’s version#

SQLite FTS5 provides tokenizer choices such as unicode61, ascii and the Porter wrapper, with documented token-character and diacritic behaviour. The exercise uses simple English inputs and does not validate every tokenizer feature. [S173]
PostgreSQL text-search configurations connect parsers and dictionaries to lexeme normalization. Query construction functions differ in how they interpret operators, phrases and ordinary text. [S175]
Maintain analyzer/version metadata with the index. Changing tokenization without rebuilding or reconciling indexed content can mix incompatible representations and make result differences difficult to explain.

44.2.6 WORDS — remember these#

Tokenisation: splitting text into searchable units — applying a specified segmentation rule to content and queries. Lexeme: a normalized searchable form — a dictionary or analyzer output that may combine several written word forms. Analyzer: the text interpretation pipeline — extraction, tokenization and normalization rules used for indexing and querying.

44.3 Inverted indexes#

44.3.1 PLAIN — in simple words#

An inverted index turns “document to words” into “word to documents.” Instead of reading every card, the searcher opens the list for the requested word.
Several word lists can be combined. AND keeps documents appearing in every required list; OR keeps documents appearing in at least one.
Word membership alone cannot prove a phrase. For that, the index or a later check needs the words’ order and positions.

44.3.2 PLAIN — a picture in your head#

Mira makes a drawer for each word. Inside the blue drawer are references to cards D1, D2 and D6. Inside pen are D1, D3, D4 and D6.
Dev intersects the two lists to find D1 and D6. He then checks positions to distinguish blue pen from pen blue.
Where the comparison breaks: real posting lists are compressed and may include frequencies, positions or other metadata. Efficient query execution can skip portions rather than literally opening every reference in order.

44.3.3 PLAIN — a worked example#

The blue posting set is {D1, D2, D6}. The pen posting set is {D1, D3, D4, D6}. Their intersection is {D1, D6} and their union contains five documents.
Using zero-based token positions, D1 has blue at 0 and pen at 1. D6 has pen at 0 and blue at 1. Requiring pen immediately after blue selects D1 only.
For the word notebook, the posting set is {D2, D5}. Intersecting notebook with pen gives an empty set in this corpus, a legitimate result rather than an index failure.
Deleting D1 requires removing its eligibility from the search result. A stale posting pointing to a deleted document must not be treated as proof that the document still exists or may be displayed.

44.3.4 PLAIN — what is really happening inside#

Index construction collects token occurrences by document. Query evaluation merges or intersects the relevant postings and may verify phrases or other conditions against positions or source content.
Updates can create new index segments that are later merged. Readers need a consistent view of which document versions and deletion markers are effective.
Some index structures return possible matches that need rechecking. This is acceptable when the recheck removes false candidates before the final result, not when approximate candidates are presented as exact matches.

44.3.5 TECHNICAL — the engineer’s version#

PostgreSQL GIN text-search indexes store lexemes with matching locations; GiST uses signatures that can require rechecking false matches. The access method’s exactness and stored metadata affect execution. [S184]
The toy index records token positions and compares its AND, OR and phrase results with direct scans of the same tokenized documents. It is not a compressed posting-list engine or a concurrent index implementation.
In FTS5 external-content configurations, applications must keep content and index updates consistent using the documented mechanisms. An index definition alone does not automatically repair a previously inconsistent external-content history. [S173]

44.3.6 WORDS — remember these#

Inverted index: a word-to-document map — an access structure locating documents containing searchable terms. Posting list: occurrences associated with one term — document references, often accompanied by frequency or position information. Positional index: an index retaining term locations — metadata supporting phrases and proximity conditions beyond word presence.

44.4 Scoring and ranking#

44.4.1 PLAIN — in simple words#

A search score orders candidates according to a rule. It is not a probability that a document is true, and scores from different queries or engines may not be directly comparable.
Useful rules can consider how often a term occurs, how common it is across documents and whether it appears in a title or a long body.
Repetition should not always grow the score without limit. A page repeating pen a thousand times is not necessarily more useful than a clear repair guide using the word twice.

44.4.2 PLAIN — a picture in your head#

Dev gives some weight to words that distinguish a card from the collection. A rare technical term can be more informative than a word printed on nearly every card.
He also notices where the match occurs. A title devoted to repair may be a stronger clue for a repair question than a passing reference in a long unrelated document.
Where the comparison breaks: relevance depends on the reader’s task and context. A numerical formula can rank clues, but it cannot guarantee that the top document answers the actual question correctly.

44.4.3 PLAIN — a worked example#

In our six-document corpus, pen appears in four documents and blue in three. A simple inverse-frequency weight ln(N / df) gives pen about 0.405 and blue about 0.693.
A presence-only score for the two query terms gives D1 and D6 about 1.099, D2 about 0.693, and D3/D4 about 0.405. This is a toy rule, not SQLite’s BM25 output.
A term-frequency saturation factor (k + 1) * f / (k + f) with k = 1.2 gives 1 when frequency f is 1 and about 1.571 when f is 3. Tripling repetition therefore does not triple this contribution.
D1 and D6 still tie under the presence rule. A deterministic document-ID tie-break makes output repeatable, but does not turn the tie-break into a claim of greater relevance.

44.4.4 PLAIN — what is really happening inside#

Ranking computes features over the candidate set and collection statistics. Document length, term frequency and field weighting can affect the result.
Changing the corpus can change scores even when a particular document stays unchanged, because collection statistics such as document frequency change.
Ranking parameters should be evaluated on representative queries and separate development/test sets. Adjusting a rule until it succeeds on one demonstration can overfit that demonstration.

44.4.5 TECHNICAL — the engineer’s version#

BM25 combines term weighting with frequency saturation and document-length normalization. The exact formula and parameter choices should be stated for the implementation being used. [S182]
SQLite FTS5 negates its BM25 score so numerically smaller values sort first for better matches under that implementation. A generic assumption that every search score should be sorted descending is therefore wrong. [S173]
Bound SQL values with parameters, but remember that a full-text query string may still have its own operators and resource costs. Define whether the interface accepts literal words or an advanced query language, and handle invalid expressions without exposing internal details.

44.4.6 WORDS — remember these#

Document frequency: how many documents contain a term — a collection statistic used to distinguish common from rarer terms. BM25: a family of lexical ranking rules — scoring that combines term weighting, frequency saturation and document-length effects. Tie-break: a rule ordering equal-scored results — a deterministic convention that does not itself establish relevance.

44.5 Language and spelling#

44.5.1 PLAIN — in simple words#

Readers may use spelling variants, abbreviations or different words for the same concept. Search can help by recognizing selected alternatives, but every expansion can also introduce unwanted matches.
Language-specific processing matters. An English stemming rule should not be presented as a solution for Hindi, Japanese or mixed-language technical writing.
Exact identifiers deserve special treatment. Correcting a misspelled ordinary word can be helpful; silently changing a receipt ID can retrieve the wrong person’s record.

44.5.2 PLAIN — a picture in your head#

Mira knows that a customer asking for a writing instrument may be looking for a pen. She can suggest that connection while still allowing the customer to inspect the original query.
She would not silently change order O-1042 to O-1043 because the second card happened to be easier to find.
Where the comparison breaks: automatic synonym and spelling systems cannot rely on human situational understanding. They need bounded rules, confidence policies and evaluation across the intended users’ language patterns.

44.5.3 PLAIN — a worked example#

A query notebok differs from notebook by one missing o. An edit-distance suggestion can propose notebook, but the interface should distinguish the suggestion from an exact match.
Expanding notebook to computer might help a device-shopping query while damaging a stationery query. The corpus and task determine whether that synonym is useful.
In our corpus, notebook backup guide is intentionally ambiguous: notebook could refer to a computer or written notes. Word overlap does not resolve the intended sense by itself.
A bilingual book reader should evaluate actual language examples and technical terms. The small English lab is evidence about its declared tokens only, not proof that every language’s segmentation and spelling needs are covered.

44.5.4 PLAIN — what is really happening inside#

Query expansion can add synonyms, spelling candidates or related forms before retrieval. This often increases the candidate set and can reduce precision while improving recall.
The expansion history should be observable when it changes the meaning of the query. A reader can then distinguish what they typed from what the system searched.
Search snippets also need safe rendering. Source text can contain markup or code; highlighting must not turn untrusted content into executable browser instructions.

44.5.5 TECHNICAL — the engineer’s version#

PostgreSQL’s text-search configurations and dictionaries are language- and task-dependent. Normalization choices are not interchangeable, and appropriate configuration must accompany stored and queried text. [S174] [S175]
Highlighting functions can return text containing markup or source characters that need safe output handling. Treat a snippet as untrusted content and use a deliberate escaping/rendering strategy rather than inserting it blindly as HTML. [S175]
Keep exact-key retrieval separate from fuzzy natural-language search when identity is consequential. A suggestion is not authorization to replace the requested key or to expose nearby private records.

44.5.6 WORDS — remember these#

Query expansion: adding related search terms — a recall-oriented technique whose extra candidates can change precision and meaning. Edit distance: the number of selected character edits between strings — a spelling similarity measure, not a proof of intended identity. Snippet: a displayed excerpt from a result — contextual text that requires source attribution and safe rendering.

44.6 Evaluating search quality#

44.6.1 PLAIN — in simple words#

Search quality must be checked against actual information needs. Finding a word is not the same as helping the reader answer a question.
Precision asks how many returned results are relevant. Recall asks how much of the known relevant material was returned. The labels and the chosen result cutoff matter.
A useful evaluation includes queries with no answer, rare terms, spelling problems and access restrictions. A few successful showcase queries do not establish general quality.

44.6.2 PLAIN — a picture in your head#

Mira gives Dev a list of questions and independently marks which cards help answer each one. She then compares his results with those judgements.
If Dev returns every card for every question, he finds all relevant cards but also burdens the reader with irrelevant material.
Where the comparison breaks: relevance judgements can be incomplete or disputed. Evaluation should preserve who labelled what, the intended task and the uncertainty in the labels rather than treating them as infallible ground truth.

44.6.3 PLAIN — a worked example#

For the labelled query “how to repair a pen,” suppose only D4 is considered relevant. A hypothetical result order is D1, D3, D4.
Precision at three is 1 relevant result divided by 3 returned, or one third. Recall at three is 1 found divided by 1 known relevant, or 1.
The first useful result is at rank 3, so reciprocal rank is 1/3. Moving D4 first improves this navigation measure without changing the three-result set’s precision or recall.
If there are no known relevant documents for another query, recall’s denominator is zero. Record the chosen evaluation convention or report it as undefined; do not silently count an arbitrary 100% success.

44.6.4 PLAIN — what is really happening inside#

Evaluation stores a corpus version, queries, relevance judgements, retrieval configuration and result lists. Repeatability requires all of those, not only the scoring formula.
Candidate generation and ranking can fail separately. If a useful document never enters the candidate set, a perfect reranker cannot recover it from nothing.
Operational quality includes response time, index freshness, deletion propagation and authorization. A relevant answer drawn from an outdated or unauthorized source can still fail the product’s requirements.

44.6.5 TECHNICAL — the engineer’s version#

Precision and recall compare retrieved documents with judged relevance; they focus on useful retrieval rather than accuracy dominated by a large irrelevant population. [S181]
Use stable tie-breaking and avoid duplicate document IDs when computing set-based metrics. State whether the unit is a whole document, passage or source, because overlapping passages can inflate apparent coverage.
The companion checks establish posting-set correctness, phrase behaviour, selected FTS5 queries and metric arithmetic on a tiny labelled corpus. Independent user evaluation and multilingual, accessibility and production-load testing remain separate tasks.

44.6.6 WORDS — remember these#

Precision: how much of the returned material is relevant — relevant retrieved items divided by retrieved items under a stated cutoff and unit. Recall: how much relevant material was found — relevant retrieved items divided by the known relevant population. Reciprocal rank: a measure of how soon the first useful answer appears — one divided by its rank, with an explicit no-answer convention.

44.97 Practice and worked answers#

Question: Which cards contain both blue and pen? Answer: D1 and D6. Only D1 contains the phrase blue immediately followed by pen.
Question: Why does tokenization belong in the index’s version record? Answer: A changed analyzer can alter boundaries and matches even when the source text is unchanged.
Question: What does a posting list contain? Answer: References to documents containing a term, potentially with frequencies and positions.
Question: Why is a search score not a truth probability? Answer: It measures the selected ranking features, not the correctness of every statement in a document.
Question: Which direction sorts SQLite FTS5 BM25 better matches first? Answer: Ascending, because that implementation returns numerically smaller scores for better matches.
Question: May spelling correction silently replace an exact order ID? Answer: No. A suggested nearby identifier is not the same request and may expose unrelated information.
Question: What are precision and recall for one relevant result among three returned when only one relevant document is known? Answer: Precision 1/3 and recall 1.
Question: Can ranking recover a useful document omitted by candidate retrieval? Answer: Not unless another retrieval stage introduces it. Ranking only orders what it receives.

44.98 Common wrong ideas#

Wrong: A word match proves a useful answer. Right: Relevance depends on the information need and context.
Wrong: Space splitting works for every language. Right: Tokenization is language- and task-dependent.
Wrong: AND word matching proves an exact phrase. Right: Phrase matching needs order and position information.
Wrong: More repetitions always mean a better result. Right: Ranking rules often limit repetition’s contribution.
Wrong: Every score should be sorted descending. Right: Read the implementation’s score convention.
Wrong: Fuzzy search is appropriate for every identifier. Right: Exact identity needs a separate contract.
Wrong: Returning everything is excellent search because recall is high. Right: Precision and reader effort also matter.
Wrong: Search-result permission can wait until the click. Right: Titles, counts and snippets can already disclose protected information.

44.99 Chapter summary in 20 lines#

Choose the document unit and collection boundary.
A query approximates a reader’s information need.
Retrieval and ranking are separate stages.
Tokenization defines the searchable units.
Normalization changes which distinctions are retained.
Query and document analyzers must be compatible.
Inverted indexes map terms to documents.
Posting intersections implement simple AND conditions.
Phrase matching requires order and positions.
Index updates must track document versions and deletions.
Ranking scores reflect a selected rule, not truth.
Rare terms can contribute different evidence from common ones.
Frequency saturation limits repeated-word influence.
Score direction and tie-breaking are implementation details.
Language and spelling expansion need task-specific evaluation.
Exact identifiers should not be silently fuzzy-matched.
Snippets require context, permission and safe rendering.
Precision and recall have different denominators.
Candidate omissions cannot be repaired by ordering alone.
Evaluate usefulness, freshness, access and operational behaviour together.

Return to contents