An engineer searches for “cache invalidation.” The service returns two documents. Behind that small response are several questions: which documents could participate, what “best” meant, which versions were searched, whether their contents could leave the service, and how much work finding them required.
This series studies those questions inside a search engine. Begin with the map here, then follow five mechanism chapters through identity, execution, filtering, visibility and distributed cost. You need basic sets and sorting; the vocabulary is introduced as we use it. Reading time covers prose, with additional time for the exercises.
Our recurring example is a synthetic engineering-document service: 50,000 documents, 10 queries/s and 20 updates/s in one region. These are scenario inputs, not measured capacity. Each chapter changes a requirement explicitly. The small tables here are complete teaching fixtures, not samples from a running database.
Documents and representations
A document is the logical unit the service retrieves. It can be a whole page or a passage cut from a page; choose that boundary explicitly. Our fixture retrieves one engineering document per result. A document ID identifies that unit across edits. Its storage address may change while its ID stays the same. A version distinguishes its successive states.
A field is a named part of the record: tenant, text, state, or the body vector. The corpus is the collection under consideration. A tenant identifies the customer or organization whose documents a request may search. Our service obtains tenant identity from trusted authentication context. A product’s namespace is a named API collection; do not assume it equals one tenant or one physical shard.
Search uses representations of the content. A tokenizer splits text into tokens; normalization produces the terms indexed for lexical search. For this toy only, lowercase words separated by spaces are terms. Production tokenization has decisions about punctuation, language and normalization. An embedding represents content as a vector of numbers produced by a model. Dense vector search ranks those representations using a declared distance or similarity function. The model, selected field and metric are part of the contract.
Our service initially stores one body vector per document: 768 numbers, each stored as float32, a four-byte floating-point value. Squared Euclidean distance adds the squared differences between corresponding coordinates; smaller means closer under this metric. We do not run an embedding model here. The saved distances below are stipulated for one query vector; they were not calculated from the illustrative text.
| doc_id | tenant | state | text | distance |
|---|---|---|---|---|
| 1 | A | live | cache invalidation guide | 0.2 |
| 2 | B | live | cache invalidation incident | 0.1 |
| 3 | A | live | cache replication guide | 0.2 |
| 4 | A | deleted | cache invalidation draft | 0.0 |
| 5 | A | live | storage snapshot guide | 0.5 |
| 6 | B | live | snapshot invalidation guide | 0.3 |
These definitions describe how this series uses the terms. Different products may choose different document boundaries, ID scopes or representation rules. Keep that choice visible when comparing them.
Indexes and candidates
An index is an access structure that helps locate records without reading every record’s complete contents. Lexical search uses indexed terms. An inverted index maps a term to documents containing it; a posting is one document’s membership, optionally with scoring metadata. The term dictionary locates each posting list.
The Stanford IR book’s index-construction chapter connects tokenization, normalized terms, document IDs and sorted postings. Selected entries in our miniature index are:
| term | doc_ids |
|---|---|
| cache | [1,2,3,4] |
| invalidation | [1,2,4,6] |
| guide | [1,3,5,6] |
| snapshot | [5,6] |
cache AND invalidation intersects two lists, producing [1,2,4] before tenant/live restrictions. This Boolean query is a membership question. Ranked lexical search instead scores matching documents and orders them by the declared rule. BM25 is a common scoring scheme using term counts, document length and term rarity in the corpus. A term posting does not contain the full document text.
A candidate is a record admitted for further evaluation by a plan. Being a candidate does not establish eligibility, a final rank or permission to disclose content. An access path is how a plan reaches candidates: intersect postings, enumerate matching attributes, traverse a vector index, or scan eligible vectors exactly.
An approximate nearest-neighbor index, abbreviated ANN, can avoid evaluating every vector by exploring promising regions. Approximation can miss better neighbors. Exact and approximate paths may coexist; pgvector v0.8.6 documents exact search on small filtered populations as well as approximate paths. “Use an index” does not always mean “use ANN.”
Hybrid lexical-and-dense retrieval combines their candidates or results under an explicit fusion or reranking rule, as pgvector’s hybrid-search discussion illustrates. Lexical scores and embedding distances are not automatically comparable. ACORN calls vector search with structured predicates “hybrid”; name the components rather than infer the contract from that word.
Answers and quality
A predicate is a condition a record satisfies or fails. Eligibility here means belonging to the trusted tenant and being live at the selected search snapshot, plus any query predicates. A snapshot is the logical database state chosen for the read. Top-k means up to k distinct eligible documents under a specified total order, including its tie rule.
For our dense query, select exactly one named field, body, with one vector per document. Sort by squared Euclidean distance ascending, then doc ID ascending. Other metrics are possible; combining several fields or many vectors per document needs a separately defined document score.
Tenant A’s eligible IDs are [1,3,5]. Its exact top-2 is [1,3]: doc1 wins the distance tie by ID. Doc4’s distance cannot override deletion, and doc2 cannot enter A’s answer. The exact eligible oracle is the exhaustive answer under that same snapshot, predicate, field and order.
Keep exact-neighbor fidelity separate from judged relevance. An approximate result [1,5] contains eligible IDs but misses doc3. Its eligible-neighbor recall is |result ∩ oracle| / |oracle| = 1/2. That measures agreement with the distance oracle. Whether either document helps the engineer requires relevance judgments or task evaluation, as the IR evaluation chapter explains.
Predict two kinds of answer
Keep the table’s snapshot fixed. For tenants A and B, calculate the eligible Boolean AND matches and the dense top-2. Then request five dense results as A and two as C. Finally calculate recall for A’s approximate [1,5], using the top-2 oracle. Write your answers before opening the check.
Check membership, nearest neighbors and smaller populations
| case | boolean_AND_ids | dense_ids |
|---|---|---|
| A-k2 | [1] | [1,3] |
| B-k2 | [2] | [2,6] |
| A-k5 | [1] | [1,3,5] |
| C-k2 | [] | [] |
The AND query requires both terms; the dense query uses saved distances and imposes no term-membership requirement. They answer different contracts. A’s approximate [1,5] has recall 1/2 against [1,3]; its count of two is insufficient evidence of exactness. For k=5, only three eligible documents exist. C legitimately receives an empty result; its empty-oracle recall is N/A because the denominator is zero.
A pass includes each list, A’s smaller-ID tie, the recall denominator, and why the lexical and dense answers differ. This checks the model, not the quality of a real embedding.
The search system map
The following map locates the whole problem. Its arrows organize logical obligations, rather than prescribe one physical execution order. Filtering can happen before, during or after ANN navigation; operators can be fused. Every chosen plan must still honor its answer and disclosure contracts.
Read path
- Trusted request and representation
Authenticate tenant; turn query text into terms or the selected-field query vector.
- State, eligibility and candidates
Choose the read contract and snapshot; use compatible access paths to obtain candidates.
- Resolve, score and select
Use the snapshot's document versions; rank distinct eligible documents under one declared order.
- Project and authorize disclosure
Fetch requested fields from selected versions; check trusted current policy before returning or forwarding content.
Write path
- Prepare an authorized update
Identify document/version; validate fields, terms and embeddings for the intended content.
- Establish durable authority
Commit under the declared write contract before promising durable success.
- Maintain and publish derived state
Update indexes and compatible read state; reads may also reconcile recent committed updates.
- Compact and reclaim safely
Merge stored structures; retain versions and deletion barriers required by readers or recovery.
Application boundaries
- Upstream preparation
Choose document/chunk boundaries, extract text, generate embeddings and preserve source versions.
- Search engine
Manage document identity, access paths, query state, ranking, storage and distributed execution.
- Downstream use
Authorized results may be reranked, displayed or used as evidence for generation; evaluate that application separately.
Conceptual map for the synthetic service. Write maintenance and reads overlap. A recent-write path can make data query-visible before index construction finishes. Authorization precedes every content disclosure.
In words, the read starts with a trusted tenant and a query representation. It chooses state and obtains enough candidates for its retrieval contract, resolves versions and eligibility, ranks, then fetches requested fields. Projection names that field fetch. A trusted disclosure decision gates content leaving the service, including forwarding to an external reranker.
The write identifies an authorized change and commits it to durable authority. Index maintenance makes efficient paths reflect it; publication exposes compatible state to readers. A recent-update path may bridge index lag. Compaction organizes storage, while reclamation needs proof that required readers and recovery no longer depend on old state.
Upstream, changing chunk boundaries or embedding models changes the data and retrieval contract. Downstream, reranking rescores a retrieved candidate set; it cannot recover a document absent from that set. Retrieval-augmented generation, or RAG, uses retrieved evidence when generating an answer. The existing retrieval-to-RAG chapter covers that application layer; this series follows the engine beneath it.
Time and disclosure
Use these words separately:
| Term | Meaning in this series |
|---|---|
| Durable | The change survives the failures covered by the declared storage contract. |
| Acknowledged | The service returned success under its stated promise; inspect what that promise includes. |
| Indexed | Published derived index state incorporates the change. |
| Query-visible | The selected read path includes the change; it need not win a top-k slot. |
| Cached | A node holds a reusable copy; residency does not prove freshness. |
| Authorized to disclose | Trusted policy permits content to leave at a defined decision point. |
turbopuffer’s architecture documents durable object-storage writes, asynchronous indexing and search of recent unindexed data. Its Query API distinguishes strong queries, which include all writes before query start, from eventual queries, which search at most 128MiB of unindexed writes and can be stale. These are named product contracts, not universal meanings of “searchable.”
Predict the update boundary
Stipulate that doc1’s deletion commits durably and is acknowledged, while the base index still has the old row. A fresh read includes that deletion through its recent-update path. What is A’s exact dense top-2 now? Must the base already be rebuilt? Separately, an allowed historical snapshot returned [1,3], but current trusted policy assigns doc3 to B at the disclosure decision. May its text go to an external reranker for A?
Check visibility and permission separately
The fresh exact answer is [3,5]. Resolving the committed deletion suppresses doc1 before selection. The base can lag because this stipulated read reconciles the recent change; durable, indexed, visible and cached are distinct states.
For the separate historical read, deny doc3’s content to A before forwarding or returning it. Historical eligibility does not establish current disclosure permission. This toy specifies a trusted check and its timing; it does not design a production permission protocol or prevent policy changes after that point.
A pass names [3,5], the recent-update path, and the denial before external disclosure.
Execution and resources
CPU, memory, storage and failures cross both paths. Vectorized execution processes batches of values, as DuckDB’s execution format illustrates; it is different from search over embedding vectors. SIMD instructions can operate on several values at once, but batching does not guarantee their use.
A cache reuses local copies. A cold query needs data absent from the relevant cache; state which cache and data you mean. Remote requests, transferred bytes, and dependent I/O rounds are separate costs: three requests issued together differ from three whose addresses are discovered sequentially.
A shard holds part of the corpus. Fanout sends work to required shards; merge combines their answers under a compatible order and state contract. Missing a required shard can make a full-looking result incomplete. Recovery reconstructs valid state from declared authority, rather than trusting an arbitrary surviving cache.
Storage maintenance introduces further work. A WAL, or write-ahead log, records recoverable changes. Compaction merges stored structures; a tombstone records deletion so an older live copy does not reappear. SlateDB’s overview makes those mechanisms concrete, and its snapshot documentation shows why active readers can keep old state alive. Those sources describe SlateDB, not turbopuffer’s private implementation.
Keep logical changed data, serialized index material, WAL/compaction bytes, remote traffic, CPU and latency in separate columns. Reducing one can increase another. Measure end-to-end latency distributions and result fidelity under the actual update, cache and failure workload before declaring a design faster.
Where the six chapters go
| Part | Question on the map | Artifact to carry forward |
|---|---|---|
| 1. This primer | What are the objects, paths and obligations? | A vocabulary and request/update map. |
| 2. Identity and layout | Which references move when a vector moves? | An update/reference trace and byte comparison. |
| 3. Query execution | Which work can be skipped safely, and how cheaply can the rest run? | A skip proof and measurement plan. |
| 4. Eligible neighbors | How do predicates change candidate access? | An exact baseline and fallback decision. |
| 5. Write visibility | Which versions have authority, including after failure? | A snapshot/recovery trace. |
| 6. Storage and shards | Can the complete answer fit the resource and failure budget? | A defensible architecture revision. |
Your exit artifact is one page: define your document boundary and IDs, fields and representations; write one query’s predicate, snapshot, order and disclosure point; trace one update to authority and visibility; then label the CPU, cache, remote and shard boundaries. Record a question to revisit in each mechanism chapter. Extend this into the capstone’s decision note.
For foundations, read the linked Stanford index-construction and evaluation selections, then pgvector’s exact/approximate filtering discussion. For the temporal path, read the named Query contract alongside architecture and SlateDB snapshots. RIP, vector database motivates the identity chapter: its September 30, 2026 account describes an in-progress migration with a performance regression and tuning beginning, not a delivered speedup.
Database Internals (Alex Petrov, 2019) and Designing Data-Intensive Applications, second edition (Martin Kleppmann and Chris Riccomini, March 2026), are study bridges for storage, maintenance, partitioning and consistency. Their full texts were not accessed for this series; the explanations here use the inspected accessible sources. No engine benchmark or learner assessment is claimed.