From 2a5ca3ffbc69929b1c3ad9e628d3bb8f2c1fa315 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 08:26:29 +0530 Subject: [PATCH 01/15] docs: add phase 7.4 design spec and update ROADMAP deferrals - Add docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md covering profiling gate and filter_facts_for_query snapshot fix - Narrow phase 7.4 ROADMAP scope to profiling + snapshot fix only - Move optimizer extensions, rule eval optimization, and predicate push-down to post-1.0 backlog in ROADMAP.md Co-Authored-By: Claude Sonnet 4.6 --- ROADMAP.md | 24 +- ...-03-27-phase-7-4-query-optimizer-design.md | 250 ++++++++++++++++++ 2 files changed, 267 insertions(+), 7 deletions(-) create mode 100644 docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md diff --git a/ROADMAP.md b/ROADMAP.md index d6faf427b8..21abfc2015 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -502,7 +502,7 @@ Current v5 stores index data as paged blobs (page type `0x11`). v6 introduces pr **Goal**: Complete the Datalog query engine โ€” negation, aggregation, disjunction, temporal range queries, and prepared statements -**Status**: ๐Ÿ”„ In Progress (7.1a + 7.1b + 7.2a + 7.2b complete โœ…) +**Status**: ๐Ÿ”„ In Progress (7.1a + 7.1b + 7.2a + 7.2b + 7.3 complete โœ…) **Priority**: ๐Ÿ”ด Critical โ€” without these, realistic production queries cannot be expressed in Datalog @@ -691,12 +691,10 @@ Current v5 stores index data as paged blobs (page type `0x11`). v6 introduces pr ### 7.4 Query Optimizer Improvements (deferred from Phase 6.3) -- ๐ŸŽฏ Cost-based optimization improvements โ€” extend `optimizer.rs` with cost estimates for the new clause types (negation sub-queries, aggregate post-processing, disjunction branch selection) -- ๐ŸŽฏ Rule evaluation optimization โ€” improve semi-naive evaluation for rules that include `not`, `or`, and aggregate expressions -- ๐ŸŽฏ **`filter_facts_for_query` snapshot overhead** โ€” `executor.rs::filter_facts_for_query` is O(N) in total fact count on every query: it streams all committed on-disk facts, clones the pending `Vec`, and rebuilds all four indexes from scratch into a throwaway `FactStorage`. Fix: replace with a read-only `Arc<[Fact]>` snapshot so the pattern matcher works against an immutable slice without index reconstruction; use the existing on-disk B+tree indexes for selective attribute/entity lookups instead of a full scan. This is the primary query performance bottleneck at scale. - ๐ŸŽฏ **Profiling integration** โ€” before optimizing, instrument the benchmark suite with a profiler to identify actual hotspots rather than relying on code inspection. Add `pprof` as a Criterion profiler (via `criterion-pprof` or the `pprof` crate's Criterion integration) so that `cargo bench` can emit flamegraphs. Run the existing `minigraf_bench.rs` benchmarks at 10K/100K facts under the profiler to confirm `filter_facts_for_query`, index rebuild, and `net_asserted_facts` are the dominant costs before investing in the fix. Profiling must precede any structural change to the query execution path. +- ๐ŸŽฏ **`filter_facts_for_query` snapshot overhead** โ€” `executor.rs::filter_facts_for_query` is O(N) in total fact count on every query: it streams all committed on-disk facts, clones the pending `Vec`, and rebuilds all four indexes from scratch into a throwaway `FactStorage`. Fix: replace with a read-only `Arc<[Fact]>` snapshot so the pattern matcher works against an immutable slice without index reconstruction; whether to also use on-disk B+tree indexes for selective lookups is determined by profiling results. This is the primary query performance bottleneck at scale. -**Note**: These items were originally scoped in Phase 6.3 but deferred here because meaningful cost estimates require the new clause types to exist first. +**Note**: The following items were originally scoped here but are deferred to the post-1.0 backlog: cost-based optimizer extensions for new clause types, rule evaluation optimization for `not`/`or`/aggregate rules, and predicate push-down. The original cost-estimate items required the new clause types to exist first (now satisfied by 7.1โ€“7.3), but the profiling-first constraint means they are lower priority than the snapshot fix. ### 7.5 Tests + Error Coverage @@ -1343,6 +1341,18 @@ Known O(Nยฒ) hotspots discovered during benchmarking (v0.13.0). Each has a well- **Fix**: Add a hash-join planning step in the aggregation post-processor for multi-pattern `with` clauses. +### Cost-Based Optimizer Extensions for New Clause Types + +Extend `optimizer.rs` `plan()` with cost estimates for negation sub-queries, aggregate post-processing, and disjunction branch selection. Requires the new clause types to exist (satisfied by 7.1โ€“7.3) and profiling data to guide estimates. Deferred from Phase 7.4 to avoid expanding scope before v1.0. + +### Rule Evaluation Optimization + +Improve semi-naive evaluation for rules that include `not`, `or`, and aggregate expressions โ€” currently routes to the mixed-rules path but does not apply any cost-aware ordering. Deferred from Phase 7.4. + +### Predicate Push-Down + +Push `Expr` predicate clauses (e.g. `[(> ?age 30)]`) down to filter bindings as early as possible rather than applying them as a final post-processing pass. Currently `apply_expr_clauses` runs after all pattern matching. A natural complement to the `filter_facts_for_query` snapshot fix, but kept separate to avoid expanding Phase 7.4's scope. + --- ## Release Strategy @@ -1514,7 +1524,7 @@ When evaluating features, ask: - โœ… Phase 7.1: Complete (March 2026) - Stratified negation (`not` / `not-join`), 407 tests - โœ… Phase 7.2a: Complete (March 2026) - Aggregation (`count`/`sum`/`min`/`max`/`distinct`/`:with`), 461 tests - โœ… Phase 7.2b: Complete (March 2026) - Arithmetic & predicate expression clauses, 527 tests -- โœ… Phase 7.3: Complete (March 2026) - Disjunction (`or` / `or-join`), 0.13.0 +- โœ… Phase 7.3: Complete (March 2026) - Disjunction (`or` / `or-join`), 562 tests - ๐ŸŽฏ Phase 7.4โ€“7.7: optimizer, prepared statements, temporal metadata bindings; โ‰ฅ90% branch coverage - **NEXT** - ๐ŸŽฏ Phase 8: 3-4 months (Cross-platform โ€” WASM, mobile, language bindings) - ๐ŸŽฏ Phase 9: Ongoing (Ecosystem โ€” integration examples, cookbook, GraphRAG/LangChain examples) @@ -1535,7 +1545,7 @@ When evaluating features, ask: 4. โœ… `evaluate_branch` / `apply_or_clauses` in `executor.rs`; union + deduplication across branches 5. โœ… `DependencyGraph::from_rules` refactored with `collect_clause_deps`; `Or`/`OrJoin` contribute positive edges 6. โœ… Rules with `or`/`or-join` route to `mixed_rules` path in `StratifiedEvaluator` -7. โœ… Integration tests in `tests/or_test.rs` and `tests/or_join_test.rs`; version bumped to v0.13.0 +7. โœ… Integration tests in `tests/disjunction_test.rs` (16 tests); 562 tests passing (384 unit + 172 integration + 6 doc); version bumped to v0.13.0 **Immediate Next Steps (Phase 7.4)**: 1. Query optimizer improvements for new clause types diff --git a/docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md b/docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md new file mode 100644 index 0000000000..bccfff2055 --- /dev/null +++ b/docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md @@ -0,0 +1,250 @@ +# Phase 7.4 โ€” Query Optimizer Improvements Design + +## Overview + +Phase 7.4 targets the primary query performance bottleneck: `filter_facts_for_query` in +`executor.rs`, which rebuilds all four in-memory indexes (`EAVT`/`AEVT`/`AVET`/`VAET`) from +scratch on every query call. The fix is gated behind a profiling step that confirms the bottleneck +before any structural change is made. + +**Scope (confirmed)**: +- Profiling integration (local validation gate only โ€” not committed to `BENCHMARKS.md`) +- `filter_facts_for_query` snapshot overhead fix + +**Deferred to post-1.0 backlog** (added to `ROADMAP.md`): +- Cost-based optimizer extensions for new clause types (`not`/`or`/aggregates) +- Rule evaluation optimization for rules with `not`/`or`/aggregates +- Predicate push-down (`Expr` clauses filtered early rather than as a final post-pass) +- Optional: `FactStorage::new_noindex()` for the rules query path (conditional on profiling) + +--- + +## Architecture Overview + +Two query paths exist and are treated differently by this phase: + +- **Non-rules path** (`execute_query`): after this phase, no `FactStorage` is constructed at + all โ€” `PatternMatcher`, `apply_or_clauses`, `not_body_matches`, and `evaluate_not_join` all + receive an `Arc<[Fact]>` snapshot directly. +- **Rules path** (`execute_query_with_rules`): still converts `Arc<[Fact]>` to a `FactStorage` + (with index rebuild) for `StratifiedEvaluator`, which needs a mutable store for derived fact + accumulation. Whether to eliminate this rebuild is deferred to profiling results. + +Evaluator-internal `PatternMatcher::new(FactStorage)` call sites in `evaluator.rs` are +**untouched** โ€” they operate on live-accumulating storage and are not part of this phase. + +--- + +## Step 1 โ€” Profiling Gate + +**Purpose**: confirm actual hotspots before making structural changes. Profiling is a local +validation step; no flamegraph files are committed to the repository. + +### `Cargo.toml` + +```toml +[dev-dependencies] +pprof = { version = "0.14", features = ["flamegraph", "criterion"] } +``` + +### `benches/minigraf_bench.rs` + +Replace the existing TODO stub with a working pprof-profiled Criterion group: + +```rust +use pprof::criterion::{Output, PProfProfiler}; + +criterion_group! { + name = benches; + config = Criterion::default() + .with_profiler(PProfProfiler::new(100, Output::Flamegraph(None))); + targets = /* existing benchmark functions */ +} +``` + +**Validation run**: `cargo bench -- --profile-time 10` on the query, negation, aggregation, and +disjunction groups at 10K and 100K facts. Flamegraphs land in +`target/criterion/*/profile/flamegraph.svg`. Inspect to confirm `filter_facts_for_query`, +`net_asserted_facts`, and the index rebuild loop are top-of-stack. + +**Gate rule**: if profiling shows a different dominant cost, stop and surface the findings before +touching executor or matcher code. + +### What the profiling reveals + +`filter_facts_for_query` performs four steps on every query call: + +| Step | What | Cost | +|---|---|---| +| 1 | `get_all_facts()` โ€” full scan of committed on-disk fact pages + clone of pending `Vec` | O(N) I/O | +| 2 | `net_asserted_facts()` โ€” HashMap pass to resolve net-asserted state per `(entity, attribute, value)` | O(N) | +| 3 | Valid-time filter | O(N) | +| 4 | 4-index rebuild via `load_fact` loop โ€” BTreeMap insertions for EAVT/AEVT/AVET/VAET | O(N) | + +**The snapshot fix eliminates step 4 only.** Steps 1โ€“3 remain after this phase. If profiling shows +that step 1 (`get_all_facts` I/O) or step 2 (`net_asserted_facts`) dominate, further work is +needed: + +- Step 1: addressed by using the on-disk B+tree for selective attribute/entity lookups (deferred + Option B, not scoped here) +- Step 2: would require caching the net-asserted view and invalidating on write (not currently + scoped) + +This is captured in the post-1.0 backlog for future consideration. + +--- + +## Step 2 โ€” Snapshot Fix + +### 2.1 `filter_facts_for_query` โ€” `executor.rs` + +Change return type from `Result` to `Result>`. The temporal filtering +logic (steps 1โ€“3 above) is unchanged. Only the final construction step is removed: + +```rust +// Before: +let filtered_storage = FactStorage::new(); +for fact in valid_filtered { + filtered_storage.load_fact(fact)?; +} +Ok(filtered_storage) + +// After: +Ok(Arc::from(valid_filtered)) +``` + +The `Arc<[Fact]>` slice contains temporally-filtered, net-asserted facts โ€” identical semantics to +the previous `FactStorage`, just without the indexes. No additional filtering is needed downstream +when matching against this slice. + +Replace the TODO comment on the function with a note pointing to the post-1.0 backlog for the +optional B+tree selective-lookup integration (the step-1 fix above). + +### 2.2 `PatternMatcher` โ€” `matcher.rs` + +Add a second internal representation and a new `from_slice` constructor. The existing +`PatternMatcher::new(FactStorage)` is kept **unchanged** for evaluator call sites. + +```rust +enum MatcherStorage { + Owned(FactStorage), + Slice(Arc<[Fact]>), +} + +pub struct PatternMatcher { + storage: MatcherStorage, +} + +impl PatternMatcher { + // Existing โ€” unchanged, used by evaluator + pub fn new(storage: FactStorage) -> Self { + PatternMatcher { storage: MatcherStorage::Owned(storage) } + } + + // New โ€” used by executor non-rules path + pub(crate) fn from_slice(facts: Arc<[Fact]>) -> Self { + PatternMatcher { storage: MatcherStorage::Slice(facts) } + } + + fn get_facts(&self) -> Vec { + match &self.storage { + MatcherStorage::Owned(s) => s.get_asserted_facts().unwrap_or_default(), + MatcherStorage::Slice(s) => s.to_vec(), + } + } +} +``` + +`match_pattern` replaces its `self.storage.get_asserted_facts()` call with `self.get_facts()`. +No other logic changes. + +**Correctness note**: the `Slice` variant receives a pre-filtered, net-asserted slice from +`filter_facts_for_query` โ€” the same set that `get_asserted_facts()` would have returned from the +old `FactStorage`. No additional filtering is needed. + +### 2.3 Cascading signature changes โ€” `executor.rs` + +All functions in `executor.rs` that accept `&FactStorage` purely to construct a `PatternMatcher` +change to accept `Arc<[Fact]>` instead. These functions never call index-based methods on the +storage; the change is mechanical. + +| Function | Old param | New param | +|---|---|---| +| `apply_or_clauses` | `storage: &FactStorage` | `storage: Arc<[Fact]>` | +| `evaluate_branch` | `storage: &FactStorage` | `storage: Arc<[Fact]>` | +| `not_body_matches` | `storage: &FactStorage` | `storage: Arc<[Fact]>` | +| `evaluate_not_join` (executor's own) | `storage: &FactStorage` | `storage: Arc<[Fact]>` | + +Inside each, `PatternMatcher::new(storage.clone())` becomes +`PatternMatcher::from_slice(storage.clone())`. The `Arc` clone is a refcount increment, not a +copy. + +`evaluate_not_join` in `evaluator.rs` (the evaluator's own version) is **unchanged** โ€” it +operates on the live-accumulating `FactStorage` path. + +### 2.4 `execute_query` call site + +Receives `Arc<[Fact]>` from `filter_facts_for_query`. Uses `PatternMatcher::from_slice` and +passes the `Arc<[Fact]>` to all or/not functions. No `FactStorage` is constructed at any point in +the non-rules path. + +### 2.5 `execute_query_with_rules` call site + +Receives `Arc<[Fact]>` from `filter_facts_for_query`, then converts to `FactStorage` for +`StratifiedEvaluator`: + +```rust +let filtered_storage = FactStorage::new(); +for fact in filtered_facts.iter().cloned() { + filtered_storage.load_fact(fact)?; +} +let evaluator = StratifiedEvaluator::new(filtered_storage, ...); +``` + +The index rebuild cost is still paid here. A TODO comment notes `FactStorage::new_noindex()` as +the next step if profiling confirms the rules-path rebuild also dominates. + +--- + +## Conditional Extension: `FactStorage::new_noindex()` + +**Only implement if profiling confirms the rules-path index rebuild is a significant cost.** + +Add a `skip_indexing: bool` field to `FactData`. When set: +- `load_fact` and `transact` skip all `pending_indexes.insert()` calls +- `get_all_facts()` always uses the full `d.facts` scan (bypassing the index fallback check) + +`execute_query_with_rules` would use `FactStorage::new_noindex()` instead of `FactStorage::new()` +when constructing the evaluator's initial storage from `Arc<[Fact]>`. `StratifiedEvaluator`'s +internal `PatternMatcher` calls only use `get_asserted_facts()` โ€” they are safe with no indexes. + +**Prerequisite**: verify that `StratifiedEvaluator` never calls index-based methods +(`get_facts_by_entity`, `get_facts_by_attribute`) directly. If it does, `new_noindex()` would +silently return empty results for those calls and must not be used. + +--- + +## Testing Strategy + +**No new test files.** The snapshot fix is a pure performance change โ€” query semantics are +unchanged. The primary correctness gate is the existing 527-test suite. + +**One new unit test** in `executor.rs` (or `tests/snapshot_test.rs`): assert that +`filter_facts_for_query` returns the correct temporally-filtered, net-asserted fact set for a +small database covering assert/retract/valid-time scenarios. This pins the return type and +semantics against future refactors. + +**Benchmark regression gate**: run `cargo bench` before and after the snapshot fix on the existing +query groups at 10K facts. Record median latency delta. Expected: measurable improvement on +non-rules query groups (simple query, negation, aggregation, disjunction); rules groups may be +unchanged until the conditional extension is implemented. + +--- + +## Out of Scope + +- Predicate push-down (post-1.0 backlog) +- Cost-based optimizer extensions for `not`/`or`/aggregate clause types (post-1.0 backlog) +- Rule evaluation optimization (post-1.0 backlog) +- B+tree selective-lookup integration in `filter_facts_for_query` step 1 (deferred to profiling) +- `net_asserted_facts` caching (not currently scoped) From ff72826d05bb9400f2f5b45982a9cf4722a4d2dd Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 08:46:05 +0530 Subject: [PATCH 02/15] docs: fix phase 7.4 spec after reviewer pass MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit - Replace pprof/criterion with cargo flamegraph (Criterion version conflict) - Enumerate both matcher.rs get_asserted_facts() call sites (lines 27 and 222) - Clarify shared functions (apply_or_clauses, evaluate_not_join) across executor.rs and evaluator.rs with per-file call-site tables - Separate execute_query (line 263) and execute_query_with_rules (line 477) not-filter rows in evaluate_not_join table - Clarify ยง2.5 insertion point for accumulated_facts Arc computation - Move evaluate_not_join propagation note (line 921) to ยง2.4 where evaluate_branch is covered - Add per-join allocation note and out-of-scope entry Co-Authored-By: Claude Sonnet 4.6 --- ...-03-27-phase-7-4-query-optimizer-design.md | 189 ++++++++++++------ 1 file changed, 133 insertions(+), 56 deletions(-) diff --git a/docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md b/docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md index bccfff2055..e2f6a7c43c 100644 --- a/docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md +++ b/docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md @@ -30,8 +30,14 @@ Two query paths exist and are treated differently by this phase: (with index rebuild) for `StratifiedEvaluator`, which needs a mutable store for derived fact accumulation. Whether to eliminate this rebuild is deferred to profiling results. -Evaluator-internal `PatternMatcher::new(FactStorage)` call sites in `evaluator.rs` are -**untouched** โ€” they operate on live-accumulating storage and are not part of this phase. +Both paths share `apply_or_clauses` (defined in `executor.rs`, imported by `evaluator.rs`) and +`evaluate_not_join` (defined in `evaluator.rs`, imported by `executor.rs`). These function +signatures change in this phase; all call sites in both files are updated. + +The evaluator's mixed-rules loop (`StratifiedEvaluator`) has inline `PatternMatcher::new(...)` and +`evaluate_not_join(...)` call sites that pass live-accumulating `FactStorage` objects โ€” these are +updated to convert to `Arc<[Fact]>` at call time but the accumulation logic is otherwise +untouched. --- @@ -40,32 +46,28 @@ Evaluator-internal `PatternMatcher::new(FactStorage)` call sites in `evaluator.r **Purpose**: confirm actual hotspots before making structural changes. Profiling is a local validation step; no flamegraph files are committed to the repository. -### `Cargo.toml` - -```toml -[dev-dependencies] -pprof = { version = "0.14", features = ["flamegraph", "criterion"] } -``` +### No `Cargo.toml` changes -### `benches/minigraf_bench.rs` +Use `cargo flamegraph` (the `cargo-flamegraph` tool wrapping `perf`) rather than a +pprof/Criterion integration. This avoids a dependency version conflict: pprof's `criterion` +feature pins against Criterion `^0.5`, while the project uses `criterion = "0.8"`. These are +incompatible and cannot coexist. `cargo flamegraph` has no Criterion dependency and produces the +same flamegraph output. -Replace the existing TODO stub with a working pprof-profiled Criterion group: +**Prerequisite**: `cargo install flamegraph` (one-time, local). -```rust -use pprof::criterion::{Output, PProfProfiler}; +### Validation run -criterion_group! { - name = benches; - config = Criterion::default() - .with_profiler(PProfProfiler::new(100, Output::Flamegraph(None))); - targets = /* existing benchmark functions */ -} +```bash +cargo bench --no-run # compile benchmarks in release mode +cargo flamegraph --bench minigraf_bench -- query_simple_10k +cargo flamegraph --bench minigraf_bench -- query_negation_10k +cargo flamegraph --bench minigraf_bench -- query_aggregation_10k +cargo flamegraph --bench minigraf_bench -- query_disjunction_10k ``` -**Validation run**: `cargo bench -- --profile-time 10` on the query, negation, aggregation, and -disjunction groups at 10K and 100K facts. Flamegraphs land in -`target/criterion/*/profile/flamegraph.svg`. Inspect to confirm `filter_facts_for_query`, -`net_asserted_facts`, and the index rebuild loop are top-of-stack. +Flamegraphs land in `flamegraph.svg` in the working directory. Inspect to confirm +`filter_facts_for_query`, `net_asserted_facts`, and the index rebuild loop are top-of-stack. **Gate rule**: if profiling shows a different dominant cost, stop and surface the findings before touching executor or matcher code. @@ -85,12 +87,12 @@ touching executor or matcher code. that step 1 (`get_all_facts` I/O) or step 2 (`net_asserted_facts`) dominate, further work is needed: -- Step 1: addressed by using the on-disk B+tree for selective attribute/entity lookups (deferred - Option B, not scoped here) +- Step 1: addressed by using the on-disk B+tree for selective attribute/entity lookups (deferred, + not scoped here) - Step 2: would require caching the net-asserted view and invalidating on write (not currently scoped) -This is captured in the post-1.0 backlog for future consideration. +Both are captured in the post-1.0 backlog for future consideration. --- @@ -123,7 +125,8 @@ optional B+tree selective-lookup integration (the step-1 fix above). ### 2.2 `PatternMatcher` โ€” `matcher.rs` Add a second internal representation and a new `from_slice` constructor. The existing -`PatternMatcher::new(FactStorage)` is kept **unchanged** for evaluator call sites. +`PatternMatcher::new(FactStorage)` is kept **unchanged** for evaluator call sites that pass +live-accumulating storage. ```rust enum MatcherStorage { @@ -136,12 +139,12 @@ pub struct PatternMatcher { } impl PatternMatcher { - // Existing โ€” unchanged, used by evaluator + // Existing โ€” unchanged pub fn new(storage: FactStorage) -> Self { PatternMatcher { storage: MatcherStorage::Owned(storage) } } - // New โ€” used by executor non-rules path + // New โ€” used by executor and evaluator call sites that provide a pre-filtered slice pub(crate) fn from_slice(facts: Arc<[Fact]>) -> Self { PatternMatcher { storage: MatcherStorage::Slice(facts) } } @@ -155,43 +158,107 @@ impl PatternMatcher { } ``` -`match_pattern` replaces its `self.storage.get_asserted_facts()` call with `self.get_facts()`. -No other logic changes. +**Two call sites** in `matcher.rs` call `self.storage.get_asserted_facts()` and must both be +updated to `self.get_facts()`: + +- `match_pattern` (line 27) +- `match_pattern_with_bindings` (line 222) + +No other logic changes. `match_patterns` and `match_patterns_seeded` delegate to these two methods +and require no further changes. + +**Per-join allocation note**: `s.to_vec()` in the `Slice` arm produces a fresh `Vec` on +every `match_pattern` / `match_pattern_with_bindings` call. This is pre-existing behaviour (the +`Owned` arm also allocates via `get_asserted_facts()`). The snapshot fix eliminates the index +rebuild (step 4) โ€” it does not eliminate per-join allocations. That would require iterating the +slice directly in the match loop, which is out of scope for this phase. **Correctness note**: the `Slice` variant receives a pre-filtered, net-asserted slice from -`filter_facts_for_query` โ€” the same set that `get_asserted_facts()` would have returned from the -old `FactStorage`. No additional filtering is needed. +`filter_facts_for_query`. This is the same fact set that `get_asserted_facts()` would have +returned from the old `FactStorage`. No additional filtering is needed. + +### 2.3 Shared function signature changes + +Two functions are shared between `executor.rs` and `evaluator.rs` and have their signatures +changed in this phase. All call sites in both files are updated. + +#### `apply_or_clauses` โ€” defined in `executor.rs`, imported by `evaluator.rs` + +Change `storage: &FactStorage` parameter to `storage: Arc<[Fact]>`. Inside, all +`PatternMatcher::new(storage.clone())` calls become `PatternMatcher::from_slice(storage.clone())`. +The `Arc` clone is a refcount increment. + +**Call sites**: -### 2.3 Cascading signature changes โ€” `executor.rs` +| File | Location | Old | New | +|---|---|---|---| +| `executor.rs` | `execute_query` | `&filtered_storage` (FactStorage) | `filtered_facts.clone()` (Arc) | +| `executor.rs` | `execute_query_with_rules` | `&derived_storage` (FactStorage) | `Arc::from(derived_storage.get_asserted_facts().unwrap_or_default())` | +| `evaluator.rs` | mixed-rules loop line 693 | `&accumulated` (FactStorage) | `Arc::from(accumulated.get_asserted_facts().unwrap_or_default())` | -All functions in `executor.rs` that accept `&FactStorage` purely to construct a `PatternMatcher` -change to accept `Arc<[Fact]>` instead. These functions never call index-based methods on the -storage; the change is mechanical. +In `execute_query_with_rules`, the `apply_or_clauses` call operates on `derived_storage` โ€” the +fully-derived fact set produced by `StratifiedEvaluator` (base facts + all rule-derived facts). +The slice must include derived facts; converting via `get_asserted_facts()` is correct. + +#### `evaluate_not_join` โ€” defined in `evaluator.rs`, imported by `executor.rs` + +Change `storage: &FactStorage` parameter to `storage: Arc<[Fact]>`. Inside, +`PatternMatcher::new(storage.clone())` becomes `PatternMatcher::from_slice(storage.clone())`. + +**Call sites**: + +| File | Location | Old | New | +|---|---|---|---| +| `executor.rs` | `execute_query` not-filter (line 263) | `¬_storage` (FactStorage clone) | `not_facts.clone()` (Arc clone) โ€” same slice as `filtered_facts` | +| `executor.rs` | `execute_query_with_rules` not-filter (line 477) | `¬_storage` (derived_storage clone) | `Arc::from(derived_storage.get_asserted_facts().unwrap_or_default())` | +| `evaluator.rs` | mixed-rules loop line 773 | `&accumulated` (FactStorage) | `Arc::from(accumulated.get_asserted_facts().unwrap_or_default())` | + +In `execute_query_with_rules`, the not-post-filter at lines 388โ€“483 must operate on +`derived_storage` (fully-derived facts), not the base `Arc<[Fact]>` from +`filter_facts_for_query`. `not` in the query body tests against the fully-derived state, +including rule-derived predicates. Converting via `derived_storage.get_asserted_facts()` is +correct. + +### 2.4 Executor-internal function signature changes + +These functions are only called within `executor.rs`; no `evaluator.rs` changes needed. | Function | Old param | New param | |---|---|---| -| `apply_or_clauses` | `storage: &FactStorage` | `storage: Arc<[Fact]>` | -| `evaluate_branch` | `storage: &FactStorage` | `storage: Arc<[Fact]>` | | `not_body_matches` | `storage: &FactStorage` | `storage: Arc<[Fact]>` | -| `evaluate_not_join` (executor's own) | `storage: &FactStorage` | `storage: Arc<[Fact]>` | +| `evaluate_branch` | `storage: &FactStorage` | `storage: Arc<[Fact]>` | + +Inside each, `PatternMatcher::new(storage.clone())` becomes `PatternMatcher::from_slice(storage.clone())`. -Inside each, `PatternMatcher::new(storage.clone())` becomes -`PatternMatcher::from_slice(storage.clone())`. The `Arc` clone is a refcount increment, not a -copy. +The `evaluate_not_join` call at line 921 (inside `evaluate_branch`) propagates the type change +automatically โ€” when `evaluate_branch`'s `storage` parameter becomes `Arc<[Fact]>`, that same +value is passed through to `evaluate_not_join` unchanged. -`evaluate_not_join` in `evaluator.rs` (the evaluator's own version) is **unchanged** โ€” it -operates on the live-accumulating `FactStorage` path. +### 2.5 Evaluator inline `PatternMatcher` call sites โ€” `evaluator.rs` -### 2.4 `execute_query` call site +The mixed-rules loop in `StratifiedEvaluator` has two inline `PatternMatcher::new(...)` call sites +that pass `accumulated` (a live-accumulating `FactStorage`). These are updated to use +`from_slice`: -Receives `Arc<[Fact]>` from `filter_facts_for_query`. Uses `PatternMatcher::from_slice` and -passes the `Arc<[Fact]>` to all or/not functions. No `FactStorage` is constructed at any point in -the non-rules path. +- Line 686: insert `let accumulated_facts: Arc<[Fact]> = Arc::from(accumulated.get_asserted_facts().unwrap_or_default());` + **before** the existing line, then replace the line itself with + `PatternMatcher::from_slice(accumulated_facts.clone())`. Reuse the same `Arc` for the + `apply_or_clauses` call at line 693 to avoid a second `get_asserted_facts()` pass. +- Line 744: `PatternMatcher::new(accumulated.clone())` (in the not-body inner loop) โ†’ + `PatternMatcher::from_slice(accumulated_facts.clone())` using the same `Arc` computed above if + it is still in scope; otherwise compute fresh. -### 2.5 `execute_query_with_rules` call site +### 2.6 `execute_query` call site -Receives `Arc<[Fact]>` from `filter_facts_for_query`, then converts to `FactStorage` for -`StratifiedEvaluator`: +Receives `Arc<[Fact]>` from `filter_facts_for_query` (renamed `filtered_facts` for clarity). +Uses `PatternMatcher::from_slice(filtered_facts.clone())`. Passes `filtered_facts.clone()` to +`apply_or_clauses` and `not_body_matches` / `evaluate_not_join`. No `FactStorage` is constructed +at any point in the non-rules path. + +### 2.7 `execute_query_with_rules` call site + +Receives `Arc<[Fact]>` from `filter_facts_for_query`. Converts to `FactStorage` for +`StratifiedEvaluator` (which needs mutable storage for derived fact accumulation): ```rust let filtered_storage = FactStorage::new(); @@ -199,10 +266,16 @@ for fact in filtered_facts.iter().cloned() { filtered_storage.load_fact(fact)?; } let evaluator = StratifiedEvaluator::new(filtered_storage, ...); +let derived_storage = evaluator.evaluate(&predicates)?; ``` -The index rebuild cost is still paid here. A TODO comment notes `FactStorage::new_noindex()` as -the next step if profiling confirms the rules-path rebuild also dominates. +After evaluation, `derived_storage` is used for pattern matching, `apply_or_clauses`, and the +not-post-filter โ€” all converted to `Arc<[Fact]>` via `derived_storage.get_asserted_facts()` at +call time (one conversion per distinct call, not one per binding). + +The index rebuild cost for the initial `filtered_storage` is still paid here. A TODO comment notes +`FactStorage::new_noindex()` as the next step if profiling confirms the rules-path rebuild also +dominates. --- @@ -212,7 +285,8 @@ the next step if profiling confirms the rules-path rebuild also dominates. Add a `skip_indexing: bool` field to `FactData`. When set: - `load_fact` and `transact` skip all `pending_indexes.insert()` calls -- `get_all_facts()` always uses the full `d.facts` scan (bypassing the index fallback check) +- `get_all_facts()` always uses the full `d.facts` scan (bypassing the `eavt.is_empty()` check, + which would fail once derived facts start populating the index) `execute_query_with_rules` would use `FactStorage::new_noindex()` instead of `FactStorage::new()` when constructing the evaluator's initial storage from `Arc<[Fact]>`. `StratifiedEvaluator`'s @@ -229,10 +303,11 @@ silently return empty results for those calls and must not be used. **No new test files.** The snapshot fix is a pure performance change โ€” query semantics are unchanged. The primary correctness gate is the existing 527-test suite. -**One new unit test** in `executor.rs` (or `tests/snapshot_test.rs`): assert that +**One new unit test** in the `#[cfg(test)]` module of `executor.rs`: assert that `filter_facts_for_query` returns the correct temporally-filtered, net-asserted fact set for a small database covering assert/retract/valid-time scenarios. This pins the return type and -semantics against future refactors. +semantics against future refactors. The function is private to `DatalogExecutor` and can only be +tested from within `executor.rs`. **Benchmark regression gate**: run `cargo bench` before and after the snapshot fix on the existing query groups at 10K facts. Record median latency delta. Expected: measurable improvement on @@ -248,3 +323,5 @@ unchanged until the conditional extension is implemented. - Rule evaluation optimization (post-1.0 backlog) - B+tree selective-lookup integration in `filter_facts_for_query` step 1 (deferred to profiling) - `net_asserted_facts` caching (not currently scoped) +- Per-join allocation elimination in `PatternMatcher` (requires iterating slice directly in match + loop; out of scope) From 81b6acf255c25c2d8bf7ed8c8cd3cd97c9e43c49 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 09:43:44 +0530 Subject: [PATCH 03/15] docs: strengthen phase 7.4 profiling gate language - Reframe gate as a proceed condition (not just a stop condition) - Add explicit Step 2 conditional header - Architecture Overview now states conditionality upfront Co-Authored-By: Claude Sonnet 4.6 --- ...-03-27-phase-7-4-query-optimizer-design.md | 21 ++++++++++++------- 1 file changed, 14 insertions(+), 7 deletions(-) diff --git a/docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md b/docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md index e2f6a7c43c..0590c52d28 100644 --- a/docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md +++ b/docs/superpowers/specs/2026-03-27-phase-7-4-query-optimizer-design.md @@ -21,11 +21,15 @@ before any structural change is made. ## Architecture Overview -Two query paths exist and are treated differently by this phase: +**Step 2 is conditional on Step 1.** No code changes are made until profiling confirms the index +rebuild (step 4 of `filter_facts_for_query`) is the dominant cost. If profiling reveals a +different bottleneck, Step 2 does not proceed and scope is reassessed. -- **Non-rules path** (`execute_query`): after this phase, no `FactStorage` is constructed at - all โ€” `PatternMatcher`, `apply_or_clauses`, `not_body_matches`, and `evaluate_not_join` all - receive an `Arc<[Fact]>` snapshot directly. +If Step 1 confirms the index rebuild, two query paths are treated differently by Step 2: + +- **Non-rules path** (`execute_query`): no `FactStorage` is constructed at all โ€” `PatternMatcher`, + `apply_or_clauses`, `not_body_matches`, and `evaluate_not_join` all receive an `Arc<[Fact]>` + snapshot directly. - **Rules path** (`execute_query_with_rules`): still converts `Arc<[Fact]>` to a `FactStorage` (with index rebuild) for `StratifiedEvaluator`, which needs a mutable store for derived fact accumulation. Whether to eliminate this rebuild is deferred to profiling results. @@ -69,8 +73,11 @@ cargo flamegraph --bench minigraf_bench -- query_disjunction_10k Flamegraphs land in `flamegraph.svg` in the working directory. Inspect to confirm `filter_facts_for_query`, `net_asserted_facts`, and the index rebuild loop are top-of-stack. -**Gate rule**: if profiling shows a different dominant cost, stop and surface the findings before -touching executor or matcher code. +**Gate rule โ€” proceed condition**: Step 2 begins **only if** the flamegraph shows the `load_fact` +loop / BTreeMap insertions (step 4) as the dominant stack frame within `filter_facts_for_query` +at 10K+ facts. If steps 1โ€“3 (`get_all_facts`, `net_asserted_facts`, valid-time filter) dominate +instead, **do not touch any executor, matcher, or evaluator code** โ€” surface the findings and +reassess scope before proceeding. ### What the profiling reveals @@ -96,7 +103,7 @@ Both are captured in the post-1.0 backlog for future consideration. --- -## Step 2 โ€” Snapshot Fix +## Step 2 โ€” Snapshot Fix *(proceeds only if Step 1 gate passes)* ### 2.1 `filter_facts_for_query` โ€” `executor.rs` From b9ac42259d147eaef701cdb923fb39733446acd9 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 10:00:25 +0530 Subject: [PATCH 04/15] =?UTF-8?q?plan:=20phase=207.4=20query=20optimizer?= =?UTF-8?q?=20=E2=80=94=20profiling=20gate=20+=20snapshot=20fix?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 8-task TDD implementation plan for filter_facts_for_query Arc<[Fact]> return type change. Gated behind flamegraph profiling confirmation. Unit tests written in red state (Task 3) before implementation (Task 5). --- .../2026-03-27-phase-7-4-query-optimizer.md | 904 ++++++++++++++++++ 1 file changed, 904 insertions(+) create mode 100644 docs/superpowers/plans/2026-03-27-phase-7-4-query-optimizer.md diff --git a/docs/superpowers/plans/2026-03-27-phase-7-4-query-optimizer.md b/docs/superpowers/plans/2026-03-27-phase-7-4-query-optimizer.md new file mode 100644 index 0000000000..617edbdbe9 --- /dev/null +++ b/docs/superpowers/plans/2026-03-27-phase-7-4-query-optimizer.md @@ -0,0 +1,904 @@ +# Phase 7.4 โ€” Query Optimizer Improvements 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:** Eliminate the four-index rebuild in `filter_facts_for_query` by returning an `Arc<[Fact]>` snapshot instead of a throwaway `FactStorage`, gated behind a flamegraph profiling step that confirms the index rebuild is the dominant cost. + +**Architecture:** `filter_facts_for_query` currently streams all facts, computes the net-asserted view, applies temporal filters, then rebuilds four BTreeMap indexes into a throwaway `FactStorage` โ€” on every query call. The fix returns `Arc<[Fact]>` from that function, gives the non-rules query path zero `FactStorage` construction, and updates all shared functions (`apply_or_clauses`, `evaluate_not_join`) to accept `Arc<[Fact]>` so their evaluator call sites convert `FactStorage โ†’ Arc` at call time via `get_asserted_facts()`. The rules path still builds a `FactStorage` for `StratifiedEvaluator` (which needs mutable accumulation), but post-evaluation calls use a derived-facts `Arc`. + +**Tech Stack:** Rust, `std::sync::Arc`, Criterion 0.8, `cargo-flamegraph` (local profiling tool, not a dependency) + +--- + +## File Map + +| File | Role | Change type | +|---|---|---| +| `benches/minigraf_bench.rs` | Benchmarks used for profiling | Run only โ€” no permanent edits | +| `src/query/datalog/matcher.rs` | `PatternMatcher` โ€” add `from_slice` constructor | Modify | +| `src/query/datalog/executor.rs` | `filter_facts_for_query`, `apply_or_clauses`, `not_body_matches`, `evaluate_branch`, `execute_query`, `execute_query_with_rules` | Modify | +| `src/query/datalog/evaluator.rs` | `evaluate_not_join`, inline `PatternMatcher` call sites at lines 686 and 744, `apply_or_clauses` call at line 693, `evaluate_not_join` call at line 773 | Modify | + +No new files are created. No test files are added โ€” the 527-test suite is the semantic regression gate, plus one new unit test inside `executor.rs`. + +--- + +## โš ๏ธ GATE: Task 1 must pass before any code changes + +**Do not start Task 2 until Task 1 explicitly confirms the index rebuild is the dominant cost.** If profiling shows a different dominant cost, stop and surface the findings. + +--- + +## Task 1: Profiling Gate + +**Files:** +- Run: `benches/minigraf_bench.rs` (no edits) + +**Context:** `filter_facts_for_query` does four things every query: (1) `get_all_facts()` โ€” full I/O scan, (2) `net_asserted_facts()` โ€” HashMap pass, (3) valid-time filter, (4) four BTreeMap index rebuilds via `load_fact` loop. The snapshot fix eliminates step 4. Profiling confirms step 4 actually dominates before we restructure code. + +- [ ] **Step 1: Install cargo-flamegraph (if not already installed)** + +```bash +cargo install flamegraph +``` + +Expected: installs `cargo flamegraph` subcommand. If already installed, this is a no-op. + +- [ ] **Step 2: Compile benchmarks in release mode** + +```bash +cargo bench --no-run +``` + +Expected: compiles cleanly. If compilation fails, check that the repo is on `main` and `cargo test` passes first. + +- [ ] **Step 3: Run flamegraph on query benchmarks at 10K facts** + +```bash +cargo flamegraph --bench minigraf_bench -- "query/point_entity/10k" +``` + +This profiles the `query/point_entity/10k` benchmark โ€” a simple EAVT lookup at 10K facts. Flamegraph writes to `flamegraph.svg` in the working directory. + +- [ ] **Step 4: Open and inspect flamegraph.svg** + +Open `flamegraph.svg` in a browser. Look for `filter_facts_for_query` in the stack. Inside it, look for `load_fact` and BTreeMap insertion frames. + +**Proceed condition:** `load_fact` / BTreeMap insertion (the four-index rebuild loop) must be visible and dominant within `filter_facts_for_query`. If `get_all_facts`, `net_asserted_facts`, or something else dominates instead, **stop here** and report findings before continuing. + +- [ ] **Step 5: Run flamegraph on negation and disjunction at 10K facts** + +```bash +cargo flamegraph --bench minigraf_bench -- "negation/not_scale/10k" +mv flamegraph.svg flamegraph_not.svg +cargo flamegraph --bench minigraf_bench -- "disjunction/or_scale/10k" +mv flamegraph.svg flamegraph_or.svg +``` + +Inspect both. Confirm `filter_facts_for_query` index rebuild still dominates (not `not_body_matches` inner loop, which is a known O(Nยฒ) post-1.0 item, not in scope here). + +- [ ] **Step 6: Record baseline benchmark timings** + +```bash +cargo bench -- "query/point_entity/10k" "negation/not_scale/10k" "disjunction/or_scale/10k" "aggregation/count_scale/10k" 2>&1 | tee /tmp/bench_baseline.txt +``` + +Save these numbers. We will compare after the fix to confirm improvement. + +- [ ] **Step 7: Clean up flamegraph files (do not commit)** + +```bash +rm -f flamegraph.svg flamegraph_not.svg flamegraph_or.svg +``` + +`flamegraph.svg` should not be committed. `/tmp/bench_baseline.txt` is kept for Task 7 comparison. Proceed only if all profiling checks passed. + +--- + +## Task 2: `PatternMatcher` dual-constructor โ€” `matcher.rs` + +**Files:** +- Modify: `src/query/datalog/matcher.rs` + +**Context:** `PatternMatcher` currently holds a `FactStorage` and calls `get_asserted_facts()` for a linear scan. We add a second internal variant (`Slice`) that holds `Arc<[Fact]>` directly. Both variants share `get_facts()` which replaces the two direct `get_asserted_facts()` calls. The existing `new(FactStorage)` constructor is unchanged โ€” evaluator call sites continue to use it. + +This task is purely additive. All existing tests continue to pass without modification. + +- [ ] **Step 1: Write failing test for `from_slice` constructor** + +**Before writing the test**, scan the existing `#[cfg(test)]` module in `matcher.rs` to verify the correct `Pattern` constructor signature. The test below assumes `Pattern::new(entity, attribute, value, None, None)` โ€” adjust if the actual constructor differs. + +In `src/query/datalog/matcher.rs`, inside the existing `#[cfg(test)]` module, add: + +```rust +#[test] +fn test_from_slice_matches_same_as_owned() { + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + storage + .transact( + vec![(alice, ":person/name".to_string(), Value::String("Alice".to_string()))], + None, + ) + .unwrap(); + + // Build owned matcher the existing way + let owned_matcher = PatternMatcher::new(storage.clone()); + + // Build slice matcher via from_slice + let facts: Arc<[Fact]> = Arc::from(storage.get_asserted_facts().unwrap()); + let slice_matcher = PatternMatcher::from_slice(facts); + + let pattern = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::Symbol("?name".to_string()), + None, + None, + ); + + let owned_results = owned_matcher.match_pattern(&pattern); + let slice_results = slice_matcher.match_pattern(&pattern); + + assert_eq!(owned_results.len(), slice_results.len(), "result count mismatch"); + assert_eq!( + owned_results[0].get("?name"), + slice_results[0].get("?name"), + "bound value mismatch" + ); +} +``` + +- [ ] **Step 2: Run the test โ€” confirm it fails to compile** + +```bash +cargo test test_from_slice_matches_same_as_owned 2>&1 | head -20 +``` + +Expected: compile error โ€” `from_slice` not found, `MatcherStorage` not defined. + +- [ ] **Step 3: Add `MatcherStorage` enum and `from_slice` constructor** + +In `src/query/datalog/matcher.rs`, replace the existing struct definition and `new` constructor with: + +```rust +use std::sync::Arc; +use crate::graph::types::Fact; + +enum MatcherStorage { + Owned(FactStorage), + Slice(Arc<[Fact]>), +} + +pub struct PatternMatcher { + storage: MatcherStorage, +} + +impl PatternMatcher { + pub fn new(storage: FactStorage) -> Self { + PatternMatcher { storage: MatcherStorage::Owned(storage) } + } + + pub(crate) fn from_slice(facts: Arc<[Fact]>) -> Self { + PatternMatcher { storage: MatcherStorage::Slice(facts) } + } + + fn get_facts(&self) -> Vec { + match &self.storage { + MatcherStorage::Owned(s) => s.get_asserted_facts().unwrap_or_default(), + MatcherStorage::Slice(s) => s.to_vec(), + } + } +} +``` + +- [ ] **Step 4: Update the two `get_asserted_facts()` call sites in `match_pattern` and `match_pattern_with_bindings`** + +In `match_pattern` (around line 27): +```rust +// Before: +let facts = self.storage.get_asserted_facts().unwrap_or_default(); +// After: +let facts = self.get_facts(); +``` + +In `match_pattern_with_bindings` (around line 222): +```rust +// Before: +let facts = self.storage.get_asserted_facts().unwrap_or_default(); +// After: +let facts = self.get_facts(); +``` + +- [ ] **Step 5: Run the new test โ€” confirm it passes** + +```bash +cargo test test_from_slice_matches_same_as_owned -- --nocapture +``` + +Expected: PASS. + +- [ ] **Step 6: Run full test suite โ€” confirm nothing is broken** + +```bash +cargo test +``` + +Expected: all 527 tests pass (or current count). + +- [ ] **Step 7: Commit** + +```bash +git add src/query/datalog/matcher.rs +git commit -m "refactor: add PatternMatcher::from_slice for Arc<[Fact]> input + +Adds MatcherStorage enum with Owned(FactStorage) and Slice(Arc<[Fact]>) +variants. from_slice constructor used by the executor snapshot path. +Existing new(FactStorage) constructor and all evaluator call sites +unchanged. + +Part of phase 7.4 snapshot fix." +``` + +--- + +## Task 3: Unit test for `filter_facts_for_query` โ€” write failing test first + +**Files:** +- Modify: `src/query/datalog/executor.rs` (add tests to `#[cfg(test)]` module) + +**Context:** `filter_facts_for_query` is a private method of `DatalogExecutor`. It can only be tested from within `executor.rs`. We write the tests NOW, before the return type changes in Task 5, so we follow TDD discipline: write failing test โ†’ implement โ†’ pass. The tests call `.len()` and index access on the return value, which are not defined on `FactStorage` โ€” so they will fail to compile until Task 5 changes the return type to `Arc<[Fact]>`. + +- [ ] **Step 1: Add unit tests inside `executor.rs` `#[cfg(test)]` module** + +Find the `#[cfg(test)]` block in `src/query/datalog/executor.rs` and add: + +```rust +#[test] +fn test_filter_facts_for_query_returns_net_asserted_slice() { + use crate::graph::storage::FactStorage; + use crate::query::datalog::types::{DatalogQuery, AsOf, ValidAt}; + use crate::query::datalog::rules::RuleRegistry; + use std::sync::{Arc, RwLock}; + + // Build a small in-memory database + let storage = FactStorage::new(); + let alice = uuid::Uuid::new_v4(); + + // Assert, then retract :person/name + storage + .transact(vec![(alice, ":person/name".to_string(), crate::graph::types::Value::String("Alice".to_string()))], None) + .unwrap(); + storage + .retract(alice, ":person/name".to_string(), crate::graph::types::Value::String("Alice".to_string()), None) + .unwrap(); + + // Assert :person/age โ€” not retracted + storage + .transact(vec![(alice, ":person/age".to_string(), crate::graph::types::Value::Integer(30))], None) + .unwrap(); + + let rules = Arc::new(RwLock::new(RuleRegistry::new())); + let executor = DatalogExecutor::new(storage, rules); + + let query = DatalogQuery { + find: vec![], + where_clauses: vec![], + rules: vec![], + as_of: None, + valid_at: None, + with_vars: vec![], + }; + + let facts = executor.filter_facts_for_query(&query).unwrap(); + + // Only the net-asserted :person/age fact should survive (name was retracted) + assert_eq!(facts.len(), 1, "expected exactly 1 net-asserted fact"); + assert_eq!(facts[0].attribute, ":person/age", "expected :person/age"); +} + +#[test] +fn test_filter_facts_for_query_valid_time_filter() { + use crate::graph::storage::FactStorage; + use crate::query::datalog::types::{DatalogQuery, ValidAt}; + use crate::query::datalog::rules::RuleRegistry; + use std::sync::{Arc, RwLock}; + + let storage = FactStorage::new(); + let alice = uuid::Uuid::new_v4(); + + // Assert with a past valid-time window that has already closed + storage + .transact_with_options( + vec![(alice, ":status".to_string(), crate::graph::types::Value::String("active".to_string()))], + Some(crate::graph::types::TransactOptions { + valid_from: Some(1_000_000), + valid_to: Some(2_000_000), + }), + ) + .unwrap(); + + let rules = Arc::new(RwLock::new(RuleRegistry::new())); + let executor = DatalogExecutor::new(storage, rules); + + // Query with valid_at in the past window โ€” fact should appear + let query_in_window = DatalogQuery { + find: vec![], + where_clauses: vec![], + rules: vec![], + as_of: None, + valid_at: Some(ValidAt::Timestamp(1_500_000)), + with_vars: vec![], + }; + let facts_in = executor.filter_facts_for_query(&query_in_window).unwrap(); + assert_eq!(facts_in.len(), 1, "fact should be visible within valid window"); + + // Query with valid_at outside the window โ€” fact should not appear + let query_outside = DatalogQuery { + find: vec![], + where_clauses: vec![], + rules: vec![], + as_of: None, + valid_at: Some(ValidAt::Timestamp(3_000_000)), + with_vars: vec![], + }; + let facts_out = executor.filter_facts_for_query(&query_outside).unwrap(); + assert_eq!(facts_out.len(), 0, "fact should not be visible outside valid window"); +} +``` + +**Note:** If `DatalogQuery`, `TransactOptions`, or `DatalogExecutor` constructors differ from the above, adjust to match the existing test patterns in the file. The key assertions (`facts.len()`, `facts[0].attribute`) are what matter. + +- [ ] **Step 2: Run the tests โ€” confirm they FAIL to compile** + +```bash +cargo test test_filter_facts_for_query 2>&1 | head -20 +``` + +Expected: compile error โ€” `filter_facts_for_query` currently returns `FactStorage`; `.len()` and index access (`[0]`) are not defined on `FactStorage`. This is the expected "red" state. Task 5 will make these tests pass. + +- [ ] **Step 3: Commit the failing tests** + +```bash +git add src/query/datalog/executor.rs +git commit -m "test: pin filter_facts_for_query semantics โ€” failing (red state) + +Two unit tests for filter_facts_for_query in executor.rs #[cfg(test)]: +net-asserted view (retracted facts excluded) and valid-time filtering. +Tests currently fail to compile; Task 5 changes the return type to +Arc<[Fact]> to make them pass. + +Phase 7.4." +``` + +--- + +## Task 4: Change `apply_or_clauses` and `evaluate_not_join` signatures + +**Files:** +- Modify: `src/query/datalog/executor.rs` (signature of `apply_or_clauses`, all executor call sites) +- Modify: `src/query/datalog/evaluator.rs` (signature of `evaluate_not_join`, all evaluator call sites; evaluator call site of `apply_or_clauses`) + +**Context:** `apply_or_clauses` (defined in `executor.rs`, imported by `evaluator.rs`) and `evaluate_not_join` (defined in `evaluator.rs`, imported by `executor.rs`) both currently accept `&FactStorage`. We change both to accept `Arc<[Fact]>`. At this stage, all existing call sites still have a `FactStorage` โ€” they convert via `.get_asserted_facts()` before calling. This keeps the code compiling and all tests passing. The FactStorage-to-Arc conversion at call sites will be simplified in later tasks once `filter_facts_for_query` returns `Arc` directly. + +**Important:** In `execute_query_with_rules`, `apply_or_clauses` and the not-filter must use `derived_storage` (the fully-derived fact set including rule-derived facts), NOT the base filtered facts. The conversion `Arc::from(derived_storage.get_asserted_facts().unwrap_or_default())` is correct for this case. + +- [ ] **Step 1: Change `apply_or_clauses` signature in `executor.rs`** + +Find the `apply_or_clauses` function signature in `src/query/datalog/executor.rs` and change the `storage` parameter: + +```rust +// Before: +pub(crate) fn apply_or_clauses( + clauses: &[WhereClause], + bindings: Vec, + storage: &FactStorage, + rules: &RuleRegistry, + as_of: Option, + valid_at: Option, +) -> anyhow::Result> + +// After: +pub(crate) fn apply_or_clauses( + clauses: &[WhereClause], + bindings: Vec, + storage: Arc<[Fact]>, + rules: &RuleRegistry, + as_of: Option, + valid_at: Option, +) -> anyhow::Result> +``` + +Add `use std::sync::Arc;` and `use crate::graph::types::Fact;` to imports if not already present. + +- [ ] **Step 2: Update `apply_or_clauses` body โ€” `PatternMatcher::new` โ†’ `from_slice`** + +Inside `apply_or_clauses` and `evaluate_branch` (which it delegates to), find any `PatternMatcher::new(storage.clone())` and change to `PatternMatcher::from_slice(storage.clone())`. `storage.clone()` is now an Arc refcount increment. + +Also update `evaluate_branch`'s `storage` parameter type to `Arc<[Fact]>` and its internal `PatternMatcher::new(storage.clone())` calls to `PatternMatcher::from_slice(storage.clone())`. + +- [ ] **Step 3: Fix `apply_or_clauses` call sites in `executor.rs`** + +There are two call sites in `executor.rs` โ€” in `execute_query` and `execute_query_with_rules`. Convert `FactStorage` to `Arc<[Fact]>` at each call site: + +In `execute_query` (uses `filtered_storage`, a `FactStorage`): +```rust +// Before: +apply_or_clauses(&query.where_clauses, bindings, &filtered_storage, ...)? +// After: +apply_or_clauses( + &query.where_clauses, + bindings, + Arc::from(filtered_storage.get_asserted_facts().unwrap_or_default()), + ... +)? +``` + +In `execute_query_with_rules` (uses `derived_storage`): +```rust +// Before: +apply_or_clauses(&query.where_clauses, bindings, &derived_storage, ...)? +// After: +apply_or_clauses( + &query.where_clauses, + bindings, + Arc::from(derived_storage.get_asserted_facts().unwrap_or_default()), + ... +)? +``` + +- [ ] **Step 4: Fix `apply_or_clauses` call site in `evaluator.rs` (line ~693)** + +```rust +// Before: +apply_or_clauses(&rule.body, raw_candidates, &accumulated, ®istry_guard, None, None)? +// After: +apply_or_clauses( + &rule.body, + raw_candidates, + Arc::from(accumulated.get_asserted_facts().unwrap_or_default()), + ®istry_guard, + None, + None, +)? +``` + +Add `use std::sync::Arc;` to imports in `evaluator.rs` if not already present. + +- [ ] **Step 5: Change `evaluate_not_join` signature in `evaluator.rs`** + +Find `pub fn evaluate_not_join` in `src/query/datalog/evaluator.rs` and change its `storage` parameter: + +```rust +// Before: +pub fn evaluate_not_join( + join_vars: &[String], + clauses: &[WhereClause], + binding: &Bindings, + storage: &FactStorage, +) -> bool + +// After: +pub fn evaluate_not_join( + join_vars: &[String], + clauses: &[WhereClause], + binding: &Bindings, + storage: Arc<[Fact]>, +) -> bool +``` + +- [ ] **Step 6: Update `evaluate_not_join` body โ€” `PatternMatcher::new` โ†’ `from_slice`** + +Inside `evaluate_not_join` (around line 447): +```rust +// Before: +let matcher = PatternMatcher::new(storage.clone()); +// After: +let matcher = PatternMatcher::from_slice(storage.clone()); +``` + +- [ ] **Step 7: Fix `evaluate_not_join` call sites in `executor.rs`** + +**Note:** There are three call sites for `evaluate_not_join` in `executor.rs`: `execute_query` (line 263), `execute_query_with_rules` (line 477), and inside `evaluate_branch` (line 921). The third call site (line 921 inside `evaluate_branch`) is already handled by Step 2 above โ€” `evaluate_branch`'s `storage` parameter is `Arc<[Fact]>` after that step, so it passes `storage` through to `evaluate_not_join` unchanged. Verify it compiles cleanly; no additional conversion is needed for line 921. + +For the two explicit conversion call sites: + +In `execute_query` (around line 263, in the not-filter closure): +```rust +// Before: +evaluate_not_join(join_vars, nj_clauses, binding, ¬_storage) +// After: +evaluate_not_join( + join_vars, + nj_clauses, + binding, + Arc::from(not_storage.get_asserted_facts().unwrap_or_default()), +) +``` + +Note: `not_storage` in `execute_query` is `filtered_storage.clone()`. After Task 5, this will be simplified further. + +In `execute_query_with_rules` (around line 477): +```rust +// Before: +evaluate_not_join(join_vars, nj_clauses, binding, ¬_storage) +// After: +evaluate_not_join( + join_vars, + nj_clauses, + binding, + Arc::from(not_storage.get_asserted_facts().unwrap_or_default()), +) +``` + +Note: `not_storage` in `execute_query_with_rules` is `derived_storage.clone()`. This must remain `derived_storage`-based โ€” it includes rule-derived facts. + +- [ ] **Step 8: Fix `evaluate_not_join` call site in `evaluator.rs` (line ~773)** + +```rust +// Before: +evaluate_not_join(join_vars, nj_clauses, &binding, &accumulated) +// After: +evaluate_not_join( + join_vars, + nj_clauses, + &binding, + Arc::from(accumulated.get_asserted_facts().unwrap_or_default()), +) +``` + +- [ ] **Step 9: Compile** + +```bash +cargo build 2>&1 | head -30 +``` + +Expected: compiles cleanly. If there are type errors, fix them before proceeding. + +- [ ] **Step 10: Run full test suite** + +```bash +cargo test +``` + +Expected: all tests pass. No semantic change has been made โ€” just type conversions at call sites. + +- [ ] **Step 11: Commit** + +```bash +git add src/query/datalog/executor.rs src/query/datalog/evaluator.rs +git commit -m "refactor: change apply_or_clauses and evaluate_not_join to take Arc<[Fact]> + +All call sites convert FactStorage โ†’ Arc at call time via get_asserted_facts(). +No semantic change. Prepares for filter_facts_for_query returning Arc directly. + +Part of phase 7.4 snapshot fix." +``` + +--- + +## Task 5: Change `filter_facts_for_query` return type and simplify `execute_query` + +**Files:** +- Modify: `src/query/datalog/executor.rs` + +**Context:** `filter_facts_for_query` currently returns `Result` by building a new `FactStorage` and calling `load_fact` for each filtered fact โ€” rebuilding all four BTreeMap indexes. After this task, it returns `Result>` directly. `execute_query` (the non-rules path) then passes the `Arc` through to all downstream calls with no FactStorage construction at all. The expensive conversion calls added in Task 4 (`Arc::from(filtered_storage.get_asserted_facts()...)`) are replaced with direct Arc clones. The unit tests from Task 3 (`test_filter_facts_for_query_*`) will pass after Step 1 of this task. + +- [ ] **Step 1: Change `filter_facts_for_query` return type and remove index rebuild** + +In `src/query/datalog/executor.rs`, find `filter_facts_for_query`. Replace the final block: + +```rust +// Before: +let filtered_storage = FactStorage::new(); +for fact in valid_filtered { + filtered_storage.load_fact(fact)?; +} +Ok(filtered_storage) + +// After: +Ok(Arc::from(valid_filtered)) +``` + +Also update the function signature: +```rust +// Before: +fn filter_facts_for_query(&self, query: &DatalogQuery) -> Result +// After: +fn filter_facts_for_query(&self, query: &DatalogQuery) -> Result> +``` + +Replace the TODO comment on the function with: +```rust +/// **Post-1.0 backlog**: Use the on-disk B+tree indexes (EAVT/AEVT/AVET/VAET) for +/// selective attribute/entity lookups instead of the full `get_all_facts()` scan (step 1). +/// Also investigate caching the `net_asserted_facts()` result and invalidating on write (step 2). +``` + +- [ ] **Step 2a: Rename `filtered_storage` to `filtered_facts` in `execute_query` and update `PatternMatcher` call** + +In `execute_query`, the `filtered_storage` variable is now `Arc<[Fact]>`. Rename it to `filtered_facts` for clarity: + +```rust +let filtered_facts = self.filter_facts_for_query(&query)?; +let matcher = PatternMatcher::from_slice(filtered_facts.clone()); +``` + +For `apply_or_clauses` โ€” replace the `Arc::from(filtered_storage.get_asserted_facts()...)` conversion from Task 4 with a direct clone: +```rust +apply_or_clauses(&query.where_clauses, bindings, filtered_facts.clone(), ...)? +``` + +For the not-filter, `not_storage` was `filtered_storage.clone()` โ€” replace with `filtered_facts.clone()`. The calls to `not_body_matches` and `evaluate_not_join` now receive direct Arc clones. + +- [ ] **Step 2b: Update `not_body_matches` signature and internal `PatternMatcher` call** + +Change `not_body_matches`'s `storage` parameter to accept `Arc<[Fact]>` (spec ยง2.4): +```rust +// Signature before: +fn not_body_matches(not_body: &[WhereClause], binding: &Binding, storage: &FactStorage) -> bool +// Signature after: +fn not_body_matches(not_body: &[WhereClause], binding: &Binding, storage: Arc<[Fact]>) -> bool +``` + +Inside `not_body_matches`, change `PatternMatcher::new(not_storage.clone())` โ†’ `PatternMatcher::from_slice(not_storage.clone())`. + +- [ ] **Step 3: Update `execute_query_with_rules` โ€” convert Arc back to FactStorage for evaluator** + +`execute_query_with_rules` also calls `filter_facts_for_query`. It now receives `Arc<[Fact]>`. It must convert this to a `FactStorage` for `StratifiedEvaluator`: + +```rust +let filtered_facts = self.filter_facts_for_query(&query)?; + +// Convert to FactStorage for StratifiedEvaluator (needs mutable accumulation) +// TODO (post-1.0): use FactStorage::new_noindex() once profiling confirms rules-path +// index rebuild is also a bottleneck. +let filtered_storage = FactStorage::new(); +for fact in filtered_facts.iter().cloned() { + filtered_storage.load_fact(fact)?; +} +let evaluator = StratifiedEvaluator::new(filtered_storage, self.rules.clone(), 1000); +let derived_storage = evaluator.evaluate(&predicates)?; +``` + +After `derived_storage` is computed, compute a `derived_facts: Arc<[Fact]>` once and reuse it for both `apply_or_clauses` and the not-post-filter (the conversion calls added in Task 4): + +```rust +let derived_facts: Arc<[Fact]> = + // NOTE: must use derived_storage (includes rule-derived facts), not filtered_facts (base facts only) + Arc::from(derived_storage.get_asserted_facts().unwrap_or_default()); +``` + +Then replace the two `Arc::from(derived_storage.get_asserted_facts()...)` calls from Task 4 with `derived_facts.clone()`. + +- [ ] **Step 4: Compile** + +```bash +cargo build 2>&1 | head -30 +``` + +Expected: compiles cleanly. + +- [ ] **Step 5: Run full test suite โ€” including Task 3 unit tests** + +```bash +cargo test +``` + +Expected: all tests pass, including the two `test_filter_facts_for_query_*` tests written in Task 3 that were previously failing to compile. Those tests are now green because `filter_facts_for_query` returns `Arc<[Fact]>` with `.len()` and index access. + +- [ ] **Step 6: Commit** + +```bash +git add src/query/datalog/executor.rs +git commit -m "perf: eliminate FactStorage index rebuild in execute_query path + +filter_facts_for_query now returns Arc<[Fact]> instead of FactStorage, +eliminating the O(N) BTreeMap rebuild (4 indexes ร— N facts) on every +non-rules query call. execute_query constructs no FactStorage at all. +execute_query_with_rules still converts Arc โ†’ FactStorage for +StratifiedEvaluator (deferred to post-profiling decision). + +Phase 7.4." +``` + +--- + +## Task 6: Simplify evaluator inline call sites โ€” `evaluator.rs` + +**Files:** +- Modify: `src/query/datalog/evaluator.rs` + +**Context:** The evaluator's mixed-rules loop has inline `PatternMatcher::new(accumulated.clone())` calls at lines 686 and 744, and `evaluate_not_join` / `apply_or_clauses` calls that currently convert `accumulated` via `get_asserted_facts()` (added in Task 4). We compute `accumulated_facts: Arc<[Fact]>` once per rule iteration and reuse it for all four usages, eliminating redundant `get_asserted_facts()` calls. + +- [ ] **Step 1: Compute `accumulated_facts` once per rule iteration** + +In `src/query/datalog/evaluator.rs`, in the mixed-rules loop, find the block around line 686. Declare `accumulated_facts` at the **outermost scope of the per-rule loop body** โ€” before line 686 โ€” so it is visible through lines 693, 744, and 773: + +```rust +// Compute once; reuse for matcher, apply_or_clauses, not-body matching, and evaluate_not_join. +// Declared at loop body scope so it remains in scope for all four usages below. +let accumulated_facts: Arc<[Fact]> = + Arc::from(accumulated.get_asserted_facts().unwrap_or_default()); +``` + +- [ ] **Step 2: Replace line 686 PatternMatcher call** + +```rust +// Before: +let matcher = PatternMatcher::new(accumulated.clone()); +// After: +let matcher = PatternMatcher::from_slice(accumulated_facts.clone()); +``` + +- [ ] **Step 3: Replace line 693 `apply_or_clauses` call** + +Replace the `Arc::from(accumulated.get_asserted_facts()...)` conversion from Task 4 with: +```rust +apply_or_clauses(&rule.body, raw_candidates, accumulated_facts.clone(), ...)? +``` + +- [ ] **Step 4: Replace line 744 PatternMatcher call (not-body inner loop)** + +```rust +// Before: +let not_matcher = PatternMatcher::new(accumulated.clone()); +// After: +let not_matcher = PatternMatcher::from_slice(accumulated_facts.clone()); +``` + +- [ ] **Step 5: Replace line 773 `evaluate_not_join` call** + +Replace the `Arc::from(accumulated.get_asserted_facts()...)` conversion from Task 4 with: +```rust +evaluate_not_join(join_vars, nj_clauses, &binding, accumulated_facts.clone()) +``` + +- [ ] **Step 6: Compile** + +```bash +cargo build 2>&1 | head -30 +``` + +Expected: compiles cleanly. + +- [ ] **Step 7: Run full test suite** + +```bash +cargo test +``` + +Expected: all tests pass. + +- [ ] **Step 8: Commit** + +```bash +git add src/query/datalog/evaluator.rs +git commit -m "refactor: compute accumulated_facts Arc once per evaluator rule iteration + +Replaces three separate accumulated.clone() + get_asserted_facts() calls +with a single Arc<[Fact]> computed once and reused for PatternMatcher, +apply_or_clauses, not-body matching, and evaluate_not_join. + +Part of phase 7.4 snapshot fix." +``` + +--- + +## Task 7: Benchmark regression check + +**Files:** +- Run only โ€” no code changes + +- [ ] **Step 1: Run the same benchmark groups as Task 1** + +```bash +cargo bench -- "query/point_entity/10k" "negation/not_scale/10k" "disjunction/or_scale/10k" "aggregation/count_scale/10k" 2>&1 | tee /tmp/bench_after.txt +``` + +- [ ] **Step 2: Compare against baseline** + +Compare the median latency numbers from `/tmp/bench_after.txt` against the numbers recorded in Task 1 Step 6 (`/tmp/bench_baseline.txt`). + +Expected: non-rules query groups (`query/point_entity`, `aggregation/count_scale`) show measurable improvement. `negation/not_scale` and `disjunction/or_scale` may show partial improvement (those paths also had FactStorage overhead eliminated) but are bounded by their O(Nยฒ) inner loops (post-1.0 items). Rules-based benchmarks (`bench_recursion`) are expected to be unchanged. + +If a group shows no improvement or regression, inspect with flamegraph to confirm the index rebuild is gone and something else now dominates. + +- [ ] **Step 3: Clean up temp files** + +```bash +rm -f /tmp/bench_after.txt /tmp/bench_baseline.txt +``` + +--- + +## Task 8: Documentation update + +**Files:** +- Modify: `CLAUDE.md` (update test count) +- Modify: `ROADMAP.md` (mark 7.4 complete, update Current Focus to 7.5) +- Modify: `CHANGELOG.md` (add 7.4 entry) + +**Context:** Per CLAUDE.md ยง8: "when a phase is marked complete, update and cross-check ALL of: CLAUDE.md, ROADMAP.md, README.md, TEST_COVERAGE.md, CHANGELOG.md." Also update affected wiki pages. + +- [ ] **Step 1: Get current test count** + +```bash +cargo test 2>&1 | tail -5 +``` + +Note the exact number. + +- [ ] **Step 2: Update `CLAUDE.md` test count** + +In `CLAUDE.md`, find the line: +``` +**527 tests passing** (365 unit + 156 integration + 6 doc). +``` +Update to the new test count. If the unit/integration/doc breakdown changed, update those too. + +- [ ] **Step 3: Update `ROADMAP.md`** + +In `ROADMAP.md`: +- Mark phase 7.4 as `โœ… Complete (March 2026)` in the progress list +- Update "Current Focus" section to point to Phase 7.5 +- Update the "Last Updated" footer line + +- [ ] **Step 4: Add `CHANGELOG.md` entry** + +Add a new entry for the 7.4 changes. Follow the existing format in the file. Key points: +- `filter_facts_for_query` now returns `Arc<[Fact]>` instead of throwaway `FactStorage` +- Eliminates O(N) four-index rebuild on every non-rules query call +- `PatternMatcher::from_slice` constructor added +- `apply_or_clauses` and `evaluate_not_join` signatures changed to accept `Arc<[Fact]>` +- 527+ tests passing + +- [ ] **Step 5: Update `TEST_COVERAGE.md`** + +Update the test count and any per-file breakdown that changed (executor.rs gained 2 tests). + +- [ ] **Step 6: Update `README.md` if needed** + +Check if README mentions test count or phase status โ€” update if so. Only modify `README.md` if it requires changes. + +- [ ] **Step 7: Update wiki pages** + +```bash +cd .wiki +``` + +Check `Architecture.md` โ€” update if the query execution path description mentions `filter_facts_for_query` or `FactStorage` construction. No syntax changes, so `Datalog-Reference.md` should not need changes. + +```bash +git add Architecture.md +git commit -m "docs: phase 7.4 complete โ€” filter_facts_for_query snapshot fix" +git push +cd .. +``` + +Only include files that were actually modified in the `git add`. + +- [ ] **Step 8: Commit all doc changes** + +```bash +git add CLAUDE.md ROADMAP.md CHANGELOG.md TEST_COVERAGE.md +# Only include README.md if it was modified in Step 6: +# git add README.md +git commit -m "docs: phase 7.4 complete โ€” snapshot fix, eliminate index rebuild + +filter_facts_for_query returns Arc<[Fact]>; execute_query path constructs +no FactStorage. PatternMatcher::from_slice added. N tests passing." +``` + +- [ ] **Step 9: Tag the version** + +Check the current version in `Cargo.toml`. Phase 7.4 is a performance fix within v0.13.x. Bump the patch version: + +```bash +# In Cargo.toml: version = "0.13.0" โ†’ "0.13.1" +# Edit manually, then: +git add Cargo.toml Cargo.lock +git commit -m "chore: bump version to v0.13.1" +git tag -a v0.13.1 -m "phase 7.4 complete โ€” filter_facts_for_query snapshot fix, eliminate 4-index rebuild" +git push origin v0.13.1 +``` From b30d3ae42030f19d43423721a1ab531e7ad19fb9 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 12:22:39 +0530 Subject: [PATCH 05/15] chore: add [profile.bench] with debug symbols for flamegraph profiling Adds strip = "none" and debug = true to the bench profile so that cargo flamegraph --bench produces readable stack frames instead of opaque binary blobs. Profiling confirmed filter_facts_for_query index rebuild (Indexes::insert / BTreeMap) is dominant cost at 10K facts (~25% query, ~23% negation). Phase 7.4 profiling gate: PASSES. --- Cargo.toml | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/Cargo.toml b/Cargo.toml index 61e826b4bf..a391de8965 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -39,3 +39,8 @@ lto = true codegen-units = 1 strip = "symbols" opt-level = "z" + +[profile.bench] +inherits = "release" +strip = "none" +debug = true From d994bb106f2f4a87e62d5fbdc031d72207ee3ef3 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 12:24:24 +0530 Subject: [PATCH 06/15] refactor: add PatternMatcher::from_slice for Arc<[Fact]> input Adds MatcherStorage enum with Owned(FactStorage) and Slice(Arc<[Fact]>) variants. from_slice constructor used by the executor snapshot path. Existing new(FactStorage) constructor and all evaluator call sites unchanged. Part of phase 7.4 snapshot fix. --- src/query/datalog/matcher.rs | 148 ++++++++++++++++++++++++++++++++++- 1 file changed, 144 insertions(+), 4 deletions(-) diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs index 14652e9241..d1a7eae8e9 100644 --- a/src/query/datalog/matcher.rs +++ b/src/query/datalog/matcher.rs @@ -2,20 +2,43 @@ use super::types::{EdnValue, Pattern}; use crate::graph::FactStorage; use crate::graph::types::{EntityId, Fact, Value}; use std::collections::HashMap; +use std::sync::Arc; use uuid::Uuid; /// Variable bindings for query execution /// Maps variable names (e.g., "?name") to their bound values pub type Bindings = HashMap; +enum MatcherStorage { + Owned(FactStorage), + #[allow(dead_code)] // call site added in Task 5 (filter_facts_for_query snapshot fix) + Slice(Arc<[Fact]>), +} + /// Pattern matcher that finds facts matching a pattern and produces bindings pub struct PatternMatcher { - storage: FactStorage, + storage: MatcherStorage, } impl PatternMatcher { pub fn new(storage: FactStorage) -> Self { - PatternMatcher { storage } + PatternMatcher { storage: MatcherStorage::Owned(storage) } + } + + /// Constructs a [`PatternMatcher`] over a pre-built, already-filtered slice of + /// asserted facts. The caller is responsible for ensuring the slice contains + /// only currently asserted facts (equivalent to `FactStorage::get_asserted_facts()` + /// at the snapshot moment). No additional filtering is applied at match time. + #[allow(dead_code)] // call site added in Task 5 (filter_facts_for_query snapshot fix) + pub(crate) fn from_slice(facts: Arc<[Fact]>) -> Self { + PatternMatcher { storage: MatcherStorage::Slice(facts) } + } + + fn get_facts(&self) -> Vec { + match &self.storage { + MatcherStorage::Owned(s) => s.get_asserted_facts().unwrap_or_default(), + MatcherStorage::Slice(s) => s.to_vec(), + } } /// Match a single pattern against all facts in storage @@ -24,7 +47,7 @@ impl PatternMatcher { let mut results = Vec::new(); // Get all currently asserted facts - let facts = self.storage.get_asserted_facts().unwrap_or_default(); + let facts = self.get_facts(); for fact in facts { if let Some(bindings) = self.match_fact_against_pattern(&fact, pattern) { @@ -219,7 +242,7 @@ impl PatternMatcher { fn match_pattern_with_bindings(&self, pattern: &Pattern, existing: &Bindings) -> Vec { let mut results = Vec::new(); - let facts = self.storage.get_asserted_facts().unwrap_or_default(); + let facts = self.get_facts(); for fact in facts { // Try to match with existing bindings @@ -578,4 +601,121 @@ mod tests { assert_eq!(results.len(), 1); assert_eq!(results[0].get("?x"), Some(&Value::Integer(42))); } + + #[test] + fn test_from_slice_matches_same_as_owned() { + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + storage + .transact( + vec![(alice, ":person/name".to_string(), Value::String("Alice".to_string()))], + None, + ) + .unwrap(); + + // Build owned matcher the existing way + let owned_matcher = PatternMatcher::new(storage.clone()); + + // Build slice matcher via from_slice + let facts: Arc<[Fact]> = Arc::from(storage.get_asserted_facts().unwrap()); + let slice_matcher = PatternMatcher::from_slice(facts); + + let pattern = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":person/name".to_string()), + EdnValue::Symbol("?name".to_string()), + ); + + let owned_results = owned_matcher.match_pattern(&pattern); + let slice_results = slice_matcher.match_pattern(&pattern); + + assert_eq!(owned_results.len(), slice_results.len(), "result count mismatch"); + assert_eq!( + owned_results[0].get("?name"), + slice_results[0].get("?name"), + "bound value mismatch" + ); + } + + #[test] + fn test_from_slice_empty() { + let empty: Arc<[Fact]> = Arc::from(vec![]); + let matcher = PatternMatcher::from_slice(empty); + let pattern = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":any".to_string()), + EdnValue::Symbol("?v".to_string()), + ); + let results = matcher.match_pattern(&pattern); + assert!(results.is_empty(), "empty slice should produce no results"); + } + + #[test] + fn test_from_slice_respects_caller_prefiltering() { + // The Slice arm applies no internal filtering โ€” the caller is responsible. + // This test verifies that if the caller correctly excludes retracted facts + // before building the slice, the matcher respects that. + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + storage + .transact( + vec![(alice, ":name".to_string(), Value::String("Alice".to_string()))], + None, + ) + .unwrap(); + storage + .retract(vec![(alice, ":name".to_string(), Value::String("Alice".to_string()))]) + .unwrap(); + + // net_asserted_facts() returns the true net state: for each (entity, attribute, value) + // triple, the most recent record wins; retractions exclude the triple entirely. + let asserted: Arc<[Fact]> = + Arc::from(crate::graph::storage::net_asserted_facts(storage.get_all_facts().unwrap())); + let matcher = PatternMatcher::from_slice(asserted); + + let pattern = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":name".to_string()), + EdnValue::Symbol("?v".to_string()), + ); + let results = matcher.match_pattern(&pattern); + assert!(results.is_empty(), "retracted fact should not appear in slice-based matcher"); + } + + #[test] + fn test_from_slice_no_internal_filtering() { + // from_slice does NO filtering โ€” the caller must pre-filter. + // If the caller passes a raw slice that includes a retracted fact, + // the matcher will return it. This is intentional by design. + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + storage + .transact( + vec![(alice, ":name".to_string(), Value::String("Alice".to_string()))], + None, + ) + .unwrap(); + storage + .retract(vec![(alice, ":name".to_string(), Value::String("Alice".to_string()))]) + .unwrap(); + + // Deliberately build a raw, unfiltered slice (all facts, including the retraction) + // This simulates a caller mistake โ€” passing unfiltered facts to from_slice. + let all_facts: Arc<[Fact]> = Arc::from(storage.get_all_facts().unwrap()); + let matcher = PatternMatcher::from_slice(all_facts); + + let pattern = Pattern::new( + EdnValue::Symbol("?e".to_string()), + EdnValue::Keyword(":name".to_string()), + EdnValue::Symbol("?v".to_string()), + ); + let results = matcher.match_pattern(&pattern); + + // The matcher returns ALL facts in the slice โ€” both the assert and retract records. + // Caller must pre-filter; from_slice does not filter internally. + assert!( + !results.is_empty(), + "from_slice does not filter internally โ€” raw slice passes through unchanged" + ); + } } From 887df1430e68416a3008f07668afdbfcc12a8f5e Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 12:35:05 +0530 Subject: [PATCH 07/15] =?UTF-8?q?test:=20pin=20filter=5Ffacts=5Ffor=5Fquer?= =?UTF-8?q?y=20semantics=20=E2=80=94=20failing=20(red=20state)?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Two unit tests for filter_facts_for_query in executor.rs #[cfg(test)]: net-asserted view (retracted facts excluded) and valid-time filtering. Tests currently fail to compile; Task 5 changes the return type to Arc<[Fact]> to make them pass. Phase 7.4. Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/executor.rs | 120 ++++++++++++++++++++++++++++++++++ 1 file changed, 120 insertions(+) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index e5adeed6a4..d2bedabc69 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -2488,6 +2488,126 @@ mod tests { assert_eq!(results_with.len(), 2); assert_eq!(results_with[0][1], Value::Integer(50)); } + + #[test] + fn test_filter_facts_for_query_returns_net_asserted_slice() { + // Setup: one fact asserted then retracted, one fact left standing. + // After filter_facts_for_query, only the standing fact should appear. + // The return type (Arc<[Fact]>) exposes .len() and index access [0]. + // NOTE: this test currently FAILS TO COMPILE because filter_facts_for_query + // still returns Result. Task 5 will change it to Result>. + use uuid::Uuid; + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + + // tx 1: assert name + storage + .transact( + vec![( + alice, + ":person/name".to_string(), + Value::String("Alice".to_string()), + )], + None, + ) + .unwrap(); + + // tx 2: retract name โ€” net state for name is now gone + storage + .retract(vec![( + alice, + ":person/name".to_string(), + Value::String("Alice".to_string()), + )]) + .unwrap(); + + // tx 3: assert age โ€” this is the only net-asserted fact + storage + .transact( + vec![(alice, ":person/age".to_string(), Value::Integer(30))], + None, + ) + .unwrap(); + + let executor = DatalogExecutor::new(storage); + let query = DatalogQuery { + find: vec![], + where_clauses: vec![], + as_of: None, + valid_at: Some(ValidAt::AnyValidTime), + with_vars: vec![], + }; + + // Task 5 changes the return type from FactStorage to Arc<[Fact]>. + // Until then, .len() and [0] do not compile on FactStorage โ†’ intentional red state. + let facts = executor.filter_facts_for_query(&query).unwrap(); + assert_eq!(facts.len(), 1, "expected exactly 1 net-asserted fact"); + assert_eq!(facts[0].attribute, ":person/age"); + } + + #[test] + fn test_filter_facts_for_query_valid_time_filter() { + // Setup: one fact with a narrow valid-time window (1000..2000), one open-ended. + // Query with valid_at inside the window โ†’ both facts visible. + // Query with valid_at outside the window โ†’ only the open-ended fact visible. + // NOTE: this test currently FAILS TO COMPILE because filter_facts_for_query + // still returns Result. Task 5 will change it to Result>. + use crate::graph::types::TransactOptions; + use uuid::Uuid; + let storage = FactStorage::new(); + let alice = Uuid::new_v4(); + + // Fact valid only during [1000, 2000) + storage + .transact( + vec![( + alice, + ":employment/status".to_string(), + Value::String("active".to_string()), + )], + Some(TransactOptions::new(Some(1000_i64), Some(2000_i64))), + ) + .unwrap(); + + // Fact valid forever (open-ended) + storage + .transact( + vec![( + alice, + ":person/name".to_string(), + Value::String("Alice".to_string()), + )], + None, + ) + .unwrap(); + + let executor = DatalogExecutor::new(storage); + + // Query inside the window: both facts should be visible + let query_inside = DatalogQuery { + find: vec![], + where_clauses: vec![], + as_of: None, + valid_at: Some(ValidAt::Timestamp(1500_i64)), + with_vars: vec![], + }; + // Task 5 changes the return type from FactStorage to Arc<[Fact]>. + // Until then, .len() does not compile on FactStorage โ†’ intentional red state. + let facts_inside = executor.filter_facts_for_query(&query_inside).unwrap(); + assert_eq!(facts_inside.len(), 2, "both facts visible at t=1500"); + + // Query outside the window: only the open-ended name fact should be visible + let query_outside = DatalogQuery { + find: vec![], + where_clauses: vec![], + as_of: None, + valid_at: Some(ValidAt::Timestamp(3000_i64)), + with_vars: vec![], + }; + let facts_outside = executor.filter_facts_for_query(&query_outside).unwrap(); + assert_eq!(facts_outside.len(), 1, "only open-ended fact visible at t=3000"); + assert_eq!(facts_outside[0].attribute, ":person/name"); + } } #[cfg(test)] From 2dea2a29e530e3bb6d16902c06ec1f9082af327d Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 12:40:04 +0530 Subject: [PATCH 08/15] refactor: change apply_or_clauses and evaluate_not_join to take Arc<[Fact]> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit All call sites convert FactStorage โ†’ Arc at call time via get_asserted_facts(). No semantic change. Prepares for filter_facts_for_query returning Arc directly. Part of phase 7.4 snapshot fix. Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/evaluator.rs | 13 ++++++--- src/query/datalog/executor.rs | 48 +++++++++++++++++++++------------- src/query/datalog/matcher.rs | 2 -- 3 files changed, 39 insertions(+), 24 deletions(-) diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index 55885ad757..b127c1e843 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -416,7 +416,7 @@ pub fn evaluate_not_join( join_vars: &[String], clauses: &[WhereClause], binding: &Bindings, - storage: &FactStorage, + storage: Arc<[Fact]>, ) -> bool { // Build a partial binding containing only the join variables let partial: Bindings = join_vars @@ -444,7 +444,7 @@ pub fn evaluate_not_join( .filter(|c| matches!(c, WhereClause::Expr { .. })) .collect(); - let matcher = PatternMatcher::new(storage.clone()); + let matcher = PatternMatcher::from_slice(storage.clone()); let mut not_bindings: Vec = if substituted.is_empty() { // Expr-only not-join body: seed with the partial binding so variables resolve. vec![partial.clone()] @@ -693,7 +693,7 @@ impl StratifiedEvaluator { let expanded = apply_or_clauses( &rule.body, raw_candidates, - &accumulated, + Arc::from(accumulated.get_asserted_facts().unwrap_or_default()), ®istry_guard, None, None, @@ -770,7 +770,12 @@ impl StratifiedEvaluator { } for (join_vars, nj_clauses) in ¬_join_clauses { - if evaluate_not_join(join_vars, nj_clauses, &binding, &accumulated) { + if evaluate_not_join( + join_vars, + nj_clauses, + &binding, + Arc::from(accumulated.get_asserted_facts().unwrap_or_default()), + ) { continue 'binding; } } diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index d2bedabc69..3b355b0558 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -218,7 +218,7 @@ impl DatalogExecutor { let bindings = apply_or_clauses( &query.where_clauses, bindings, - &filtered_storage, + Arc::from(filtered_storage.get_asserted_facts().unwrap_or_default()), &rules_guard, query.as_of.clone(), query.valid_at.clone(), @@ -250,17 +250,23 @@ impl DatalogExecutor { let not_filtered: Vec<_> = if not_clauses.is_empty() && not_join_clauses.is_empty() { bindings } else { - let not_storage = filtered_storage.clone(); + let not_storage: Arc<[Fact]> = + Arc::from(filtered_storage.get_asserted_facts().unwrap_or_default()); bindings .into_iter() .filter(|binding| { for not_body in ¬_clauses { - if not_body_matches(not_body, binding, ¬_storage) { + if not_body_matches(not_body, binding, not_storage.clone()) { return false; } } for (join_vars, nj_clauses) in ¬_join_clauses { - if evaluate_not_join(join_vars, nj_clauses, binding, ¬_storage) { + if evaluate_not_join( + join_vars, + nj_clauses, + binding, + not_storage.clone(), + ) { return false; } } @@ -354,7 +360,7 @@ impl DatalogExecutor { let bindings = apply_or_clauses( &query.where_clauses, bindings, - &derived_storage, + Arc::from(derived_storage.get_asserted_facts().unwrap_or_default()), &rules_guard, query.as_of.clone(), query.valid_at.clone(), @@ -388,7 +394,8 @@ impl DatalogExecutor { let not_filtered: Vec<_> = if not_clauses.is_empty() && not_join_clauses.is_empty() { bindings } else { - let not_storage = derived_storage.clone(); + let not_storage: Arc<[Fact]> = + Arc::from(derived_storage.get_asserted_facts().unwrap_or_default()); bindings .into_iter() .filter(|binding| { @@ -452,7 +459,7 @@ impl DatalogExecutor { .collect(); // Compute not_bindings: if no patterns, seed with current binding. - let m = PatternMatcher::new(not_storage.clone()); + let m = PatternMatcher::from_slice(not_storage.clone()); let mut not_bindings: Vec = if substituted.is_empty() { vec![binding.clone()] } else { @@ -474,7 +481,12 @@ impl DatalogExecutor { } } for (join_vars, nj_clauses) in ¬_join_clauses { - if evaluate_not_join(join_vars, nj_clauses, binding, ¬_storage) { + if evaluate_not_join( + join_vars, + nj_clauses, + binding, + not_storage.clone(), + ) { return false; } } @@ -547,7 +559,7 @@ impl DatalogExecutor { fn not_body_matches( not_body: &[WhereClause], outer: &Binding, - storage: &crate::graph::FactStorage, + storage: Arc<[Fact]>, ) -> bool { use crate::query::datalog::evaluator::substitute_pattern; @@ -564,7 +576,7 @@ fn not_body_matches( }) .collect(); - let matcher = crate::query::datalog::matcher::PatternMatcher::new(storage.clone()); + let matcher = crate::query::datalog::matcher::PatternMatcher::from_slice(storage.clone()); let mut not_bindings: Vec = if patterns.is_empty() { // Expr-only not body: start with the outer binding so variables resolve. vec![outer.clone()] @@ -838,7 +850,7 @@ type Binding = std::collections::HashMap; pub(crate) fn evaluate_branch( branch: &[WhereClause], incoming: Vec, - storage: &FactStorage, + storage: Arc<[Fact]>, rules: &crate::query::datalog::rules::RuleRegistry, as_of: Option, valid_at: Option, @@ -862,7 +874,7 @@ pub(crate) fn evaluate_branch( }) .collect(); - let matcher = PatternMatcher::new(storage.clone()); + let matcher = PatternMatcher::from_slice(storage.clone()); let bindings = if patterns.is_empty() { incoming } else { @@ -877,7 +889,7 @@ pub(crate) fn evaluate_branch( let bindings = apply_or_clauses( branch, bindings, - storage, + storage.clone(), rules, as_of.clone(), valid_at.clone(), @@ -913,12 +925,12 @@ pub(crate) fn evaluate_branch( .into_iter() .filter(|binding| { for not_body in ¬_clauses { - if not_body_matches(not_body, binding, storage) { + if not_body_matches(not_body, binding, storage.clone()) { return false; } } for (join_vars, nj_clauses) in ¬_join_clauses { - if evaluate_not_join(join_vars, nj_clauses, binding, storage) { + if evaluate_not_join(join_vars, nj_clauses, binding, storage.clone()) { return false; } } @@ -941,7 +953,7 @@ pub(crate) fn evaluate_branch( pub(crate) fn apply_or_clauses( clauses: &[WhereClause], mut bindings: Vec, - storage: &FactStorage, + storage: Arc<[Fact]>, rules: &crate::query::datalog::rules::RuleRegistry, as_of: Option, valid_at: Option, @@ -954,7 +966,7 @@ pub(crate) fn apply_or_clauses( let branch_result = evaluate_branch( branch, bindings.clone(), - storage, + storage.clone(), rules, as_of.clone(), valid_at.clone(), @@ -980,7 +992,7 @@ pub(crate) fn apply_or_clauses( let branch_result = evaluate_branch( branch, bindings.clone(), - storage, + storage.clone(), rules, as_of.clone(), valid_at.clone(), diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs index d1a7eae8e9..e0ba81de6a 100644 --- a/src/query/datalog/matcher.rs +++ b/src/query/datalog/matcher.rs @@ -11,7 +11,6 @@ pub type Bindings = HashMap; enum MatcherStorage { Owned(FactStorage), - #[allow(dead_code)] // call site added in Task 5 (filter_facts_for_query snapshot fix) Slice(Arc<[Fact]>), } @@ -29,7 +28,6 @@ impl PatternMatcher { /// asserted facts. The caller is responsible for ensuring the slice contains /// only currently asserted facts (equivalent to `FactStorage::get_asserted_facts()` /// at the snapshot moment). No additional filtering is applied at match time. - #[allow(dead_code)] // call site added in Task 5 (filter_facts_for_query snapshot fix) pub(crate) fn from_slice(facts: Arc<[Fact]>) -> Self { PatternMatcher { storage: MatcherStorage::Slice(facts) } } From 43a90e614d90c3b831e472809a6f1e0a65b1daac Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 12:48:49 +0530 Subject: [PATCH 09/15] perf: eliminate FactStorage index rebuild in execute_query path filter_facts_for_query now returns Arc<[Fact]> instead of FactStorage, eliminating the O(N) BTreeMap rebuild (4 indexes x N facts) on every non-rules query call. execute_query constructs no FactStorage at all. execute_query_with_rules still converts Arc -> FactStorage for StratifiedEvaluator (deferred to post-profiling decision). Also fixes the test_filter_facts_for_query_valid_time_filter test: the "open-ended" fact now uses explicit valid_from=0 so it is visible at the test's query timestamps (1500, 3000) rather than at tx_id_now() which is epoch-ms and far larger. Phase 7.4. Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/executor.rs | 92 +++++++++++++++-------------------- 1 file changed, 40 insertions(+), 52 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 3b355b0558..81b0220914 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -128,32 +128,21 @@ impl DatalogExecutor { Ok(QueryResult::Retracted(tx_id)) } - /// Build a filtered FactStorage for a query's temporal constraints. + /// Build a filtered fact snapshot for a query's temporal constraints. /// /// Step 1: apply transaction-time filter (`:as-of`) โ€” defaults to all facts. - /// Step 2: discard retracted facts within the tx window. + /// Step 2: discard retracted facts within the tx window (`net_asserted_facts`). /// Step 3: apply valid-time filter (`:valid-at`) โ€” defaults to "currently valid". /// - /// # Performance note + /// Returns an `Arc<[Fact]>` snapshot. `.clone()` is a cheap Arc refcount increment, + /// so `or`-branches and `not`/`not-join` sub-evaluations share the same allocation. + /// The three steps above are paid exactly once per `execute_query` / + /// `execute_query_with_rules` call. /// - /// This method is O(N) in the total number of facts on every query: - /// - /// 1. `get_all_facts()` streams all committed (on-disk) facts and clones the - /// pending in-memory `Vec`. - /// 2. A brand-new `FactStorage` is constructed and all four indexes (EAVT/AEVT/AVET/VAET) - /// are rebuilt from scratch via one `load_fact()` call per surviving fact. - /// - /// Subsequent `.clone()` calls on the returned `FactStorage` are cheap (Arc refcount), - /// so `or`-branches and `not`/`not-join` sub-evaluations do not add further full scans. - /// The cost is paid exactly once per `execute_query` / `execute_query_with_rules` call. - /// - /// **TODO (optimizer phase)**: Replace this with a read-only snapshot type โ€” - /// e.g. `Arc<[Fact]>` โ€” so that the pattern matcher can work directly against an - /// immutable slice without rebuilding the index structure. The existing on-disk B+tree - /// indexes (EAVT/AEVT/AVET/VAET) should be used for selective lookups instead of a - /// full scan + rebuild. This is the primary query performance bottleneck for databases - /// with more than a few thousand facts. - fn filter_facts_for_query(&self, query: &DatalogQuery) -> Result { + /// **Post-1.0 backlog**: Use the on-disk B+tree indexes (EAVT/AEVT/AVET/VAET) for + /// selective attribute/entity lookups instead of the full `get_all_facts()` scan (step 1). + /// Also investigate caching the `net_asserted_facts()` result and invalidating on write (step 2). + fn filter_facts_for_query(&self, query: &DatalogQuery) -> Result> { let now = tx_id_now() as i64; // Step 1: transaction-time filter @@ -180,12 +169,7 @@ impl DatalogExecutor { .collect(), }; - // Build a temporary FactStorage with the filtered facts - let filtered_storage = FactStorage::new(); - for fact in valid_filtered { - filtered_storage.load_fact(fact)?; - } - Ok(filtered_storage) + Ok(Arc::from(valid_filtered)) } /// Execute a query: find matching facts and return specified variables @@ -197,8 +181,8 @@ impl DatalogExecutor { } // Apply temporal filters before pattern matching - let filtered_storage = self.filter_facts_for_query(&query)?; - let matcher = PatternMatcher::new(filtered_storage.clone()); // keep filtered_storage for not-filter + let filtered_facts = self.filter_facts_for_query(&query)?; + let matcher = PatternMatcher::from_slice(filtered_facts.clone()); let patterns = query.get_patterns(); // Plan patterns: assign index hints and reorder by selectivity. @@ -218,7 +202,7 @@ impl DatalogExecutor { let bindings = apply_or_clauses( &query.where_clauses, bindings, - Arc::from(filtered_storage.get_asserted_facts().unwrap_or_default()), + filtered_facts.clone(), &rules_guard, query.as_of.clone(), query.valid_at.clone(), @@ -250,13 +234,11 @@ impl DatalogExecutor { let not_filtered: Vec<_> = if not_clauses.is_empty() && not_join_clauses.is_empty() { bindings } else { - let not_storage: Arc<[Fact]> = - Arc::from(filtered_storage.get_asserted_facts().unwrap_or_default()); bindings .into_iter() .filter(|binding| { for not_body in ¬_clauses { - if not_body_matches(not_body, binding, not_storage.clone()) { + if not_body_matches(not_body, binding, filtered_facts.clone()) { return false; } } @@ -265,7 +247,7 @@ impl DatalogExecutor { join_vars, nj_clauses, binding, - not_storage.clone(), + filtered_facts.clone(), ) { return false; } @@ -306,7 +288,15 @@ impl DatalogExecutor { .collect(); // Apply temporal filters before evaluating recursive rules - let filtered_storage = self.filter_facts_for_query(&query)?; + let filtered_facts = self.filter_facts_for_query(&query)?; + + // Convert to FactStorage for StratifiedEvaluator (needs mutable accumulation) + // TODO (post-1.0): use FactStorage::new_noindex() once profiling confirms rules-path + // index rebuild is also a bottleneck. + let filtered_storage = FactStorage::new(); + for fact in filtered_facts.iter().cloned() { + filtered_storage.load_fact(fact)?; + } // Create StratifiedEvaluator โ€” handles negation, stratification, and positive-only rules let evaluator = StratifiedEvaluator::new( @@ -351,16 +341,21 @@ impl DatalogExecutor { all_patterns.push(pattern); } + // Compute derived_facts Arc once; reuse for or-clauses and not-post-filter. + // NOTE: must use derived_storage (includes rule-derived facts), not filtered_facts (base facts only) + let derived_facts: Arc<[Fact]> = + Arc::from(derived_storage.get_asserted_facts().unwrap_or_default()); + // Match all patterns against derived facts - let matcher = PatternMatcher::new(derived_storage.clone()); + let matcher = PatternMatcher::from_slice(derived_facts.clone()); let bindings = matcher.match_patterns(&all_patterns); - // Apply Or/OrJoin clauses against derived_storage (rules already evaluated) + // Apply Or/OrJoin clauses against derived facts (rules already evaluated) let rules_guard = self.rules.read().unwrap(); let bindings = apply_or_clauses( &query.where_clauses, bindings, - Arc::from(derived_storage.get_asserted_facts().unwrap_or_default()), + derived_facts.clone(), &rules_guard, query.as_of.clone(), query.valid_at.clone(), @@ -394,8 +389,6 @@ impl DatalogExecutor { let not_filtered: Vec<_> = if not_clauses.is_empty() && not_join_clauses.is_empty() { bindings } else { - let not_storage: Arc<[Fact]> = - Arc::from(derived_storage.get_asserted_facts().unwrap_or_default()); bindings .into_iter() .filter(|binding| { @@ -459,7 +452,7 @@ impl DatalogExecutor { .collect(); // Compute not_bindings: if no patterns, seed with current binding. - let m = PatternMatcher::from_slice(not_storage.clone()); + let m = PatternMatcher::from_slice(derived_facts.clone()); let mut not_bindings: Vec = if substituted.is_empty() { vec![binding.clone()] } else { @@ -485,7 +478,7 @@ impl DatalogExecutor { join_vars, nj_clauses, binding, - not_storage.clone(), + derived_facts.clone(), ) { return false; } @@ -2506,8 +2499,6 @@ mod tests { // Setup: one fact asserted then retracted, one fact left standing. // After filter_facts_for_query, only the standing fact should appear. // The return type (Arc<[Fact]>) exposes .len() and index access [0]. - // NOTE: this test currently FAILS TO COMPILE because filter_facts_for_query - // still returns Result. Task 5 will change it to Result>. use uuid::Uuid; let storage = FactStorage::new(); let alice = Uuid::new_v4(); @@ -2550,8 +2541,6 @@ mod tests { with_vars: vec![], }; - // Task 5 changes the return type from FactStorage to Arc<[Fact]>. - // Until then, .len() and [0] do not compile on FactStorage โ†’ intentional red state. let facts = executor.filter_facts_for_query(&query).unwrap(); assert_eq!(facts.len(), 1, "expected exactly 1 net-asserted fact"); assert_eq!(facts[0].attribute, ":person/age"); @@ -2562,8 +2551,7 @@ mod tests { // Setup: one fact with a narrow valid-time window (1000..2000), one open-ended. // Query with valid_at inside the window โ†’ both facts visible. // Query with valid_at outside the window โ†’ only the open-ended fact visible. - // NOTE: this test currently FAILS TO COMPILE because filter_facts_for_query - // still returns Result. Task 5 will change it to Result>. + // filter_facts_for_query now returns Result> (changed in Task 5). use crate::graph::types::TransactOptions; use uuid::Uuid; let storage = FactStorage::new(); @@ -2581,7 +2569,9 @@ mod tests { ) .unwrap(); - // Fact valid forever (open-ended) + // Fact valid forever (open-ended): explicit valid_from=0 so it is visible at t=1500 and t=3000. + // Passing None would set valid_from=tx_id_now() (current epoch ms โ‰ˆ 1.7T), which is + // far beyond the test's query timestamps. storage .transact( vec![( @@ -2589,7 +2579,7 @@ mod tests { ":person/name".to_string(), Value::String("Alice".to_string()), )], - None, + Some(TransactOptions::new(Some(0_i64), None)), ) .unwrap(); @@ -2603,8 +2593,6 @@ mod tests { valid_at: Some(ValidAt::Timestamp(1500_i64)), with_vars: vec![], }; - // Task 5 changes the return type from FactStorage to Arc<[Fact]>. - // Until then, .len() does not compile on FactStorage โ†’ intentional red state. let facts_inside = executor.filter_facts_for_query(&query_inside).unwrap(); assert_eq!(facts_inside.len(), 2, "both facts visible at t=1500"); From 4b996a401e6557786f2582a18c473a2f3097d544 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 12:53:44 +0530 Subject: [PATCH 10/15] refactor: compute accumulated_facts Arc once per evaluator rule iteration Replaces four separate accumulated.clone() + get_asserted_facts() calls with a single Arc<[Fact]> computed once and reused for PatternMatcher, apply_or_clauses, not-body matching, and evaluate_not_join. Part of phase 7.4 snapshot fix. Co-Authored-By: Claude Sonnet 4.6 --- src/query/datalog/evaluator.rs | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index b127c1e843..10f7e49f69 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -683,7 +683,12 @@ impl StratifiedEvaluator { .filter(|c| matches!(c, WhereClause::Expr { .. })) .collect(); - let matcher = PatternMatcher::new(accumulated.clone()); + // Compute once; reuse for matcher, apply_or_clauses, not-body matching, and evaluate_not_join. + // Declared at loop body scope so it remains in scope for all four usages below. + let accumulated_facts: Arc<[Fact]> = + Arc::from(accumulated.get_asserted_facts().unwrap_or_default()); + + let matcher = PatternMatcher::from_slice(accumulated_facts.clone()); let raw_candidates = matcher.match_patterns(&positive_patterns); // Apply Or/OrJoin clauses before Expr (mirrors top-level execute_query order) @@ -693,7 +698,7 @@ impl StratifiedEvaluator { let expanded = apply_or_clauses( &rule.body, raw_candidates, - Arc::from(accumulated.get_asserted_facts().unwrap_or_default()), + accumulated_facts.clone(), ®istry_guard, None, None, @@ -741,7 +746,7 @@ impl StratifiedEvaluator { }) .collect(); - let not_matcher = PatternMatcher::new(accumulated.clone()); + let not_matcher = PatternMatcher::from_slice(accumulated_facts.clone()); let mut not_bindings: Vec = if substituted.is_empty() { vec![binding.clone()] } else { @@ -774,7 +779,7 @@ impl StratifiedEvaluator { join_vars, nj_clauses, &binding, - Arc::from(accumulated.get_asserted_facts().unwrap_or_default()), + accumulated_facts.clone(), ) { continue 'binding; } From b6d55bf335fe27de5b02b78c4b9c44c5bd586296 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 13:42:18 +0530 Subject: [PATCH 11/15] =?UTF-8?q?docs:=20phase=207.4=20complete=20?= =?UTF-8?q?=E2=80=94=20snapshot=20fix,=20eliminate=20index=20rebuild?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit filter_facts_for_query returns Arc<[Fact]>; execute_query path constructs no FactStorage. PatternMatcher::from_slice added. 568 tests passing. ~62-65% speedup on non-rules queries at 10K facts. Co-Authored-By: Claude Sonnet 4.6 --- CHANGELOG.md | 21 +++++++++++++++++ CLAUDE.md | 2 +- README.md | 4 ++-- ROADMAP.md | 59 ++++++++++++++++++++++++++++++++---------------- TEST_COVERAGE.md | 50 +++++++++++++++++++++++++++++----------- llms.txt | 13 +++++++---- 6 files changed, 110 insertions(+), 39 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 61ea9d733a..d065a87fc3 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -5,6 +5,27 @@ 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). +## [0.13.1] โ€” 2026-03-27 + +### Performance + +- **`filter_facts_for_query` snapshot fix** โ€” function now returns `Arc<[Fact]>` instead of a throwaway `FactStorage`, eliminating the O(N) four-BTreeMap index rebuild that occurred on every non-rules query call. `execute_query` path constructs zero `FactStorage` objects. `execute_query_with_rules` still converts `Arc<[Fact]>` back to `FactStorage` for `StratifiedEvaluator` (deferred). +- ~62โ€“65% speedup on non-rules queries at 10K facts: `query/point_entity/10k` 22 ms โ†’ 8.6 ms; `aggregation/count_scale/10k` 28 ms โ†’ 9.7 ms. +- Evaluator loop: `accumulated_facts` computed once per iteration (was 4 separate `get_asserted_facts()` calls). + +### Added + +- `PatternMatcher::from_slice(Arc<[Fact]>)` constructor โ€” creates a matcher from an immutable fact snapshot without index reconstruction. + +### Technical + +- `apply_or_clauses` and `evaluate_not_join` signatures updated to accept `Arc<[Fact]>` instead of `&FactStorage`. +- 6 new tests: 4 in `matcher.rs` (unit), 2 in `executor.rs` (unit). + +### Tests + +- Total: 568 tests passing (390 unit + 172 integration + 6 doc) + ## [0.13.0] โ€” 2026-03-26 ### Added diff --git a/CLAUDE.md b/CLAUDE.md index b90dbd3adc..734250161e 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -165,7 +165,7 @@ Auto-migrates v1/v2/v3/v4/v5 โ†’ v6 on open/checkpoint. ## Test Coverage -**527 tests passing** (365 unit + 156 integration + 6 doc). +**568 tests passing** (390 unit + 172 integration + 6 doc). See `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 3034f5644d..98c3df9df3 100644 --- a/README.md +++ b/README.md @@ -4,7 +4,7 @@ [![Clippy Status](https://github.com/adityamukho/minigraf/actions/workflows/rust-clippy.yml/badge.svg)](https://github.com/adityamukho/minigraf/actions/workflows/rust-clippy.yml) [![License: MIT OR Apache-2.0](https://img.shields.io/badge/license-MIT%20OR%20Apache--2.0-blue.svg)](https://github.com/adityamukho/minigraf#license) [![Rust Edition](https://img.shields.io/badge/rust-2024-orange.svg)](https://blog.rust-lang.org/2024/10/17/Rust-1.82.0.html) -[![Phase](https://img.shields.io/badge/phase-7.2b%20complete-blue.svg)](https://github.com/adityamukho/minigraf/blob/main/ROADMAP.md) +[![Phase](https://img.shields.io/badge/phase-7.3%20complete-blue.svg)](https://github.com/adityamukho/minigraf/blob/main/ROADMAP.md) > **Embedded graph memory for AI agents, mobile apps, and the browser** โ€” the SQLite of bi-temporal graph databases @@ -67,7 +67,7 @@ db.execute(r#"(rule [(reachable ?a ?b) [?a :friend ?b]]) ```bash cargo run # interactive Datalog REPL -cargo test # run 527 tests +cargo test # run 568 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/ROADMAP.md b/ROADMAP.md index 21abfc2015..d29146fb38 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -515,7 +515,7 @@ Current v5 stores index data as paged blobs (page type `0x11`). v6 introduces pr - **7.2b** โœ… Arithmetic & predicate expression clauses (`[(< ?v 100)]`, `[(+ ?a ?b) ?c]`, string predicates, type predicates) - **7.2** ~~Aggregation (`count`, `sum`, `min`, `max`, `distinct`, `:with`) โ€” includes arithmetic filter predicates~~ โ†’ split into 7.2a + 7.2b - **7.3** โœ… Disjunction (`or` / `or-join`) -- **7.4** Query Optimizer Improvements (deferred from Phase 6.3) +- **7.4** โœ… Query Optimizer Improvements / `filter_facts_for_query` snapshot fix - **7.5** Tests + Error Coverage (โ‰ฅ90% branch coverage target) - **7.6** Prepared Statements (parse + plan once, execute many times, temporal bind slots) - **7.7** Temporal Metadata Bindings + Range Queries (`:db/valid-from`, `:db/valid-to`, `:db/tx-count` as queryable pseudo-attributes; unlocks Time Interval, Time-Point Lookup, Time-Interval Lookup query classes) @@ -689,12 +689,16 @@ Current v5 stores index data as paged blobs (page type `0x11`). v6 introduces pr **Estimated complexity**: 2-3 weeks -### 7.4 Query Optimizer Improvements (deferred from Phase 6.3) +### 7.4 Query Optimizer Improvements / `filter_facts_for_query` snapshot fix โœ… COMPLETE -- ๐ŸŽฏ **Profiling integration** โ€” before optimizing, instrument the benchmark suite with a profiler to identify actual hotspots rather than relying on code inspection. Add `pprof` as a Criterion profiler (via `criterion-pprof` or the `pprof` crate's Criterion integration) so that `cargo bench` can emit flamegraphs. Run the existing `minigraf_bench.rs` benchmarks at 10K/100K facts under the profiler to confirm `filter_facts_for_query`, index rebuild, and `net_asserted_facts` are the dominant costs before investing in the fix. Profiling must precede any structural change to the query execution path. -- ๐ŸŽฏ **`filter_facts_for_query` snapshot overhead** โ€” `executor.rs::filter_facts_for_query` is O(N) in total fact count on every query: it streams all committed on-disk facts, clones the pending `Vec`, and rebuilds all four indexes from scratch into a throwaway `FactStorage`. Fix: replace with a read-only `Arc<[Fact]>` snapshot so the pattern matcher works against an immutable slice without index reconstruction; whether to also use on-disk B+tree indexes for selective lookups is determined by profiling results. This is the primary query performance bottleneck at scale. +**Status**: โœ… Completed (March 2026, v0.13.1) -**Note**: The following items were originally scoped here but are deferred to the post-1.0 backlog: cost-based optimizer extensions for new clause types, rule evaluation optimization for `not`/`or`/aggregate rules, and predicate push-down. The original cost-estimate items required the new clause types to exist first (now satisfied by 7.1โ€“7.3), but the profiling-first constraint means they are lower priority than the snapshot fix. +- โœ… **Profiling integration** โ€” Criterion profiling gate added; flamegraph support via `pprof` crate. +- โœ… **`filter_facts_for_query` snapshot fix** โ€” `filter_facts_for_query` now returns `Arc<[Fact]>` instead of a throwaway `FactStorage`; eliminates O(N) four-BTreeMap index rebuild on every non-rules query call. `execute_query` path constructs zero `FactStorage` objects. `execute_query_with_rules` still converts `Arc<[Fact]>` back to `FactStorage` for `StratifiedEvaluator` (deferred to later phase). `apply_or_clauses` and `evaluate_not_join` signatures updated to accept `Arc<[Fact]>`. Evaluator loop: `accumulated_facts` computed once per iteration (was 4 separate `get_asserted_facts()` calls). `PatternMatcher::from_slice(Arc<[Fact]>)` constructor added. +- โœ… **Benchmark results**: ~62โ€“65% speedup on non-rules queries at 10K facts (`query/point_entity/10k`: 22 ms โ†’ 8.6 ms; `aggregation/count_scale/10k`: 28 ms โ†’ 9.7 ms). +- โœ… 568 tests passing (390 unit + 172 integration + 6 doc); version bumped to v0.13.1. + +**Note**: The following items were originally scoped here but are deferred to the post-1.0 backlog: cost-based optimizer extensions for new clause types, rule evaluation optimization for `not`/`or`/aggregate rules, and predicate push-down. ### 7.5 Tests + Error Coverage @@ -1449,6 +1453,22 @@ Push `Expr` predicate clauses (e.g. `[(> ?age 30)]`) down to filter bindings as - โœ… `eval_expr` / `is_truthy`: int/float promotion, integer division truncation, NaN guard, type mismatch โ†’ row drop, div/0 โ†’ row drop - โœ… `tests/predicate_expr_test.rs` โ€” 28 integration tests; 527 tests passing (365 unit + 156 integration + 6 doc) +### v0.13.0 - โœ… Phase 7.3 (Disjunction โ€” `or` / `or-join`) +- โœ… `WhereClause::Or(Vec>)` and `WhereClause::OrJoin { join_vars, branches }` variants +- โœ… `(or ...)` / `(or-join [?v...] ...)` in `:where` clauses and rule bodies; `(and ...)` grouping +- โœ… `match_patterns_seeded` on `PatternMatcher`; `evaluate_branch` / `apply_or_clauses` in `executor.rs` +- โœ… `DependencyGraph::from_rules` refactored with recursive `collect_clause_deps` +- โœ… `tests/disjunction_test.rs` โ€” 16 integration tests; 562 tests passing (384 unit + 172 integration + 6 doc) + +### v0.13.1 - โœ… Phase 7.4 (`filter_facts_for_query` snapshot fix) +- โœ… `filter_facts_for_query` returns `Arc<[Fact]>` โ€” eliminates O(N) four-BTreeMap index rebuild on every non-rules query call +- โœ… `execute_query` path constructs zero `FactStorage` objects; `execute_query_with_rules` still converts for `StratifiedEvaluator` +- โœ… `PatternMatcher::from_slice(Arc<[Fact]>)` constructor added +- โœ… `apply_or_clauses` and `evaluate_not_join` signatures updated to accept `Arc<[Fact]>` +- โœ… Evaluator loop: `accumulated_facts` computed once per iteration (was 4 separate `get_asserted_facts()` calls) +- โœ… ~62โ€“65% speedup on non-rules queries at 10K facts (`query/point_entity/10k`: 22 ms โ†’ 8.6 ms; `aggregation/count_scale/10k`: 28 ms โ†’ 9.7 ms) +- โœ… 568 tests passing (390 unit + 172 integration + 6 doc) + ### v1.0.0 - ๐ŸŽฏ Phase 7 (Datalog Completeness) - Stratified negation (`not` / `not-join`) - Aggregation (`count`, `sum`, `min`, `max`, `distinct`, `:with`) + arithmetic filter predicates @@ -1525,7 +1545,8 @@ When evaluating features, ask: - โœ… Phase 7.2a: Complete (March 2026) - Aggregation (`count`/`sum`/`min`/`max`/`distinct`/`:with`), 461 tests - โœ… Phase 7.2b: Complete (March 2026) - Arithmetic & predicate expression clauses, 527 tests - โœ… Phase 7.3: Complete (March 2026) - Disjunction (`or` / `or-join`), 562 tests -- ๐ŸŽฏ Phase 7.4โ€“7.7: optimizer, prepared statements, temporal metadata bindings; โ‰ฅ90% branch coverage - **NEXT** +- โœ… Phase 7.4: Complete (March 2026) - `filter_facts_for_query` snapshot fix, eliminate 4-index rebuild, 568 tests +- ๐ŸŽฏ Phase 7.5โ€“7.7: tests/error coverage, prepared statements, temporal metadata bindings; โ‰ฅ90% branch coverage - **NEXT** - ๐ŸŽฏ Phase 8: 3-4 months (Cross-platform โ€” WASM, mobile, language bindings) - ๐ŸŽฏ Phase 9: Ongoing (Ecosystem โ€” integration examples, cookbook, GraphRAG/LangChain examples) - ๐ŸŽฏ **v1.0.0: 9-12 months** @@ -1536,20 +1557,20 @@ When evaluating features, ask: ## Current Focus -**Right Now**: Phase 7.3 Complete โ€” Phase 7.4 Next (Query Optimizer Improvements) +**Right Now**: Phase 7.4 Complete โ€” Phase 7.5 Next (Tests + Error Coverage, โ‰ฅ90% branch coverage) -**Phase 7.3 Achievements**: -1. โœ… `WhereClause::Or(Vec>)` and `WhereClause::OrJoin { join_vars, branches }` variants in `types.rs` -2. โœ… `parse_or` / `parse_or_join` / `(and ...)` grouping in `parser.rs`; safety checks at all 4 clause sites -3. โœ… `match_patterns_seeded` on `PatternMatcher` for seeded branch evaluation -4. โœ… `evaluate_branch` / `apply_or_clauses` in `executor.rs`; union + deduplication across branches -5. โœ… `DependencyGraph::from_rules` refactored with `collect_clause_deps`; `Or`/`OrJoin` contribute positive edges -6. โœ… Rules with `or`/`or-join` route to `mixed_rules` path in `StratifiedEvaluator` -7. โœ… Integration tests in `tests/disjunction_test.rs` (16 tests); 562 tests passing (384 unit + 172 integration + 6 doc); version bumped to v0.13.0 +**Phase 7.4 Achievements**: +1. โœ… `filter_facts_for_query` returns `Arc<[Fact]>` โ€” eliminates O(N) four-BTreeMap index rebuild on every non-rules query call +2. โœ… `execute_query` path constructs zero `FactStorage` objects; `execute_query_with_rules` still converts for `StratifiedEvaluator` +3. โœ… `PatternMatcher::from_slice(Arc<[Fact]>)` constructor added +4. โœ… `apply_or_clauses` and `evaluate_not_join` signatures updated to accept `Arc<[Fact]>` +5. โœ… Evaluator loop: `accumulated_facts` computed once per iteration (was 4 separate `get_asserted_facts()` calls) +6. โœ… ~62โ€“65% speedup on non-rules queries at 10K facts (`query/point_entity/10k`: 22 ms โ†’ 8.6 ms; `aggregation/count_scale/10k`: 28 ms โ†’ 9.7 ms) +7. โœ… 568 tests passing (390 unit + 172 integration + 6 doc); version bumped to v0.13.1 -**Immediate Next Steps (Phase 7.4)**: -1. Query optimizer improvements for new clause types -2. Push error-path coverage toward โ‰ฅ90% target +**Immediate Next Steps (Phase 7.5)**: +1. Unit tests for each new clause type (parser, types, matcher) +2. Push error-path branch coverage toward โ‰ฅ90% target **Key Decisions Made**: - โœ… Datalog query language (simpler, better for temporal) @@ -1565,4 +1586,4 @@ See [GitHub Issues](https://github.com/adityamukho/minigraf/issues) for specific --- -Last Updated: Phase 7.3 Complete - Disjunction (`or`/`or-join`), benchmarks extended to cover negation/aggregation/disjunction/expressions, post-1.0 performance backlog added (March 2026) +Last Updated: Phase 7.4 Complete - `filter_facts_for_query` snapshot fix, eliminate O(N) index rebuild, ~62โ€“65% speedup on non-rules queries at 10K facts, 568 tests passing, v0.13.1 (March 2026) diff --git a/TEST_COVERAGE.md b/TEST_COVERAGE.md index 09eb93fb14..1621d0ed38 100644 --- a/TEST_COVERAGE.md +++ b/TEST_COVERAGE.md @@ -1,11 +1,11 @@ # Minigraf Test Coverage Report -**Last Updated**: Phase 7.2b COMPLETE - Arithmetic & Predicate Expression Clauses โœ… +**Last Updated**: Phase 7.4 COMPLETE - `filter_facts_for_query` snapshot fix โœ… ## Test Summary -**Total Tests**: 527 โœ… -- โœ… 365 unit tests (lib) +**Total Tests**: 568 โœ… +- โœ… 390 unit tests (lib) - โœ… 10 bi-temporal tests (integration) - โœ… 10 complex query tests (integration) - โœ… 9 recursive rules tests (integration) @@ -20,13 +20,36 @@ - โœ… 14 not-join tests (integration, Phase 7.1b) - โœ… 24 aggregation tests (integration, Phase 7.2a) - โœ… 28 predicate expression tests (integration, Phase 7.2b) +- โœ… 16 disjunction tests (integration, Phase 7.3) - โœ… 6 doc tests -**Status**: โœ… **All 527 tests passing** - -## Phase 7.2b Completion Status: โœ… COMPLETE - -**Core Features Implemented**: +**Status**: โœ… **All 568 tests passing** + +## Phase 7.4 Completion Status: โœ… COMPLETE + +**Phase 7.4 Features** (current, complete): +- โœ… `filter_facts_for_query` returns `Arc<[Fact]>` โ€” eliminates O(N) four-BTreeMap index rebuild on every non-rules query call +- โœ… `execute_query` path constructs zero `FactStorage` objects; `execute_query_with_rules` still converts for `StratifiedEvaluator` +- โœ… `PatternMatcher::from_slice(Arc<[Fact]>)` constructor added +- โœ… `apply_or_clauses` and `evaluate_not_join` signatures updated to accept `Arc<[Fact]>` +- โœ… Evaluator loop: `accumulated_facts` computed once per iteration (was 4 separate `get_asserted_facts()` calls) +- โœ… ~62โ€“65% speedup on non-rules queries at 10K facts (`query/point_entity/10k`: 22 ms โ†’ 8.6 ms; `aggregation/count_scale/10k`: 28 ms โ†’ 9.7 ms) +- โœ… 4 new unit tests in `matcher.rs`, 2 new unit tests in `executor.rs` (6 total) +- โœ… Version bumped to v0.13.1 + +## Phase 7.3 Completion Status: โœ… COMPLETE + +**Phase 7.3 Features** (current, complete): +- โœ… `WhereClause::Or(Vec>)` and `WhereClause::OrJoin { join_vars, branches }` variants in `types.rs` +- โœ… `(or branch1 branch2 ...)` and `(or-join [?v...] branch1 branch2 ...)` in `:where` clauses and rule bodies +- โœ… `(and ...)` grouping clause to collect multiple clauses into a single branch +- โœ… `match_patterns_seeded` on `PatternMatcher`; `evaluate_branch` and `apply_or_clauses` helpers in `executor.rs` +- โœ… `DependencyGraph::from_rules` refactored with recursive `collect_clause_deps`; `Or`/`OrJoin` branches contribute positive dependency edges +- โœ… Rules with `or`/`or-join` in bodies routed to `mixed_rules` path in `StratifiedEvaluator` +- โœ… `tests/disjunction_test.rs`: 16 integration tests (Phase 7.3) +- โœ… Version bumped to v0.13.0 + +**Core Features Implemented** (Phase 6.2): - โœ… Packed fact pages (`page_type = 0x02`): ~25 facts per 4KB page (~25ร— space reduction) - โœ… LRU page cache (`cache.rs`): approximate-LRU, read-lock on hits, `Arc>` entries - โœ… `CommittedFactReader` trait + `CommittedFactLoaderImpl`: on-demand fact resolution @@ -63,7 +86,7 @@ - โœ… File format v1โ†’v2 migration - โœ… UTC-only timestamp parsing (chrono, avoids GHSA-wcg3-cvx6-7396) -**Phase 7.2b Features** (current, complete): +**Phase 7.2b Features** (also complete): - โœ… `BinOp` (14 variants), `UnaryOp` (5 variants), `Expr` AST, `WhereClause::Expr { expr, binding }` in `types.rs` - โœ… Filter predicates: `[(< ?age 30)]`, `[(string? ?v)]`, `[(starts-with? ?tag "work")]`, `[(matches? ?email "...")]` - โœ… Arithmetic bindings: `[(+ ?price ?tax) ?total]`, nested `[(+ (* ?a 2) ?b) ?result]`, type-predicate binding `[(integer? ?v) ?is-int]` @@ -569,13 +592,14 @@ cargo test -- --nocapture - Stratified negation (`not` / `not-join`) verified: safety validation, stratification, negative cycle rejection, time-travel integration (Phase 7.1) - Aggregation verified: all 6 aggregate functions, `:with` grouping, bi-temporal + aggregate, rule + aggregate (Phase 7.2a) - Arithmetic & predicate expressions verified: all operators, silent-drop semantics, int/float promotion, regex validation, expr in not/rule body, bi-temporal + expr (Phase 7.2b) -- 527 tests covering all Phase 3-7.2b features +- Disjunction (`or` / `or-join`) verified: flat queries, rule bodies, nested or/not/expr, or-join with private variables, dependency graph (Phase 7.3) +- 562 tests covering all Phase 3-7.3 features -**Confidence Level**: โœ… **Production-ready for Phase 7.1 scope** +**Confidence Level**: โœ… **Production-ready for Phase 7.3 scope** -**Readiness for Phase 7.3**: โœ… **Ready to proceed** +**Readiness for Phase 7.4**: โœ… **Ready to proceed** -The aggregation + arithmetic/predicate expression capable, stratified-negation-capable, on-disk B+tree indexed, packed, cached bi-temporal Datalog engine is **solid, well-tested, and benchmarked**. +The disjunction + aggregation + arithmetic/predicate expression capable, stratified-negation-capable, on-disk B+tree indexed, packed, cached bi-temporal Datalog engine is **solid, well-tested, and benchmarked**. --- diff --git a/llms.txt b/llms.txt index e6b9a24697..462f9e7575 100644 --- a/llms.txt +++ b/llms.txt @@ -4,8 +4,8 @@ Minigraf is the SQLite of graph databases: zero configuration, one `.graph` file, embedded as a library. It stores facts in an Entity-Attribute-Value (EAV) model and queries them with Datalog, including recursive rules for graph traversal and stratified negation (`not` / `not-join`). Every fact carries two independent time dimensions (transaction time and valid time), enabling full bi-temporal time travel. -**Current version**: 0.11.0 (pre-1.0 โ€” API and file format may change before v1.0) -**Maturity**: See [README](https://github.com/adityamukho/minigraf/blob/main/README.md) for current phase and [ROADMAP](https://github.com/adityamukho/minigraf/blob/main/ROADMAP.md) for the full plan. ACID + WAL are production-quality. Covering indexes (EAVT/AEVT/AVET/VAET), packed page storage, LRU page cache, and on-disk B+tree indexes are complete. Stratified negation and scalar aggregation are complete. Not recommended for production use until v1.0 (file format stability guaranteed only after Phase 8). +**Current version**: 0.13.1 (pre-1.0 โ€” API and file format may change before v1.0) +**Maturity**: See [README](https://github.com/adityamukho/minigraf/blob/main/README.md) for current phase and [ROADMAP](https://github.com/adityamukho/minigraf/blob/main/ROADMAP.md) for the full plan. ACID + WAL are production-quality. Covering indexes (EAVT/AEVT/AVET/VAET), packed page storage, LRU page cache, and on-disk B+tree indexes are complete. Stratified negation, scalar aggregation, arithmetic/predicate expression clauses, and disjunction (`or`/`or-join`) are complete. Non-rules query path avoids all `FactStorage` index reconstruction (`filter_facts_for_query` snapshot fix, v0.13.1). Not recommended for production use until v1.0 (file format stability guaranteed only after Phase 8). ## Use for @@ -52,7 +52,7 @@ Query either axis independently or together: The unit of storage is `(entity, attribute, value, valid_from, valid_to, tx_id, tx_count, asserted)`. Entities are UUIDs. Attributes are keywords (`:person/name`). Values are strings, integers, floats, booleans, entity refs, keywords, or null. **Datalog queries** -Pattern matching with variable unification. Recursive rules use semi-naive fixed-point evaluation. Transitive closure and cycle-safe graph traversal are first-class. Stratified negation (`not` / `not-join`) is supported with negative-cycle detection at rule registration time. +Pattern matching with variable unification. Recursive rules use semi-naive fixed-point evaluation. Transitive closure and cycle-safe graph traversal are first-class. Stratified negation (`not` / `not-join`), scalar aggregation (`count`, `sum`, `min`, `max`, `count-distinct`, `sum-distinct`), arithmetic/predicate expression clauses (`[(< ?age 30)]`, `[(+ ?a ?b) ?c]`), and disjunction (`or` / `or-join`) are all supported. **ACID transactions** `begin_write()` โ†’ `commit()` / `rollback()`. Fact-level WAL with CRC32 protection. Crash recovery on open. @@ -130,6 +130,11 @@ tx.commit()?; :where [ ] ... (not [ ] ...) ;; optional, negation (not-join [?join-var ...] ...) ;; optional, existential negation + (or branch1 branch2 ...) ;; optional, disjunction (all branches bind same vars) + (or-join [?v ...] b1 b2 ...) ;; optional, existential disjunction + (and clause1 clause2 ...) ;; group clauses into one branch (inside or/or-join) + [( ?a ?b)] ;; filter predicate: <, >, <=, >=, =, !=, string?, etc. + [( ?a ?b) ?result] ;; arithmetic binding: +, -, *, / ]) ;; Recursive rule @@ -160,7 +165,7 @@ tx.commit()?; - `src/wal.rs` โ€” write-ahead log, CRC32 entries, crash recovery - `src/temporal.rs` โ€” UTC timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396) -## Performance summary (v0.11.0) +## Performance summary (v0.13.0) See [BENCHMARKS.md](https://github.com/adityamukho/minigraf/blob/main/BENCHMARKS.md) for full tables and methodology. From 1173fb7febe6b43beb103affe03157e4299dda8b Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 13:42:25 +0530 Subject: [PATCH 12/15] chore: bump version to v0.13.1 Co-Authored-By: Claude Sonnet 4.6 --- Cargo.toml | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/Cargo.toml b/Cargo.toml index a391de8965..0c9b396ddf 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,6 +1,6 @@ [package] name = "minigraf" -version = "0.13.0" +version = "0.13.1" edition = "2024" description = "Zero-config, single-file, embedded graph database with bi-temporal Datalog queries" license = "MIT OR Apache-2.0" From 8e5c1d1ea2a8f21ed90b6d6bc2346c40333e6960 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 13:50:26 +0530 Subject: [PATCH 13/15] style: apply cargo fmt formatting --- src/query/datalog/executor.rs | 28 +++++++----------- src/query/datalog/matcher.rs | 54 ++++++++++++++++++++++++++++------- 2 files changed, 53 insertions(+), 29 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 81b0220914..1d54ba7605 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -243,12 +243,8 @@ impl DatalogExecutor { } } for (join_vars, nj_clauses) in ¬_join_clauses { - if evaluate_not_join( - join_vars, - nj_clauses, - binding, - filtered_facts.clone(), - ) { + if evaluate_not_join(join_vars, nj_clauses, binding, filtered_facts.clone()) + { return false; } } @@ -474,12 +470,8 @@ impl DatalogExecutor { } } for (join_vars, nj_clauses) in ¬_join_clauses { - if evaluate_not_join( - join_vars, - nj_clauses, - binding, - derived_facts.clone(), - ) { + if evaluate_not_join(join_vars, nj_clauses, binding, derived_facts.clone()) + { return false; } } @@ -549,11 +541,7 @@ impl DatalogExecutor { /// Evaluate a `not` body against the current outer binding. /// /// Returns true if the body "matches" (i.e., the outer binding should be excluded). -fn not_body_matches( - not_body: &[WhereClause], - outer: &Binding, - storage: Arc<[Fact]>, -) -> bool { +fn not_body_matches(not_body: &[WhereClause], outer: &Binding, storage: Arc<[Fact]>) -> bool { use crate::query::datalog::evaluator::substitute_pattern; let patterns: Vec<_> = not_body @@ -2605,7 +2593,11 @@ mod tests { with_vars: vec![], }; let facts_outside = executor.filter_facts_for_query(&query_outside).unwrap(); - assert_eq!(facts_outside.len(), 1, "only open-ended fact visible at t=3000"); + assert_eq!( + facts_outside.len(), + 1, + "only open-ended fact visible at t=3000" + ); assert_eq!(facts_outside[0].attribute, ":person/name"); } } diff --git a/src/query/datalog/matcher.rs b/src/query/datalog/matcher.rs index e0ba81de6a..012114164b 100644 --- a/src/query/datalog/matcher.rs +++ b/src/query/datalog/matcher.rs @@ -21,7 +21,9 @@ pub struct PatternMatcher { impl PatternMatcher { pub fn new(storage: FactStorage) -> Self { - PatternMatcher { storage: MatcherStorage::Owned(storage) } + PatternMatcher { + storage: MatcherStorage::Owned(storage), + } } /// Constructs a [`PatternMatcher`] over a pre-built, already-filtered slice of @@ -29,7 +31,9 @@ impl PatternMatcher { /// only currently asserted facts (equivalent to `FactStorage::get_asserted_facts()` /// at the snapshot moment). No additional filtering is applied at match time. pub(crate) fn from_slice(facts: Arc<[Fact]>) -> Self { - PatternMatcher { storage: MatcherStorage::Slice(facts) } + PatternMatcher { + storage: MatcherStorage::Slice(facts), + } } fn get_facts(&self) -> Vec { @@ -606,7 +610,11 @@ mod tests { let alice = Uuid::new_v4(); storage .transact( - vec![(alice, ":person/name".to_string(), Value::String("Alice".to_string()))], + vec![( + alice, + ":person/name".to_string(), + Value::String("Alice".to_string()), + )], None, ) .unwrap(); @@ -627,7 +635,11 @@ mod tests { let owned_results = owned_matcher.match_pattern(&pattern); let slice_results = slice_matcher.match_pattern(&pattern); - assert_eq!(owned_results.len(), slice_results.len(), "result count mismatch"); + assert_eq!( + owned_results.len(), + slice_results.len(), + "result count mismatch" + ); assert_eq!( owned_results[0].get("?name"), slice_results[0].get("?name"), @@ -657,18 +669,27 @@ mod tests { let alice = Uuid::new_v4(); storage .transact( - vec![(alice, ":name".to_string(), Value::String("Alice".to_string()))], + vec![( + alice, + ":name".to_string(), + Value::String("Alice".to_string()), + )], None, ) .unwrap(); storage - .retract(vec![(alice, ":name".to_string(), Value::String("Alice".to_string()))]) + .retract(vec![( + alice, + ":name".to_string(), + Value::String("Alice".to_string()), + )]) .unwrap(); // net_asserted_facts() returns the true net state: for each (entity, attribute, value) // triple, the most recent record wins; retractions exclude the triple entirely. - let asserted: Arc<[Fact]> = - Arc::from(crate::graph::storage::net_asserted_facts(storage.get_all_facts().unwrap())); + let asserted: Arc<[Fact]> = Arc::from(crate::graph::storage::net_asserted_facts( + storage.get_all_facts().unwrap(), + )); let matcher = PatternMatcher::from_slice(asserted); let pattern = Pattern::new( @@ -677,7 +698,10 @@ mod tests { EdnValue::Symbol("?v".to_string()), ); let results = matcher.match_pattern(&pattern); - assert!(results.is_empty(), "retracted fact should not appear in slice-based matcher"); + assert!( + results.is_empty(), + "retracted fact should not appear in slice-based matcher" + ); } #[test] @@ -689,12 +713,20 @@ mod tests { let alice = Uuid::new_v4(); storage .transact( - vec![(alice, ":name".to_string(), Value::String("Alice".to_string()))], + vec![( + alice, + ":name".to_string(), + Value::String("Alice".to_string()), + )], None, ) .unwrap(); storage - .retract(vec![(alice, ":name".to_string(), Value::String("Alice".to_string()))]) + .retract(vec![( + alice, + ":name".to_string(), + Value::String("Alice".to_string()), + )]) .unwrap(); // Deliberately build a raw, unfiltered slice (all facts, including the retraction) From d85e01cd47506b01a0f663822f946107acfc683b Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 13:57:15 +0530 Subject: [PATCH 14/15] docs: update BENCHMARKS.md with Phase 7.4 results MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit - Update query latency point_entity/10K: 15.6 ms โ†’ 8.6 ms (-61.5% vs pre-fix baseline of 22 ms) - Update aggregation count_scale/10K: 23.4 ms โ†’ 9.7 ms (-64.7%) - Update negation not_scale/10K: 13.4 s โ†’ 7.0 s (-12.1% vs pre-fix baseline) - Update disjunction or_scale/10K: 73.7 s โ†’ 68.9 s (within noise, p=0.36) - Add Phase 7.3 โ†’ Phase 7.4 summary section with before/after table - Update Known Limitations: index rebuild eliminated for non-rules path - Fix Criterion version: 0.5 โ†’ 0.8 - Update header note to reference v0.13.1 Co-Authored-By: Claude Sonnet 4.6 --- BENCHMARKS.md | 40 ++++++++++++++++++++++++++++++++-------- 1 file changed, 32 insertions(+), 8 deletions(-) diff --git a/BENCHMARKS.md b/BENCHMARKS.md index a097c27d3d..f2e4ca9b7f 100644 --- a/BENCHMARKS.md +++ b/BENCHMARKS.md @@ -2,7 +2,7 @@ **Live benchmark history**: [bencher.dev/console/projects/minigraf/perf](https://bencher.dev/console/projects/minigraf/perf) -Benchmark results for Minigraf. Core query benchmarks are from v0.8.0 (Phase 6.5 โ€” on-disk B+tree indexes, file format v6). Negation, disjunction, aggregation, and expression benchmarks were first run on v0.13.0. +Benchmark results for Minigraf. Core query benchmarks were updated in v0.13.1 (Phase 7.4 โ€” query path snapshot fix). Negation, disjunction, aggregation, and expression benchmarks were first run on v0.13.0 and selectively re-run on v0.13.1. ## Environment @@ -15,7 +15,7 @@ Benchmark results for Minigraf. Core query benchmarks are from v0.8.0 (Phase 6.5 | Profile | `release` (`opt-level = 3`, `lto = "thin"`, `panic = "abort"`) | | Swap | None | -Benchmarks were run with [Criterion 0.5](https://bheisler.github.io/criterion.rs/book/). Each benchmark group is described below. +Benchmarks were run with [Criterion 0.8](https://bheisler.github.io/criterion.rs/book/). Each benchmark group is described below. ### How to read these numbers @@ -67,11 +67,13 @@ Measures single-query latency against databases pre-loaded with 1K / 10K / 100K | Benchmark | 1K | 10K | 100K | 1M | |---|---|---|---|---| -| `point_entity` (query by entity + attribute) | 1.26 ms | 15.6 ms | 266 ms | 4.33 s | +| `point_entity` (query by entity + attribute) | 1.26 ms | **8.6 ms** | 266 ms | 4.33 s | | `point_attribute` (query by attribute only) | 1.16 ms | 14.7 ms | 258 ms | 4.29 s | | `join_3pattern` (3-clause join) | 4.38 ms | 53.6 ms | 857 ms | 12.93 s | -Query performance scales linearly with dataset size. The query executor resolves committed facts via the on-disk B+tree range scan and page cache, then filters in memory. Range-scan selectivity is not yet exploited to skip non-matching facts โ€” that optimisation is planned for Phase 7. +10K `point_entity` updated in v0.13.1 (Phase 7.4 โ€” snapshot fix, -61.5% vs pre-fix baseline of 22 ms, -45% vs Phase 6.5 v0.8.0). `point_attribute` and `join_3pattern` 10K numbers are from v0.8.0 and will be updated when re-benchmarked. 100K and 1M numbers are unchanged (from v0.8.0). + +Query performance scales linearly with dataset size. The query executor resolves committed facts via the on-disk B+tree range scan and page cache, then filters in memory. Starting from Phase 7.4, the non-rules query path no longer rebuilds in-memory EAVT/AEVT/AVET/VAET indexes on each call โ€” facts are passed as a pre-filtered `Arc<[Fact]>` slice. Range-scan selectivity is not yet exploited to skip non-matching facts โ€” that optimisation is deferred to a future phase. --- @@ -159,10 +161,12 @@ All 10K benchmarks were run with 100 samples. The O(Nยฒ) scaling is a known limi | Benchmark | 1K | 10K | |---|---|---| -| `not_scale` | 101.84 ms | 13.394 s | +| `not_scale` | 101.84 ms | **6.986 s** | | `not_join_scale` | 226.82 ms | 22.898 s | | `not_rule_body` | 172.96 ms | 16.883 s | +10K `not_scale` updated in v0.13.1 (Phase 7.4 โ€” snapshot fix, -12.1% vs pre-fix baseline of 7.95 s). `not_join_scale` and `not_rule_body` 10K numbers are from v0.13.0 and will be updated when re-benchmarked. + `not_selectivity` โ€” fixed 10K DB, exclusion fraction swept from 0% to 100% (100 samples each): | Selectivity | 0% excl. | 25% excl. | 50% excl. | 75% excl. | 100% excl. | @@ -181,10 +185,12 @@ The 10K numbers reflect a known O(Nยฒ) characteristic in the current `apply_or_c | Benchmark | 1K | 10K | |---|---|---| -| `or_scale` | 644.76 ms | 73.722 s | +| `or_scale` | 644.76 ms | 68.929 s | | `or_join_scale` | 683.99 ms | 72.751 s | | `or_rule_body` | 26.468 ms | 2.123 s | +10K `or_scale` updated in v0.13.1 (Phase 7.4 โ€” change not statistically significant at p=0.36; disjunction is O(Nยฒ) and dominated by branch enumeration, not the index rebuild). Other 10K numbers are from v0.13.0. + `or_selectivity` โ€” fixed 10K DB, fraction matching either branch swept from 0% to 100% (10 samples each): | Selectivity | 0% match | 25% match | 50% match | 75% match | 100% match | @@ -201,11 +207,13 @@ Measures aggregation post-processing overhead. `count_scale`/`sum_scale` use the | Benchmark | 1K | 10K | |---|---|---| -| `count_scale` (scalar `count`) | 1.770 ms | 23.437 ms | +| `count_scale` (scalar `count`) | 1.770 ms | **9.720 ms** | | `sum_scale` (scalar `sum`) | 1.881 ms | 22.745 ms | | `grouped_count_scale` (grouped by dept, 10 groups) | 4.038 ms | 51.550 ms | | `with_grouped_sum` (`:with` clause, grouped sum) | 670.85 ms | 67.266 s | +10K `count_scale` updated in v0.13.1 (Phase 7.4 โ€” snapshot fix, -64.7% vs pre-fix baseline of 27.5 ms). Other 10K numbers are from v0.13.0 and will be updated when re-benchmarked. + > `count` and `sum` are O(N). `grouped_count` is slightly higher due to the two-pattern join (`[?e :dept ?dept]` ร— `[?e :val ?v]`). `with_grouped_sum` at 10K shows O(Nยฒ) scaling from the same two-pattern cross-product join โ€” the planner currently lacks a hash-join step; this is tracked as a future optimisation. --- @@ -264,9 +272,25 @@ Peak heap consumption during `examples/memory_profile` (insert N facts + one que --- +## Phase 7.3 โ†’ Phase 7.4 Summary + +Phase 7.4 eliminated the per-query 4-index rebuild (`load_fact` loop โ€” BTreeMap insertions for EAVT/AEVT/AVET/VAET) in the non-rules query path. `filter_facts_for_query` now returns an `Arc<[Fact]>` slice instead of constructing a `FactStorage`; the rules path still builds a `FactStorage` for `StratifiedEvaluator`. + +| Metric | Pre-fix (v0.13.0) | Post-fix (v0.13.1) | Change | +|---|---|---|---| +| `query/point_entity` at 10K | 22.1 ms | 8.6 ms | **-61.5%** | +| `aggregation/count_scale` at 10K | 27.5 ms | 9.7 ms | **-64.7%** | +| `negation/not_scale` at 10K | 7.95 s | 6.99 s | -12.1% | +| `disjunction/or_scale` at 10K | 70.9 s | 68.9 s | ~same (p=0.36) | +| Rules path | unchanged | unchanged | index rebuild still paid | + +Negation and disjunction improvements are smaller because those paths are O(Nยฒ) and dominated by the inner binding-loop cost, not the index rebuild. The rules-path index rebuild is tracked in the post-1.0 backlog. + +--- + ## Known Limitations -- **Query scan is O(facts)**: Queries resolve all facts matching the range scan, then filter in memory. Phase 7 will enable index-based predicate pushdown for sub-linear lookups. +- **Query scan is O(facts)**: Queries resolve all facts matching the range scan, then filter in memory. The per-query index rebuild (EAVT/AEVT/AVET/VAET) was eliminated in Phase 7.4 for the non-rules path. Index-based predicate pushdown for sub-linear lookups is deferred to a future phase. - **Backend mutex held on cache-cold page reads**: Concurrent B+tree scans serialise only when a page must be loaded from disk (cache miss). Cache-warm reads are fully parallel. Further per-page I/O parallelism is deferred to Phase 8. - **1M recursion not benchmarked**: `chain/depth_100` takes 16 s; `chain/depth_1000` was not run. From 48fa4014b94ec6b3543478b5cf8131ab28f4fd9a Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 27 Mar 2026 14:04:28 +0530 Subject: [PATCH 15/15] docs: add B+Tree Selective Lookup to post-1.0 backlog; fix deferred phase references - Add named post-1.0 backlog entry for B+Tree Selective Lookup (range-scan predicate push-down): the get_all_facts() full scan is O(N) regardless of query predicates; fix is to use get_facts_by_entity/get_facts_by_attribute for bound patterns to achieve O(log N) selective fetch - Update BENCHMARKS.md query latency and known limitations sections to reference "post-1.0 backlog" instead of vague "future phase" Co-Authored-By: Claude Sonnet 4.6 --- BENCHMARKS.md | 4 ++-- ROADMAP.md | 8 ++++++++ 2 files changed, 10 insertions(+), 2 deletions(-) diff --git a/BENCHMARKS.md b/BENCHMARKS.md index f2e4ca9b7f..ff22658489 100644 --- a/BENCHMARKS.md +++ b/BENCHMARKS.md @@ -73,7 +73,7 @@ Measures single-query latency against databases pre-loaded with 1K / 10K / 100K 10K `point_entity` updated in v0.13.1 (Phase 7.4 โ€” snapshot fix, -61.5% vs pre-fix baseline of 22 ms, -45% vs Phase 6.5 v0.8.0). `point_attribute` and `join_3pattern` 10K numbers are from v0.8.0 and will be updated when re-benchmarked. 100K and 1M numbers are unchanged (from v0.8.0). -Query performance scales linearly with dataset size. The query executor resolves committed facts via the on-disk B+tree range scan and page cache, then filters in memory. Starting from Phase 7.4, the non-rules query path no longer rebuilds in-memory EAVT/AEVT/AVET/VAET indexes on each call โ€” facts are passed as a pre-filtered `Arc<[Fact]>` slice. Range-scan selectivity is not yet exploited to skip non-matching facts โ€” that optimisation is deferred to a future phase. +Query performance scales linearly with dataset size. The query executor resolves committed facts via the on-disk B+tree range scan and page cache, then filters in memory. Starting from Phase 7.4, the non-rules query path no longer rebuilds in-memory EAVT/AEVT/AVET/VAET indexes on each call โ€” facts are passed as a pre-filtered `Arc<[Fact]>` slice. Range-scan selectivity is not yet exploited to skip non-matching facts โ€” that optimisation is in the post-1.0 backlog (B+Tree Selective Lookup). --- @@ -290,7 +290,7 @@ Negation and disjunction improvements are smaller because those paths are O(Nยฒ) ## Known Limitations -- **Query scan is O(facts)**: Queries resolve all facts matching the range scan, then filter in memory. The per-query index rebuild (EAVT/AEVT/AVET/VAET) was eliminated in Phase 7.4 for the non-rules path. Index-based predicate pushdown for sub-linear lookups is deferred to a future phase. +- **Query scan is O(facts)**: Queries resolve all facts matching the range scan, then filter in memory. The per-query index rebuild (EAVT/AEVT/AVET/VAET) was eliminated in Phase 7.4 for the non-rules path. Index-based predicate pushdown for sub-linear lookups is in the post-1.0 backlog (B+Tree Selective Lookup). - **Backend mutex held on cache-cold page reads**: Concurrent B+tree scans serialise only when a page must be loaded from disk (cache miss). Cache-warm reads are fully parallel. Further per-page I/O parallelism is deferred to Phase 8. - **1M recursion not benchmarked**: `chain/depth_100` takes 16 s; `chain/depth_1000` was not run. diff --git a/ROADMAP.md b/ROADMAP.md index d29146fb38..0476be75dd 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -1357,6 +1357,14 @@ Improve semi-naive evaluation for rules that include `not`, `or`, and aggregate Push `Expr` predicate clauses (e.g. `[(> ?age 30)]`) down to filter bindings as early as possible rather than applying them as a final post-processing pass. Currently `apply_expr_clauses` runs after all pattern matching. A natural complement to the `filter_facts_for_query` snapshot fix, but kept separate to avoid expanding Phase 7.4's scope. +### B+Tree Selective Lookup (Range-Scan Predicate Push-Down) + +**Problem**: `filter_facts_for_query` step 1 calls `get_all_facts()`, which performs a full B+tree range scan regardless of query predicates. Every query pays O(N) I/O even when the query pattern binds a specific entity or attribute that could be resolved in O(log N) via an existing EAVT/AEVT index key lookup. + +**Fix**: Inspect query patterns before calling `get_all_facts()`. If a pattern binds a concrete entity (or entity + attribute), use `get_facts_by_entity` / `get_facts_by_attribute` to fetch only the relevant subset from the on-disk B+tree. This makes point-entity and point-attribute queries sub-linear in total fact count. + +**Scope**: Requires changes to `filter_facts_for_query` and the query planner to propagate bound values from patterns into the storage fetch call. More invasive than the Phase 7.4 snapshot fix; deferred to avoid destabilising the pre-1.0 query path. + --- ## Release Strategy