adityamukho · Oct 6, 2026 · Oct 6, 2026 · Oct 6, 2026 · Oct 6, 2026 · Oct 6, 2026
@@ -24,3 +24,8 @@ jobs:
         run: cargo test --test smoke_test -- --include-ignored --nocapture
         env:
           RUST_BACKTRACE: 1
+
+      - name: Size per fact at 1M facts (spec §11)
+        run: cargo test --lib size_per_fact_in_433_shape_1m -- --include-ignored --nocapture
+        env:
+          RUST_BACKTRACE: 1
@@ -13,6 +13,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - **Crash-atomic checkpoints with verified pages** (v8 storage format, PR 2 of 5; #374, #388). Two alternating meta pages replace the 84-byte file header and are the only commit point: a checkpoint writes only pages the last commit does not use, syncs, then writes the other meta page and syncs. A crash or torn write at any point leaves the previous checkpoint intact, so opening never rebuilds an index, and the whole-file index checksum is gone. Every other page carries a 24-byte header (type, CRC32, its own page id, the checkpoint generation that wrote it), checked on every read: a torn, corrupted, misplaced or stale page now fails with `STG-029`, `STG-030` or `STG-031` instead of being read. If the newest meta page is damaged after its WAL was already deleted, open fails with `STG-033` rather than silently going back to the previous checkpoint. New codes `STG-029`–`STG-035`. The WAL header gains a base generation (WAL version 2); a v2.x WAL beside a migrated file is still replayed. Pages freed by a checkpoint are reused by later ones. Files written by a v3.0.0 development build before this change fail with `STG-032`.
 - **Covering indexes with dictionary-coded keys** (v8 storage format, PR 3 of 5; #433). Every index entry now holds the whole fact as a byte-comparable key, so a query reads only index pages, never a separate fact page. Entities and idents (attribute names and keyword values) get sequential internal ids from a dictionary stored in the file, and strings longer than 64 bytes are stored once in value pages and deduplicated. Fact pages are gone. A file with 100,000 facts (10 attributes per entity) takes 88 bytes per fact, down from 314. Facts from committed data now come back in internal-id order (entity, then attribute) rather than insertion or UUID order; query results are sets, and code that relied on an order must sort. New codes `STG-036` (dictionary entry missing) and `STG-037` (one transaction with two timestamps: a checkpoint or v7 upgrade refuses to change a stored timestamp). Files written by a v3.0.0 development build before this change fail with `STG-032`.
 - **Checkpoints cost what changed, not the size of the database** (v8 storage format, PR 4 of 5; #434). A checkpoint now inserts copy-on-write: it rewrites only the index leaves that receive new facts and their paths to the root, and reuses pages freed by earlier checkpoints through a free list it reads and extends only as far as it needs. A checkpoint after one new fact takes 3.1 ms on a 10,000-fact file and 3.3 ms on a 100,000-fact file (it took 15.5 ms and 43 ms before, and grew with the file). One new fact at 100,000 facts writes 16 pages. The `checkpoint()` and `wal_checkpoint_threshold` docs now describe this cost.
+- **A damaged page is reported, not worked around** (v8 storage format, PR 5 of 5). A query whose indexed lookup reaches a damaged page now fails with that page's `STG-029`/`STG-030`/`STG-031`. Before, the query fell back to a full scan, which could hide the damage. Tests damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every read or checkpoint that reaches the page fails, and the file still opens at its last checkpoint. Measured at 1.15M facts in #433's shape: 142 bytes per fact, history included. A checkpoint after one new fact takes 6.1 ms at 1M facts. Concurrent point queries are 19–31 % faster than before this change: reads reuse the entity and attribute the caller passed, and share cached ident and timestamp lookups.
 - **Size limits for file-backed databases:** a string value may be up to 4,068 bytes, whatever the rest of the fact, and an attribute name or keyword value up to 1,024 bytes. Both are checked when the transaction is written and fail with `WAL-003`, whose message now names the value. This replaces the 4,080-byte limit on a whole serialised fact (4,052 in earlier v3.0.0 development builds). In-memory databases have no limit.
 - **Formats v1–v6 are no longer readable.** Opening one fails with the new `STG-028`; open it once with Minigraf v2.x to upgrade it to v7 first. `STG-003` and `STG-004` are deprecated (no longer emitted, still registered, never reused). `STG-005` and `STG-006` message text changed.
 

@@ -193,7 +193,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are
 
 ## Test Coverage
 
-**1230 tests** (1222 passing, 8 ignored; unit + integration + doc).
+**1236 tests** (1227 passing, 9 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.

@@ -105,7 +105,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit
 
 ```bash
 cargo run          # interactive Datalog REPL
-cargo test         # run 1230 tests
+cargo test         # run 1236 tests
 cargo run < demos/demo_recursive.txt   # recursive rules demo
 ```
 

@@ -41,8 +41,12 @@ This was the GitHub milestone named “2.0” before v2.0.0 used that version nu
 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)
+- v8 storage format, done on `v3` in five PRs (#374, #434, #388, #433):
+  - per-page CRC32, page id and generation on every page (#388);
+  - two alternating meta pages; crash-atomic, copy-on-write checkpoints whose cost follows the change (#374, #434);
+  - covering byte-comparable keys with a dictionary and deduplicated long values, at about 142 bytes per fact (#433).
+
+  The format is frozen for the golden-file corpus (#391).
 - 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)

@@ -425,7 +425,7 @@ fn bench_checkpoint_after_1_fact(c: &mut Criterion) {
 
     let mut group = c.benchmark_group("checkpoint/after_1_fact");
     group.sample_size(20);
-    for &(label, n) in &[("10k", 10_000usize), ("100k", 100_000)] {
+    for &(label, n) in &[("10k", 10_000usize), ("100k", 100_000), ("1m", 1_000_000)] {
         let tmp = NamedTempFile::new().unwrap();
         let path = tmp.path().to_str().unwrap().to_string();
         helpers::populate_file_no_checkpoint(n, &path);
@@ -449,6 +449,46 @@ fn bench_checkpoint_after_1_fact(c: &mut Criterion) {
     group.finish();
 }
 
+// ── checkpoint/after_100k_facts (#434) ───────────────────────────────────────
+
+/// Checkpoint cost after 100,000 new facts on an already-checkpointed graph of
+/// `n` facts. With copy-on-write checkpoints the cost follows the 100,000 new
+/// facts, not `n`. Each sample adds 100,000 more facts, so the graph grows by
+/// the sample count over the run.
+fn bench_checkpoint_after_100k_facts(c: &mut Criterion) {
+    use criterion::BatchSize;
+    use tempfile::NamedTempFile;
+
+    let mut group = c.benchmark_group("checkpoint/after_100k_facts");
+    group.sample_size(10);
+    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 round = 0u64;
+        group.bench_function(BenchmarkId::from_parameter(label), |b| {
+            b.iter_batched(
+                || {
+                    round += 1;
+                    for chunk in 0..100u64 {
+                        let mut cmd = String::from("(transact [");
+                        for i in 0..1_000u64 {
+                            cmd.push_str(&format!("[:ck{round}_{chunk}_{i} :val {i}]"));
+                        }
+                        cmd.push_str("])");
+                        db.execute(&cmd).unwrap();
+                    }
+                },
+                |()| db.checkpoint().unwrap(),
+                BatchSize::PerIteration,
+            );
+        });
+    }
+    group.finish();
+}
+
 // ── Task 10: concurrent/ ─────────────────────────────────────────────────────
 
 fn bench_concurrent(c: &mut Criterion) {
@@ -1828,6 +1868,7 @@ criterion_group!(
     bench_open,
     bench_checkpoint,
     bench_checkpoint_after_1_fact,
+    bench_checkpoint_after_100k_facts,
     bench_concurrent,
     bench_concurrent_file,
     bench_concurrent_btree_scan,