From f4207bc8c7d42cc395ebd58e53f56d0db9fcc2ec Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 18:14:20 +0530 Subject: [PATCH 01/12] docs: design spec for point-query history scan mitigation (#323) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- ...6-09-25-point-query-history-scan-design.md | 168 ++++++++++++++++++ 1 file changed, 168 insertions(+) create mode 100644 docs/superpowers/specs/2026-09-25-point-query-history-scan-design.md 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..1c9383e0e1 --- /dev/null +++ b/docs/superpowers/specs/2026-09-25-point-query-history-scan-design.md @@ -0,0 +1,168 @@ +# 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)>` | ~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 by ≥3× on the churned attribute itself. +- 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). +- Lookup count = Σ over entities of (1 if `None` else number of attributes) + number of + attribute-only lookups; compared against the existing `threshold` (4). Over threshold → + `None` (full scan), as today. +- 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 Dedup only when sources can overlap + +- If exactly one lookup is issued, its facts are returned without the `seen` set: a single + index range scan cannot yield the same record twice. +- With ≥2 lookups the dedup stays with the same key `(entity, attribute, tx_count, + asserted)`, but the `HashSet` uses `FxBuildHasher` from §4.3. + +### 4.3 Cheaper `net_asserted_facts` + +- Add a small in-crate FxHash-style hasher (`FxHasher` + `type FxBuildHasher = + BuildHasherDefault`) in a new private module `src/graph/fxhash.rs` + (~30 lines, no dependency). Word-at-a-time multiply-rotate as in rustc's FxHash. +- 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, FxBuildHasher>`. + 3. `by_window: HashMap<(&Uuid, &str, &[u8], i64, i64), usize, FxBuildHasher>` 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: not a concern — keys are the embedding application's own data, in-process. + +## 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 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. +- `[:e/hot :hash ?v]` and `[?e :hash ?v]` at depth 2000 ≥3× faster than the baseline in §1. +- Full suite green; clippy/fmt clean. + +## 6. Follow-up: v3 structural fix (separate issue, 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. From 0e3e361f4fd5a75c9b00a76ccd139d4c5a6a769c Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 23:26:12 +0530 Subject: [PATCH 02/12] docs: implementation plan for #323; spec: drop dedup, threshold collapse Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- .../2026-09-25-point-query-history-scan.md | 1096 +++++++++++++++++ ...6-09-25-point-query-history-scan-design.md | 29 +- 2 files changed, 1115 insertions(+), 10 deletions(-) create mode 100644 docs/superpowers/plans/2026-09-25-point-query-history-scan.md 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/specs/2026-09-25-point-query-history-scan-design.md b/docs/superpowers/specs/2026-09-25-point-query-history-scan-design.md index 1c9383e0e1..46b472fa56 100644 --- 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 @@ -30,7 +30,7 @@ entity-wide, not attribute-wide. |---|---:| | `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)>` | ~16% | +| `selective_fact_fetch` dedup `HashSet<(Uuid, String, u64, bool)>` (redundant — §4.2) | ~16% | It is CPU overhead per dead record, not I/O. @@ -82,9 +82,12 @@ pub(crate) fn get_facts_by_entity_attribute_indexed( 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). -- Lookup count = Σ over entities of (1 if `None` else number of attributes) + number of - attribute-only lookups; compared against the existing `threshold` (4). Over threshold → - `None` (full scan), as today. +- 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. @@ -94,12 +97,17 @@ filter is per-fact, so restricting input to one `(e, a)` never splits a group. `or-join`, so every attribute any clause could match on that entity is fetched. Rule-using queries never reach this path. -### 4.2 Dedup only when sources can overlap +### 4.2 Remove the executor dedup -- If exactly one lookup is issued, its facts are returned without the `seen` set: a single - index range scan cannot yield the same record twice. -- With ≥2 lookups the dedup stays with the same key `(entity, attribute, tx_count, - asserted)`, but the `HashSet` uses `FxBuildHasher` from §4.3. +`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` @@ -129,7 +137,8 @@ TDD; correctness first, then measurement. - `:a` vs `:ab` prefix isolation; - other entities / other attributes excluded. -**`net_asserted_facts` tests**: existing tests keep passing; add a property-style test +**`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. From 135a2668232f549ccdb2f976790a7bd1f2fc5901 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 23:32:53 +0530 Subject: [PATCH 03/12] perf: add in-crate FxHash hasher for hot-path maps (#323) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- src/graph/fxhash.rs | 101 ++++++++++++++++++++++++++++++++++++++++++++ src/graph/mod.rs | 1 + 2 files changed, 102 insertions(+) create mode 100644 src/graph/fxhash.rs diff --git a/src/graph/fxhash.rs b/src/graph/fxhash.rs new file mode 100644 index 0000000000..d61465acb9 --- /dev/null +++ b/src/graph/fxhash.rs @@ -0,0 +1,101 @@ +//! 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); + } +} diff --git a/src/graph/mod.rs b/src/graph/mod.rs index 714f8b021e..2eebb7e7d1 100644 --- a/src/graph/mod.rs +++ b/src/graph/mod.rs @@ -1,3 +1,4 @@ +pub(crate) mod fxhash; pub(crate) mod storage; pub(crate) mod types; From d0a63259a6a16cd69591f56b07762a6b20830082 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 23:34:36 +0530 Subject: [PATCH 04/12] perf: borrow keys and use FxHash in net_asserted_facts (#323) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- src/graph/storage.rs | 290 +++++++++++++++++++++++++++++++++++-------- 1 file changed, 236 insertions(+), 54 deletions(-) diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 74c9405d78..7cb14d6902 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, and use +/// [`FxBuildHasher`](crate::graph::fxhash::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. /// -/// - `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 crate::graph::fxhash::FxBuildHasher; 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, 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); } - } 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() } @@ -1893,4 +1891,188 @@ 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"]); + } } From 56479f71d122dcb8dd834b970ee9010703961d48 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 23:35:15 +0530 Subject: [PATCH 05/12] perf: add (entity, attribute) EAVT range lookup (#323) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- src/graph/storage.rs | 188 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 188 insertions(+) diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 7cb14d6902..948276f803 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -682,6 +682,71 @@ impl FactStorage { Ok(facts) } + /// 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: 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, 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) + } + /// 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; @@ -2075,4 +2140,127 @@ mod tests { 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)); + } } From 269549652a8f982c9a199a80067adb4f487e16cf Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 23:37:04 +0530 Subject: [PATCH 06/12] perf: narrow bound-entity fetch to queried attributes, drop redundant dedup (#323) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- src/query/datalog/executor.rs | 110 ++++++++++------- tests/point_query_history_test.rs | 192 ++++++++++++++++++++++++++++++ 2 files changed, 256 insertions(+), 46 deletions(-) create mode 100644 tests/point_query_history_test.rs diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index dfaa16aacc..1b33b03541 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -368,17 +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)`. + /// 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; + use std::collections::{BTreeMap, BTreeSet}; - let mut entity_ids: HashSet = HashSet::new(); - let mut attributes: HashSet = HashSet::new(); + // 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 { @@ -388,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; } @@ -399,54 +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; } - // Dedup key: (entity uuid, attribute string, tx_count, asserted) — avoids Value debug - // formatting. Including `asserted` ensures that a retraction and an assertion committed in - // the same WriteTransaction (same tx_count) are both retained, since they differ only by - // the `asserted` flag. - let mut seen: HashSet<(uuid::Uuid, String, u64, bool)> = 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, + 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, - ); - 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) @@ -3891,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/tests/point_query_history_test.rs b/tests/point_query_history_test.rs new file mode 100644 index 0000000000..f4b3c6f1c3 --- /dev/null +++ b/tests/point_query_history_test.rs @@ -0,0 +1,192 @@ +//! #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")); +} From 30627fc60950ae187d0bc8b63fafb50ea804ca5e Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 23:39:12 +0530 Subject: [PATCH 07/12] perf: rotate FxHasher output so hashbrown's low-bit bucket index is mixed (#323) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- src/graph/fxhash.rs | 23 +++++++++++++++++++++-- 1 file changed, 21 insertions(+), 2 deletions(-) diff --git a/src/graph/fxhash.rs b/src/graph/fxhash.rs index d61465acb9..f4d894900b 100644 --- a/src/graph/fxhash.rs +++ b/src/graph/fxhash.rs @@ -1,6 +1,7 @@ //! Small non-cryptographic hasher for internal hot-path hash maps (#323). //! -//! Same multiply-rotate scheme as rustc's `FxHasher`. Not HashDoS-resistant; +//! Same multiply-rotate scheme as rustc's `FxHasher`, plus rustc-hash 2.x's +//! final rotation so hashbrown's low-bit bucket index is well mixed. 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. @@ -60,9 +61,12 @@ impl Hasher for FxHasher { self.add_to_hash(i); } + /// The multiply only propagates entropy upwards, but hashbrown takes the + /// bucket index from the low bits; rotating moves the well-mixed high bits + /// down (same fix as rustc-hash 2.x). #[inline] fn finish(&self) -> u64 { - self.hash + self.hash.rotate_left(26) } } @@ -98,4 +102,19 @@ mod tests { let s: HashSet = (0..1000).collect(); assert_eq!(s.len(), 1000); } + + /// hashbrown picks the bucket from the hash's low bits. Keys that differ only + /// in the upper bytes of their last word (e.g. "h0001".."h1024") must still + /// spread across low bits, or every probe collides (#323). + #[test] + fn low_bits_spread_for_keys_differing_in_high_bytes() { + let b = FxBuildHasher::default(); + let buckets: HashSet = (0..1024) + .map(|i| b.hash_one(format!("h{i:04}").as_str()) & 0x3ff) + .collect(); + assert!( + buckets.len() > 512, + "low 10 bits should take most of 1024 values" + ); + } } From ab56899d599a4ee989d83d6b9ab50dc5eb85f6ff Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 25 Sep 2026 23:40:55 +0530 Subject: [PATCH 08/12] bench: point_query_chain_depth (#323) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- benches/minigraf_bench.rs | 51 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 50 insertions(+), 1 deletion(-) diff --git a/benches/minigraf_bench.rs b/benches/minigraf_bench.rs index e8f27bc8d8..d4b901a7c1 100644 --- a/benches/minigraf_bench.rs +++ b/benches/minigraf_bench.rs @@ -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) { @@ -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); From 613aef6b1a37a6c43dae82513bb9118226f5c546 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 26 Sep 2026 00:01:41 +0530 Subject: [PATCH 09/12] docs: changelog, benchmarks and test counts for #323; revise spec acceptance to measured Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- CHANGELOG.md | 6 ++++++ CLAUDE.md | 5 +++-- README.md | 2 +- docs/BENCHMARKS.md | 20 +++++++++++++++++++ docs/TEST_COVERAGE.md | 6 +++--- ...6-09-25-point-query-history-scan-design.md | 14 +++++++++---- 6 files changed, 43 insertions(+), 10 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 1da1272b15..cbcc6dd48d 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -5,6 +5,12 @@ 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: at 2,000 retract/reassert cycles on a sibling attribute, it drops from 4.67 ms to 18.6 µs. Reading the heavily rewritten attribute itself, and attribute scans (`[?e :attr ?v]`), are about 1.6× faster (4.66 ms → 2.88 ms) from cheaper net-assert grouping and removing a redundant dedup pass. File format and query results are unchanged. 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. diff --git a/CLAUDE.md b/CLAUDE.md index bcec61ef7f..1c33b322ab 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -101,7 +101,8 @@ 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` + - `fxhash.rs`: `FxBuildHasher` — in-crate non-cryptographic hasher for hot-path maps (#323) 2. **`src/storage/`** — Persistence layer - `mod.rs`: `StorageBackend` trait, `FileHeader` v7 (84 bytes), `CommittedFactReader` / `CommittedIndexReader` traits @@ -167,7 +168,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). +**1175 tests passing** (1167 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. diff --git a/README.md b/README.md index 7e2a6e24ad..229e7577c8 100644 --- a/README.md +++ b/README.md @@ -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 1175 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index af74770b4e..7e692b41d7 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -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. + +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.1 µs | 18.6 µs | +| | 500 | 1.17 ms | 737 µs | +| | 2000 | 4.66 ms | 2.88 ms | +| `[:e/hot :other ?v]` (sibling attribute) | 1 | 20.2 µs | 19.4 µs | +| | 500 | 1.18 ms | 20.5 µs | +| | 2000 | 4.67 ms | 18.6 µs | +| `[?e :hash ?v]` (attribute scan) | 1 | 17.7 µs | 17.9 µs | +| | 500 | 1.16 ms | 721 µs | +| | 2000 | 4.57 ms | 2.87 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. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 3e5a9a8739..a1aaf97df9 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -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,167 passing tests and 8 ignored tests (1,175 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 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 index 46b472fa56..01ea5a9313 100644 --- 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 @@ -45,7 +45,8 @@ and narrow the scan to the queried attribute. **Goals** - Other attributes on a churned entity no longer pay for that entity's churn. -- Constant factor per history record cut by ≥3× on the churned attribute itself. +- 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. @@ -160,11 +161,16 @@ All assert messages follow the CLAUDE.md testing convention (no `{:?}` of UUID-b Record before/after numbers in the PR and `docs/BENCHMARKS.md`. **Acceptance:** -- `[:e/hot :other ?v]` at depth 2000 within 2× of depth 1. -- `[:e/hot :hash ?v]` and `[?e :hash ?v]` at depth 2000 ≥3× faster than the baseline in §1. +- `[:e/hot :other ?v]` at depth 2000 within 2× of depth 1. **Met**: 18.6 µs vs 19.4 µs. +- `[:e/hot :hash ?v]` and `[?e :hash ?v]` at depth 2000 faster than baseline. Original + target ≥3×; **measured 1.62× / 1.59×** (criterion, bench profile with LTO and + `opt-level = "z"`: 4.66 → 2.88 ms, 4.57 → 2.87 ms). Revised to the measured numbers on + 2026-09-26 and shipped as a mitigation. The remaining cost is per-record fact resolve + + decode (~31%), EAVT leaf-key decode (~22%) and `net_asserted_facts` (~27%) — the + first two are inherent to v7 keys; see §6 / #379. - Full suite green; clippy/fmt clean. -## 6. Follow-up: v3 structural fix (separate issue, milestone v3.0.0) +## 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: From 5b9f43a03b83d5984db85008cc5874195eefc707 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 26 Sep 2026 00:09:46 +0530 Subject: [PATCH 10/12] fix: bound (entity, attribute) EAVT scan exactly; pin same-tx multi-window fix (#323) End the committed range at attribute + NUL (exact successor) instead of incrementing the last byte, which returned None for attributes ending in 0x7F or a 0xBF UTF-8 byte and left the scan unbounded to the end of the index. Also stops resolving prefix siblings. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- CHANGELOG.md | 10 ++- src/graph/storage.rs | 105 ++++++++++++++++++++++++++---- tests/point_query_history_test.rs | 17 +++++ 3 files changed, 120 insertions(+), 12 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index cbcc6dd48d..dbc85f8c1a 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -9,7 +9,15 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### 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: at 2,000 retract/reassert cycles on a sibling attribute, it drops from 4.67 ms to 18.6 µs. Reading the heavily rewritten attribute itself, and attribute scans (`[?e :attr ?v]`), are about 1.6× faster (4.66 ms → 2.88 ms) from cheaper net-assert grouping and removing a redundant dedup pass. File format and query results are unchanged. 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. +- **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: at 2,000 retract/reassert cycles on a sibling attribute, it drops from 4.67 ms to 18.6 µs. Reading the heavily rewritten attribute itself, and attribute scans (`[?e :attr ?v]`), are about 1.6× faster (4.66 ms → 2.88 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 diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 948276f803..798cac97ad 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -684,10 +684,9 @@ impl FactStorage { /// 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`). + /// 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, @@ -713,15 +712,17 @@ impl FactStorage { 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 { + // 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: *entity_id, - attribute: next_attr, + attribute: format!("{attribute}\0"), valid_from: i64::MIN, valid_to: i64::MIN, tx_count: 0, - }); + }; let mut facts = Vec::new(); @@ -734,9 +735,10 @@ impl FactStorage { facts.push(resolve_fact_ref(&d, fr)?); } - // Committed: on-disk B+tree range scan, post-filtered on the exact pair. + // 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, end_opt.as_ref())? { + for fr in reader.range_scan_eavt(&start, Some(&end))? { let fact = resolve_fact_ref(&d, fr)?; if matches(&fact) { facts.push(fact); @@ -2263,4 +2265,85 @@ mod tests { 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" + ); + } + } } diff --git a/tests/point_query_history_test.rs b/tests/point_query_history_test.rs index f4b3c6f1c3..26878311bc 100644 --- a/tests/point_query_history_test.rs +++ b/tests/point_query_history_test.rs @@ -190,3 +190,20 @@ fn valid_at_past_on_churned_attribute() { 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"); +} From 49e31b8edfce30790f7ea89e860d251ab040d01f Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 26 Sep 2026 08:44:40 +0530 Subject: [PATCH 11/12] perf: keep std's keyed hasher in net_asserted_facts; drop FxHash (#323) Fact values are often untrusted text (agent memory); a fixed-seed fast hash would let crafted colliding values make queries quadratic. The borrowed-key / encode-once rewrite stays. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- CLAUDE.md | 1 - src/graph/fxhash.rs | 120 ------------------------------------------- src/graph/mod.rs | 1 - src/graph/storage.rs | 10 ++-- 4 files changed, 5 insertions(+), 127 deletions(-) delete mode 100644 src/graph/fxhash.rs diff --git a/CLAUDE.md b/CLAUDE.md index 1c33b322ab..682b8ecf06 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -102,7 +102,6 @@ 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`, `get_facts_by_entity_attribute_indexed` - - `fxhash.rs`: `FxBuildHasher` — in-crate non-cryptographic hasher for hot-path maps (#323) 2. **`src/storage/`** — Persistence layer - `mod.rs`: `StorageBackend` trait, `FileHeader` v7 (84 bytes), `CommittedFactReader` / `CommittedIndexReader` traits diff --git a/src/graph/fxhash.rs b/src/graph/fxhash.rs deleted file mode 100644 index f4d894900b..0000000000 --- a/src/graph/fxhash.rs +++ /dev/null @@ -1,120 +0,0 @@ -//! Small non-cryptographic hasher for internal hot-path hash maps (#323). -//! -//! Same multiply-rotate scheme as rustc's `FxHasher`, plus rustc-hash 2.x's -//! final rotation so hashbrown's low-bit bucket index is well mixed. 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); - } - - /// The multiply only propagates entropy upwards, but hashbrown takes the - /// bucket index from the low bits; rotating moves the well-mixed high bits - /// down (same fix as rustc-hash 2.x). - #[inline] - fn finish(&self) -> u64 { - self.hash.rotate_left(26) - } -} - -/// `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); - } - - /// hashbrown picks the bucket from the hash's low bits. Keys that differ only - /// in the upper bytes of their last word (e.g. "h0001".."h1024") must still - /// spread across low bits, or every probe collides (#323). - #[test] - fn low_bits_spread_for_keys_differing_in_high_bytes() { - let b = FxBuildHasher::default(); - let buckets: HashSet = (0..1024) - .map(|i| b.hash_one(format!("h{i:04}").as_str()) & 0x3ff) - .collect(); - assert!( - buckets.len() > 512, - "low 10 bits should take most of 1024 values" - ); - } -} diff --git a/src/graph/mod.rs b/src/graph/mod.rs index 2eebb7e7d1..714f8b021e 100644 --- a/src/graph/mod.rs +++ b/src/graph/mod.rs @@ -1,4 +1,3 @@ -pub(crate) mod fxhash; pub(crate) mod storage; pub(crate) mod types; diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 798cac97ad..e4fbf0491b 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -514,8 +514,9 @@ pub(crate) fn filter_facts_as_of(facts: Vec, as_of: &AsOf) -> Vec { /// /// 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`](crate::graph::fxhash::FxBuildHasher). `by_window` stores the +/// 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. /// @@ -523,7 +524,6 @@ pub(crate) fn filter_facts_as_of(facts: Vec, as_of: &AsOf) -> Vec { /// 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]); @@ -533,8 +533,8 @@ pub(crate) fn net_asserted_facts(facts: Vec) -> Vec { 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(); + 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; From 086ec3d583abb0a5898ec579eba7fef8e9fb8d2c Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Sat, 26 Sep 2026 09:15:53 +0530 Subject: [PATCH 12/12] docs: final #323 benchmark numbers (std hasher, AC) and test counts Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_01BedF9ZmqVZLkvDwn91fuKy --- CHANGELOG.md | 2 +- CLAUDE.md | 2 +- README.md | 2 +- docs/BENCHMARKS.md | 20 +++++++-------- docs/TEST_COVERAGE.md | 2 +- ...6-09-25-point-query-history-scan-design.md | 25 ++++++++++--------- 6 files changed, 27 insertions(+), 26 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index dbc85f8c1a..f5ad6d863e 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -9,7 +9,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### 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: at 2,000 retract/reassert cycles on a sibling attribute, it drops from 4.67 ms to 18.6 µs. Reading the heavily rewritten attribute itself, and attribute scans (`[?e :attr ?v]`), are about 1.6× faster (4.66 ms → 2.88 ms) from cheaper net-assert grouping and removing a redundant dedup pass. The file format is unchanged. +- **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 diff --git a/CLAUDE.md b/CLAUDE.md index 682b8ecf06..f0359ec370 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -167,7 +167,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1175 tests passing** (1167 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. diff --git a/README.md b/README.md index 229e7577c8..93af3e1e0f 100644 --- a/README.md +++ b/README.md @@ -92,7 +92,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1175 tests +cargo test # run 1173 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index 7e692b41d7..8b13948d99 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -32,21 +32,21 @@ Each value is Criterion's estimated per-query latency; the range is its 95% conf ### 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. +**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.1 µs | 18.6 µs | -| | 500 | 1.17 ms | 737 µs | -| | 2000 | 4.66 ms | 2.88 ms | -| `[:e/hot :other ?v]` (sibling attribute) | 1 | 20.2 µs | 19.4 µs | -| | 500 | 1.18 ms | 20.5 µs | -| | 2000 | 4.67 ms | 18.6 µs | -| `[?e :hash ?v]` (attribute scan) | 1 | 17.7 µs | 17.9 µs | -| | 500 | 1.16 ms | 721 µs | -| | 2000 | 4.57 ms | 2.87 ms | +| `[: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. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index a1aaf97df9..86fd20e154 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-09-26 with `cargo test` -**Result**: 1,167 passing tests and 8 ignored tests (1,175 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). 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). 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 index 01ea5a9313..6621c10581 100644 --- 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 @@ -112,21 +112,22 @@ unit test (§5) so a future change to `net_asserted_facts` cannot silently break ### 4.3 Cheaper `net_asserted_facts` -- Add a small in-crate FxHash-style hasher (`FxHasher` + `type FxBuildHasher = - BuildHasherDefault`) in a new private module `src/graph/fxhash.rs` - (~30 lines, no dependency). Word-at-a-time multiply-rotate as in rustc's FxHash. +- ~~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, FxBuildHasher>`. - 3. `by_window: HashMap<(&Uuid, &str, &[u8], i64, i64), usize, FxBuildHasher>` storing the + 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: not a concern — keys are the embedding application's own data, in-process. +- HashDoS: fact values can be untrusted text, so hashing stays randomly keyed (see above). ## 5. Testing @@ -161,13 +162,13 @@ All assert messages follow the CLAUDE.md testing convention (no `{:?}` of UUID-b 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**: 18.6 µs vs 19.4 µs. +- `[: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.62× / 1.59×** (criterion, bench profile with LTO and - `opt-level = "z"`: 4.66 → 2.88 ms, 4.57 → 2.87 ms). Revised to the measured numbers on - 2026-09-26 and shipped as a mitigation. The remaining cost is per-record fact resolve + - decode (~31%), EAVT leaf-key decode (~22%) and `net_asserted_facts` (~27%) — the - first two are inherent to v7 keys; see §6 / #379. + 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)