Exact nearest-neighbour search, declared like every other read

Status

In progress

Component

server

Priority

High — the owner put a RAG-capable vector store into 1.0.0

Blocked by

—

Blocks

SAPE-39; SAPE-38 needs its measurement

Why it is here

The owner decided that 1.0.0 is a vector database that can serve RAG — retrieval-augmented generation, where an application finds the passages most similar to a question and hands them to a language model. Measured before any of this was written: the engine had no vector code at all. A document body is unconstrained JSON, so a vector could already be stored as an array of numbers. Nothing could search by one.

sapedb does not produce embeddings. The application calls an embedding model and stores the vector it gets back; the database stores and searches. That is the same division every vector store draws, and it is said here so nobody expects otherwise.

What RAG needs from it, and how each maps onto this store

• The k nearest chunks to a query vector — the retrieval step itself. This ticket.
• The chunk's text back with the result, not only its key and distance. A RAG caller needs the passage to put into a prompt; returning only keys turns every search into a search plus k more reads. So the result carries the row's fields, through a declared projection exactly as scan and get do — which also lets a caller leave out the embedding itself, usually the largest field and the one nobody wants back.
• Searching within one document. Chunks are naturally keyed <document>/<chunk>, and a walk bounded to one document's key prefix is “search only in this document”. This store's range walk already provides that filter for free; the ticket proves it.
• Filtering on other fields — tenant, date, source. In exact search a filter applied during the walk is honest: more rows are scanned, and the answer is still the true top-k of the rows that pass. That is not true of filtering after an approximate index, where recall can collapse silently — one of the reasons SAPE-38 is its own decision.
• Replacing a document's chunks when it changes. Already possible: deleteRange clears a document's key prefix, and a batch writes the new chunks.
• Storing the vectors at a size a corpus can live in. Not today — as JSON text a vector is five times its size. That is SAPE-39, and it waits for this ticket on purpose.

Why exact comes first, and alone

Exact search compares every row in the range it walks and returns the true top-k. Its cost is declared — rows walked times dimension — and its answer is correct. That is this product's argument, kept intact the same way hashRange keeps it.

Approximate search (HNSW, IVF) is what a large RAG corpus eventually needs, and it breaks a different promise: not cost but correctness, and silently. That is SAPE-38. How far exact search stretches before approximate search becomes necessary is being measured now, at the dimensions RAG actually uses.

What it is

• The metric is a declared enumeration — cosine, L2, inner product — modelled on hashRange's decode: a choice written into the declaration, not an expression a caller composes.
• Two declared ceilings: k, and a row limit on how far it walks, both counted by the host per run — the lesson of W7, which both sibling primitives had to prove across a partition boundary.
• The dimension is declared, and a query of the wrong dimension is refused before a single row is read.
• A row whose vector is missing, malformed or the wrong dimension refuses, naming the key. A nearest-neighbour answer that silently skipped a row is a wrong answer that looks right.
• Ties break deterministically, so the same call returns the same rows in the same order.

The one open question inside it

What happens at the row ceiling. hashRange refuses, because a digest of part of a range is indistinguishable from a digest of all of it. deleteRange returns a cursor, because its answer says it stopped. The k nearest of a prefix are not the k nearest of the range, so an answer that stopped early without saying so would be silently wrong. Which precedent applies is being worked out with the implementation, and the reasoning will be on this page.

Out of scope

• Any approximate index — SAPE-38.
• Compact vector storage — SAPE-39.
• Keyword or hybrid search. Common in good RAG, and a separate feature.

Acceptance criteria

1. The answer equals a brute-force top-k computed outside the package from the same vectors — a guard that computes its expectation through the same code is circular.
2. Each metric is checked on vectors where the metrics disagree about the order, so a swapped metric fails.
3. The result carries the row's projected fields, so a caller gets the chunk text back in one call.
4. A search bounded to one document's key prefix returns only that document's chunks.
5. A wrong-dimension, missing or non-numeric row refuses and names the key; a wrong-dimension query refuses before any row is read.
6. Ties are deterministic, pinned with vectors built to tie.
7. The row ceiling is counted per run, proven across partitions.
8. Memory scales with k, not with the range — measured.
9. Every new guard watched failing.