# Secondary indexing engineering report

Implementation revision e0cde76, based on a37a35c. The storage prerequisite landed in 4ab93c9 and the document, shell and client integration in 0dc00da. The [index guide](SECONDARY_INDEXES.md) describes the API, wire commands, migration, uniqueness semantics and recovery procedure.

V3 uses an append-only, path-copying binary radix tree with checksummed variable-length records. One durable root covers documents, catalog, definitions and postings. V1 and the fixed-key PG2 prototype retain their separate formats. An explicit migration preserves the original and verifies the new file against every original key and value. No third-party storage engine or new Cargo dependency was added.

## Verification

Windows x86-64 GNU and Ubuntu x86-64 under WSL each passed 69 workspace Rust tests, documentation test targets, 21 additional core tests with default features disabled, strict all-target Clippy, formatting, and release builds. The release subprocess matrix passed 11 suites on Windows and 12 under WSL. The extra Linux suite exercises the terminal. Existing v1 and PG2 durability tests were retained. The portable core and PG2 also compiled for thumbv7em-none-eabi.

- The document tests cover backfill over duplicates, sparse uniqueness, mixed scalar types, unsupported values, paging, reuse after delete, atomic value swaps, failed batches, namespace isolation, and missing or mismatched physical claims. Each index operation was interrupted at every mutating adapter call under two persistence models. Every recovered image matched the old or new generation and passed the bidirectional document/posting audit. [Document tests](../crates/ratdb-document/tests/secondary.rs)
- The real-server test races authenticated inserts and edits, runs the requested shell transcript, and kills the server after observing the index builder extend the actual file. A second kill interrupts a 120-document indexed transaction. Restart verifies every proposed claim and document as one complete state. It also exercises an online backup and a served restore that rejects duplicates. The archived alpha fixture migrates with its empty den, named-warren data and typed values. The old executable refuses v3 while leaving its bytes intact. [Server and migration tests](../scripts/secondary_index_test.py)
- Ordered model tests exercise binary keys, seeking and reopen. Faults cover torn writes, uncertain syncs, a lost root mirror, repeated repair interruption, and a checksum-valid invalid discriminator. A compact backup excludes a deleted payload and preserves generation. [Core tests](../crates/ratdb-core/src/tests.rs)
- The sector and short-transfer file mocks commit and reopen a variable-key transaction. Adapters must preserve existing bytes on growth and satisfy the flush contract. Only the core and storage API compile without std. The JSON document layer, file tools and TCP clients still require their respective host facilities. Physical Asterhold hardware and real power-cut qualification remain open. [Adapter tests](../crates/ratdb-core/examples/asterhold.rs)

## Measurements

Release builds ran the same complete, successful username query on v3 before and after adding one unique index. Rows used zero-padded IDs and short distinct usernames. The target was the last ID. The scan followed every continuation. Query latency is the mean of three calls on the same open handle. The mutation probe inserts a key beside the middle ID, renames its indexed field and deletes it. FileStorage syncs the actual volume at commit. MemoryStorage syncs are no-ops. WSL file measurements used its Linux filesystem. These are single-host runs with warm data and a counting allocator. They do not estimate cold-cache behavior or tail latency.

|Host and adapter|Documents|Scan µs|Indexed µs|Build ms|Extra allocated bytes|Extra live bytes|Scan / indexed query heap bytes|Reopen and audit ms, scan / indexed|
|---|---:|---:|---:|---:|---:|---:|---:|---:|
|Windows RAM|100|83.4|9.4|0.60|0|5,791|921 / 976|0.5 / 1.5|
|Windows RAM|1,000|728.6|10.7|7.70|262,144|57,091|985 / 976|5.4 / 17.4|
|Windows RAM|10,000|8,519.2|13.9|96.70|5,242,880|570,091|985 / 976|66.8 / 210.3|
|Windows RAM|100,000|82,287.6|17.7|1,121.41|62,652,416|5,700,091|1,001 / 976|771.3 / 2,652.0|
|Windows file|10,000|78,682.6|214.6|1,260.80|5,242,880|570,091|985 / 976|1,131.6 / 3,553.0|
|Linux WSL RAM|100|78.1|110.4|0.75|0|5,791|921 / 976|0.5 / 1.9|
|Linux WSL RAM|1,000|754.6|13.4|9.46|262,144|57,091|985 / 976|6.6 / 23.2|
|Linux WSL RAM|10,000|7,824.5|17.2|120.22|5,242,880|570,091|985 / 976|79.4 / 279.1|
|Linux WSL RAM|100,000|84,767.6|20.6|1,394.10|62,652,416|5,700,091|1,001 / 976|914.7 / 3,293.9|
|Linux WSL file|10,000|18,950.5|180.8|289.06|5,242,880|570,091|985 / 976|212.7 / 654.2|

