[P3][lens] Secondary indexes for document and relational queries

[cevheri]

Summary

Roadmap item (README "Next"; DESIGN.md section 6 lists secondary indexes as an honest v1 deferral for both the document and relational lenses). Today every find()/where() is an O(n) collection scan by design; secondary indexes are the single largest lever on the query surface.

Why

• The performance envelope (README) documents the O(n) scan honestly; indexes move the practical ceiling for read-heavy workloads.
• The kernel already provides everything an index needs: ordered byte keys, composite-key ranges, and atomic multi-key transactions — an index is a lens-level convention (<reserved>index:<ns>:<field>:<value>:<id> style keys), not a kernel feature.

Scope sketch (exploratory — each choice must earn its place against the comprehension budget)

• Index maintenance inside the same transact() as the row write (atomic by construction).
• A catalog entry per index so cold-opening tools (Studio) can render them; reserved-namespace placement.
• Query planning stays trivial: equality-predicate lookup via index when one exists, scan otherwise — no planner.
• Open questions: value encoding for ordered numeric keys, index backfill for existing data, multi-field indexes (defer?).

Constraints

• Kernel (src/core.ts) unchanged — this is lens-level, open-edge work.
• No silent behavior changes to unindexed queries.
• Changeset (minor) when it ships; bun run gate green with 100% coverage.

[harish18092002]

Use case: A lookup on a non-primary-key field, such as users.where({ email }), is probably the most common query in a typical app after primary-key get. Today, this appears to be an O(n) scan on every call (find in relational.ts / document.ts), so performance scales linearly with collection size. For example, a 1M-row table means up to 1M row comparisons per lookup.

Why it matters for the test/dev beachhead: Even in development, seeding realistic data with tens of thousands of rows can make repeated where / find calls noticeably slow. That pushes people back toward mocks, which works against LibreDB’s “real store instead of mocks” pitch.

Fit note: This seems like it belongs above the trust boundary, in the lens layer, so core.ts can remain a pure ordered-KV store. An index can simply be additional KV entries under a reserved prefix, maintained by the lens during writes. Happy to help prototype this if useful.

Has a rough design direction already been decided? For example, should index entries be stored as \x00...index:... keys and maintained in the same transaction as the write, or is that still open? @cevheri

[cevheri]

Thanks for the thoughtful questions — they pushed us to settle the design direction. Both of your specific questions have answers now, and since this comment will serve as the design record for this issue, I will also explain the reasoning: every choice below follows from the project's philosophy (MANIFESTO.md, docs/DESIGN.md) — a small guarded kernel, conscious omission, no magic, readability as a design constraint.

The root idea first. A secondary index is derived data — a second, reorganized copy of the truth (value-to-id instead of id-to-row). The one real danger with derived data is drift: if the index ever disagrees with the rows, the database returns wrong answers silently, which is the worst failure class a database has. Almost every decision below answers one of two questions: how does the copy never get a chance to lie, and how does it stay cheap to understand.

1. Reserved prefix — yes, exactly as you guessed.

\x00libredb:index:<collection>:<field>:<valueLen>:<value>:<id>

• Why \x00: the kernel is one ordered byte space; \x00 sorts before every printable character, so internal entries cluster at the front and never interleave with user data. The convention also already exists — the catalog lives at \x00libredb:catalog: and isReservedKey already guards it. We reuse a convention readers have already learned instead of inventing a second one.
• Why the length prefix: : is the delimiter and can also appear inside a value, so two different facts could otherwise produce identical bytes (value a:b + id 7 vs value a + id b:7). <valueLen> (the byte length of the serialized value) makes the parse unambiguous by construction. We chose it over escaping because escaping rewrites the value's bytes — a hex dump would no longer show the real value, and "nothing is hidden" should hold for the file's bytes too.
• Equality lookup is an exact-prefix range scan over ...:<field>:<valueLen>:<value>:, reusing the same prefixRange mechanism collection scans already use.
• Why lens-level, not kernel: an index is rebuildable derived data — if lost, it is regenerated from the rows — so it does not earn a place inside the guarded durability core. core.ts stays unchanged. This is the same reasoning FoundationDB uses: indexes are a layer convention, not a kernel feature.

2. Same transaction — yes. The only moment an index can drift from its row is the window between the two writes. The kernel's transact() already gives atomic multi-key commits — document.ts's put() already writes the row and its catalog entry in one commit — so the zero-window option is free. Index maintenance joins that same transaction: insert writes the entry, update deletes the old-value entry and writes the new one, delete removes it. The alternative (async index maintenance) buys throughput at the price of readers seeing a stale index — exactly the kind of hidden behavior the manifesto forbids.

A few more decisions that came out of settling this:

• v1 scope: equality-only, single-field. find/where only support top-level equality today (DESIGN.md 6.1/6.2 defer query operators), so range support would be capability nothing can use yet — and order-preserving numeric encoding is genuinely subtle (IEEE 754 negative floats sort backwards as raw bytes). Conscious omission: that complexity has to earn its place first. Composite (multi-field) indexes are deferred for the same reason.
• Values are always JSON-stringified and restricted to primitives (string/number/boolean/null). An index is a claim that value equality can be translated into byte equality. find uses structural equality (1 !== "1"), and always-JSON keeps them distinct as bytes (1 vs "1"). Objects break the claim — {a:1,b:2} and {b:2,a:1} are structurally equal but serialize differently — so v1 refuses to index them rather than build canonicalization. The invariant: an indexed lookup must never return (or miss) anything a scan would not.
• Backfill is synchronous and eager, and the catalog entry is written last. createIndex on a non-empty collection scans and backfills (chunked into multiple transactions for large collections), and only then records the index in the catalog. This is the WAL commit-record pattern applied again: data first, the mark that makes it real last. If a crash interrupts backfill, no catalog entry exists, so queries never trust a half-built index — the worst case is slow-but-correct (fallback scan), never wrong-but-silent. Orphaned entries under the reserved prefix are inert and overwritten on retry.
• Index definitions live in the existing catalog registry. DESIGN.md 6.3 already names "a secondary-index catalog" as the deferred next entry there — this is the doorway the design left open, not a new concept. It also makes the file self-describing: on reopen the lens learns which indexes to maintain from the file itself (if definitions lived only in application code, a writer that forgets to redeclare an index would silently stop maintaining it — drift again), and cold-opening tools like Studio get index visibility for free.
• No planner. With single-field equality indexes there is never more than one candidate per predicate, so a planner would choose among zero or one option. The rule is one documented, deterministic sentence: a single-field equality predicate on an indexed field uses the index; everything else is the existing O(n) scan, byte-for-byte unchanged. Planners (statistics, cost models) are where databases turn into black boxes; refusing one is the manifesto's core move.

Your prototype offer is very welcome. The natural shape is a shared module (src/lens/index-store.ts) that both document.ts and relational.ts call — they already share the same underlying key scheme, mirroring how catalog.ts serves both lenses. One correctness note for a prototype: the field argument needs the same validation the catalog applies to names (reject \x00 and :), otherwise a field name could break the key format. MANIFESTO.md and docs/DESIGN.md are short and worth reading before prototyping — they explain why the answer to most "should we add X?" questions here is a deliberate no. Happy to review a PR.