Indexing & Fuzzy Matching Study Portal

How it works

Why a database does not read every row

A table is, physically, a pile of blocks on disk holding rows in roughly the order they were written. Answering WHERE passport_number = 'X12345' from that alone means reading every block and checking every row — a sequential scan. On 190 million rows that is tens of gigabytes of I/O for one answer, and the cost grows linearly with the table: double the data, double the time.

An index is a second, separate structure that stores a copy of one or more columns, kept in an order that makes lookup cheap, alongside a pointer back to the row. You pay for it twice — in storage, and on every write, because an insert must now update the table and every index on it — and you buy back the ability to find rows without reading them all.

The book-index analogy is the standard one and it is correct as far as it goes: you look up a term alphabetically at the back and it gives you page numbers, instead of reading the book. Where it breaks down matters more than where it holds:

• A book has one index; a table has many, one per access pattern, each with its own write cost.
• A book index is static; a database index is maintained on every write, which is the whole reason indexes are not free and why a table with twelve indexes has slow inserts.
• A book index only does exact term lookup. A database B-tree also does ranges and prefixes, because it is sorted rather than hashed — and it still cannot do "similar to".
• The book's page numbers are the answer. A database index usually gives a pointer, and the engine must then fetch the actual row — a second random read per row, which is why an index that matches ten million rows can be slower than a scan and why the planner will sometimes correctly ignore it.

The B-tree, and the one thing it cannot do

The B-tree is the default index in essentially every relational database — Postgres, MySQL, SQL Server, Oracle. It is a balanced sorted tree: each node holds a sorted run of keys, and the children between those keys hold the values in that gap. Searching is a descent. At each node you binary-search the keys to pick one child, discarding everything under the others.

The arithmetic is the point. Each step reduces the remaining candidates by the tree's branching factor, so the depth is logarithmic in the row count. Taking the pessimistic binary case, log₂(190,000,000) ≈ 27.5 — about 27 comparisons to locate one row among 190 million. Real B-trees pack hundreds of keys per page rather than two, so the actual depth is 4 or 5 page reads, but "halving each step" is the intuition that matters: going from 190 million rows to 380 million adds one step.

Because it is sorted rather than hashed, a B-tree serves three query shapes:

The last row is the load-bearing fact of this entire module. Sorting RASHEED puts it near RASHEEM and nowhere near RASHID, even though the second is far more likely to be the same person. The B-tree's ordering is lexicographic, and lexicographic distance is not similarity distance. There is no way to fix this with a better B-tree, because the structure's speed comes precisely from being able to discard whole subtrees — and to discard a subtree you must be certain nothing similar is in it, which sorted order cannot tell you.

Every other technique below — trigrams, blocking, phonetics, search engines — is a different answer to that single gap.

Trigram indexes and GIN