All indexed cases examined one document. The scan examined the entire den. On the 100-row WSL RAM run the indexed query was slower. At 100,000 rows, the indexed RAM query used 976 peak heap bytes above the pre-query baseline. This excludes the backing store, operating-system cache and process overhead. The live-byte column counts logical record framing, keys and values. Allocated extent growth includes private historical nodes created during backfill. At 100,000 rows the indexed file geometry reached 101,187,584 bytes. The operator can compact reachable records to another file.

### Mutation cost and write amplification

Each cell shows unindexed / indexed latency in microseconds followed by unindexed / indexed bytes written at the Storage boundary. The samples include all commit-record writes. The adapter byte counts exclude filesystem metadata, flash erase blocks and controller writes. At 100,000 keys the indexed field update wrote 1,208 bytes versus 860 bytes without the index, about 1.40 times as many. File latency is a single sample per mutation and varies with flush timing.

|Host and adapter|Documents|Insert µs · bytes|Update µs · bytes|Delete µs · bytes|
|---|---:|---:|---:|---:|
|Windows RAM|100|12.8 / 18.0 · 528 / 785|12.6 / 24.3 · 530 / 878|8.0 / 10.7 · 404 / 522|
|Windows RAM|1,000|11.5 / 22.8 · 641 / 898|14.8 / 27.9 · 643 / 991|8.6 / 12.7 · 517 / 635|
|Windows RAM|10,000|21.9 / 31.3 · 751 / 1,008|22.4 / 32.4 · 753 / 1,101|12.8 / 14.5 · 627 / 745|
|Windows RAM|100,000|22.9 / 39.3 · 858 / 1,115|24.5 / 40.1 · 860 / 1,208|13.9 / 17.8 · 734 / 852|
|Windows file|10,000|4,308.0 / 3,617.3 · 751 / 1,008|4,894.1 / 5,015.1 · 753 / 1,101|4,150.7 / 5,590.8 · 627 / 745|
|Linux WSL RAM|100|10.0 / 23.3 · 528 / 785|13.7 / 28.7 · 530 / 878|7.8 / 12.9 · 404 / 522|
|Linux WSL RAM|1,000|15.0 / 26.7 · 641 / 898|16.8 / 34.1 · 643 / 991|9.8 / 15.2 · 517 / 635|
|Linux WSL RAM|10,000|18.5 / 34.4 · 751 / 1,008|20.2 / 40.7 · 753 / 1,101|11.9 / 17.8 · 627 / 745|
|Linux WSL RAM|100,000|26.3 / 43.7 · 858 / 1,115|24.9 / 47.2 · 860 / 1,208|14.4 / 20.6 · 734 / 852|
|Linux WSL file|10,000|7,805.1 / 10,279.9 · 751 / 1,008|7,866.6 / 10,937.5 · 753 / 1,101|8,149.6 / 8,071.2 · 627 / 745|

Reproduce the memory series with `cargo run --release --locked -p ratdb-document --example index_cost`. Append `-- PATH_TO_UNUSED_FILE 10000` for the file run. The file benchmark refuses existing output paths. The complete host gate is `python -B scripts/verify.py` with the native Rust and Node toolchains. On Windows pass `stable-x86_64-pc-windows-gnu` as the script argument.

## Remaining engineering work

1. Qualify root durability and recovery on specific physical storage devices under power cuts.
2. Measure long-running, mixed workloads, including near-capacity behavior, skewed values and tail latency.
3. Reduce historical-node growth and qualify reclamation while retaining an independent checked backup.
4. Shorten the exclusive lock during large index builds and startup audits while preserving crash-safe publication.
5. Exercise a real Asterhold growth/flush adapter and measure RAM, flash wear and recovery on a physical board.