From b4fff46161a808c9c4ad3050670cf8166e7270dc Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 29 Oct 2026 08:12:05 +0530 Subject: [PATCH 1/3] perf(engine): avoid pending maps for selective ancestor joins (#723) --- CHANGELOG.md | 2 + CLAUDE.md | 3 +- README.md | 2 + ROADMAP.md | 2 + docs/BENCHMARKS.md | 42 +++++ docs/TEST_COVERAGE.md | 10 +- docs/benchmarks/723-recursive-joins.txt | 101 ++++++++++++ src/graph/storage.rs | 62 +++++++- src/query/engine/plan.rs | 80 +++++++++- src/query/engine/recursive.rs | 65 +++++++- src/query/engine/scan.rs | 4 + src/query/engine/tests.rs | 194 ++++++++++++++++++++++++ 12 files changed, 553 insertions(+), 14 deletions(-) create mode 100644 docs/benchmarks/723-recursive-joins.txt diff --git a/CHANGELOG.md b/CHANGELOG.md index 1bc980f61b..ba73944842 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -9,6 +9,8 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Performance +- **Avoid whole-attribute reads for selective in-memory ancestors** (#723). Eligible three-pattern recursive delta runs can start from a small derived relation and probe stored facts by entity, preserving the same semi-naive ranges and answers. The choice is reconsidered each round using bounded pending-index counts. Populated committed generations retain AVET value probes; general value joins retain their existing behavior. No persistent index, dependency, API or format change. + - **Skip sorting proven ordered input** (#641, first slice). Plain queries can omit `Sort` when a committed integer, float, or Boolean range already provides the complete ascending result order. Attribute scans use AVET; entity-and-attribute scans retain their selective EAVT range. `:offset` and `:limit` then stop reading early, so memory-limit (`QRY-012`) or I/O errors in unread later input may be avoided. The proof uses the query's pinned reader, including a large write transaction's working trees, and rejects pending or staged records in the source range, mixed kinds, unsupported comparators, tie suffixes, order-changing operators, user callbacks and `collect-set`. Unproven queries retain their original plan. - **Release completed count groups** (#641, second slice). A plain query with exactly one proved scalar grouping key, no `:with` or windows, and only built-in `count`/`count-distinct` holds one active group plus bounded batches. Completed groups are released, and a limit can stop before later groups; one large distinct group still grows with its members. Integer, Boolean and committed-float keys qualify, including mixed integer/float grouping in `Value::Ord` order. A unique single-kind group key can also remove the final ascending Sort; mixed numeric keys retain numeric Sort. Fallible aggregates, callbacks and `collect-set` retain full-input validation and later errors. Small selective grouped queries pay proof startup cost, and a single growing group is slower (see `docs/BENCHMARKS.md`). No new aggregate syntax or function is added. diff --git a/CLAUDE.md b/CLAUDE.md index 497b5d074c..73d2c34c16 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -216,7 +216,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1996 tests** (1979 passing, 17 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**2000 tests** (1983 passing, 17 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. @@ -226,6 +226,7 @@ See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **v2.0.5 released** (2026-10-11) — short-file open refused with STG-045 (#506), commit after a torn WAL entry no longer lost, WAL-007 (#513); backported rule-query `max_results` (#528), all-checkpointed WAL removal (#457) and `usize::MAX` close-time save (#476); weekly soak test (#392), real coverage gates (#396). **v2.0.4** (2026-10-08) — `BrowserDb` IndexedDB flush returns an error for an unreadable dirty page (#470); golden-file v7 corpus (#391) and SIGKILL committed-data crash test (#384). **v2.0.3** (2026-10-06) — data-integrity patch under the support policy: indexed queries with >65,535 uncheckpointed facts (#445), tx counter rewound on reopen next to an already-checkpointed WAL (#447). **v2.0.2** (2026-09-27) — last planned v2.x feature/fix release: query fixes (#297, #405, #407, #410), directory fsync (#389), point-query/attribute-scan/checkpoint perf mitigations (#323, #381, #315), CI policy checks (#395), support policy and tiers (#397, #399, #400). **v2.0.1** (2026-09-25) fixed index rebuild on open (#370). **v2.0.0** introduced kernel file locking (#317, #304), structured runtime error codes (#277), `OpenOptions` `#[non_exhaustive]`, and an MSRV of Rust 1.89. See `CHANGELOG.md` for the full rationale and release history. Current plan (see `ROADMAP.md` and the milestones): +- **In-memory ancestors (#723)**: eligible positive three-pattern delta runs retain an entity-first alternative with the same `Old`/`Delta`/`Full` ranges and separately planned head slots. Each round can select it when the committed dictionary is empty, the source relation has at most 128 rows and no stored records, and a capped AEVT count favors entity probes over building an uncached pending value map. Populated committed generations keep AVET probes. No additional write-time index. - **v2.x** (`main`, format v7) now gets only data-integrity and security fixes as patch releases (v2.0.3 is the first); v2.0.2 was the last planned v2.x release. - **v3.0.0** (format v8 and data integrity, plus `:limit` #306, optional `:distinct` output #493, `lag`/`lead` #182, sliding row frames #183, query profiler #185, set membership predicates #316 and prepared queries in every binding #181, UDF registration in every binding #180; tracker #383) is developed on the long-lived `v3` branch. All v3 PRs target `v3`; `main` stays untouched. CI runs on PRs to `v3` the same as on PRs to `main`. Do not merge `main` into `v3` routinely: `main` only gets backports of fixes already on `v3`. Shared CI and workflow changes land on both branches as separate PRs. Just before the v3.0.0 cut, merge `main` into `v3` once (merge commit; source conflicts resolved to `v3`, `main`'s v2.0.x CHANGELOG sections brought over) so the cut is a fast-forward. At the first v3 release, the current `main` is copied to `v2` and `v3` becomes the new `main`. - **Input order (#641)** targets v3.0.0 in three slices: committed scalar Sort omission, one-group count/count-distinct and partition-at-a-time windows are implemented in the dependent PRs for `v3`. The reviewed design, fallback scope and acceptance gates are in `docs/superpowers/specs/2026-10-28-641-input-order-design.md`. diff --git a/README.md b/README.md index a182ae2bee..67a637f2a4 100644 --- a/README.md +++ b/README.md @@ -34,6 +34,8 @@ The unreleased v3.0.0 branch adds bounded sliding windows such as `(avg ?salary On v3.0.0, an ascending value-only query such as `[:find ?v :where [?e :score ?v] :order-by [?v] :limit 10]` can read directly in index order and stop early when all committed `:score` history has one value kind (integer, float, or Boolean) and its source range has no pending writes. A query whose full order cannot be proved uses the existing sort (#641). Built-in `count` and `count-distinct` can also release completed groups when one committed integer/Boolean/float key is proved ordered (including mixed integer/float groups), with no `:with`, windows, callbacks or `collect-set`. Memory then follows the active group and batches; distinct members within one group still grow. Other aggregates keep full-input validation. When every built-in window uses the same proved nonconstant partition key, the engine can also finish and release one partition at a time. Its memory follows the largest partition plus bounded batches; one growing partition still grows. Unpartitioned windows, incompatible keys, aggregate queries, callbacks and `collect-set` keep full-input evaluation. A surrounding sort or distinct operation can still require more memory. +On the unreleased v3 branch, selective in-memory ancestor queries can use entity probes instead of reading the whole edge attribute (#723). This is a query-planning optimization; it adds no storage index or configuration. + **Status**: See [ROADMAP.md](ROADMAP.md) for planned work and current direction. ## Why Datalog? diff --git a/ROADMAP.md b/ROADMAP.md index d9924a9186..1dd9b02157 100644 --- a/ROADMAP.md +++ b/ROADMAP.md @@ -93,6 +93,8 @@ Scope — format and storage integrity: Scope — query API: +- Selective in-memory ancestor joins avoid building a whole-attribute value map (#723; implemented for eligible three-pattern recursive bodies). Populated committed generations keep AVET probes; general in-memory value joins remain unchanged. + - Optional `:distinct` result tuples, preserving bag output by default (#493; done on `v3`) - `lag` and `lead` window functions for the previous/next row within an ordered partition (#182; v3.0.0) - Bounded sliding row frames, `:rows N preceding`, for window aggregates (#183; v3.0.0, implemented on `v3`; builds on #182) diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index b65da4cae9..07640b4aeb 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -2,6 +2,48 @@ This document records reproducible local benchmark snapshots. Completed release-performance history belongs in the [CHANGELOG](../CHANGELOG.md); continuous CI history is available on [Bencher](https://bencher.dev/perf/minigraf/plots). +## Selective in-memory ancestors (#723, unreleased) + +**Date**: 2026-10-29 · **Baseline**: `v3` at `756ffea20`. Both revisions +used the same dependency lockfile and the existing `bench` profile. Prebuilt +Criterion executables ran sequentially on the idle bench machine, pinned +to the same NUMA node, with 10 samples, 3 seconds of warm-up and 5 seconds +of requested measurement time. Builds and tests finished before timing. +The estimates below are Criterion's fitted per-query times, not individual +query percentiles. + +| Workload | Baseline | Change | +|---|---:|---:| +| `recursion/ancestors/w10_d4` | 15.049 ms | 0.297 ms | +| same ancestors, second pair | 14.487 ms | 0.286 ms | +| `recursion/chain/depth_10` | 0.522 ms | 0.542 ms | +| `recursion/chain/depth_100` | 21.515 ms | 21.651 ms | +| `recursion/fanout/w10_d3` | 19.663 ms | 19.817 ms | + +The ancestor query is about 50 times faster in both pairs. Criterion found +no significant change for the depth-100 chain or fanout. The depth-10 chain +regressed by about 4% (Criterion's mean-change estimate); the added planning +and selection work is visible on this small query. General value joins +retain their existing behavior. Populated committed generations continue +to use AVET probes; this optimization targets eligible positive +three-pattern recursive bodies with small derived demand and preserves the +original value-head binding. + +The regression test returns three ancestors in a 1,999-edge tree with a +128 KiB query budget, including a staged edge replacement. The baseline +fails with `QRY-012` while building the pending value map. No persistent +value index or write-time cost is added. + +Release size with the same toolchain and lockfile: baseline 1,258,712 bytes, +change 1,261,432 bytes (+2,720). The existing 1,230 KiB gate (1,259,520 bytes) +is exceeded by 1,912 bytes; a budget decision is required before merge. + +Reproduce with `cargo bench --bench minigraf_bench -- '^recursion/'` on each +revision. For an isolated timed phase, build with `--no-run` first and invoke +the resulting benchmark executable with `'^recursion/' --bench` under the +same CPU/memory affinity. The [raw Criterion output](benchmarks/723-recursive-joins.txt) +contains both ancestor pairs and the control shapes. + ## Bounded recursive entity probes (#672, unreleased) **Date**: 2026-10-28 · **Baseline**: `v3` at `d0ad89c1d` · **Machine**: diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 711a569d95..fd9d5525bd 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,11 +4,13 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Passing** | 1,979 | 2,012 | +| **Passing** | 1,983 | 2,016 | | **Ignored** | 17 | 18 | -| **Total** | 1,996 | 2,030 | +| **Total** | 2,000 | 2,034 | -**Verified**: 2026-10-28 on the designated bench machine: full default/test-hooks tests and the full branch-coverage suite pass, including golden files and migration/fault injection after sharing stable-sort code. Disabling internal reference-result cache eviction makes the targeted window regression fail. All unchanged coverage floors pass; measured overall coverage is 95.44% lines and 86.50% branches. Strict native/browser/WASI lint, WASI tests (1,182 passing, seven ignored), the WASI release build and Firefox tests (61 passing) also pass; the new committed-reader window fixture executes on both portable runners. The #672 default and `test-hooks` suites passed separately on 2026-10-28 before rebasing onto #641. +**#723 verification (2026-10-29)**: full default and `test-hooks` suites passed on the bench machine before the final head-binding guard; the added representation regression, full non-fault unit suite and plan-independence matrix passed after it. The shared pending-count refactor passed the non-fault unit suite. The unchanged fault matrix passed in both full runs. Strict all-features clippy and formatting pass; the docs site builds 13 versions. No frozen answers were changed. + +**Earlier verification**: 2026-10-28 on the designated bench machine: full default/test-hooks tests and the full branch-coverage suite pass, including golden files and migration/fault injection after sharing stable-sort code. Disabling internal reference-result cache eviction makes the targeted window regression fail. All unchanged coverage floors pass; measured overall coverage is 95.44% lines and 86.50% branches. Strict native/browser/WASI lint, WASI tests (1,182 passing, seven ignored), the WASI release build and Firefox tests (61 passing) also pass; the new committed-reader window fixture executes on both portable runners. The #672 default and `test-hooks` suites passed separately on 2026-10-28 before rebasing onto #641. #641 slice 1 adds 30 tests with default features and one more with `test-hooks`. Slice 2 adds 22 default-feature tests (21 active and one ignored committed-fixture memory diagnostic). Slice 3 adds 26 default-feature tests (25 active and one ignored committed-fixture memory diagnostic). @@ -26,6 +28,8 @@ Not counted above: the browser tests and the WASI run (see [Browser and WASI](#b ## Covered Areas +- **In-memory ancestor join ordering** (#723; four tests): a 1,999-edge tree returns three ancestors within a 128 KiB query budget, also after staged edge replacement; cursor close releases its metered state. Reordered and text-order plans return identical bags across keyword/ref edges, cycles, multi-valued edges, retractions, transaction/valid-time filters, empty and unbound queries, in memory and with checkpointed facts. A direct comparison against the original delta plan protects keyword/ref output representation in rule heads. The bounded cost count excludes writes after a captured snapshot, includes staged records, respects the cap, and excludes prefix-neighbor attributes. + - **Proven input order** (#641, first slice; `src/query/engine/order_tests.rs`, `order/tests.rs`, `tests/input_order_test.rs`): full result keys and projection slots, constants and repeated slots, integer/Boolean/float edge cases including NaNs and signed zeros, replacements, join fallback orientation and distinct canonicalization. Snapshot tests cover unrelated versus in-range pending/staged records, captured prefixes, temporal filters, prepared queries, checkpoints and large-transaction working readers including rejected statements and rollback. Counters establish early stopping, bounded raw proof reads and no reads without demand; optional proof-read errors leave the original plan. Late callback and `collect-set` errors retain their evaluation. A forced-fallback differential matrix checks identical ordered lists across plan switches. A committed `MemoryBackend` fixture runs on native, WASI and the browser. Storage tests cover every key kind/tag and raw seeks over retracted history. - **One-group count aggregation** (#641, second slice; `src/query/engine/aggregate_order_tests.rs`, `order/tests.rs`, `engine/tests.rs`): count/count-distinct over one certified scalar group, cross-batch boundaries, unique-key Sort omission and retained descending/aggregate-first/mixed-numeric Sort, Boolean/float representatives and mixed numeric group order. Arbitrary argument kinds, nil, `:distinct`, offset/limit and probe joins match forced fallback. Tests cover no `:with`/window/multiple-key eligibility, later fallible-aggregate/callback/collect-set errors and dropped-group precedence, pending/staged/prepared/working-reader changes and rejected statements, atomic fallback on every optional proof-read failure, bounded group state with one active group, internal DICT-cache eviction within one group spanning many probe batches, a growing distinct-group control, low budgets, allocator refusal, close/drop/rewind, and defensive `INT-032` for injected decreasing input before and after an answer batch. A committed `MemoryBackend` fixture also runs under WASI and in the browser. diff --git a/docs/benchmarks/723-recursive-joins.txt b/docs/benchmarks/723-recursive-joins.txt new file mode 100644 index 0000000000..de052ba9f9 --- /dev/null +++ b/docs/benchmarks/723-recursive-joins.txt @@ -0,0 +1,101 @@ +=== Baseline, all recursion === +Gnuplot not found, using plotters backend +Benchmarking recursion/chain/depth_10 +Benchmarking recursion/chain/depth_10: Warming up for 3.0000 s +Benchmarking recursion/chain/depth_10: Collecting 10 samples in estimated 5.0008 s (9405 iterations) +Benchmarking recursion/chain/depth_10: Analyzing +recursion/chain/depth_10 + time: [520.16 µs 522.50 µs 525.30 µs] +Benchmarking recursion/chain/depth_100 +Benchmarking recursion/chain/depth_100: Warming up for 3.0000 s +Benchmarking recursion/chain/depth_100: Collecting 10 samples in estimated 5.9262 s (275 iterations) +Benchmarking recursion/chain/depth_100: Analyzing +recursion/chain/depth_100 + time: [21.431 ms 21.515 ms 21.623 ms] +Found 2 outliers among 10 measurements (20.00%) + 1 (10.00%) high mild + 1 (10.00%) high severe + +Benchmarking recursion/fanout/w10_d3 +Benchmarking recursion/fanout/w10_d3: Warming up for 3.0000 s +Benchmarking recursion/fanout/w10_d3: Collecting 10 samples in estimated 5.3519 s (275 iterations) +Benchmarking recursion/fanout/w10_d3: Analyzing +recursion/fanout/w10_d3 time: [19.371 ms 19.663 ms 20.026 ms] +Found 1 outliers among 10 measurements (10.00%) + 1 (10.00%) high severe + +Benchmarking recursion/ancestors/w10_d4 +Benchmarking recursion/ancestors/w10_d4: Warming up for 3.0000 s +Benchmarking recursion/ancestors/w10_d4: Collecting 10 samples in estimated 5.0845 s (330 iterations) +Benchmarking recursion/ancestors/w10_d4: Analyzing +recursion/ancestors/w10_d4 + time: [14.932 ms 15.049 ms 15.271 ms] + + +=== Change, all recursion === +Gnuplot not found, using plotters backend +Benchmarking recursion/chain/depth_10 +Benchmarking recursion/chain/depth_10: Warming up for 3.0000 s +Benchmarking recursion/chain/depth_10: Collecting 10 samples in estimated 5.0229 s (9240 iterations) +Benchmarking recursion/chain/depth_10: Analyzing +recursion/chain/depth_10 + time: [539.67 µs 541.70 µs 543.32 µs] + change: [+2.3867% +4.0966% +6.5937%] (p = 0.00 < 0.05) + Performance has regressed. +Found 1 outliers among 10 measurements (10.00%) + 1 (10.00%) high severe +Benchmarking recursion/chain/depth_100 +Benchmarking recursion/chain/depth_100: Warming up for 3.0000 s +Benchmarking recursion/chain/depth_100: Collecting 10 samples in estimated 5.9721 s (275 iterations) +Benchmarking recursion/chain/depth_100: Analyzing +recursion/chain/depth_100 + time: [21.533 ms 21.651 ms 21.809 ms] + change: [−0.0508% +0.6154% +1.2708%] (p = 0.12 > 0.05) + No change in performance detected. +Found 2 outliers among 10 measurements (20.00%) + 2 (20.00%) high severe + +Benchmarking recursion/fanout/w10_d3 +Benchmarking recursion/fanout/w10_d3: Warming up for 3.0000 s +Benchmarking recursion/fanout/w10_d3: Collecting 10 samples in estimated 5.4592 s (275 iterations) +Benchmarking recursion/fanout/w10_d3: Analyzing +recursion/fanout/w10_d3 time: [19.750 ms 19.817 ms 19.894 ms] + change: [−0.2400% +1.3412% +2.4849%] (p = 0.09 > 0.05) + No change in performance detected. +Found 1 outliers among 10 measurements (10.00%) + 1 (10.00%) high mild + +Benchmarking recursion/ancestors/w10_d4 +Benchmarking recursion/ancestors/w10_d4: Warming up for 3.0000 s +Benchmarking recursion/ancestors/w10_d4: Collecting 10 samples in estimated 5.0057 s (17k iterations) +Benchmarking recursion/ancestors/w10_d4: Analyzing +recursion/ancestors/w10_d4 + time: [295.85 µs 297.06 µs 298.17 µs] + change: [−98.077% −98.046% −98.017%] (p = 0.00 < 0.05) + Performance has improved. + + +=== Baseline, repeated ancestors === +Gnuplot not found, using plotters backend +Benchmarking recursion/ancestors/w10_d4 +Benchmarking recursion/ancestors/w10_d4: Warming up for 3.0000 s +Benchmarking recursion/ancestors/w10_d4: Collecting 10 samples in estimated 5.8294 s (385 iterations) +Benchmarking recursion/ancestors/w10_d4: Analyzing +recursion/ancestors/w10_d4 + time: [14.431 ms 14.487 ms 14.519 ms] + + +=== Change, repeated ancestors === +Gnuplot not found, using plotters backend +Benchmarking recursion/ancestors/w10_d4 +Benchmarking recursion/ancestors/w10_d4: Warming up for 3.0000 s +Benchmarking recursion/ancestors/w10_d4: Collecting 10 samples in estimated 5.0107 s (18k iterations) +Benchmarking recursion/ancestors/w10_d4: Analyzing +recursion/ancestors/w10_d4 + time: [283.91 µs 285.74 µs 289.04 µs] + change: [−98.039% −98.022% −98.000%] (p = 0.00 < 0.05) + Performance has improved. +Found 1 outliers among 10 measurements (10.00%) + 1 (10.00%) high severe + + diff --git a/src/graph/storage.rs b/src/graph/storage.rs index 2ca3407cc1..78373a0f46 100644 --- a/src/graph/storage.rs +++ b/src/graph/storage.rs @@ -305,18 +305,28 @@ impl Snapshot { /// Any pending/staged record of this attribute (and optional entity) in /// the captured snapshot, even a retraction or excluded version (#641). pub(crate) fn has_pending(&self, attribute: &str, entity: Option<&EntityId>) -> Result { + Ok(self.pending_attribute_count(attribute, entity, 1)? != 0) + } + + /// A capped record count for join costing (#723). Walk index keys only, + /// stopping at `cap`; include staged facts and exclude later writes. + /// History counts too: building a value map must read it before filtering. + pub(crate) fn pending_attribute_count( + &self, + attribute: &str, + entity: Option<&EntityId>, + cap: usize, + ) -> Result { use crate::storage::index::AevtKey; - if self.pending_len() == 0 { - return Ok(false); + if self.pending_len() == 0 || cap == 0 { + return Ok(0); } let pending = self.read_pending()?; let mut start = AevtKey::attribute_start(attribute); if let Some(e) = entity { start.entity = *e; } - // Existence needs no merge: stop each index at the source boundary - // before filtering records appended after the captured prefix. - let has = |store: &PendingStore, len: usize| { + let count = |store: &PendingStore, len: usize, cap: usize| { store .indexes .aevt @@ -324,10 +334,15 @@ impl Snapshot { .take_while(|(k, _)| { k.attribute == attribute && entity.is_none_or(|e| k.entity == *e) }) - .any(|(_, &pos)| pos < len) + .filter(|(_, pos)| **pos < len) + .take(cap) + .count() }; - Ok(has(&pending, self.pending_len) - || self.staged.as_ref().is_some_and(|s| has(s, s.facts.len()))) + let n = count(&pending, self.pending_len, cap); + Ok(n + self + .staged + .as_ref() + .map_or(0, |s| count(s, s.facts.len(), cap - n))) } /// This snapshot with `facts` staged after its pending ones (#550 spec @@ -2341,6 +2356,37 @@ mod tests { assert_eq!(attrs, [":t/y", ":t/x", ":t/x", ":t/y"]); } + #[test] + fn pending_attribute_cost_uses_the_captured_and_staged_prefixes() { + let storage = FactStorage::new(); + let e = uuid::Uuid::new_v4(); + storage + .load_facts(vec![ + Fact::new(e, ":a".into(), Value::Integer(1), 1), + Fact::new(e, ":ab".into(), Value::Integer(2), 1), + ]) + .unwrap(); + let snap = storage.snapshot().unwrap(); + storage + .load_facts(vec![Fact::new(e, ":a".into(), Value::Integer(3), 2)]) + .unwrap(); + assert_eq!(snap.pending_attribute_count(":a", None, 10).unwrap(), 1); + assert_eq!( + snap.pending_attribute_count(":absent", None, 10).unwrap(), + 0 + ); + let snap = snap.with_staged(vec![ + Fact::new(e, ":a".into(), Value::Integer(4), 3), + Fact::new(e, ":ab".into(), Value::Integer(5), 3), + ]); + for (cap, expected) in [(0, 0), (1, 1), (2, 2), (10, 2)] { + assert_eq!( + snap.pending_attribute_count(":a", None, cap).unwrap(), + expected + ); + } + } + #[test] fn snapshot_reads_leave_out_later_appends() { use crate::storage::Scan; diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index c8f4784758..59b95f59a9 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -701,6 +701,9 @@ pub(crate) struct RuleRun { pub(crate) entity: HeadArg, /// `None` for a one-argument head, whose value is `true`. pub(crate) value: Option, + /// Same delta ranges, starting from a relation and probing by entity + /// instead of building a pending value map (#723). + pub(crate) entity_first: Option>, } /// A head argument. @@ -876,6 +879,7 @@ fn rule_plan( entity: arg(entity), value: head.get(2).map(arg), plan: b.finish()?, + entity_first: None, }) }; let full = run(Vec::new(), None)?; @@ -898,7 +902,24 @@ fn rule_plan( // even when an equal invocation comes before it (#694). let d = ranges.remove(i); ranges.insert(0, d); - deltas.push(run(ranges, Some(delta))?); + let mut primary = run(ranges.clone(), Some(delta))?; + // Only a positive three-pattern chain: no callbacks, filters, + // metadata or branching whose evaluation order could change. + if optimizer::reorder() + && matches!(primary.plan.steps.first(), Some(Step::Join(j)) + if matches!(j.kind, JoinKind::ProbeValue { .. })) + && clauses.len() == 3 + && clauses.iter().all(|c| { + matches!(c, WhereClause::Pattern(p) + if p.meta.is_empty() && matches!(p.attribute, AttributeSpec::Real(_))) + }) + { + let alternative = run(ranges, None)?; + if entity_first_alternative(&primary, &alternative) { + primary.entity_first = Some(Box::new(alternative)); + } + } + deltas.push(primary); } } Ok(RulePlan { @@ -910,6 +931,63 @@ fn rule_plan( }) } +/// The alternative reads a relation, probes the primary's stored attribute +/// by entity, then probes the delta by entity. Both runs retain their own +/// head slots; changing the order never reuses the primary's slot numbers. +fn entity_first_alternative(primary: &RuleRun, alternative: &RuleRun) -> bool { + let (Source::Scan(delta), Source::Scan(source)) = + (&primary.plan.source, &alternative.plan.source) + else { + return false; + }; + let [Step::Join(value), Step::Join(_)] = primary.plan.steps.as_slice() else { + return false; + }; + let [Step::Join(entity), Step::Join(tail)] = alternative.plan.steps.as_slice() else { + return false; + }; + // Join equality equates a keyword with its entity, but a rule's value + // head preserves its input representation. Only move a run whose value + // head is supplied by the delta's value in both orders, never by a key + // that the other order could bind from a different pattern. + let (Some(HeadArg::Slot(head)), Term::Bind(value_slot)) = (&primary.value, &delta.v) else { + return false; + }; + let (Some(HeadArg::Slot(other_head)), Term::Bind(other_value)) = + (&alternative.value, &tail.inner.v) + else { + return false; + }; + if head != value_slot + || !tail + .new + .iter() + .enumerate() + .any(|(i, slot)| slot == other_value && *other_head == tail.outer_width + i) + { + return false; + } + delta + .derived + .as_ref() + .is_some_and(|d| d.range == Range::Delta) + && source + .derived + .as_ref() + .is_some_and(|d| d.range != Range::Delta) + && matches!(value.kind, JoinKind::ProbeValue { .. }) + && value.inner.derived.is_none() + && matches!(entity.kind, JoinKind::Probe(_)) + && entity.inner.derived.is_none() + && matches!((&value.inner.a, &entity.inner.a), (Term::Const(a), Term::Const(b)) if a == b) + && matches!(tail.kind, JoinKind::Probe(_)) + && tail + .inner + .derived + .as_ref() + .is_some_and(|d| d.range == Range::Delta) +} + /// Whether a rule body reads a relation of its stratum (the attributes /// `stratum`) other than through a top-level invocation, outside `not` and /// `not-join` (spec §5.3): it is then evaluated in full every round. diff --git a/src/query/engine/recursive.rs b/src/query/engine/recursive.rs index 43ad81a572..50d5a8510b 100644 --- a/src/query/engine/recursive.rs +++ b/src/query/engine/recursive.rs @@ -12,7 +12,7 @@ use super::cell::{Cell, JoinKey, Scalar}; use super::ids::IdSpace; use super::meter::{HASH_ENTRY_OVERHEAD, Held, Meter, cell_bytes, growth, key_bytes}; -use super::plan::{HeadArg, RuleRun, RulesPlan, ScanSpec, Term}; +use super::plan::{HeadArg, RuleRun, RulesPlan, ScanSpec, Source, Step, Term}; use super::relation::Relations; use super::scan::Scan; use super::{Ctx, Operator, build}; @@ -158,6 +158,7 @@ fn heads( ids: &mut IdSpace, meter: &Arc, ) -> Result<(Vec<[Cell; 2]>, Held)> { + let run = choose_run(run, rels, reads, ids)?; let mut out: Vec<[Cell; 2]> = Vec::new(); let mut seen: HashSet<[JoinKey; 2]> = HashSet::new(); let mut held = Held::new(meter, "Recursive"); @@ -198,6 +199,68 @@ fn heads( Ok((out, held)) } +/// Reconsider each round, before opening operators. A small relation can +/// avoid the initial whole-attribute read of an in-memory value probe. +/// Committed databases keep AVET probes; a value map already built is free +/// to reuse. The cap bounds both costing work and the alternative's seed. +fn choose_run<'a>( + run: &'a RuleRun, + rels: &Relations, + reads: &Reads<'_>, + ids: &IdSpace, +) -> Result<&'a RuleRun> { + let Some(alternative) = run.entity_first.as_deref() else { + return Ok(run); + }; + // In-memory databases also have an empty committed reader. With no + // allocated entity ids it cannot contain a fact; populated generations + // keep their AVET path. This is metadata-only, with no index read. + if reads.keys.is_some_and(|k| k.next_ids().0 > 1) { + return Ok(run); + } + let (Source::Scan(delta), Source::Scan(source)) = (&run.plan.source, &alternative.plan.source) + else { + return Ok(run); + }; + let count = |s: &ScanSpec| { + s.derived.as_ref().map_or(0, |d| { + d.rels.iter().fold(0usize, |n, &r| { + n.saturating_add(rels.span(r, d.range).len()) + }) + }) + }; + let n = count(source); + if count(delta) == 0 || n > 128 { + return Ok(run); + } + let (Term::Const(source_attr), Some(Step::Join(join))) = + (&source.a, alternative.plan.steps.first()) + else { + return Ok(run); + }; + let Term::Const(attribute) = &join.inner.a else { + return Ok(run); + }; + if ids.probes().is_some_and(|p| p.has_values(attribute)) + || reads.snapshot.has_pending(source_attr, None)? + { + return Ok(run); + } + // Allow eight records per source row for the entity lookup and the + // final delta probe. Count at most 1,024 snapshot-visible records; + // later appends are skipped and no facts are cloned. + let cost = n * 8; + if reads + .snapshot + .pending_attribute_count(attribute, None, cost)? + >= cost + { + Ok(alternative) + } else { + Ok(run) + } +} + /// A candidate head and its key in `heads`' set. fn head_bytes(row: &[Cell; 2]) -> usize { let key = key_bytes(&JoinKey::ident(&row[0])) + key_bytes(&JoinKey::ident(&row[1])); diff --git a/src/query/engine/scan.rs b/src/query/engine/scan.rs index f8093f261f..00b2df787f 100644 --- a/src/query/engine/scan.rs +++ b/src/query/engine/scan.rs @@ -63,6 +63,10 @@ pub(crate) struct Probes { } impl Probes { + pub(crate) fn has_values(&self, attribute: &str) -> bool { + self.values.contains_key(attribute) + } + pub(crate) fn new(meter: &Arc) -> Self { Probes { values: HashMap::new(), diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 6c429eeb0b..2b18f53355 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -2570,6 +2570,200 @@ fn rule_delta_runs_join_on_a_bound_variable() { assert_eq!(rows(&db, "(query [:find ?to :where (reach :n1 ?to)])"), 10); } +/// #723: finding three ancestors must not retain every unrelated edge in +/// a query-local value map. The store itself is outside the query budget. +#[test] +fn ancestors_do_not_materialize_the_pending_attribute() { + let db = crate::OpenOptions::new() + .query_memory_limit(128 * 1024) + .open_memory() + .unwrap(); + let facts: String = (1..2000) + .map(|i| format!("[:p{i} :manager :p{}]", i / 10)) + .collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + db.execute("(rule [(boss ?x ?y) [?x :manager ?y]])") + .unwrap(); + db.execute("(rule [(boss ?x ?z) [?x :manager ?y] (boss ?y ?z)])") + .unwrap(); + let mut cursor = db + .query("(query [:find ?b :where (boss :p199 ?b)])") + .expect("a selective ancestor query fits the budget"); + let meter = cursor.stream_mut().unwrap().meter().clone(); + let mut got = Vec::new(); + while let Some(batch) = cursor.next_batch(10).unwrap() { + got.extend_from_slice(batch.rows()); + } + let expected: Vec> = [":p19", ":p1", ":p0"] + .into_iter() + .map(|k| vec![crate::Value::Keyword(k.into())]) + .collect(); + assert_eq!(got.len(), expected.len()); + assert!(expected.iter().all(|r| got.contains(r)), "all ancestors"); + cursor.close(); + assert_eq!(meter.used(), 0, "rule state released on close"); + + // The same choice must see staged retractions and assertions, without + // changing either the committed query or the transaction on rollback. + let mut tx = db.begin_write().unwrap(); + tx.execute("(retract [[:p199 :manager :p19]])").unwrap(); + tx.execute("(transact [[:p199 :manager :p2]])").unwrap(); + let QueryResult::QueryResults { results, .. } = tx + .execute("(query [:find ?b :where (boss :p199 ?b)])") + .unwrap() + else { + panic!("expected rows"); + }; + assert_eq!(results.len(), 2); + for k in [":p2", ":p0"] { + assert!(results.contains(&vec![crate::Value::Keyword(k.into())])); + } + drop(tx); +} + +/// The alternative keeps the delta ranges, head slots and temporal reads. +/// Exercise small and broad demand, refs as well as keywords, a cycle, +/// multi-valued edges, and retractions on both storage paths. +#[test] +fn ancestor_join_orders_preserve_temporal_answers() { + fn answer(db: &Minigraf, q: &str, reorder: bool) -> Vec> { + let _guard = crate::query::datalog::optimizer::set_reorder(reorder); + let QueryResult::QueryResults { mut results, .. } = db.execute(q).unwrap() else { + panic!("expected rows"); + }; + results.sort_by(|a, b| a.partial_cmp(b).unwrap()); + results + } + let dir = tempfile::tempdir().unwrap(); + for file in [false, true] { + let db = if file { + Minigraf::open(dir.path().join("ancestor-orders.graph")).unwrap() + } else { + Minigraf::in_memory().unwrap() + }; + let facts: String = (1..300) + .map(|i| format!("[:p{i} :manager :p{}]", i / 10)) + .collect(); + db.execute(&format!( + "(transact {{:valid-from \"2020-01-01\"}} [{facts}])" + )) + .unwrap(); + if file { + db.checkpoint().unwrap(); + } + db.execute(&format!( + "(transact {{:valid-from \"2021-01-01\"}} [[:p199 :manager #uuid \"{}\"] [:p1 :manager :p199]])", + uuid_of(":p2") + )).unwrap(); + db.execute("(retract [[:p19 :manager :p1]])").unwrap(); + db.execute("(rule [(boss ?x ?y) [?x :manager ?y]])") + .unwrap(); + db.execute("(rule [(boss ?x ?z) [?x :manager ?y] (boss ?y ?z)])") + .unwrap(); + for time in [ + "", + ":as-of 1", + ":as-of 2", + ":valid-at \"2020-06-01\"", + ":any-valid-time", + ] { + for call in [ + "(boss :p199 ?b)", + "(boss ?a ?b)", + "(boss :p299 ?b)", + "(boss :missing ?b)", + ] { + let q = format!("(query [:find ?b {time} :where {call}])"); + let baseline = answer(&db, &q, false); + let selected = answer(&db, &q, true); + assert!(selected == baseline, "join orders return the same bag"); + } + } + } +} + +/// A join-equal keyword/ref pair is not interchangeable in a rule's value +/// head. Reordering must preserve which pattern supplies that cell. +#[test] +fn ancestor_alternative_preserves_head_value_representation() { + use crate::graph::storage::FactStorage; + use crate::query::datalog::{ + functions::FunctionRegistry, parser::parse_datalog_command, rules::RuleRegistry, + types::DatalogCommand, + }; + let storage = FactStorage::new(); + storage + .transact( + (1..300) + .map(|i| { + ( + uuid_of(&format!(":p{i}")), + ":manager".into(), + crate::Value::Keyword(format!(":p{}", i / 10)), + ) + }) + .collect(), + None, + ) + .unwrap(); + for head in ["?x ?z", "?x ?y"] { + let mut registry = RuleRegistry::new(); + for text in [ + "(rule [(boss ?x ?y) [?x :manager ?y]])".to_string(), + format!("(rule [(boss {head}) [?x :manager ?y] (boss ?y ?z)])"), + ] { + let DatalogCommand::Rule(rule) = parse_datalog_command(&text).unwrap() else { + panic!("rule"); + }; + registry.register_rule("boss".into(), rule).unwrap(); + } + let DatalogCommand::Query(query) = + parse_datalog_command("(query [:find ?b :where (boss :p199 ?b)])").unwrap() + else { + panic!("query"); + }; + let (rewritten, seeds) = + crate::query::datalog::magic_sets::rewrite(&query, ®istry).unwrap(); + let attrs: Vec<&str> = seeds.iter().map(|(_, a, _)| a.as_str()).collect(); + let plan = super::plan_rules(&query, &rewritten, &attrs).unwrap(); + let answer = |allow_alternative: bool| { + let mut plan = plan.clone(); + if !allow_alternative { + for (_, rules) in &mut plan.strata { + for rule in rules { + for run in &mut rule.deltas { + run.entity_first = None; + } + } + } + } + let mut stream = super::open_rules( + storage.snapshot().unwrap(), + plan, + &seeds, + &[":p199".into()], + std::sync::Arc::new(FunctionRegistry::with_builtins()), + super::recursive::Limits { + max_iterations: 100, + max_derived_facts: 10000, + query_memory: usize::MAX, + }, + ) + .unwrap(); + let mut rows = Vec::new(); + while let Some(batch) = stream.next_rows().unwrap() { + rows.extend(batch); + } + rows.sort_by(|a, b| a.partial_cmp(b).unwrap()); + rows + }; + assert!( + answer(true) == answer(false), + "head value retains its original representation" + ); + } +} + /// #721: after the magic-set rewrite of `(boss :leaf ?b)` over a tree, the /// run from the `boss` delta joins `[?x :manager ?y]` on its value. It /// probes the AVET range of each `?y` instead of hashing every `:manager` From 4fe946b8377357da47181ed864fbcaa442c6ce91 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 29 Oct 2026 08:16:20 +0530 Subject: [PATCH 2/3] chore: apply approved 1234 KiB v3 size budget (#723) --- .github/workflows/binary-size.yml | 2 +- CHANGELOG.md | 2 +- CLAUDE.md | 2 +- PHILOSOPHY.md | 5 ++++- docs/BENCHMARKS.md | 5 +++-- docs/TEST_COVERAGE.md | 2 +- 6 files changed, 11 insertions(+), 7 deletions(-) diff --git a/.github/workflows/binary-size.yml b/.github/workflows/binary-size.yml index 6ab5bb25cb..66ddf18cfb 100644 --- a/.github/workflows/binary-size.yml +++ b/.github/workflows/binary-size.yml @@ -14,7 +14,7 @@ jobs: name: Check release binary size runs-on: ubuntu-latest env: - SIZE_LIMIT_BYTES: 1259520 # 1230 KiB — raised from 1 MiB for #277's structured error codes, from 1200 KiB for #306's :order-by/top-k; see PHILOSOPHY.md §4 + SIZE_LIMIT_BYTES: 1263616 # 1234 KiB — #277 error codes, #306 top-k, #723 ancestor join planning; see PHILOSOPHY.md §4 steps: - name: Checkout code uses: actions/checkout@v4 diff --git a/CHANGELOG.md b/CHANGELOG.md index ba73944842..6132100488 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -9,7 +9,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Performance -- **Avoid whole-attribute reads for selective in-memory ancestors** (#723). Eligible three-pattern recursive delta runs can start from a small derived relation and probe stored facts by entity, preserving the same semi-naive ranges and answers. The choice is reconsidered each round using bounded pending-index counts. Populated committed generations retain AVET value probes; general value joins retain their existing behavior. No persistent index, dependency, API or format change. +- **Avoid whole-attribute reads for selective in-memory ancestors** (#723). Eligible three-pattern recursive delta runs can start from a small derived relation and probe stored facts by entity, preserving the same semi-naive ranges and answers. The choice is reconsidered each round using bounded pending-index counts. Populated committed generations retain AVET value probes; general value joins retain their existing behavior. No persistent index, dependency, API or format change. The approved v3 binary-size budget increases from 1,230 to 1,234 KiB for this change. - **Skip sorting proven ordered input** (#641, first slice). Plain queries can omit `Sort` when a committed integer, float, or Boolean range already provides the complete ascending result order. Attribute scans use AVET; entity-and-attribute scans retain their selective EAVT range. `:offset` and `:limit` then stop reading early, so memory-limit (`QRY-012`) or I/O errors in unread later input may be avoided. The proof uses the query's pinned reader, including a large write transaction's working trees, and rejects pending or staged records in the source range, mixed kinds, unsupported comparators, tie suffixes, order-changing operators, user callbacks and `collect-set`. Unproven queries retain their original plan. diff --git a/CLAUDE.md b/CLAUDE.md index 73d2c34c16..bf01abd6b1 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -16,7 +16,7 @@ Minigraf follows the "SQLite for bi-temporal graph databases" philosophy: - **Zero-configuration** - No setup, no config files, just works - **Embedded-first** - Library not server, in-process execution - **Single-file database** - One portable `.graph` file -- **Self-contained** - Minimal dependencies, small binary (~1.2MB budget as of #277, 1,230 KiB enforced on v3 since #306; see PHILOSOPHY.md §4) +- **Self-contained** - Minimal dependencies, small binary (~1.2MB budget as of #277, 1,234 KiB enforced on v3 since #723; see PHILOSOPHY.md §4) - **Cross-platform** - Native, WASM, mobile, embedded - **Reliability over features** - Do less, do it perfectly - **Bi-temporal first-class** - Time travel is a core feature, not addon diff --git a/PHILOSOPHY.md b/PHILOSOPHY.md index 6cfd02e2c3..d384c5afd5 100644 --- a/PHILOSOPHY.md +++ b/PHILOSOPHY.md @@ -115,7 +115,10 @@ SQLite's success comes from a clear philosophy: be a library, not a server. Be s strip=symbols all already applied; see CI's `binary-size.yml` for the enforced limit). v3.0.0 raises the enforced limit to 1,230 KiB for `:order-by`/`:offset` and the top-k `Sort` (#306), whose ~11 KiB did not - fit the 2 KiB left after the streaming engine (#473) and set values (#316) + fit the 2 KiB left after the streaming engine (#473) and set values (#316). + The approved #723 ancestor-join optimization raises it to 1,234 KiB: + the measured increase is 2,720 bytes, avoiding a whole-attribute value + map for selective in-memory recursion without adding a storage index - No runtime dependencies (no JVM, no Python, no Node.js) **Anti-pattern**: Requiring external services, libraries, or runtimes to function. diff --git a/docs/BENCHMARKS.md b/docs/BENCHMARKS.md index 07640b4aeb..60d51139dd 100644 --- a/docs/BENCHMARKS.md +++ b/docs/BENCHMARKS.md @@ -35,8 +35,9 @@ fails with `QRY-012` while building the pending value map. No persistent value index or write-time cost is added. Release size with the same toolchain and lockfile: baseline 1,258,712 bytes, -change 1,261,432 bytes (+2,720). The existing 1,230 KiB gate (1,259,520 bytes) -is exceeded by 1,912 bytes; a budget decision is required before merge. +change 1,261,432 bytes (+2,720). The maintainer approved raising the v3 gate +from 1,230 to 1,234 KiB (1,263,616 bytes), leaving 2,184 bytes of headroom. +The budget and its rationale are recorded in PHILOSOPHY.md §4. Reproduce with `cargo bench --bench minigraf_bench -- '^recursion/'` on each revision. For an isolated timed phase, build with `--no-run` first and invoke diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index fd9d5525bd..bcde2aa08f 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -8,7 +8,7 @@ | **Ignored** | 17 | 18 | | **Total** | 2,000 | 2,034 | -**#723 verification (2026-10-29)**: full default and `test-hooks` suites passed on the bench machine before the final head-binding guard; the added representation regression, full non-fault unit suite and plan-independence matrix passed after it. The shared pending-count refactor passed the non-fault unit suite. The unchanged fault matrix passed in both full runs. Strict all-features clippy and formatting pass; the docs site builds 13 versions. No frozen answers were changed. +**#723 verification (2026-10-29)**: full default and `test-hooks` suites passed on the bench machine before the final head-binding guard. The final revision passes the full `test-hooks` suite excluding the unchanged fault matrix (2,000 passing, 18 ignored); those 16 fault tests passed in both earlier full runs. The final non-fault default unit suite and plan-independence matrix also pass. Strict all-features clippy and formatting pass; the docs site builds 13 versions. No frozen answers were changed. **Earlier verification**: 2026-10-28 on the designated bench machine: full default/test-hooks tests and the full branch-coverage suite pass, including golden files and migration/fault injection after sharing stable-sort code. Disabling internal reference-result cache eviction makes the targeted window regression fail. All unchanged coverage floors pass; measured overall coverage is 95.44% lines and 86.50% branches. Strict native/browser/WASI lint, WASI tests (1,182 passing, seven ignored), the WASI release build and Firefox tests (61 passing) also pass; the new committed-reader window fixture executes on both portable runners. The #672 default and `test-hooks` suites passed separately on 2026-10-28 before rebasing onto #641. From 75f7d3eb138dadd844ce407b43e82e2e3863fdcc Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Thu, 29 Oct 2026 08:47:21 +0530 Subject: [PATCH 3/3] test(query): cover ancestor plan fallback boundaries --- CLAUDE.md | 2 +- docs/TEST_COVERAGE.md | 10 +++- src/query/engine/recursive.rs | 106 ++++++++++++++++++++++++++++++++++ src/query/engine/tests.rs | 14 ++++- 4 files changed, 125 insertions(+), 7 deletions(-) diff --git a/CLAUDE.md b/CLAUDE.md index 1d35a4ad54..481187ac5d 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -218,7 +218,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**2004 tests** (1987 passing, 17 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). +**2005 tests** (1988 passing, 17 ignored; unit + integration + doc). Engine answers once checked by the executor are frozen in `tests/answers/` (#551). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 567b76f97e..de7c6b7f7f 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,11 +4,13 @@ | | Default features | With `--features test-hooks` | |---|---|---| -| **Passing** | 1,987 | 2,020 | +| **Passing** | 1,988 | 2,021 | | **Ignored** | 17 | 18 | -| **Total** | 2,004 | 2,038 | +| **Total** | 2,005 | 2,039 | -**#785 integration verification (2026-10-29)**: after merging the #693 decoder work from `v3`, the bench machine passed 76 engine tests (2 ignored), 24 key-decoder tests, the 16-test plan-independence matrix, and strict all-features clippy. Formatting passed. The release binary is 1,261,656 bytes, below the approved 1,263,616-byte cap. The totals above include both branches' four added tests; the earlier full-suite and proof results below remain tied to their original revisions. +**#785 patch-coverage verification (2026-10-29)**: the bench machine passed the complete CI branch-coverage run (1,973 passing, 13 ignored; this command excludes doctests) and every unchanged module floor. Overall line coverage is 95.54%. The new boundary cases cover five lines previously reported as missing or partial. CI-equivalent all-features clippy and formatting pass. + +**#785 integration verification (2026-10-29)**: after merging the #693 decoder work from `v3`, the bench machine passed 76 engine tests (2 ignored), 24 key-decoder tests, the 16-test plan-independence matrix, and strict all-features clippy. Formatting passed. The release binary is 1,261,656 bytes, below the approved 1,263,616-byte cap. The totals above include both branches' four added tests and the additional #723 costing-boundary test; the earlier full-suite and proof results below remain tied to their original revisions. **#723 verification (2026-10-29)**: full default and `test-hooks` suites passed on the bench machine before the final head-binding guard. The final revision passes the full `test-hooks` suite excluding the unchanged fault matrix (2,000 passing, 18 ignored); those 16 fault tests passed in both earlier full runs. The final non-fault default unit suite and plan-independence matrix also pass. Strict all-features clippy and formatting pass; the docs site builds 13 versions. No frozen answers were changed. @@ -50,6 +52,8 @@ Not counted above: the browser tests and the WASI run (see [Browser and WASI](#b - **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md). - **Compatibility and quality**: golden-file corpus of released file formats, cross-platform format compatibility, property-based tests, long-haul smoke coverage, a weekly soak at 10M facts with a 5-hour churn (#392), XTDB/Datomic semantic compatibility, grammar conformance, and rustdoc examples. +The #723 ancestor tests also cover empty deltas, the 128-row demand cap, the eight-records-per-demand-row cutoff, stored demand facts, repeated head variables and internally generated constant heads. These protect the fallback decisions as well as the optimized path. + ## Whole-System Checks These tests compare the database against an independent answer rather than a single fixed case. diff --git a/src/query/engine/recursive.rs b/src/query/engine/recursive.rs index 50d5a8510b..dc04856f35 100644 --- a/src/query/engine/recursive.rs +++ b/src/query/engine/recursive.rs @@ -374,3 +374,109 @@ fn unbound(var: &str) -> anyhow::Error { format!("Unbound variable in rule head: {var}") ) } + +#[cfg(test)] +mod tests { + use super::*; + use crate::graph::storage::FactStorage; + use crate::query::datalog::{ + magic_sets, parser::parse_datalog_command, rules::RuleRegistry, types::DatalogCommand, + }; + + /// Costing must stay bounded even when a later round has a much larger + /// demand relation. Empty deltas must not trigger an unrelated scan. + #[test] + fn ancestor_costing_respects_round_and_attribute_boundaries() { + let mut registry = RuleRegistry::new(); + for text in [ + "(rule [(boss ?x ?y) [?x :manager ?y]])", + "(rule [(boss ?x ?z) [?x :manager ?y] (boss ?y ?z)])", + ] { + let DatalogCommand::Rule(rule) = parse_datalog_command(text).unwrap() else { + panic!("expected rule"); + }; + registry.register_rule("boss".into(), rule).unwrap(); + } + let DatalogCommand::Query(query) = + parse_datalog_command("(query [:find ?b :where (boss :leaf ?b)])").unwrap() + else { + panic!("expected query"); + }; + let (registry, seeds) = magic_sets::rewrite(&query, ®istry).unwrap(); + let attrs: Vec<_> = seeds.iter().map(|(_, a, _)| a.as_str()).collect(); + let plan = super::super::plan_rules(&query, ®istry, &attrs).unwrap(); + let run = plan + .strata + .iter() + .flat_map(|(_, rules)| rules) + .flat_map(|rule| &rule.deltas) + .find(|run| run.entity_first.is_some()) + .expect("ancestor plan has an entity-first alternative"); + let alternative = run.entity_first.as_deref().unwrap(); + let Source::Scan(delta) = &run.plan.source else { + panic!("delta scan"); + }; + let Source::Scan(source) = &alternative.plan.source else { + panic!("demand scan"); + }; + let delta_rel = delta.derived.as_ref().unwrap().rels[0]; + let source_rel = source.derived.as_ref().unwrap().rels[0]; + let Term::Const(source_attr) = &source.a else { + panic!("demand attribute"); + }; + // (demand rows, delta rows, pending edges, stored demand, use alternative) + for (demand, delta, edges, stored_demand, expected) in [ + (1, 0, 100, false, false), + (1, 1, 7, false, false), + (1, 1, 8, false, true), + (128, 1, 1024, false, true), + (129, 1, 1032, false, false), + (1, 1, 100, true, false), + ] { + let meter = Meter::new(usize::MAX); + let ids = IdSpace::new(None, &meter); + let mut rels = Relations::new(0..plan.evaluated.attrs.len() as u64, &meter); + for i in 0..demand { + rels.add(source_rel, [Cell::Eid(i), Cell::Val(Scalar::Bool(true))]) + .unwrap(); + } + rels.end_round(); + for i in 0..delta { + rels.add(delta_rel, [Cell::Eid(i), Cell::Eid(i + 1)]) + .unwrap(); + } + rels.end_round(); + let storage = FactStorage::new(); + let mut facts: Vec<_> = (0..edges) + .map(|i| { + ( + uuid::Uuid::from_u128(i + 1), + ":manager".into(), + crate::Value::Integer(1), + ) + }) + .collect(); + if stored_demand { + facts.push(( + uuid::Uuid::from_u128(1), + source_attr.clone(), + crate::Value::Boolean(true), + )); + } + storage.transact(facts, None).unwrap(); + let snapshot = storage.snapshot().unwrap(); + let reads = Reads { + snapshot: &snapshot, + keys: None, + functions: &FunctionRegistry::with_builtins(), + bound: &TxBound::All, + }; + let selected = choose_run(run, &rels, &reads, &ids).unwrap(); + assert_eq!( + std::ptr::eq(selected, alternative), + expected, + "demand={demand}, delta={delta}, edges={edges}, stored={stored_demand}" + ); + } + } +} diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 2b18f53355..d899af78b3 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -2706,15 +2706,23 @@ fn ancestor_alternative_preserves_head_value_representation() { None, ) .unwrap(); - for head in ["?x ?z", "?x ?y"] { + for head in ["?x ?z", "?x ?y", "?x ?x", "?x :fixed"] { let mut registry = RuleRegistry::new(); for text in [ "(rule [(boss ?x ?y) [?x :manager ?y]])".to_string(), - format!("(rule [(boss {head}) [?x :manager ?y] (boss ?y ?z)])"), + format!( + "(rule [(boss {}) [?x :manager ?y] (boss ?y ?z)])", + head.replace(":fixed", "?z") + ), ] { - let DatalogCommand::Rule(rule) = parse_datalog_command(&text).unwrap() else { + let DatalogCommand::Rule(mut rule) = parse_datalog_command(&text).unwrap() else { panic!("rule"); }; + // Internal rewrites may supply constant heads, although the + // public rule syntax allows only variables. + if head == "?x :fixed" && rule.body.len() == 2 { + rule.head[2] = crate::query::datalog::types::EdnValue::Keyword(":fixed".into()); + } registry.register_rule("boss".into(), rule).unwrap(); } let DatalogCommand::Query(query) =