Case: Implement Search
"Search products by name" is, in V1, a loop over products checking whether a name contains the query. Meaning, state, operations, rules and examples first; database search, a full-text index and a search engine only when a measured reason arrives.
The situation, the reflex, and why it stalls
Every lesson starts where being stuck starts: someone has a problem, and the first move that comes to mind feels like progress.
Someone says "we need search" and you picture a search engine. What is the smallest thing that is honestly search, how do you derive it, and what would have to be true before the bigger things are justified?
The store has a product list and the founder wants a search box. You have heard of Elasticsearch and full-text indexes and relevance ranking, and you are not sure whether "search" without those is allowed to be called search.
Research search engines. Compare Elasticsearch with Meilisearch, read about inverted indexes and BM25, sketch a sync job from the product table to the index. It feels responsible: search is a known hard problem and you are taking it seriously.
A day of reading produces a comparison of engines and no search box. The product list has forty items; every engine in the comparison was built for a problem this store does not have, and none of the reading said what "matches" should mean for this catalog.
- A day of reading produces a comparison of engines and no search box. The product list has forty items; every engine in the comparison was built for a problem this store does not have, and none of the reading said what "matches" should mean for this catalog.
- The pasted engine integration returns results, but nobody wrote down whether "lap" should match "Laptop", whether case matters, or what an empty query returns. Those are the rules; the engine has defaults for all of them, and the defaults are now the product's behaviour by accident.
- There are no examples, so there is no way to say the search is right. "It returns something" is the only test, and the first complaint — "I typed Mouse and got nothing" — has no example to check against.
The move
Precisely enough to apply it to a problem you have never seen — not a slogan.
- Define search as a concept before choosing a mechanism: given a query, return the products whose name matches the query. Then say what "matches" means for V1 — contains, case-insensitive — as a rule, because that sentence is the whole specification.
- Discover the state: search itself remembers nothing in V1; it reads the product collection and the query. That is a finding — a concept with no state of its own is a pure function over someone else's state, and it can be implemented and tested in isolation (Pure Logic First).
- Write examples — normal, edge, invalid — and derive the algorithm from them: loop through products, check whether the lowercased name contains the lowercased query, collect matches. Annotate the cost: O(n × m) for n products of name length m, and say at what n that stops being fine.
- Then climb only on evidence: the loop → a database
WHERE name ILIKE→ a full-text index → a search engine. Each level exists because a measured reading — result time, catalog size, ranking complaints — said the previous one was insufficient (Add Complexity Only When Required).
Meaning, state, rules — the only hard word is "matches"
Search has an unusual state canvas: everything on it is derived from somewhere else. The products belong to the catalog, the query belongs to the request, and the result is computed. The finding is worth writing down because it makes V1 search a pure function — testable with three literal products — and because every later level adds state (an index, a cache) that V1 did not have.
The rules all live inside one word. The question ladder shows why "we need search" is not a specification and what the best form makes answerable.
- An empty query returns every product — decided by the example of a shopper clearing the box; the alternative (return nothing) is defensible and must be chosen on purpose.
- No match is a normal case with an empty result, not an error; the operation has no error cases in V1.
- Order of results is catalog order in V1 — ranking is a rule that does not exist yet, and pretending the loop ranks would be a lie.
why The best form is a list of examples with predicted answers. It can be implemented by a loop, tested this afternoon, and — because it says what matching means — survives the move to a database or an engine without changing behaviour by accident.
rule A product matches when its name, ignoring case, contains the query, ignoring case and surrounding whitespace.
↓ becomes validation Normalise both sides — trim the query, lowercase both — before comparing; never compare raw strings.
q = lowercase(trim(query)) matches(product) = contains(lowercase(product.name), q)
Examples, then the loop, then its cost
Five examples fix the behaviour. Two were surprising when first written: "MOUSE" finding Mouse is only true if the rule says so, and "" returning everything is a decision that a naive contains happens to make for the wrong reason (every string contains the empty string). Writing the example makes the accident a decision.
The algorithm is what the examples demand and nothing more: one loop, one normalised comparison, one collection. The trace below runs it on the first example so that the branch — the only decision the code makes — is visible.
- inputproducts = [Laptop, Mouse, Keyboard], query = "lap"
- lookupq = "lap"; for each product, lowercase(name) — "laptop", "mouse", "keyboard"
- branch"laptop" contains "lap" → true; "mouse" → false; "keyboard" → false
- mutationresults: [] → [Laptop] — search mutates only its own result list; products are untouched
- output[Laptop]
1function search(products, query):2 q = lowercase(trim(query))3 results = empty list4 for each product in products:5 if contains(lowercase(product.name), q):6 append product to results7 return resultsCost: one pass over n products, each a substring check of the name — O(n) checks, each O(m) in the name length. The cost is annotated so that the ladder's first trigger — "this pass is slower than the render" — can be measured rather than feared.
The ladder, with a trigger for every rung
The reflex started at the top of this ladder. The method starts at the bottom and climbs on readings. Each level below says what it adds and what measurement or requirement makes the previous level insufficient; a level without a trigger is a preference.
Notice where the state appears: the index at the third level is the first state search owns, and it brings a sync problem — the index can lag the products — that the loop and the database query did not have (Keeping a Search Index in Sync in Backend).
“We need a search engine.”
- ↓Why a search engine? Because search is hard and we want it done right.
- ↓Why is it hard here? It is not, yet — the catalog has forty products and the requirement is "find by name".
- ↓What does "done right" mean for this catalog? Case-insensitive contains, empty query returns everything, results in catalog order.
the claim was right when Relevance ranking, typo tolerance or faceted filtering are requirements, or the catalog is large enough that a measured database query is too slow — none of which is true of a forty-product store on its first day.
- V1 — loop over an in-memory arrayThe function above; five examples as tests. — The behaviour is fully specified by the rules and examples, and every product fits in memory.
- V2 — database query
WHERE lower(name) LIKE '%' || lower(?) || '%'returned by the same function signature. — The products now live in a database and loading all of them to filter in memory costs more than asking the database — a reading, not a guess (Why Is This Query Slow? Indexes explains why this query still scans). - V3 — full-text indexA tsvector or equivalent over the name and description; the query becomes a text-search query. — Substring matching cannot handle word forms or rank results, and a requirement for either has arrived — or the LIKE scan has been measured as the slowest query on the page.
- V4 — search engineA separate index synchronised from the product table; typo tolerance, facets, relevance tuning. — Ranking, typo tolerance and facets are product requirements the database index cannot meet, and someone now owns the sync path and the index lag.
The implementation ladder
Concept, examples, pseudocode, code, tests, production — for the concept this lesson is about. Code is the fourth tab, not the first.
Simple Search = Given some words a person typed, find the products whose names those words describe.
- Does a search have identity? No. A search is a question asked of the catalog, and the answer is computed each time. Two identical queries are the same question. The *products* have identity; the search does not, which is why V0 is a function and not a thing that is stored.
- Who owns it? Nobody owns a search; the catalog owns the products it runs over. When saved searches or search history arrive, *those* have an owner — a different concept.
- How long does it exist? For the duration of one call. Nothing persists — until V4, when an index is built ahead of time, and then the index has a lifetime and can go stale.
- Should it survive reload? The query in the URL should, so a result page can be shared; the results are recomputed. That is a frontend decision, not part of the concept.
- Is it a search engine? Not yet, and probably never. A search engine is a V6 answer to problems — fuzzy matching, ranking across fields, millions of documents — that a catalog of a thousand products does not have. Start with the loop.
- productscollection of Product (id, name)deriveSearch runs over the catalog; without it there is nothing to find.
- querystringdropWhat the person typed.
- normalisedNamestring per productdependsComparing lower-cased names each time repeats work.
- indexmap from word to product idsdependsAnswering a query without touching every product.
- scorenumber per resultdependsBetter matches should come first.
- read Search — the products whose name contains the query, in catalog order
- domain Rank (later) — the same matches, best first
- domain Index (later) — the index
- • Matching is case-insensitive.
- • An empty query returns nothing.
- • Results contain only products that match, each at most once, in a stable order.
- • Search never changes the products.
- • An index must say how stale it may be.
How to do it
Most important first.
- Write the meaning: "find the products whose name matches what the shopper typed". Underline "matches" — it is the only word whose meaning is not obvious, and every rule lives inside it.
- Ask what search must remember. For V1, nothing: it reads products and a query. Write that down; a later version that caches or indexes has state, and knowing V1 has none makes the later addition a visible decision.
- Write the operation contract: input query, reads products, changes nothing, output a list of matching products, errors none — an empty query is a case, not an error (Inputs, Outputs and Side Effects).
- Write the rules as sentences: matching is case-insensitive; a query matches anywhere in the name, not only at the start; an empty query returns everything or nothing — decide, and write the example.
- Write five examples with predicted outputs before running anything, then implement the loop and run them as tests (Examples Become Tests).
- Write down the reading that would justify the next level — "the loop takes longer than the page render at this catalog size" — so the upgrade has a trigger instead of a mood.
Worked on a concrete problem
The move has to produce something. This is what it produced.
- Meaning: return the products whose name matches the query. State: none of its own; reads products (the catalog's state) and the query (the input). Operations: one — search(query). That is unusually small, and it is honest: V1 search is a function.
- Rules: case-insensitive ("mouse" finds "Mouse"); contains, not prefix ("top" finds "Laptop"); whitespace around the query is ignored; an empty query returns every product, because the shopper who cleared the box expects the list back, not an empty screen. Each rule was found by writing an example and being surprised by the naive answer.
- Examples: products = [Laptop, Mouse, Keyboard]; search "lap" → [Laptop]; search "MOUSE" → [Mouse]; search " key " → [Keyboard]; search "" → [Laptop, Mouse, Keyboard]; search "tablet" → []. The last one is normal, not invalid — no match is a valid answer.
- Representation: the products are already an array; search needs no structure of its own. Cost: one pass, O(n) name checks, each a substring scan. At forty products that is nothing; at ten thousand it is still under the page render; at ten million the loop is the wrong level and the reading will say so.
- The ladder with its triggers: loop over an in-memory array (V1) →
WHERE lower(name) LIKE lower(?)when the products live in a database and the loop would mean loading them all → a full-text index when substring matching cannot rank or handle word forms → a search engine when relevance, typo tolerance and facets are requirements the database cannot meet.
How you know it worked
What now exists that did not before, and what question you can now ask.
- You can say what "matches" means in one sentence and point to the example that made each clause necessary.
- The search function has no state and no dependency beyond the product list, so it runs in a unit test with three hard-coded products.
- You can name the observation that would justify moving from the loop to the database, and from the database to an index — before either has happened.
- The word "Elasticsearch" has not appeared in the code, the schema or the plan, and you can say exactly which requirement would make it appear.
The questions you can now ask
The field this whole domain exists for. After this lesson, these are the questions to put to an unfamiliar problem.
- ?What does "matches" mean for this catalog — and which example forced each clause?
- ?Does this concept have state of its own, or is it a function over another concept's state?
- ?What does one search cost at today's catalog size — and at what size does the cost cross the page render?
- ?Which reading would justify moving to the next level of the ladder?
- ?What should an empty query return — and who decided?
What can go wrong
- The V1 loop is kept past its evidence. The catalog grows to a size where every keystroke loads every product from the database into memory to filter it — the reading that should trigger the next level was never written down, so nobody noticed.
- The rules are borrowed from an engine's defaults and never made explicit, so when the engine is swapped the behaviour changes and no test catches it.
- "Contains" is treated as the only possible meaning of matching. For a catalog of book titles, word-boundary or prefix matching is what users expect, and the rule should have been written from that catalog's examples, not the store's.
- The loop is the whole implementation for V1, which means the search box ships in an afternoon and has no ranking, no typo tolerance and no facets. Those are absent by decision, and the decision has to be revisited on evidence.
- Writing the rules explicitly means owning them: when a user expects "key board" to find "Keyboard", the rule says it will not, and someone has to change the rule rather than blame the engine.
- Deferring the engine means that if the catalog does reach the size where it is needed, the migration happens under pressure — mitigated by having written the trigger down.
- "A loop is not real search." It is search with a small rule set; a search engine is search with a larger rule set and an index. The concept is the same; the mechanism grows with the requirements, not with the vocabulary.
- "Use a full-text index from the start, it costs nothing." It costs a schema, a sync path and a set of matching rules you did not write and cannot easily state. The cost is small; it is not nothing, and it buys nothing at forty products.
- "Search has no state, so it is trivial." It has no state; it has rules, and the rules are where every complaint will land. The state finding makes it testable, not trivial.
Where this applies
Problem-solving advice is stated as universal far more often than it is. These labels say what each method is specific to — and where CONTESTED appears, the note gives the strongest form of the opposing view.
- ILLUSTRATIVEForty products, ten thousand and ten million are for the shape of the argument; the point at which the loop stops being fine is a measurement, not a number in a lesson.
- SCALE-SPECIFICThe loop is correct while every product fits in memory and one pass is cheaper than the render; it flips when the catalog lives only in a database or when ranking becomes a requirement, and the lesson's ladder names both triggers.
- DOMAIN-SPECIFICFor a product catalog, substring match on the name is what shoppers expect; for legal documents or logs, word forms, phrase queries and ranking are the requirement from the first day, and the ladder starts higher.
Where the depth lives
This domain asks the question and hands the answer off by name.