Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
14 changes: 14 additions & 0 deletions CHANGELOG.md
Original file line number Diff line number Diff line change
Expand Up @@ -5,6 +5,20 @@ All notable changes to this project will be documented in this file.
The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/),
and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).

## 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 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.

### Fixed

- **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.

### 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.

## v2.0.1 — 2026-09-25

Patch release on the v2.x line. File format is unchanged (v7); no API changes.
Expand Down
4 changes: 2 additions & 2 deletions CLAUDE.md
Original file line number Diff line number Diff line change
Expand Up @@ -101,7 +101,7 @@ 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` v7 (84 bytes), `CommittedFactReader` / `CommittedIndexReader` traits
Expand Down Expand Up @@ -167,7 +167,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint.

## Test Coverage

**1154 tests passing** (1146 passing, 8 ignored; unit + integration + doc).
**1173 tests passing** (1165 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.
Expand Down
2 changes: 1 addition & 1 deletion README.md
Original file line number Diff line number Diff line change
Expand Up @@ -92,7 +92,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit

```bash
cargo run # interactive Datalog REPL
cargo test # run 1154 tests
cargo test # run 1173 tests
cargo run < demos/demo_recursive.txt # recursive rules demo
```

Expand Down
51 changes: 50 additions & 1 deletion benches/minigraf_bench.rs
Original file line number Diff line number Diff line change
Expand Up @@ -1582,6 +1582,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) {
Expand Down Expand Up @@ -1752,6 +1800,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);
20 changes: 20 additions & 0 deletions docs/BENCHMARKS.md
Original file line number Diff line number Diff line change
Expand Up @@ -30,6 +30,26 @@ 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.

## 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.
Expand Down
6 changes: 3 additions & 3 deletions docs/TEST_COVERAGE.md
Original file line number Diff line number Diff line change
Expand Up @@ -2,11 +2,11 @@

## v2.0.1 Coverage Summary

**Verified**: 2026-09-25 with `cargo test`
**Verified**: 2026-09-26 with `cargo test`

**Result**: 1,146 passing tests and 8 ignored tests (1,154 total)
**Result**: 1,165 passing tests and 8 ignored tests (1,173 total)

The v2.0.1 suite covers the public database API, the Datalog engine, storage and recovery paths, and the v2.0.0 locking and structured-error-code changes, plus v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370).
The v2.0.1 suite covers the public database API, the Datalog engine, storage and recovery paths, and the v2.0.0 locking and structured-error-code changes, plus v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Since v2.0.1, `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).

### Covered Areas

Expand Down
Loading
Loading