diff --git a/.github/SECURITY.md b/.github/SECURITY.md index 9509777b88..41c5befe88 100644 --- a/.github/SECURITY.md +++ b/.github/SECURITY.md @@ -9,8 +9,8 @@ patched unless a separate security advisory explicitly says otherwise. | Version | Supported | | ------- | --------- | -| latest 1.x minor line | ✅ | -| older 1.x minor lines | ❌ | +| 2.x (latest release) | ✅ | +| 1.x | ❌ | | 0.x | ❌ | ## Reporting a Vulnerability diff --git a/.github/workflows/bench.yml b/.github/workflows/bench.yml index d3efe0b37e..2b28408a02 100644 --- a/.github/workflows/bench.yml +++ b/.github/workflows/bench.yml @@ -8,6 +8,7 @@ on: permissions: contents: read issues: write + actions: read # read the previous night's job logs to confirm an alert repeats jobs: compile: @@ -212,6 +213,7 @@ jobs: id: bencher continue-on-error: true run: | + set -o pipefail bencher run \ --project minigraf \ --token "${{ secrets.BENCHER_API_TOKEN }}" \ @@ -222,42 +224,111 @@ jobs: --threshold-upper-boundary ${{ matrix.threshold }} \ --err \ --adapter rust_criterion \ - --file ${{ matrix.file }} - - - name: Open regression issue + --file ${{ matrix.file }} \ + 2>&1 | tee bencher_out.txt + + # Shared CI runners are noisy, so one alert on its own is usually a slow + # runner, not a regression. Report only benchmarks that also alerted in + # this suite on the previous run. If a regression issue is already open, + # add a comment to it instead of skipping, so later alerts stay visible. + - name: Report regression if: steps.bencher.outcome == 'failure' uses: actions/github-script@v6 + env: + SUITE: ${{ matrix.name }} with: script: | - const today = new Date().toISOString().slice(0, 10); - const title = `Benchmark regression - ${today}`; + const fs = require('fs'); + const { owner, repo } = context.repo; + const suite = process.env.SUITE; + const jobName = `bench / ${suite}`; + + // Bencher lists each alert as "- (Latency): <.../alerts/>". + // The "View results" lines use /perf? URLs, so they do not match. + const alertRe = /- (\S+) \(Latency\): https:\/\/bencher\.dev\/console\/projects\/[^/\s]+\/alerts\//g; + const parseAlerts = text => new Set([...text.matchAll(alertRe)].map(m => m[1])); + + const current = parseAlerts(fs.readFileSync('bencher_out.txt', 'utf8')); + const runUrl = `${context.serverUrl}/${owner}/${repo}/actions/runs/${context.runId}`; + + let body; + if (current.size === 0) { + // Bencher failed without listing alerts (API or upload error). + // Report it at once so a broken setup does not go unnoticed. + body = [ + `Bencher failed in the nightly benchmark run (${suite}) but listed no alerts. This is likely an API or upload error.`, + '', + `**Run:** ${runUrl}`, + ].join('\n'); + } else { + // Find this suite's job in the previous completed run and read its alerts. + let previous = new Set(); + let previousUrl = null; + try { + const { data: runs } = await github.rest.actions.listWorkflowRuns({ + owner, repo, + workflow_id: 'bench.yml', + branch: 'main', + status: 'completed', + per_page: 10, + }); + const prevRun = runs.workflow_runs.find(r => r.id !== context.runId); + if (prevRun) { + previousUrl = prevRun.html_url; + const { data: jobs } = await github.rest.actions.listJobsForWorkflowRun({ + owner, repo, run_id: prevRun.id, per_page: 100, + }); + const prevJob = jobs.jobs.find(j => j.name === jobName); + if (prevJob) { + const { data: log } = await github.rest.actions.downloadJobLogsForWorkflowRun({ + owner, repo, job_id: prevJob.id, + }); + previous = parseAlerts(typeof log === 'string' ? log : Buffer.from(log).toString('utf8')); + } + } + } catch (err) { + core.warning(`Could not read the previous run's alerts: ${err.message}`); + } + + const repeated = [...current].filter(b => previous.has(b)).sort(); + console.log(`Alerts this run: ${[...current].join(', ')}`); + console.log(`Alerts in previous run: ${[...previous].join(', ') || 'none'}`); + if (repeated.length === 0) { + core.notice(`No benchmark in ${suite} alerted on two runs in a row. Not reporting.`); + return; + } + + body = [ + `Bencher flagged these benchmarks in the nightly run (${suite}) on two runs in a row:`, + '', + ...repeated.map(b => `- \`${b}\``), + '', + `**Run:** ${runUrl}`, + `**Previous run:** ${previousUrl}`, + '', + 'Please review the Bencher dashboard to confirm the regression.', + ].join('\n'); + } const { data: openIssues } = await github.rest.issues.listForRepo({ - owner: context.repo.owner, - repo: context.repo.repo, + owner, repo, labels: 'performance', state: 'open', per_page: 100, }); - const existing = openIssues.filter(i => - i.title.startsWith('Benchmark regression') - ); - if (existing.length > 0) { - console.log(`Skipping: open regression issue already exists (#${existing[0].number})`); + const existing = openIssues.find(i => i.title.startsWith('Benchmark regression')); + if (existing) { + await github.rest.issues.createComment({ + owner, repo, issue_number: existing.number, body, + }); + console.log(`Commented on open regression issue #${existing.number}`); return; } - const runUrl = `${context.serverUrl}/${context.repo.owner}/${context.repo.repo}/actions/runs/${context.runId}`; + const today = new Date().toISOString().slice(0, 10); await github.rest.issues.create({ - owner: context.repo.owner, - repo: context.repo.repo, - title: title, - body: [ - `Bencher detected a performance regression in the nightly benchmark run (${{ matrix.name }}).`, - '', - `**Run:** ${runUrl}`, - '', - 'Please review the Bencher dashboard for details on which benchmarks regressed.', - ].join('\n'), + owner, repo, + title: `Benchmark regression - ${today}`, + body, labels: ['performance'], }); diff --git a/CHANGELOG.md b/CHANGELOG.md index 557cbc003a..5b054e5d64 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -17,6 +17,48 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - Two values of the same attribute written in one transaction are both returned by every query path. Previously only one came back, and entity-bound and attribute-bound queries could return different ones (#371, #287). - A retract that removes several values of one attribute in one call now hides all of them (#371). +## Unreleased on v2.x (main) — v2.0.2 + +These changes ship first in v2.0.2 from `main` and are merged into the `v3` branch. + +### Performance + +- **Bound-entity point queries no longer pay for other attributes' history (#323).** `[:e :attr ?v]` now range-scans only `(e, :attr)` in the EAVT index instead of every record the entity has ever written. Reading a rarely changed attribute of a heavily rewritten entity no longer slows down as that entity's history grows: with 2,000 retract/reassert cycles on another attribute of the same entity, it drops from 4.58 ms to 19.0 µs. Reading the heavily rewritten attribute itself, and attribute scans (`[?e :attr ?v]`), are about 1.35–1.4× faster (4.64 ms → 3.36 ms), from cheaper net-assert grouping and removing a redundant dedup pass. The file format is unchanged. +- **Attribute scans are bounded to exactly the queried attribute (#381).** `[?e :attr ?v]` computed the end of its AEVT range by incrementing the attribute's last byte. For attributes whose last byte is `0x7F` or `0xBF` — including about 1 in 64 non-ASCII characters, such as `:丿` or `:ÿ` — the result was not valid UTF-8, so the scan ran to the end of the whole AEVT index and read every later fact before filtering. It also read facts for prefix siblings (`:ab`, `:a/b` when scanning `:a`). The range now ends at `attribute + "\0"`, which covers exactly one attribute. Scanning 100 `:丿` facts in a checkpointed file with 40,000 facts on neighbouring attributes drops from 45.4 ms to 251 µs. Results are unchanged. + +- **Checkpoints no longer re-encode the whole index (#315).** `checkpoint()` decoded and re-serialised every entry of all four covering indexes and re-read every page of the file for its checksum, so checkpointing after one new fact cost almost as much as after thousands. Index leaves that receive no new entries are now copied verbatim, only the leaves that do are decoded and re-split, and unchanged fact pages are no longer re-hashed. Leaves are still bounds-checked and the leaf chain is checked for cycles, so a damaged index fails the checkpoint instead of being copied forward. Checkpoint after one new fact drops from 246 ms to 26.3 ms on a 100k-fact file and from 23.9 ms to 4.0 ms at 10k. Cost still grows with graph size, because the index pages are copied on every checkpoint; the file format is unchanged. The `checkpoint()` and `wal_checkpoint_threshold` docs now state that a checkpoint is not a durability boundary: the WAL is already crash-durable. + +### Fixed + +- **A power loss could lose a new database or WAL file, or bring back a deleted WAL (#389).** On Linux and other POSIX systems, a created or deleted file survives a power loss only once its parent directory is fsynced; Minigraf fsynced file contents but never a directory. Creating the `.graph` file or the `.wal` sidecar, and deleting the WAL after a checkpoint, now fsync the parent directory after the file operation. A resurrected WAL was already harmless, since replay skips entries at or below the last checkpointed transaction, but a lost `.graph` or WAL lost committed data. Windows needs no directory sync and is unchanged. Process kills were never affected, because they leave the OS page cache intact. +- **Recursive rules failed with a literal start when the recursion goes through another rule (#297).** `(query [:find ?y :where (chain :a ?y)])` over `(chain ?x ?y) :- (link ?x ?mid) (chain ?mid ?y)` failed with `Unbound variable in rule head: ?mid` (INT-022). The magic-sets rewrite, which runs when a rule argument is given as a literal, dropped earlier rule calls from the rules that pass bindings to the next call, so a variable bound only by such a call (here `?mid`, bound by `link`) was never bound. #300 fixed the case where a fact pattern binds it. Those calls are now kept, and results match the same query without a literal start. +- **Bound-entity queries could drop rows when one `WriteTransaction` wrote the same attribute in several valid-time windows (#323).** Both facts share a `tx_count`, and the selective lookup path de-duplicated on `(entity, attribute, tx_count, asserted)`, so one window's value was silently lost, while the same query via a full scan returned both. That de-duplication has been removed, and bound-entity queries now always match a full scan. + +### Documentation + +- **Unsafe WAL recovery advice removed from `docs/ERROR_REFERENCE.md`.** The WAL-001, WAL-002 and STG-011 resolutions said a `.wal` file could be deleted with no data loss, or that a database could be rebuilt from the WAL alone. Both are wrong: transactions committed since the last checkpoint exist only in the WAL, and the WAL holds nothing older than that checkpoint. The resolutions now say to copy both files first, to checkpoint with the version that wrote the WAL, and what is lost if the WAL is deleted. +- CLAUDE.md now matches the milestones (v2.0.2 final v2.x release, v3.0.0 format v8 and data integrity, v3.1.0 features) and documents `error.rs`, `magic_sets.rs`, `fault_inject.rs` and `src/browser/`. ROADMAP lists #405 and #407 in the v2.0.2 scope. +- README: MSRV (1.89) stated, v2.x known issue (#371) shown near the top, Maven coordinates corrected to `io.github.project-minigraf`, Android listed on Maven Central, and binding download locations point to the binding repos. +- `.github/SECURITY.md` lists 2.x as the supported line. About 50 broken wiki links in `docs/ERROR_REFERENCE.md` now use full wiki URLs. + +### Notes + +- On v2.x, reading a heavily rewritten attribute still costs time proportional to its history, because v7 index keys carry neither the value nor the assert/retract flag; the structural fix needs the v8 keys and is tracked for v3.0.0 in #379. +- Checkpoints on v2.x still copy every index page, so their cost grows with graph size. Copy-on-write index pages on the v3 branch, which also make `save()` crash-atomic, are needed for checkpoints proportional to the change alone (#374). + +## v2.0.1 — 2026-09-25 + +Patch release on the v2.x line. File format is unchanged (v7); no API changes. + +### Fixed + +- **Entity-bound lookups could silently return nothing after an index rebuild on open (#370).** When the index checksum does not match on open (for example after a process was killed during `save()`), Minigraf rebuilds all four indexes from the fact pages. The rebuild computed each fact's location by re-packing all facts contiguously, but a file written by several checkpoints has partially filled pages that a contiguous re-pack does not reproduce. From the second checkpoint onward, rebuilt index entries pointed at the wrong page/slot: entity-bound queries (`[:some/ident ?a ?v]`) returned `[]` or errored while attribute-driven queries still worked, and `checkpoint()` copied the bad entries forward. The rebuild now reads each fact's real on-disk location (#372). + +### Known issues + +- Files whose indexes were already rebuilt with wrong locations by v2.0.0 are not repaired by this release. A public integrity check and rebuild-indexes-from-fact-pages operation is tracked in #373; a crash-atomic `save()` in #374. +- Two values of the same attribute for one entity written in a single `transact` (or retracted in a single `retract`) can read back as one value, differently per query path (#371, #287). The fix changes the index key layout (file format v8) and ships in v3.0.0. Workaround on v2.x: write or retract each value of a multi-valued attribute in its own call. + ## v2.0.0 — 2026-08-26 This was originally slated as v1.3.0, matching the GitHub milestone name under diff --git a/CLAUDE.md b/CLAUDE.md index d54e87d9e1..cd555758a9 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -101,15 +101,17 @@ cargo run < demos/demo_negation.txt 1. **`src/graph/`** — EAV fact store with bi-temporal support - `types.rs`: `Fact`, `Value`, `EntityId`, `TxId`, `VALID_TIME_FOREVER` - - `storage.rs`: `FactStorage` — in-memory store, `transact_batch`, `retract`, `get_facts_as_of`, `get_facts_valid_at`, `net_asserted_facts` + - `storage.rs`: `FactStorage` — in-memory store, `transact_batch`, `retract`, `get_facts_as_of`, `get_facts_valid_at`, `net_asserted_facts`, `get_facts_by_entity_attribute_indexed` 2. **`src/storage/`** — Persistence layer - `mod.rs`: `StorageBackend` trait, `FileHeader` v8 (84 bytes), `CommittedFactReader` / `CommittedIndexReader` traits - `backend/file.rs`: Single `.graph` file backend (4KB pages, cross-platform) - `backend/memory.rs`: In-memory backend for testing + - `backend/fault_inject.rs`: `FaultInjectingBackend` — injects I/O errors for durability tests (test builds only) - `index.rs`: EAVT / AEVT / AVET / VAET key types, `FactRef`, `encode_value` - - `btree_v6.rs`: On-disk B+tree (`build_btree`, `OnDiskIndexReader`, `MutexStorageBackend`) + - `btree_v6.rs`: On-disk B+tree (`build_btree`, `rebuild_btree_incremental`, `OnDiskIndexReader`, `MutexStorageBackend`) - `cache.rs`: LRU page cache (`PageCache`, default 256 pages) + - `dir_sync.rs`: `sync_parent_dir` — fsyncs the parent directory after creating the `.graph`/WAL or deleting the WAL (no-op off Unix) - `packed_pages.rs`: Packed fact pages (~25 facts/4KB page), `MAX_FACT_BYTES` - `persistent_facts.rs`: `PersistentFactStorage` — v8 save/load, auto-migration v7→v8 @@ -123,6 +125,7 @@ cargo run < demos/demo_negation.txt - `types.rs`: `EdnValue`, `Pattern`, `DatalogQuery`, `AsOf`, `ValidAt`, `WhereClause` (incl. `Not`, `NotJoin`); `PseudoAttr` enum, `AttributeSpec` wrapper - `optimizer.rs`: Selectivity-based join reordering; disabled under `wasm` feature - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute` + - `magic_sets.rs`: Magic-sets rewriting for demand-driven recursive rule evaluation (not applied to rules with `not`/`not-join`) 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396) @@ -132,6 +135,10 @@ cargo run < demos/demo_negation.txt 7. **`src/wal.rs`** — Fact-level sidecar WAL, CRC32-protected entries, crash recovery +8. **`src/error.rs`** — Structured error codes: `MinigrafError`, `ErrorCategory`, `ErrorCode` registry (PRS/QRY/STG/WAL/API/INT codes); must match `docs/ERROR_REFERENCE.md` + +9. **`src/browser/`** — Browser WASM backend (`browser` feature): `buffer.rs` (`BrowserBufferBackend`, in-memory pages with dirty tracking), `indexeddb.rs` (IndexedDB persistence) + ### Data Model ```rust @@ -166,18 +173,20 @@ Auto-migrates v7 → v8 on open (index rebuild). v1–v6 are rejected (STG-028). ## Test Coverage -**1157 tests passing** (1149 passing, 8 ignored; unit + integration + doc). +**1206 tests passing** (1198 passing, 8 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. ## Current Maintainer Context -**v2.0.0 released** — it introduced kernel file locking (#317, #304), structured runtime error codes (#277), `OpenOptions` `#[non_exhaustive]`, and an MSRV of Rust 1.89. See `CHANGELOG.md` for the full rationale and release history. +**v2.0.1 released** (2026-09-25) — patch fixing index rebuild on open (#370). **v2.0.0** introduced kernel file locking (#317, #304), structured runtime error codes (#277), `OpenOptions` `#[non_exhaustive]`, and an MSRV of Rust 1.89. See `CHANGELOG.md` for the full rationale and release history. -Relevant areas for the planned query-profiler work (see `ROADMAP.md`): -- `src/query/datalog/` — query executor where profiling hooks will go (#185) -- `docs/BENCHMARKS.md` — post-1.0 performance baseline updates +Current plan (see `ROADMAP.md` and the milestones): +- **v2.0.2** (final planned v2.x release, format v7, no API change) ships from `main`. +- **v3.0.0** (format v8 and data integrity, tracker #383) is developed on the long-lived `v3` branch. Merge `main` into `v3` regularly. +- **v3.1.0** holds new features (query profiler #185, `:limit` #306/#310, lag/lead #182, UniFFI additions). +- Known v2.x data issue: same-transaction multi-valued facts (#371). Fix ships in v3.0.0. ## Testing Conventions diff --git a/Cargo.toml b/Cargo.toml index b9533f3916..480c6b9bf6 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -5,7 +5,7 @@ resolver = "2" [package] name = "minigraf" -version = "2.0.0" +version = "2.0.1" edition = "2024" rust-version = "1.89" description = "Zero-config, single-file, embedded graph database with bi-temporal Datalog queries" diff --git a/README.md b/README.md index 721a0fa11a..e70aa0a919 100644 --- a/README.md +++ b/README.md @@ -6,7 +6,8 @@ [![Clippy Status](https://github.com/project-minigraf/minigraf/actions/workflows/rust-clippy.yml/badge.svg)](https://github.com/project-minigraf/minigraf/actions/workflows/rust-clippy.yml) [![Coverage](https://codecov.io/gh/project-minigraf/minigraf/branch/main/graph/badge.svg)](https://codecov.io/gh/project-minigraf/minigraf) [![License: MIT OR Apache-2.0](https://img.shields.io/badge/license-MIT%20OR%20Apache--2.0-blue.svg)](https://github.com/project-minigraf/minigraf#license) -[![Rust Edition](https://img.shields.io/badge/rust-2024-orange.svg)](https://blog.rust-lang.org/2024/10/17/Rust-1.82.0.html) +[![Rust Edition](https://img.shields.io/badge/rust-2024-orange.svg)](https://doc.rust-lang.org/edition-guide/rust-2024/index.html) +[![MSRV](https://img.shields.io/badge/MSRV-1.89-orange.svg)](Cargo.toml) > **Embedded graph memory for AI agents, mobile apps, and the browser** — the SQLite of bi-temporal graph databases @@ -41,7 +42,7 @@ Minigraf is a **single-file embedded graph database** that lets you: ```toml [dependencies] -minigraf = "2.0.0" +minigraf = "2.0.1" ``` Or via cargo: @@ -50,6 +51,10 @@ Or via cargo: cargo add minigraf ``` +Requires Rust 1.89 or newer (the minimum supported Rust version, set in `Cargo.toml`). + +**Known issue on v2.x:** two values of the same attribute for one entity written in a single `transact` (or retracted in a single `retract`) can read back as one value (#371). Write or retract each value of a multi-valued attribute in its own call. The fix changes the file format and ships in v3.0.0. See the [CHANGELOG](CHANGELOG.md). + ## Quick Start ```rust @@ -92,7 +97,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1157 tests +cargo test # run 1206 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` @@ -114,7 +119,7 @@ No other database offers this combination: | **Embedded** | ✅ Yes | ✅ Yes | ✅ Yes | ❌ No | ✅ Yes | | **Graph Native** | ✅ Yes | ✅ Yes | ✅ Yes | ✅ Yes | ❌ No | | **Rust** | ✅ Yes | ❌ Clojure | ✅ Yes | ❌ Java | ❌ C | -| **WASM Ready** | ✅ Yes (browser + WASI + 6 targets) | ❌ No | ⚠️ Limited | ❌ No | ✅ Yes | +| **WASM Ready** | ✅ Yes (browser + WASI) | ❌ No | ⚠️ Limited | ❌ No | ✅ Yes | ## Platform support @@ -122,13 +127,13 @@ No other database offers this combination: |---|---|---| | Rust (native) | `minigraf` on crates.io | `cargo add minigraf` | | Browser WASM | `@minigraf/browser` on npm | `npm install @minigraf/browser` | -| WASI | `@minigraf/wasi` on npm, `.wasm` on GitHub Releases | `npm install @minigraf/wasi` | +| WASI | `@minigraf/wasi` on npm | `npm install @minigraf/wasi` | | Node.js | `minigraf` on npm | `npm install minigraf` | | Python | `minigraf` on PyPI | `pip install minigraf` | -| Java/JVM | `io.github.adityamukho:minigraf-jvm` on Maven Central | see [wiki](https://github.com/project-minigraf/minigraf/wiki/Use-Cases) | -| Android | `.aar` on GitHub Packages | see [wiki](https://github.com/project-minigraf/minigraf/wiki/Use-Cases) | -| iOS / macOS | `.xcframework` via Swift Package Manager | see [wiki](https://github.com/project-minigraf/minigraf/wiki/Use-Cases) | -| C / FFI | header + tarball on GitHub Releases | see [wiki](https://github.com/project-minigraf/minigraf/wiki/Use-Cases) | +| Java/JVM | `io.github.project-minigraf:minigraf-jvm` on Maven Central | see [wiki](https://github.com/project-minigraf/minigraf/wiki/Use-Cases) | +| Android | `io.github.project-minigraf:minigraf-android` (`.aar`) on Maven Central | see [wiki](https://github.com/project-minigraf/minigraf/wiki/Use-Cases) | +| iOS / macOS | `.xcframework` via Swift Package Manager ([minigraf-swift](https://github.com/project-minigraf/minigraf-swift)) | see [wiki](https://github.com/project-minigraf/minigraf/wiki/Use-Cases) | +| C / FFI | header + tarball on [minigraf-c releases](https://github.com/project-minigraf/minigraf-c/releases) | see [wiki](https://github.com/project-minigraf/minigraf/wiki/Use-Cases) | **Embedded graph memory for agents, mobile, and the browser — SQLite's simplicity + Datomic's temporal model.** @@ -140,8 +145,8 @@ No other database offers this combination: | Node.js | [`minigraf` on npm](https://www.npmjs.com/package/minigraf) | [minigraf-node](https://github.com/project-minigraf/minigraf-node) | | Browser WASM | [`@minigraf/browser` on npm](https://www.npmjs.com/package/@minigraf/browser) | [minigraf-wasm](https://github.com/project-minigraf/minigraf-wasm) | | WASI | [`@minigraf/wasi` on npm](https://www.npmjs.com/package/@minigraf/wasi) | [minigraf-wasm](https://github.com/project-minigraf/minigraf-wasm) | -| Java | `minigraf-jvm` on Maven Central | [minigraf-java](https://github.com/project-minigraf/minigraf-java) | -| Android | Android bindings | [minigraf-android](https://github.com/project-minigraf/minigraf-android) | +| Java | `io.github.project-minigraf:minigraf-jvm` on Maven Central | [minigraf-java](https://github.com/project-minigraf/minigraf-java) | +| Android | `io.github.project-minigraf:minigraf-android` on Maven Central | [minigraf-android](https://github.com/project-minigraf/minigraf-android) | | iOS/macOS | Swift bindings | [minigraf-swift](https://github.com/project-minigraf/minigraf-swift) | | C | C bindings | [minigraf-c](https://github.com/project-minigraf/minigraf-c) | @@ -155,7 +160,7 @@ Pairs well with vector stores (GraphRAG pattern): the vector store answers "what ### For Mobile Apps -Offline-first storage with retroactive corrections — the bi-temporal model lets you correct a mis-entered value while preserving the original record. Native Kotlin and Swift bindings ship as an Android `.aar` (GitHub Packages) and an iOS `.xcframework` (Swift Package Manager) via [UniFFI](https://github.com/mozilla/uniffi-rs). No Rust required. +Offline-first storage with retroactive corrections — the bi-temporal model lets you correct a mis-entered value while preserving the original record. Native Kotlin and Swift bindings ship as an Android `.aar` (Maven Central) and an iOS `.xcframework` (Swift Package Manager) via [UniFFI](https://github.com/mozilla/uniffi-rs). No Rust required. ```kotlin // Android (Kotlin) diff --git a/ROADMAP.md b/ROADMAP.md index 969c4c6b16..24270938e8 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -8,15 +8,64 @@ Completed releases and their implementation details live in the [CHANGELOG](CHAN --- -## v3.0.0 — File Format Policy +## v2.0.2 — Final Planned v2.x Release -**#287/#371 have landed in-tree (unreleased): file format v8, replacing v7.** Fixing #287's `EavtKey`/`AevtKey` missing-value-bytes data-loss bug bumped the format from v7 to v8; index keys now include the encoded value and the assert/retract flag. Support for v1–v6 is dropped at the same time — opening one fails with `STG-028`. A v7 file is auto-migrated (re-indexed) to v8 the first time it is opened. v3.0.0 itself has not been released yet; this work will ship as part of it. Any database opened at least once under a v1.x release will already be on v7; there are no known users on older formats. - -This was the GitHub milestone named “2.0” before v2.0.0 used that version number for the kernel-locking and structured-error-code breaking changes; it was consequently renumbered to v3.0.0. +**The v2.x line (`main`) ends with a patch.** File format stays v7 and the public API does not change. All new feature work has moved to v3.x. Tracker: #383. Scope: -- ✅ `EavtKey`/`AevtKey` value-bytes fix, format v8, v7→v8 migration, v1–v6 dropped (#287, #371) +- Already merged: bound-entity point queries narrowed to the queried attribute (#323 mitigation), exact attribute-scan bounds (#381), and checkpoints that copy untouched index leaves (#315 mitigation) +- fsync the parent directory after creating the `.graph`/WAL file and after deleting the WAL (#389) +- `or-join` returns an empty result, not INT-031, when the clauses before it match no rows (#405) +- A clear user error for `$slot` queries run through `execute()`, not internal INT-025 (#407) +- Benchmark regression alerting that is not silently muted (#393) +- CI: MSRV build, public-API semver check, dependency policy (#395) +- Stability and support policy, including how long v2.x gets data-integrity fixes after v3.0.0 (#397) +- Known-issues process: data-integrity issues stay open until the fix is in a published release (#399) +- Support tiers for language bindings and platforms (#400) + +**Known issue on all v2.x releases:** same-transaction multi-valued facts read back as one value (#371, #287). The fix needs format v8 and ships in v3.0.0. Workaround: write or retract each value of a multi-valued attribute in its own `transact`/`retract` call. + +--- + +## v3.0.0 — File Format v8 and Data Integrity + +**v3.0.0 supports file format v8 only.** Fixing #287/#371 (`EavtKey`/`AevtKey` carry no value bytes, so same-transaction multi-values collapse) bumps the format from v7 to v8. Support for v1–v6 is dropped at the same time. The v1–v6 → v7 auto-migration code in `persistent_facts.rs` can be removed when cutting this release; a v7→v8 migration replaces it. Any database opened at least once under a v1.x release will already be on v7; there are no known users on older formats. Every other layout change this release needs goes into v8 too, so there is no separate v9. + +This was the GitHub milestone named “2.0” before v2.0.0 used that version number for the kernel-locking and structured-error-code breaking changes; it was consequently renumbered to v3.0.0. It is developed on the long-lived `v3` branch and merges into `main` at the cut. + +Scope — format and storage integrity: + +- v8 index keys with value bytes and v7→v8 migration (#371, #287; done on `v3`) +- Per-page CRC32 checksums on fact pages and B+tree pages (#388) +- Crash-atomic `save()`, with checkpoints proportional to the change (#374) +- Index `verify` and public `rebuild_indexes()` (#373) +- Net-assert on v8 keys before resolving facts, for O(live) point queries (#379) +- `btree_page` fuzz target that reaches node decoding (#375) + +Scope — release-gate testing and documentation: + +- Golden-file compatibility corpus for every format version, frozen before v8 work goes further (#391) +- SIGKILL crash test that checks committed data through EAVT, AEVT and full scan (#384) +- Model-based test of transact/retract/checkpoint/reopen (#385) +- Wider property tests: file-backed, batched, retracts, temporal, joins (#386) +- Persistent fuzz corpus and an operation-sequence target (#387) +- Fault injection across save/WAL/recovery (#390) +- Long-running soak test at scale (#392) +- Benchmarks at 100K–10M facts and a published performance envelope (#394) +- Higher storage/WAL coverage gates and branch-coverage gates (#396) +- Durability, recovery and operations guide (#398) + +--- + +## v3.1.0 — Features + +Additive features, kept out of v3.0.0 so the #371 fix is not held up by them: + +- Rule persistence — design first (#241) +- Query profiler (#185) +- Native `:limit N` / `:offset` for plain `:find` queries (#306, #310) +- Set membership predicates (#316) - `lag`/`lead` window functions (#182) - Sliding row frames — `:rows N preceding` (#183; builds on #182) - `PreparedQuery` over UniFFI (#181) @@ -33,7 +82,7 @@ Scope: ### Developer Tools - 🎯 Database inspector/debugger (separate repository: [minigraf-inspector](https://github.com/project-minigraf/minigraf-inspector)) -- 🎯 Query profiler +- 🎯 Query profiler (#185, v3.1.0) - 🎯 Time-travel visualizer (separate repository: [minigraf-visualizer](https://github.com/project-minigraf/minigraf-visualizer)) ### Integration Examples @@ -105,7 +154,9 @@ When evaluating features, ask: ## Current Focus -- The v3.0.0 file-format policy and its scoped work above +- v2.0.2, the final planned v2.x release, on `main` +- v3.0.0 (format v8 and data integrity) on the `v3` branch, then v3.1.0 features +- Production readiness for high-stakes deployments, tracked in #383 - Ecosystem work tracked in [`minigraf-examples`](https://github.com/project-minigraf/minigraf-examples) - Developer tools tracked in `minigraf-inspector` and `minigraf-visualizer` @@ -113,4 +164,4 @@ See [GitHub Issues](https://github.com/project-minigraf/minigraf/issues) for spe --- -**Last updated**: August 2026 — v2.0.0 is the current release; v3.0.0 is the next core milestone described here. +**Last updated**: September 2026 — v2.0.1 is the current release. v2.0.2 is the final planned v2.x release and ships from `main` first; v3.0.0 work, including the file-format v8 fix for #287/#371, is developed on the long-lived `v3` branch and merges into `main` at the v3.0.0 cut. diff --git a/benches/minigraf_bench.rs b/benches/minigraf_bench.rs index e8f27bc8d8..2de35d982a 100644 --- a/benches/minigraf_bench.rs +++ b/benches/minigraf_bench.rs @@ -415,6 +415,40 @@ fn bench_checkpoint(c: &mut Criterion) { group.finish(); } +// ── checkpoint/after_1_fact (#315) ──────────────────────────────────────────── + +/// Checkpoint cost when only one fact is dirty, on an already-checkpointed graph. +/// Before #315 this was flat in dirty bytes and proportional to graph size. +fn bench_checkpoint_after_1_fact(c: &mut Criterion) { + use criterion::BatchSize; + use tempfile::NamedTempFile; + + let mut group = c.benchmark_group("checkpoint/after_1_fact"); + group.sample_size(20); + for &(label, n) in &[("10k", 10_000usize), ("100k", 100_000)] { + let tmp = NamedTempFile::new().unwrap(); + let path = tmp.path().to_str().unwrap().to_string(); + helpers::populate_file_no_checkpoint(n, &path); + let db = helpers::open_file_no_checkpoint(&path); + db.checkpoint().unwrap(); + let mut i = 0u64; + group.bench_function(BenchmarkId::from_parameter(label), |b| { + b.iter_batched( + || { + i += 1; + db.execute(&format!("(transact [[:ck{i} :val {i}]])")) + .unwrap(); + }, + // One dirty fact per checkpoint: batched setups would leave + // every checkpoint after the first with nothing to do. + |()| db.checkpoint().unwrap(), + BatchSize::PerIteration, + ); + }); + } + group.finish(); +} + // ── Task 10: concurrent/ ───────────────────────────────────────────────────── fn bench_concurrent(c: &mut Criterion) { @@ -1582,6 +1616,54 @@ fn bench_btree_lookup(c: &mut Criterion) { } } +// ── point_query_chain_depth (Issue #323) ───────────────────────────────────── +// +// One entity whose :hash is retracted/reasserted `depth` times (exactly one live +// value), plus a never-churned :other on the same entity; checkpointed file DB. + +fn bench_point_query_chain_depth(c: &mut Criterion) { + const DEPTHS: &[usize] = &[1, 500, 2000]; + const QUERIES: &[(&str, &str)] = &[ + ( + "churned_attr", + "(query [:find ?v :where [:e/hot :hash ?v]])", + ), + ( + "sibling_attr", + "(query [:find ?v :where [:e/hot :other ?v]])", + ), + ("attr_scan", "(query [:find ?v :where [?e :hash ?v]])"), + ]; + for &(name, q) in QUERIES { + let mut group = c.benchmark_group(format!("point_query_chain_depth/{name}")); + group.sample_size(20); + for &depth in DEPTHS { + let dir = tempfile::tempdir().unwrap(); + let db = minigraf::Minigraf::open(dir.path().join("b.graph")).unwrap(); + for i in 0..2000 { + db.execute(&format!("(transact [[:f/{i} :x {i}]])")) + .unwrap(); + } + db.execute("(transact [[:e/hot :other \"o\"]])").unwrap(); + db.execute("(transact {:valid-from \"2020-01-01T00:00:00Z\"} [[:e/hot :hash \"h0\"]])") + .unwrap(); + for i in 1..depth { + db.execute(&format!("(retract [[:e/hot :hash \"h{}\"]])", i - 1)) + .unwrap(); + db.execute(&format!( + "(transact {{:valid-from \"2020-01-01T00:00:00Z\"}} [[:e/hot :hash \"h{i}\"]])" + )) + .unwrap(); + } + db.checkpoint().unwrap(); + group.bench_with_input(BenchmarkId::from_parameter(depth), &depth, |b, _| { + b.iter(|| black_box(db.execute(q).unwrap())); + }); + } + group.finish(); + } +} + // ── query/predicate_pushdown ────────────────────────────────────────────────── fn bench_predicate_pushdown(c: &mut Criterion) { @@ -1745,6 +1827,7 @@ criterion_group!( bench_query_extras, bench_open, bench_checkpoint, + bench_checkpoint_after_1_fact, bench_concurrent, bench_concurrent_file, bench_concurrent_btree_scan, @@ -1752,6 +1835,7 @@ criterion_group!( bench_retract, bench_btree_lookup, bench_predicate_pushdown, - bench_simd, // Issue #229 + bench_point_query_chain_depth, // Issue #323 + bench_simd, // Issue #229 ); criterion_main!(benches); diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index af74770b4e..d67494cbab 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -30,6 +30,39 @@ Each value is Criterion's estimated per-query latency; the range is its 95% conf `point_entity` uses a selective index-backed lookup. `point_attribute` and `join_3pattern` return larger result sets and therefore scale with the number of matching facts. Do not compare these local measurements directly with CI runs or earlier releases: host load, CPU-frequency policy, toolchain, and implementation all affect the result. +### Point Query vs. Version-Chain Depth (#323) + +**Date**: 2026-09-26 · **Command**: `cargo bench --bench minigraf_bench -- point_query_chain_depth` · same host as above, on AC power and otherwise idle. + +One entity's `:hash` is retracted and reasserted `depth` times (exactly one live value), plus a never-changed `:other` on the same entity and 2,000 filler facts; checkpointed file database. "Before" is v2.0.1; "after" is the #323 change. + +| Query | Depth | Before | After | +|---|---:|---:|---:| +| `[:e/hot :hash ?v]` (churned attribute) | 1 | 19.5 µs | 18.3 µs | +| | 500 | 1.18 ms | 855 µs | +| | 2000 | 4.64 ms | 3.36 ms | +| `[:e/hot :other ?v]` (sibling attribute) | 1 | 20.0 µs | 19.2 µs | +| | 500 | 1.17 ms | 20.6 µs | +| | 2000 | 4.58 ms | 19.0 µs | +| `[?e :hash ?v]` (attribute scan) | 1 | 17.5 µs | 17.8 µs | +| | 500 | 1.14 ms | 841 µs | +| | 2000 | 4.49 ms | 3.33 ms | + +The churned attribute still scales with its own history on v2.x; see #379 for the v3.0.0 fix. + +### Checkpoint After One Dirty Fact (#315) + +**Date**: 2026-09-26 · **Command**: `cargo bench --bench minigraf_bench -- checkpoint/after_1_fact` · same host as above; file on tmpfs, so fsync cost is excluded. + +An already-checkpointed file database of `n` facts receives one new fact, then `checkpoint()` runs; every iteration has exactly one dirty fact. "Before" is v2.0.1, which decoded and re-encoded every index entry. "After" copies index leaves that receive no new entries. + +| Facts | Before | After | +|---:|---:|---:| +| 10k | 23.9 ms | 4.01 ms | +| 100k | 246 ms | 26.3 ms | + +Cost still grows with graph size, because index pages are copied on every checkpoint. Checkpoints proportional to the change alone need copy-on-write pages, tracked with #374 for v3.0.0. + ## Measurement Method Criterion warms up each benchmark, collects ten samples for this query group, and estimates per-call latency from repeated iterations. The reported confidence intervals describe measurement uncertainty on this host; they are not cross-machine performance guarantees. diff --git a/docs/ERROR_REFERENCE.md b/docs/ERROR_REFERENCE.md index e14e299159..fb99aef85e 100644 --- a/docs/ERROR_REFERENCE.md +++ b/docs/ERROR_REFERENCE.md @@ -218,7 +218,7 @@ Deprecated codes: STG-003 and STG-004 (pre-v7 header sizes) are deprecated as of Parser errors occur when Minigraf cannot parse the Datalog/EDN input string. They are returned immediately from `db.execute()` before any fact is read or written. -See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidance. +See the [Datalog Reference](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference) for syntax guidance. ### PRS-001 Unexpected end of input @@ -262,7 +262,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Check surrounding delimiters for balance. -- Consult the [Datalog Reference](../../.wiki/Datalog-Reference.md) for expected syntax at that position. +- Consult the [Datalog Reference](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference) for expected syntax at that position. **Example**: ```datalog @@ -434,7 +434,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Add a value: `:as-of 5` (transaction count) or `:as-of "2024-01-01T00:00:00Z"` (ISO 8601 wall-clock time). -- See the [Datalog Reference — Time Travel](../../.wiki/Datalog-Reference.md#time-travel). +- See the [Datalog Reference — Time Travel](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#bi-temporal-queries). **Example**: ```datalog @@ -451,7 +451,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use a non-negative integer. - `:as-of 0` returns the database before any transaction; `:as-of 1` returns the state after the first transaction. -- See the [Datalog Reference — Time Travel](../../.wiki/Datalog-Reference.md#time-travel). +- See the [Datalog Reference — Time Travel](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#bi-temporal-queries). **Example**: ```datalog @@ -467,7 +467,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use `42` (tx-count) or `"2024-01-01T00:00:00Z"` (wall-clock). -- See the [Datalog Reference — Time Travel](../../.wiki/Datalog-Reference.md#time-travel). +- See the [Datalog Reference — Time Travel](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#bi-temporal-queries). **Example**: ```datalog @@ -483,7 +483,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Add an ISO 8601 timestamp: `:valid-at "2024-06-01T00:00:00Z"`. -- See the [Datalog Reference — Time Travel](../../.wiki/Datalog-Reference.md#time-travel). +- See the [Datalog Reference — Time Travel](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#bi-temporal-queries). **Example**: ```datalog @@ -499,7 +499,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use `"2024-06-01T00:00:00Z"` or `:any-valid-time`. -- See the [Datalog Reference — Time Travel](../../.wiki/Datalog-Reference.md#time-travel). +- See the [Datalog Reference — Time Travel](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#bi-temporal-queries). **Example**: ```datalog @@ -515,7 +515,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use `"2024-01-01T00:00:00Z"` format. -- See the [Datalog Reference — Time Travel](../../.wiki/Datalog-Reference.md#time-travel). +- See the [Datalog Reference — Time Travel](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#bi-temporal-queries). **Example**: ```datalog @@ -532,7 +532,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use `"2024-12-31T23:59:59Z"` format. - To express "forever", omit `:valid-to` (the default is `VALID_TIME_FOREVER`). -- See the [Datalog Reference — Time Travel](../../.wiki/Datalog-Reference.md#time-travel). +- See the [Datalog Reference — Time Travel](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#bi-temporal-queries). **Example**: ```datalog @@ -548,7 +548,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Add an aggregate to `:find`, or remove `:with` if no aggregation is needed. -- See the [Datalog Reference — Aggregates](../../.wiki/Datalog-Reference.md#aggregates). +- See the [Datalog Reference — Aggregates](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#aggregation). **Example**: ```datalog @@ -566,7 +566,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Add a `:where` clause that binds the variable, or remove it from `:with`. -- See the [Datalog Reference — Aggregates](../../.wiki/Datalog-Reference.md#aggregates). +- See the [Datalog Reference — Aggregates](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#aggregation). **Example**: ```datalog @@ -584,7 +584,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Add a `:where` clause that binds the variable. -- See the [Datalog Reference — Aggregates](../../.wiki/Datalog-Reference.md#aggregates). +- See the [Datalog Reference — Aggregates](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#aggregation). **Example**: ```datalog @@ -601,7 +601,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use `(count ?e)`, `(sum ?amount)`, `(avg ?score)` — one function name, one variable. -- See the [Datalog Reference — Aggregates](../../.wiki/Datalog-Reference.md#aggregates). +- See the [Datalog Reference — Aggregates](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#aggregation). **Example**: ```datalog @@ -618,7 +618,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use `sum`, not `:sum`. -- See the [Datalog Reference — Aggregates](../../.wiki/Datalog-Reference.md#aggregates). +- See the [Datalog Reference — Aggregates](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#aggregation). **Example**: ```datalog @@ -635,7 +635,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use a `?variable`, not a literal value. -- See the [Datalog Reference — Aggregates](../../.wiki/Datalog-Reference.md#aggregates). +- See the [Datalog Reference — Aggregates](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#aggregation). **Example**: ```datalog @@ -652,7 +652,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Add an `:over` clause: `(rank :over (:order-by ?score))`. -- See the [Datalog Reference — Window Functions](../../.wiki/Datalog-Reference.md#window-functions). +- See the [Datalog Reference — Window Functions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#window-functions). **Example**: ```datalog @@ -669,7 +669,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Provide at least `:order-by` or `:partition-by` inside the `:over` list. -- See the [Datalog Reference — Window Functions](../../.wiki/Datalog-Reference.md#window-functions). +- See the [Datalog Reference — Window Functions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#window-functions). **Example**: ```datalog @@ -686,7 +686,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use `rank`, not `:rank`. -- See the [Datalog Reference — Window Functions](../../.wiki/Datalog-Reference.md#window-functions). +- See the [Datalog Reference — Window Functions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#window-functions). **Example**: ```datalog @@ -720,7 +720,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Drop the `:over` clause and use the function as a plain aggregate. -- See the [Datalog Reference — Aggregates](../../.wiki/Datalog-Reference.md#aggregates). +- See the [Datalog Reference — Aggregates](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#aggregation). **Example**: ```datalog @@ -737,7 +737,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Add the variable argument before `:over`. -- See the [Datalog Reference — Window Functions](../../.wiki/Datalog-Reference.md#window-functions). +- See the [Datalog Reference — Window Functions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#window-functions). **Example**: ```datalog @@ -754,7 +754,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Add `:over` after the variable. -- See the [Datalog Reference — Window Functions](../../.wiki/Datalog-Reference.md#window-functions). +- See the [Datalog Reference — Window Functions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#window-functions). **Example**: ```datalog @@ -771,7 +771,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Remove the variable: `(rank :over (:order-by ?score))`. -- See the [Datalog Reference — Window Functions](../../.wiki/Datalog-Reference.md#window-functions). +- See the [Datalog Reference — Window Functions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#window-functions). **Example**: ```datalog @@ -788,7 +788,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Always follow `:over` with a list: `(rank :over (:order-by ?score))`. -- See the [Datalog Reference — Window Functions](../../.wiki/Datalog-Reference.md#window-functions). +- See the [Datalog Reference — Window Functions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#window-functions). **Example**: ```datalog @@ -805,7 +805,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - The window expression must end after the `:over` clause. Remove trailing tokens. -- See the [Datalog Reference — Window Functions](../../.wiki/Datalog-Reference.md#window-functions). +- See the [Datalog Reference — Window Functions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#window-functions). **Example**: ```datalog @@ -822,7 +822,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use a `?variable`: `(rank :over (:partition-by ?dept :order-by ?score))`. -- See the [Datalog Reference — Window Functions](../../.wiki/Datalog-Reference.md#window-functions). +- See the [Datalog Reference — Window Functions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#window-functions). **Example**: ```datalog @@ -839,7 +839,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use a `?variable`: `(rank :over (:order-by ?score))`. -- See the [Datalog Reference — Window Functions](../../.wiki/Datalog-Reference.md#window-functions). +- See the [Datalog Reference — Window Functions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#window-functions). **Example**: ```datalog @@ -856,7 +856,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use only `:order-by` and `:partition-by`. -- See the [Datalog Reference — Window Functions](../../.wiki/Datalog-Reference.md#window-functions). +- See the [Datalog Reference — Window Functions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#window-functions). **Example**: ```datalog @@ -873,7 +873,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - The `:over` list must contain only `:order-by` / `:partition-by` followed by variables. -- See the [Datalog Reference — Window Functions](../../.wiki/Datalog-Reference.md#window-functions). +- See the [Datalog Reference — Window Functions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#window-functions). **Example**: ```datalog @@ -1027,7 +1027,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Remove the empty list or replace it with a valid clause. -- See the [Datalog Reference](../../.wiki/Datalog-Reference.md). +- See the [Datalog Reference](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference). **Example**: ```datalog @@ -1045,7 +1045,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Double negation is logically equivalent to the positive pattern; use the pattern directly. - For complex negation use `not-join` with explicit join variables. -- See the [Datalog Reference — Negation](../../.wiki/Datalog-Reference.md#negation). +- See the [Datalog Reference — Negation](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#negation). **Example**: ```datalog @@ -1062,7 +1062,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Add at least one pattern inside `(not ...)`. -- See the [Datalog Reference — Negation](../../.wiki/Datalog-Reference.md#negation). +- See the [Datalog Reference — Negation](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#negation). **Example**: ```datalog @@ -1079,7 +1079,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Add at least one branch. -- See the [Datalog Reference](../../.wiki/Datalog-Reference.md#disjunction). +- See the [Datalog Reference](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#disjunction). **Example**: ```datalog @@ -1096,7 +1096,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use the form `(or-join [?e] [[?e :a 1]] [[?e :b 2]])`. -- See the [Datalog Reference](../../.wiki/Datalog-Reference.md#disjunction). +- See the [Datalog Reference](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#disjunction). **Example**: ```datalog @@ -1113,7 +1113,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - The form is `(or-join [?var1 ?var2] ...)`. -- See the [Datalog Reference](../../.wiki/Datalog-Reference.md#disjunction). +- See the [Datalog Reference](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#disjunction). **Example**: ```datalog @@ -1130,7 +1130,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use `?variable` not `:keyword` or a string. -- See the [Datalog Reference](../../.wiki/Datalog-Reference.md#disjunction). +- See the [Datalog Reference](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#disjunction). **Example**: ```datalog @@ -1148,7 +1148,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Restructure branches so they all bind the same new variables. - Or use `or-join` to specify exactly which variables to share. -- See the [Datalog Reference](../../.wiki/Datalog-Reference.md#disjunction). +- See the [Datalog Reference](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#disjunction). **Example**: ```datalog @@ -1166,7 +1166,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Add at least one clause inside `(and ...)`. -- See the [Datalog Reference](../../.wiki/Datalog-Reference.md#disjunction). +- See the [Datalog Reference](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#disjunction). **Example**: ```datalog @@ -1183,7 +1183,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use `(not-join [?e] [?e :deleted true])`. -- See the [Datalog Reference — Negation](../../.wiki/Datalog-Reference.md#negation). +- See the [Datalog Reference — Negation](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#negation). **Example**: ```datalog @@ -1200,7 +1200,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Each `:where` element must be a vector `[e a v]`, a `(not ...)`, `(not-join ...)`, `(or ...)`, `(or-join ...)`, or expression `[(expr) ?out]`. -- See the [Datalog Reference](../../.wiki/Datalog-Reference.md). +- See the [Datalog Reference](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference). **Example**: ```datalog @@ -1218,7 +1218,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Valid query map keys are `:find`, `:where`, `:with`, `:as-of`, `:valid-at`. - Check spelling. -- See the [Datalog Reference](../../.wiki/Datalog-Reference.md). +- See the [Datalog Reference](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference). **Example**: ```datalog @@ -1234,7 +1234,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Provide a function: `[(+ ?a ?b) ?sum]`. -- See the [Datalog Reference — Expressions](../../.wiki/Datalog-Reference.md#expressions). +- See the [Datalog Reference — Expressions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#arithmetic--predicate-expressions). **Example**: ```datalog @@ -1251,7 +1251,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use `+` not `:+`. -- See the [Datalog Reference — Expressions](../../.wiki/Datalog-Reference.md#expressions). +- See the [Datalog Reference — Expressions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#arithmetic--predicate-expressions). **Example**: ```datalog @@ -1269,7 +1269,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Check the argument count. - Single-argument operators: `abs`, `not`, `str` (for coercion). -- See the [Datalog Reference — Expressions](../../.wiki/Datalog-Reference.md#expressions). +- See the [Datalog Reference — Expressions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#arithmetic--predicate-expressions). **Example**: ```datalog @@ -1287,7 +1287,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Check the argument count. - Two-argument operators: `+`, `-`, `*`, `/`, `mod`, `quot`, `=`, `!=`, `<`, `<=`, `>`, `>=`, `starts-with?`, `ends-with?`, `contains?`, `matches?`. -- See the [Datalog Reference — Expressions](../../.wiki/Datalog-Reference.md#expressions). +- See the [Datalog Reference — Expressions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#arithmetic--predicate-expressions). **Example**: ```datalog @@ -1304,7 +1304,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Pass the pattern as a string literal: `[(matches? ?name "alice.*")]`. -- See the [Datalog Reference — Expressions](../../.wiki/Datalog-Reference.md#expressions). +- See the [Datalog Reference — Expressions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#arithmetic--predicate-expressions). **Example**: ```datalog @@ -1322,7 +1322,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Check spelling against the supported operator list above. - For missing operators, register a custom predicate via `db.register_predicate()`. -- See the [Datalog Reference — Expressions](../../.wiki/Datalog-Reference.md#expressions). +- See the [Datalog Reference — Expressions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#arithmetic--predicate-expressions). **Example**: ```datalog @@ -1339,7 +1339,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Ensure the expression is wrapped in exactly one outer `[...]`. -- See the [Datalog Reference — Expressions](../../.wiki/Datalog-Reference.md#expressions). +- See the [Datalog Reference — Expressions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#arithmetic--predicate-expressions). **Example**: ```datalog @@ -1356,7 +1356,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Use a `?variable`: `[(+ ?a ?b) ?sum]`. -- See the [Datalog Reference — Expressions](../../.wiki/Datalog-Reference.md#expressions). +- See the [Datalog Reference — Expressions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#arithmetic--predicate-expressions). **Example**: ```datalog @@ -1374,7 +1374,7 @@ See the [Datalog Reference](../../.wiki/Datalog-Reference.md) for syntax guidanc **Resolution**: - Expressions accept variables (`?x`), integers, floats, strings, booleans, and keywords. - Restructure to avoid passing complex types. -- See the [Datalog Reference — Expressions](../../.wiki/Datalog-Reference.md#expressions). +- See the [Datalog Reference — Expressions](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#arithmetic--predicate-expressions). **Example**: ```datalog @@ -1796,7 +1796,9 @@ See the [file format section in README](../README.md#file-format) for version hi **Cause**: An internal B+tree page was found with an empty children list, which violates B+tree invariants. This indicates index corruption. **Resolution**: -- Restore from backup. If the corruption occurred after a recent write, the WAL file may contain a recoverable state — delete the `.graph` file and try opening from the WAL only (by restoring the last good checkpoint and replaying the WAL). See the [file format section in README](../README.md#file-format). +- Stop writing to the database and copy both the `.graph` file and its `.wal` sidecar before trying anything else. +- Restore from backup. Do not delete the `.graph` file: the WAL holds only the transactions written since the last checkpoint, so it cannot rebuild the database on its own. If you restore an older `.graph` file, you can keep the matching `.wal` only if it was written after that file's last checkpoint. +- Index integrity checking and rebuilding from fact pages are tracked in #373. **Scenario**: A crash mid-checkpoint left an internal B+tree page in an inconsistent state. @@ -2014,7 +2016,8 @@ The WAL is replayed on open and deleted on checkpoint. **Cause**: The sidecar `.wal` file does not start with the expected WAL magic bytes. The file may have been replaced, corrupted, or created by an incompatible tool. **Resolution**: -- If the WAL file is stale or corrupt, delete `.wal` and reopen the database — Minigraf will replay only from the committed state in the `.graph` file. +- Copy both the `.graph` file and the `.wal` file before changing anything. +- Deleting `.wal` makes the database open, but **every transaction committed since the last checkpoint is lost**, because those transactions exist only in the WAL. Do this only if you have a backup or accept that loss. - Do not manually create or edit `.wal` files. **Scenario**: `my-db.wal` was accidentally replaced with an empty file before `Minigraf::open("my-db.graph")` was called. @@ -2026,8 +2029,8 @@ The WAL is replayed on open and deleted on checkpoint. **Cause**: The `.wal` file was written by a version of Minigraf with a different WAL format. This can occur when downgrading the library after a WAL was written by a newer version. **Resolution**: -- Delete the `.wal` file if it is from an incomplete or stale session (no data is lost — committed facts are in the `.graph` file). -- If the WAL contains uncommitted in-flight data you need to recover, upgrade the library to the version that wrote the WAL before reopening. +- Open the database with the Minigraf version that wrote the WAL and call `checkpoint()`. This moves the WAL's transactions into the `.graph` file and removes the WAL. Then open it with the new version. +- Deleting the `.wal` file instead loses **every transaction committed since the last checkpoint**, because those transactions exist only in the WAL. Do this only if you have a backup or accept that loss. **Scenario**: A `.wal` file written by a pre-release version of Minigraf is opened with the stable release, which uses a different WAL version number — e.g. `Unsupported WAL version: 3 (expected 2)`. @@ -2041,7 +2044,7 @@ The WAL is replayed on open and deleted on checkpoint. - Store large payloads in an external file or object store. - Store the file path or URL as a `Value::String` attribute on the entity. - Or create a dedicated entity for the content and reference it with `Value::Ref`. -- See [BENCHMARKS.md](../BENCHMARKS.md) for size guidance. +- See the [Datalog Reference — Constraints and Limits](https://github.com/project-minigraf/minigraf/wiki/Datalog-Reference#constraints-and-limits) for the size limit. **Example**: ```datalog diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index eecbbd86d3..3e03a5ca12 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -2,15 +2,11 @@ ## Coverage Summary -**Verified**: 2026-09-25 with `cargo test --quiet` +**Verified**: 2026-09-26 with `cargo test --quiet` -**Result**: 1,149 passing tests and 8 ignored tests (1,157 total) +**Result**: 1,198 passing tests and 8 ignored tests (1,206 total) -This supersedes the v2.0.0-era count (1,145 passing, 8 ignored) with the unreleased -file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 -migration, and the drop of formats v1–v6. It otherwise still covers the public -database API, the Datalog engine, storage and recovery paths, and v2.0.0's locking -and structured-error-code changes. +This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a cyclic leaf chain or damaged slot directory is rejected rather than copied (#315). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). ### Covered Areas diff --git a/docs/superpowers/plans/2026-09-25-point-query-history-scan.md b/docs/superpowers/plans/2026-09-25-point-query-history-scan.md new file mode 100644 index 0000000000..cc44585e10 --- /dev/null +++ b/docs/superpowers/plans/2026-09-25-point-query-history-scan.md @@ -0,0 +1,1096 @@ +# Point-Query History Scan Mitigation (#323) Implementation Plan + +> **For agentic workers:** REQUIRED SUB-SKILL: Use superpowers:subagent-driven-development (recommended) or superpowers:executing-plans to implement this plan task-by-task. Steps use checkbox (`- [ ]`) syntax for tracking. + +**Goal:** Stop bound-entity point queries from paying for other attributes' history, and cut the per-history-record constant on the churned attribute itself by ≥3×, without changing file format, API, or results. + +**Architecture:** (1) an in-crate FxHash hasher; (2) `net_asserted_facts` rewritten to encode each value once, borrow keys, and use FxHash; (3) a new EAVT `(entity, attribute)` range lookup in `FactStorage`; (4) `selective_fact_fetch` narrows bound-entity lookups to the attributes the query references and drops its redundant dedup set. + +**Tech Stack:** Rust 2024 edition, MSRV 1.89, criterion benches, cargo test. + +**Spec:** `docs/superpowers/specs/2026-09-25-point-query-history-scan-design.md` + +## Global Constraints + +- No file-format change (stays v7), no public API change, no new dependencies (runtime or dev). +- Clippy workspace lints deny `unwrap_used`, `expect_used`, `panic`, `indexing_slicing`, `cast_possible_truncation`, `cast_possible_wrap`, `cast_sign_loss` in non-test code. Tests are exempt (`src/lib.rs` `cfg_attr(test, allow(...))`; integration tests are separate crates, where these lints still apply only as configured — existing tests use `.unwrap()` freely). +- Never use `{:?}` of `Result`/`Fact`/`Value`/`EdnValue`/UUID-bearing types in `assert!`/`assert_eq!` message strings (CodeQL `rust/cleartext-logging`). `{:?}` elsewhere (e.g. as a sort key) is fine. +- `#![forbid(unsafe_code)]` — no `unsafe`. +- Query results must be identical to before for every query. +- Work in `.worktrees/perf-323-point-query` on branch `perf/323-point-query-history-scan`. `cargo test --release` is broken by design (panic=abort); use `cargo test` and `cargo bench`. +- Commit messages end with: + ``` + Co-Authored-By: Claude Opus 5.5 + Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy + ``` + Commits must reference `#323` but never use a closing keyword for it until the final PR body. + +## Review Focus + +1. **Attribute prefix collision** (`:a` vs `:ab`, `:hash` vs `:hash2`) on a bound entity — only the exact attribute's facts may be returned, in pending *and* committed indexes. → Task 3 test `entity_attribute_indexed_excludes_prefix_sibling`, Task 4 test `prefix_sibling_attribute_not_leaked`. +2. **Bound entity whose query also uses a variable or pseudo-attribute** (`[:e ?a ?v]`, `[:e :db/valid-from ?vf]`) — must still see all of the entity's facts. → Task 4 tests `bound_entity_variable_attribute_sees_all`, `bound_entity_pseudo_attribute_matches_full_scan`. +3. **Many attributes on one bound entity (> threshold)** — must not regress to a full scan, and results must be correct. → Task 4 test `five_attributes_on_one_entity`. +4. **Facts visible in both pending and committed indexes / duplicated input records** — `net_asserted_facts` must be idempotent under duplicates since the executor dedup is removed. → Task 2 test `net_asserted_idempotent_under_duplicates`. +5. **Same-transaction assert + retract, and retraction followed by reassertion of the same value** across a checkpoint boundary. → Task 2 randomized equivalence test; Task 4 test `churned_attribute_live_value_file_backed`. + +--- + +## File Structure + +| File | Change | Responsibility | +|---|---|---| +| `src/graph/fxhash.rs` | Create | `FxHasher`, `FxBuildHasher` — fast non-cryptographic hasher | +| `src/graph/mod.rs` | Modify | register `pub(crate) mod fxhash;` | +| `src/graph/storage.rs` | Modify | rewrite `net_asserted_facts`; add `get_facts_by_entity_attribute_indexed`; tests | +| `src/query/datalog/executor.rs` | Modify | `selective_fact_fetch` narrowing + dedup removal | +| `tests/point_query_history_test.rs` | Create | end-to-end result-equivalence tests | +| `benches/minigraf_bench.rs` | Modify | `point_query_chain_depth` group | +| `docs/BENCHMARKS.md`, `CHANGELOG.md`, `docs/TEST_COVERAGE.md`, `CLAUDE.md` | Modify | doc sync | + +--- + +### Task 1: FxHash hasher + +**Files:** +- Create: `src/graph/fxhash.rs` +- Modify: `src/graph/mod.rs` + +**Interfaces:** +- Produces: `crate::graph::fxhash::FxBuildHasher` (type alias `BuildHasherDefault`), used as `HashMap` / `HashSet` created with `::default()`. + +- [ ] **Step 1: Write the module with its failing-by-absence tests** + +`src/graph/mod.rs` becomes: +```rust +pub(crate) mod fxhash; +pub(crate) mod storage; +pub(crate) mod types; +``` + +`src/graph/fxhash.rs`: +```rust +//! Small non-cryptographic hasher for internal hot-path hash maps (#323). +//! +//! Same multiply-rotate scheme as rustc's `FxHasher`. Not HashDoS-resistant; +//! only use it for maps keyed by data the embedding application already +//! controls (facts in its own database), never for untrusted network input. + +use std::hash::{BuildHasherDefault, Hasher}; + +const SEED: u64 = 0x51_7c_c1_b7_27_22_0a_95; + +/// Word-at-a-time multiply-rotate hasher. +#[derive(Default, Clone, Copy)] +pub(crate) struct FxHasher { + hash: u64, +} + +impl FxHasher { + #[inline] + fn add_to_hash(&mut self, word: u64) { + self.hash = (self.hash.rotate_left(5) ^ word).wrapping_mul(SEED); + } +} + +impl Hasher for FxHasher { + #[inline] + fn write(&mut self, bytes: &[u8]) { + let mut chunks = bytes.chunks_exact(8); + for chunk in &mut chunks { + let mut buf = [0u8; 8]; + buf.copy_from_slice(chunk); + self.add_to_hash(u64::from_le_bytes(buf)); + } + let rem = chunks.remainder(); + if !rem.is_empty() { + let mut buf = [0u8; 8]; + for (dst, src) in buf.iter_mut().zip(rem) { + *dst = *src; + } + self.add_to_hash(u64::from_le_bytes(buf)); + } + } + + #[inline] + fn write_u8(&mut self, i: u8) { + self.add_to_hash(u64::from(i)); + } + + #[inline] + fn write_u16(&mut self, i: u16) { + self.add_to_hash(u64::from(i)); + } + + #[inline] + fn write_u32(&mut self, i: u32) { + self.add_to_hash(u64::from(i)); + } + + #[inline] + fn write_u64(&mut self, i: u64) { + self.add_to_hash(i); + } + + #[inline] + fn finish(&self) -> u64 { + self.hash + } +} + +/// `BuildHasher` for [`FxHasher`]; use with `HashMap::default()`. +pub(crate) type FxBuildHasher = BuildHasherDefault; + +#[cfg(test)] +mod tests { + use super::*; + use std::collections::{HashMap, HashSet}; + use std::hash::BuildHasher; + + #[test] + fn equal_inputs_hash_equal() { + let b = FxBuildHasher::default(); + assert_eq!(b.hash_one(("abc", 1u64)), b.hash_one(("abc", 1u64))); + } + + #[test] + fn remainder_bytes_affect_hash() { + let b = FxBuildHasher::default(); + // 9 bytes: one full word + 1 remainder byte that differs. + assert_ne!(b.hash_one(b"abcdefghX"), b.hash_one(b"abcdefghY")); + assert_ne!(b.hash_one(":a"), b.hash_one(":ab")); + } + + #[test] + fn usable_as_map_and_set_hasher() { + let mut m: HashMap<(&str, u64), u64, FxBuildHasher> = HashMap::default(); + m.insert((":x", 1), 10); + m.insert((":x", 2), 20); + assert_eq!(m.get(&(":x", 2)).copied(), Some(20)); + let s: HashSet = (0..1000).collect(); + assert_eq!(s.len(), 1000); + } +} +``` + +- [ ] **Step 2: Run tests** + +Run: `cargo test --lib graph::fxhash` +Expected: 3 passed. (Until Task 2 uses it, non-test builds warn `dead_code` for `FxBuildHasher`; that is resolved in Task 2 — do not add `#[allow(dead_code)]`.) + +- [ ] **Step 3: Commit** +```bash +git add src/graph/fxhash.rs src/graph/mod.rs +git commit -m "perf: add in-crate FxHash hasher for hot-path maps (#323)" +``` + +--- + +### Task 2: Faster `net_asserted_facts` + +**Files:** +- Modify: `src/graph/storage.rs` (function at ~line 528; tests module at ~line 827) + +**Interfaces:** +- Consumes: `crate::graph::fxhash::FxBuildHasher` (Task 1). +- Produces: `pub(crate) fn net_asserted_facts(facts: Vec) -> Vec` — same signature and semantics; output now preserves input order of surviving facts. Idempotent under duplicated input records (Task 4 relies on this). + +- [ ] **Step 1: Move the current implementation into the test module as the reference oracle** + +Cut the current body of `net_asserted_facts` and paste it into `mod tests` as: +```rust + /// Pre-#323 implementation, kept verbatim as the oracle for the + /// randomized equivalence test. + fn net_asserted_facts_reference(facts: Vec) -> Vec { + use std::collections::HashMap; + + type EavKey = (EntityId, Attribute, Vec); + type WindowKey = (EntityId, Attribute, Vec, i64, i64); + + let mut max_retract_tx: HashMap = HashMap::new(); + let mut by_window: HashMap = HashMap::new(); + + for fact in facts { + let eav_key = ( + fact.entity, + fact.attribute.clone(), + encode_value(&fact.value), + ); + + if fact.asserted { + let window_key = ( + eav_key.0, + eav_key.1, + eav_key.2, + fact.valid_from, + fact.valid_to, + ); + match by_window.get(&window_key) { + None => { + by_window.insert(window_key, fact); + } + Some(existing) if fact.tx_count > existing.tx_count => { + by_window.insert(window_key, fact); + } + _ => {} + } + } else { + let tx_count = fact.tx_count; + max_retract_tx + .entry(eav_key) + .and_modify(|max_tx| *max_tx = (*max_tx).max(tx_count)) + .or_insert(tx_count); + } + } + + by_window + .into_iter() + .filter_map(|((entity, attribute, value, _, _), fact)| { + let retract_tx = max_retract_tx + .get(&(entity, attribute, value)) + .copied() + .unwrap_or(0); + (fact.tx_count > retract_tx).then_some(fact) + }) + .collect() + } +``` +(Copy it from the file rather than from here if they differ — the file is the source of truth.) + +- [ ] **Step 2: Add the new tests to `mod tests`** + +```rust + /// Order-independent comparison key for a fact set. + fn sorted_keys(facts: &[Fact]) -> Vec { + let mut v: Vec = facts + .iter() + .map(|f| { + format!( + "{}|{}|{:?}|{}|{}|{}|{}", + f.entity, f.attribute, f.value, f.tx_count, f.valid_from, f.valid_to, f.asserted + ) + }) + .collect(); + v.sort(); + v + } + + /// Deterministic xorshift so the test needs no RNG dependency. + struct XorShift(u64); + impl XorShift { + fn next(&mut self) -> u64 { + let mut x = self.0; + x ^= x << 13; + x ^= x >> 7; + x ^= x << 17; + self.0 = x; + x + } + fn below(&mut self, n: u64) -> u64 { + self.next() % n + } + } + + #[test] + fn net_asserted_matches_reference_on_random_histories() { + let entities = [uuid::Uuid::from_u128(1), uuid::Uuid::from_u128(2)]; + let attrs = [":a", ":ab", ":b"]; + let windows = [ + (0_i64, VALID_TIME_FOREVER), + (1_000, 2_000), + (1_500, VALID_TIME_FOREVER), + ]; + let mut rng = XorShift(0x9E37_79B9_7F4A_7C15); + for _case in 0..500 { + let n = rng.below(40) + 1; + let mut facts = Vec::new(); + let mut tx = 0_u64; + for _ in 0..n { + // ~25% of records share the previous tx_count (same-transaction batches). + if rng.below(4) != 0 { + tx += 1; + } + let e = entities[rng.below(2) as usize]; + let a = attrs[rng.below(3) as usize]; + let v = Value::Integer(i64::try_from(rng.below(3)).unwrap()); + if rng.below(3) == 0 { + facts.push(make_retract(e, a, v, tx)); + } else { + let (vf, vt) = windows[rng.below(3) as usize]; + facts.push(make_assert(e, a, v, tx, vf, vt)); + } + } + let expected = sorted_keys(&net_asserted_facts_reference(facts.clone())); + let actual = sorted_keys(&net_asserted_facts(facts)); + assert_eq!(actual, expected, "new net_asserted_facts diverged from reference"); + } + } + + /// The executor's selective fetch no longer dedups (#323); it relies on + /// net_asserted_facts collapsing duplicated input records. + #[test] + fn net_asserted_idempotent_under_duplicates() { + let e = uuid::Uuid::from_u128(7); + let facts = vec![ + make_assert(e, ":hash", Value::String("h0".into()), 1, 0, VALID_TIME_FOREVER), + make_retract(e, ":hash", Value::String("h0".into()), 2), + make_assert(e, ":hash", Value::String("h1".into()), 3, 0, VALID_TIME_FOREVER), + make_assert(e, ":other", Value::String("o".into()), 3, 0, VALID_TIME_FOREVER), + ]; + let mut doubled = facts.clone(); + doubled.extend(facts.clone()); + let once = sorted_keys(&net_asserted_facts(facts)); + let twice = sorted_keys(&net_asserted_facts(doubled)); + assert_eq!(once.len(), 2, "h1 and o are live"); + assert_eq!(twice, once, "duplicated records must not change the result"); + } + + #[test] + fn net_asserted_preserves_input_order() { + let e = uuid::Uuid::from_u128(9); + let facts = vec![ + make_assert(e, ":z", Value::Integer(1), 1, 0, VALID_TIME_FOREVER), + make_assert(e, ":a", Value::Integer(2), 2, 0, VALID_TIME_FOREVER), + make_assert(e, ":m", Value::Integer(3), 3, 0, VALID_TIME_FOREVER), + ]; + let out = net_asserted_facts(facts); + let attrs: Vec<&str> = out.iter().map(|f| f.attribute.as_str()).collect(); + assert_eq!(attrs, vec![":z", ":a", ":m"]); + } +``` + +- [ ] **Step 3: Run the new tests against the unchanged production function** + +At this point the production `net_asserted_facts` still has the old body (Step 1 *copied* it into the test module; do not delete it from production yet). +Run: `cargo test --lib graph::storage::tests::net_asserted` +Expected: `net_asserted_preserves_input_order` FAILS (old code returns HashMap order); `net_asserted_matches_reference_on_random_histories` and `net_asserted_idempotent_under_duplicates` PASS. + +- [ ] **Step 4: Replace the production body** + +Replace the whole `pub(crate) fn net_asserted_facts` body (keep the existing doc comment, but replace its `# Implementation note` section with the text below): +```rust +/// # Implementation note +/// +/// Hot path for every non-`:as-of` query (#323). Each value is encoded once; +/// the two group maps borrow `(entity, attribute, value_bytes)` from the input +/// instead of cloning them, and use [`FxBuildHasher`]. `by_window` stores the +/// index and `tx_count` of the winning assertion per validity window; survivors +/// are moved out of `facts` at the end, preserving input order. +/// +/// Idempotent under duplicated input records (a duplicate assertion ties with +/// the original and loses; a duplicate retraction leaves the max unchanged). +/// `selective_fact_fetch` relies on this instead of deduplicating. +pub(crate) fn net_asserted_facts(facts: Vec) -> Vec { + use crate::graph::fxhash::FxBuildHasher; + use std::collections::HashMap; + + type EavKey<'a> = (&'a EntityId, &'a str, &'a [u8]); + type WindowKey<'a> = (&'a EntityId, &'a str, &'a [u8], i64, i64); + + let encoded: Vec> = facts.iter().map(|f| encode_value(&f.value)).collect(); + let mut keep = vec![false; facts.len()]; + + { + let mut max_retract_tx: HashMap, u64, FxBuildHasher> = HashMap::default(); + let mut by_window: HashMap, (usize, u64), FxBuildHasher> = + HashMap::default(); + + for (idx, (fact, value_bytes)) in facts.iter().zip(encoded.iter()).enumerate() { + let entity = &fact.entity; + let attribute = fact.attribute.as_str(); + let value = value_bytes.as_slice(); + if fact.asserted { + by_window + .entry((entity, attribute, value, fact.valid_from, fact.valid_to)) + .and_modify(|winner| { + if fact.tx_count > winner.1 { + *winner = (idx, fact.tx_count); + } + }) + .or_insert((idx, fact.tx_count)); + } else { + max_retract_tx + .entry((entity, attribute, value)) + .and_modify(|max_tx| *max_tx = (*max_tx).max(fact.tx_count)) + .or_insert(fact.tx_count); + } + } + + for ((entity, attribute, value, _, _), (idx, tx_count)) in &by_window { + let retract_tx = max_retract_tx + .get(&(*entity, *attribute, *value)) + .copied() + .unwrap_or(0); + if *tx_count > retract_tx + && let Some(slot) = keep.get_mut(*idx) + { + *slot = true; + } + } + } + + facts + .into_iter() + .zip(keep) + .filter_map(|(fact, kept)| kept.then_some(fact)) + .collect() +} +``` +Also add `use crate::graph::fxhash::FxBuildHasher;` only inside the function as shown (keeps the top-level imports untouched). Update the doc-comment link to `[`FxBuildHasher`](crate::graph::fxhash::FxBuildHasher)` if rustdoc complains about the intra-doc link. + +- [ ] **Step 5: Run the storage tests, then the whole suite** + +Run: `cargo test --lib graph::storage` +Expected: all pass, including the 3 new tests. +Run: `cargo test 2>&1 | grep -E "^test result|FAILED|panicked"` +Expected: no failures. If any test fails because it indexed `net_asserted_facts` output assuming HashMap order, that test was already order-fragile: fix the test to compare sorted/set results, never the production code. + +- [ ] **Step 6: Clippy + commit** + +Run: `cargo clippy --all-targets -- -D warnings` → clean. +```bash +git add src/graph/storage.rs +git commit -m "perf: borrow keys and use FxHash in net_asserted_facts (#323)" +``` + +--- + +### Task 3: `(entity, attribute)` EAVT range lookup + +**Files:** +- Modify: `src/graph/storage.rs` — add method inside `impl FactStorage` block that starts with `/// Production helpers on FactStorage` (~line 617), right after `get_facts_by_entity`; tests in `mod tests`. + +**Interfaces:** +- Produces: `pub(crate) fn get_facts_by_entity_attribute_indexed(&self, entity_id: &EntityId, attribute: &Attribute) -> Result>` — every stored record (assert and retract, all versions) whose `entity == entity_id && attribute == attribute`, pending + committed. Task 4 calls it. + +- [ ] **Step 1: Write failing tests in `mod tests`** + +```rust + #[test] + fn entity_attribute_indexed_pending_only() { + let storage = FactStorage::new(); + let e = uuid::Uuid::from_u128(1); + let other = uuid::Uuid::from_u128(2); + storage + .transact(vec![ + (e, ":hash".to_string(), Value::String("h0".into())), + (e, ":other".to_string(), Value::String("o".into())), + (other, ":hash".to_string(), Value::String("x".into())), + ], None) + .unwrap(); + storage + .retract(vec![(e, ":hash".to_string(), Value::String("h0".into()))]) + .unwrap(); + let facts = storage + .get_facts_by_entity_attribute_indexed(&e, &":hash".to_string()) + .unwrap(); + assert_eq!(facts.len(), 2, "assert + retract of :hash for e only"); + assert!(facts.iter().all(|f| f.entity == e && f.attribute == ":hash")); + } + + #[test] + fn entity_attribute_indexed_excludes_prefix_sibling() { + let storage = FactStorage::new(); + let e = uuid::Uuid::from_u128(1); + storage + .transact(vec![ + (e, ":a".to_string(), Value::Integer(1)), + (e, ":ab".to_string(), Value::Integer(2)), + (e, ":a/b".to_string(), Value::Integer(3)), + ], None) + .unwrap(); + let facts = storage + .get_facts_by_entity_attribute_indexed(&e, &":a".to_string()) + .unwrap(); + assert_eq!(facts.len(), 1, "only :a, not :ab or :a/b"); + assert_eq!(facts[0].value, Value::Integer(1)); + } + + #[test] + fn entity_attribute_indexed_no_index_fallback() { + // FactStorage with facts but empty pending indexes and no committed reader + // exercises the fallback branch. + let storage = FactStorage::new(); + let e = uuid::Uuid::from_u128(1); + storage + .transact(vec![ + (e, ":a".to_string(), Value::Integer(1)), + (e, ":b".to_string(), Value::Integer(2)), + ], None) + .unwrap(); + storage.replace_pending_indexes(crate::storage::index::Indexes::new()); + let facts = storage + .get_facts_by_entity_attribute_indexed(&e, &":b".to_string()) + .unwrap(); + assert_eq!(facts.len(), 1); + assert_eq!(facts[0].value, Value::Integer(2)); + } + + #[test] + fn entity_attribute_indexed_committed_and_pending() { + use crate::storage::CommittedFactReader; + use crate::storage::index::{FactRef, Indexes}; + use std::sync::Arc; + + struct MockLoader { + facts: Vec, + } + impl CommittedFactReader for MockLoader { + fn resolve(&self, fr: FactRef) -> anyhow::Result { + self.facts + .get(fr.slot_index as usize) + .cloned() + .ok_or_else(|| anyhow::anyhow!("no fact at slot")) + } + fn stream_all(&self) -> anyhow::Result> { + Ok(self.facts.clone()) + } + fn committed_page_count(&self) -> u64 { + 1 + } + } + + let storage = FactStorage::new(); + let e = uuid::Uuid::from_u128(1); + let committed = vec![ + make_assert(e, ":a", Value::Integer(1), 1, 0, VALID_TIME_FOREVER), + make_assert(e, ":ab", Value::Integer(9), 1, 0, VALID_TIME_FOREVER), + ]; + let mut indexes = Indexes::new(); + for (slot, f) in committed.iter().enumerate() { + indexes.insert( + f, + FactRef { + page_id: 1, + slot_index: u16::try_from(slot).unwrap(), + }, + ); + } + storage.replace_pending_indexes(indexes); + storage.set_committed_reader(Arc::new(MockLoader { facts: committed })); + + let facts = storage + .get_facts_by_entity_attribute_indexed(&e, &":a".to_string()) + .unwrap(); + assert_eq!(facts.len(), 1, "committed :a only, :ab excluded"); + assert_eq!(facts[0].value, Value::Integer(1)); + } +``` +`FactStorage::transact(&self, Vec<(EntityId, Attribute, Value)>, Option) -> Result` and `FactStorage::retract(&self, Vec<(EntityId, Attribute, Value)>) -> Result<(TxId, u64)>` are the real signatures (verified). Each test transacts distinct attributes per entity, so the v2 same-transaction multi-value key collision (#371) cannot interfere. + +Note: the mock uses `page_id: 1` entries in the *pending* index map; this exercises the committed-resolve branch of `resolve_fact_ref` through the pending range loop, mirroring `test_committed_reader_resolves_facts`. The on-disk committed index path (`range_scan_eavt`) is covered end-to-end by Task 4's file-backed tests. + +- [ ] **Step 2: Run to verify failure** + +Run: `cargo test --lib entity_attribute_indexed` +Expected: compile error `no method named get_facts_by_entity_attribute_indexed`. + +- [ ] **Step 3: Implement** + +Insert after `get_facts_by_entity`: +```rust + /// Get every stored record for one `(entity, attribute)` pair (index-driven, #323). + /// + /// Range-scans EAVT over `[(e, a, …), (e, next_prefix(a), …))` so other + /// attributes of the same entity — and their version history — are never + /// resolved. Both index sources post-filter on the exact attribute because a + /// prefix range also covers longer attributes (`:a` → `:ab`). + pub(crate) fn get_facts_by_entity_attribute_indexed( + &self, + entity_id: &EntityId, + attribute: &Attribute, + ) -> Result> { + use crate::storage::index::EavtKey; + let d = self.data.read().unwrap_or_else(|e| e.into_inner()); + let matches = |f: &Fact| &f.entity == entity_id && &f.attribute == attribute; + + // Fallback: no indexes built yet + if d.pending_indexes.eavt.is_empty() && d.committed_index_reader.is_none() { + let mut result: Vec = d.facts.iter().filter(|f| matches(f)).cloned().collect(); + if let Some(loader) = &d.committed { + result.extend(loader.stream_all()?.into_iter().filter(|f| matches(f))); + } + return Ok(result); + } + + let start = EavtKey { + entity: *entity_id, + attribute: attribute.clone(), + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + }; + // None only for the empty attribute; then the committed scan is unbounded + // above and relies on the post-filter. + let end_opt: Option = next_string_prefix(attribute).map(|next_attr| EavtKey { + entity: *entity_id, + attribute: next_attr, + valid_from: i64::MIN, + valid_to: i64::MIN, + tx_count: 0, + }); + + let mut facts = Vec::new(); + + // Pending: walk forward from `start` while still on this exact (e, a). + for (key, &fr) in d.pending_indexes.eavt.range(start.clone()..) { + if key.entity != *entity_id || key.attribute != *attribute { + break; + } + facts.push(resolve_fact_ref(&d, fr)?); + } + + // Committed: on-disk B+tree range scan, post-filtered on the exact pair. + if let Some(reader) = &d.committed_index_reader { + for fr in reader.range_scan_eavt(&start, end_opt.as_ref())? { + let fact = resolve_fact_ref(&d, fr)?; + if matches(&fact) { + facts.push(fact); + } + } + } + + Ok(facts) + } +``` +Why the pending loop can `break`: EAVT orders by `(entity, attribute, …)`, so all keys for the exact pair are contiguous starting at `start`; the first key with a different entity or attribute ends the run (`:ab` sorts after every `:a` key). + +- [ ] **Step 4: Run tests** + +Run: `cargo test --lib entity_attribute_indexed` +Expected: 4 passed. + +- [ ] **Step 5: Clippy + commit** + +Run: `cargo clippy --all-targets -- -D warnings`. `get_facts_by_entity_attribute_indexed` is unused outside tests until Task 4 → a `dead_code` warning is expected here; if clippy's `-D warnings` blocks the commit hook, fold this commit into Task 4 instead of adding `#[allow(dead_code)]`. +```bash +git add src/graph/storage.rs +git commit -m "perf: add (entity, attribute) EAVT range lookup (#323)" +``` + +--- + +### Task 4: Narrow `selective_fact_fetch` and drop its dedup + +**Files:** +- Modify: `src/query/datalog/executor.rs` — `selective_fact_fetch` (~lines 369–455) and the doc comment on `filter_facts_for_query` if it mentions dedup +- Create: `tests/point_query_history_test.rs` + +**Interfaces:** +- Consumes: `FactStorage::get_facts_by_entity_attribute_indexed` (Task 3); `FactStorage::get_facts_by_entity`, `get_facts_by_attribute` (existing); `net_asserted_facts` idempotence (Task 2). +- Produces: same signature `fn selective_fact_fetch(&self, patterns: &[Pattern], threshold: usize) -> Option>`. + +- [ ] **Step 1: Write the integration tests** + +`tests/point_query_history_test.rs`: +```rust +//! #323 — bound-entity point queries must return exactly what a full scan returns, +//! while only reading the queried attributes' history. +//! +//! Oracle: the same query with `:as-of 1000000000` goes through the full-scan +//! `get_facts_as_of` path (never the selective path) and, since every tx_count in +//! these tests is far below that bound, must produce identical rows. +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::{Minigraf, QueryResult}; + +const ORACLE_AS_OF: &str = ":as-of 1000000000"; + +fn rows(r: QueryResult) -> Vec { + match r { + QueryResult::QueryResults { results, .. } => { + let mut v: Vec = results.iter().map(|row| format!("{row:?}")).collect(); + v.sort(); + v + } + _ => panic!("expected QueryResults"), + } +} + +/// Run `(query [:find :where ])` via the selective path and via +/// the full-scan oracle; assert equal; return the selective rows. +fn same_as_full_scan(db: &Minigraf, find: &str, opts: &str, body: &str) -> Vec { + let selective = rows( + db.execute(&format!("(query [:find {find} {opts} :where {body}])")) + .unwrap(), + ); + let oracle = rows( + db.execute(&format!( + "(query [:find {find} {ORACLE_AS_OF} {opts} :where {body}])" + )) + .unwrap(), + ); + assert_eq!(selective, oracle, "selective path diverged from full scan"); + selective +} + +fn churn(db: &Minigraf, depth: usize) { + db.execute("(transact [[:e/hot :other \"o\"]])").unwrap(); + db.execute("(transact {:valid-from \"2020-01-01T00:00:00Z\"} [[:e/hot :hash \"h0\"]])") + .unwrap(); + for i in 1..depth { + db.execute(&format!("(retract [[:e/hot :hash \"h{}\"]])", i - 1)) + .unwrap(); + db.execute(&format!( + "(transact {{:valid-from \"2020-01-01T00:00:00Z\"}} [[:e/hot :hash \"h{i}\"]])" + )) + .unwrap(); + } +} + +#[test] +fn churned_attribute_live_value_in_memory() { + let db = Minigraf::in_memory().unwrap(); + churn(&db, 50); + let r = same_as_full_scan(&db, "?v", "", "[:e/hot :hash ?v]"); + assert_eq!(r.len(), 1, "exactly one live value"); + assert!(r[0].contains("h49")); + let r = same_as_full_scan(&db, "?v", "", "[:e/hot :other ?v]"); + assert_eq!(r.len(), 1); +} + +#[test] +fn churned_attribute_live_value_file_backed() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + { + let db = Minigraf::open(&path).unwrap(); + churn(&db, 30); + db.checkpoint().unwrap(); + // Pending on top of committed: more churn after the checkpoint, + // including reasserting a previously retracted value. + db.execute("(retract [[:e/hot :hash \"h29\"]])").unwrap(); + db.execute("(transact {:valid-from \"2020-01-01T00:00:00Z\"} [[:e/hot :hash \"h3\"]])") + .unwrap(); + let r = same_as_full_scan(&db, "?v", "", "[:e/hot :hash ?v]"); + assert_eq!(r.len(), 1); + assert!(r[0].contains("\"h3\"")); + } + let db = Minigraf::open(&path).unwrap(); + let r = same_as_full_scan(&db, "?v", "", "[:e/hot :hash ?v]"); + assert_eq!(r.len(), 1); + assert!(r[0].contains("\"h3\"")); +} + +#[test] +fn two_attributes_on_one_entity() { + let db = Minigraf::in_memory().unwrap(); + churn(&db, 10); + let r = same_as_full_scan(&db, "?h ?o", "", "[:e/hot :hash ?h] [:e/hot :other ?o]"); + assert_eq!(r.len(), 1); +} + +#[test] +fn five_attributes_on_one_entity() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:e/x :a 1] [:e/x :b 2] [:e/x :c 3] [:e/x :d 4] [:e/x :f 5]])") + .unwrap(); + let r = same_as_full_scan( + &db, + "?a ?b ?c ?d ?f", + "", + "[:e/x :a ?a] [:e/x :b ?b] [:e/x :c ?c] [:e/x :d ?d] [:e/x :f ?f]", + ); + assert_eq!(r.len(), 1); +} + +#[test] +fn bound_entity_variable_attribute_sees_all() { + let db = Minigraf::in_memory().unwrap(); + churn(&db, 5); + let r = same_as_full_scan(&db, "?a ?v", "", "[:e/hot ?a ?v]"); + assert_eq!(r.len(), 2, ":hash h4 and :other o"); + // Mixed: one narrowed pattern + one variable-attribute pattern on the same entity. + let r = same_as_full_scan(&db, "?a ?h", "", "[:e/hot :hash ?h] [:e/hot ?a _]"); + assert_eq!(r.len(), 2); +} + +#[test] +fn bound_entity_pseudo_attribute_matches_full_scan() { + let db = Minigraf::in_memory().unwrap(); + churn(&db, 5); + same_as_full_scan( + &db, + "?v ?vf", + ":any-valid-time", + "[:e/hot :hash ?v] [:e/hot :db/valid-from ?vf]", + ); +} + +#[test] +fn not_and_or_on_narrowed_entity() { + let db = Minigraf::in_memory().unwrap(); + churn(&db, 5); + db.execute("(transact [[:e/hot :flag true]])").unwrap(); + same_as_full_scan(&db, "?v", "", "[:e/hot :hash ?v] (not [:e/hot :flag false])"); + let r = same_as_full_scan(&db, "?v", "", "[:e/hot :hash ?v] (not [:e/hot :flag true])"); + assert!(r.is_empty(), "not must see :flag although only :hash is projected"); + same_as_full_scan( + &db, + "?v", + "", + "(or [:e/hot :hash ?v] [:e/hot :other ?v])", + ); +} + +#[test] +fn prefix_sibling_attribute_not_leaked() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("p.graph")).unwrap(); + db.execute("(transact [[:e/x :hash \"a\"] [:e/x :hash2 \"b\"] [:e/x :hash/sub \"c\"]])") + .unwrap(); + db.checkpoint().unwrap(); + db.execute("(transact [[:e/x :hashx \"d\"]])").unwrap(); + let r = same_as_full_scan(&db, "?v", "", "[:e/x :hash ?v]"); + assert_eq!(r.len(), 1); + assert!(r[0].contains("\"a\"")); +} + +#[test] +fn entity_and_attribute_patterns_mixed() { + let db = Minigraf::in_memory().unwrap(); + churn(&db, 5); + db.execute("(transact [[:e/a :hash \"z\"]])").unwrap(); + same_as_full_scan(&db, "?e ?v ?o", "", "[?e :hash ?v] [:e/hot :other ?o]"); +} + +#[test] +fn valid_at_past_on_churned_attribute() { + let db = Minigraf::in_memory().unwrap(); + db.execute( + "(transact {:valid-from \"2020-01-01T00:00:00Z\" :valid-to \"2021-01-01T00:00:00Z\"} [[:e/v :hash \"old\"]])", + ) + .unwrap(); + db.execute("(transact {:valid-from \"2021-01-01T00:00:00Z\"} [[:e/v :hash \"new\"]])") + .unwrap(); + db.execute("(transact [[:e/v :other 1]])").unwrap(); + let r = same_as_full_scan(&db, "?v", ":valid-at \"2020-06-01T00:00:00Z\"", "[:e/v :hash ?v]"); + assert_eq!(r.len(), 1); + assert!(r[0].contains("old")); +} +``` +Adjust syntax only if the parser rejects something (e.g. option order `:as-of` / `:valid-at` / `:any-valid-time` — check `tests/bitemporal_test.rs` for accepted forms); never weaken an assertion to make it pass. + +- [ ] **Step 2: Run tests against the current code** + +Run: `cargo test --test point_query_history_test` +Expected: all PASS already (current code is correct, just slow). These are regression guards for Step 3. If one fails now, stop and investigate — it is a pre-existing bug, report it rather than fixing it inside this task. + +- [ ] **Step 3: Rewrite `selective_fact_fetch`** + +Replace the function (doc comment included) with: +```rust + /// Attempt a selective index-backed fact fetch for the given patterns. + /// + /// Patterns with a bound entity literal (UUID or keyword → deterministic UUID) are + /// fetched by entity; if every pattern on that entity also binds a concrete attribute + /// keyword, only those `(entity, attribute)` EAVT ranges are read, so other attributes' + /// version history is never resolved (#323). An entity also referenced with a variable + /// or pseudo-attribute is read whole. Patterns without a bound entity are fetched by + /// attribute. If any pattern has neither, returns `None` (full scan). + /// + /// Lookup budget: if narrowing needs more than `threshold` lookups, every entity falls + /// back to a single whole-entity scan; only if that still exceeds `threshold` does this + /// return `None`. Narrowing therefore never turns a selective query into a full scan. + /// + /// Results are not deduplicated: the sole caller feeds them to `net_asserted_facts`, + /// which is idempotent under duplicated records. + fn selective_fact_fetch(&self, patterns: &[Pattern], threshold: usize) -> Option> { + use std::collections::{BTreeMap, BTreeSet}; + + // Per bound entity: Some(attrs) = only these attributes are referenced; + // None = the whole entity is needed. BTree* for deterministic lookup order. + let mut entity_attrs: BTreeMap>> = BTreeMap::new(); + let mut attributes: BTreeSet = BTreeSet::new(); + + for pattern in patterns { + let bound_entity = match &pattern.entity { + EdnValue::Uuid(u) => Some(*u), + EdnValue::Keyword(_) => edn_to_entity_id(&pattern.entity).ok(), + _ => None, + }; + + if let Some(uid) = bound_entity { + let slot = entity_attrs + .entry(uid) + .or_insert_with(|| Some(BTreeSet::new())); + match &pattern.attribute { + AttributeSpec::Real(EdnValue::Keyword(attr)) => { + if let Some(attrs) = slot { + attrs.insert(attr.clone()); + } + } + _ => *slot = None, + } + continue; + } + + if let AttributeSpec::Real(EdnValue::Keyword(attr)) = &pattern.attribute { + attributes.insert(attr.clone()); + } else { + return None; + } + } + + let narrowed_lookups: usize = entity_attrs + .values() + .map(|a| a.as_ref().map_or(1, BTreeSet::len)) + .sum::() + + attributes.len(); + let narrow = narrowed_lookups <= threshold; + let total = if narrow { + narrowed_lookups + } else { + entity_attrs.len() + attributes.len() + }; + if total == 0 || total > threshold { + return None; + } + + let mut all_facts: Vec = Vec::new(); + + for (uid, attrs) in &entity_attrs { + match attrs { + Some(attrs) if narrow => { + for attr in attrs { + all_facts.extend( + self.storage + .get_facts_by_entity_attribute_indexed(uid, attr) + .ok()?, + ); + } + } + _ => all_facts.extend(self.storage.get_facts_by_entity(uid).ok()?), + } + } + + for attr in &attributes { + all_facts.extend(self.storage.get_facts_by_attribute(attr).ok()?); + } + + Some(all_facts) + } +``` +Behaviour kept from the old version: any storage error → `None` (caller falls back to full scan). + +- [ ] **Step 4: Run the targeted and full suites** + +Run: `cargo test --test point_query_history_test` → all pass. +Run: `cargo test 2>&1 | grep -E "^test result|FAILED|panicked"` → no failures. +Run: `cargo clippy --all-targets -- -D warnings` and `cargo fmt --check` → clean. + +- [ ] **Step 5: Commit** +```bash +git add src/query/datalog/executor.rs tests/point_query_history_test.rs +git commit -m "perf: narrow bound-entity fetch to queried attributes, drop redundant dedup (#323)" +``` + +--- + +### Task 5: Benchmark, measure, docs, follow-up issue + +**Files:** +- Modify: `benches/minigraf_bench.rs`, `docs/BENCHMARKS.md`, `CHANGELOG.md`, `docs/TEST_COVERAGE.md`, `CLAUDE.md` + +- [ ] **Step 1: Add the bench group** + +Before `// ── query/predicate_pushdown` add: +```rust +// ── point_query_chain_depth (Issue #323) ───────────────────────────────────── +// +// One entity whose :hash is retracted/reasserted `depth` times (exactly one live +// value), plus a never-churned :other on the same entity; checkpointed file DB. + +fn bench_point_query_chain_depth(c: &mut Criterion) { + const DEPTHS: &[usize] = &[1, 500, 2000]; + const QUERIES: &[(&str, &str)] = &[ + ("churned_attr", "(query [:find ?v :where [:e/hot :hash ?v]])"), + ("sibling_attr", "(query [:find ?v :where [:e/hot :other ?v]])"), + ("attr_scan", "(query [:find ?v :where [?e :hash ?v]])"), + ]; + for &(name, q) in QUERIES { + let mut group = c.benchmark_group(format!("point_query_chain_depth/{name}")); + group.sample_size(20); + for &depth in DEPTHS { + let dir = tempfile::tempdir().unwrap(); + let db = minigraf::Minigraf::open(dir.path().join("b.graph")).unwrap(); + for i in 0..2000 { + db.execute(&format!("(transact [[:f/{i} :x {i}]])")).unwrap(); + } + db.execute("(transact [[:e/hot :other \"o\"]])").unwrap(); + db.execute( + "(transact {:valid-from \"2020-01-01T00:00:00Z\"} [[:e/hot :hash \"h0\"]])", + ) + .unwrap(); + for i in 1..depth { + db.execute(&format!("(retract [[:e/hot :hash \"h{}\"]])", i - 1)) + .unwrap(); + db.execute(&format!( + "(transact {{:valid-from \"2020-01-01T00:00:00Z\"}} [[:e/hot :hash \"h{i}\"]])" + )) + .unwrap(); + } + db.checkpoint().unwrap(); + group.bench_with_input(BenchmarkId::from_parameter(depth), &depth, |b, _| { + b.iter(|| black_box(db.execute(q).unwrap())); + }); + } + group.finish(); + } +} +``` +Register `bench_point_query_chain_depth, // Issue #323` in `criterion_group!` after `bench_predicate_pushdown`. Confirm `tempfile` is usable from benches (it is a non-wasm dev-dependency; benches are native). + +- [ ] **Step 2: Baseline vs after** + +Commit the bench first, then measure the baseline in a throwaway worktree at the branch's merge-base (pre-Task-1 `src/`) with the new bench file copied in. Do not use `git stash` (shared across worktrees). +```bash +git add benches/minigraf_bench.rs && git commit -m "bench: point_query_chain_depth (#323)" +BASE=$(git merge-base HEAD origin/main) +git worktree add /tmp/claude-1000/-home-aditya-Work-AMC-Minigraf-minigraf/008662fe-0225-4a06-a393-915f375e4da0/scratchpad/base "$BASE" +cp benches/minigraf_bench.rs /tmp/claude-1000/-home-aditya-Work-AMC-Minigraf-minigraf/008662fe-0225-4a06-a393-915f375e4da0/scratchpad/base/benches/ +(cd /tmp/claude-1000/-home-aditya-Work-AMC-Minigraf-minigraf/008662fe-0225-4a06-a393-915f375e4da0/scratchpad/base && cargo bench --bench minigraf_bench -- point_query_chain_depth --save-baseline before) +cargo bench --bench minigraf_bench -- point_query_chain_depth +git worktree remove --force /tmp/claude-1000/-home-aditya-Work-AMC-Minigraf-minigraf/008662fe-0225-4a06-a393-915f375e4da0/scratchpad/base +``` +Record the median for each (query, depth) before and after. + +Acceptance (spec §5): `sibling_attr` at depth 2000 within 2× of depth 1; `churned_attr` and `attr_scan` at depth 2000 ≥3× faster than before. If not met, stop and report the numbers — do not tune further without discussing. + +- [ ] **Step 3: Docs** + +- `CHANGELOG.md`: add at top, above `## v2.0.1`: + ```markdown + ## Unreleased + + ### Performance + + - **Bound-entity point queries no longer pay for other attributes' history (#323).** `[:e :attr ?v]` now range-scans only `(e, :attr)` in the EAVT index instead of every record the entity has ever had. The remaining per-record cost on a heavily retracted/reasserted attribute is cut by × (cheaper net-assert grouping, redundant dedup removed); attribute scans (`[?e :attr ?v]`) benefit from the same change. File format and results unchanged. Resolve cost on a churned attribute is still proportional to its history on v2.x; the structural fix needs the v8 index keys and is tracked in #. + ``` + Fill `` from Step 2 and `` from Step 4. +- `docs/BENCHMARKS.md`: add a "Point query vs. version-chain depth (#323)" table (before/after medians) under the query latency section, following that file's existing table style. +- `docs/TEST_COVERAGE.md` and `CLAUDE.md` test count: run `cargo test 2>&1 | grep "^test result"` and sum passed/ignored; update both to the new totals and add `tests/point_query_history_test.rs` to the per-file breakdown. +- Also add `fxhash.rs` to the `src/graph/` module list in `CLAUDE.md`'s Architecture section. + +- [ ] **Step 4: File the v3 follow-up issue** + +```bash +gh issue create --milestone "v3.0.0" --title "perf: compute net-assert on v8 index keys before resolving facts (O(live) point queries)" --body "$(cat <<'EOF' +Follow-up to #323 (v2.x mitigation). + +v8 `EavtKey`/`AevtKey` carry `value_bytes` and `asserted`. `net_asserted_facts` semantics can therefore be computed over index keys **before** `resolve_fact_ref`, and only surviving records resolved. Resolve cost becomes O(live facts); the key walk stays O(history) but over B+tree leaf pages, which is far cheaper than a page resolve + postcard decode per record. + +Scope: `get_facts_by_entity_attribute_indexed`, `get_facts_by_entity`, `get_facts_by_attribute` on the `v3` branch; the executor's selective path. `:as-of` needs `tx_count <= N` applied on keys first. + +Refs #323 +EOF +)" +``` +If the milestone name differs, run `gh api repos/:owner/:repo/milestones --jq '.[].title'` and use the v3.0.0 one. + +- [ ] **Step 5: Commit docs** +```bash +git add CHANGELOG.md docs/BENCHMARKS.md docs/TEST_COVERAGE.md CLAUDE.md +git commit -m "docs: changelog, benchmarks and test counts for #323" +``` + +- [ ] **Step 6: PR** — push the branch and open a PR against `main` whose body ends with `Closes #323` and the attribution footer; then monitor CI until green (never merge without explicit confirmation). diff --git a/docs/superpowers/plans/2026-09-26-incremental-checkpoint.md b/docs/superpowers/plans/2026-09-26-incremental-checkpoint.md new file mode 100644 index 0000000000..88eca25c69 --- /dev/null +++ b/docs/superpowers/plans/2026-09-26-incremental-checkpoint.md @@ -0,0 +1,1076 @@ +# Incremental Checkpoint Index Rebuild Implementation Plan + +> **For agentic workers:** REQUIRED SUB-SKILL: Use superpowers:subagent-driven-development (recommended) or superpowers:executing-plans to implement this plan task-by-task. Steps use checkbox (`- [ ]`) syntax for tracking. + +**Goal:** Make `checkpoint()` decode/re-encode only the index leaves the delta touches, and stop re-reading unchanged fact pages for the file checksum, without changing file format v7. + +**Architecture:** `save()` snapshots each old B+tree's raw leaf pages, then `rebuild_btree_incremental` copies untouched leaves verbatim (patching only `next_leaf`), repacks only leaves that receive pending entries, and rebuilds internal levels with a helper extracted from `build_btree`. `PersistentFactStorage` caches the CRC32 state over its (immutable) fact pages so each save hashes only new fact pages plus the index region. + +**Tech Stack:** Rust (MSRV 1.89), postcard, crc32fast, criterion. + +**Spec:** `docs/superpowers/specs/2026-09-26-incremental-checkpoint-design.md` + +## Global Constraints + +- File format stays v7: node layout, header layout, and `index_checksum` value (CRC32 over pages `1..page_count`) are unchanged; files must open on v2.0.1 without the index-rebuild path. +- No public API change; no new dependencies (dev or runtime). +- Test assert messages must never format `Result`, `Fact`, `Value`, `EdnValue`, `EavtKey`, `FactRef` or anything containing a `Uuid` with `{:?}` (CodeQL `rust/cleartext-logging`). Use plain string messages. +- Match the surrounding clippy style: `btree_v6.rs` functions that index/do arithmetic carry `#[allow(clippy::arithmetic_side_effects)]` / `#[allow(clippy::indexing_slicing)]`; errors use `err_coded!`/`bail_coded!` with `ErrorCode::Int049` for B+tree invariant violations. +- `cargo test --release` does not work (panic=abort profile); use `cargo test` and `cargo bench`. +- Pre-push hook runs `cargo fmt --check`, `cargo clippy`, `cargo test`; run `cargo fmt` and `cargo clippy --all-targets -- -D warnings` before each commit. +- Commit messages end with: + ``` + Co-Authored-By: Claude Opus 5.5 + Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy + ``` +- Success target: 50k-fact graph, checkpoint after 1 fact ≤ 15 ms (was ~80 ms). + +## Review Focus + +1. **New index region overlaps the old one** — `save()` writes new fact pages over the start of the old index, and the new tree starts where the old tree's leaves were. Expect: entries identical to a from-scratch build. Pinned by `test_incremental_new_tree_overlaps_old_pages` (Task 3). +2. **Repeated checkpoints on an incrementally built tree** — the second, third… checkpoint consumes a tree whose leaves were raw-copied/split by the previous one. Expect: still exact. Pinned by `test_incremental_repeated_rounds` (Task 3) and `test_incremental_saves_keep_indexes_and_checksum_exact` (Task 4). +3. **Pending keys outside the old key range** (below the first leaf's first key, above the last leaf's last key). Expect: land in first/last leaf, range scans find them. Pinned by `test_incremental_pending_outside_old_range` (Task 3). +4. **Stale or wrong checksum-prefix cache** (after a failed save, a rebuild-on-open, or a page-count mismatch). Expect: silent fallback to a full pass and a correct stored checksum. Pinned by `test_prefix_cache_page_count_mismatch_falls_back` and `test_prefix_cache_absent_after_rebuild_on_open` (Task 4). +5. **Many pending entries into one leaf** (hot key range, e.g. all new facts for one entity). Expect: leaf splits into several ≤75%-fill leaves, no overflow. Pinned by `test_incremental_many_pending_into_one_leaf_splits` (Task 3). + +--- + +### Task 1: Benchmark `checkpoint/after_1_fact` and record the baseline + +**Files:** +- Modify: `benches/minigraf_bench.rs` (new function after `bench_checkpoint`, ~line 416; register in `criterion_group!` at ~line 1778) + +**Interfaces:** +- Consumes: `helpers::populate_file_no_checkpoint(n, &path)`, `helpers::open_file_no_checkpoint(&path) -> Arc` +- Produces: criterion group `checkpoint/after_1_fact` with ids `10k`, `100k` + +- [ ] **Step 1: Add the bench function** after `bench_checkpoint`: + +```rust +// ── checkpoint/after_1_fact (#315) ──────────────────────────────────────────── + +/// Checkpoint cost when only one fact is dirty, on an already-checkpointed graph. +/// Before #315 this was flat in dirty bytes and proportional to graph size. +fn bench_checkpoint_after_1_fact(c: &mut Criterion) { + use criterion::BatchSize; + use tempfile::NamedTempFile; + + let mut group = c.benchmark_group("checkpoint/after_1_fact"); + group.sample_size(20); + for &(label, n) in &[("10k", 10_000usize), ("100k", 100_000)] { + let tmp = NamedTempFile::new().unwrap(); + let path = tmp.path().to_str().unwrap().to_string(); + helpers::populate_file_no_checkpoint(n, &path); + let db = helpers::open_file_no_checkpoint(&path); + db.checkpoint().unwrap(); + let mut i = 0u64; + group.bench_function(BenchmarkId::from_parameter(label), |b| { + b.iter_batched( + || { + i += 1; + db.execute(&format!("(transact [[:ck{i} :val {i}]])")) + .unwrap(); + }, + |()| db.checkpoint().unwrap(), + BatchSize::SmallInput, + ); + }); + } + group.finish(); +} +``` + +- [ ] **Step 2: Register it** — add `bench_checkpoint_after_1_fact,` to the `criterion_group!(benches, ...)` list directly after `bench_checkpoint,`. + +- [ ] **Step 3: Record the baseline** + +Run: `cargo bench --bench minigraf_bench -- checkpoint/after_1_fact` +Expected: completes; note the two `time:` medians (≈ tens of ms at 100k) in the task report — they are the "Before" column for Task 5. + +- [ ] **Step 4: Commit** + +```bash +cargo fmt && git add benches/minigraf_bench.rs +git commit -m "bench: add checkpoint/after_1_fact group (#315)" +``` + +--- + +### Task 2: Extract leaf encoding, fill rule and internal-level build from `build_btree` + +Pure refactor; existing `btree_v6` tests are the safety net. + +**Files:** +- Modify: `src/storage/btree_v6.rs:62-420` + +**Interfaces:** +- Produces (module-private, used by Task 3): + - `fn encode_leaf_page(entries: &[Vec], next_leaf: u64) -> Result>` + - `fn leaf_overflows(n_entries: usize, data_bytes: usize, entry_len: usize) -> bool` + - `fn build_internal_levels(leaf_infos: Vec<(u64, Vec)>, backend: &mut dyn StorageBackend, cache: &PageCache, next_page: u64) -> Result<(u64, u64)>` — returns `(root_page_id, next_free_page_id)` + +- [ ] **Step 1: Split `write_leaf_page`.** Rename the current body (everything up to but excluding `backend.write_page`) into `encode_leaf_page` returning the page, and make `write_leaf_page` a wrapper: + +```rust +/// Encode a leaf page: fixed header, slot directory, entries written end-to-start. +/// +/// `entries`: each element is the postcard-serialised `(K, FactRef)` bytes for +/// one index entry, in sort order. +#[allow(clippy::arithmetic_side_effects, clippy::indexing_slicing)] +fn encode_leaf_page(entries: &[Vec], next_leaf: u64) -> Result> { + // ... existing body of write_leaf_page from `let entry_count = ...` + // through the slot-directory loop, unchanged ... + Ok(page) +} + +/// Write a single leaf page and insert it into the cache. +fn write_leaf_page( + backend: &mut dyn StorageBackend, + cache: &PageCache, + page_id: u64, + entries: &[Vec], + next_leaf: u64, +) -> Result<()> { + let page = encode_leaf_page(entries, next_leaf)?; + backend.write_page(page_id, &page)?; + cache.put_dirty(page_id, page); + Ok(()) +} +``` + +- [ ] **Step 2: Extract the fill rule.** Add below `write_internal_page`: + +```rust +/// True when adding an entry of `entry_len` bytes to a leaf that already holds +/// `n_entries` entries totalling `data_bytes` would exceed the fill threshold. +#[allow(clippy::arithmetic_side_effects)] +fn leaf_overflows(n_entries: usize, data_bytes: usize, entry_len: usize) -> bool { + LEAF_HEADER_SIZE + (n_entries + 1) * SLOT_SIZE + data_bytes + entry_len > PAGE_FILL_BYTES +} +``` + +and in `build_btree` phase 1 replace + +```rust + let projected = LEAF_HEADER_SIZE + + (cur_entries.len() + 1) * SLOT_SIZE + + cur_data_bytes + + entry_bytes.len(); + + if projected > PAGE_FILL_BYTES && !cur_entries.is_empty() { +``` + +with + +```rust + if !cur_entries.is_empty() + && leaf_overflows(cur_entries.len(), cur_data_bytes, entry_bytes.len()) + { +``` + +- [ ] **Step 3: Extract phase 2.** Move everything in `build_btree` from `// Single leaf: it is the root` to the end of the function into: + +```rust +/// Build internal levels bottom-up over `leaf_infos` (`(page_id, first_key_bytes)` +/// per leaf, in key order), writing nodes from `next_page` onward. +/// +/// Returns `(root_page_id, next_free_page_id)`. A single leaf is its own root. +#[allow(clippy::arithmetic_side_effects, clippy::indexing_slicing)] +fn build_internal_levels( + leaf_infos: Vec<(u64, Vec)>, + backend: &mut dyn StorageBackend, + cache: &PageCache, + next_page: u64, +) -> Result<(u64, u64)> { + if leaf_infos.is_empty() { + bail_coded!( + ErrorCode::Int049, + "build_internal_levels: no leaves".to_string() + ); + } + let mut next_page = next_page; + let mut current_level = leaf_infos; + loop { + // ... existing phase-2 loop body, unchanged (it already returns + // `(current_level[0].0, next_page)` when current_level.len() == 1) ... + } +} +``` + +Delete the now-redundant "Single leaf: it is the root" block (the loop handles `len() == 1`). End `build_btree` with: + +```rust + build_internal_levels(leaf_infos, backend, cache, next_page) +``` + +- [ ] **Step 4: Run the B+tree and storage tests** + +Run: `cargo test --lib storage::` +Expected: all PASS (no behaviour change). + +- [ ] **Step 5: Commit** + +```bash +cargo fmt && cargo clippy --all-targets -- -D warnings +git add src/storage/btree_v6.rs +git commit -m "refactor(btree_v6): extract leaf encoding, fill rule, internal-level build (#315)" +``` + +--- + +### Task 3: `collect_leaf_pages` and `rebuild_btree_incremental` + +**Files:** +- Modify: `src/storage/btree_v6.rs` (new section after `merge_sorted_vecs`; tests in the existing `mod tests`) + +**Interfaces:** +- Consumes (Task 2): `encode_leaf_page`, `leaf_overflows`, `build_internal_levels`; existing `build_btree`, `btree_entries`, `merge_sorted_vecs`, `read_leaf_entries`, `find_leftmost_leaf`, `read_u16_at`, `read_u64_at`. +- Produces (used by Task 4): + - `pub fn collect_leaf_pages(root_page_id: u64, backend: &dyn StorageBackend, cache: &PageCache) -> Result>>>` + - `pub fn rebuild_btree_incremental(old_leaves: Vec>>, pending: Vec<(K, FactRef)>, backend: &mut dyn StorageBackend, cache: &PageCache, start_page_id: u64) -> Result<(u64, u64)> where K: Serialize + for<'de> Deserialize<'de> + Ord` — `pending` must be sorted; returns `(root_page_id, next_free_page_id)`. + +- [ ] **Step 1: Write the failing tests** in `mod tests` (add `use std::sync::Arc;` if not already imported there): + +```rust + /// Deterministic xorshift64 so randomized tests are reproducible without deps. + struct Rng(u64); + impl Rng { + fn next(&mut self) -> u64 { + let mut x = self.0; + x ^= x << 13; + x ^= x >> 7; + x ^= x << 17; + self.0 = x; + x + } + } + + /// `n` EAVT entries with random entities; `counter` keeps keys unique. + fn random_eavt(rng: &mut Rng, n: usize, counter: &mut u64) -> Vec<(EavtKey, FactRef)> { + let mut v: Vec<(EavtKey, FactRef)> = (0..n) + .map(|_| { + *counter += 1; + let entity = (u128::from(rng.next()) << 64) | u128::from(*counter); + make_eavt(entity, ":attr", *counter) + }) + .collect(); + v.sort(); + v + } + + fn sorted_union( + a: &[(EavtKey, FactRef)], + b: &[(EavtKey, FactRef)], + ) -> Vec<(EavtKey, FactRef)> { + let mut v: Vec<_> = a.iter().chain(b.iter()).cloned().collect(); + v.sort(); + v + } + + /// Build `committed` at page 1, then rebuild with `pending` starting at `start`. + fn build_then_incremental( + committed: &[(EavtKey, FactRef)], + pending: &[(EavtKey, FactRef)], + start: u64, + ) -> (MemoryBackend, PageCache, u64, u64) { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let ser = btree_entries(committed.iter().cloned()).unwrap(); + let (old_root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let leaves = collect_leaf_pages(old_root, &backend, &cache).unwrap(); + let (root, next_free) = + rebuild_btree_incremental(leaves, pending.to_vec(), &mut backend, &cache, start) + .unwrap(); + (backend, cache, root, next_free) + } + + /// Stream equality, a strictly ascending next_leaf chain of non-empty leaves, + /// and range_scan agreement on random bounds. + fn assert_tree_exact( + root: u64, + backend: &MemoryBackend, + cache: &PageCache, + expected: &[(EavtKey, FactRef)], + rng: &mut Rng, + ) { + let got: Vec<(EavtKey, FactRef)> = stream_all_entries(root, backend, cache).unwrap(); + assert_eq!(got.len(), expected.len(), "entry count differs"); + assert!(got == expected, "streamed entries differ from expected"); + + let leaves = collect_leaf_pages(root, backend, cache).unwrap(); + if expected.is_empty() { + assert_eq!(leaves.len(), 1, "empty tree is one empty leaf"); + } else { + for page in &leaves { + assert!(read_u16_at(&page[..], 2).unwrap() > 0, "empty leaf in tree"); + } + } + + for _ in 0..20 { + if expected.is_empty() { + break; + } + let a = (rng.next() as usize) % expected.len(); + let b = (rng.next() as usize) % expected.len(); + let (lo, hi) = (a.min(b), a.max(b)); + let start = &expected[lo].0; + let end = &expected[hi].0; + let want: Vec = expected[lo..hi].iter().map(|(_, r)| *r).collect(); + let refs = range_scan(root, start, Some(end), backend, cache).unwrap(); + assert!(refs == want, "range_scan differs from expected slice"); + } + } + + #[test] + fn test_incremental_no_pending_copies_leaves_verbatim() { + let mut rng = Rng(0x315); + let mut ctr = 0; + let committed = random_eavt(&mut rng, 2000, &mut ctr); + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let ser = btree_entries(committed.iter().cloned()).unwrap(); + let (old_root, old_next) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let old_leaves = collect_leaf_pages(old_root, &backend, &cache).unwrap(); + let (root, _) = rebuild_btree_incremental( + old_leaves.clone(), + Vec::new(), + &mut backend, + &cache, + old_next, + ) + .unwrap(); + let new_leaves = collect_leaf_pages(root, &backend, &cache).unwrap(); + assert_eq!(new_leaves.len(), old_leaves.len(), "leaf count changed"); + for (o, n) in old_leaves.iter().zip(new_leaves.iter()) { + assert!(o[..4] == n[..4], "leaf header prefix changed"); + assert!(o[12..] == n[12..], "leaf body changed"); + } + assert_tree_exact(root, &backend, &cache, &committed, &mut rng); + } + + #[test] + fn test_incremental_matches_merge_random() { + let mut rng = Rng(0xC0FFEE); + let mut ctr = 0; + for round in 0..40 { + let committed = random_eavt(&mut rng, (rng.next() % 3000) as usize, &mut ctr); + let pending = random_eavt(&mut rng, (rng.next() % 200) as usize, &mut ctr); + let (backend, cache, root, _) = build_then_incremental(&committed, &pending, 5000); + let expected = sorted_union(&committed, &pending); + assert_tree_exact(root, &backend, &cache, &expected, &mut rng); + let _ = round; + } + } + + #[test] + fn test_incremental_pending_outside_old_range() { + let mut rng = Rng(7); + let committed: Vec<_> = (1000u128..3000).map(|n| make_eavt(n, ":a", n as u64)).collect(); + let pending = vec![ + make_eavt(1, ":a", 1), + make_eavt(2, ":a", 2), + make_eavt(9_000, ":a", 9_000), + make_eavt(9_001, ":a", 9_001), + ]; + let (backend, cache, root, _) = build_then_incremental(&committed, &pending, 5000); + assert_tree_exact(root, &backend, &cache, &sorted_union(&committed, &pending), &mut rng); + } + + #[test] + fn test_incremental_many_pending_into_one_leaf_splits() { + let mut rng = Rng(11); + // Committed entities are 0, 10_000, 20_000, ...: pending 0 < e < 10_000 all route to leaf 0. + let committed: Vec<_> = (0u128..2000) + .map(|n| make_eavt(n * 10_000, ":a", n as u64 + 1)) + .collect(); + let pending: Vec<_> = (1u128..3000) + .map(|n| make_eavt(n, ":a", 100_000 + n as u64)) + .collect(); + let (backend, cache, root, _) = build_then_incremental(&committed, &pending, 5000); + assert_tree_exact(root, &backend, &cache, &sorted_union(&committed, &pending), &mut rng); + } + + #[test] + fn test_incremental_empty_old_tree_falls_back_to_bulk_build() { + let mut rng = Rng(13); + let mut ctr = 0; + let pending = random_eavt(&mut rng, 500, &mut ctr); + let (backend, cache, root, _) = build_then_incremental(&[], &pending, 5000); + assert_tree_exact(root, &backend, &cache, &pending, &mut rng); + // Nothing old, nothing new: still a valid single empty leaf. + let (backend, cache, root, next) = build_then_incremental(&[], &[], 5000); + assert_eq!(next, root + 1, "empty result is one page"); + assert_tree_exact(root, &backend, &cache, &[], &mut rng); + } + + #[test] + fn test_incremental_new_tree_overlaps_old_pages() { + // save() writes the new tree over the old tree's pages; old leaves are + // snapshotted first, so the result must still be exact. + let mut rng = Rng(17); + let mut ctr = 0; + let committed = random_eavt(&mut rng, 3000, &mut ctr); + let pending = random_eavt(&mut rng, 100, &mut ctr); + let (backend, cache, root, _) = build_then_incremental(&committed, &pending, 3); + assert_tree_exact(root, &backend, &cache, &sorted_union(&committed, &pending), &mut rng); + } + + #[test] + fn test_incremental_repeated_rounds() { + // Each round consumes the previous round's incrementally built tree, + // writing the new tree at the same start page like save() does. + let mut rng = Rng(19); + let mut ctr = 0; + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let mut expected = random_eavt(&mut rng, 1500, &mut ctr); + let ser = btree_entries(expected.iter().cloned()).unwrap(); + let (mut root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + for round in 0..30u64 { + let pending = random_eavt(&mut rng, 1 + (rng.next() % 150) as usize, &mut ctr); + let leaves = collect_leaf_pages(root, &backend, &cache).unwrap(); + let start = 1 + round % 3; + let (r, _) = + rebuild_btree_incremental(leaves, pending.clone(), &mut backend, &cache, start) + .unwrap(); + root = r; + expected = sorted_union(&expected, &pending); + assert_tree_exact(root, &backend, &cache, &expected, &mut rng); + } + } +``` + +- [ ] **Step 2: Run to verify failure** + +Run: `cargo test --lib btree_v6::tests::test_incremental` +Expected: compile error — `collect_leaf_pages` / `rebuild_btree_incremental` not found. + +- [ ] **Step 3: Implement.** Add after `merge_sorted_vecs`: + +```rust +// ─── Incremental rebuild (#315) ─────────────────────────────────────────────── + +/// Collect the raw leaf pages of the B+tree at `root_page_id`, in key order. +/// +/// `save()` calls this before writing anything: new fact pages overwrite the +/// start of the old index region, so the old leaves must be snapshotted first. +pub fn collect_leaf_pages( + root_page_id: u64, + backend: &dyn StorageBackend, + cache: &PageCache, +) -> Result>>> { + let mut leaves = Vec::new(); + let mut leaf_id = find_leftmost_leaf(root_page_id, backend, cache)?; + loop { + let page = cache.get_or_load(leaf_id, backend)?; + if page.first().copied() != Some(PAGE_TYPE_LEAF) { + bail_coded!( + ErrorCode::Int049, + format!("collect_leaf_pages: expected leaf page at page_id={leaf_id}") + ); + } + let next_leaf = read_u64_at(&page[..], 4)?; + leaves.push(page); + if next_leaf == 0 { + break; + } + leaf_id = next_leaf; + } + Ok(leaves) +} + +/// Decode the key of a leaf's first entry; `None` for an empty leaf. +#[allow(clippy::arithmetic_side_effects)] +fn leaf_first_key(page: &[u8]) -> Result> +where + K: for<'de> Deserialize<'de>, +{ + if read_u16_at(page, 2)? == 0 { + return Ok(None); + } + let offset = read_u16_at(page, LEAF_HEADER_SIZE)? as usize; + let length = read_u16_at(page, LEAF_HEADER_SIZE + 2)? as usize; + let slice = page + .get(offset..offset.saturating_add(length)) + .ok_or_else(|| { + err_coded!( + ErrorCode::Int049, + format!("first entry out of bounds: offset={offset} len={length}") + ) + })?; + let (key, _): (K, FactRef) = postcard::from_bytes(slice)?; + Ok(Some(key)) +} + +/// Writes leaf pages at consecutive page ids, linking each to the next. +/// +/// One page is held back so its `next_leaf` can be set to the following page +/// id, or to 0 once it is known to be the last leaf. +struct LeafEmitter<'a> { + backend: &'a mut dyn StorageBackend, + cache: &'a PageCache, + next_page: u64, + held: Option<(u64, Vec)>, + infos: Vec<(u64, Vec)>, +} + +impl LeafEmitter<'_> { + #[allow(clippy::arithmetic_side_effects)] + fn push(&mut self, page: Vec, first_key_bytes: Vec) -> Result<()> { + let page_id = self.next_page; + self.next_page += 1; + self.release_held(page_id)?; + self.held = Some((page_id, page)); + self.infos.push((page_id, first_key_bytes)); + Ok(()) + } + + fn release_held(&mut self, next_leaf: u64) -> Result<()> { + if let Some((page_id, mut page)) = self.held.take() { + page.get_mut(4..12) + .ok_or_else(|| { + err_coded!( + ErrorCode::Int049, + "page too small to write next_leaf".to_string() + ) + })? + .copy_from_slice(&next_leaf.to_le_bytes()); + self.backend.write_page(page_id, &page)?; + self.cache.put_dirty(page_id, page); + } + Ok(()) + } + + /// Write the last held leaf and return `(leaf_infos, next_free_page_id)`. + fn finish(mut self) -> Result<(Vec<(u64, Vec)>, u64)> { + self.release_held(0)?; + Ok((self.infos, self.next_page)) + } +} + +/// Serialise sorted entries and emit them as leaves using `build_btree`'s fill rule. +#[allow(clippy::arithmetic_side_effects)] +fn emit_packed( + emitter: &mut LeafEmitter<'_>, + entries: impl Iterator, +) -> Result<()> { + let mut cur: Vec> = Vec::new(); + let mut cur_bytes = 0usize; + let mut cur_first: Option> = None; + for (key, fact_ref) in entries { + let entry = postcard::to_allocvec(&(&key, &fact_ref))?; + if !cur.is_empty() && leaf_overflows(cur.len(), cur_bytes, entry.len()) { + let first = cur_first.take().ok_or_else(|| { + err_coded!(ErrorCode::Int049, "BUG: leaf without first key".to_string()) + })?; + emitter.push(encode_leaf_page(&cur, 0)?, first)?; + cur.clear(); + cur_bytes = 0; + } + if cur_first.is_none() { + cur_first = Some(postcard::to_allocvec(&key)?); + } + cur_bytes += entry.len(); + cur.push(entry); + } + if let Some(first) = cur_first { + emitter.push(encode_leaf_page(&cur, 0)?, first)?; + } + Ok(()) +} + +/// Rebuild a B+tree from its old leaves plus sorted `pending` entries. +/// +/// Leaves that receive no pending entry are copied verbatim (only `next_leaf` +/// is patched); only leaves that do are decoded, merged and repacked. Internal +/// levels are rebuilt from scratch. Pending keys route to leaf `i` when +/// `first_key[i] <= key < first_key[i + 1]`; keys below the first leaf's first +/// key go to leaf 0. With no non-empty old leaves this is a plain bulk build. +/// +/// `old_leaves` must be snapshotted (see [`collect_leaf_pages`]) before any +/// page in `start_page_id..` is written. Returns `(root_page_id, next_free_page_id)`. +pub fn rebuild_btree_incremental( + old_leaves: Vec>>, + pending: Vec<(K, FactRef)>, + backend: &mut dyn StorageBackend, + cache: &PageCache, + start_page_id: u64, +) -> Result<(u64, u64)> +where + K: Serialize + for<'de> Deserialize<'de> + Ord, +{ + let mut leaves: Vec<(Arc>, K)> = Vec::with_capacity(old_leaves.len()); + for page in old_leaves { + if let Some(first_key) = leaf_first_key::(&page[..])? { + leaves.push((page, first_key)); + } + } + if leaves.is_empty() { + return build_btree( + btree_entries(pending.into_iter())?.into_iter(), + backend, + cache, + start_page_id, + ); + } + + let mut emitter = LeafEmitter { + backend: &mut *backend, + cache, + next_page: start_page_id, + held: None, + infos: Vec::new(), + }; + let mut pending = pending.into_iter().peekable(); + for (i, (page, first_key)) in leaves.iter().enumerate() { + let upper = leaves.get(i.saturating_add(1)).map(|(_, k)| k); + let mut batch = Vec::new(); + while let Some((key, _)) = pending.peek() { + if upper.is_some_and(|u| key >= u) { + break; + } + if let Some(entry) = pending.next() { + batch.push(entry); + } + } + if batch.is_empty() { + emitter.push((**page).clone(), postcard::to_allocvec(first_key)?)?; + } else { + let old = read_leaf_entries::(&page[..])?; + emit_packed(&mut emitter, merge_sorted_vecs(old, batch))?; + } + } + let (leaf_infos, next_page) = emitter.finish()?; + build_internal_levels(leaf_infos, backend, cache, next_page) +} +``` + +- [ ] **Step 4: Run the tests** + +Run: `cargo test --lib btree_v6::` +Expected: all PASS, including the seven `test_incremental_*`. + +- [ ] **Step 5: Commit** + +```bash +cargo fmt && cargo clippy --all-targets -- -D warnings +git add src/storage/btree_v6.rs +git commit -m "feat(btree_v6): incremental rebuild that copies untouched leaves (#315)" +``` + +--- + +### Task 4: Wire into `save()` and cache the fact-page checksum prefix + +**Files:** +- Modify: `src/storage/persistent_facts.rs` — struct (~line 145), `new` (~line 166), `load` checksum block (~lines 277-301), `save` Steps A/D/checksum (~lines 842-970), `compute_page_checksum` (~line 1102), imports (lines 10-13), tests module + +**Interfaces:** +- Consumes (Task 3): `collect_leaf_pages`, `rebuild_btree_incremental`. +- Produces: field `fact_prefix_crc: Option<(u64, Hasher)>`; `fn hash_pages(backend: &dyn StorageBackend, hasher: &mut Hasher, first_page: u64, num_pages: u64) -> Result<()>`. + +- [ ] **Step 1: Write the failing tests** in the `#[cfg(test)] mod tests` of `persistent_facts.rs`: + +```rust + /// All four on-disk indexes equal a from-scratch derivation from the fact pages, + /// and the stored checksum equals a full pass over pages 1..page_count. + fn assert_indexes_and_checksum_exact( + pfs: &PersistentFactStorage, + ) { + let backend = pfs.backend.lock().unwrap(); + let header = FileHeader::from_bytes(&backend.read_page(0).unwrap()).unwrap(); + let full = compute_page_checksum(&*backend, 1, header.page_count - 1).unwrap(); + assert_eq!(header.index_checksum, full, "stored checksum != full pass"); + + let (facts, refs) = crate::storage::packed_pages::read_all_with_refs( + &*backend, + 1, + header.fact_page_count, + ) + .unwrap(); + let (eavt, aevt, avet, vaet) = build_sorted_index_entries(&facts, &refs); + let cache = &pfs.page_cache; + let got_eavt: Vec<(EavtKey, FactRef)> = + stream_all_entries(header.eavt_root_page, &*backend, cache).unwrap(); + let got_aevt: Vec<(AevtKey, FactRef)> = + stream_all_entries(header.aevt_root_page, &*backend, cache).unwrap(); + let got_avet: Vec<(AvetKey, FactRef)> = + stream_all_entries(header.avet_root_page, &*backend, cache).unwrap(); + let got_vaet: Vec<(VaetKey, FactRef)> = + stream_all_entries(header.vaet_root_page, &*backend, cache).unwrap(); + assert!(got_eavt == eavt, "EAVT differs from full derivation"); + assert!(got_aevt == aevt, "AEVT differs from full derivation"); + assert!(got_avet == avet, "AVET differs from full derivation"); + assert!(got_vaet == vaet, "VAET differs from full derivation"); + } + + /// One transact of `n` facts: new and reused entities, strings and refs (VAET). + fn transact_mixed( + pfs: &mut PersistentFactStorage, + entities: &mut Vec, + n: usize, + seed: u64, + ) { + let mut batch = Vec::new(); + for i in 0..n { + let k = seed.wrapping_mul(31).wrapping_add(i as u64); + let e = if entities.is_empty() || k % 3 == 0 { + let e = Uuid::new_v4(); + entities.push(e); + e + } else { + entities[(k as usize) % entities.len()] + }; + let value = if k % 4 == 0 { + Value::Ref(entities[(k as usize / 4) % entities.len()]) + } else { + Value::String(format!("v{k}")) + }; + batch.push((e, format!(":a{}", k % 5), value)); + } + pfs.storage().transact(batch, None).unwrap(); + pfs.mark_dirty(); + } + + #[test] + fn test_incremental_saves_keep_indexes_and_checksum_exact() { + let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); + let mut entities = Vec::new(); + for round in 0..25u64 { + let n = 1 + ((round * 37) % 60) as usize; + transact_mixed(&mut pfs, &mut entities, n, round); + pfs.save().unwrap(); + assert!(pfs.fact_prefix_crc.is_some(), "prefix cached after save"); + assert_indexes_and_checksum_exact(&pfs); + } + } + + #[test] + fn test_reopen_after_incremental_saves_takes_no_rebuild() { + use crate::storage::backend::FileBackend; + use tempfile::NamedTempFile; + let tmp = NamedTempFile::new().unwrap(); + let path = tmp.path().to_str().unwrap().to_string(); + let mut entities = Vec::new(); + { + let mut pfs = + PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); + for round in 0..10u64 { + transact_mixed(&mut pfs, &mut entities, 40, round); + pfs.save().unwrap(); + } + } + let mut pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); + // Set only when the full checksum matched on load, i.e. no rebuild. + assert!(pfs.fact_prefix_crc.is_some(), "full checksum must match on reopen"); + transact_mixed(&mut pfs, &mut entities, 40, 99); + pfs.save().unwrap(); + assert_indexes_and_checksum_exact(&pfs); + } + + #[test] + fn test_prefix_cache_page_count_mismatch_falls_back() { + let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); + let mut entities = Vec::new(); + transact_mixed(&mut pfs, &mut entities, 50, 1); + pfs.save().unwrap(); + pfs.fact_prefix_crc = Some((999, Hasher::new())); + transact_mixed(&mut pfs, &mut entities, 50, 2); + pfs.save().unwrap(); + assert_indexes_and_checksum_exact(&pfs); + } + + #[test] + fn test_prefix_cache_absent_after_rebuild_on_open() { + use crate::storage::backend::FileBackend; + use tempfile::NamedTempFile; + let tmp = NamedTempFile::new().unwrap(); + let path = tmp.path().to_str().unwrap().to_string(); + let mut entities = Vec::new(); + { + let mut pfs = + PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); + for round in 0..3u64 { + transact_mixed(&mut pfs, &mut entities, 30, round); + pfs.save().unwrap(); + } + } + // Corrupt index_checksum (re-sealing the header) to force the rebuild path. + { + let mut backend = FileBackend::open(&path).unwrap(); + let mut page = backend.read_page(0).unwrap(); + page[64] ^= 0xFF; + let cs = compute_header_checksum_from_bytes(&page); + page[80..84].copy_from_slice(&cs.to_le_bytes()); + backend.write_page(0, &page).unwrap(); + backend.sync().unwrap(); + } + let mut pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); + assert!(pfs.fact_prefix_crc.is_none(), "no prefix after rebuild-on-open"); + transact_mixed(&mut pfs, &mut entities, 30, 7); + pfs.save().unwrap(); + assert_indexes_and_checksum_exact(&pfs); + } +``` + +Add any missing test-module imports (`FileHeader`, `StorageBackend`, `MemoryBackend`, `Value`, `Uuid`, `Hasher`, `EavtKey`/`AevtKey`/`AvetKey`/`VaetKey`, `FactRef`, `stream_all_entries`) — most are already imported via `use super::*;`; the compiler will list the rest. + +- [ ] **Step 2: Run to verify failure** + +Run: `cargo test --lib persistent_facts::tests::test_ -- incremental prefix reopen_after` +Expected: compile error — no field `fact_prefix_crc`. + +- [ ] **Step 3: Add the field.** In `PersistentFactStorage`: + +```rust + committed_fact_pages: Arc, + /// CRC32 state after hashing fact pages `1..=n` (`n` is the first element). + /// Fact pages are never rewritten, so `save()` extends this instead of + /// re-reading them; `None` (or a stale `n`) falls back to a full pass (#315). + fact_prefix_crc: Option<(u64, Hasher)>, +``` + +and `fact_prefix_crc: None,` in the constructor literal in `new`. + +- [ ] **Step 4: Add `hash_pages`** and re-express `compute_page_checksum` with it: + +```rust +/// Feed pages `first_page..first_page + num_pages` into `hasher`. +fn hash_pages( + backend: &dyn StorageBackend, + hasher: &mut Hasher, + first_page: u64, + num_pages: u64, +) -> Result<()> { + for i in 0..num_pages { + let page_id = first_page + .checked_add(i) + .ok_or_else(|| err_coded!(ErrorCode::Stg021))?; + hasher.update(&backend.read_page(page_id)?); + } + Ok(()) +} + +fn compute_page_checksum( + backend: &dyn StorageBackend, + first_page: u64, + num_pages: u64, +) -> Result { + let mut hasher = Hasher::new(); + hash_pages(backend, &mut hasher, first_page, num_pages)?; + Ok(hasher.finalize()) +} +``` + +- [ ] **Step 5: Capture the prefix in `load()`.** In the `needs_rebuild` block replace + +```rust + let full_checksum = compute_page_checksum(&*backend, 1, total_data_pages)?; + if full_checksum == stored { + false // new-style checksum matches: facts + indexes verified +``` + +with + +```rust + // Hash fact pages, keep that state for save() (#315), then the index pages. + let (full_checksum, fact_prefix) = if total_data_pages >= num_fact_pages { + let mut hasher = Hasher::new(); + hash_pages(&*backend, &mut hasher, 1, num_fact_pages)?; + let prefix = hasher.clone(); + let index_start = num_fact_pages + .checked_add(1) + .ok_or_else(|| err_coded!(ErrorCode::Stg021))?; + hash_pages( + &*backend, + &mut hasher, + index_start, + total_data_pages - num_fact_pages, + )?; + (hasher.finalize(), Some(prefix)) + } else { + (compute_page_checksum(&*backend, 1, total_data_pages)?, None) + }; + if full_checksum == stored { + self.fact_prefix_crc = fact_prefix.map(|p| (num_fact_pages, p)); + false // new-style checksum matches: facts + indexes verified +``` + +(The subtraction is guarded by the `>=` check; add `#[allow(clippy::arithmetic_side_effects)]` only if clippy asks.) + +- [ ] **Step 6: Step A of `save()`** — replace the four `committed_* = stream_all_entries(...)` blocks with raw-leaf snapshots: + +```rust + // Snapshot old B+tree leaves BEFORE writing new pages that may overlap them. + let old_leaves = |root: u64| -> Result>>> { + if root == 0 { + Ok(Vec::new()) + } else { + collect_leaf_pages(root, &*backend, &self.page_cache) + } + }; + let old_eavt = old_leaves(curr_header.eavt_root_page)?; + let old_aevt = old_leaves(curr_header.aevt_root_page)?; + let old_avet = old_leaves(curr_header.avet_root_page)?; + let old_vaet = old_leaves(curr_header.vaet_root_page)?; +``` + +(If the closure's borrow of `backend` conflicts with the later `&mut *backend`, it ends at its last use; if the borrow checker still objects, inline the four `if` expressions.) + +- [ ] **Step 7: Step D of `save()`** — replace the four `*_ser` / `build_btree` pairs with: + +```rust + let (eavt_root, next1) = rebuild_btree_incremental( + old_eavt, + pending_eavt, + &mut *backend, + &self.page_cache, + index_start, + )?; + let (aevt_root, next2) = + rebuild_btree_incremental(old_aevt, pending_aevt, &mut *backend, &self.page_cache, next1)?; + let (avet_root, next3) = + rebuild_btree_incremental(old_avet, pending_avet, &mut *backend, &self.page_cache, next2)?; + let (vaet_root, next4) = + rebuild_btree_incremental(old_vaet, pending_vaet, &mut *backend, &self.page_cache, next3)?; +``` + +- [ ] **Step 8: Checksum in `save()`** — replace + +```rust + let total_data_pages = next4.saturating_sub(1); + let checksum = compute_page_checksum(&*backend, 1, total_data_pages)?; +``` + +with + +```rust + // Fact pages 1..=old count are unchanged since the last save/load, so extend + // the cached CRC state instead of re-reading them (#315). Taking the cache + // means a failed save leaves None and the next save does a full pass. + let mut hasher = match self.fact_prefix_crc.take() { + Some((n, prefix)) if n == old_fact_page_count => { + let mut h = prefix; + hash_pages(&*backend, &mut h, new_fact_start, new_pages_len)?; + h + } + _ => { + let mut h = Hasher::new(); + hash_pages(&*backend, &mut h, 1, new_total_fact_pages)?; + h + } + }; + let new_prefix = hasher.clone(); + hash_pages( + &*backend, + &mut hasher, + index_start, + next4.saturating_sub(index_start), + )?; + let checksum = hasher.finalize(); +``` + +and after `self.committed_fact_pages.store(new_total_fact_pages, ...)` add: + +```rust + self.fact_prefix_crc = Some((new_total_fact_pages, new_prefix)); +``` + +- [ ] **Step 9: Fix imports** — add `collect_leaf_pages, rebuild_btree_incremental` to the `use crate::storage::btree_v6::{...}` list; drop names clippy reports unused in non-test code (e.g. `merge_sorted_vecs`; `stream_all_entries` if only tests use it — then import it inside `mod tests`). + +- [ ] **Step 10: Run the tests** + +Run: `cargo test --lib persistent_facts::` then `cargo test` +Expected: all PASS; total = baseline 1168 + 7 (Task 3) + 4 (this task) = 1179 passing, 8 ignored. + +- [ ] **Step 11: Measure** — `cargo bench --bench minigraf_bench -- checkpoint/after_1_fact`. Expected: substantially below the Task 1 baseline. Also rerun the scratch harness if still present (50k facts target ≤ 15 ms). Record numbers in the task report. + +- [ ] **Step 12: Commit** + +```bash +cargo fmt && cargo clippy --all-targets -- -D warnings +git add src/storage/persistent_facts.rs +git commit -m "perf: checkpoint copies untouched index leaves and skips re-hashing fact pages (#315)" +``` + +--- + +### Task 5: Docs, comment trim, doc sync + +**Files:** +- Modify: `src/db.rs` (`OpenOptions::wal_checkpoint_threshold` field doc ~line 112; `Minigraf::checkpoint` doc ~line 684; `do_checkpoint` guard comment ~lines 730-742) +- Modify: `docs/BENCHMARKS.md`, `CHANGELOG.md`, `CLAUDE.md`, `README.md`, `docs/TEST_COVERAGE.md` + +- [ ] **Step 1: `Minigraf::checkpoint` rustdoc** — replace the first paragraph with: + +```rust + /// Manually trigger a checkpoint: flush all in-memory facts to the main file + /// and delete the WAL sidecar. + /// + /// A checkpoint is **not** a durability boundary: committed writes are already + /// crash-durable in the `.wal` sidecar and are replayed on the next open. + /// Checkpointing less often only makes that replay (reopen) slower. + /// + /// Cost: every checkpoint rewrites the four covering indexes after the fact + /// pages, so it copies pages in proportion to the total index size; only the + /// index leaves that receive new entries are decoded and re-encoded. Prefer + /// checkpointing on a size or time budget over once per logical unit of work. + /// + /// No-op for in-memory databases. +``` + +- [ ] **Step 2: `wal_checkpoint_threshold` field doc** — append: + +```rust + /// + /// A checkpoint's cost grows with the total size of the database (see + /// [`Minigraf::checkpoint`]), while durability does not depend on it: the WAL + /// is crash-durable. Raise this for write-heavy workloads on large graphs. +``` + +- [ ] **Step 3: Trim the `do_checkpoint` guard comment** — replace the paragraph starting "The kernel file lock taken by FileBackend::open…" through "…concurrent writers." with: + +```rust + // Kernel file locking refuses a second writer (another process, or a + // second handle in this one — #304/#314). The guard still matters where + // the filesystem cannot lock and the caller set `allow_unlocked`. +``` + +- [ ] **Step 4: `docs/BENCHMARKS.md`** — add after the "Point Query vs. Version-Chain Depth (#323)" section: + +```markdown +### Checkpoint After One Dirty Fact (#315) + +**Date**: · **Command**: `cargo bench --bench minigraf_bench -- checkpoint/after_1_fact` · same host as above. + +An already-checkpointed file database of `n` facts receives one new fact, then `checkpoint()` runs. "Before" is v2.0.1 behaviour (every index entry decoded and re-encoded); "after" copies untouched index leaves verbatim. + +| Facts | Before | After | +|---:|---:|---:| +| 10k | | | +| 100k | | | + +Cost still grows with graph size (index pages are copied every checkpoint); O(delta) checkpoints need copy-on-write pages and are tracked with #374 for v3.0.0. +``` + +Fill `<…>` with the recorded numbers — no placeholders may remain. + +- [ ] **Step 5: `CHANGELOG.md`** — under `## Unreleased` → `### Performance` (create headings if absent), add: + +```markdown +- **Checkpoints no longer re-encode the whole index (#315).** `checkpoint()` used to decode and re-serialise every entry of all four covering indexes and re-read every page for the file checksum, so checkpointing after one new fact cost as much as after thousands. Index leaves that receive no new entries are now copied verbatim, and unchanged fact pages are not re-hashed. On a 100k-fact file, checkpoint after one fact drops from to . Cost still scales with graph size in page copies; the file format is unchanged. The `checkpoint()` docs now state that a checkpoint is not a durability boundary. +``` + +- [ ] **Step 6: Test counts** — run `cargo test 2>&1 | grep "^test result"` and sum; update `CLAUDE.md` (`**N tests passing** (P passing, 8 ignored…)`), `README.md` (`cargo test # run N tests`), `docs/TEST_COVERAGE.md` (`**Verified**` date, `**Result**` line, and one sentence appended to the suite summary: "Since v2.0.1, incremental B+tree rebuild tests check that checkpoints which copy untouched leaves produce exactly the indexes and checksum a full rebuild would (#315)."). + +- [ ] **Step 7: Verify and commit** + +Run: `cargo test` and `cargo doc --no-deps 2>&1 | grep -i warning` (expect none new) + +```bash +cargo fmt && cargo clippy --all-targets -- -D warnings +git add src/db.rs docs/BENCHMARKS.md CHANGELOG.md CLAUDE.md README.md docs/TEST_COVERAGE.md +git commit -m "docs: checkpoint cost and durability semantics; #315 benchmarks and doc sync" +``` + +- [ ] **Step 8 (at PR time, with the user's go-ahead):** comment on #374 that copy-on-write pages there also own #315's remaining O(size) page-copy term. The PR body uses "Mitigates #315" wording chosen with the user, never a closing keyword for #374. diff --git a/docs/superpowers/specs/2026-09-25-point-query-history-scan-design.md b/docs/superpowers/specs/2026-09-25-point-query-history-scan-design.md new file mode 100644 index 0000000000..6621c10581 --- /dev/null +++ b/docs/superpowers/specs/2026-09-25-point-query-history-scan-design.md @@ -0,0 +1,184 @@ +# Point-query history scan mitigation (#323) — Design + +**Issue:** #323 — point query on a bound entity scans the entity's whole version history +**Milestone:** v2.3.0 (`main`, file format v7 — no format change) +**Follow-up:** structural O(live) fix on the `v3` branch (separate issue, see §6) + +## 1. Problem + +`[:e/x :attr ?v]` costs O(every record ever written for `:e/x`), not O(live facts). +An entity whose attribute is retracted and reasserted N times gets ~N× slower to read. +Downstream (temporal_reasoning#239) this is ~⅓ of ingestion wall clock. Attribute-only +scans (`[?e :attr ?v]`) show the same history-bound behaviour. + +Reproduced locally (2000 filler facts, checkpointed, median of 20): + +| depth | `[:e/hot :hash ?v]` | `[:e/hot :other ?v]` | `[?e :hash ?v]` | +|---:|---:|---:|---:| +| 1 | 0.026 ms | 0.024 ms | 0.022 ms | +| 500 | 1.769 ms | 1.749 ms | 1.688 ms | +| 2000 | 7.156 ms | 7.250 ms | 7.067 ms | + +`:other` is written once and never churned, yet costs the same as `:hash`: the scan is +entity-wide, not attribute-wide. + +## 2. Where the time goes + +`perf` at depth 2000 (4001 EAVT records for the entity): + +| component | share | +|---|---:| +| `net_asserted_facts` — SipHash on cloned `(Uuid, String, Vec, i64, i64)` keys | ~40% | +| `get_facts_by_entity` — `resolve_fact_ref` + postcard decode per record | ~30% | +| `selective_fact_fetch` dedup `HashSet<(Uuid, String, u64, bool)>` (redundant — §4.2) | ~16% | + +It is CPU overhead per dead record, not I/O. + +**Why v2 cannot be O(live):** v7 `EavtKey`/`AevtKey` carry neither the value nor the +`asserted` flag. Deciding whether a record is live requires knowing its `(e, a, v)` and +whether a later retraction of that `v` exists — only obtainable by resolving the record. +Retraction records also have their own validity window (`[tx_id, ∞)`), so key-level +valid-time pruning cannot safely discard them. v2 can therefore only shrink the constant +and narrow the scan to the queried attribute. + +## 3. Goals / non-goals + +**Goals** +- Other attributes on a churned entity no longer pay for that entity's churn. +- Constant factor per history record cut on the churned attribute itself (original target ≥3×; + revised to the measured ~1.6× — see §5 Acceptance). +- The attribute-scan and full-scan paths benefit from the cheaper `net_asserted_facts`. +- Zero change to query results, file format, public API, or dependencies. + +**Non-goals** +- O(live) resolve cost (needs v8 keys — §6). +- Changes to `retract`/`transact` write paths. +- Changes to the `:as-of` path beyond the shared `net_asserted_facts` speed-up. + +## 4. Design + +### 4.1 Attribute-narrowed entity scan + +**Storage** (`src/graph/storage.rs`): new production method + +```rust +pub(crate) fn get_facts_by_entity_attribute_indexed( + &self, entity_id: &EntityId, attribute: &Attribute, +) -> Result> +``` + +- EAVT range `[(e, a, i64::MIN, i64::MIN, 0), (e, next_string_prefix(a), i64::MIN, i64::MIN, 0))`. + If `next_string_prefix` returns `None`, upper bound is `(e+1, "", …)` and results are + filtered by `key.attribute == a`. +- Pending (in-memory `BTreeMap`) and committed (`range_scan_eavt`) merged exactly as + `get_facts_by_entity` does; both paths post-filter `attribute == a` so prefix-sharing + attributes (`:a` vs `:ab`) never leak. +- No-index fallback: filter `d.facts` / `loader.stream_all()` on entity **and** attribute. +- The existing `#[cfg(test)] get_facts_by_entity_attribute` (full-scan) helper stays as is. + +**Executor** (`selective_fact_fetch` in `src/query/datalog/executor.rs`): + +- Replace `entity_ids: HashSet` with `entity_attrs: HashMap>>`. + - Pattern with bound entity and `AttributeSpec::Real(EdnValue::Keyword(a))` → add `a` + to that entity's set (unless it is already `None`). + - Pattern with bound entity and any other attribute (variable, pseudo-attribute) → + set that entity to `None` (whole-entity scan). +- Narrowed lookup count = Σ over entities of (1 if `None` else number of attributes) + + number of attribute-only lookups. If it exceeds the existing `threshold` (4), every + entity collapses back to one whole-entity scan (today's behaviour) and the count is + recomputed; only if *that* still exceeds the threshold → `None` (full scan), as today. + This guarantees narrowing never turns a query that used the selective path into a + full scan (e.g. five attributes of one bound entity). +- Fetch `get_facts_by_entity` for `None` entries and + `get_facts_by_entity_attribute_indexed` per `(e, a)` otherwise. + +**Correctness argument:** `net_asserted_facts` groups by `(e, a, v)` and the valid-time +filter is per-fact, so restricting input to one `(e, a)` never splits a group. +`collect_all_patterns` already includes patterns inside `not`, `not-join`, `or`, +`or-join`, so every attribute any clause could match on that entity is fetched. +Rule-using queries never reach this path. + +### 4.2 Remove the executor dedup + +`selective_fact_fetch` has exactly one caller, `filter_facts_for_query`, which passes its +output straight into `net_asserted_facts`. That function is idempotent under duplicated +input records: an identical assertion lands in the same `(e, a, v, valid_from, valid_to)` +window and the first one wins the tie; a duplicated retraction leaves the per-`(e, a, v)` +max `tx_count` unchanged. So the `seen: HashSet<(Uuid, String, u64, bool)>` pass is +redundant and is deleted. It cannot simply be skipped "for single-source lookups" instead: +between `set_committed_index_reader` and `post_checkpoint_clear` a concurrent reader can +see a fact in both the pending and the committed index. The idempotence is pinned by a +unit test (§5) so a future change to `net_asserted_facts` cannot silently break it. + +### 4.3 Cheaper `net_asserted_facts` + +- ~~Add a small in-crate FxHash-style hasher.~~ **Dropped after final review + (2026-09-26):** a fixed-seed fast hash lets crafted colliding values (untrusted text in + agent memory) make every query quadratic. It bought ~13%; the maps keep std's randomly + keyed `RandomState`. +- Restructure `net_asserted_facts` so each fact's value is encoded once and group keys + borrow from the input rather than cloning `attribute`/`value_bytes` into every key: + 1. `encoded: Vec> = facts.iter().map(|f| encode_value(&f.value)).collect()`. + 2. `max_retract_tx: HashMap<(&Uuid, &str, &[u8]), u64>`. + 3. `by_window: HashMap<(&Uuid, &str, &[u8], i64, i64), (usize, u64)>` storing the + index of the winning assertion. + 4. Collect surviving indices, then move the winning facts out of `facts` + (e.g. mark survivors in a `Vec` and `into_iter().zip(...).filter`). +- Output **order**: callers must not depend on it today (current output is HashMap + iteration order). Tests that compare results already sort or use sets; verify during + implementation. +- HashDoS: fact values can be untrusted text, so hashing stays randomly keyed (see above). + +## 5. Testing + +TDD; correctness first, then measurement. + +**Storage unit tests** (`src/graph/storage.rs`), for `get_facts_by_entity_attribute_indexed`: +- pending-only, committed-only, pending+committed after checkpoint; +- no-index fallback path; +- `:a` vs `:ab` prefix isolation; +- other entities / other attributes excluded. + +**`net_asserted_facts` tests**: existing tests keep passing; add a duplicate-idempotence +test (`net_asserted_facts(xs ++ dup) == net_asserted_facts(xs)` as sorted sets); add a property-style test +comparing the new implementation against the old one (kept as a `#[cfg(test)]` reference +function) on randomized assert/retract sequences incl. multiple windows, same-tx +assert+retract, and multi-valued attributes — compared as sorted sets. + +**Executor integration tests** (`tests/point_query_history_test.rs`, new): +- churned attribute returns exactly the live value after N retract/reassert cycles + (in-memory and file-backed, before and after checkpoint); +- `[:e :a ?x] [:e :b ?y]` on one entity (two narrowed ranges, dedup path); +- bound entity with variable attribute `[:e ?a ?v]` (whole-entity fallback); +- bound entity with pseudo-attribute under `:any-valid-time`; +- `not` / `not-join` / `or` referencing another attribute of the same bound entity; +- entity + attribute-only pattern mix exceeding threshold → full-scan path, same results; +- `:valid-at` past timestamp on a churned attribute. + +All assert messages follow the CLAUDE.md testing convention (no `{:?}` of UUID-bearing types). + +**Benchmark** (`benches/minigraf_bench.rs`): `point_query_chain_depth/{1,500,2000}` for +`[:e/hot :hash ?v]`, `[:e/hot :other ?v]`, `[?e :hash ?v]` on a checkpointed file DB. +Record before/after numbers in the PR and `docs/BENCHMARKS.md`. + +**Acceptance:** +- `[:e/hot :other ?v]` at depth 2000 within 2× of depth 1. **Met**: 19.0 µs vs 19.2 µs. +- `[:e/hot :hash ?v]` and `[?e :hash ?v]` at depth 2000 faster than baseline. Original + target ≥3×; **measured 1.38× / 1.35×** (criterion on AC, bench profile with LTO and + `opt-level = "z"`: 4.64 → 3.36 ms, 4.49 → 3.33 ms; 1.6× with the dropped FxHash). + Revised to the measured numbers on 2026-09-26 and shipped as a mitigation. The remaining + cost is mostly per-record fact resolve + decode and EAVT leaf-key decode — inherent to + v7 keys; see §6 / #379. +- Full suite green; clippy/fmt clean. + +## 6. Follow-up: v3 structural fix (#379, milestone v3.0.0) + +v8 `EavtKey`/`AevtKey` (on `v3`) carry `value_bytes` and `asserted`. Net-assert can then be +computed over index keys *before* `resolve_fact_ref`, resolving only surviving records: +resolve cost O(live), key walk O(history) but on leaf pages already in cache. File as a +new issue referencing #323; not part of this change. + +## 7. Docs + +On merge: `CHANGELOG.md` (Unreleased → Performance), `docs/BENCHMARKS.md`, +`docs/TEST_COVERAGE.md` + `CLAUDE.md` test count. No wiki or file-format docs change. diff --git a/docs/superpowers/specs/2026-09-26-incremental-checkpoint-design.md b/docs/superpowers/specs/2026-09-26-incremental-checkpoint-design.md new file mode 100644 index 0000000000..5c6bf4fa0d --- /dev/null +++ b/docs/superpowers/specs/2026-09-26-incremental-checkpoint-design.md @@ -0,0 +1,175 @@ +# Incremental checkpoint index rebuild (#315) — Design + +**Issue:** #315 — `checkpoint()` is O(graph size) and flat in dirty bytes +**Milestone:** v2.3.0 (`main`, file format v7 — no format change) +**Follow-up:** true O(delta) checkpoints move to #374 on the `v3` branch (see §7) + +## 1. Problem + +Every `checkpoint()` streams all four covering indexes (EAVT/AEVT/AVET/VAET) off +disk, decodes every entry, merges in the pending entries, re-serialises everything +and bulk-builds four new B+trees. Cost scales with total graph size, not with the +number of dirty facts. Downstream (temporal_reasoning#241) this was ~half of +at-scale ingestion wall clock. The default `wal_checkpoint_threshold` (1000) makes +every default user pay `N_checkpoints × graph_size`. + +Reproduced locally (50k facts, 13 MB, checkpoint after **one** new fact, mean of 20): +**~80 ms**. + +## 2. Where the time goes + +Phase timing of `PersistentFactStorage::save` (tmpfs, same harness): + +| phase | ms | +|---|---:| +| merge + serialise + `build_btree` (Step D) | ~58 | +| `stream_all_entries` × 4 (Step A) | ~19 | +| full-file CRC re-read | ~3.5 | +| pack facts + fsyncs | <1 (a few ms on NVMe) | + +The cost is CPU in decode/re-encode of every index entry, not I/O. + +## 3. Why true O(delta) is out of scope here + +In format v7, fact pages must be contiguous at pages `1..=fact_page_count` +(`read_all_with_refs`, `CommittedFactLoaderImpl::first_fact_page`), and indexes live +directly after them. New fact pages therefore always overwrite the start of the old +index region, so every checkpoint must relocate the index. Avoiding that needs +copy-on-write B+trees plus free-space management — a format change, and the same +change #374 (save() is not crash-atomic) requires. That work belongs on `v3`. + +Dropping the unconditional `force_dirty()` (issue option 2) does not help: with one +dirty fact `dirty` is already true, and the zero-dirty case is already short-circuited +by the `wal_entry_count == 0 && !pfs.is_dirty()` guard. + +## 4. Design + +### 4.1 Leaf reuse — `src/storage/btree_v6.rs` + +`btree_v6.rs` is the B+tree for both v6 and v7 (v7 changed only the header). The +node layout is unchanged by this design, so v2.x readers are unaffected. + +New function: + +```rust +pub fn rebuild_btree_incremental( + old_leaves: Vec>>, // raw leaf pages of the old tree, in next_leaf order + pending: Vec<(K, FactRef)>, // sorted + backend: &mut dyn StorageBackend, + cache: &PageCache, + start_page_id: u64, +) -> Result<(u64, u64)> // (root_page_id, next_free_page_id) +where K: Serialize + for<'de> Deserialize<'de> + Ord +``` + +Algorithm: + +1. For each old leaf decode **only the first entry's key** → `first_key[i]`. +2. Route each pending entry to leaf `i` where `first_key[i] ≤ key < first_key[i+1]`; + keys below `first_key[0]` go to leaf 0. +3. Leaf with no pending entries → **raw copy**: write the 4 KB page verbatim to the + next page id, patching only bytes 4..12 (`next_leaf`). No decode/encode. +4. Leaf with pending entries → decode all its entries, merge with its pending + entries and serialise. If the result fits in one physical page it stays one + leaf; otherwise it splits into pages of at most `PAGE_FILL_BYTES`, balanced by + size (classic B+tree split). *Revised during implementation:* repacking with + `build_btree`'s "fill to 75%, then start a new leaf" rule left a near-empty + leaf on every checkpoint that inserted into a full leaf (43 → 596 leaves after + 600 single-fact checkpoints), so cost drifted upward with checkpoint count. +5. Leaves are written in order with `next_leaf = pid + 1` (0 for the last), so there + is no second patch pass. +6. Collect `(page_id, first_key_bytes)` per new leaf (postcard of the first key) and + build internal levels bottom-up via a helper **extracted from `build_btree`'s + phase 2** (`build_internal_levels`), shared by both paths. + +`build_btree` remains the path for the first save, for an empty or missing old tree +(root 0 or a single empty leaf), and for load-time index rebuild / migrations. + +Collecting raw leaves: `collect_leaf_pages(root, backend, cache) -> Vec>>` +walks `find_leftmost_leaf` + the `next_leaf` chain, validating page type as +`stream_all_entries` does. + +Leaf fill: untouched leaves keep their existing fill; touched leaves stay between +roughly 37% and 100% full. The tree shape differs from a fresh bulk build but is a +valid B+tree for `range_scan` / `stream_all_entries` / `find_leaf_for_key`. No +merging of under-filled neighbours (inserts only; nothing is ever removed from an +index). + +### 4.2 `save()` ordering — `src/storage/persistent_facts.rs` + +Step A reads the raw leaf pages of all four old trees into memory **before** any +write (new fact pages overwrite the start of the old index region). This replaces +the decoded `Vec<(K, FactRef)>` streams; memory drops (raw pages ≤ decoded entries ++ serialised copies held today). + +Step D calls `rebuild_btree_incremental` per index when the old root is non-zero, +otherwise `build_btree` as today. + +Crash semantics are unchanged: the WAL is only deleted after the header write, and a +checksum mismatch on open rebuilds indexes from fact pages (#370 path). #374 remains +the real fix for atomicity. + +### 4.3 Checksum prefix cache + +`PersistentFactStorage` gains `fact_prefix_crc: Option` — CRC32 +state after hashing fact pages `1..=committed_fact_pages`. + +- **Set** in `load()`: the existing full-checksum pass is split into fact pages then + index pages; the hasher is cloned between the two segments. Only set when the + new-style full checksum matched. +- **Set** at the end of `save()`: prefix + the new fact pages (hashed from the + in-memory page buffers). +- **Cleared (None)** on any other path that rewrites the header/indexes (index + rebuild in `load()`, legacy/v5 migrations). +- **Use** in `save()`: clone the prefix, update with the new fact pages from memory, + then read back and hash only the index pages. `None` → today's full pass. + +The stored `index_checksum` value is identical to today's (CRC over pages +`1..page_count`), so older v2.x readers verify it unchanged. + +### 4.4 Docs and cleanup + +- `Minigraf::checkpoint` rustdoc: cost is O(graph size) page copies plus O(delta) + decode; checkpoint is **not** a durability boundary (the WAL is crash-durable); + batching trades only reopen latency (WAL replay). +- Same note on `OpenOptions::wal_checkpoint_threshold`. +- Trim the obsolete "same-process double-opens" rationale in `do_checkpoint`'s + guard comment (now refused outright since #304/#314). +- At release: `CHANGELOG.md`, `ROADMAP.md`, `docs/BENCHMARKS.md`, + `docs/TEST_COVERAGE.md`, `CLAUDE.md` test count. + +## 5. Testing + +No new dependencies; deterministic seeded loops. + +- **Equivalence (unit, `btree_v6.rs`):** for random committed sets and random + pending batches (including batches that force leaf splits, keys below the first + leaf, keys after the last leaf, and many pending entries in one leaf), + `stream_all_entries` of the incremental tree equals the merged sorted set. +- **Structure:** `next_leaf` chain is strictly ascending across leaves; `range_scan` + over random bounds matches a filter over the expected set. +- **Multi-checkpoint (`persistent_facts.rs`):** many save cycles on a file backend; + after each, all four indexes stream equal to a from-scratch build over all facts. +- **Checksum:** after incremental saves `header.index_checksum == + compute_page_checksum(1, page_count-1)`; reopening does not take the rebuild path. + Prefix cache is `None` after a rebuild/migration path and a subsequent save still + writes a correct checksum. +- **Regression:** full existing suite. +- **Benchmark:** new `checkpoint/after_1_fact` group (10k / 100k facts) in + `benches/minigraf_bench.rs`; before/after numbers in `docs/BENCHMARKS.md`. + +Test assert messages follow the CodeQL rule (no `{:?}` of UUID-bearing types). + +## 6. Success criteria + +- 50k facts, checkpoint after 1 fact: ~80 ms → **≤ 15 ms** on the §1 harness. +- No file-format or public-API change; files written by the new code open without + index rebuild on v2.0.1. +- All existing tests pass. + +## 7. Follow-up + +Comment on #374 (v3.0.0): copy-on-write B+tree pages with a free list make save() +crash-atomic **and** give O(delta · log n) checkpoints; #315's remaining O(size) +page-copy term is owned there. #315 is closed by this work as mitigated, not fully +resolved (no closing keyword on #374). diff --git a/src/db.rs b/src/db.rs index 4d0a4c4b6b..eb1dc65480 100644 --- a/src/db.rs +++ b/src/db.rs @@ -113,6 +113,10 @@ pub struct OpenOptions { /// /// Defaults to 1000. Lower values mean more frequent checkpoints (smaller WAL, /// more I/O). Higher values mean less frequent checkpoints (larger WAL, less I/O). + /// + /// A checkpoint's cost grows with the total size of the database (see + /// [`Minigraf::checkpoint`]), while durability does not depend on it: the WAL + /// is crash-durable. Raise this for write-heavy workloads on large graphs. pub wal_checkpoint_threshold: usize, /// Number of pages to hold in the LRU page cache. Default: 256 (= 1MB at 4KB pages). /// @@ -684,6 +688,15 @@ impl Minigraf { /// Manually trigger a checkpoint: flush all in-memory facts to the main file /// and delete the WAL sidecar. /// + /// A checkpoint is **not** a durability boundary: committed writes are already + /// crash-durable in the `.wal` sidecar and are replayed on the next open. + /// Checkpointing less often only makes that replay (reopen) slower. + /// + /// Cost: every checkpoint rewrites the four covering indexes after the fact + /// pages, so it copies pages in proportion to the total index size; only the + /// index leaves that receive new entries are decoded and re-encoded. Prefer + /// checkpointing on a size or time budget over once per logical unit of work. + /// /// No-op for in-memory databases. /// /// # Errors @@ -733,13 +746,10 @@ impl Minigraf { // replayed WAL entries on open (crash-recovery path). `pfs.is_dirty()` // catches any facts marked dirty via the normal write path. // - // The kernel file lock taken by FileBackend::open covers both a - // second process and a second handle in this one, since flock - // and OFD locks attach to the open file description. This guard - // remains for environments where the filesystem cannot lock at all — - // for example, NFSv3 without lockd or some FUSE mounts — where the - // caller set `allow_unlocked` to accept that Minigraf cannot detect - // concurrent writers. + // Kernel file locking refuses a second writer (another process, or a + // second handle in this one — #304/#314). The guard still matters where + // the filesystem cannot lock (e.g. NFSv3 without lockd, some FUSE + // mounts) and the caller set `allow_unlocked`. if *wal_entry_count == 0 && !pfs.is_dirty() { return Ok(()); } diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 6935515976..97fd70877f 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -512,70 +512,68 @@ pub(crate) fn filter_facts_as_of(facts: Vec, as_of: &AsOf) -> Vec { /// /// # Implementation note /// -/// This function uses two flat `HashMap`s in a single pass over the input: +/// Hot path for every non-`:as-of` query (#323). Each value is encoded once; +/// the two group maps borrow `(entity, attribute, value_bytes)` from the input +/// instead of cloning them. They keep std's randomly keyed hasher on purpose: +/// values are often untrusted text (agent memory), and a fixed-seed fast hash +/// would let crafted colliding values make every query quadratic. `by_window` stores the +/// index and `tx_count` of the winning assertion per validity window; survivors +/// are moved out of `facts` at the end, preserving input order. /// -/// - `max_retract_tx`: EAV → highest retraction `tx_count` seen so far. -/// - `by_window`: (EAV + valid_from + valid_to) → highest-`tx_count` assertion -/// for that time window. -/// -/// The retraction filter (`fact.tx_count > max_retract_tx`) is applied in the -/// final `filter_map` rather than eagerly. This means `by_window` temporarily -/// holds assertions that will be filtered out, so on workloads where most -/// EAV triples are immediately retracted it uses more peak memory than the -/// previous per-group approach. The trade-off is intentional: eliminating the -/// per-group `Vec` allocation yields a measurable throughput gain on large -/// mostly-unique fact sets (see issue #227). +/// Idempotent under duplicated input records (a duplicate assertion ties with +/// the original and loses; a duplicate retraction leaves the max unchanged). +/// `selective_fact_fetch` relies on this instead of deduplicating. pub(crate) fn net_asserted_facts(facts: Vec) -> Vec { use std::collections::HashMap; - type EavKey = (EntityId, Attribute, Vec); - type WindowKey = (EntityId, Attribute, Vec, i64, i64); - - let mut max_retract_tx: HashMap = HashMap::new(); - let mut by_window: HashMap = HashMap::new(); - - for fact in facts { - let eav_key = ( - fact.entity, - fact.attribute.clone(), - encode_value(&fact.value), - ); - - if fact.asserted { - let window_key = ( - eav_key.0, - eav_key.1, - eav_key.2, - fact.valid_from, - fact.valid_to, - ); - match by_window.get(&window_key) { - None => { - by_window.insert(window_key, fact); - } - Some(existing) if fact.tx_count > existing.tx_count => { - by_window.insert(window_key, fact); - } - _ => {} + type EavKey<'a> = (&'a EntityId, &'a str, &'a [u8]); + type WindowKey<'a> = (&'a EntityId, &'a str, &'a [u8], i64, i64); + + let encoded: Vec> = facts.iter().map(|f| encode_value(&f.value)).collect(); + let mut keep = vec![false; facts.len()]; + + { + let mut max_retract_tx: HashMap, u64> = HashMap::new(); + let mut by_window: HashMap, (usize, u64)> = HashMap::new(); + + for (idx, (fact, value_bytes)) in facts.iter().zip(encoded.iter()).enumerate() { + let entity = &fact.entity; + let attribute = fact.attribute.as_str(); + let value = value_bytes.as_slice(); + if fact.asserted { + by_window + .entry((entity, attribute, value, fact.valid_from, fact.valid_to)) + .and_modify(|winner| { + if fact.tx_count > winner.1 { + *winner = (idx, fact.tx_count); + } + }) + .or_insert((idx, fact.tx_count)); + } else { + max_retract_tx + .entry((entity, attribute, value)) + .and_modify(|max_tx| *max_tx = (*max_tx).max(fact.tx_count)) + .or_insert(fact.tx_count); } - } else { - let tx_count = fact.tx_count; - max_retract_tx - .entry(eav_key) - .and_modify(|max_tx| *max_tx = (*max_tx).max(tx_count)) - .or_insert(tx_count); } - } - by_window - .into_iter() - .filter_map(|((entity, attribute, value, _, _), fact)| { + for ((entity, attribute, value, _, _), (idx, tx_count)) in &by_window { let retract_tx = max_retract_tx - .get(&(entity, attribute, value)) + .get(&(*entity, *attribute, *value)) .copied() .unwrap_or(0); - (fact.tx_count > retract_tx).then_some(fact) - }) + if *tx_count > retract_tx + && let Some(slot) = keep.get_mut(*idx) + { + *slot = true; + } + } + } + + facts + .into_iter() + .zip(keep) + .filter_map(|(fact, kept)| kept.then_some(fact)) .collect() } @@ -597,23 +595,6 @@ fn resolve_fact_ref(d: &FactData, fr: FactRef) -> Result { } } -/// Increment the last byte of a string for prefix upper-bound construction. -/// Returns `None` if all bytes are 0xFF (true unbounded scan needed). -/// Used by the production index-driven lookup methods (`get_facts_by_attribute`). -fn next_string_prefix(s: &str) -> Option { - let mut bytes = s.as_bytes().to_vec(); - for i in (0..bytes.len()).rev() { - if let Some(b) = bytes.get_mut(i) - && *b < 0xFF - { - *b += 1; - bytes.truncate(i + 1); - return String::from_utf8(bytes).ok(); - } - } - None -} - /// Production helpers on FactStorage: index-driven entity/attribute lookups used by the query executor. impl FactStorage { /// Get all facts for a specific entity (index-driven). @@ -672,6 +653,61 @@ impl FactStorage { Ok(facts) } + /// Get every stored record for one `(entity, attribute)` pair (index-driven, #323). + /// + /// Range-scans EAVT over exactly `[(e, a, …), (e, a + "\0", …))`, so other + /// attributes of the same entity — including prefix siblings such as `:ab` for + /// `:a` — and their version history are never resolved. + pub(crate) fn get_facts_by_entity_attribute_indexed( + &self, + entity_id: &EntityId, + attribute: &Attribute, + ) -> Result> { + use crate::storage::index::EavtKey; + let d = self.data.read().unwrap_or_else(|e| e.into_inner()); + let matches = |f: &Fact| &f.entity == entity_id && &f.attribute == attribute; + + // Fallback: no indexes built yet + if d.pending_indexes.eavt.is_empty() && d.committed_index_reader.is_none() { + let mut result: Vec = d.facts.iter().filter(|f| matches(f)).cloned().collect(); + if let Some(loader) = &d.committed { + result.extend(loader.stream_all()?.into_iter().filter(|f| matches(f))); + } + return Ok(result); + } + + let start = EavtKey::entity_attribute_start(*entity_id, attribute); + // Exact successor of `attribute`: the smallest string that sorts after it is + // `attribute + "\0"`, so `[start, end)` holds exactly this (e, a) pair. Always + // valid UTF-8 — unlike incrementing the last byte, which fails for attributes + // ending in 0x7F or a character whose last UTF-8 byte is 0xBF (e.g. `:丿`). + let end = EavtKey::entity_attribute_start(*entity_id, &format!("{attribute}\0")); + + let mut facts = Vec::new(); + + // Pending: EAVT keys for the exact (e, a) are contiguous from `start`; + // the first key with a different entity or attribute ends the run. + for (key, &fr) in d.pending_indexes.eavt.range(start.clone()..) { + if key.entity != *entity_id || key.attribute != *attribute { + break; + } + facts.push(resolve_fact_ref(&d, fr)?); + } + + // Committed: on-disk B+tree range scan over exactly this (e, a) pair; the + // post-filter is a cheap guard, not something the range relies on. + if let Some(reader) = &d.committed_index_reader { + for fr in reader.range_scan_eavt(&start, Some(&end))? { + let fact = resolve_fact_ref(&d, fr)?; + if matches(&fact) { + facts.push(fact); + } + } + } + + Ok(facts) + } + /// Get all facts for a specific attribute (index-driven). pub(crate) fn get_facts_by_attribute(&self, attribute: &Attribute) -> Result> { use crate::storage::index::AevtKey; @@ -688,36 +724,22 @@ impl FactStorage { } let start = AevtKey::attribute_start(attribute); - let end_opt: Option = - next_string_prefix(attribute).map(|next_attr| AevtKey::attribute_start(&next_attr)); + // Exact successor of `attribute` (see `get_facts_by_entity_attribute_indexed`): + // `[start, end)` holds exactly this attribute, never prefix siblings such as + // `:ab` for `:a`, and is valid UTF-8 for any attribute (#381). + let end = AevtKey::attribute_start(&format!("{attribute}\0")); let mut facts = Vec::new(); - // Pending - let pending_range: Vec = match &end_opt { - Some(end) => d - .pending_indexes - .aevt - .range(start.clone()..end.clone()) - .filter(|(k, _)| k.attribute == *attribute) - .map(|(_, &r)| r) - .collect(), - None => d - .pending_indexes - .aevt - .range(start.clone()..) - .take_while(|(k, _)| k.attribute == *attribute) - .map(|(_, &r)| r) - .collect(), - }; - for fr in pending_range { + // Pending: AEVT keys for the exact attribute are contiguous from `start`. + for (_, &fr) in d.pending_indexes.aevt.range(start.clone()..end.clone()) { facts.push(resolve_fact_ref(&d, fr)?); } - // Committed + // Committed: on-disk B+tree range scan over exactly this attribute; the + // post-filter is a cheap guard, not something the range relies on. if let Some(reader) = &d.committed_index_reader { - let committed_refs = reader.range_scan_aevt(&start, end_opt.as_ref())?; - for fr in committed_refs { + for fr in reader.range_scan_aevt(&start, Some(&end))? { let fact = resolve_fact_ref(&d, fr)?; if &fact.attribute == attribute { facts.push(fact); @@ -1870,4 +1892,495 @@ mod tests { "retraction should wipe all windows for the EAV triple" ); } + + /// Pre-#323 implementation, kept verbatim as the oracle for the + /// randomized equivalence test. + fn net_asserted_facts_reference(facts: Vec) -> Vec { + use std::collections::HashMap; + + type EavKey = (EntityId, Attribute, Vec); + type WindowKey = (EntityId, Attribute, Vec, i64, i64); + + let mut max_retract_tx: HashMap = HashMap::new(); + let mut by_window: HashMap = HashMap::new(); + + for fact in facts { + let eav_key = ( + fact.entity, + fact.attribute.clone(), + encode_value(&fact.value), + ); + + if fact.asserted { + let window_key = ( + eav_key.0, + eav_key.1, + eav_key.2, + fact.valid_from, + fact.valid_to, + ); + match by_window.get(&window_key) { + None => { + by_window.insert(window_key, fact); + } + Some(existing) if fact.tx_count > existing.tx_count => { + by_window.insert(window_key, fact); + } + _ => {} + } + } else { + let tx_count = fact.tx_count; + max_retract_tx + .entry(eav_key) + .and_modify(|max_tx| *max_tx = (*max_tx).max(tx_count)) + .or_insert(tx_count); + } + } + + by_window + .into_iter() + .filter_map(|((entity, attribute, value, _, _), fact)| { + let retract_tx = max_retract_tx + .get(&(entity, attribute, value)) + .copied() + .unwrap_or(0); + (fact.tx_count > retract_tx).then_some(fact) + }) + .collect() + } + + /// Order-independent comparison key for a fact set. + fn sorted_keys(facts: &[Fact]) -> Vec { + let mut v: Vec = facts + .iter() + .map(|f| { + format!( + "{}|{}|{:?}|{}|{}|{}|{}", + f.entity, + f.attribute, + f.value, + f.tx_count, + f.valid_from, + f.valid_to, + f.asserted + ) + }) + .collect(); + v.sort(); + v + } + + /// Deterministic xorshift so the test needs no RNG dependency. + struct XorShift(u64); + impl XorShift { + fn next(&mut self) -> u64 { + let mut x = self.0; + x ^= x << 13; + x ^= x >> 7; + x ^= x << 17; + self.0 = x; + x + } + fn below(&mut self, n: u64) -> u64 { + self.next() % n + } + } + + #[test] + fn net_asserted_matches_reference_on_random_histories() { + let entities = [uuid::Uuid::from_u128(1), uuid::Uuid::from_u128(2)]; + let attrs = [":a", ":ab", ":b"]; + let windows = [ + (0_i64, VALID_TIME_FOREVER), + (1_000, 2_000), + (1_500, VALID_TIME_FOREVER), + ]; + let mut rng = XorShift(0x9E37_79B9_7F4A_7C15); + for _case in 0..500 { + let n = rng.below(40) + 1; + let mut facts = Vec::new(); + let mut tx = 0_u64; + for _ in 0..n { + // ~25% of records share the previous tx_count (same-transaction batches). + if rng.below(4) != 0 { + tx += 1; + } + let e = entities[rng.below(2) as usize]; + let a = attrs[rng.below(3) as usize]; + let v = Value::Integer(i64::try_from(rng.below(3)).unwrap()); + if rng.below(3) == 0 { + facts.push(make_retract(e, a, v, tx)); + } else { + let (vf, vt) = windows[rng.below(3) as usize]; + facts.push(make_assert(e, a, v, tx, vf, vt)); + } + } + let expected = sorted_keys(&net_asserted_facts_reference(facts.clone())); + let actual = sorted_keys(&net_asserted_facts(facts)); + assert_eq!( + actual, expected, + "new net_asserted_facts diverged from reference" + ); + } + } + + /// The executor's selective fetch no longer dedups (#323); it relies on + /// net_asserted_facts collapsing duplicated input records. + #[test] + fn net_asserted_idempotent_under_duplicates() { + let e = uuid::Uuid::from_u128(7); + let facts = vec![ + make_assert( + e, + ":hash", + Value::String("h0".into()), + 1, + 0, + VALID_TIME_FOREVER, + ), + make_retract(e, ":hash", Value::String("h0".into()), 2), + make_assert( + e, + ":hash", + Value::String("h1".into()), + 3, + 0, + VALID_TIME_FOREVER, + ), + make_assert( + e, + ":other", + Value::String("o".into()), + 3, + 0, + VALID_TIME_FOREVER, + ), + ]; + let mut doubled = facts.clone(); + doubled.extend(facts.clone()); + let once = sorted_keys(&net_asserted_facts(facts)); + let twice = sorted_keys(&net_asserted_facts(doubled)); + assert_eq!(once.len(), 2, "h1 and o are live"); + assert_eq!(twice, once, "duplicated records must not change the result"); + } + + #[test] + fn net_asserted_preserves_input_order() { + let e = uuid::Uuid::from_u128(9); + let facts = vec![ + make_assert(e, ":z", Value::Integer(1), 1, 0, VALID_TIME_FOREVER), + make_assert(e, ":a", Value::Integer(2), 2, 0, VALID_TIME_FOREVER), + make_assert(e, ":m", Value::Integer(3), 3, 0, VALID_TIME_FOREVER), + ]; + let out = net_asserted_facts(facts); + let attrs: Vec<&str> = out.iter().map(|f| f.attribute.as_str()).collect(); + assert_eq!(attrs, vec![":z", ":a", ":m"]); + } + + #[test] + fn entity_attribute_indexed_pending_only() { + let storage = FactStorage::new(); + let e = uuid::Uuid::from_u128(1); + let other = uuid::Uuid::from_u128(2); + storage + .transact( + vec![ + (e, ":hash".to_string(), Value::String("h0".into())), + (e, ":other".to_string(), Value::String("o".into())), + (other, ":hash".to_string(), Value::String("x".into())), + ], + None, + ) + .unwrap(); + storage + .retract(vec![(e, ":hash".to_string(), Value::String("h0".into()))]) + .unwrap(); + let facts = storage + .get_facts_by_entity_attribute_indexed(&e, &":hash".to_string()) + .unwrap(); + assert_eq!(facts.len(), 2, "assert + retract of :hash for e only"); + assert!( + facts + .iter() + .all(|f| f.entity == e && f.attribute == ":hash") + ); + } + + #[test] + fn entity_attribute_indexed_excludes_prefix_sibling() { + let storage = FactStorage::new(); + let e = uuid::Uuid::from_u128(1); + storage + .transact( + vec![ + (e, ":a".to_string(), Value::Integer(1)), + (e, ":ab".to_string(), Value::Integer(2)), + (e, ":a/b".to_string(), Value::Integer(3)), + ], + None, + ) + .unwrap(); + let facts = storage + .get_facts_by_entity_attribute_indexed(&e, &":a".to_string()) + .unwrap(); + assert_eq!(facts.len(), 1, "only :a, not :ab or :a/b"); + assert_eq!(facts[0].value, Value::Integer(1)); + } + + #[test] + fn entity_attribute_indexed_no_index_fallback() { + // FactStorage with facts but empty pending indexes and no committed reader + // exercises the fallback branch. + let storage = FactStorage::new(); + let e = uuid::Uuid::from_u128(1); + storage + .transact( + vec![ + (e, ":a".to_string(), Value::Integer(1)), + (e, ":b".to_string(), Value::Integer(2)), + ], + None, + ) + .unwrap(); + storage.replace_pending_indexes(crate::storage::index::Indexes::new()); + let facts = storage + .get_facts_by_entity_attribute_indexed(&e, &":b".to_string()) + .unwrap(); + assert_eq!(facts.len(), 1); + assert_eq!(facts[0].value, Value::Integer(2)); + } + + #[test] + fn entity_attribute_indexed_committed_and_pending() { + use crate::storage::CommittedFactReader; + use crate::storage::index::{FactRef, Indexes}; + use std::sync::Arc; + + struct MockLoader { + facts: Vec, + } + impl CommittedFactReader for MockLoader { + fn resolve(&self, fr: FactRef) -> anyhow::Result { + self.facts + .get(fr.slot_index as usize) + .cloned() + .ok_or_else(|| anyhow::anyhow!("no fact at slot")) + } + fn stream_all(&self) -> anyhow::Result> { + Ok(self.facts.clone()) + } + fn committed_page_count(&self) -> u64 { + 1 + } + } + + let storage = FactStorage::new(); + let e = uuid::Uuid::from_u128(1); + let committed = vec![ + make_assert(e, ":a", Value::Integer(1), 1, 0, VALID_TIME_FOREVER), + make_assert(e, ":ab", Value::Integer(9), 1, 0, VALID_TIME_FOREVER), + ]; + let mut indexes = Indexes::new(); + for (slot, f) in committed.iter().enumerate() { + indexes.insert( + f, + FactRef { + page_id: 1, + slot_index: u16::try_from(slot).unwrap(), + }, + ); + } + storage.replace_pending_indexes(indexes); + storage.set_committed_reader(Arc::new(MockLoader { facts: committed })); + + let facts = storage + .get_facts_by_entity_attribute_indexed(&e, &":a".to_string()) + .unwrap(); + assert_eq!(facts.len(), 1, "committed :a only, :ab excluded"); + assert_eq!(facts[0].value, Value::Integer(1)); + } + + /// #323 review: the committed EAVT range must end at the exact successor of + /// `(e, a)` for every attribute — including ones whose last UTF-8 byte is 0xBF + /// (e.g. `:丿`), where incrementing the last byte is not valid UTF-8 and the scan + /// used to run unbounded to the end of the index. + #[test] + fn entity_attribute_indexed_committed_range_is_bounded_for_any_attribute() { + use crate::storage::CommittedIndexReader; + use crate::storage::index::{AevtKey, AvetKey, EavtKey, FactRef, VaetKey}; + use std::sync::{Arc, Mutex}; + + struct RecordingReader { + eavt_bounds: Mutex)>>, + } + impl CommittedIndexReader for RecordingReader { + fn range_scan_eavt( + &self, + start: &EavtKey, + end: Option<&EavtKey>, + ) -> anyhow::Result> { + self.eavt_bounds + .lock() + .unwrap() + .push((start.clone(), end.cloned())); + Ok(vec![]) + } + fn range_scan_aevt( + &self, + _: &AevtKey, + _: Option<&AevtKey>, + ) -> anyhow::Result> { + Ok(vec![]) + } + fn range_scan_avet( + &self, + _: &AvetKey, + _: Option<&AvetKey>, + ) -> anyhow::Result> { + Ok(vec![]) + } + fn range_scan_vaet( + &self, + _: &VaetKey, + _: Option<&VaetKey>, + ) -> anyhow::Result> { + Ok(vec![]) + } + } + + let reader = Arc::new(RecordingReader { + eavt_bounds: Mutex::new(Vec::new()), + }); + let storage = FactStorage::new(); + storage.set_committed_index_reader(reader.clone()); + let e = uuid::Uuid::from_u128(5); + + for attr in [":plain", ":\u{4e3f}", ":\u{bf}", ":a\u{7f}"] { + storage + .get_facts_by_entity_attribute_indexed(&e, &attr.to_string()) + .unwrap(); + } + + let bounds = reader.eavt_bounds.lock().unwrap(); + assert_eq!(bounds.len(), 4, "one committed scan per lookup"); + for (start, end) in bounds.iter() { + let end = end + .as_ref() + .expect("committed EAVT scan must have an upper bound"); + assert_eq!(end.entity, e, "upper bound must stay within the entity"); + assert!(start < end, "range must be non-empty"); + // No other attribute may sort between start and end. + let sibling = EavtKey { + attribute: format!("{}x", start.attribute), + ..start.clone() + }; + assert!( + sibling >= *end, + "prefix sibling must fall outside the range" + ); + } + } + + #[test] + fn attribute_committed_range_is_bounded_for_any_attribute() { + use crate::storage::CommittedIndexReader; + use crate::storage::index::{AevtKey, AvetKey, EavtKey, FactRef, VaetKey}; + use std::sync::{Arc, Mutex}; + + struct RecordingReader { + aevt_bounds: Mutex)>>, + } + impl CommittedIndexReader for RecordingReader { + fn range_scan_eavt( + &self, + _: &EavtKey, + _: Option<&EavtKey>, + ) -> anyhow::Result> { + Ok(vec![]) + } + fn range_scan_aevt( + &self, + start: &AevtKey, + end: Option<&AevtKey>, + ) -> anyhow::Result> { + self.aevt_bounds + .lock() + .unwrap() + .push((start.clone(), end.cloned())); + Ok(vec![]) + } + fn range_scan_avet( + &self, + _: &AvetKey, + _: Option<&AvetKey>, + ) -> anyhow::Result> { + Ok(vec![]) + } + fn range_scan_vaet( + &self, + _: &VaetKey, + _: Option<&VaetKey>, + ) -> anyhow::Result> { + Ok(vec![]) + } + } + + let reader = Arc::new(RecordingReader { + aevt_bounds: Mutex::new(Vec::new()), + }); + let storage = FactStorage::new(); + storage.set_committed_index_reader(reader.clone()); + + for attr in [":plain", ":\u{4e3f}", ":\u{bf}", ":a\u{7f}"] { + storage.get_facts_by_attribute(&attr.to_string()).unwrap(); + } + + let bounds = reader.aevt_bounds.lock().unwrap(); + assert_eq!(bounds.len(), 4, "one committed scan per lookup"); + for (start, end) in bounds.iter() { + let end = end + .as_ref() + .expect("committed AEVT scan must have an upper bound"); + assert!(start < end, "range must be non-empty"); + // No other attribute may sort between start and end. + let sibling = AevtKey { + attribute: format!("{}x", start.attribute), + ..start.clone() + }; + assert!( + sibling >= *end, + "prefix sibling must fall outside the range" + ); + } + } + + #[test] + fn attribute_scan_excludes_prefix_siblings_and_non_ascii_neighbours() { + let storage = FactStorage::new(); + let e = uuid::Uuid::from_u128(7); + for attr in [ + ":a", + ":ab", + ":a/b", + ":\u{4e3f}", + ":\u{4e40}", + ":\u{bf}", + ":\u{c0}", + ] { + storage + .transact( + vec![(e, attr.to_string(), Value::String(attr.to_string()))], + None, + ) + .unwrap(); + } + for attr in [":a", ":\u{4e3f}", ":\u{bf}"] { + let facts = storage.get_facts_by_attribute(&attr.to_string()).unwrap(); + assert_eq!(facts.len(), 1, "exactly one fact for the attribute"); + assert!( + facts.iter().all(|f| f.attribute == attr), + "no sibling facts" + ); + } + } } diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 6aa3d8b1a4..1b33b03541 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -368,30 +368,26 @@ impl DatalogExecutor { /// Attempt a selective index-backed fact fetch for the given patterns. /// - /// For each pattern, prefer a bound entity literal (UUID or keyword -> deterministic UUID) - /// over a bound attribute keyword for that same pattern. Entity lookups are usually more - /// selective, but multi-pattern joins still need attribute candidates for patterns that do not - /// bind an entity. If any pattern has neither a bound entity nor a bound attribute, or if the - /// distinct lookup count exceeds `threshold`, returns `None` to use a full scan. Otherwise - /// returns `Some(facts)`, deduplicated by `(entity, attribute, tx_count, asserted, value)`. + /// Patterns with a bound entity literal (UUID or keyword → deterministic UUID) are + /// fetched by entity; if every pattern on that entity also binds a concrete attribute + /// keyword, only those `(entity, attribute)` EAVT ranges are read, so other attributes' + /// version history is never resolved (#323). An entity also referenced with a variable + /// or pseudo-attribute is read whole. Patterns without a bound entity are fetched by + /// attribute. If any pattern has neither, returns `None` (full scan). + /// + /// Lookup budget: if narrowing needs more than `threshold` lookups, every entity falls + /// back to a single whole-entity scan; only if that still exceeds `threshold` does this + /// return `None`. Narrowing therefore never turns a selective query into a full scan. + /// + /// Results are not deduplicated: the sole caller feeds them to `net_asserted_facts`, + /// which is idempotent under duplicated records. fn selective_fact_fetch(&self, patterns: &[Pattern], threshold: usize) -> Option> { - use std::collections::HashSet; - - // Dedup key: (entity, attribute, tx_count, asserted, encoded value, - // valid_from, valid_to). `asserted` keeps an assertion and a - // retraction from the same WriteTransaction apart; the encoded value - // keeps two values of one attribute written in the same transaction - // apart (#371). Uses `encode_value` bytes rather than `Value` to - // avoid Float hashing. `valid_from`/`valid_to` keep two distinct - // valid-time stints of the same (entity, attribute, value, tx_count, - // asserted) tuple apart — without them, two per-fact valid-time - // windows on the same value in one transaction collapse into a - // single arbitrary survivor and the other window's row is silently - // dropped from `:valid-at` and `:any-valid-time` results (#371). - type FactDedupKey = (uuid::Uuid, String, u64, bool, Vec, i64, i64); - - let mut entity_ids: HashSet = HashSet::new(); - let mut attributes: HashSet = HashSet::new(); + use std::collections::{BTreeMap, BTreeSet}; + + // Per bound entity: Some(attrs) = only these attributes are referenced; + // None = the whole entity is needed. BTree* for deterministic lookup order. + let mut entity_attrs: BTreeMap>> = BTreeMap::new(); + let mut attributes: BTreeSet = BTreeSet::new(); for pattern in patterns { let bound_entity = match &pattern.entity { @@ -401,7 +397,17 @@ impl DatalogExecutor { }; if let Some(uid) = bound_entity { - entity_ids.insert(uid); + let slot = entity_attrs + .entry(uid) + .or_insert_with(|| Some(BTreeSet::new())); + match &pattern.attribute { + AttributeSpec::Real(EdnValue::Keyword(attr)) => { + if let Some(attrs) = slot { + attrs.insert(attr.clone()); + } + } + _ => *slot = None, + } continue; } @@ -412,56 +418,40 @@ impl DatalogExecutor { } } - let total = entity_ids.len() + attributes.len(); + let narrowed_lookups: usize = entity_attrs + .values() + .map(|a| a.as_ref().map_or(1, BTreeSet::len)) + .sum::() + + attributes.len(); + let narrow = narrowed_lookups <= threshold; + let total = if narrow { + narrowed_lookups + } else { + entity_attrs.len() + attributes.len() + }; if total == 0 || total > threshold { return None; } - let mut seen: HashSet = HashSet::new(); let mut all_facts: Vec = Vec::new(); - for uid in &entity_ids { - match self.storage.get_facts_by_entity(uid) { - Ok(facts) => { - for fact in facts { - let key = ( - fact.entity, - fact.attribute.clone(), - fact.tx_count, - fact.asserted, - crate::storage::index::encode_value(&fact.value), - fact.valid_from, - fact.valid_to, + for (uid, attrs) in &entity_attrs { + match attrs { + Some(attrs) if narrow => { + for attr in attrs { + all_facts.extend( + self.storage + .get_facts_by_entity_attribute_indexed(uid, attr) + .ok()?, ); - if seen.insert(key) { - all_facts.push(fact); - } } } - Err(_) => return None, + _ => all_facts.extend(self.storage.get_facts_by_entity(uid).ok()?), } } for attr in &attributes { - match self.storage.get_facts_by_attribute(attr) { - Ok(facts) => { - for fact in facts { - let key = ( - fact.entity, - fact.attribute.clone(), - fact.tx_count, - fact.asserted, - crate::storage::index::encode_value(&fact.value), - fact.valid_from, - fact.valid_to, - ); - if seen.insert(key) { - all_facts.push(fact); - } - } - } - Err(_) => return None, - } + all_facts.extend(self.storage.get_facts_by_attribute(attr).ok()?); } Some(all_facts) @@ -3906,11 +3896,24 @@ mod tests { _ => panic!("expected query"), }; + let facts = executor.filter_facts_for_query(&query).unwrap(); + assert_eq!( + facts.len(), + 1, + "bound entity + attribute query should fetch only that (entity, attribute) pair (#323)" + ); + + // A variable attribute on the same bound entity still needs the whole entity. + let query = match parse_datalog_command("(query [:find ?a ?v :where [:e0 ?a ?v]])").unwrap() + { + DatalogCommand::Query(query) => query, + _ => panic!("expected query"), + }; let facts = executor.filter_facts_for_query(&query).unwrap(); assert_eq!( facts.len(), 2, - "bound entity + attribute query should fetch only the bound entity's facts" + "bound entity + variable attribute should fetch all of the entity's facts" ); } diff --git a/src/query/datalog/magic_sets.rs b/src/query/datalog/magic_sets.rs index 2ba77b1408..48660baa43 100644 --- a/src/query/datalog/magic_sets.rs +++ b/src/query/datalog/magic_sets.rs @@ -188,7 +188,7 @@ pub(crate) fn inject_magic_guard(rule: &Rule, predicate: &str, adornment: &[char /// Build magic propagation rules for adorned recursive calls within a rule body. /// /// For each `RuleInvocation` in the body that calls an adorned predicate, -/// emits a rule: (magic-p-ad ?bound_arg) :- (magic-p-ad ?head_bound_var) +/// emits a rule: (magic-p-ad ?bound_arg) :- (magic-p-ad ?head_bound_var) /// /// Returns Vec<(predicate_name, Rule)> to be registered with `register_rule_unchecked`. #[allow(dead_code)] @@ -284,13 +284,12 @@ pub(crate) fn build_propagation_rules( .filter_map(|(pos, _)| called_args.get(pos).cloned()) .collect(); - // Propagation body = guard + all non-RuleInvocation clauses before this call. - let mut prop_body = vec![guard.clone()]; - for preceding in rule.body.iter().take(i) { - if !matches!(preceding, WhereClause::RuleInvocation { .. }) { - prop_body.push(preceding.clone()); - } - } + // Propagation body = guard + every clause before this call, including rule + // invocations: a preceding call may be the only binder of a variable passed + // in a bound position (e.g. `(link ?x ?mid) (chain ?mid ?y)`, #297). + let mut prop_body = Vec::with_capacity(1 + i); + prop_body.push(guard.clone()); + prop_body.extend(rule.body.iter().take(i).cloned()); // Build the propagation rule head. // For fb-adorned called predicates: head = [pred, sentinel, bound_val_var] @@ -695,6 +694,36 @@ mod tests { } } + #[test] + fn test_propagation_rule_keeps_preceding_rule_invocation() { + // (chain ?x ?y) :- (link ?x ?mid) (chain ?mid ?y) + // bf → (__magic_chain_bf ?mid) :- (__magic_chain_bf ?x) (link ?x ?mid) + // The preceding (link ...) call is the only binder of ?mid (#297). + let rule = make_rule( + "chain", + &["?x", "?y"], + vec![ + rule_inv("link", &["?x", "?mid"]), + rule_inv("chain", &["?mid", "?y"]), + ], + ); + let adorned: HashMap> = [ + ("chain".to_string(), vec!['b', 'f']), + ("link".to_string(), vec!['b', 'f']), + ] + .into_iter() + .collect(); + let prop_rules = build_propagation_rules(&rule, "chain", &adorned); + let chain_magic = magic_pred_name("chain", &['b', 'f']); + let (_, prop) = prop_rules + .iter() + .find(|(pred, _)| *pred == chain_magic) + .expect("propagation rule for the recursive chain call"); + assert_eq!(prop.head[1], EdnValue::Symbol("?mid".to_string())); + assert_eq!(prop.body.len(), 2, "guard + preceding link call"); + assert_eq!(prop.body[1], rule_inv("link", &["?x", "?mid"])); + } + #[test] fn test_propagation_rule_bb_adornment() { // (reachable ?a ?b) :- (reachable ?a ?c) [?c :edge/to ?b] diff --git a/src/storage/backend/file.rs b/src/storage/backend/file.rs index 9db2a66199..f521ee292f 100644 --- a/src/storage/backend/file.rs +++ b/src/storage/backend/file.rs @@ -1,5 +1,6 @@ /// File-based storage backend for native platforms. use crate::error::{ErrorCode, bail_coded, err_coded}; +use crate::storage::dir_sync::sync_parent_dir; use crate::storage::{FileHeader, PAGE_SIZE, StorageBackend}; use anyhow::Result; use std::fs::{File, OpenOptions}; @@ -285,9 +286,14 @@ impl FileBackend { } } } else { - // New file or empty file: write initial header + // New file or empty file: write initial header, then make the + // file's directory entry durable. Without the directory sync a + // power loss can lose the whole file despite the header fsync + // (#389). An empty file left by a crash before this point takes + // this branch again on the next open, so the sync is repeated. let header = FileHeader::new(); Self::write_header(&mut file, &header)?; + sync_parent_dir(&path)?; header }; @@ -855,4 +861,50 @@ mod tests { "exactly one concurrent claimant should be admitted" ); } + + // ── #389: parent-directory fsync ──────────────────────────────────────── + + #[test] + fn test_create_syncs_parent_dir_after_header_write() { + use crate::storage::dir_sync::take_sync_log; + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("new.graph"); + take_sync_log(); + + let backend = FileBackend::open(&path).unwrap(); + + let log = take_sync_log(); + assert_eq!( + log.len(), + 1, + "creating the file must sync its directory once" + ); + assert_eq!( + log[0].dir, + dir.path(), + "must sync the file's parent directory" + ); + assert!( + log[0].child_existed, + "directory sync must follow the create" + ); + drop(backend); + } + + #[test] + fn test_reopen_existing_does_not_sync_parent_dir() { + use crate::storage::dir_sync::take_sync_log; + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("existing.graph"); + drop(FileBackend::open(&path).unwrap()); + take_sync_log(); + + let backend = FileBackend::open(&path).unwrap(); + + assert!( + take_sync_log().is_empty(), + "reopening an initialized file creates nothing, so needs no directory sync" + ); + drop(backend); + } } diff --git a/src/storage/btree_v6.rs b/src/storage/btree_v6.rs index e9a6020b34..1c8628cb77 100644 --- a/src/storage/btree_v6.rs +++ b/src/storage/btree_v6.rs @@ -61,18 +61,12 @@ fn read_u64_at(page: &[u8], offset: usize) -> Result { // ─── Low-level page writers ─────────────────────────────────────────────────── -/// Write a single leaf page and insert it into the cache. +/// Encode a leaf page: fixed header, slot directory, entries written end-to-start. /// /// `entries`: each element is the postcard-serialised `(K, FactRef)` bytes for -/// one index entry, in sort order. Written end-to-start in the page. +/// one index entry, in sort order. #[allow(clippy::arithmetic_side_effects, clippy::indexing_slicing)] -fn write_leaf_page( - backend: &mut dyn StorageBackend, - cache: &PageCache, - page_id: u64, - entries: &[Vec], - next_leaf: u64, -) -> Result<()> { +fn encode_leaf_page(entries: &[Vec], next_leaf: u64) -> Result> { let entry_count = u16::try_from(entries.len()).map_err(|_| { err_coded!( ErrorCode::Int049, @@ -108,7 +102,18 @@ fn write_leaf_page( page[slot_off..slot_off + 2].copy_from_slice(&write_pos_u16.to_le_bytes()); page[slot_off + 2..slot_off + 4].copy_from_slice(&entry_len_u16.to_le_bytes()); } + Ok(page) +} +/// Write a single leaf page and insert it into the cache. +fn write_leaf_page( + backend: &mut dyn StorageBackend, + cache: &PageCache, + page_id: u64, + entries: &[Vec], + next_leaf: u64, +) -> Result<()> { + let page = encode_leaf_page(entries, next_leaf)?; backend.write_page(page_id, &page)?; cache.put_dirty(page_id, page); Ok(()) @@ -188,6 +193,13 @@ fn write_internal_page( Ok(()) } +/// True when adding an entry of `entry_len` bytes to a leaf that already holds +/// `n_entries` entries totalling `data_bytes` would exceed the fill threshold. +#[allow(clippy::arithmetic_side_effects)] +fn leaf_overflows(n_entries: usize, data_bytes: usize, entry_len: usize) -> bool { + LEAF_HEADER_SIZE + (n_entries + 1) * SLOT_SIZE + data_bytes + entry_len > PAGE_FILL_BYTES +} + // ─── build_btree ────────────────────────────────────────────────────────────── /// Serialize `(key, fact_ref)` pairs into the byte format expected by [`build_btree`]. @@ -235,12 +247,9 @@ pub fn build_btree( let mut next_page = start_page_id; for (entry_bytes, key_bytes) in sorted_entries { - let projected = LEAF_HEADER_SIZE - + (cur_entries.len() + 1) * SLOT_SIZE - + cur_data_bytes - + entry_bytes.len(); - - if projected > PAGE_FILL_BYTES && !cur_entries.is_empty() { + if !cur_entries.is_empty() + && leaf_overflows(cur_entries.len(), cur_data_bytes, entry_bytes.len()) + { write_leaf_page(backend, cache, next_page, &cur_entries, 0)?; let first_key = cur_first_key.take().ok_or_else(|| { err_coded!( @@ -310,23 +319,27 @@ pub fn build_btree( cache.put_dirty(pid, page); } - // Single leaf: it is the root - if leaf_infos.len() == 1 { - return Ok(( - leaf_infos - .first() - .ok_or_else(|| { - err_coded!( - ErrorCode::Int049, - "leaf_infos unexpectedly empty".to_string() - ) - })? - .0, - next_page, - )); - } + build_internal_levels(leaf_infos, backend, cache, next_page) +} - // ── Phase 2: build internal levels bottom-up ────────────────────────────── +/// Build internal levels bottom-up over `leaf_infos` (`(page_id, first_key_bytes)` +/// per leaf, in key order), writing nodes from `next_page` onward. +/// +/// Returns `(root_page_id, next_free_page_id)`. A single leaf is its own root. +#[allow(clippy::arithmetic_side_effects, clippy::indexing_slicing)] +fn build_internal_levels( + leaf_infos: Vec<(u64, Vec)>, + backend: &mut dyn StorageBackend, + cache: &PageCache, + next_page: u64, +) -> Result<(u64, u64)> { + if leaf_infos.is_empty() { + bail_coded!( + ErrorCode::Int049, + "build_internal_levels: no leaves".to_string() + ); + } + let mut next_page = next_page; let mut current_level = leaf_infos; loop { @@ -437,6 +450,264 @@ pub fn merge_sorted_vecs(a: Vec, b: Vec) -> impl Iterator Result>>> { + // A chain longer than the file has pages must contain a cycle. + let max_leaves = backend.page_count()?; + let mut leaves = Vec::new(); + let mut leaf_id = find_leftmost_leaf(root_page_id, backend, cache)?; + loop { + let page = cache.get_or_load(leaf_id, backend)?; + if page.first().copied() != Some(PAGE_TYPE_LEAF) { + bail_coded!( + ErrorCode::Int049, + format!("collect_leaf_pages: expected leaf page at page_id={leaf_id}") + ); + } + if u64::try_from(leaves.len()).map_or(true, |n| n >= max_leaves) { + bail_coded!( + ErrorCode::Int049, + format!("collect_leaf_pages: leaf chain longer than the file at page_id={leaf_id}") + ); + } + validate_leaf_slots(&page[..], leaf_id)?; + let next_leaf = read_u64_at(&page[..], 4)?; + leaves.push(page); + if next_leaf == 0 { + break; + } + leaf_id = next_leaf; + } + Ok(leaves) +} + +/// Check a leaf's slot directory stays inside the page without decoding entries. +/// +/// Untouched leaves are copied verbatim and sealed under a fresh file checksum, +/// so damage must be caught here instead of being carried forward. +#[allow(clippy::arithmetic_side_effects)] +fn validate_leaf_slots(page: &[u8], page_id: u64) -> Result<()> { + let count = read_u16_at(page, 2)? as usize; + let data_start = LEAF_HEADER_SIZE + count * SLOT_SIZE; + if data_start > page.len() { + bail_coded!( + ErrorCode::Int049, + format!("leaf page_id={page_id}: slot directory overflows the page") + ); + } + for i in 0..count { + let slot_off = LEAF_HEADER_SIZE + i * SLOT_SIZE; + let offset = read_u16_at(page, slot_off)? as usize; + let length = read_u16_at(page, slot_off + 2)? as usize; + if offset < data_start || offset + length > page.len() { + bail_coded!( + ErrorCode::Int049, + format!("leaf page_id={page_id}: slot {i} out of bounds") + ); + } + } + Ok(()) +} + +/// Decode the key of a leaf's first entry; `None` for an empty leaf. +#[allow(clippy::arithmetic_side_effects)] +fn leaf_first_key(page: &[u8]) -> Result> +where + K: for<'de> Deserialize<'de>, +{ + if read_u16_at(page, 2)? == 0 { + return Ok(None); + } + let offset = read_u16_at(page, LEAF_HEADER_SIZE)? as usize; + let length = read_u16_at(page, LEAF_HEADER_SIZE + 2)? as usize; + let slice = page + .get(offset..offset.saturating_add(length)) + .ok_or_else(|| { + err_coded!( + ErrorCode::Int049, + format!("first entry out of bounds: offset={offset} len={length}") + ) + })?; + let (key, _): (K, FactRef) = postcard::from_bytes(slice)?; + Ok(Some(key)) +} + +/// Writes leaf pages at consecutive page ids, linking each to the next. +/// +/// One page is held back so its `next_leaf` can be set to the following page +/// id, or to 0 once it is known to be the last leaf. +struct LeafEmitter<'a> { + backend: &'a mut dyn StorageBackend, + cache: &'a PageCache, + next_page: u64, + held: Option<(u64, Vec)>, + infos: Vec<(u64, Vec)>, +} + +impl LeafEmitter<'_> { + #[allow(clippy::arithmetic_side_effects)] + fn push(&mut self, page: Vec, first_key_bytes: Vec) -> Result<()> { + let page_id = self.next_page; + self.next_page += 1; + self.release_held(page_id)?; + self.held = Some((page_id, page)); + self.infos.push((page_id, first_key_bytes)); + Ok(()) + } + + fn release_held(&mut self, next_leaf: u64) -> Result<()> { + if let Some((page_id, mut page)) = self.held.take() { + page.get_mut(4..12) + .ok_or_else(|| { + err_coded!( + ErrorCode::Int049, + "page too small to write next_leaf".to_string() + ) + })? + .copy_from_slice(&next_leaf.to_le_bytes()); + self.backend.write_page(page_id, &page)?; + self.cache.put_dirty(page_id, page); + } + Ok(()) + } + + /// Write the last held leaf and return `(leaf_infos, next_free_page_id)`. + #[allow(clippy::type_complexity)] + fn finish(mut self) -> Result<(Vec<(u64, Vec)>, u64)> { + self.release_held(0)?; + Ok((self.infos, self.next_page)) + } +} + +/// Serialise sorted entries and emit them as leaves. +/// +/// Entries that fit in one physical page stay in one leaf. Otherwise they are +/// split into pages of at most `PAGE_FILL_BYTES`, balanced by size, so a leaf that +/// overflows by one entry splits roughly in half. Splitting "full page + remainder" +/// instead left a near-empty leaf behind on every checkpoint that inserted into a +/// full leaf, growing the index without bound (#315). +#[allow(clippy::arithmetic_side_effects)] +fn emit_packed( + emitter: &mut LeafEmitter<'_>, + entries: impl Iterator, +) -> Result<()> { + // Each entry costs its bytes plus one slot-directory entry. + let mut serialised: Vec<(Vec, K)> = Vec::new(); + let mut total = 0usize; + for (key, fact_ref) in entries { + let entry = postcard::to_allocvec(&(&key, &fact_ref))?; + total += entry.len() + SLOT_SIZE; + serialised.push((entry, key)); + } + if serialised.is_empty() { + return Ok(()); + } + let target = if LEAF_HEADER_SIZE + total <= PAGE_SIZE { + total + } else { + let usable = PAGE_FILL_BYTES - LEAF_HEADER_SIZE; + total.div_ceil(total.div_ceil(usable)) + }; + + let mut cur: Vec> = Vec::new(); + let mut cur_size = 0usize; + let mut cur_first: Option> = None; + for (entry, key) in serialised { + let size = entry.len() + SLOT_SIZE; + if !cur.is_empty() && cur_size + size > target { + let first = cur_first.take().ok_or_else(|| { + err_coded!(ErrorCode::Int049, "BUG: leaf without first key".to_string()) + })?; + emitter.push(encode_leaf_page(&cur, 0)?, first)?; + cur.clear(); + cur_size = 0; + } + if cur_first.is_none() { + cur_first = Some(postcard::to_allocvec(&key)?); + } + cur_size += size; + cur.push(entry); + } + if let Some(first) = cur_first { + emitter.push(encode_leaf_page(&cur, 0)?, first)?; + } + Ok(()) +} + +/// Rebuild a B+tree from its old leaves plus sorted `pending` entries. +/// +/// Leaves that receive no pending entry are copied verbatim (only `next_leaf` +/// is patched); only leaves that do are decoded, merged and repacked. Internal +/// levels are rebuilt from scratch. Pending keys route to leaf `i` when +/// `first_key[i] <= key < first_key[i + 1]`; keys below the first leaf's first +/// key go to leaf 0. With no non-empty old leaves this is a plain bulk build. +/// +/// `old_leaves` must be snapshotted (see [`collect_leaf_pages`]) before any +/// page in `start_page_id..` is written. Returns `(root_page_id, next_free_page_id)`. +pub fn rebuild_btree_incremental( + old_leaves: Vec>>, + pending: Vec<(K, FactRef)>, + backend: &mut dyn StorageBackend, + cache: &PageCache, + start_page_id: u64, +) -> Result<(u64, u64)> +where + K: Serialize + for<'de> Deserialize<'de> + Ord, +{ + let mut leaves: Vec<(Arc>, K)> = Vec::with_capacity(old_leaves.len()); + for page in old_leaves { + if let Some(first_key) = leaf_first_key::(&page[..])? { + leaves.push((page, first_key)); + } + } + if leaves.is_empty() { + return build_btree( + btree_entries(pending.into_iter())?.into_iter(), + backend, + cache, + start_page_id, + ); + } + + let mut emitter = LeafEmitter { + backend: &mut *backend, + cache, + next_page: start_page_id, + held: None, + infos: Vec::new(), + }; + let mut pending = pending.into_iter().peekable(); + for (i, (page, first_key)) in leaves.iter().enumerate() { + let upper = leaves.get(i.saturating_add(1)).map(|(_, k)| k); + let mut batch = Vec::new(); + while let Some((key, _)) = pending.peek() { + if upper.is_some_and(|u| key >= u) { + break; + } + if let Some(entry) = pending.next() { + batch.push(entry); + } + } + if batch.is_empty() { + emitter.push((**page).clone(), postcard::to_allocvec(first_key)?)?; + } else { + let old = read_leaf_entries::(&page[..])?; + emit_packed(&mut emitter, merge_sorted_vecs(old, batch))?; + } + } + let (leaf_infos, next_page) = emitter.finish()?; + build_internal_levels(leaf_infos, backend, cache, next_page) +} + // ─── Leaf traversal helpers ─────────────────────────────────────────────────── /// Traverse internal nodes from `root` to find the leftmost (first) leaf page. @@ -571,6 +842,10 @@ where // ─── stream_all_entries ─────────────────────────────────────────────────────── /// Stream all `(K, FactRef)` entries from a B+tree in sorted order. +/// +/// Test-only since #315: `save()` snapshots raw leaves via [`collect_leaf_pages`] +/// instead of decoding every entry. +#[cfg(test)] pub fn stream_all_entries( root_page_id: u64, backend: &dyn StorageBackend, @@ -828,6 +1103,310 @@ mod tests { ) } + /// Deterministic xorshift64 so randomized tests are reproducible without deps. + struct Rng(u64); + impl Rng { + fn next(&mut self) -> u64 { + let mut x = self.0; + x ^= x << 13; + x ^= x >> 7; + x ^= x << 17; + self.0 = x; + x + } + } + + /// `n` EAVT entries with random entities; `counter` keeps keys unique. + fn random_eavt(rng: &mut Rng, n: usize, counter: &mut u64) -> Vec<(EavtKey, FactRef)> { + let mut v: Vec<(EavtKey, FactRef)> = (0..n) + .map(|_| { + *counter += 1; + let entity = (u128::from(rng.next()) << 64) | u128::from(*counter); + make_eavt(entity, ":attr", *counter) + }) + .collect(); + v.sort(); + v + } + + fn sorted_union(a: &[(EavtKey, FactRef)], b: &[(EavtKey, FactRef)]) -> Vec<(EavtKey, FactRef)> { + let mut v: Vec<_> = a.iter().chain(b.iter()).cloned().collect(); + v.sort(); + v + } + + /// Build `committed` at page 1, then rebuild with `pending` starting at `start`. + fn build_then_incremental( + committed: &[(EavtKey, FactRef)], + pending: &[(EavtKey, FactRef)], + start: u64, + ) -> (MemoryBackend, PageCache, u64, u64) { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let ser = btree_entries(committed.iter().cloned()).unwrap(); + let (old_root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let leaves = collect_leaf_pages(old_root, &backend, &cache).unwrap(); + let (root, next_free) = + rebuild_btree_incremental(leaves, pending.to_vec(), &mut backend, &cache, start) + .unwrap(); + (backend, cache, root, next_free) + } + + /// Stream equality, a next_leaf chain of non-empty leaves, and range_scan + /// agreement on random bounds. + fn assert_tree_exact( + root: u64, + backend: &MemoryBackend, + cache: &PageCache, + expected: &[(EavtKey, FactRef)], + rng: &mut Rng, + ) { + let got: Vec<(EavtKey, FactRef)> = stream_all_entries(root, backend, cache).unwrap(); + assert_eq!(got.len(), expected.len(), "entry count differs"); + assert!(got == expected, "streamed entries differ from expected"); + + let leaves = collect_leaf_pages(root, backend, cache).unwrap(); + if expected.is_empty() { + assert_eq!(leaves.len(), 1, "empty tree is one empty leaf"); + } else { + for page in &leaves { + assert!(read_u16_at(&page[..], 2).unwrap() > 0, "empty leaf in tree"); + } + } + + for _ in 0..20 { + if expected.is_empty() { + break; + } + let a = (rng.next() as usize) % expected.len(); + let b = (rng.next() as usize) % expected.len(); + let (lo, hi) = (a.min(b), a.max(b)); + let start = &expected[lo].0; + let end = &expected[hi].0; + let want: Vec = expected[lo..hi].iter().map(|(_, r)| *r).collect(); + let refs = range_scan(root, start, Some(end), backend, cache).unwrap(); + assert!(refs == want, "range_scan differs from expected slice"); + } + } + + /// Build a multi-leaf tree and return (backend, cache, root, leaf page ids). + fn multi_leaf_tree() -> (MemoryBackend, PageCache, u64, Vec) { + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let entries: Vec<_> = (0u128..500).map(|n| make_eavt(n, ":a", n as u64)).collect(); + let ser = btree_entries(entries.into_iter()).unwrap(); + let (root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let mut ids = vec![find_leftmost_leaf(root, &backend, &cache).unwrap()]; + loop { + let page = cache.get_or_load(*ids.last().unwrap(), &backend).unwrap(); + let next = read_u64_at(&page[..], 4).unwrap(); + if next == 0 { + break; + } + ids.push(next); + } + assert!(ids.len() >= 3, "fixture needs several leaves"); + (backend, cache, root, ids) + } + + fn overwrite_page(backend: &mut MemoryBackend, cache: &PageCache, id: u64, page: Vec) { + backend.write_page(id, &page).unwrap(); + cache.put_dirty(id, page); + } + + #[test] + fn test_collect_leaf_pages_rejects_cyclic_chain() { + // A corrupt next_leaf pointing back must be an error, not an endless loop. + let (mut backend, cache, root, ids) = multi_leaf_tree(); + let mut page = cache.get_or_load(ids[1], &backend).unwrap().to_vec(); + page[4..12].copy_from_slice(&ids[0].to_le_bytes()); + overwrite_page(&mut backend, &cache, ids[1], page); + assert!( + collect_leaf_pages(root, &backend, &cache).is_err(), + "cyclic leaf chain must be rejected" + ); + } + + #[test] + fn test_collect_leaf_pages_rejects_corrupt_slot_directory() { + // Untouched leaves are copied without decoding, so a damaged slot must be + // caught here rather than sealed under a fresh checksum. + let (mut backend, cache, root, ids) = multi_leaf_tree(); + let mut page = cache.get_or_load(ids[1], &backend).unwrap().to_vec(); + let bad_offset = u16::try_from(PAGE_SIZE - 2).unwrap(); + page[LEAF_HEADER_SIZE..LEAF_HEADER_SIZE + 2].copy_from_slice(&bad_offset.to_le_bytes()); + overwrite_page(&mut backend, &cache, ids[1], page); + assert!( + collect_leaf_pages(root, &backend, &cache).is_err(), + "slot pointing past the page end must be rejected" + ); + + let (mut backend, cache, root, ids) = multi_leaf_tree(); + let mut page = cache.get_or_load(ids[2], &backend).unwrap().to_vec(); + page[2..4].copy_from_slice(&u16::MAX.to_le_bytes()); + overwrite_page(&mut backend, &cache, ids[2], page); + assert!( + collect_leaf_pages(root, &backend, &cache).is_err(), + "entry count overflowing the page must be rejected" + ); + } + + #[test] + fn test_incremental_no_pending_copies_leaves_verbatim() { + let mut rng = Rng(0x315); + let mut ctr = 0; + let committed = random_eavt(&mut rng, 2000, &mut ctr); + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let ser = btree_entries(committed.iter().cloned()).unwrap(); + let (old_root, old_next) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let old_leaves = collect_leaf_pages(old_root, &backend, &cache).unwrap(); + let (root, _) = rebuild_btree_incremental( + old_leaves.clone(), + Vec::<(EavtKey, FactRef)>::new(), + &mut backend, + &cache, + old_next, + ) + .unwrap(); + let new_leaves = collect_leaf_pages(root, &backend, &cache).unwrap(); + assert_eq!(new_leaves.len(), old_leaves.len(), "leaf count changed"); + for (o, n) in old_leaves.iter().zip(new_leaves.iter()) { + assert!(o[..4] == n[..4], "leaf header prefix changed"); + assert!(o[12..] == n[12..], "leaf body changed"); + } + assert_tree_exact(root, &backend, &cache, &committed, &mut rng); + } + + #[test] + fn test_incremental_matches_merge_random() { + let mut rng = Rng(0xC0FFEE); + let mut ctr = 0; + for _ in 0..40 { + let n_committed = (rng.next() % 3000) as usize; + let committed = random_eavt(&mut rng, n_committed, &mut ctr); + let n_pending = (rng.next() % 200) as usize; + let pending = random_eavt(&mut rng, n_pending, &mut ctr); + let (backend, cache, root, _) = build_then_incremental(&committed, &pending, 5000); + let expected = sorted_union(&committed, &pending); + assert_tree_exact(root, &backend, &cache, &expected, &mut rng); + } + } + + #[test] + fn test_incremental_pending_outside_old_range() { + let mut rng = Rng(7); + let committed: Vec<_> = (1000u128..3000) + .map(|n| make_eavt(n, ":a", n as u64)) + .collect(); + let pending = vec![ + make_eavt(1, ":a", 1), + make_eavt(2, ":a", 2), + make_eavt(9_000, ":a", 9_000), + make_eavt(9_001, ":a", 9_001), + ]; + let (backend, cache, root, _) = build_then_incremental(&committed, &pending, 5000); + let expected = sorted_union(&committed, &pending); + assert_tree_exact(root, &backend, &cache, &expected, &mut rng); + } + + #[test] + fn test_incremental_many_pending_into_one_leaf_splits() { + let mut rng = Rng(11); + // Committed entities are 0, 10_000, 20_000, …: every pending 0 < e < 10_000 + // routes to leaf 0, which must split into several leaves. + let committed: Vec<_> = (0u128..2000) + .map(|n| make_eavt(n * 10_000, ":a", n as u64 + 1)) + .collect(); + let pending: Vec<_> = (1u128..3000) + .map(|n| make_eavt(n, ":a", 100_000 + n as u64)) + .collect(); + let (backend, cache, root, _) = build_then_incremental(&committed, &pending, 5000); + let expected = sorted_union(&committed, &pending); + assert_tree_exact(root, &backend, &cache, &expected, &mut rng); + } + + #[test] + fn test_incremental_empty_old_tree_falls_back_to_bulk_build() { + let mut rng = Rng(13); + let mut ctr = 0; + let pending = random_eavt(&mut rng, 500, &mut ctr); + let (backend, cache, root, _) = build_then_incremental(&[], &pending, 5000); + assert_tree_exact(root, &backend, &cache, &pending, &mut rng); + // Nothing old, nothing new: still a valid single empty leaf. + let (backend, cache, root, next) = build_then_incremental(&[], &[], 5000); + assert_eq!(next, root + 1, "empty result is one page"); + assert_tree_exact(root, &backend, &cache, &[], &mut rng); + } + + #[test] + fn test_incremental_new_tree_overlaps_old_pages() { + // save() writes the new tree over the old tree's pages; old leaves are + // snapshotted first, so the result must still be exact. + let mut rng = Rng(17); + let mut ctr = 0; + let committed = random_eavt(&mut rng, 3000, &mut ctr); + let pending = random_eavt(&mut rng, 100, &mut ctr); + let (backend, cache, root, _) = build_then_incremental(&committed, &pending, 3); + let expected = sorted_union(&committed, &pending); + assert_tree_exact(root, &backend, &cache, &expected, &mut rng); + } + + #[test] + fn test_incremental_single_inserts_do_not_fragment_leaves() { + // One random insert per round into a bulk-built (75%-full) tree, like one + // checkpoint per new fact. Splitting "75% + remainder" left a near-empty + // leaf per insert; leaves must stay reasonably full instead. + let mut rng = Rng(23); + let mut ctr = 0; + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let mut expected = random_eavt(&mut rng, 3000, &mut ctr); + let ser = btree_entries(expected.iter().cloned()).unwrap(); + let (mut root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + let bulk_leaves = collect_leaf_pages(root, &backend, &cache).unwrap().len(); + for _ in 0..600 { + let pending = random_eavt(&mut rng, 1, &mut ctr); + let leaves = collect_leaf_pages(root, &backend, &cache).unwrap(); + root = rebuild_btree_incremental(leaves, pending.clone(), &mut backend, &cache, 1) + .unwrap() + .0; + expected = sorted_union(&expected, &pending); + } + assert_tree_exact(root, &backend, &cache, &expected, &mut rng); + // 20% more entries; at >= ~37% fill that is at most ~2.5x the bulk leaf count. + let leaves = collect_leaf_pages(root, &backend, &cache).unwrap().len(); + assert!( + leaves <= bulk_leaves * 5 / 2, + "leaf count grew from {bulk_leaves} to {leaves}" + ); + } + + #[test] + fn test_incremental_repeated_rounds() { + // Each round consumes the previous round's incrementally built tree, + // writing the new tree over the old pages like save() does. + let mut rng = Rng(19); + let mut ctr = 0; + let mut backend = MemoryBackend::new(); + let cache = PageCache::new(4096); + let mut expected = random_eavt(&mut rng, 1500, &mut ctr); + let ser = btree_entries(expected.iter().cloned()).unwrap(); + let (mut root, _) = build_btree(ser.into_iter(), &mut backend, &cache, 1).unwrap(); + for round in 0..30u64 { + let n_pending = 1 + (rng.next() % 150) as usize; + let pending = random_eavt(&mut rng, n_pending, &mut ctr); + let leaves = collect_leaf_pages(root, &backend, &cache).unwrap(); + let start = 1 + round % 3; + let (r, _) = + rebuild_btree_incremental(leaves, pending.clone(), &mut backend, &cache, start) + .unwrap(); + root = r; + expected = sorted_union(&expected, &pending); + assert_tree_exact(root, &backend, &cache, &expected, &mut rng); + } + } + #[test] fn test_read_u16_at_oob_rejected() { let page = vec![0u8; 4]; diff --git a/src/storage/dir_sync.rs b/src/storage/dir_sync.rs new file mode 100644 index 0000000000..21f9d8d9ce --- /dev/null +++ b/src/storage/dir_sync.rs @@ -0,0 +1,126 @@ +//! Parent-directory fsync (#389). +//! +//! On POSIX systems a newly created, deleted or renamed file survives a power +//! loss only once its parent directory has been fsynced: `fsync` on the file +//! itself makes the file's *contents* durable, not the directory entry that +//! names it. Without this, a power loss (not a process kill -- a kill leaves +//! the OS page cache intact) can lose a freshly created `.graph` or `.wal`, +//! or bring back a WAL that `checkpoint()` deleted. +//! +//! Durability order: +//! +//! - Create: create file → write + `sync_all` its first bytes → sync parent dir. +//! - Delete: remove file → sync parent dir. +//! +//! Windows needs no directory sync (NTFS journals directory metadata), and +//! cannot open a directory as a `File` without extra flags, so this is a no-op +//! there and on every other non-Unix target. + +use std::io; +use std::path::Path; + +/// Fsync the directory that contains `child`, making `child`'s creation or +/// removal durable. +/// +/// `child` is the path of the file that was just created or removed, not the +/// directory itself. A bare file name (no parent component) refers to the +/// current directory. +pub(crate) fn sync_parent_dir(child: &Path) -> io::Result<()> { + let dir = match child.parent() { + Some(p) if !p.as_os_str().is_empty() => p, + _ => Path::new("."), + }; + + #[cfg(test)] + record(dir, child); + + #[cfg(unix)] + std::fs::File::open(dir)?.sync_all()?; + #[cfg(not(unix))] + let _ = dir; + Ok(()) +} + +// ─── Test-only call log ───────────────────────────────────────────────────── +// +// A power loss cannot be simulated in a test, so tests instead check that the +// sync happens at all and in the right order relative to the file operation: +// each call records the directory and whether `child` existed at that moment. +// After a create it must exist; after a delete it must not. Thread-local, so +// concurrently running tests do not see each other's calls. + +#[cfg(test)] +thread_local! { + static SYNC_LOG: std::cell::RefCell> = + const { std::cell::RefCell::new(Vec::new()) }; +} + +/// One recorded `sync_parent_dir` call. +#[cfg(test)] +#[derive(Debug, Clone, PartialEq, Eq)] +pub(crate) struct DirSync { + /// The directory that was synced. + pub dir: std::path::PathBuf, + /// The file the sync was made on behalf of. + pub child: std::path::PathBuf, + /// Whether `child` existed when the directory was synced. + pub child_existed: bool, +} + +#[cfg(test)] +fn record(dir: &Path, child: &Path) { + SYNC_LOG.with(|log| { + log.borrow_mut().push(DirSync { + dir: dir.to_path_buf(), + child: child.to_path_buf(), + child_existed: child.exists(), + }) + }); +} + +/// Return and clear this thread's recorded directory syncs. +#[cfg(test)] +pub(crate) fn take_sync_log() -> Vec { + SYNC_LOG.with(|log| std::mem::take(&mut *log.borrow_mut())) +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_syncs_parent_of_child() { + let dir = tempfile::tempdir().unwrap(); + let child = dir.path().join("a.graph"); + std::fs::write(&child, b"x").unwrap(); + take_sync_log(); + + sync_parent_dir(&child).unwrap(); + + let log = take_sync_log(); + assert_eq!(log.len(), 1, "expected exactly one directory sync"); + assert_eq!(log[0].dir, dir.path(), "must sync the child's parent"); + assert!(log[0].child_existed, "child existed at sync time"); + } + + #[test] + fn test_bare_file_name_syncs_current_dir() { + take_sync_log(); + sync_parent_dir(Path::new("no-such-file.graph")).unwrap(); + let log = take_sync_log(); + assert_eq!(log.len(), 1, "expected exactly one directory sync"); + assert_eq!(log[0].dir, Path::new("."), "bare name means current dir"); + assert!(!log[0].child_existed, "child does not exist"); + } + + #[cfg(unix)] + #[test] + fn test_missing_parent_dir_is_an_error() { + let dir = tempfile::tempdir().unwrap(); + let child = dir.path().join("gone").join("a.graph"); + assert!( + sync_parent_dir(&child).is_err(), + "a directory that cannot be opened must surface as an error" + ); + } +} diff --git a/src/storage/index.rs b/src/storage/index.rs index 9099c46605..efcbadb79a 100644 --- a/src/storage/index.rs +++ b/src/storage/index.rs @@ -169,6 +169,14 @@ impl EavtKey { asserted: false, } } + + /// Smallest possible key for the `(entity, attribute)` pair. + pub fn entity_attribute_start(entity: EntityId, attribute: &str) -> Self { + EavtKey { + attribute: attribute.to_string(), + ..EavtKey::entity_start(entity) + } + } } impl AevtKey { diff --git a/src/storage/mod.rs b/src/storage/mod.rs index 14a28b8de1..6853699d38 100644 --- a/src/storage/mod.rs +++ b/src/storage/mod.rs @@ -8,6 +8,7 @@ pub mod backend; pub mod btree_v6; pub mod cache; +pub(crate) mod dir_sync; pub mod index; pub mod packed_pages; pub mod persistent_facts; diff --git a/src/storage/persistent_facts.rs b/src/storage/persistent_facts.rs index 8afcbe53a0..2ce30b6494 100644 --- a/src/storage/persistent_facts.rs +++ b/src/storage/persistent_facts.rs @@ -7,8 +7,8 @@ use crate::graph::FactStorage; use crate::graph::types::Fact; use crate::storage::FACT_PAGE_FORMAT_PACKED; use crate::storage::btree_v6::{ - MutexStorageBackend, OnDiskIndexReader, btree_entries, build_btree, merge_sorted_vecs, - stream_all_entries, + MutexStorageBackend, OnDiskIndexReader, btree_entries, build_btree, collect_leaf_pages, + rebuild_btree_incremental, }; use crate::storage::cache::PageCache; use crate::storage::index::{AevtKey, AvetKey, EavtKey, FactRef, VaetKey}; @@ -136,6 +136,10 @@ pub struct PersistentFactStorage { dirty: bool, last_checkpointed_tx_count: u64, committed_fact_pages: Arc, + /// CRC32 state after hashing fact pages `1..=n` (`n` is the first element). + /// Fact pages are never rewritten, so `save()` extends this instead of + /// re-reading them; `None` (or a stale `n`) falls back to a full pass (#315). + fact_prefix_crc: Option<(u64, Hasher)>, } impl PersistentFactStorage { @@ -157,6 +161,7 @@ impl PersistentFactStorage { dirty: false, last_checkpointed_tx_count: 0, committed_fact_pages, + fact_prefix_crc: None, }; // Try to load existing data. @@ -252,7 +257,30 @@ impl PersistentFactStorage { .lock() .map_err(|_| err_coded!(ErrorCode::Stg016))?; let total_data_pages = header.page_count.saturating_sub(1); - compute_page_checksum(&*backend, 1, total_data_pages)? != header.index_checksum + // Hash fact pages, keep that state for save() (#315), then the index pages. + let (full_checksum, fact_prefix) = if total_data_pages >= num_fact_pages { + let mut hasher = Hasher::new(); + hash_pages(&*backend, &mut hasher, 1, num_fact_pages)?; + let prefix = hasher.clone(); + let index_start = num_fact_pages + .checked_add(1) + .ok_or_else(|| err_coded!(ErrorCode::Stg021))?; + hash_pages( + &*backend, + &mut hasher, + index_start, + total_data_pages.saturating_sub(num_fact_pages), + )?; + (hasher.finalize(), Some(prefix)) + } else { + (compute_page_checksum(&*backend, 1, total_data_pages)?, None) + }; + if full_checksum == header.index_checksum { + self.fact_prefix_crc = fact_prefix.map(|p| (num_fact_pages, p)); + false + } else { + true + } }; // Register CommittedFactReader on FactStorage (before WAL replay) @@ -459,27 +487,18 @@ impl PersistentFactStorage { Err(e) => bail_coded!(ErrorCode::Stg010, e), }; - // Stream committed B+tree entries BEFORE writing new pages that may overlap - let committed_eavt: Vec<(EavtKey, FactRef)> = if curr_header.eavt_root_page != 0 { - stream_all_entries(curr_header.eavt_root_page, &*backend, &self.page_cache)? - } else { - Vec::new() - }; - let committed_aevt: Vec<(AevtKey, FactRef)> = if curr_header.aevt_root_page != 0 { - stream_all_entries(curr_header.aevt_root_page, &*backend, &self.page_cache)? - } else { - Vec::new() - }; - let committed_avet: Vec<(AvetKey, FactRef)> = if curr_header.avet_root_page != 0 { - stream_all_entries(curr_header.avet_root_page, &*backend, &self.page_cache)? - } else { - Vec::new() - }; - let committed_vaet: Vec<(VaetKey, FactRef)> = if curr_header.vaet_root_page != 0 { - stream_all_entries(curr_header.vaet_root_page, &*backend, &self.page_cache)? - } else { - Vec::new() + // Snapshot old B+tree leaves BEFORE writing new pages that may overlap them. + let old_leaves = |root: u64| -> Result>>> { + if root == 0 { + Ok(Vec::new()) + } else { + collect_leaf_pages(root, &*backend, &self.page_cache) + } }; + let old_eavt = old_leaves(curr_header.eavt_root_page)?; + let old_aevt = old_leaves(curr_header.aevt_root_page)?; + let old_avet = old_leaves(curr_header.avet_root_page)?; + let old_vaet = old_leaves(curr_header.vaet_root_page)?; // Invalidate cached pages that will be overwritten (old index pages) self.page_cache.invalidate_from(new_fact_start); @@ -513,41 +532,35 @@ impl PersistentFactStorage { .checked_add(new_total_fact_pages) .ok_or_else(|| err_coded!(ErrorCode::Stg017))?; - let eavt_ser = if !committed_eavt.is_empty() { - btree_entries(merge_sorted_vecs(committed_eavt, pending_eavt))? - } else { - btree_entries(pending_eavt.into_iter())? - }; - let (eavt_root, next1) = build_btree( - eavt_ser.into_iter(), + // Copy untouched leaves, repack only leaves that receive pending entries (#315). + let (eavt_root, next1) = rebuild_btree_incremental( + old_eavt, + pending_eavt, &mut *backend, &self.page_cache, index_start, )?; - - let aevt_ser = if !committed_aevt.is_empty() { - btree_entries(merge_sorted_vecs(committed_aevt, pending_aevt))? - } else { - btree_entries(pending_aevt.into_iter())? - }; - let (aevt_root, next2) = - build_btree(aevt_ser.into_iter(), &mut *backend, &self.page_cache, next1)?; - - let avet_ser = if !committed_avet.is_empty() { - btree_entries(merge_sorted_vecs(committed_avet, pending_avet))? - } else { - btree_entries(pending_avet.into_iter())? - }; - let (avet_root, next3) = - build_btree(avet_ser.into_iter(), &mut *backend, &self.page_cache, next2)?; - - let vaet_ser = if !committed_vaet.is_empty() { - btree_entries(merge_sorted_vecs(committed_vaet, pending_vaet))? - } else { - btree_entries(pending_vaet.into_iter())? - }; - let (vaet_root, next4) = - build_btree(vaet_ser.into_iter(), &mut *backend, &self.page_cache, next3)?; + let (aevt_root, next2) = rebuild_btree_incremental( + old_aevt, + pending_aevt, + &mut *backend, + &self.page_cache, + next1, + )?; + let (avet_root, next3) = rebuild_btree_incremental( + old_avet, + pending_avet, + &mut *backend, + &self.page_cache, + next2, + )?; + let (vaet_root, next4) = rebuild_btree_incremental( + old_vaet, + pending_vaet, + &mut *backend, + &self.page_cache, + next3, + )?; // Sync index pages to disk before writing the header. // The header update is the atomic commit point: once it's durable, @@ -557,8 +570,29 @@ impl PersistentFactStorage { // CRC32 over ALL data pages (facts + indexes), excluding page 0 (header). // This detects corruption in both fact pages and B+tree index pages. - let total_data_pages = next4.saturating_sub(1); - let checksum = compute_page_checksum(&*backend, 1, total_data_pages)?; + // Fact pages 1..=old count are unchanged since the last save/load, so extend + // the cached CRC state instead of re-reading them (#315). Taking the cache + // means a failed save leaves None and the next save does a full pass. + let mut hasher = match self.fact_prefix_crc.take() { + Some((n, prefix)) if n == old_fact_page_count => { + let mut h = prefix; + hash_pages(&*backend, &mut h, new_fact_start, new_pages_len)?; + h + } + _ => { + let mut h = Hasher::new(); + hash_pages(&*backend, &mut h, 1, new_total_fact_pages)?; + h + } + }; + let new_prefix = hasher.clone(); + hash_pages( + &*backend, + &mut hasher, + index_start, + next4.saturating_sub(index_start), + )?; + let checksum = hasher.finalize(); // ── Step E: write header (last write = crash-safe boundary) ───────────── let mut header = FileHeader::new(); // version=FORMAT_VERSION @@ -587,6 +621,7 @@ impl PersistentFactStorage { self.committed_fact_pages .store(new_total_fact_pages, Ordering::SeqCst); + self.fact_prefix_crc = Some((new_total_fact_pages, new_prefix)); self.last_checkpointed_tx_count = self.storage.current_tx_count(); self.dirty = false; @@ -701,14 +736,24 @@ fn compute_page_checksum( num_pages: u64, ) -> Result { let mut hasher = Hasher::new(); + hash_pages(backend, &mut hasher, first_page, num_pages)?; + Ok(hasher.finalize()) +} + +/// Feed pages `first_page..first_page + num_pages` into `hasher`. +fn hash_pages( + backend: &dyn StorageBackend, + hasher: &mut Hasher, + first_page: u64, + num_pages: u64, +) -> Result<()> { for i in 0..num_pages { let page_id = first_page .checked_add(i) .ok_or_else(|| err_coded!(ErrorCode::Stg021))?; - let page = backend.read_page(page_id)?; - hasher.update(&page); + hasher.update(&backend.read_page(page_id)?); } - Ok(hasher.finalize()) + Ok(()) } /// Compute CRC32 checksum over header bytes 0-79 (header_checksum field zeroed). @@ -811,9 +856,187 @@ mod tests { use super::*; use crate::graph::types::Value; use crate::storage::backend::MemoryBackend; + use crate::storage::btree_v6::stream_all_entries; use std::io::Write; use uuid::Uuid; + /// All four on-disk indexes equal a from-scratch derivation from the fact pages, + /// and the stored checksum equals a full pass over pages 1..page_count. + fn assert_indexes_and_checksum_exact( + pfs: &PersistentFactStorage, + ) { + let backend = pfs.backend.lock().unwrap(); + let header = FileHeader::from_bytes(&backend.read_page(0).unwrap()).unwrap(); + let full = compute_page_checksum(&*backend, 1, header.page_count - 1).unwrap(); + assert_eq!(header.index_checksum, full, "stored checksum != full pass"); + + let (facts, refs) = + crate::storage::packed_pages::read_all_with_refs(&*backend, 1, header.fact_page_count) + .unwrap(); + let (eavt, aevt, avet, vaet) = build_sorted_index_entries(&facts, &refs); + let cache = &pfs.page_cache; + let got_eavt: Vec<(EavtKey, FactRef)> = + stream_all_entries(header.eavt_root_page, &*backend, cache).unwrap(); + let got_aevt: Vec<(AevtKey, FactRef)> = + stream_all_entries(header.aevt_root_page, &*backend, cache).unwrap(); + let got_avet: Vec<(AvetKey, FactRef)> = + stream_all_entries(header.avet_root_page, &*backend, cache).unwrap(); + let got_vaet: Vec<(VaetKey, FactRef)> = + stream_all_entries(header.vaet_root_page, &*backend, cache).unwrap(); + assert!( + got_eavt.is_sorted_by(|a, b| a.0 <= b.0), + "EAVT not in key order" + ); + assert!( + got_aevt.is_sorted_by(|a, b| a.0 <= b.0), + "AEVT not in key order" + ); + assert!( + got_avet.is_sorted_by(|a, b| a.0 <= b.0), + "AVET not in key order" + ); + assert!( + got_vaet.is_sorted_by(|a, b| a.0 <= b.0), + "VAET not in key order" + ); + // One transaction can write the same (entity, attribute) twice, giving equal + // v7 keys (#371); their relative order is unspecified, so compare as sets. + fn by_key_then_ref(mut v: Vec<(K, FactRef)>) -> Vec<(K, FactRef)> { + v.sort(); + v + } + let (eavt, aevt, avet, vaet) = ( + by_key_then_ref(eavt), + by_key_then_ref(aevt), + by_key_then_ref(avet), + by_key_then_ref(vaet), + ); + let (got_eavt, got_aevt, got_avet, got_vaet) = ( + by_key_then_ref(got_eavt), + by_key_then_ref(got_aevt), + by_key_then_ref(got_avet), + by_key_then_ref(got_vaet), + ); + assert!(got_eavt == eavt, "EAVT differs from full derivation"); + assert!(got_aevt == aevt, "AEVT differs from full derivation"); + assert!(got_avet == avet, "AVET differs from full derivation"); + assert!(got_vaet == vaet, "VAET differs from full derivation"); + } + + /// One transact of `n` facts: new and reused entities, strings and refs (VAET). + fn transact_mixed( + pfs: &mut PersistentFactStorage, + entities: &mut Vec, + n: usize, + seed: u64, + ) { + let mut batch = Vec::new(); + for i in 0..n { + let k = seed.wrapping_mul(31).wrapping_add(i as u64); + let e = if entities.is_empty() || k % 3 == 0 { + let e = Uuid::new_v4(); + entities.push(e); + e + } else { + entities[(k as usize) % entities.len()] + }; + let value = if k % 4 == 0 { + Value::Ref(entities[(k as usize / 4) % entities.len()]) + } else { + Value::String(format!("v{k}")) + }; + batch.push((e, format!(":a{}", k % 5), value)); + } + pfs.storage().transact(batch, None).unwrap(); + pfs.mark_dirty(); + } + + #[test] + fn test_incremental_saves_keep_indexes_and_checksum_exact() { + let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); + let mut entities = Vec::new(); + for round in 0..25u64 { + let n = 1 + ((round * 37) % 60) as usize; + transact_mixed(&mut pfs, &mut entities, n, round); + pfs.save().unwrap(); + assert!(pfs.fact_prefix_crc.is_some(), "prefix cached after save"); + assert_indexes_and_checksum_exact(&pfs); + } + } + + #[test] + fn test_reopen_after_incremental_saves_takes_no_rebuild() { + use crate::storage::backend::FileBackend; + use tempfile::NamedTempFile; + let tmp = NamedTempFile::new().unwrap(); + let path = tmp.path().to_str().unwrap().to_string(); + let mut entities = Vec::new(); + { + let mut pfs = + PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); + for round in 0..10u64 { + transact_mixed(&mut pfs, &mut entities, 40, round); + pfs.save().unwrap(); + } + } + let mut pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); + // Set only when the full checksum matched on load, i.e. no rebuild. + assert!( + pfs.fact_prefix_crc.is_some(), + "full checksum must match on reopen" + ); + transact_mixed(&mut pfs, &mut entities, 40, 99); + pfs.save().unwrap(); + assert_indexes_and_checksum_exact(&pfs); + } + + #[test] + fn test_prefix_cache_page_count_mismatch_falls_back() { + let mut pfs = PersistentFactStorage::new(MemoryBackend::new(), 256).unwrap(); + let mut entities = Vec::new(); + transact_mixed(&mut pfs, &mut entities, 50, 1); + pfs.save().unwrap(); + pfs.fact_prefix_crc = Some((999, Hasher::new())); + transact_mixed(&mut pfs, &mut entities, 50, 2); + pfs.save().unwrap(); + assert_indexes_and_checksum_exact(&pfs); + } + + #[test] + fn test_prefix_cache_absent_after_rebuild_on_open() { + use crate::storage::backend::FileBackend; + use tempfile::NamedTempFile; + let tmp = NamedTempFile::new().unwrap(); + let path = tmp.path().to_str().unwrap().to_string(); + let mut entities = Vec::new(); + { + let mut pfs = + PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); + for round in 0..3u64 { + transact_mixed(&mut pfs, &mut entities, 30, round); + pfs.save().unwrap(); + } + } + // Corrupt index_checksum (re-sealing the header) to force the rebuild path. + { + let mut backend = FileBackend::open(&path).unwrap(); + let mut page = backend.read_page(0).unwrap(); + page[64] ^= 0xFF; + let cs = compute_header_checksum_from_bytes(&page); + page[80..84].copy_from_slice(&cs.to_le_bytes()); + backend.write_page(0, &page).unwrap(); + backend.sync().unwrap(); + } + let mut pfs = PersistentFactStorage::new(FileBackend::open(&path).unwrap(), 256).unwrap(); + assert!( + pfs.fact_prefix_crc.is_none(), + "no prefix after rebuild-on-open" + ); + transact_mixed(&mut pfs, &mut entities, 30, 7); + pfs.save().unwrap(); + assert_indexes_and_checksum_exact(&pfs); + } + #[test] fn test_page_cache_capacity_reflects_constructed_value() { let zero_cap = PersistentFactStorage::new(MemoryBackend::new(), 0).unwrap(); diff --git a/src/wal.rs b/src/wal.rs index 781bbf77a1..3c611c940a 100644 --- a/src/wal.rs +++ b/src/wal.rs @@ -22,6 +22,7 @@ use crate::db::SyncMode; use crate::error::{ErrorCode, bail_coded, err_coded}; use crate::graph::types::Fact; +use crate::storage::dir_sync::sync_parent_dir; use crate::storage::packed_pages::MAX_FACT_BYTES; use anyhow::Result; use std::fs::{File, OpenOptions}; @@ -148,6 +149,9 @@ impl WalWriter { { Ok(mut file) => { write_wal_header(&mut file)?; + // The header is durable; make the WAL's directory entry + // durable too, or a power loss can lose the whole file (#389). + sync_parent_dir(path)?; file.seek(SeekFrom::End(0))?; return Ok(WalWriter { file, sync_mode }); } @@ -162,7 +166,12 @@ impl WalWriter { // A previous crash landed between this file's creation and its // header write completing; no entry could have been appended // yet, so re-initialize it as a fresh, empty WAL. - WalHeaderState::Absent => write_wal_header(&mut file)?, + // The crash may also have preceded the directory sync that + // follows creation, so repeat it (#389). + WalHeaderState::Absent => { + write_wal_header(&mut file)?; + sync_parent_dir(path)?; + } } file.seek(SeekFrom::End(0))?; Ok(WalWriter { file, sync_mode }) @@ -192,6 +201,9 @@ impl WalWriter { /// Delete the WAL file at `path`. Called after a successful checkpoint. /// + /// Fsyncs the parent directory after the remove, so a power loss cannot + /// bring the deleted WAL back (#389). + /// /// Uses a short retry loop to tolerate Windows races where the OS file handle /// is not immediately released after the `WalWriter` is dropped. pub fn delete_file(path: &Path) -> Result<()> { @@ -200,7 +212,10 @@ impl WalWriter { let mut last_err = None; for i in 0..retries { match std::fs::remove_file(path) { - Ok(()) => return Ok(()), + Ok(()) => { + sync_parent_dir(path)?; + return Ok(()); + } Err(e) => { last_err = Some(e); if i.saturating_add(1) < retries { @@ -740,4 +755,116 @@ mod tests { std::fs::remove_dir(&path).unwrap(); } + + // ── #389: parent-directory fsync ──────────────────────────────────────── + + #[test] + fn test_wal_create_syncs_parent_dir_after_create() { + use crate::storage::dir_sync::take_sync_log; + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("test.wal"); + take_sync_log(); + + let _writer = WalWriter::open_or_create(&path, SyncMode::Full).unwrap(); + + let log = take_sync_log(); + assert_eq!( + log.len(), + 1, + "creating the WAL must sync its directory once" + ); + assert_eq!( + log[0].dir, + dir.path(), + "must sync the WAL's parent directory" + ); + assert!( + log[0].child_existed, + "directory sync must follow the create" + ); + } + + #[test] + fn test_wal_reopen_existing_does_not_sync_parent_dir() { + use crate::storage::dir_sync::take_sync_log; + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("test.wal"); + drop(WalWriter::open_or_create(&path, SyncMode::Full).unwrap()); + take_sync_log(); + + let _writer = WalWriter::open_or_create(&path, SyncMode::Full).unwrap(); + + assert!( + take_sync_log().is_empty(), + "reopening an intact WAL creates nothing, so needs no directory sync" + ); + } + + #[test] + fn test_wal_reinit_headerless_syncs_parent_dir() { + use crate::storage::dir_sync::take_sync_log; + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("test.wal"); + // A crash between `create_new` and the header write leaves a short + // file whose directory entry may never have been synced either. + std::fs::write(&path, b"MW").unwrap(); + take_sync_log(); + + let _writer = WalWriter::open_or_create(&path, SyncMode::Full).unwrap(); + + let log = take_sync_log(); + assert_eq!( + log.len(), + 1, + "re-initializing the WAL must sync its directory" + ); + assert!( + log[0].child_existed, + "directory sync must follow the header write" + ); + } + + #[test] + fn test_wal_delete_syncs_parent_dir_after_remove() { + use crate::storage::dir_sync::take_sync_log; + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("test.wal"); + drop(WalWriter::open_or_create(&path, SyncMode::Full).unwrap()); + take_sync_log(); + + WalWriter::delete_file(&path).unwrap(); + + let log = take_sync_log(); + assert_eq!( + log.len(), + 1, + "deleting the WAL must sync its directory once" + ); + assert_eq!( + log[0].dir, + dir.path(), + "must sync the WAL's parent directory" + ); + assert!( + !log[0].child_existed, + "directory sync must follow the remove" + ); + } + + #[test] + fn test_wal_failed_delete_does_not_sync_parent_dir() { + use crate::storage::dir_sync::take_sync_log; + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("not-a-file.wal"); + std::fs::create_dir(&path).unwrap(); + take_sync_log(); + + assert!(WalWriter::delete_file(&path).is_err(), "delete must fail"); + assert!( + take_sync_log().is_empty(), + "nothing was removed, nothing to sync" + ); + + std::fs::remove_dir(&path).unwrap(); + } } diff --git a/tests/magic_sets_test.rs b/tests/magic_sets_test.rs index 2191b4ab8f..7f035b46fb 100644 --- a/tests/magic_sets_test.rs +++ b/tests/magic_sets_test.rs @@ -306,3 +306,70 @@ fn test_recursive_intermediate_variable_with_keyword_entity() { _ => panic!("expected QueryResults"), } } + +fn extract_keywords(result: QueryResult) -> Vec { + match result { + QueryResult::QueryResults { results, .. } => { + let mut kws: Vec = results + .into_iter() + .map(|row| match &row[0] { + Value::Keyword(k) => k.clone(), + _ => panic!("Expected Keyword in result row"), + }) + .collect(); + kws.sort(); + kws + } + _ => panic!("Expected QueryResults"), + } +} + +/// #297 (reopened) — the intermediate variable is bound by a call to another +/// user-defined rule rather than a fact pattern. The magic propagation rule +/// must keep that call in its body, otherwise `?mid` is unbound in its head. +#[test] +fn test_recursive_intermediate_variable_bound_by_rule_call() { + let db = open_db(); + + exec( + &db, + r#"(transact [[:a :next :b] [:b :next :c] [:x :next :y]])"#, + ); + exec(&db, r#"(rule [(link ?x ?y) [?x :next ?y]])"#); + exec(&db, r#"(rule [(chain ?x ?y) (link ?x ?y)])"#); + exec( + &db, + r#"(rule [(chain ?x ?y) (link ?x ?mid) (chain ?mid ?y)])"#, + ); + + let bound = extract_keywords(exec(&db, r#"(query [:find ?y :where (chain :a ?y)])"#)); + assert_eq!(bound, vec![":b".to_string(), ":c".to_string()]); + + // Same answer as the pattern-bound form, which does not go through magic sets. + let via_pattern = extract_keywords(exec( + &db, + r#"(query [:find ?y :where [?a :next :b] (chain ?a ?y)])"#, + )); + assert_eq!(bound, via_pattern, "magic sets must not change results"); +} + +/// #297 (reopened) — left-recursive variant: the intermediate variable is bound +/// by a preceding recursive call and then fed into another user rule. +#[test] +fn test_left_recursive_intermediate_variable_bound_by_rule_call() { + let db = open_db(); + + exec( + &db, + r#"(transact [[:a :next :b] [:b :next :c] [:x :next :y]])"#, + ); + exec(&db, r#"(rule [(link ?x ?y) [?x :next ?y]])"#); + exec(&db, r#"(rule [(path ?x ?y) (link ?x ?y)])"#); + exec( + &db, + r#"(rule [(path ?x ?y) (path ?x ?mid) (link ?mid ?y)])"#, + ); + + let bound = extract_keywords(exec(&db, r#"(query [:find ?y :where (path :a ?y)])"#)); + assert_eq!(bound, vec![":b".to_string(), ":c".to_string()]); +} diff --git a/tests/point_query_history_test.rs b/tests/point_query_history_test.rs new file mode 100644 index 0000000000..68d9ff3bc1 --- /dev/null +++ b/tests/point_query_history_test.rs @@ -0,0 +1,240 @@ +//! #323 — bound-entity point queries must return exactly what a full scan returns, +//! while only reading the queried attributes' history. +//! +//! Oracle: the same query with `:as-of 1000000000` goes through the full-scan +//! `get_facts_as_of` path (never the selective path) and, since every tx_count in +//! these tests is far below that bound, must produce identical rows. +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::{Minigraf, QueryResult}; + +const ORACLE_AS_OF: &str = ":as-of 1000000000"; + +fn rows(r: QueryResult) -> Vec { + match r { + QueryResult::QueryResults { results, .. } => { + let mut v: Vec = results.iter().map(|row| format!("{row:?}")).collect(); + v.sort(); + v + } + _ => panic!("expected QueryResults"), + } +} + +/// Run `(query [:find :where ])` via the selective path and via +/// the full-scan oracle; assert equal; return the selective rows. +fn same_as_full_scan(db: &Minigraf, find: &str, opts: &str, body: &str) -> Vec { + let selective = rows( + db.execute(&format!("(query [:find {find} {opts} :where {body}])")) + .unwrap(), + ); + let oracle = rows( + db.execute(&format!( + "(query [:find {find} {ORACLE_AS_OF} {opts} :where {body}])" + )) + .unwrap(), + ); + assert_eq!(selective, oracle, "selective path diverged from full scan"); + selective +} + +fn churn(db: &Minigraf, depth: usize) { + db.execute("(transact [[:e/hot :other \"o\"]])").unwrap(); + db.execute("(transact {:valid-from \"2020-01-01T00:00:00Z\"} [[:e/hot :hash \"h0\"]])") + .unwrap(); + for i in 1..depth { + db.execute(&format!("(retract [[:e/hot :hash \"h{}\"]])", i - 1)) + .unwrap(); + db.execute(&format!( + "(transact {{:valid-from \"2020-01-01T00:00:00Z\"}} [[:e/hot :hash \"h{i}\"]])" + )) + .unwrap(); + } +} + +#[test] +fn churned_attribute_live_value_in_memory() { + let db = Minigraf::in_memory().unwrap(); + churn(&db, 50); + let r = same_as_full_scan(&db, "?v", "", "[:e/hot :hash ?v]"); + assert_eq!(r.len(), 1, "exactly one live value"); + assert!(r[0].contains("h49")); + let r = same_as_full_scan(&db, "?v", "", "[:e/hot :other ?v]"); + assert_eq!(r.len(), 1); +} + +#[test] +fn churned_attribute_live_value_file_backed() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + { + let db = Minigraf::open(&path).unwrap(); + churn(&db, 30); + db.checkpoint().unwrap(); + // Pending on top of committed: more churn after the checkpoint, + // including reasserting a previously retracted value. + db.execute("(retract [[:e/hot :hash \"h29\"]])").unwrap(); + db.execute("(transact {:valid-from \"2020-01-01T00:00:00Z\"} [[:e/hot :hash \"h3\"]])") + .unwrap(); + let r = same_as_full_scan(&db, "?v", "", "[:e/hot :hash ?v]"); + assert_eq!(r.len(), 1); + assert!(r[0].contains("\"h3\"")); + } + let db = Minigraf::open(&path).unwrap(); + let r = same_as_full_scan(&db, "?v", "", "[:e/hot :hash ?v]"); + assert_eq!(r.len(), 1); + assert!(r[0].contains("\"h3\"")); +} + +#[test] +fn two_attributes_on_one_entity() { + let db = Minigraf::in_memory().unwrap(); + churn(&db, 10); + let r = same_as_full_scan(&db, "?h ?o", "", "[:e/hot :hash ?h] [:e/hot :other ?o]"); + assert_eq!(r.len(), 1); +} + +#[test] +fn five_attributes_on_one_entity() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:e/x :a 1] [:e/x :b 2] [:e/x :c 3] [:e/x :d 4] [:e/x :f 5]])") + .unwrap(); + let r = same_as_full_scan( + &db, + "?a ?b ?c ?d ?f", + "", + "[:e/x :a ?a] [:e/x :b ?b] [:e/x :c ?c] [:e/x :d ?d] [:e/x :f ?f]", + ); + assert_eq!(r.len(), 1); +} + +#[test] +fn bound_entity_variable_attribute_sees_all() { + let db = Minigraf::in_memory().unwrap(); + churn(&db, 5); + let r = same_as_full_scan(&db, "?a ?v", "", "[:e/hot ?a ?v]"); + assert_eq!(r.len(), 2, ":hash h4 and :other o"); + // Mixed: one narrowed pattern + one variable-attribute pattern on the same entity. + let r = same_as_full_scan(&db, "?a ?h", "", "[:e/hot :hash ?h] [:e/hot ?a _]"); + assert_eq!(r.len(), 2); +} + +#[test] +fn bound_entity_pseudo_attribute_matches_full_scan() { + let db = Minigraf::in_memory().unwrap(); + churn(&db, 5); + same_as_full_scan( + &db, + "?v ?vf", + ":any-valid-time", + "[:e/hot :hash ?v] [:e/hot :db/valid-from ?vf]", + ); +} + +#[test] +fn not_and_or_on_narrowed_entity() { + let db = Minigraf::in_memory().unwrap(); + churn(&db, 5); + db.execute("(transact [[:e/hot :flag true]])").unwrap(); + same_as_full_scan( + &db, + "?v", + "", + "[:e/hot :hash ?v] (not [:e/hot :flag false])", + ); + let r = same_as_full_scan(&db, "?v", "", "[:e/hot :hash ?v] (not [:e/hot :flag true])"); + assert!( + r.is_empty(), + "not must see :flag although only :hash is projected" + ); + same_as_full_scan(&db, "?v", "", "(or [:e/hot :hash ?v] [:e/hot :other ?v])"); +} + +#[test] +fn prefix_sibling_attribute_not_leaked() { + let dir = tempfile::tempdir().unwrap(); + let db = Minigraf::open(dir.path().join("p.graph")).unwrap(); + db.execute("(transact [[:e/x :hash \"a\"] [:e/x :hash2 \"b\"] [:e/x :hash/sub \"c\"]])") + .unwrap(); + db.checkpoint().unwrap(); + db.execute("(transact [[:e/x :hashx \"d\"]])").unwrap(); + let r = same_as_full_scan(&db, "?v", "", "[:e/x :hash ?v]"); + assert_eq!(r.len(), 1); + assert!(r[0].contains("\"a\"")); +} + +#[test] +fn entity_and_attribute_patterns_mixed() { + let db = Minigraf::in_memory().unwrap(); + churn(&db, 5); + db.execute("(transact [[:e/a :hash \"z\"]])").unwrap(); + same_as_full_scan(&db, "?e ?v ?o", "", "[?e :hash ?v] [:e/hot :other ?o]"); +} + +#[test] +fn valid_at_past_on_churned_attribute() { + let db = Minigraf::in_memory().unwrap(); + db.execute( + "(transact {:valid-from \"2020-01-01T00:00:00Z\" :valid-to \"2021-01-01T00:00:00Z\"} [[:e/v :hash \"old\"]])", + ) + .unwrap(); + db.execute("(transact {:valid-from \"2021-01-01T00:00:00Z\"} [[:e/v :hash \"new\"]])") + .unwrap(); + db.execute("(transact [[:e/v :other 1]])").unwrap(); + let r = same_as_full_scan( + &db, + "?v", + ":valid-at \"2020-06-01T00:00:00Z\"", + "[:e/v :hash ?v]", + ); + assert_eq!(r.len(), 1); + assert!(r[0].contains("old")); +} + +/// One WriteTransaction writing the same (entity, attribute) in two valid-time +/// windows gives both facts the same tx_count. The selective path used to dedup on +/// (entity, attribute, tx_count, asserted) and silently drop one window's row; it +/// must match a full scan (#323 review). +#[test] +fn same_transaction_multi_window_matches_full_scan() { + let db = Minigraf::in_memory().unwrap(); + let mut tx = db.begin_write().unwrap(); + tx.execute(r#"(transact {:valid-from "2020-01-01T00:00:00Z" :valid-to "2021-01-01T00:00:00Z"} [[:e/w :x 1]])"#) + .unwrap(); + tx.execute(r#"(transact {:valid-from "2021-01-01T00:00:00Z"} [[:e/w :x 2]])"#) + .unwrap(); + tx.commit().unwrap(); + let r = same_as_full_scan(&db, "?v", ":any-valid-time", "[:e/w :x ?v]"); + assert_eq!(r.len(), 2, "both windows' values must be returned"); +} + +/// #381 — attribute-bound scans (`[?e :a ?v]`) over a checkpointed file return exactly +/// the queried attribute, including non-ASCII names whose last UTF-8 byte is 0xBF +/// (`:丿`, `:ÿ`) and ordinary names with prefix siblings (`:a` vs `:ab`, `:a/b`). +#[test] +fn attribute_scan_exact_for_non_ascii_and_prefix_siblings_file_backed() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("t.graph"); + let attrs = [":a", ":ab", ":a/b", ":丿", ":丿x", ":乀", ":ÿ", ":ÿx", ":Ā"]; + let db = Minigraf::open(&path).unwrap(); + for (i, attr) in attrs.iter().enumerate() { + db.execute(&format!("(transact [[:e/c{i} {attr} \"c{i}\"]])")) + .unwrap(); + } + db.checkpoint().unwrap(); + // Pending on top of committed. + for (i, attr) in attrs.iter().enumerate() { + db.execute(&format!("(transact [[:e/p{i} {attr} \"p{i}\"]])")) + .unwrap(); + } + for (i, attr) in attrs.iter().enumerate() { + let r = same_as_full_scan(&db, "?e ?v", "", &format!("[?e {attr} ?v]")); + assert_eq!( + r.len(), + 2, + "one committed and one pending fact per attribute" + ); + assert!(r.iter().any(|row| row.contains(&format!("\"c{i}\"")))); + assert!(r.iter().any(|row| row.contains(&format!("\"p{i}\"")))); + } +}