A trigram is a three-character window over a string. RASHID decomposes into ras, ash, shi, hid (Postgres's pg_trgm also pads the ends, producing fragments for the word start, so short strings and word boundaries are represented).

The trick is that a misspelling shares most of its trigrams with the original:

RASHID   -> ras, ash, shi, hid
RASHEED  -> ras, ash, she, hee, eed
            ^^^^^^^^ two shared out of a small set
RASHIDD  -> ras, ash, shi, hid, idd
            ^^^^^^^^^^^^^^^^^^^ four shared out of five

Similarity is then defined as shared trigrams over total distinct trigrams — a Jaccard-style ratio. Postgres exposes it as similarity(a, b) and the % operator, which is true when similarity exceeds pg_trgm.similarity_threshold (default 0.3). Remember that default; it comes back as a failure mode below.

GIN — Generalised Inverted iNdex — is the index type that makes this searchable. An ordinary B-tree entry maps one key to one row. An inverted index maps one key to a posting list of many rows:

'ras' -> [row 12, row 88, row 401, row 9902, ...]
'ash' -> [row 12, row 55, row 401, ...]
'shi' -> [row 12, row 7734, ...]

A fuzzy query decomposes the search term into trigrams, fetches the posting list for each, and intersects or unions them to get candidate rows — which is exactly the "find things that share fragments" operation a B-tree cannot express. It is the same structure a search engine uses for words; a trigram index is an inverted index whose "words" are three-character fragments.

The costs follow directly from the shape:

• Size. One row with a 20-character name produces roughly 20 index entries instead of 1. A GIN index on a text column is routinely larger than the column itself, sometimes larger than the table.
• Write cost. An insert must append the row to ~20 posting lists. Postgres mitigates this with a fastupdate pending list that batches insertions and merges them later, which makes writes cheap but leaves the pending list to be scanned on every query until it is merged — so a write-heavy table can see query latency drift upward between merges.
• Update amplification. Changing one character in a name rewrites several posting lists, not one entry.

pg_bigm is the same idea with two-character fragments (bigrams). Fewer distinct fragments means each posting list is longer and more rows share any given fragment, so it matches more aggressively — better recall on very short strings and on scripts where trigrams are sparse, but less selective: ra appears in a huge fraction of names, so the candidate set it returns is far larger and more of the work moves to the scoring stage. Trigrams are the usual default because three characters is selective enough to prune hard while still surviving a single typo.

Blocking, and blocking keys

Record linkage is deciding whether two records refer to the same real-world entity. The immediate obstacle is arithmetic: comparing every record against every other is O(n²). With 1 million records on each side that is 10¹² comparisons. At a million comparisons per second that is over eleven days for one run.

Blocking is the standard escape. You compute a short blocking key for every record such that records which are plausibly the same will produce the same key, then you only compare records that share a key. Comparison drops from "all pairs" to "all pairs within each block", which is orders of magnitude smaller.

Two worked examples:

Phonetic blocking key. Encode the surname with a phonetic algorithm and use that as the key.

RASHID   -> Soundex R230
RASHEED  -> Soundex R230     ✅ same block, will be compared
RACHID   -> Soundex R230     ✅ same block
ALI      -> Soundex A400     -- different block, never compared

Sorted-token blocking key. Split the name into words, lowercase, sort alphabetically, rejoin. This defeats word-order variation, which is endemic in international name data.

"Mohammed Al Rashid"   -> al|mohammed|rashid
"Rashid, Mohammed Al"  -> al|mohammed|rashid   ✅ same block
"Mohammad Al Rashid"   -> al|mohammad|rashid   ❌ DIFFERENT block

That last line is the honest part of the trade, and it is why blocking is dangerous in a way that is easy to under-state. Blocking is all-or-nothing. A pair that does not share a key is never compared — not compared and scored low, not surfaced as a near miss, not compared at all. There is no partial credit, no ranking, and critically no error: the query returns successfully, quickly, with a result set that silently omits the true match. This is a pure recall failure, and recall failures do not appear in logs, metrics, or exception trackers. You find them when someone notices the answer was wrong, or you never find them.

The standard mitigation is multiple independent blocking passes — block on phonetic surname, and on sorted tokens, and on date of birth, and union the candidate sets. A record must be missed by every pass to be lost, so independent passes multiply the recall rather than add to it. The cost is more candidates and more scoring work, which is the correct direction to err.

Both of the keys above have been measured, on a real 677,596-name sanctions corpus against 699 known-true matches, and the numbers are worth sitting with:

                       mean block size    true matches retained
trigram (baseline)          244                699 / 699  = 100%
sorted-token key              1                302 / 699  = 43.2%
phonetic surname            596                607 / 699  = 86.8%
surname + initial            48                503 / 699  = 72.0%
union of sorted + surname     -                619 / 699  = 88.6%

Three things fall out of that table, and none of them are obvious from the mechanism alone. First, the union beats both of its members (88.6% against 43.2% and 86.8%), which is the multi-pass argument confirmed on data rather than asserted. Second, it is still not enough — 88.6% recall means one true match in nine is never compared, and on a sanctions screen that is not a tuning detail. Third, and least intuitive: the phonetic key produced a mean block of 596 against the trigram baseline's 244. The "cheap narrow key" was 2.4x wider than the index it was supposed to replace. A blocking key is a bet that your key is more selective than your index, and that bet can simply lose.

These are full, unbudgeted blocks, so those recall figures are a ceiling, not a starting point — no amount of ranking or ORDER BY inside the block can retrieve a record the key never admitted.

Fellegi-Sunter and probabilistic record linkage

Fellegi and Sunter's 1969 framework is the standard academic formalisation of "are these two records the same entity", and it is what most serious linkage tooling implements.

The idea: for each pair, compare a set of fields and record which agreed. For every field, estimate two probabilities from the data:

• m = P(this field agrees | the pair IS a match). Less than 1, because real matching records still disagree through typos and stale data.
• u = P(this field agrees | the pair is NOT a match). Small for a high-cardinality field like date of birth, much larger for something like gender.

The evidence contributed by one agreeing field is the ratio m/u, and because fields are treated as conditionally independent the log-ratios simply add up into a single match weight. A disagreement contributes (1-m)/(1-u), which is a negative weight — disagreement is evidence against, not merely absence of evidence.

The consequence worth internalising: agreement on a rare value is worth vastly more than agreement on a common one, because u is tiny for rare values. Two records agreeing on the surname "Kowalczyk" is strong evidence; two records agreeing on "Smith" is nearly none. That is the same insight as IDF weighting below, arrived at from probability rather than information theory.

Fellegi-Sunter then sets two thresholds, not one: above the upper one, declare a match; below the lower one, declare a non-match; in between, route to human review. Systems that collapse this to a single cut-off lose the ability to represent "we genuinely do not know", which in compliance and identity contexts is the answer that matters most.

Splink is the widely used open-source implementation, from the UK Ministry of Justice's analytical services team. Its documentation states plainly that "Splink's core linkage algorithm is based on Fellegi-Sunter's model of record linkage, with various customizations to improve accuracy", and describes itself as fast, accurate and scalable probabilistic data linkage for datasets lacking unique identifiers. It estimates m and u from your own data rather than requiring hand-set weights. — (verified)

Phonetic algorithms

Phonetic algorithms map a string to a code approximating how it sounds, so that differently-spelled but similarly-pronounced names collide.

Soundex (1918, developed for US census work) keeps the first letter, maps consonants to six digit-classes, drops vowels, collapses repeats, and pads or truncates to four characters: R + 230 for both RASHID and RASHEED. It is crude, fixed-length, and over-collides — but it is present in almost every database as a built-in and is adequate as a blocking key.

Metaphone (1990) replaced the digit classes with rules over English letter combinations — PH → F, TH → a single sound, silent letters dropped, GH handled contextually — producing a variable-length code that is markedly more accurate than Soundex.

Double Metaphone (2000) is the practical choice. It emits two codes per name — a primary and an alternate — precisely to handle names whose pronunciation depends on linguistic origin. Schmidt yields both a Germanic and an anglicised reading; a match on either code counts. That two-code design is what makes it usable on non-English name data at all.

Why Mohammed and Muhammad collide: both are transliterations of the same Arabic name, and every phonetic algorithm drops or neutralises vowels — which is exactly where the two spellings differ. The consonant skeleton M-H-M-D is identical, so they share a code. This is the mechanism, and it is also the limit.

Where they fail:

• They encode English phonetics. The rules are about how English speakers pronounce letter combinations. Applied to Arabic, Chinese, Slavic or Indian names they encode a foreign speaker's guess at pronunciation, and their accuracy drops sharply.
• Transliteration variance is not phonetic variance. Zhang / Chang and Yusuf / Youssef / Jusuf differ because of which romanisation system was used, not because of pronunciation drift, and English phonetic rules do not model that.
• Soundex is anchored on the first letter, which it preserves verbatim — so Catherine and Katherine never collide, a failure on a pair any human would call identical.
• They over-collide. Soundex's four-character output buys recall by producing false collisions in enormous numbers, which is acceptable for blocking and useless as a decision.

The correct framing: a phonetic code is a blocking key, never a match verdict. It belongs in stage one.

String similarity measures

Once you have candidates, you need a number. Three measures cover most cases and they are not interchangeable.

Levenshtein edit distance — the minimum number of single-character insertions, deletions or substitutions to turn one string into the other. RASHID → RASHEED is 2. It is symmetric, interpretable, and position-agnostic, and it is computed by a dynamic-programming table that costs O(m×n), which is fine on names and prohibitive on long text. Normalise it by the longer length to get a comparable ratio, and bound it: on names, a distance above 2 or 3 is almost never worth pursuing, and setting that bound lets the algorithm abandon early.

Jaro-Winkler — Jaro similarity counts matching characters within a sliding window and penalises transpositions, then Winkler adds a bonus scaled by the length of the common prefix (up to four characters). It returns 0–1. The prefix bonus is deliberate and empirical: it was designed for census person-names, where errors were observed to cluster toward the end of a name — typos, truncations, dropped suffixes — while the beginning is usually typed correctly. So Jonathon/Jonathan scores very high, and it is the standard first choice for given names and surnames. The same bias makes it wrong elsewhere: for identifiers, addresses or codes with a shared prefix (ACC-2024-0001 vs ACC-2024-9999), the bonus manufactures similarity that is not there.

Token-set overlap — split into words, compare as sets (Jaccard, or a token-sort/token-set ratio). It ignores word order and, depending on the variant, extra words entirely. This is the right tool when the tokens are stable and their arrangement is not: "Mohammed Al Rashid" vs "Al-Rashid, Mohammed" is a perfect token match and a poor character-level one. Handling multi-part names, missing middle names, honorifics and reordering is exactly its domain — and it is blind to typos within a token, which is why it is normally combined with a per-token character measure rather than used alone.

IDF and rarity weighting

Without rarity weighting, every Mohammed matches every other Mohammed, every Smith matches every other Smith, and the top of your result list is permanently occupied by the most common names in the dataset — which are, definitionally, the least informative.

Inverse document frequency is the fix, borrowed from information retrieval. The weight of a token is inversely related to how many records contain it, conventionally idf = log(N / df) where N is the corpus size and df the number of records containing the token.

A concrete calculation over a 190-million-name corpus:

Agreement on kowalczyk carries roughly three times the weight of agreement on mohammed, derived from the data itself with no hand-maintained stopword list. That last point matters: a hardcoded list of common name-parts is a maintenance burden that is always wrong for the next dataset, whereas IDF is recomputed from the corpus and adapts automatically — including to the fact that al is common in one dataset and rare in another.

The direct consequence for matching: a query for "Mohammed Ali" against a corpus where both tokens are common should score low on token agreement alone and require corroboration — a date of birth, a nationality, a rare middle token — before it is treated as a match. This is the same principle as Fellegi-Sunter's u probability; IDF is its information-theoretic expression, and BM25 (below) is its production form in search engines.

Partitioning

Partitioning splits one logical table into multiple physical tables — partitions — behind a single name. The database routes each query and write to the relevant partition(s) using a declared key, typically a date range or a hash.

CREATE TABLE screening_hits (
    id           BIGSERIAL,
    subject_id   UUID        NOT NULL,
    matched_at   TIMESTAMPTZ NOT NULL,
    score        NUMERIC     NOT NULL
) PARTITION BY RANGE (matched_at);

CREATE TABLE screening_hits_2026_08 PARTITION OF screening_hits
    FOR VALUES FROM ('2026-08-01') TO ('2026-09-01');

Two properties make it worth the complexity:

Dropping a partition beats deleting rows. DELETE FROM screening_hits WHERE matched_at < '2025-01-01' on 40 million rows is a long-running transaction that writes a WAL record per row, leaves 40 million dead tuples for vacuum to reclaim, bloats the table and every index on it, and holds locks throughout. DROP TABLE screening_hits_2025_01 — or DETACH PARTITION first — unlinks files. It is effectively instant, generates no dead tuples, needs no vacuum, and releases the disk immediately. Retention policy stops being a maintenance operation and becomes a metadata change.

Index maintenance stays flat as history grows. This is the subtler and more valuable property, and it is the one that matters for the fuzzy-matching indexes above. A GIN trigram index over one unpartitioned table grows with total history; every insert updates posting lists inside a structure that is now hundreds of gigabytes, its upper levels no longer fit in the buffer pool, and write latency climbs year over year even though the write rate is unchanged. With range partitioning on time, only the newest partition takes writes, so the index being mutated is only as large as the current period — bounded, cache-resident, and the same size next year as this year. Older partitions' indexes are read-only, fully packed, and never touched by the write path.

The costs are real: the partition key must appear in queries for the planner to prune (a query without it touches every partition), unique constraints must include the partition key, and cross-partition queries fan out. Partition count also matters — thousands of partitions make planning itself slow.

Row store versus column store

A row store — Postgres, MySQL, SQL Server — keeps all the columns of one row physically adjacent. Reading one row is one contiguous read; reading one column across a million rows means touching every row's worth of bytes.

A column store — DuckDB, ClickHouse, and analytical formats like Parquet — keeps all the values of one column adjacent. Reading one column across a billion rows touches only that column's data, which compresses extremely well because adjacent values are homogeneous, and vectorises cleanly because the CPU processes a run of identical types.

Column stores are optimised for scanning many rows to produce few numbers. They are not designed for retrieving specific rows by a fuzzy key, and they do not generally offer the inverted-index machinery that fuzzy retrieval requires.

Which is why listing ClickHouse beside OpenSearch as "the search tier" is a category error, not merely a suboptimal choice. They answer different questions:

• OpenSearch answers "which documents best match this messy string, ranked by relevance?" — an inverted-index, per-document-scoring question.
• ClickHouse answers "across these billion rows, what is the count/sum/percentile grouped by these dimensions?" — a scan-and-aggregate question.

A design that names them as alternatives has not identified which question it is asking. The correct pairing is usually both, for different jobs: OpenSearch for candidate retrieval and relevance, ClickHouse for analytics over the resulting events. Asking ClickHouse to do fuzzy name retrieval means scanning, because there is no inverted index to prune with — which is precisely the sequential scan this whole module exists to avoid.

Search engines, and the explainability myth

OpenSearch and Elasticsearch (same Lucene lineage, forked in 2021), and the lighter Typesense and Meilisearch, add three things a relational database does not have natively:

Analyzers — a configurable pipeline applied identically at index time and query time: tokenise, lowercase, strip accents, apply a stemmer, expand synonyms, optionally emit character n-grams. "Müller-Schmidt" can be normalised to the tokens muller and schmidt before it is ever indexed, so the messiness is resolved in the index rather than in every query.

Typo tolerance — fuzzy matching over the term dictionary using a bounded edit distance, implemented with a Levenshtein automaton so it does not degenerate into scanning the dictionary. Typesense and Meilisearch enable this by default; Lucene engines expose it per query (fuzziness).

BM25 relevance scoring — the default ranking function. It scores a document against a query by combining three factors: term frequency with saturation (the tenth occurrence of a word adds much less than the second), inverse document frequency (the rarity weighting above), and field-length normalisation (a match in a short title counts for more than the same match buried in a long body).

And then the part that is routinely got wrong. It is a common assumption that a search engine's ranking is a black box you must accept on faith. It is not. OpenSearch exposes an Explain API at GET /{index}/_explain/{id} (also POST /{index}/_explain/{id}), documented as returning "detailed information about why a specific document matches or does not match a query". The response is a nested tree of scoring contributions built on Lucene's TF-IDF/BM25 framework, with the individual inputs named — boost, idf (documented as "the inverse document frequency", measuring how rare a term is), tf, and the field-length inputs dl and avgdl — each with its computed value and a human-readable description, composed into the final score. — (verified)

So "we cannot use a search engine because we could not explain the score to an auditor" is false as stated. The per-document breakdown is a first-class API. What is true is that the explanation is expressed in retrieval terms — term rarity, frequency, field length — rather than domain terms, and it explains ranking, not a decision. Which is another argument for the two-stage pattern: let the engine rank, and make the decision in your own scorer, whose weights you chose and can defend.

Why embeddings and vector search are wrong for name matching

This is the item most worth internalising, because the instinct to reach for a model is strong and the reason it fails is genuinely non-obvious.

An embedding maps text to a vector such that texts with similar meaning land near each other. That is the property the model is trained for: "physician" and "doctor" are close because they mean the same thing, despite sharing few characters. Vector search then finds nearest neighbours in that space, usually approximately (HNSW, IVF).

Names have no meaning to capture. John Smith and Jon Smyth should match because they share characters — because one is plausibly a misspelling or transliteration of the other — not because they denote similar concepts. Semantic similarity is simply the wrong metric for the task, and the failure is not a tuning problem:

• The model normalises away the signal you need. Tokenizers and embeddings are built to be robust to surface variation so that meaning survives it. Name matching is entirely about surface variation. The model discards exactly the information you are trying to measure.
• Semantic neighbours are the wrong neighbours. In embedding space John Smith sits near other common Anglo names and generic person-name patterns, because that is what "similar meaning" amounts to for a name. Jon Smyth, a rare spelling, may embed some distance away.
• Rarity is inverted. Everything above says a rare token should dominate the score. An embedding model has seen rare names least, so its representations of them are the least reliable — the model is weakest exactly where the matching signal is strongest.
• Non-determinism and drift. The same input embeds differently across model versions, so re-embedding on an upgrade silently changes which pairs match, with no diff you can review. Character-based similarity is deterministic and reproducible years later, which matters in any audited context.
• It cannot be explained in the terms that matter. "Cosine similarity 0.87 in a 768-dimensional space" is not an account of why two people are the same person. "Surname edit distance 1, given names token-match, date of birth agrees, surname occurs in 400 of 190 million records" is.

The correct tool for names is character-level and token-level: trigrams and phonetics for retrieval, edit distance, token overlap and rarity weighting for scoring. Embeddings are the right tool nearby — for adverse-media text, for job titles, for descriptions, for anything where meaning is genuinely the signal. The error is applying them to the one field in the record that carries no semantics at all.

The two-stage pattern

Everything above assembles into one architecture:

STAGE 1 — RETRIEVE (cheap, wide, recall-oriented)
   trigram / GIN, phonetic blocking key, sorted-token key,
   search-engine query — union of several independent passes
   -> a few hundred candidates
                    |
                    v
STAGE 2 — SCORE (expensive, narrow, precision-oriented)
   Jaro-Winkler per token, Levenshtein, token-set overlap,
   IDF rarity weights, corroborating fields (DOB, nationality),
   Fellegi-Sunter weights -> one number per candidate
                    |
                    v
DECIDE — two thresholds: auto-match / review / auto-discard

The rule that governs it: retrieval must be wider than the decision. Stage one should return candidates that stage two will confidently reject, and if it never does, stage one is too narrow. The asymmetry is the whole point — stage two can discard a bad candidate, but nothing downstream can recover a candidate stage one never produced.

The classic failure is collapsing the two: deciding at retrieval time. It looks efficient and is always tempting, because filtering earlier means less work. It shows up as a similarity threshold applied inside the SQL WHERE clause, as a phonetic key treated as a match verdict, as LIMIT 10 on the retrieval query because ten results is what the UI shows. In every form the effect is the same: the decision is being made by the cheap, coarse, recall-oriented mechanism instead of the precise one, and every pair it drops is invisible — never scored, never logged, never reviewable, no error. The two failure modes below are both instances of exactly this.

Measured: what this costs on a real system

Everything above is mechanism, and the corpus sizes used to illustrate it are hypothetical. This section is not: the figures below are measurements from a production sanctions-screening system, and they are worth reading because the mechanism shows up clearly at a corpus far smaller than the 190-million-row examples used above.

The corpus and the index.

~474,000 names across ~273,000 entities
  names table        ~300 MB
  GIN trigram index   ~88 MB   (~29% of the table it indexes)
  whole database     ~655 MB
  trigram match       p50 53 ms   p90 289 ms

The index-to-table ratio is the number to carry: a GIN trigram index is a large fraction of the data it indexes, because it stores an entry per fragment rather than per row. That is the storage side of the same fact that halves ingestion throughput.

Where the time actually goes. Stage one — candidate retrieval — was 95% of total screening time. Not the scoring, not the decision logic, not the network: the retrieval. Warm per-name latency varied by an order of magnitude across four real queries:

Lindqvist    344 -  864 ms      <- rare name, small candidate set
Putin        413 -  438 ms
al-Assad    2012 - 2278 ms
Kony        2308 - 2536 ms      <- common fragments, huge candidate set

That spread is the whole lesson. The corpus is identical for all four queries; what differs is how many rows share trigrams with the query. Retrieval cost tracks candidate-set size, not corpus size — which is why a system can pass every benchmark on rare names and fall over on common ones, exactly where matching is hardest.

Why the common name is slow. A cold first hit for Kony took 2.7 seconds, and the query plan says why: a bitmap heap scan fetching roughly 6,000 heap blocks in order to re-check similarity() over a 9,494-row candidate superset. A GIN index returns row locations, not answers — the trigram match is lossy, so every candidate must be visited in the heap and re-checked. The index prunes 474,000 rows to 9,494; the remaining 9,494 random reads are the bill.

One measured strategy comparison. A single inbound name fans out to four to eight spelling variants that all have to be retrieved. Issuing them as four sequential trigram queries cost 1,312 ms of database time; issuing the same four as one CROSS JOIN LATERAL over the variant list cost 488 ms — 2.7x faster, with the candidate sets verified identical (zero rows differing in either direction). Nothing about the index, the threshold or the data changed. How you issue retrieval can matter as much as which index you built, because per-statement overhead is paid per variant and the variants are not optional.

Restructuring retrieval on that finding produced, warm:

Note the shape: the rare name improved most and the common name least, because the common name's cost is dominated by the heap re-check, which restructuring the query does not remove. Fixing the wrong stage would have moved these numbers barely at all.

Thresholds come from labelled data, not taste. A labelled set of 1,736 names with known verdicts moved the default similarity threshold from 0.85 to 0.70 — a change nobody could have justified by inspection. A larger benchmark of 1,536 labelled positives put recall at 75%, with an estimate of plus or minus 4.3 points at 95% confidence, and common-name precision at 14%. That last pair is the honest summary of this problem domain: recall is moderate, precision on common names is poor, and the two are traded against each other deliberately rather than accidentally.

What was labelled unmeasured — and what happened when it was measured. The same programme evaluated a blocking key as an alternative retrieval strategy and wrote, verbatim, that "nothing in this table is measured on our data", marking the blocking-key option "size not measured" and "test this first". The quoted figure that a computed key "cuts the field to about a hundred candidates" was derived arithmetic, not an observation.

It was then tested, and the derived figure was wrong in direction: the measured mean block was 596, against a trigram baseline of 244. Not "a hundred rather than a few hundred" — 2.4x larger than the thing it was proposed to replace, at 86.8% recall where the criterion was to match today's candidate sets exactly. The proposal did not survive contact with the corpus.

Two lessons, and the second is the one people miss. The obvious one is that the labelling saved the project: because the estimate was marked derived, the number was testable rather than load-bearing, and an unlabelled estimate becomes indistinguishable from a measurement once it has been copied twice. The subtler one is about the kind of error — a derived estimate is not simply imprecise, it can be inverted, because it is produced by a model of the data rather than by the data. The arithmetic assumed keys partition the corpus roughly evenly; real name distributions are savagely skewed, so the common blocks that dominate the mean are exactly the ones the estimate cannot see. Whenever an estimate depends on a distribution you have not looked at, treat its direction as unknown, not just its magnitude.

Failure mode 1 — a fixed candidate budget over a growing pool

The design: retrieval returns the top 50 candidates per query, which stage two then scores precisely. Fifty was chosen when the reference dataset held 5 million names, where it was comfortably generous.

The dataset grows to 190 million. Nothing in the code changes.

  5M names: query "MOHAMMED AL RASHID" -> ~180 rows share a blocking key
            top 50 taken -> true match is at rank 31     ✅ found
190M names: same query                 -> ~6,800 rows share a blocking key
            top 50 taken -> true match is at rank 1,190  ❌ never scored

The number of names competing for those 50 slots grew 38×; the slots did not. Recall falls continuously, and the degree of the fall depends on how common the queried name is — so it is worst exactly where matching is hardest.

What makes this severe is what it does not produce:

• No error. The query succeeds and returns 50 well-formed rows.
• No latency change. Stage two does exactly as much work as before — the cost is capped by the budget, which is the entire reason it was introduced.
• Nothing in monitoring. Throughput, error rate, p99, CPU, memory: all flat. Match count may even look stable, because common names still produce matches — just the wrong ones.

A fixed budget over a growing pool degrades silently, and monitoring built on errors and latency cannot see it. The only signals that can are ones you must deliberately build:

1. Measure recall against a labelled set on a schedule, not once at launch — this is the only direct measurement, and the number moving is the alarm.
2. Alert on truncation, not on failure. Record when retrieval returns exactly the budget, meaning it was capped. A rising truncation rate is the leading indicator, and it is available for free.
3. Track the score of the lowest-ranked candidate. If the 50th candidate's score is high, good candidates are being cut off below it; if it is low, the budget is genuinely sufficient.
4. Make the budget adaptive — derive it from the block size, or keep expanding until the marginal candidate falls below a score floor, rather than pinning a constant.

Failure mode 2 — a threshold that only works in one direction

The design: retrieval uses Postgres pg_trgm's % operator, then survivors are re-checked in application code against a configurable MinimumSimilarity.

-- Stage 1, in SQL: prunes at pg_trgm.similarity_threshold (default 0.30)
SELECT id, name FROM subjects WHERE name % :query;

// Stage 2, in code: re-checks against the configured floor
var hits = rows.Where(r => Similarity(r.Name, query) >= config.MinimumSimilarity);

Turn MinimumSimilarity up to 0.5 and results narrow, exactly as documented. The knob works.

Turn it down to 0.2 to widen recall, and nothing happens. Not "less than expected" — nothing. Every row between 0.2 and 0.3 was already removed by the SQL % operator, which pruned at the database's own default of 0.30 before the application ever saw a row. The application filter can only remove rows from a set that is already floored at 0.30; it can never add one back.

The knob appears to work because raising it does what you expect, and one-directional tests are the normal case — you tune a threshold by tightening it until precision looks right. The bug is only visible when someone tries to widen recall, and even then it presents as "lowering it didn't help much", which reads as a modelling limitation rather than an inert control.

The general shape, worth recognising anywhere: a filter applied twice, where the first application uses a default the second does not know about. The effective threshold is max(database_default, configured_value), and the configured value is only in force when it exceeds the default. Related instances: a client-side page size larger than a server-side cap, a retry count above a gateway timeout, a log level set below a sink's own minimum.

The fixes are all about making the two applications agree:

• Set the database threshold from the same config value — SET LOCAL pg_trgm.similarity_threshold = :minSimilarity in the same transaction, so there is one number.
• Use the explicit form — similarity(name, :query) >= :minSimilarity instead of %, so the threshold is in the SQL rather than in a session setting. Note this can forfeit index usage, which is often why % was used in the first place; the config-driven SET LOCAL is usually the better answer.
• Assert the invariant at startup — refuse to boot if the configured floor is below the database default, so the impossible configuration is a startup error rather than a silent no-op.
• Test both directions. The test that would have caught this is "lower the threshold and assert the result count increases".

Keeping index maintenance off the customer-facing path

There are two lessons in this section and the second is the rarer one. The first is the mechanism by which an optimisation aimed at writes turns into a read problem on a GIN index. The second is how to settle a design question honestly when the measurement that would settle it does not exist yet and cannot be taken — deciding on shape rather than on a benchmark, and knowing when that is legitimate.

The index in question is a Postgres trigram GIN index over normalized watchlist names: CREATE INDEX ix_watchlist_names_trgm ON "WatchlistNames" USING gin ("NormalizedName" gin_trgm_ops), created in PROOViD/AMLService/AMLService/Migrations/20260617062152_AddWatchlists.cs:83-88, and the candidate-retrieval query that rides it is in PROOViD/AMLService/AMLService/Infrastructure/Screening/LocalWatchlistProvider.cs:167. Everything below concerns the maintenance cost of that one index.

The question as it was actually posed: how do we keep the cost of writing to the index from hurting the customer-facing screening path? Ingest is bulk, machine-driven and tolerant of delay; screening is a synchronous request with a customer waiting on it. Three options were on the table:

• A — monthly partitions, an index per partition, a bulk build for the backfill. Expiry becomes dropping a partition.
• B — one table, GIN fastupdate enabled, so index writes are deferred into a pending list.
• C — one table, ordinary inserts, accept the cost.

A was chosen. The recorded rationale was not about write throughput at all: partitions make the expiry question a drop rather than a mass delete, which is the expensive half of retention. Revisit once the first real index exists; that is a build-time gate, not a reason to wait now.

Why B is a trap

GIN is an inverted index: one row contributes one posting-list entry per distinct key it contains, so a name yields as many index mutations as it has trigrams. fastupdate makes that cheap by not doing it — new entries are appended to an unsorted pending list instead of being merged into the tree. Writes get faster because the expensive part has been postponed, not removed.

The postponed work reappears on the read side, twice over, and the read side is the customer-facing one.

• Every search must scan the pending list linearly in addition to descending the tree. The pending list is unsorted, so there is nothing to prune with; the scan is proportional to how far ingest has run ahead of the merge. Read cost therefore grows with the ingest backlog — which is precisely the coupling the whole question was trying to break.
• The flush is not scheduled on a maintenance thread. It happens during autovacuum, or when the pending list exceeds gin_pending_list_limit — and in that second case the query that trips the threshold performs the merge itself. That query is an arbitrary customer screening request, chosen by nothing but timing.

So B converts a steady, predictable, known write cost into an unpredictable tail-latency spike on the exact path the change was meant to protect, and it does it in a way that is invisible in averages and shows up only in the tail, sporadically, on whichever request was unlucky. "Trades a write problem for a read problem" is not a figure of speech here; it names the mechanism exactly.

Why A works

Under partitioning each partition carries its own, smaller index. Three consequences follow structurally, without needing a number attached to any of them:

• Only the current partition takes live writes. Index maintenance is bounded by the size of one period's data rather than by the whole accumulated history, so the marginal cost of an insert stops growing as history grows.
• The backfill can be built per partition in bulk — load the rows first, build the index afterwards. Building an index once over a static set is a fundamentally different operation from maintaining it incrementally across every row insert, and it is the cheaper one.
• Partition pruning keeps reads off partitions the query cannot match, so a query constrained on the partition key never opens their indexes at all.

The retention half, which is what actually decided it

This is the argument that carried the decision, and it is about deletes, not inserts.

Under one big table, expiry is a mass DELETE. In Postgres a delete does not remove anything immediately: it writes a tombstone, marking the row dead but leaving it and its index entries in place. The index bloats with entries pointing at dead rows, reads pay to traverse them, and the space comes back only when VACUUM runs. That vacuum is heavy I/O contending with the read path — so retention reintroduces the same customer-facing latency spike, through a different door than B did.

Under partitions, expiry is DROP TABLE on the oldest partition: a catalog change plus a file unlink. No tombstones, no bloat, no vacuum debt, and no per-row work at all — the cost is independent of how many rows the partition held. That asymmetry is what made A the answer even before anything about write throughput was known, because retention was a hard requirement and mass deletion was going to be its most expensive operation regardless of how the write side turned out.

The price of A — state it, or the recommendation is not honest

• Partition creation must be automated, or it silently stops. A missing future partition means inserts start failing at a boundary nobody was watching. This is a new operational obligation, and it fails on a date rather than on a code change, which is the hardest kind of failure to attribute.
• Partition count is not free. The planner carries per-partition overhead, so a fine-grained scheme trades query-planning cost for maintenance granularity.
• Cross-partition queries get harder, and global uniqueness is genuinely harder — a unique constraint that does not include the partition key cannot be enforced across partitions.
• More objects to manage: one index per partition means more things to build, monitor, reindex and get wrong.

The part that matters most: this was decided on shape, not on a benchmark

Nothing in this decision was measured, and it could not have been. Settling it empirically would require an index built at one million, ten million and fifty million rows, and those builds were gated by a different open question that was still open. There is no latency figure, no throughput table, and no "N times faster" here — and the absence is deliberate. An invented number in a design record is indistinguishable from a real one six months later, and it will be quoted as if it had been taken.

What made deciding anyway legitimate was that the argument turned on directions and mechanisms, not magnitudes. "A mass delete leaves tombstones and needs a vacuum; a partition drop is a file unlink" is true at every scale, so no benchmark could reverse it. "A query that trips the pending-list threshold performs the merge itself" is a property of the implementation, not of the data volume. Reasoning from shape is sound exactly when the options differ in kind, and when the option you pick is also the one that is easier to reverse.

It would not have been legitimate if the choice had come down to magnitude — if both options had the same shape and the question were whether one is fast enough. "Is a per-partition GIN build fast enough to fit the maintenance window?" is a benchmark question and no amount of reasoning substitutes for running it. The test is whether flipping the unknown quantity could flip the answer: if it could, measure; if it cannot, decide and record why.

Finally, "revisit once the first real index exists" is a build-time gate, not a deferral. A deferral names no trigger and therefore never fires. A gate names the concrete event that makes the missing evidence available, and commits to re-examining then. That distinction is the difference between deciding under uncertainty and postponing a decision while pretending to have made one.