diff --git a/CHANGELOG.md b/CHANGELOG.md index 3d2755a53d..f7d16a9bca 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -24,6 +24,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **The `uuid` dependency no longer enables `v4`** (#439). The library only makes v5 UUIDs, so the `v4` feature and, on browser wasm, `js` are gone from its `uuid` dependency, and with them `getrandom`. A crate that called `Uuid::new_v4` only because Cargo feature unification turned `v4` on through minigraf must now enable `uuid/v4` itself. The release binary shrinks by 48 bytes. - **Join answers no longer depend on the query plan** (#545). Two cases changed. A join on a float value now pairs `0.0` with `-0.0`, as a shared variable compared after the join key already did; before, `Value`'s hash told them apart, so the join key never paired them. NaN still equals nothing. Float constants in a pattern still match within `f64::EPSILON`. And a variable bound to a keyword by one pattern and to the ref of the entity the keyword names by another, which already joined, now returns the kind from the first of those patterns in the `:where` text. Before, it returned the kind from the pattern the planner ran first, so the answer could change with the selectivity of the other patterns, and differed under the `wasm` feature, which does not reorder. For example, with `[:alice :friend :bob]` stored as a keyword, `[:find ?b :where [?a :friend ?b] [?b :name "Bob"]]` returned the ref of `:bob`, because the planner runs the pattern with two constants first, and now returns the keyword `:bob`. Expression bindings follow the next entry (#596). The rule covers the top-level `:where` of queries with and without rules; inside `or`, `not` and rule bodies the kinds are unchanged. - **An expression binding a variable that another clause binds keeps only the rows where the two agree** (#596). `[(f …) ?x]` used to overwrite `?x` wherever the planner ran it, so when a pattern also bound `?x` the answer depended on whether that pattern ran first, and differed under the `wasm` feature, which does not reorder. Now the expression unifies: the row is kept when its result equals `?x`'s value, with the join equality of #545 (floats by IEEE `==`, a keyword equal to a ref to the entity it names, an integer never equal to a float, NaN equal to nothing). For example, with `[:a :age 30] [:b :age 40] [:p1 :score 41]`, `[:find ?a ?x :where [?e :age ?a] [:p1 :score ?x] [(+ ?a 1) ?x]]` returned `[30 31] [40 41]` natively and now returns `[40 41]`, as it did under `wasm`. `[(+ ?v 1) ?v]` never matches, and two expressions binding one variable must agree. When the two values differ only as keyword and ref, the variable returns the value of the first clause in the `:where` text that binds it, expressions included. This applies to `or` branches, `not` bodies and rule bodies too, on the executor and on the streaming engine. +- **A value a `not` / `not-join` body takes from the outer row compares as a join compares it** (#546). The executor had two paths for a negation body: the exclusion-set path compared the outer row's values as joins do (floats by IEEE `==`, a keyword equal to a ref to the entity it names), while the per-row path, taken when the body held an expression or a pseudo-attribute, in a query that invokes a rule, in an `or` branch and in a rule body, substituted each outer value into the body as a literal, so a float matched within `f64::EPSILON`. The answer therefore changed with the shape of the body: with `[:e1 :x 1e-20] [:g :y 2e-20]`, `[:find ?e :where [?e :x ?f] (not-join [?f] [?g :y ?f])]` returned `:e1` and `[:find ?e :where [?e :x ?f] (not-join [?f] [?g :y ?f] [(> ?f 0.0)])]` returned nothing. Every path now matches the body from the outer values, compared by join equality, so both return `:e1`; `0.0` and `-0.0` are equal and NaN equals nothing. A literal constant in the body still matches floats within `f64::EPSILON`. - **A per-fact pseudo-attribute reads the nearest pattern before it with the same entity** (#594). `:db/valid-from`, `:db/valid-to`, `:db/tx-count` and `:db/tx-id` read the metadata of one fact: the one matched by their *source*, chosen when the query, rule or prepared query is parsed, as the nearest pattern before them in the `:where` text with the same entity term and a stored attribute (a keyword, or a variable as in `[?e ?a _]`). The search starts in the pseudo-attribute's own clause list and moves outwards, before each enclosing `not` / `or`; it crosses a `not-join` / `or-join` only for an entity variable in its join variables, and stops at a rule body, which never reads its caller's patterns. Terms are the same when they are one variable, one `$slot`, or constants naming one entity (`:alice` and its UUID). Before, they read the last pattern *the planner ran* that matched the entity, so the answer depended on the plan and differed under the `wasm` feature: in `[?e :person/name ?n] [?e :person/age ?a] [?e :db/tx-count ?t]`, `?t` could be the tx-count of either fact, and is now the `:person/age` fact's. Three further changes follow: (1) with no source, the query fails at parse time with the new `PRS-081` instead of matching every visible fact of the entity (`[?e :db/tx-count ?t]` before `[?e :person/name ?n]`, a `_` entity, a pseudo-attribute in a rule body whose only candidate is in the caller); to read every fact of an entity, write `[?e ?a _]` before it; (2) inside `not`, `not-join`, `or` and `or-join`, a pseudo-attribute reads the outer fact, so `[?e :person/name ?n] (not [?e :db/tx-count 1])` excludes the entities whose *name* fact is from tx 1, where before the body matched any fact of the entity; (3) rows that differ only in a source fact's metadata are no longer merged by `or`. `:db/valid-at` is unchanged. The pseudo-attribute pattern now binds or checks a value; it never scans facts, so the planner places it after its source rather than by selectivity. - **A pseudo-attribute pattern never gives a variable its value** (#606). A variable bound by several patterns returns the value of the first real pattern in the `:where` text that binds it (#545); a `:db/valid-at` pattern that the planner ran first used to bind its entity variable itself, as a ref, so `[:find ?b ?t :where [?b :db/valid-at ?t] [?a :friend ?b] [?b :name "Bob"]]` returned the ref of `:bob` with source order and the keyword `:bob` stored by `:friend` natively. It returns the keyword now, whatever runs first. Only the keyword-or-ref kind changes; rows and counts are the same. - **Every build reorders query clauses; the `wasm` feature does nothing** (#594, #596). The `wasm` Cargo feature kept patterns, `not` clauses and `or` branches in source order and turned off the `or` short-circuits (#250), for small browser datasets and a predictable order. With every answer independent of the plan (#594, #596, #606) it only made queries slower, and no first-party build enabled it (the browser package uses `browser`). The feature is kept, so builds that name it still resolve, but is deprecated and has no effect. @@ -72,6 +73,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **Cursors stream the queries the engine runs** (#473, part 2: #544, third PR). `Minigraf::query`, `PreparedQuery::query` and `BrowserDb.query` no longer compute the whole answer at open for these queries: the cursor pulls one batch of up to 1,024 rows from the engine's operators when it runs out of rows, and `close` or dropping it stops the work. An attribute scan drained with `next_batch(1000)` holds 7 MiB at 1M and 10M facts (was 58 and 458 MiB) and runs 3–17 % faster (#394 envelope). The answer is still the database as it was when the cursor opened, whatever is written or checkpointed while it is open. A read error that happens after some rows of a `next_batch` call were gathered is returned by the next call, after those rows. No API change. - **Joins run on the streaming engine** (#473, part 3: #545, second PR). Queries of several patterns with stored attributes, with or without expression clauses, now run on the engine. Patterns run in the planner's order: the first is a scan, and each later one is an `IndexNestedLoopJoin` when its entity is a variable already bound (one entity range per row, committed and pending), or a `HashJoin` otherwise (value and attribute positions, cross products), built on the side with the smaller estimate. Joins follow the executor's rules (#545, first PR): floats are equal by IEEE `==`, a keyword equals a ref to the entity it names, and a variable keeps the value of its first pattern in the `:where` text. Measured at 1M facts (#394 envelope, p50 and peak RSS): `[:p :follows ?f] [?f :name ?n]` 796 ms → 50 µs and 322 → 4 MiB; `[:p :manager ?b] [?s :manager ?b] [?s :name ?n]` 1.67 s → 148 ms and 392–462 → 14 MiB; `[?e :follows ?f] [?f :group 7] [?f :name ?n]` 2.6 s → 1.1 s and 468–480 → 42 MiB. `or`, `not`, rules and aggregates still run on the executor. Results are unchanged (`test-oracle`). - **Pseudo-attributes across joins and `:db/valid-at` run on the streaming engine** (#473, part 3: #545, third PR). A per-fact pseudo-attribute pattern (`:db/valid-from`, `:db/valid-to`, `:db/tx-count`, `:db/tx-id`) reads the metadata of its source (#594, above): the source's scan or join fills a metadata column from the fact's key, and the pattern binds or checks against it. A `:db/valid-at` pattern joins with every visible fact of its entity, as `[e _ _]` would, with the query's valid time as a column. Measured at 10M facts (#394 envelope, p50 and peak RSS): `[:p :follows ?f] [?f :name ?n] [?f :db/tx-count ?t]` 34 s → 56 µs and 6.0–7.5 GiB → 4 MiB (3.2 s → 56 µs at 1M). Results are unchanged (`test-oracle`). +- **`not` and `not-join` run on the streaming engine** (#473, part 4: #546, first PR). An `AntiJoin` keeps the outer rows for which the body has no row; it never deduplicates. A body that has the same rows for every outer row (its expressions and pseudo-attributes read only variables its own patterns bind) runs once, and its rows' values of the variables it shares with the outer row form a hash set. Any other body, and one whose first pattern's entity comes from the outer row, runs once per outer row from a one-row seed of the values it imports, stopping at its first row: an entity-bound body costs one index probe per row and holds nothing. Bodies are ordered with the imported variables counted as bound. Queries whose negation holds a rule invocation, and queries with `or` / `or-join`, stay on the executor. Measured (#394 envelope, p50 and peak RSS): an entity-bound `not` (`[?e :group 7] (not [?e :age 7])`, run per row) 760 ms → 27 ms and 222 → 6 MiB at 1M facts, 8.7 s → 0.29 s and 1.2 GiB → 6 MiB at 10M; a `not-join` keyed on a value whose body has an expression (`(not-join [?a] [?f :group 17] [?f :age ?a] [(< ?a 50)])`, hashed) 1.29 s → 5.8 ms at 100K, over 60 s → 53 ms and 171 → 7 MiB at 1M, over 60 s → 0.57 s and 1.5 GiB → 9 MiB at 10M. Other workloads unchanged. Results are unchanged (`test-oracle`). - **Committed reads hide superseded history on index keys** (#379). A query's committed facts are now reduced to the ones that survive net-assert (each fact's assertion from its newest transaction, unless that transaction retracted it; #435) while walking the index keys, before any fact is built. Only surviving entries are decoded and translated through the dictionary. A transaction that retracted a triple hides everything older in it, and a long run of hidden entries is skipped with one `seek`. `:as-of N` point and attribute queries now take the same index path instead of reading every fact in the file. On a checkpointed file with 2,000 superseded values, a point query takes 1.03 ms instead of 4.61 ms, an attribute scan 1.24 ms instead of 5.87 ms, and an `:as-of` point query 23 µs instead of 5.6 ms (at depth 1). Results are unchanged: the executor still applies net-assert to committed and pending facts together, and a pending fact is always newer than a committed one. - **B+tree reads no longer follow leaf sibling links** (v8 storage format, PR 1 of 5; #374). Every index scan uses a cursor that walks down from the root and keeps the path, with a forward `seek` that climbs only as far as needed. This prepares for copy-on-write index pages, which cannot keep sibling links. The file format and query results are unchanged. Concurrent 100k-fact scans take 25–37 % less time and checkpointing after one fact at 10k facts 9 % less; single point lookups and attribute scans are 2–6 % slower (about 0.4 µs per lookup). A corrupted child pointer now fails with STG-013 (wrong page type) or INT-049 (cycle) instead of following a bad link. @@ -87,6 +89,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 - **Performance envelope at 100K–10M facts (#394).** `examples/perf_envelope.rs` builds and caches fixtures of 100K, 1M and 10M facts (six attributes per entity, a ref tree, two valid-time windows, an entity with 1,000 versions). It reports open and checkpoint times, RSS, and p50/p99 latency for twelve query shapes, each shape in its own process. It builds with a new `envelope` Cargo profile (`release` at opt-level 3, as an application compiles the library; `release` itself is opt-level "z"). `docs/BENCHMARKS.md` and the README publish the results: point lookups and single-entity time travel stay flat (12–14 µs at 10M facts). Scans, aggregations and joins grow linearly with the attributes they touch. Rule queries are supported to 100K facts only. A Python FFI round trip (`bench/envelope.py` in minigraf-python) adds about 70 µs per query. `.github/workflows/envelope.yml` runs 100K and 1M on demand, and a 10K smoke pass on PRs that change the harness. The nightly Criterion `query/*` groups gain 100K and 1M scales. Profiling at 1M facts found #528, #529, #530, #531 and #532. - **Pseudo-attribute sources (#594).** `tests/pseudo_source_test.rs` covers the source rule (nearest earlier pattern in the text, two pseudo-attributes sharing one, every fact through `[?e ?a _]`, constants by entity id, `$slot`s by name), `PRS-081` for each shape with no source, reading the outer fact from `not`, `not-join` (listed and unlisted variable), `or` (never a sibling branch) and `or-join`, closed rule bodies, and `:db/valid-at`. Parser, optimizer and matcher unit tests cover the hidden variables, their placement and the join variables a crossed `not-join` gains. The plan-independence matrix gains the pseudo-attribute shapes. - **Answers that depend on the plan fail the tests (#596).** A test-only switch (`minigraf::__reorder`, `test-oracle` feature) turns off every place the native build reorders: the pattern selectivity sort, the `not`/`not-join` and `or`/`or-join` cost sorts and the `or` short-circuits (#250), and the engine's `HashJoin` build side. `tests/plan_independence_test.rs` runs a matrix of queries (joins, expressions, rules, `or`/`or-join`, `not`/`not-join`, keyword and ref, floats, long strings, aggregates, time travel), in memory and on file, through `execute` and a cursor, with the switch on and off, and requires the same rows. Under `test-oracle` the model-based (#385) and property (#386) tests also run every generated query with the switch off. +- **Negation bodies in both forms (#546).** A second test-only switch (`minigraf::__subplans`, `test-oracle` feature) forces the engine's `not` / `not-join` bodies to run hashed or correlated. `tests/plan_independence_test.rs` runs every query with the body forms chosen, forced hashed and forced correlated, each with reordering on and off; its matrix gains negations over floats near zero, `0.0` and `-0.0`, keywords and refs of one entity, long strings, bodies reading an imported variable they do not bind, variable-free bodies and `:db/valid-at`. `tests/negation_equality_test.rs` checks the changed answers on every executor path, in memory and after a checkpoint. The property test's rerun also forces hashed bodies. Engine unit tests cover the form the planner picks, routing, multiplicity, failing expressions in bodies, and that a hashed body is read once and a correlated one probes once per row. - `tests/snapshot_atomicity_test.rs` races a writer against a reader: a query must see each transaction whole, whether written with `execute` or a `WriteTransaction` (#554), and must read one state for all its patterns (#555), in memory and on file. It also runs the v2.x checkpoint race from #558, which never failed on v3: copy-on-write checkpoints do not overwrite pages a published reader uses. - **The `datalog_eval` fuzz guard counts partial bindings** (#597). The guard skipped inputs whose patterns join to more than 50,000 rows, counting only the rows after the last pattern. A `not-join` body still runs on the executor pattern by pattern in text order, so a 120-pattern body built hundreds of thousands of partial bindings before its last pattern matched nothing, and ran past the 60-second timeout. The guard now counts the bindings after every pattern. On the `v3` corpus (4,783 inputs) coverage drops by 7 of 9,719 edges. The input is added as a seed, as is the `btree_page` input of the cursor fix above. diff --git a/CLAUDE.md b/CLAUDE.md index 9b72531933..a70ab298cd 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -135,11 +135,11 @@ cargo run < demos/demo_negation.txt - `stratification.rs`: `DependencyGraph`, `stratify()` — negative edges + cycle detection - `rules.rs`: `RuleRegistry` — thread-safe rule management - `types.rs`: `EdnValue`, `Pattern`, `DatalogQuery`, `AsOf`, `ValidAt`, `WhereClause` (incl. `Not`, `NotJoin`); `PseudoAttr` enum, `AttributeSpec` wrapper - - `optimizer.rs`: Selectivity-based join reordering on every build (the `wasm` feature is a deprecated no-op). `reorder()` gates every reordering site; tests turn it off per thread (`set_reorder`, `minigraf::__reorder` under `test-oracle`, #596) + - `optimizer.rs`: Selectivity-based join reordering on every build (the `wasm` feature is a deprecated no-op). `reorder()` gates every reordering site; tests turn it off per thread (`set_reorder`, `minigraf::__reorder` under `test-oracle`, #596); `plan_seeded` orders a body with its imported variables counted as bound, and `subplans()` lets tests force the engine's negation bodies hashed or correlated (`set_subplans`, `minigraf::__subplans`, #546) - `prepared.rs`: `BindValue`, `PreparedQuery` — parse-once/execute-many with named `$slot` bind slots; `prepare_query`, `substitute` - `magic_sets.rs`: Magic-sets rewriting for demand-driven recursive rule evaluation (not applied to rules with `not`/`not-join`) -3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: patterns and expression clauses in `optimizer::plan` order; a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, today), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, `HashJoin` otherwise; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree). `mod.rs`: `Operator` (`next_batch`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` try it first: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it. +3a. **`src/query/engine/`** — Streaming query engine (#473), beside the executor until #551: `plan.rs` (which queries it runs: patterns, expression clauses and `not`/`not-join` without rule invocations, in `optimizer::plan` order (deferred `not`s last); a per-fact pseudo-attribute pattern reads the metadata column its source's scan fills (the hidden variable the parser named, #594), and `:db/valid-at` joins as `[e _ _]`; plain `:find` variables, today), `scan.rs` (one pattern over committed key ranges via `CommittedReader::key_source`/`live_keys`, AVET ranges for cross-kind constants, then the pending range by whole runs; one entity per probe for a join), `join.rs` (`IndexNestedLoopJoin` when the pattern's entity is bound, `HashJoin` otherwise; `JoinKey`: floats by IEEE `==`, a keyword equals a ref to the entity it names), `filter.rs` (`Filter`/`Bind` and pseudo-attribute steps over batches; a `Bind` on a bound slot keeps the rows where the result is join-equal, #596), `anti.rs` (`AntiJoin`, #546: a body with the same rows for every outer row runs once into a hash set of its imported-variable keys; any other body, or one whose first pattern's entity is imported, runs per outer row from `seed.rs`'s one-row `Seed`, via `Operator::rewind`; never deduplicates), `cell.rs`/`batch.rs` (id cells in columnar batches of 1,024), `ids.rs` (DICT and provisional ids, `keyword_eid`), `project.rs` (ids → values for returned rows only), `oracle.rs` (with `cfg(test)` or the `test-oracle` feature, every engine query also runs on the executor and must agree). `mod.rs`: `Operator` (`next_batch`/`rewind`/`close`/`counters`), `Stream` (the operator tree over an owned `Snapshot`, pulled one batch at a time). `DatalogExecutor::open` / `execute_query` try it first: a cursor gets the `Stream` (`Answer::Stream`), `execute` drains it. 4. **`src/temporal.rs`** — UTC-only timestamp parsing (avoids chrono CVE GHSA-wcg3-cvx6-7396) @@ -204,7 +204,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are ## Test Coverage -**1565 tests** (1555 passing, 10 ignored; unit + integration + doc). +**1578 tests** (1568 passing, 10 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/README.md b/README.md index 92365a36d5..dbbab0d037 100644 --- a/README.md +++ b/README.md @@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit ```bash cargo run # interactive Datalog REPL -cargo test # run 1565 tests +cargo test # run 1578 tests cargo run < demos/demo_recursive.txt # recursive rules demo ``` diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index e48cf5537f..e2eb4ee769 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -2,9 +2,9 @@ ## Coverage Summary -**Verified**: 2026-10-16 with `cargo test --quiet` +**Verified**: 2026-10-19 with `cargo test --quiet` -**Result**: 1,555 passing tests and 10 ignored tests (1,565 total) +**Result**: 1,568 passing tests and 10 ignored tests (1,578 total) This covers the unreleased file-format-v8 work (#287, #371): the index-key value-collision fix, the v7→v8 migration, and the drop of formats v1–v6. It otherwise still covers the public database API, the Datalog engine, storage and recovery paths, v2.0.0's locking and structured-error-code changes, and v2.0.1's regression test for rebuilding indexes on open after several checkpoints (#370). Merged from the v2.x line: `tests/point_query_history_test.rs` and new storage unit tests check that attribute-narrowed bound-entity lookups return exactly what a full scan returns, and that `net_asserted_facts` matches its previous implementation on randomized histories (#323). Attribute-scan tests check that the AEVT range covers exactly the queried attribute, including non-ASCII names such as `:丿` and prefix siblings such as `:ab` for `:a` (#381). Incremental B+tree rebuild tests check that checkpoints which copy untouched index leaves produce exactly the entries and file checksum a full rebuild would, including over repeated checkpoints, that single-fact checkpoints do not fragment the index, and that a damaged slot directory is rejected rather than copied (#315). B+tree cursor tests check that every scan walks the tree, not the leaf `next_leaf` chain: full scans and start positions match the input, `seek` from the current position lands where a fresh descent from the root would (randomized, plus within a leaf, to a sibling, across subtrees, past the end, into the gap after a leaf, and backwards as a no-op), a seek to the sibling leaf reads exactly one page, reads are unchanged with every `next_leaf` zeroed, a child pointer into a non-B+tree page is STG-013, and a cycle in child pointers is an error, not a hang (v8 storage format PR 1, #374). Directory-sync unit tests check that creating the `.graph` file or the WAL, and deleting the WAL, fsync the parent directory after the file operation, and that reopening an existing file does not (#389). Disjunction tests check that `or-join` returns an empty result, not INT-031, when no rows reach it: on an empty database, after a pattern that matches nothing, after a `not` that removes every row, and in a rule body (#405). A stratification unit test builds the same two-rule negative cycle 64 times and checks that the INT-054 message names the same predicate pair every time (#410). Magic-sets tests check that a recursive rule with a literal start that recurses through another rule returns the same results as without the literal (#297). API tests check that `execute()` and `WriteTransaction::execute()` reject `$slot` bind tokens in every position with API-010 (#407). The REPL `run()` test now runs in a child process with null stdin, so it no longer hangs when the test runner's stdin is an open non-TTY stream (#415). v8 page-format tests (PR 2, #374, #388) check the 24-byte page header (a flipped bit, a wrong page id and a future generation each give their own STG code, legacy page types fail before the CRC, and a failed page is never cached), meta-page encoding, the free-list chain, WAL v2's base generation, and every row of the meta-selection table: both slots valid, a torn newest slot with the WAL's base generation (opens at the older one), a WAL newer than the valid meta, pages of the next generation on the free list or past `page_count` with no WAL (all STG-033, with the file unmodified), an unknown feature bit (STG-034), and a pre-release v8 single header (STG-032). Fault-injection tests crash `save()` at every page write (cleanly and with torn pages, including the meta write) and every sync, and crash a v7 migration at every write; each reopen finds exactly the old or the new checkpoint, and every reachable page plus the free list covers the file exactly. Twenty-five consecutive saves never write a page the previous meta references. Covering-key tests (PR 3, #433) check that byte order equals logical order for every key component and value type on random tuples (negative, zero and large integers, NaN and ±0.0, strings with 0x00, 64- and 65-byte strings, FOREVER, newest-transaction-first) and that every component round-trips; that prefix-compressed leaves and shortest-separator internal nodes round-trip, agree with a linear scan, keep `max(left) < s ≤ min(right)`, and reject an overflow; that the byte-key B+tree's builds, incremental rebuilds, cursor and `seek` match their expected sets; that dictionary ids are assigned once, never reused, shared between a keyword attribute and value, and deterministic; that a re-asserted or retracted long value writes no new value page and a forced hash collision still finds the right value; that one transaction with two timestamps is STG-037 and a missing dictionary entry STG-036; that committed reads by entity, entity and attribute, attribute, and in full equal an in-memory model across eight checkpoints and a reopen; that short-valued reads touch no value page; that a v7 file with every value type, long strings, refs and retractions migrates to exactly the same facts; that a pre-covering-key v8 file is STG-032; and that string values over 4,068 bytes and attributes or keywords over 1,024 bytes are WAL-003. A WAL test checks that reopening next to a fully checkpointed WAL does not reuse transaction numbers (#447). Copy-on-write checkpoint tests (PR 4, #434) check that lazy free-list pops and pushes conserve every page across page boundaries, partial head pages and chain exhaustion, never hand out a page freed in the same generation, and share unread chain pages unchanged; that a copy-on-write insert equals a sorted merge for random batches (including keys below the first and above the last, many into one leaf, root growth to depth 3, and 1 KB separators that split internal nodes), leaves the old tree readable and unchanged, frees exactly the replaced nodes, writes only new pages, writes exactly one leaf and two internal nodes for one entry in a depth-3 tree, and does not fragment leaves under single inserts; that a checkpoint after 1 or 100 right-edge facts writes at most the tree-depth difference more pages at 100,000 facts than at 10,000, and at most one path per new entry per tree for random keys; and that four reader threads querying throughout 40 checkpoints never fail and never see the fact count go backwards. Hardening tests (PR 5) damage an index leaf, an internal node, a dictionary leaf, a value page and a free-list page in turn. Every committed read or checkpoint that reaches the damaged page fails with STG-029, never with wrong or fewer rows. A query through `Minigraf` on a file with damaged leaves fails with STG-029, and the file still opens at its last checkpoint. A size test measures at most 200 bytes per fact (142 measured) on 144k facts in #433's shape; its 1.15M-fact variant is ignored locally and runs in the nightly smoke workflow. A shared dictionary-cache test checks that cached ident and timestamp lookups return the same facts and that the cache stays bounded. Merged from the v2.x line: storage and `edge_cases_test.rs` tests check that more than 65,535 uncheckpointed facts each resolve to their own fact through entity lookups and attribute scans, in memory and file-backed (#445). Merged from the v2.x line: `tests/golden_corpus_test.rs` opens a copy of each committed golden file in `tests/golden/` (v7 files written by minigraf 2.0.3: one checkpoint, several checkpoints, indexes rebuilt on open, a crash-left WAL, an already-checkpointed WAL, same-transaction multi-values) and checks its manifest's CRC32, `tx_count` and query results after open, after a checkpoint and reopen, and after one more write; a second test checks that every golden file has a manifest (#391). On `v3` the same test checks that each v7 file has a v8 meta page after its first open and gives the same results after reopening the migrated file, and adds seven v8 golden files (one checkpoint, seven copy-on-write checkpoints, a crash-left v2 WAL, an already-checkpointed v2 WAL, same-transaction multi-values, a v7 file migrated in place, and long values at the size limits); the #371 queries, skipped on v2.x, run and pass. `tests/model_based_test.rs` runs random sequences of transacts, retracts, write transactions, checkpoints, reopens and simulated crashes against a file and, after every step, compares the transaction counter, `verify`, full rows with windows and tx counts, and six query shapes under `:as-of N` and `:valid-at T` with a reference model (#385). `tests/property_test.rs` writes random histories (batched transacts, retracts, write transactions, checkpoints) in memory and to a file, and compares random queries (one to three joined patterns, `not` or `not-join`, a comparison predicate, `:as-of`, `:valid-at` or `:any-valid-time`) with a reference evaluator, on the open file and after a reopen; a query error fails the test (#386). `tests/crash_kill_test.rs` kills a child process running a seeded workload (multi-valued batches, batched retracts, five checkpoint modes) at a random point and checks that the reopened file holds exactly the transactions the child logged as committed, or those plus the one in flight, through full-scan, AEVT, AVET, EAVT and `:as-of` queries and `verify`, again after a second reopen and after a checkpoint plus reopen (#384). Integrity tests (#373) check that intact files verify with no problems and an exact fact and page count, and that `verify` reports each kind of damage with its code: an EAVT, AEVT, AVET or VAET leaf missing an entry (STG-038), keys out of order and a page reached from two trees (STG-039), a rotted index leaf (STG-029), a free page still in use and a leaked page (STG-035), a missing transaction entry (STG-036), and an entity id whose UUID maps to another id (STG-040). After each index or free-list damage, `rebuild_indexes` leaves a file that verifies clean, reads back every fact and accounts for every page. The source is an index that agrees with another one, or the only intact one; three intact indexes that all disagree, or a damaged dictionary, give STG-041 with the file unchanged. A rebuild commits pending facts, including new ids and long values. A crash at every write (clean and torn) and every sync of a rebuild reopens either at the old generation with only its old damage or at the new one with none, never losing a fact. Through `Minigraf` (`tests/integrity_test.rs`), a rebuild commits WAL entries and deletes the WAL, and flipping a byte in each leaf of a file in turn is always reported, then either repaired (index leaves) or refused with STG-041 and the file unchanged (dictionary leaves). Page-count tests (#497) check that a CRC-valid meta whose `page_count` is past the end of the file (one page past, 2^50, `u64::MAX`; with the other slot valid or damaged; with or without a WAL) and a file cut short by one page, three pages or down to three pages are `STG-044` at open, with the file unchanged and not grown, while a `page_count` exactly at the end opens; that a checkpoint whose pages did not all reach the backend fails with `INT-049` before writing its meta, and the file reopens at the previous generation; and that `verify` at a meta counting pages past the end reports `STG-044` without scanning to that count. Through `Minigraf` (`tests/integrity_test.rs`), a file truncated by one or three pages and a file whose meta was rewritten with `page_count` 2^50 and a valid CRC are `STG-044` read-write and read-only, with no WAL created and the file length unchanged. The `file_header` fuzz input from #497 is a corpus seed. A sub-page test (#506, `tests/integrity_test.rs`) checks that a file of 1 to 4,095 bytes is `STG-045` read-write and read-only, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes writes when it is a prefix of the first meta page or all zeros; a file-backend unit test checks that `partial_page` returns the bytes past the last whole page. The `corrupt_file` fuzzer no longer skips files under one page: they must fail to open or open empty, and the #506 input is a corpus seed. Damaged v7 fact page tests (#496) check that a page in the counted fact range whose type byte is anything but the fact-page type (zero, `0x01`, the v2.x B+tree types, `0xFF`, a zeroed page; first and last page) is `STG-014` rather than skipped, while a range derived from the first index root skips only v2.x B+tree pages; that opening such a v7 file read-write or read-only fails with `STG-014` and writes nothing; and, in `tests/migration_matrix_test.rs`, that the golden `v7_basic.graph` with page 1's type byte changed or page 1 overwritten with noise fails both opens with the file unchanged and no WAL created. Both inputs are `fact_page` corpus seeds. Merged from the v2.x line: `tests/edge_cases_test.rs` checks the same refusal and acceptance through `Minigraf::open` on a database checkpointed twice (#506). Torn-WAL-tail tests (#513) check that opening a WAL writer cuts off a partial last entry (cut in the checksum, the header or the payload) or an entry with a bad checksum and everything after it, then appends where replay reaches, and leaves an intact WAL byte for byte; that an append that fails part-way makes every later append `WAL-007` while a rejected oversize fact (`WAL-003`, nothing written) does not; through `Minigraf`, that the failed transaction is not applied, later `transact` and `commit` are `WAL-007`, and a `checkpoint()` makes writes work again; and, in `tests/wal_test.rs`, that a commit made after reopening a crash-left WAL with each kind of torn tail survives a second crash. The fault matrix (#390, `src/fault_matrix.rs`) drives a test-only fault plan through the real file backend, WAL and directory fsync: an EIO, a short or torn write (1, 40 and 4,095 bytes), a full disk that keeps failing every later write, a failed fsync, and a failed fsync that also loses the writes since the last good one ("fsyncgate"), each at every write or sync call of a transact, a transact that creates the WAL, an automatic checkpoint, `checkpoint()`, the close-time checkpoint and `rebuild_indexes()`, on a database committed over two checkpoints with multi-valued, retracted and long values and entries pending in the WAL. After each fault, the handle holds the old facts or those plus the whole transaction, never part of one; after a failed checkpoint another is `STG-046`; a later write succeeds or is `WAL-007`/`STG-046`; a kill and reopen gives exactly the handle's facts, plus the failed transaction whole or not at all, and `verify` finds nothing; and a commit after recovery survives another kill. Two more tests fill the disk halfway through a checkpoint (`STG-046`, reads unchanged, reopen intact), and fail the fsync after a checkpoint's meta write and then retry the checkpoint, crashing at each of its writes: the retry is refused and every reopen is intact (without the refusal, a reopen hits `STG-029`). Unit tests check the fault plan's counting, and that a `rebuild_indexes` refused with `STG-041` leaves the handle usable. Live-read tests (#379) check that `triple_len` ends exactly where `tx↓` begins for every value type and index; that on random histories (several valid-time windows, retractions, re-assertions, several values per attribute, long values, 12 transactions per checkpoint) the committed live read for every scan kind and `:as-of` point is exactly the net-asserted set, that it stays equivalent with pending facts on top, and after reopen; and that a point read on a triple asserted and retracted 2,000 times reads under a third of the pages a history read does, with or without `:as-of`. `tests/live_reads_test.rs` runs the same history in a checkpointed file database and in memory and checks that point, attribute, full-scan, join, valid-time, `:as-of` and rule queries return the same rows, before and after reopen. One-window tests (#435) check that `net_asserted_facts` keeps each triple's newest transaction only (a later window replaces an earlier one, closing an open window, a retraction in the newest transaction hides it, records with two windows in one transaction keep both, once each) against a per-triple model on random histories; that the on-disk key walk agrees at every `:as-of` before and after reopen; and that `API-011` rejects two windows of one fact in one transaction without taking a `tx_count`. `tests/valid_time_window_test.rs` checks replacing, closing, extending, reopening and retract-then-reassert through entity-bound and attribute queries in memory, on a checkpointed file and after reopen, `API-011` from `transact` and from `WriteTransaction::execute`, and a later statement's window committed when two statements of a `WriteTransaction` give one fact different windows. Window-validation tests (#436) check that `check_valid_windows` rejects an empty window, an inverted one, and a `:valid-to` at or before the transaction time when `:valid-from` is left out, but not retractions; that `execute` rejects each such `transact` (both bounds, equal bounds, `:valid-to` only, a per-fact bound inverting the transaction's window) with `API-019` without writing or taking a `tx_count`, in memory, checkpointed and after reopen; that `tx.execute()` rejects them and the transaction still commits its other statements; that `commit()` rejects a default `valid_from` that has passed the `:valid-to` by commit time; and that `FactStorage::transact_batch` takes no `tx_count` on rejection. Statement-order tests (#477, `tests/statement_order_test.rs`) run every mix of two statements on one fact inside a `WriteTransaction` (retract then assert, assert then retract, two retracts, two windows, after a committed assertion and on an empty database) and check that reads inside the transaction and the committed rows agree, in memory, checkpointed and after reopen; that other facts of an overridden statement survive; that the commit is one transaction without the overridden records; and that two windows in one statement are `API-011` from `tx.execute()` while the rest commits. A unit test checks the commit collapse keeps each fact's newest statement in order. A log-writer test checks that an inverted window is `API-019`, a second window of a fact in one transaction `API-011`, and an assertion and a retraction of one fact in one transaction `API-020` in either order, each leaving the writer usable and the output exact, while duplicate retractions, identical repeats and the same fact in the next transaction are accepted. Cursor tests (#432, `tests/cursor_test.rs`) check that `query()` batches partition the `execute()` answer for several batch sizes (never empty, never over `max_rows`, `max_rows == 0` still progresses, `None` stays `None`), that the iterator and aggregates, rules, `:as-of` and `:any-valid-time` match `execute()`, that a cursor opened before a `transact`, a `WriteTransaction` commit, a retract or a checkpoint returns the pre-write answer to the end (in memory and file-backed), that `transact`/`retract`/`rule` are `API-012` and bind slots `API-010`, that a `WriteTransaction` thread gets `INT-001`, that rule limits give `INT-020` as from `execute()`, that `PreparedQuery::query` matches `PreparedQuery::execute`, and that a cursor is `Send` and outlives its database handle. Fact-log tests (#430, `tests/fact_log_test.rs`) check that `fact_log()` returns exactly the records written (assertions and retractions, with `tx_count` and `tx_id`) in memory, with everything pending, half checkpointed, fully checkpointed and after reopen, in both orders, with windows of 1 to 1,000 records and batch sizes of 1 to 1,000, in non-decreasing `tx_count` in Tx order; that every layout gives identical records, including valid-time windows and long string values; that a transaction larger than the window is split with no loss or duplicate; that attribute, attribute-prefix, entity and tx-range filters and their combinations match a model, and unknown names match nothing; that writes after open are not in the log; that `checkpoint()` and `rebuild_indexes()` are `API-013` while a log is open (a checkpoint with nothing to write is allowed), that automatic checkpoints from `execute()` and `WriteTransaction::commit` wait for the log, and that closing, dropping or finishing the log releases the database; that a `WriteTransaction` thread gets `INT-001`; and that a log is `Send`, outlives its database handle, and the deferred writes replay on the next open. Read-only open tests (#429, `tests/read_only_open_test.rs`) check that a read-only handle on a file with checkpointed facts and a pending WAL returns the same query results, `tx_count` and fact log as a read-write open; that queries, a cursor, a fact log, `verify`, `prepare`, rules and a UDF leave the `.graph` and WAL bytes and the `.graph` mtime unchanged, and no WAL is created; that `transact`, `retract`, `begin_write`, `checkpoint` and `rebuild_indexes` are `API-014` without taking a `tx_count`, also on a read-only in-memory database and through the builder path; that a missing file is `STG-042` and nothing is created; that an empty file is an empty database and stays 0 bytes; that read-only handles share a file while a read-write one is refused with `STG-025`, both ways; that a file without write permission opens read-only; and that small and whole-file page caches work. File-backend unit tests check that a shared-mode backend refuses page writes and syncs with `INT-056`, that the in-process registry counts readers and admits readers or one writer (also without kernel locks), and that a reader in another process shares the file with a reader here and refuses a writer here with `STG-026`. Storage unit tests check that a read-only open of a v7 file at every point of an interrupted migration (clean and torn writes) sees every fact and writes nothing, and that an empty backend stays empty. `tests/golden_corpus_test.rs` opens a copy of every golden file read-only first and checks its `tx_count` and queries, and that neither the file nor its WAL changes. Log-writer tests (#431, `tests/log_writer_test.rs`) copy a source's fact log (assertions, retractions, an explicit valid-time window, long strings, refs, keywords, checkpointed and pending facts) through `LogWriter` and check that the new file has no `.partial` or WAL, verifies clean, and gives the source's `tx_count`, fact log and query results (current, `:valid-at`, `:any-valid-time`, every `:as-of`, and entity-, attribute- and value-bound lookups) read-write, read-only and after reopen (#370); that it takes new writes at the source's next `tx_count`; that 90,000 facts over two batch commits verify clean and count correctly at `:as-of`; that a purged middle transaction is a hole whose `:as-of` equals the one before, and trailing holes keep the counter through `advance_tx_count`; that an empty log is an empty database with the counter; that `tx_count` 0, a lower or closed transaction and a backwards advance are `API-015`, a second `tx_id` `API-016`, a second window `API-011`, a retraction of an asserted fact in one transaction `API-020`, an empty window `API-019` and oversize values or idents `WAL-003`, each leaving the writer usable and the output exact, with repeats written once; that an existing target or WAL is `STG-043`, a second writer `STG-025` and `read_only` `API-014`; that a stale `.partial` is reused; that dropping an unfinished writer leaves nothing; that `finish` refuses a target created during the build and leaves it untouched; and that `LogWriter` is `Send`. Unit tests check that a batch commits only when a transaction opens past the batch size, never splitting one, and that `FileBackend::truncate` empties a file. A unit test in `error.rs` checks that `MinigrafError::invalid_argument` and `MinigrafError::closed`, the constructors for language bindings, give API-017 and API-018 with their text. Query-validation tests (#406, #414) check that a plain `:find` variable or a window function's argument, `:partition-by` or `:order-by` variable that no `:where` clause binds (including `?_` wildcards) is `PRS-080` from both `execute()` and `prepare()`, naming the variable, while variables bound by a pattern, an attribute position, a rule call, an expression binding, an `or-join`, every branch of an `or`, a pseudo-attribute or a window spec are accepted, and bind slots are not mistaken for `:find` variables; and that an unknown aggregate is `QRY-010` and an unknown window function `QRY-011` on an empty database, when no row matches, when rows match, through a rule query and through a prepared query, while a registered UDF in either position returns an empty result on an empty database. Coverage-gate tests (#396) check that replay stops at a WAL entry whose first fact is longer than 10 MB or that claims more than 1M facts, that a WAL writer cannot be opened in a missing directory, and that a failed cut of a torn WAL tail fails the open and leaves the file as it was; that a short v7 page and a slot past the record count are `INT-024`; that a migration backup meta of another generation or file length is not used (`STG-032`, file unchanged), and a torn first meta with data in page 1 is `STG-032`, not a new file; that `save` with nothing pending writes nothing, `into_backend` saves pending facts, and `rebuild_indexes` with nothing checkpointed commits the pending facts; and that unsorted or repeated B+tree input and a stored key inserted with another value are `INT-049`, a tree pointer to a free-list page is `STG-013` from `get`, a leaf walk and a copy-on-write insert, and the read-only `MutexStorageBackend` refuses writes, syncs and close. A page-cache test holds two threads in the backend read so both miss the same page, and checks that both get the one cached copy; before it, that path ran only when the scheduler happened to race the threads, and the gate flapped. Three `BrowserDb` tests (wasm32, run with `wasm-bindgen-test` in a browser, not counted above) check that `query()` batches of 1, 7 and 1,000 give the rows of `execute()`, that a cursor keeps the answer from when it opened and returns the end after `close()`, and that a `transact` is API-012. The wasm32 targets run in CI (`.github/workflows/wasm.yml`). In a browser (`wasm-pack test --headless`, Firefox and Chrome): 32 `wasm_bindgen_test` tests: nineteen for `BrowserDb` (including IndexedDB persistence, the cursor, and the flush returning every dirty page and failing on one it cannot read, from #470), eleven for `BrowserBufferBackend` (which used `#[test]` and never ran before), and two checking that IndexedDB page keys accept only whole numbers from 0 to 2^53. Five of the `BrowserDb` tests (#411, #440) check that opening a v7 store written straight into IndexedDB stores a v8 meta page and only the live pages, with nothing written on the next open; that after each of 60 transacts memory, and at the end IndexedDB, hold exactly the pages not on the free list while the file grows by under one page per transact; that a commit applied in memory but never flushed reopens at the previous one and keeps working; that an export after churn is as long as the meta says and imports back with its free pages dropped; and that `importGraph()` deletes the replaced database's IndexedDB keys. Two buffer tests check that releasing a page drops its bytes and any unflushed write, and that export writes a released page as zeros. A native storage test checks that a file whose free pages are all zeros (as the browser exports them), both just migrated from v7 and after 20 saves, opens, verifies clean and keeps committing, and the free-list test checks that a checkpoint reports exactly the ids it newly lists. On `wasm32-wasip1` under Wasmtime: the unit and integration tests that do not use a file run, 956 passing; ten that spawn threads or a child process are ignored on WASI. These are not counted above. A WAL test checks that a checkpoint with no facts to flush still removes a WAL whose entries are all already in the file, and the golden-corpus test now requires the WAL to be gone after a checkpoint for the `stale_wal` fixtures too (#457). A WAL test checks that closing a handle opened with `wal_checkpoint_threshold(usize::MAX)`, in both sync modes, leaves the `.graph` file byte for byte as it was and keeps the WAL, whose entries replay on the next open, and a unit test closes an in-memory handle under the same setting (#476). A recursive-rule test checks that a rule query on a database with more live facts than `max_results` returns its answer, with a bound and with a free first argument, and that a query deriving more facts than its `:max-results` is still `INT-020` (#528). A log-writer test runs the online backup from `docs/DURABILITY.md`: it copies a read-write handle with an uncheckpointed transaction through `fact_log` and `LogWriter` while another thread writes past the automatic checkpoint threshold, and checks that the copy verifies clean, holds exactly the records the log returned and the counter read after the log opened, and that every concurrent write reaches the source's file once the log is dropped (#398). Rule-body tests in `tests/recursive_rules_test.rs` check that a `:db/valid-at` pattern in a rule definition, in its `not` and `not-join` bodies and in its `or` branches binds the query's valid time, on the semi-naive, stratified and magic-sets paths (#617). @@ -20,7 +20,8 @@ This covers the unreleased file-format-v8 work (#287, #371): the index-key value - **Prepared time travel** (#603): `tests/prepared_statements_test.rs` runs literal `:as-of` (counter and timestamp), `:valid-at`, `:any-valid-time` and a per-fact pseudo-attribute query through `execute`, a prepared `execute` and a prepared cursor, which must agree; a `prepared.rs` unit test checks that `substitute` keeps non-slot `:as-of` and `:valid-at`. - **Join rules** (`tests/join_rules_test.rs`, 10 tests; #545): a join on a float value pairs `0.0` with `-0.0`, through the hash key and as a shared variable, and a float constant still matches within epsilon; a variable bound to a keyword by one pattern and to the ref of the same entity by another returns the kind from the first pattern in `:where` text order, when the planner runs the patterns in another order, through the attribute position, before and after a rule call, and with a repeated pattern; an expression binding unifies with a pattern binding the same variable, and the first binder in the text, pattern or expression, gives the value (#596); a pseudo-attribute pattern never gives a variable its value, even when it runs first (#606; the plan-independence matrix checks it with reordering off). Under the `test-oracle` feature the joins among them also run on the streaming engine. A unit test checks that `-0.0` and `0.0` hash alike. - **Pseudo-attribute sources** (`tests/pseudo_source_test.rs`, 12 tests; #594): a per-fact pseudo-attribute reads the nearest earlier pattern in the text with the same entity term (#594's example in both text orders), two pseudo-attributes share a source, `[:alice ?a _]` gives one row per fact, constant and bound value terms check, `:alice` and its UUID are one term while `?e` and `:alice` are not, PRS-081 for a pattern after it, alone, `_`/`?_x` entities, another entity's pattern and a rule call; a `not` body reads the outer fact (and a source inside the body), `not-join` crosses for a listed variable only, `or` branches read the outer fact and never a sibling, `or-join`, closed rule bodies, `$slot`s by name at prepare time, and `:db/valid-at` once per fact. Parser unit tests check the hidden variables (`?#.`), the join variable a crossed `not-join` gains, and the PRS-081 text; an optimizer test places a pseudo-attribute pattern after its source and the pattern binding its value; matcher tests read the hidden variable, a substituted integer, and nothing without a source; the engine tests run the sourced shapes and check PRS-081 for the old fallback shapes. The plan-independence matrix gains eleven pseudo-attribute shapes. -- **Plan independence** (`tests/plan_independence_test.rs`, 12 tests, `test-oracle` feature only; #596): a matrix of queries (joins in both text orders, cross products, keyword and ref, floats, long strings, filter and binding expressions, recursive rules and rules with `not`, `or`/`or-join` including the #250 short-circuit shapes, placed and deferred `not`/`not-join`, aggregates, `:as-of`, `:valid-at`, `:any-valid-time`), in memory and on file after a checkpoint and a reopen, through `execute` and a cursor, gives the same bag of rows with clause reordering on and off (`minigraf::__reorder`); #596's example and the unification cases (an expression whose output is its input, two expressions on one variable, integer vs float, `-0.0` vs `0.0`); and `or` / `or-join` branches whose expressions read or bind from a variable only the outer row binds, nested and in rule bodies (#620). Under `test-oracle` the model-based and property tests also rerun every generated query with reordering off. Unit tests cover `branch_outer_reads` (#620), `apply_expr` (equal, different, integer vs float, NaN, `-0.0`/`0.0` with and without replacing, keyword vs ref both ways, a failing expression), `Binders::expression`, the switch (source order kept, per thread, restored on drop), and the engine planner's `Bind` modes and build side with the switch off; the engine's join matrix gains six unification shapes. +- **Negation equality** (`tests/negation_equality_test.rs`, 5 tests; #546): a value a `not` / `not-join` body takes from the outer row compares by join equality on every path (exclusion set, per-row body with an expression, a query that invokes a rule, a rule body): `1e-20` and `2e-20` differ, `0.0` equals `-0.0`, a keyword imported into an entity position equals the ref, and a float literal in the body still matches within `f64::EPSILON`; through `execute` and a cursor, in memory and after a checkpoint. Engine unit tests (`src/query/engine/tests.rs`, 6 more) run every negation shape (hashed and correlated bodies, keys on entity, value and attribute positions, floats, keywords and refs, long strings, bodies reading an imported variable, variable-free bodies, per-fact pseudo-attributes and `:db/valid-at` in bodies, deferred and repeated negations) at six temporal settings with each body form forced and reordering on and off, in memory and on file before and after checkpoints, against the executor; and check the form the planner picks, routing, multiplicity, failing expressions and unknown predicates in bodies, and that a hashed body is read once while a correlated one probes once per outer row. Optimizer unit tests cover `plan_seeded` and the `SUBPLANS` switch. +- **Plan independence** (`tests/plan_independence_test.rs`, 12 tests, `test-oracle` feature only; #596): a matrix of queries (joins in both text orders, cross products, keyword and ref, floats, long strings, filter and binding expressions, recursive rules and rules with `not`, `or`/`or-join` including the #250 short-circuit shapes, placed and deferred `not`/`not-join`, aggregates, `:as-of`, `:valid-at`, `:any-valid-time`), in memory and on file after a checkpoint and a reopen, through `execute` and a cursor, gives the same bag of rows with clause reordering on and off (`minigraf::__reorder`) and with the engine's negation bodies chosen, forced hashed and forced correlated (`minigraf::__subplans`, #546; the matrix gains #546's negation shapes); #596's example and the unification cases (an expression whose output is its input, two expressions on one variable, integer vs float, `-0.0` vs `0.0`); and `or` / `or-join` branches whose expressions read or bind from a variable only the outer row binds, nested and in rule bodies (#620). Under `test-oracle` the model-based and property tests also rerun every generated query with reordering off (the property test also with negation bodies forced hashed). Unit tests cover `branch_outer_reads` (#620), `apply_expr` (equal, different, integer vs float, NaN, `-0.0`/`0.0` with and without replacing, keyword vs ref both ways, a failing expression), `Binders::expression`, the switch (source order kept, per thread, restored on drop), and the engine planner's `Bind` modes and build side with the switch off; the engine's join matrix gains six unification shapes. - **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. diff --git a/docs/superpowers/plans/2026-10-18-546-negation-disjunction.md b/docs/superpowers/plans/2026-10-18-546-negation-disjunction.md new file mode 100644 index 0000000000..b539d087a0 --- /dev/null +++ b/docs/superpowers/plans/2026-10-18-546-negation-disjunction.md @@ -0,0 +1,230 @@ +# Negation and disjunction on the streaming engine (#546) — Plan + +Spec: `docs/superpowers/specs/2026-10-16-negation-disjunction-engine-design.md`. PRs target +`v3`. Neither uses a closing keyword for #473; #546 closes by hand after PR 2. + +| PR | Steps | Branch | +|---|---|---| +| 1 | 1–9: one comparison rule in `not` bodies, sub-plans, `AntiJoin` | `feat/546-not` | +| 2 | 10–15: `or`/`or-join` on the engine, `Union`, `Distinct` | `feat/546-or` | + +Each PR leaves `v3` with no unused code, updates the test counts and `CHANGELOG.md` for +what it ships, and has a docs-site PR (`../minigraf-docs`). + +## Already done + +- Spec §3.4 on the executor: #615 (PR #616) and #617 (PR #619) made every executor path + bind the query's valid time for `:db/valid-at` in bodies, branches and rule + definitions; the CHANGELOG entries exist. §3.6 item 2 needs no new entry. PR 1 only + builds body plans with the query's `as_of` and `Valid`. +- #620 (PR #622): an `or` branch whose expression reads an outer variable is seeded + (`branch_outer_reads`). PR 2's correlated branches cover that shape on the engine. + +## Where the executor substitutes imported values today + +Spec §3.1 needs every comparison of an imported value to use join equality. Four places +substitute the outer value into the body as a literal (`substitute_pattern` / +`substitute_value`), so a float matches within `f64::EPSILON`: + +| Place | Path | +|---|---| +| `executor::not_body_matches` | `not` per-row path (bodies with an expression or pseudo-attribute; `evaluate_branch`) | +| `executor::not_clause_violated_via_rules` | `not` in a query that invokes a rule | +| `evaluator::evaluate_not_join` | every `not-join` per-row path, rule or not | +| `StratifiedEvaluator` negation loop (`evaluator.rs`, `'binding:` loop) | `not` in a rule body | + +The exclusion-set paths (`apply_not_clause`, `apply_not_join_clause`) already compare +`normalize_value` keys, which is join equality (`Value`'s `Eq`/`Hash` treat `-0.0` as +`0.0` and NaN as equal to nothing, #545). + +## Design decisions not fixed by the spec + +1. **The executor seeds instead of substituting.** One helper, + `executor::body_rows(body, seed: Binding, matcher) -> Vec`: the body's + patterns (and rule invocations, through `rule_invocation_to_pattern`, unsubstituted) + are matched with `match_patterns_seeded(patterns, vec![seed])`, then its expressions + applied. `seed` holds the imported values only: the body's variables bound in the + outer row for `not`, the join variables for `not-join` (hidden metadata variables + are already join variables, #594). The matcher joins a seeded variable through its + hash path, keyed by `normalize_join_value`, so the comparison is join equality. The + four places above call it; `substitute_pattern` stays for prepared queries and + magic sets. The merge-the-outer-row-afterwards step goes, since the seed is already + in every body row. +2. **Sub-plans start from a seed.** `plan.rs` splits into `plan(query)` and + `plan_clauses(clauses, Start, …) -> Option`, where `Start` is either + nothing (the first pattern is a `Scan`, as today) or a seed: imported variables + given slots `0..k` with their outer `Slots::kinds` (spec §4.5). With a seed, every + pattern is a `Join`; the first one's outer side is the seed, so it is an + `IndexNestedLoopJoin` when its entity is imported and otherwise a `HashJoin` built on + the seed (`build_inner = false`). `Plan` gets `source: Source` (`Scan(ScanSpec)` or + `Seed(width)`) in place of `scan`. +3. **One new leaf and one new trait method.** `Seed`: a leaf that returns one row (the + imported cells) and ends. `Operator::rewind(&mut self, seed: &[Cell])`: start again + from the beginning, reopening a closed operator; it passes `seed` down the outer + (left) spine to the `Seed`; a join's inner `Scan` restarts without it. `Scan` keeps + its resolved constants across rewinds. Every operator implements it; only correlated + sub-plans call it. +4. **One body abstraction, used by `not` now and `or` in PR 2.** `engine/sub.rs`: + - `Correlated { root: Box, imports: Vec }`: `imports` are the + outer slots copied into the seed, in seed order. `first(row) -> bool` rewinds with + the seed, pulls one batch, closes; `rows(row)` (PR 2) yields every body row. + - `Hashed { root, keys: Vec, set or table }`: the body's standalone plan, run + once on the first use, its rows keyed by the imported variables it binds + (`JoinKey`, `Key::normalise` as a join's; a row with a NaN key cell is skipped). A + rewind of the enclosing tree keeps the set: a closed body does not depend on the + outer row. +5. **`AntiJoin` is one operator over either body.** `engine/anti.rs`: pulls an outer + batch, keeps the rows whose body is empty (`Correlated::first` is false, or the key + is absent from `Hashed`'s set; an empty key with a non-empty set removes every row, + spec §4.2 step 3). It never deduplicates. Counters: its own, then the body's, then + the outer side's. +6. **Closed.** `plan::closed(body)`: every variable read by an expression or a + pseudo-attribute pattern (its `pseudo_source`) is bound by a stored-attribute + pattern of the body. A body with no stored-attribute pattern is never hashed (there + is nothing to scan once). +7. **Hash or correlated (spec §4.4).** Correlated when the body is not closed, has no + stored-attribute pattern, or its first pattern in `optimizer::plan_seeded` order has an + imported entity; hashed otherwise. Deviation from spec §4.4: a first pattern with a + *constant* entity (and no imported one) is hashed, not correlated. Such a body reads + one entity range whatever the outer row, so reading it once and holding its few rows + is cheaper than probing the same range for every outer row. A test switch beside `REORDER`, + `optimizer::SUBPLANS` (`Option`, `None` = choose), forces one or the other, + with `minigraf::__subplans(Mode) -> SubplanGuard` under `test-oracle` only. Forcing + `Hash` on a body that cannot be hashed (not closed, or no pattern) leaves it + correlated: the switch tests the choice, not shapes only one form runs. +8. **Body order counts imported variables as bound.** `optimizer::plan` scores an + imported entity as a variable, so a body such as `[?x :a ?y] [?e :b ?x]` with `?e` + imported could start with the unprobed pattern. `optimizer::plan_seeded(clauses, + bound: &HashSet)` scores a bound variable as a constant; `plan(c)` is + `plan_seeded(c, &empty)`. Under the test switch off it keeps text order, as `plan` + does. Cost only: answers do not depend on it (the differential test checks). +9. **Placement.** The engine runs `optimizer::plan`'s clauses in its order, then the + deferred `not`s (sorted by `clause_cost` when reordering), as + `execute_query_on_executor` does. A `not` with no required variable, which `plan` + puts first, runs right after the first pattern instead: it reads nothing from the + row, so its place does not change the rows (the engine has no row before the first + pattern). +10. **Body binders.** Expressions in a body bind with `Out::New` for a body variable and + `Out::Check` for an imported or already-bound one; body joins replace nothing + (`JoinSpec::replace` empty). For a `not`, only whether a row exists matters, so + replacing a cell could not change an answer; this matches the executor, whose body + paths pass `replace = false`. + +## Steps + +### 1. Executor: seeded bodies (PR 1) +- `body_rows` (decision 1) in the four places of the table. `evaluate_not_join` keeps its + signature (the evaluator and executor both call it). +- Unit tests: a float imported into each path matches by IEEE `==` (`1e-20` vs `2e-20` + no longer equal; `0.0` vs `-0.0` equal); NaN matches nothing; a keyword imported into + an entity position equals the ref; a body constant float still matches within + `f64::EPSILON`. + +### 2. Answer-change tests (PR 1) +- `tests/negation_equality_test.rs`: spec §3.6 item 1's two queries both return `:e1`, + on `execute` and on the cursor, in memory and after a checkpoint; the same for `not` + (body with and without an expression), a rule query's `not`, and a rule body's `not`. + +### 3. `optimizer::plan_seeded` and the switch (PR 1) +- Decisions 7 and 8. Unit tests: an imported entity sorts first; text order with + `REORDER` off; `SUBPLANS` is per thread and restored by the guard. + +### 4. Sub-plans (PR 1) +- Decision 2: `Source`, `plan_clauses`, `Seed` (decision 3) in `engine/seed.rs`, and + `rewind` on `Scan`, `Join`, `Apply`. +- `engine/tests.rs`: a seeded plan with an imported entity probes (counter + `IndexNestedLoopJoin`, `rows_in` per seed); rewinding a scan after `close` reads + again; a seeded `HashJoin` builds on the seed. + +### 5. `AntiJoin` (PR 1) +- `engine/sub.rs` (decision 4, `Correlated::first` and `Hashed` set only; `rows` and the + table come in PR 2), `engine/anti.rs` (decision 5), `Step::Anti(AntiSpec)`, and + `plan` accepting `Not`/`NotJoin` (decisions 6, 9, 10). Queries holding `or`/`or-join` + still return `None`. +- Module docs: `engine/mod.rs`, `plan.rs` (no longer "patterns and expression clauses"). + +### 6. Tests (PR 1) +- Routing (`RUNS`): `not`, `not-join`, deferred `not`, `not` with no required variable, + pseudo-attribute and `:db/valid-at` bodies run on the engine; a body with a rule + invocation does not; a query with `or` does not. +- `engine/tests.rs`: hashed vs correlated choice per decision 7 (counters name the + operators); empty key removes every row; NaN outer value kept; multiplicity kept + (duplicate outer rows both survive); a failing expression in a body keeps the row + (spec §3.3), including an unknown predicate. +- `tests/plan_independence_test.rs`: the spec §6 negation matrix (floats near zero, + `-0.0`, NaN, keywords and refs to the same entities, `:db/valid-at` and per-fact + pseudo-attributes in bodies, placed and deferred), each run with reordering on/off × + `SUBPLANS` hash/correlated/choose; all must be the same bag. +- `tests/property_test.rs`: generated queries gain `not` and `not-join` bodies over the + existing schema (the rerun with the switches off covers them). +- Existing tests that pinned the old float matching in bodies: each change listed in the + PR body. + +### 7. Measurement (PR 1) +- `examples/perf_envelope.rs`: `not_probe` (`[?e :name ?n] (not [?e :banned true])`, + correlated) and `not_join_hash` (`[?e :score ?s] (not-join [?s] [?b :blocked ?s])`, + hashed). On the bench machine, idle: 100K, 1M, 10M against `v3` before the PR; no + existing workload regresses. Binary size (`binary-size.yml`). + +### 8. PR 1 checks and docs +- `CHANGELOG.md` (v3.0.0): Breaking, spec §3.6 item 1 with its example; Internal, the + engine runs `not`/`not-join` (`AntiJoin`, sub-plans). +- `cargo fmt`; clippy native, `--features wasm`, `browser`/wasm32; `cargo test`; + `cargo test --features test-oracle`; fuzz crate `cargo check` if `reference_model` + changes. +- Test counts: `CLAUDE.md`, `docs/TEST_COVERAGE.md`, `README.md`; `CLAUDE.md` module list + (engine `seed.rs`, `sub.rs`, `anti.rs`; `plan.rs` scope; `optimizer.rs` + `plan_seeded`/`SUBPLANS`). +- Docs site: `content/datalog-reference.md` (comparison inside `not`, `@since v3.0.0` / + `@until v3.0.0`), `content/architecture.md` (engine operators). +- Codex review; comment on #546 with the PR 1 summary. + +### 9. Before PR 2 +- Record in the PR 1 body any shape the differential test found that the spec does not + cover; file it as its own issue (v3.0.0) unless PR 1 fixes it. + +### 10. Executor: `or` by join equality (PR 2) +- `apply_or_clauses` fast path: the hash join of branch rows onto incoming rows keys on + `normalize_join_value` for `or` and `or-join` (spec §5.3). The dedup keys (`seen`, + `seen_keys`, `seen_result`, `seen_proj`) stay exact `Value` keys (spec §5.2). +- Answer-change tests (spec §3.6 item 3): a keyword in a branch meets a ref outside, in + both paths (with and without a `not` in the branch). + +### 11. `Union` and `Distinct` (PR 2) +- `Correlated::rows` and `Hashed`'s table of new cells (decision 4). +- `engine/union.rs`: per outer row, every branch's merged rows (outer row, then the + branch's new slots); a closed branch by `Hashed` lookup, the others `Correlated`. + Imported variables per spec §2 (every outer variable for `or`, join variables for + `or-join`, hidden metadata variables). The parser requires every `or` branch to bind + the same new variables (`same set of new variables`), so every branch fills the same + slots; `or-join` adds none. +- `engine/distinct.rs`: a hash set of rows keyed by `JoinKey::of(cell, false)` per slot, + NaN never equal (so such rows are kept), as the executor's `Value` keys behave. +- `plan`: `Or`/`OrJoin` after every pattern, expression and placed `not`, before the + deferred `not`s, in text order (spec §5.1); a branch holding a rule invocation keeps + the query on the executor. Closed for a branch: decision 6, plus every variable a + nested `not`, `or` or `or-join` needs from outside is bound by the branch. +- The #250 early stop is not reproduced: it is an executor optimisation. + +### 12. Tests (PR 2) +- Routing for `or`/`or-join` (and nested `not`/`or` in branches); disjunction matrix in + `tests/plan_independence_test.rs` with reordering and `SUBPLANS` both ways; Distinct + collapses duplicate outer rows; property-test `or`/`or-join` branches. + +### 13. Measurement (PR 2) +- `or_2` workload (two closed branches over different attributes); 100K, 1M, 10M against + `v3` after PR 1. + +### 14. PR 2 checks and docs +- As step 8, plus `CHANGELOG.md` §3.6 item 3; docs site `content/datalog-reference.md` + (`or` comparison), `content/architecture.md` (`Union`, `Distinct`). +- Codex review; close #546 by hand after merge; check off the #546 boxes. + +### 15. After #546 +- `docs/superpowers/specs/2026-10-11-streaming-engine-design.md` stays as written (spec + §9 lists the deviations). Next sub-issue of #473: #547. + +## Bindings + +No public API or error code changes; `minigraf::__subplans` exists only under the +`test-oracle` feature. No binding cascade. diff --git a/examples/perf_envelope.rs b/examples/perf_envelope.rs index 71c9c56081..9622c413c9 100644 --- a/examples/perf_envelope.rs +++ b/examples/perf_envelope.rs @@ -496,6 +496,28 @@ fn shapes(e: usize, tx_half: u64, hot_tx_half: u64) -> Vec { ), rows: 1, }, + // #546: a `not` probed once per outer row (its entity is imported). + Shape { + name: "not_probe", + query: "[:find ?e :where [?e :group 7] (not [?e :age 7])]".into(), + rows: (0..e).filter(|i| i % 100 == 7 && i % 90 != 7).count(), + }, + // #546: a closed `not-join` keyed on a value: its body read once. + Shape { + name: "not_join_hash", + query: "[:find ?e :where [?e :group 7] [?e :age ?a] \ + (not-join [?a] [?f :group 17] [?f :age ?a] [(< ?a 50)])]" + .into(), + rows: { + let ages: std::collections::HashSet = (0..e) + .filter(|i| i % 100 == 17 && i % 90 < 50) + .map(|i| i % 90) + .collect(); + (0..e) + .filter(|i| i % 100 == 7 && !ages.contains(&(i % 90))) + .count() + }, + }, Shape { name: "recursive_ancestors", query: format!("[:find ?b :where (boss :p{leaf} ?b)]"), diff --git a/src/lib.rs b/src/lib.rs index cbb4ebef02..bf8ab9e015 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -134,3 +134,18 @@ pub use query::datalog::optimizer::ReorderGuard; pub fn __reorder(on: bool) -> ReorderGuard { query::datalog::optimizer::set_reorder(on) } + +// Plan-independence tests (#546): force how negation bodies run. +#[cfg(feature = "test-oracle")] +#[doc(hidden)] +pub use query::datalog::optimizer::{Subplans, SubplansGuard}; + +/// Forces how the streaming engine runs `not` / `not-join` bodies (hashed or +/// correlated) on this thread until the returned guard drops. Only for tests +/// that check both forms give the same rows (#546); built with the +/// `test-oracle` feature only. +#[cfg(feature = "test-oracle")] +#[doc(hidden)] +pub fn __subplans(mode: Subplans) -> SubplansGuard { + query::datalog::optimizer::set_subplans(mode) +} diff --git a/src/query/datalog/evaluator.rs b/src/query/datalog/evaluator.rs index 1efe404be0..31e0cb2973 100644 --- a/src/query/datalog/evaluator.rs +++ b/src/query/datalog/evaluator.rs @@ -26,7 +26,7 @@ use super::functions::FunctionRegistry; use super::matcher::{Bindings, PatternMatcher, edn_to_entity_id, edn_to_value}; use super::rules::RuleRegistry; -use super::types::{AttributeSpec, EdnValue, Pattern, Rule, ValidAt, WhereClause}; +use super::types::{EdnValue, Pattern, Rule, ValidAt, WhereClause}; use crate::error::{ErrorCode, err_coded}; use crate::graph::FactStorage; use crate::graph::types::{Fact, Value}; @@ -443,36 +443,6 @@ pub fn value_to_edn(value: &Value) -> EdnValue { } } -/// Substitute bound variables in a Pattern, returning a new Pattern with concrete values. -pub fn substitute_pattern(pattern: &Pattern, binding: &Bindings) -> Pattern { - let attribute = match &pattern.attribute { - AttributeSpec::Real(edn) => AttributeSpec::Real(substitute_value(edn, binding)), - AttributeSpec::Pseudo(p) => AttributeSpec::Pseudo(p.clone()), - }; - Pattern { - entity: substitute_value(&pattern.entity, binding), - attribute, - value: substitute_value(&pattern.value, binding), - pseudo_source: pattern - .pseudo_source - .as_ref() - .map(|v| substitute_value(v, binding)), - ..pattern.clone() - } -} - -/// Substitute a single value: if it's a bound variable, replace it; otherwise clone. -pub fn substitute_value(value: &EdnValue, binding: &Bindings) -> EdnValue { - if let Some(var) = value.as_variable() { - binding - .get(var) - .map(value_to_edn) - .unwrap_or_else(|| value.clone()) - } else { - value.clone() - } -} - /// Convert a predicate name + argument list to a Pattern. /// /// 1-arg: `(blocked ?x)` → `[?x :blocked ?_rule_value]` @@ -507,20 +477,52 @@ pub(crate) fn rule_invocation_to_pattern(predicate: &str, args: &[EdnValue]) -> } } +/// The outer row's values of the variables a `not` body imports: every +/// variable the body names, `?_` ones aside (spec §2 of the #546 design). +pub(crate) fn not_seed(body: &[WhereClause], outer: &Bindings) -> Bindings { + crate::query::datalog::optimizer::clause_ref_vars(body) + .into_iter() + .filter(|v| !v.starts_with("?_")) + .filter_map(|v| outer.get(&v).map(|val| (v, val.clone()))) + .collect() +} + +/// The rows of a negation body's patterns and rule invocations, matched from +/// `seed`, the outer row's values of the variables the body imports. A seeded +/// variable is compared as a join compares it (`normalize_join_value`: floats +/// by IEEE `==`, a keyword equal to a ref to the entity it names), never +/// substituted as a literal (#546). Every row carries the seed; the caller +/// applies the body's expressions. +pub(crate) fn seeded_body_rows( + body: &[WhereClause], + seed: Bindings, + storage: Arc<[Fact]>, + valid_at: Value, +) -> Vec { + let patterns: Vec = body + .iter() + .filter_map(|c| match c { + WhereClause::Pattern(p) => Some(p.clone()), + // Rule-derived facts are already in `storage` (accumulated) from + // lower strata. + WhereClause::RuleInvocation { predicate, args } => { + rule_invocation_to_pattern(predicate, args).ok() + } + _ => None, + }) + .collect(); + PatternMatcher::from_slice_with_valid_at(storage, valid_at) + .match_patterns_seeded(&patterns, vec![seed]) +} + /// Test whether a `not-join` body is satisfiable given a current binding. /// /// Returns `true` if the body IS satisfiable → outer binding should be **rejected**. /// Returns `false` if the body cannot be satisfied → outer binding survives. /// -/// Algorithm: -/// 1. Build a partial binding containing only the join_vars entries. -/// 2. For each clause: -/// - Pattern → substitute join_vars via substitute_pattern. -/// - RuleInvocation → convert to Pattern via rule_invocation_to_pattern, then substitute. -/// Rule-derived facts are already present in `storage` (accumulated) from lower strata. -/// 3. Run PatternMatcher::match_patterns on all resulting patterns against `storage`, -/// with `valid_at` as the value a `:db/valid-at` pattern binds (#615). -/// 4. Any complete match → body is satisfiable → return true (reject outer binding). +/// The body is matched from the binding's join variables ([`seeded_body_rows`]), +/// with `valid_at` as the value a `:db/valid-at` pattern binds (#615), and its +/// expressions applied; any row left means the body is satisfiable. pub fn evaluate_not_join( join_vars: &[String], clauses: &[WhereClause], @@ -529,52 +531,16 @@ pub fn evaluate_not_join( valid_at: Value, functions: &FunctionRegistry, ) -> bool { - // Build a partial binding containing only the join variables - let partial: Bindings = join_vars + let seed: Bindings = join_vars .iter() .filter_map(|v| binding.get(v.as_str()).map(|val| (v.clone(), val.clone()))) .collect(); - - // Convert Pattern and RuleInvocation clauses to patterns (excluding Expr) - let substituted: Vec = clauses - .iter() - .filter_map(|c| match c { - WhereClause::Pattern(p) => Some(substitute_pattern(p, &partial)), - WhereClause::RuleInvocation { predicate, args } => { - rule_invocation_to_pattern(predicate, args) - .ok() - .map(|p| substitute_pattern(&p, &partial)) - } - _ => None, - }) - .collect(); - - // Collect Expr clauses from the not-join body let expr_clauses: Vec<&WhereClause> = clauses .iter() .filter(|c| matches!(c, WhereClause::Expr { .. })) .collect(); - - let matcher = PatternMatcher::from_slice_with_valid_at(storage.clone(), valid_at); - 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()] - } else { - matcher - .match_patterns(&substituted) - .into_iter() - .map(|mut nb| { - for (k, v) in &partial { - nb.entry(k.clone()).or_insert_with(|| v.clone()); - } - nb - }) - .collect() - }; - - // Apply Expr clauses to filter not_bindings - not_bindings = apply_expr_clauses_in_evaluator(not_bindings, &expr_clauses, functions); - !not_bindings.is_empty() + let rows = seeded_body_rows(clauses, seed, storage, valid_at); + !apply_expr_clauses_in_evaluator(rows, &expr_clauses, functions).is_empty() } // NOTE: This mirrors apply_expr_clauses in executor.rs but uses the evaluator's @@ -938,59 +904,12 @@ impl StratifiedEvaluator { 'binding: for binding in candidates { for not_body in ¬_clauses { - let substituted: Vec = not_body - .iter() - .filter_map(|c| match c { - WhereClause::Pattern(p) => Some(substitute_pattern(p, &binding)), - WhereClause::RuleInvocation { predicate, args } => { - let subst_args: Vec = args - .iter() - .map(|a| substitute_value(a, &binding)) - .collect(); - match subst_args.len() { - 1 => subst_args.first().map(|a0| { - Pattern::new( - a0.clone(), - EdnValue::Keyword(format!(":{}", predicate)), - EdnValue::Symbol("?_rule_value".to_string()), - ) - }), - 2 => subst_args.first().and_then(|a0| { - subst_args.get(1).map(|a1| { - Pattern::new( - a0.clone(), - EdnValue::Keyword(format!(":{}", predicate)), - a1.clone(), - ) - }) - }), - _ => None, - } - } - WhereClause::Not(_) | WhereClause::NotJoin { .. } => None, - WhereClause::Expr { .. } => None, - WhereClause::Or(_) | WhereClause::OrJoin { .. } => None, // Or/OrJoin inside not bodies: rejected at parse time (see parser.rs). - }) - .collect(); - - let not_matcher = PatternMatcher::from_slice_with_valid_at( + let not_bindings = seeded_body_rows( + not_body, + not_seed(not_body, &binding), accumulated_facts.clone(), self.valid_at.clone(), ); - let mut not_bindings: Vec = if substituted.is_empty() { - vec![binding.clone()] - } else { - not_matcher - .match_patterns(&substituted) - .into_iter() - .map(|mut nb| { - for (k, v) in &binding { - nb.entry(k.clone()).or_insert_with(|| v.clone()); - } - nb - }) - .collect() - }; // Apply Expr clauses from the not body let not_body_expr_clauses: Vec<&WhereClause> = not_body @@ -1001,7 +920,7 @@ impl StratifiedEvaluator { .functions .read() .map_err(|_| err_coded!(ErrorCode::Qry008))?; - not_bindings = apply_expr_clauses_in_evaluator( + let not_bindings = apply_expr_clauses_in_evaluator( not_bindings, ¬_body_expr_clauses, &fn_guard, diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index a676cbb329..28133fb3bc 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -1081,6 +1081,9 @@ fn normalize_value(v: &Value) -> Value { /// Evaluate a `not` body against the current outer binding. /// /// Returns true if the body "matches" (i.e., the outer binding should be excluded). +/// The body is matched from the outer values of the variables it names +/// (`seeded_body_rows`, #546). Rule invocations in it match the rule-derived +/// facts `storage` holds on the rules path. fn not_body_matches( not_body: &[WhereClause], outer: &Binding, @@ -1088,47 +1091,13 @@ fn not_body_matches( valid_at: Value, registry: &FunctionRegistry, ) -> bool { - use crate::query::datalog::evaluator::substitute_pattern; - - let patterns: Vec<_> = not_body - .iter() - .filter_map(|c| match c { - WhereClause::Pattern(p) => Some(substitute_pattern(p, outer)), - // INVARIANT: not_body_matches is only called from execute_query, which is - // only reached when query.uses_rules() is false. uses_rules() descends into - // Not bodies via rule_invocations(), so any not body containing a - // RuleInvocation is routed to execute_query_with_rules instead. - // WhereClause::Expr clauses are handled by apply_expr_clauses below. - _ => None, - }) - .collect(); - - let matcher = crate::query::datalog::matcher::PatternMatcher::from_slice_with_valid_at( - storage.clone(), - valid_at, - ); - let mut not_bindings: Vec = if patterns.is_empty() { - // Expr-only not body: start with the outer binding so variables resolve. - vec![outer.clone()] - } else { - // Merge outer binding with pattern-match results. - matcher - .match_patterns(&patterns) - .into_iter() - .map(|mut nb| { - for (k, v) in outer { - nb.entry(k.clone()).or_insert_with(|| v.clone()); - } - nb - }) - .collect() - }; - - // Apply Expr clauses from the not body. + use crate::query::datalog::evaluator::{not_seed, seeded_body_rows}; + let rows = seeded_body_rows(not_body, not_seed(not_body, outer), storage, valid_at); // Errors (e.g. unknown UDF predicate) are treated as "no match" — same as an // empty result — so the outer row is kept (not-condition not violated). - not_bindings = apply_expr_clauses(not_bindings, not_body, registry).unwrap_or_default(); - !not_bindings.is_empty() + !apply_expr_clauses(rows, not_body, registry) + .unwrap_or_default() + .is_empty() } /// Filter `bindings` through a single `(not ...)` body, for the rule-free query path @@ -1324,98 +1293,8 @@ fn apply_not_join_clause( .collect() } -/// Returns true if `not_body` is satisfied against `binding` (i.e. the outer binding -/// should be excluded) — for the rules query path (`execute_query_with_rules`), where -/// a `not` body may contain `WhereClause::RuleInvocation` against `derived_facts` -/// (all referenced rules are pre-evaluated by the `StratifiedEvaluator` before this -/// runs). No exclusion-set precomputation here: rule-invocation args are resolved -/// per binding, same as the pre-#248 post-filter. -fn not_clause_violated_via_rules( - not_body: &[WhereClause], - binding: &Binding, - derived_facts: Arc<[Fact]>, - valid_at_value: Value, - registry: &FunctionRegistry, -) -> bool { - use crate::query::datalog::evaluator::substitute_pattern; - - let substituted: Vec = not_body - .iter() - .filter_map(|c| match c { - WhereClause::Pattern(p) => Some(substitute_pattern(p, binding)), - WhereClause::RuleInvocation { predicate, args } => { - // Convert rule invocation to a pattern against derived storage. - // Apply the current binding to any variables in args first. - let resolved_args: Vec = args - .iter() - .map(|a| match a { - EdnValue::Symbol(s) if s.starts_with('?') => { - // Look up the bound value and convert back to EdnValue - binding - .get(s) - .map(|v| match v { - Value::Keyword(k) => EdnValue::Keyword(k.clone()), - Value::String(s) => EdnValue::String(s.clone()), - Value::Integer(i) => EdnValue::Integer(*i), - Value::Float(f) => EdnValue::Float(*f), - Value::Boolean(b) => EdnValue::Boolean(*b), - Value::Ref(u) => EdnValue::Uuid(*u), - Value::Null => EdnValue::Nil, - }) - .unwrap_or_else(|| a.clone()) - } - other => other.clone(), - }) - .collect(); - // Safety: match arms guarantee len()==1 or len()==2. - let pattern = match resolved_args.len() { - 1 => { - #[allow(clippy::indexing_slicing)] - let entity = resolved_args[0].clone(); - Pattern::new( - entity, - EdnValue::Keyword(format!(":{}", predicate)), - EdnValue::Symbol("?_rule_value".to_string()), - ) - } - 2 => { - #[allow(clippy::indexing_slicing)] - let entity = resolved_args[0].clone(); - #[allow(clippy::indexing_slicing)] - let value = resolved_args[1].clone(); - Pattern::new(entity, EdnValue::Keyword(format!(":{}", predicate)), value) - } - _ => return None, - }; - Some(substitute_pattern(&pattern, binding)) - } - _ => None, - }) - .collect(); - - let m = PatternMatcher::from_slice_with_valid_at(derived_facts.clone(), valid_at_value); - let mut not_bindings: Vec = if substituted.is_empty() { - vec![binding.clone()] - } else { - m.match_patterns(&substituted) - .into_iter() - .map(|mut nb| { - for (k, v) in binding { - nb.entry(k.clone()).or_insert_with(|| v.clone()); - } - nb - }) - .collect() - }; - - // Apply Expr clauses from the not body. Errors (e.g. unknown UDF predicate) are - // treated as "no match" so the outer row is kept (not-condition not violated). - not_bindings = apply_expr_clauses(not_bindings, not_body, registry).unwrap_or_default(); - !not_bindings.is_empty() -} - -/// Filter `bindings` through a single `(not ...)` body for the rules query path. -/// See [`not_clause_violated_via_rules`]. +/// Filter `bindings` through a single `(not ...)` body for the rules query path, +/// where rule invocations in the body match `derived_facts`. fn apply_not_clause_derived( bindings: Vec, not_body: &[WhereClause], @@ -1426,7 +1305,7 @@ fn apply_not_clause_derived( bindings .into_iter() .filter(|b| { - !not_clause_violated_via_rules( + !not_body_matches( not_body, b, derived_facts.clone(), diff --git a/src/query/datalog/optimizer.rs b/src/query/datalog/optimizer.rs index d2ddf8ee29..b7a75fb7d7 100644 --- a/src/query/datalog/optimizer.rs +++ b/src/query/datalog/optimizer.rs @@ -47,6 +47,58 @@ impl Drop for ReorderGuard { } } +/// How the engine runs a `not` / `not-join` body (#546): the planner's +/// choice, or one form forced by a test. +#[derive(Clone, Copy, Debug, PartialEq, Eq)] +#[cfg_attr( + not(any(test, feature = "test-oracle")), + allow(dead_code, reason = "only tests force a form") +)] +pub enum Subplans { + /// Hashed when the body allows it and no probe is cheaper (spec §4.4). + Choose, + /// Hashed whenever the body allows it. + Hash, + /// Always correlated: run once per outer row. + Correlated, +} + +#[cfg(any(test, feature = "test-oracle"))] +thread_local! { + /// How bodies on this thread run; tests only. + static SUBPLANS: std::cell::Cell = const { std::cell::Cell::new(Subplans::Choose) }; +} + +/// How the engine runs a negation body: [`Subplans::Choose`], except in +/// tests while this thread forces a form ([`set_subplans`]). Both forms give +/// the same rows. +#[inline] +pub(crate) fn subplans() -> Subplans { + #[cfg(any(test, feature = "test-oracle"))] + return SUBPLANS.with(std::cell::Cell::get); + #[cfg(not(any(test, feature = "test-oracle")))] + Subplans::Choose +} + +/// Forces how bodies run on this thread until the guard drops, which +/// restores the previous setting. +#[cfg(any(test, feature = "test-oracle"))] +pub(crate) fn set_subplans(mode: Subplans) -> SubplansGuard { + SubplansGuard(SUBPLANS.with(|s| s.replace(mode))) +} + +/// Restores the previous [`set_subplans`] setting on drop. +#[cfg(any(test, feature = "test-oracle"))] +#[must_use = "the setting is restored when the guard drops"] +pub struct SubplansGuard(Subplans); + +#[cfg(any(test, feature = "test-oracle"))] +impl Drop for SubplansGuard { + fn drop(&mut self) { + SUBPLANS.with(|s| s.set(self.0)); + } +} + /// Which covering index to use for a given pattern. #[derive(Debug, Clone, PartialEq, Eq)] pub enum IndexHint { @@ -79,13 +131,17 @@ fn attr_is_index_bound(a: &AttributeSpec) -> bool { } } -/// Count the number of non-variable components in a pattern. -/// Higher score = more selective. -/// -fn selectivity_score(p: &Pattern) -> u8 { - let e = !is_variable(&p.entity); - let a = attr_is_index_bound(&p.attribute); - let v = !is_variable(&p.value); +/// Count the components of a pattern that are constants or variables in +/// `bound`. Higher score = more selective. +fn selectivity_score(p: &Pattern, bound: &std::collections::HashSet) -> u8 { + let fixed = + |v: &EdnValue| !is_variable(v) || v.as_variable().is_some_and(|n| bound.contains(n)); + let e = fixed(&p.entity); + let a = match &p.attribute { + AttributeSpec::Real(edn) => fixed(edn), + AttributeSpec::Pseudo(_) => false, + }; + let v = fixed(&p.value); (e as u8).saturating_add(a as u8).saturating_add(v as u8) } @@ -162,7 +218,7 @@ pub(crate) fn pattern_bound_vars(p: &Pattern) -> Vec { /// clauses — used to determine a `Not`/`NotJoin` clause's dependency on preceding /// bindings. Walks `Pattern` positions, `Expr` trees (+ output binding), nested /// `Not`/`NotJoin` bodies, and `RuleInvocation` arguments. -fn clause_ref_vars(clauses: &[WhereClause]) -> std::collections::HashSet { +pub(crate) fn clause_ref_vars(clauses: &[WhereClause]) -> std::collections::HashSet { let mut vars = std::collections::HashSet::new(); for clause in clauses { match clause { @@ -210,6 +266,17 @@ fn clause_ref_vars(clauses: &[WhereClause]) -> std::collections::HashSet /// `Some(hint)` and each Expr/Not/NotJoin with `None`. pub fn plan( clauses: Vec, +) -> (Vec<(WhereClause, Option)>, Vec) { + plan_seeded(clauses, &Default::default()) +} + +/// [`plan`] for a body whose variables in `seeded` come bound from the outer +/// row (#546): they count as constants for selectivity, and a clause that +/// reads only them may run before every pattern. Cost only: no answer +/// depends on the order. +pub(crate) fn plan_seeded( + clauses: Vec, + seeded: &std::collections::HashSet, ) -> (Vec<(WhereClause, Option)>, Vec) { // Separate into patterns (with hints), exprs, and not/not-join clauses. let mut patterns: Vec<(WhereClause, IndexHint)> = Vec::new(); @@ -238,7 +305,7 @@ pub fn plan( if reorder() { patterns.sort_by_key(|(clause, _)| { if let WhereClause::Pattern(p) = clause { - std::cmp::Reverse(selectivity_score(p)) + std::cmp::Reverse(selectivity_score(p, seeded)) } else { std::cmp::Reverse(0u8) } @@ -275,9 +342,13 @@ pub fn plan( required.insert(v.clone()); } let hint = select_index(p); - let mut bound: std::collections::HashSet = Default::default(); + let mut bound = seeded.clone(); let mut insert_pos = result.len(); for (pos, (c, _)) in result.iter().enumerate() { + if required.is_subset(&bound) { + insert_pos = pos; + break; + } if let WhereClause::Pattern(q) = c { bound.extend(pattern_bound_vars(q)); if required.is_subset(&bound) { @@ -298,11 +369,13 @@ pub fn plan( Default::default() }; - let mut bound: std::collections::HashSet = Default::default(); + let mut bound = seeded.clone(); // Default: append at end (covers no-var Exprs and vars never bound by any pattern). let mut insert_pos = result.len(); - if !vars.is_empty() { + if !vars.is_empty() && vars.is_subset(&bound) { + insert_pos = 0; + } else if !vars.is_empty() { for (pos, (clause, _)) in result.iter().enumerate() { if let WhereClause::Pattern(p) = clause { bound.extend(pattern_bound_vars(p)); @@ -352,9 +425,12 @@ pub fn plan( continue; } - let mut bound: std::collections::HashSet = Default::default(); - let mut insert_pos: Option = None; + let mut bound = seeded.clone(); + let mut insert_pos: Option = required.is_subset(&bound).then_some(0); for (pos, (clause, _)) in result.iter().enumerate() { + if insert_pos.is_some() { + break; + } if let WhereClause::Pattern(p) = clause { bound.extend(pattern_bound_vars(p)); if required.is_subset(&bound) { @@ -461,6 +537,58 @@ mod tests { EdnValue::Uuid(Uuid::new_v4()) } + #[test] + fn plan_seeded_counts_seeded_variables_as_bound() { + let body = vec![ + WhereClause::Pattern(make_pattern(var("x"), kw(":a"), var("y"))), + WhereClause::Pattern(make_pattern(var("e"), kw(":b"), var("x"))), + WhereClause::Expr { + expr: Expr::BinOp( + crate::query::datalog::types::BinOp::Gt, + Box::new(Expr::Var("?e".to_string())), + Box::new(Expr::Lit(crate::graph::types::Value::Integer(1))), + ), + binding: None, + }, + ]; + let first = |planned: &[(WhereClause, Option)]| -> Vec { + planned + .iter() + .map(|(c, _)| match c { + WhereClause::Pattern(p) => p.entity.as_variable().unwrap_or("").to_string(), + _ => "expr".to_string(), + }) + .collect() + }; + let (plain, _) = plan(body.clone()); + assert_eq!(first(&plain)[0], "?x"); + let seeded: std::collections::HashSet = ["?e".to_string()].into(); + let (planned, _) = plan_seeded(body.clone(), &seeded); + // The expression reads only the seed; the imported entity sorts first. + assert_eq!(first(&planned)[0], "expr"); + assert_eq!(first(&planned)[1], "?e"); + let _off = set_reorder(false); + let (planned, _) = plan_seeded(body, &seeded); + assert_eq!(first(&planned)[1], "?x", "text order"); + } + + #[test] + fn subplans_switch_is_per_thread_and_restored() { + assert_eq!(subplans(), Subplans::Choose); + { + let _h = set_subplans(Subplans::Hash); + assert_eq!(subplans(), Subplans::Hash); + // WASI has no threads. + #[cfg(not(target_arch = "wasm32"))] + std::thread::spawn(|| assert_eq!(subplans(), Subplans::Choose)) + .join() + .unwrap(); + let _c = set_subplans(Subplans::Correlated); + assert_eq!(subplans(), Subplans::Correlated); + } + assert_eq!(subplans(), Subplans::Choose); + } + #[test] fn test_entity_bound_selects_eavt() { let p = make_pattern(entity_lit(), var("a"), var("v")); diff --git a/src/query/engine/anti.rs b/src/query/engine/anti.rs new file mode 100644 index 0000000000..c4708943ff --- /dev/null +++ b/src/query/engine/anti.rs @@ -0,0 +1,192 @@ +//! `AntiJoin` (#546 spec §4): `not` and `not-join`. An outer row is kept +//! when its body has no row. It filters; it never deduplicates. +//! +//! A correlated body runs once per outer row, from a [`Seed`](super::seed::Seed) +//! of the cells it imports, and stops at its first row. A hashed body runs +//! once, on the first pull; its rows' keys (their cells of the imported +//! variables, as [`JoinKey`]s) form a set the outer rows are looked up in. + +use super::batch::Batch; +use super::cell::{Cell, JoinKey}; +use super::plan::{Body as Spec, Key}; +use super::{Counters, Ctx, Operator, build}; +use anyhow::Result; +use std::collections::HashSet; + +pub(crate) struct AntiJoin { + outer: Box, + body: Body, + /// `rows_in` counts the outer rows received. + counters: Counters, +} + +enum Body { + Correlated { + root: Box, + imports: Vec, + seed: Vec, + }, + Hashed { + root: Box, + keys: Vec, + /// Built on the first pull, then kept: the body does not depend on + /// the outer row, so a rewind keeps it too. + set: Option, + }, +} + +/// The keys of a hashed body's rows, and whether it has any row. +struct Set { + keys: HashSet>, + any: bool, +} + +impl AntiJoin { + pub(crate) fn new(outer: Box, spec: Spec) -> Self { + let body = match spec { + Spec::Correlated { plan, imports } => Body::Correlated { + root: build(plan.source, plan.steps), + imports, + seed: Vec::new(), + }, + Spec::Hashed { plan, keys } => Body::Hashed { + root: build(plan.source, plan.steps), + keys, + set: None, + }, + }; + AntiJoin { + outer, + body, + counters: Counters::new("AntiJoin"), + } + } +} + +/// The cell of row `i` in `slot`. +fn cell(batch: &Batch, slot: usize, i: usize) -> Option<&Cell> { + batch.cols.get(slot).and_then(|c| c.get(i)) +} + +impl Body { + /// Whether the body has a row for row `i` of `batch`. + fn matches(&mut self, batch: &Batch, i: usize, ctx: &mut Ctx<'_>) -> Result { + match self { + Body::Correlated { + root, + imports, + seed, + } => { + seed.clear(); + for &slot in imports.iter() { + // Every imported slot is filled. + if let Some(c) = cell(batch, slot, i) { + seed.push(c.clone()); + } + } + root.rewind(seed); + let hit = root.next_batch(ctx)?.is_some(); + root.close(); + Ok(hit) + } + Body::Hashed { root, keys, set } => { + if set.is_none() { + *set = Some(collect(root.as_mut(), keys, ctx)?); + } + let Some(set) = set else { + return Ok(false); + }; + if keys.is_empty() { + return Ok(set.any); + } + let mut key = Vec::with_capacity(keys.len()); + for k in keys.iter() { + let Some(c) = cell(batch, k.outer, i) else { + return Ok(false); + }; + // A NaN equals nothing a body row holds. + let Some(j) = JoinKey::of(c, k.normalise, ctx)? else { + return Ok(false); + }; + key.push(j); + } + Ok(set.keys.contains(&key)) + } + } + } + + fn root(&self) -> &dyn Operator { + match self { + Body::Correlated { root, .. } | Body::Hashed { root, .. } => root.as_ref(), + } + } + + fn root_mut(&mut self) -> &mut dyn Operator { + match self { + Body::Correlated { root, .. } | Body::Hashed { root, .. } => root.as_mut(), + } + } +} + +/// Every row of a hashed body, as the keys of `keys`' inner slots. +fn collect(root: &mut dyn Operator, keys: &[Key], ctx: &mut Ctx<'_>) -> Result { + let mut set = Set { + keys: HashSet::new(), + any: false, + }; + while let Some(b) = root.next_batch(ctx)? { + set.any = true; + if keys.is_empty() { + break; + } + 'row: for i in 0..b.len { + let mut key = Vec::with_capacity(keys.len()); + for k in keys { + let Some(c) = cell(&b, k.inner, i) else { + continue 'row; + }; + // A row with a NaN key equals no outer row. + let Some(j) = JoinKey::of(c, k.normalise, ctx)? else { + continue 'row; + }; + key.push(j); + } + set.keys.insert(key); + } + } + root.close(); + Ok(set) +} + +impl Operator for AntiJoin { + fn next_batch(&mut self, ctx: &mut Ctx<'_>) -> Result> { + while let Some(mut batch) = self.outer.next_batch(ctx)? { + self.counters.rows_in += batch.len as u64; + let mut keep = Vec::with_capacity(batch.len); + for i in 0..batch.len { + keep.push(!self.body.matches(&batch, i, ctx)?); + } + batch.retain(&keep); + if batch.len > 0 { + self.counters.out(&batch); + return Ok(Some(batch)); + } + } + Ok(None) + } + + fn rewind(&mut self, seed: &[Cell]) { + self.outer.rewind(seed); + } + + fn close(&mut self) { + self.outer.close(); + self.body.root_mut().close(); + } + + fn counters(&self, out: &mut Vec) { + out.push(self.counters); + self.body.root().counters(out); + self.outer.counters(out); + } +} diff --git a/src/query/engine/filter.rs b/src/query/engine/filter.rs index 281ad90566..8adce32a3d 100644 --- a/src/query/engine/filter.rs +++ b/src/query/engine/filter.rs @@ -28,6 +28,7 @@ impl Apply { Step::Filter(..) => "Filter", Step::Bind(..) => "Bind", Step::Join(_) => "Join", + Step::Anti(_) => "AntiJoin", }; Apply { child, @@ -50,6 +51,10 @@ impl Operator for Apply { Ok(None) } + fn rewind(&mut self, seed: &[Cell]) { + self.child.rewind(seed); + } + fn close(&mut self) { self.child.close(); } @@ -120,8 +125,8 @@ fn apply(step: &Step, mut batch: Batch, ctx: &mut Ctx<'_>) -> Result { batch.retain(&keep); batch.set_col(*slot, out); } - // Joins are operators of their own (`join::Join`). - Step::Join(_) => {} + // Joins are operators of their own (`join::Join`, `anti::AntiJoin`). + Step::Join(_) | Step::Anti(_) => {} } Ok(batch) } diff --git a/src/query/engine/join.rs b/src/query/engine/join.rs index ee23d4cf5d..8ba893a33a 100644 --- a/src/query/engine/join.rs +++ b/src/query/engine/join.rs @@ -362,6 +362,12 @@ impl Operator for Join { Ok(Some(out)) } + fn rewind(&mut self, seed: &[Cell]) { + self.state = State::Start; + self.outer.rewind(seed); + self.inner.rewind(&[]); + } + fn close(&mut self) { self.state = State::Done; self.outer.close(); diff --git a/src/query/engine/mod.rs b/src/query/engine/mod.rs index de61da4bb4..6af0a4dd2f 100644 --- a/src/query/engine/mod.rs +++ b/src/query/engine/mod.rs @@ -6,6 +6,7 @@ //! `test-oracle` feature, every query run here is also run by the executor //! and the answers are compared ([`oracle`]). +mod anti; mod batch; mod cell; mod filter; @@ -16,6 +17,7 @@ pub(crate) mod oracle; mod plan; mod project; mod scan; +mod seed; #[cfg(all(test, not(target_arch = "wasm32")))] mod tests; @@ -80,6 +82,10 @@ impl Counters { /// batch; after `close`, it returns `None` and reads nothing. pub(crate) trait Operator: Send { fn next_batch(&mut self, ctx: &mut Ctx<'_>) -> Result>; + /// Start again from the beginning, reopening a closed operator, with + /// `seed` as the row of the plan's [`seed::Seed`], if it has one (#546). + /// Only a correlated body's plan is rewound. + fn rewind(&mut self, seed: &[cell::Cell]); /// Stop: release what the operator holds and close its children. fn close(&mut self); /// This operator's counters, then its children's. @@ -125,18 +131,12 @@ pub(crate) fn open( }; let ids = IdSpace::new(keys); let Plan { - scan, + source, steps, find, vars, } = plan; - let mut root: Box = Box::new(scan::Scan::new(scan)); - for step in steps { - root = match step { - plan::Step::Join(spec) => Box::new(join::Join::new(root, spec)), - step => Box::new(filter::Apply::new(root, step)), - }; - } + let root = build(source, steps); Some(Stream { snapshot, ids, @@ -149,6 +149,22 @@ pub(crate) fn open( }) } +/// The operator tree of a plan's source and steps. +pub(crate) fn build(source: plan::Source, steps: Vec) -> Box { + let mut root: Box = match source { + plan::Source::Scan(spec) => Box::new(scan::Scan::new(spec)), + plan::Source::Seed => Box::new(seed::Seed::new()), + }; + for step in steps { + root = match step { + plan::Step::Join(spec) => Box::new(join::Join::new(root, spec)), + plan::Step::Anti(body) => Box::new(anti::AntiJoin::new(root, body)), + step => Box::new(filter::Apply::new(root, step)), + }; + } + root +} + impl Stream { /// A stream of `root`'s batches, projecting slot 0 as `?x`. #[cfg(test)] diff --git a/src/query/engine/plan.rs b/src/query/engine/plan.rs index 55575128b3..62eb367daa 100644 --- a/src/query/engine/plan.rs +++ b/src/query/engine/plan.rs @@ -29,7 +29,7 @@ use crate::query::datalog::types::{ AsOf, AttributeSpec, DatalogQuery, EdnValue, Expr, FindSpec, Pattern, PseudoAttr, ValidAt, WhereClause, }; -use std::collections::HashMap; +use std::collections::{HashMap, HashSet}; /// One position of a pattern. #[derive(Debug, Clone)] @@ -127,6 +127,32 @@ pub(crate) enum Step { Bind(Expr, Vars, usize, Out), /// A later pattern, joined with the rows so far. Join(JoinSpec), + /// `not` / `not-join`: keeps the rows for which the body has no row + /// (#546). + Anti(Body), +} + +/// A `not` / `not-join` body (#546 spec §4). +#[derive(Debug, Clone)] +pub(crate) enum Body { + /// Run once per outer row, from a seed of its cells at `imports` (in + /// seed slots `0..imports.len()`). + Correlated { + plan: Box, + imports: Vec, + }, + /// Run once; a body row matches the outer rows whose cells at each + /// `keys[k].outer` are join-equal to its cells at `keys[k].inner`. + Hashed { plan: Box, keys: Vec }, +} + +/// Where a plan's rows start. +#[derive(Debug, Clone)] +pub(crate) enum Source { + /// The first pattern. + Scan(ScanSpec), + /// One row: the cells a correlated body imports, in its first slots. + Seed, } /// A join of the rows so far (the outer side) with one pattern (spec §6.2). @@ -186,11 +212,11 @@ pub(crate) enum Out { /// The variables an expression reads that are bound when it runs, by slot. pub(crate) type Vars = Vec<(String, usize)>; -#[derive(Debug)] +#[derive(Debug, Clone)] pub(crate) struct Plan { - pub(crate) scan: ScanSpec, + pub(crate) source: Source, pub(crate) steps: Vec, - /// The slot of each `:find` variable. + /// The slot of each `:find` variable; empty for a body. pub(crate) find: Vec, pub(crate) vars: Vec, } @@ -216,6 +242,10 @@ impl Slots { fn len(&self) -> usize { self.kinds.len() } + + fn kind(&self, slot: usize) -> u8 { + self.kinds.get(slot).copied().unwrap_or(OTHER) + } } /// The plan of `query`, or `None` when the engine does not run it yet. @@ -232,32 +262,111 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { Some(ValidAt::AnyValidTime) => Valid::Any, Some(ValidAt::Slot(_)) => return None, }; - if !query - .where_clauses - .iter() - .all(|c| matches!(c, WhereClause::Pattern(_) | WhereClause::Expr { .. })) - { + if !query.where_clauses.iter().all(|c| { + matches!( + c, + WhereClause::Pattern(_) + | WhereClause::Expr { .. } + | WhereClause::Not(_) + | WhereClause::NotJoin { .. } + ) + }) { return None; } - let mut binders = Binders::new(&query.where_clauses, Vec::new()); - let (planned, _) = optimizer::plan(query.where_clauses.clone()); - let all: Vec = planned.into_iter().map(|(c, _)| c).collect(); - let mut slots = Slots::default(); - let mut outer_patterns: Vec = Vec::new(); - let mut scan = None; - let mut steps = Vec::with_capacity(all.len()); - for c in all { + let mut b = Builder::new( + Some(Binders::new(&query.where_clauses, Vec::new())), + as_of, + valid, + ); + let (planned, mut deferred) = optimizer::plan(query.where_clauses.clone()); + for (c, _) in planned { + b.clause(c)?; + } + // A `not` whose variables only an expression binds runs last, as on the + // executor. + if optimizer::reorder() { + deferred.sort_by_key(optimizer::clause_cost); + } + for c in deferred { + b.clause(c)?; + } + + let mut find = Vec::with_capacity(query.find.len()); + for spec in &query.find { + let FindSpec::Variable(var) = spec else { + return None; + }; + // The parser rejects a variable no clause binds (PRS-080). + find.push(*b.slots.by_var.get(var)?); + } + let mut plan = b.finish()?; + plan.find = find; + plan.vars = query.find.iter().map(FindSpec::display_name).collect(); + Some(plan) +} + +/// Builds the operator steps of one clause list: a query's `:where`, or a +/// body. +struct Builder { + slots: Slots, + /// Which pattern or expression gives a variable its value; `None` in a + /// body, where no join or expression replaces a cell (decision 10 of the + /// #546 plan). + binders: Option, + as_of: Option, + valid: Valid, + source: Option, + steps: Vec, + /// `not`s planned before the first pattern (they read no variable): they + /// run right after it, which does not change the rows (decision 9). + front: Vec, + /// The stored-attribute patterns so far, for the `HashJoin` build side. + outer_patterns: Vec, +} + +impl Builder { + fn new(binders: Option, as_of: Option, valid: Valid) -> Self { + Builder { + slots: Slots::default(), + binders, + as_of, + valid, + source: None, + steps: Vec::new(), + front: Vec::new(), + outer_patterns: Vec::new(), + } + } + + fn finish(self) -> Option { + if !self.front.is_empty() { + return None; + } + Some(Plan { + source: self.source?, + steps: self.steps, + find: Vec::new(), + vars: Vec::new(), + }) + } + + /// Add the steps of `c`; `None` when the engine cannot run it. + fn clause(&mut self, c: WhereClause) -> Option<()> { + let (as_of, valid) = (self.as_of, self.valid); match c { WhereClause::Pattern(q) => { - let rebind = binders.pattern(&q); + let rebind = match &mut self.binders { + Some(b) => b.pattern(&q), + None => Vec::new(), + }; let pseudo = meta(&q); if pseudo.is_some_and(|m| m != Meta::ValidAt) { // Reads the hidden variable its source's scan filled. let source = q.pseudo_source.as_ref()?.as_variable()?; - let col = *slots.by_var.get(source)?; - let value = term(&q.value, &mut slots, OTHER, pseudo_const)?; - steps.push(Step::Pseudo { col, value }); - continue; + let col = *self.slots.by_var.get(source)?; + let value = term(&q.value, &mut self.slots, OTHER, pseudo_const)?; + self.steps.push(Step::Pseudo { col, value }); + return Some(()); } // A pattern with a stored attribute, or `:db/valid-at` read // as `[e _ _]` and the query's valid time. @@ -279,11 +388,12 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { if pseudo.is_some() { wants.push((Meta::ValidAt, None)); } + let slots = &mut self.slots; let mut metas: Vec<(Meta, usize)> = Vec::new(); - if scan.is_none() { - let e = term(&scanned.entity, &mut slots, OTHER, entity_const)?; - let a = term(&attribute, &mut slots, ATTRIBUTE, attribute_const)?; - let v = term(&scanned.value, &mut slots, OTHER, value_const)?; + if self.source.is_none() { + let e = term(&scanned.entity, slots, OTHER, entity_const)?; + let a = term(&attribute, slots, ATTRIBUTE, attribute_const)?; + let v = term(&scanned.value, slots, OTHER, value_const)?; for &(m, var) in &wants { let slot = slots.add(OTHER); if let Some(var) = var { @@ -291,7 +401,7 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { } metas.push((m, slot)); } - scan = Some(ScanSpec { + self.source = Some(Source::Scan(ScanSpec { e, a, v, @@ -299,9 +409,10 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { as_of, valid, width: slots.len(), - }); + })); + self.steps.append(&mut self.front); } else { - let mut join = join(&scanned, &attribute, &mut slots, &rebind, as_of, valid)?; + let mut join = join(&scanned, &attribute, slots, &rebind, as_of, valid)?; for &(m, var) in &wants { let local = join.inner.width; join.inner.width += 1; @@ -315,66 +426,178 @@ pub(crate) fn plan(query: &DatalogQuery) -> Option { } if let JoinKind::Hash { build_inner } = &mut join.kind { // With the test switch off, always the inner pattern - // (decision 3 of the #596 plan). + // (decision 3 of the #596 plan). After a seed and no + // pattern, the seed (`branch_cost` of nothing is 0). *build_inner = !optimizer::reorder() || optimizer::branch_cost(&[WhereClause::Pattern(q.clone())]) - <= optimizer::branch_cost(&outer_patterns); + <= optimizer::branch_cost(&self.outer_patterns); } - steps.push(Step::Join(join)); + self.steps.push(Step::Join(join)); } - outer_patterns.push(WhereClause::Pattern(q.clone())); + self.outer_patterns.push(WhereClause::Pattern(q.clone())); if pseudo.is_some() { let col = metas.last()?.1; - let value = term(&q.value, &mut slots, OTHER, pseudo_const)?; - steps.push(Step::Pseudo { col, value }); + let value = term(&q.value, &mut self.slots, OTHER, pseudo_const)?; + self.steps.push(Step::Pseudo { col, value }); } } WhereClause::Expr { expr, binding } => { // A clause before the first pattern sees no variable. - let vars = expr_vars(&expr, &slots); + self.source.as_ref()?; + let vars = expr_vars(&expr, &self.slots); let step = match binding { None => Step::Filter(expr, vars), Some(out) => { - let replace = binders.expression(&expr, &out); - let (slot, mode) = match slots.by_var.get(&out) { + let replace = match &mut self.binders { + Some(b) => b.expression(&expr, &out), + None => false, + }; + let (slot, mode) = match self.slots.by_var.get(&out) { Some(&s) if replace => { - if let Some(k) = slots.kinds.get_mut(s) { + if let Some(k) = self.slots.kinds.get_mut(s) { *k |= OTHER; } (s, Out::Replace) } Some(&s) => (s, Out::Check), None => { - let s = slots.add(OTHER); - slots.by_var.insert(out, s); + let s = self.slots.add(OTHER); + self.slots.by_var.insert(out, s); (s, Out::New) } }; Step::Bind(expr, vars, slot, mode) } }; - scan.as_ref()?; - steps.push(step); + self.steps.push(step); + } + WhereClause::Not(body) => { + // Every variable the body names that the rows bind; the + // others are the body's own (its sources' hidden variables). + let imports = optimizer::clause_ref_vars(&body); + let step = self.anti(&body, imports.into_iter().collect())?; + self.push_anti(step); + } + WhereClause::NotJoin { join_vars, clauses } => { + let step = self.anti(&clauses, join_vars)?; + self.push_anti(step); } _ => return None, } + Some(()) } - let scan = scan?; - let mut find = Vec::with_capacity(query.find.len()); - for spec in &query.find { - let FindSpec::Variable(var) = spec else { + fn push_anti(&mut self, step: Step) { + if self.source.is_some() { + self.steps.push(step); + } else { + self.front.push(step); + } + } + + /// The `AntiJoin` of `body`, whose variables `vars` the outer row gives + /// where it binds them (spec §2), hashed or correlated (spec §4.4). + fn anti(&self, body: &[WhereClause], vars: Vec) -> Option { + if !body + .iter() + .all(|c| matches!(c, WhereClause::Pattern(_) | WhereClause::Expr { .. })) + { return None; + } + let mut imports: Vec<(String, usize)> = vars + .into_iter() + .filter_map(|v| self.slots.by_var.get(&v).map(|&s| (v, s))) + .collect(); + imports.sort_by_key(|&(_, s)| s); + let seeded: HashSet = imports.iter().map(|(v, _)| v.clone()).collect(); + let (seeded_order, _) = optimizer::plan_seeded(body.to_vec(), &seeded); + // A probe per outer row holds nothing: correlated when the first + // pattern's entity is imported. + let probe = seeded_order + .iter() + .find_map(|(c, _)| match c { + WhereClause::Pattern(p) if !per_fact(p) => Some(p), + _ => None, + }) + .and_then(|p| p.entity.as_variable()) + .is_some_and(|e| seeded.contains(e)); + let hashable = closed(body); + let hash = match optimizer::subplans() { + optimizer::Subplans::Choose => hashable && !probe, + optimizer::Subplans::Hash => hashable, + optimizer::Subplans::Correlated => false, }; - // The parser rejects a variable no clause binds (PRS-080). - find.push(*slots.by_var.get(var)?); + let (as_of, valid) = (self.as_of, self.valid); + if hash { + let mut b = Builder::new(None, as_of, valid); + for (c, _) in optimizer::plan(body.to_vec()).0 { + b.clause(c)?; + } + let keys = imports + .iter() + .filter_map(|(v, outer)| { + let inner = *b.slots.by_var.get(v)?; + let both = + self.slots.kind(*outer) == ATTRIBUTE && b.slots.kind(inner) == ATTRIBUTE; + Some(Key { + inner, + outer: *outer, + normalise: !both, + }) + }) + .collect(); + return Some(Step::Anti(Body::Hashed { + plan: Box::new(b.finish()?), + keys, + })); + } + let mut b = Builder::new(None, as_of, valid); + for (v, outer) in &imports { + let s = b.slots.add(self.slots.kind(*outer)); + b.slots.by_var.insert(v.clone(), s); + } + b.source = Some(Source::Seed); + for (c, _) in seeded_order { + b.clause(c)?; + } + Some(Step::Anti(Body::Correlated { + plan: Box::new(b.finish()?), + imports: imports.into_iter().map(|(_, s)| s).collect(), + })) } - Some(Plan { - scan, - steps, - find, - vars: query.find.iter().map(FindSpec::display_name).collect(), - }) +} + +/// Whether `p` is a per-fact pseudo-attribute pattern (it scans nothing). +fn per_fact(p: &Pattern) -> bool { + matches!(&p.attribute, AttributeSpec::Pseudo(a) if a.is_per_fact()) +} + +/// Whether `body` has the same rows for every outer row (spec §2): it has a +/// pattern to scan, and every variable its expressions and per-fact +/// pseudo-attributes read is bound by one of its other patterns (decision 6 +/// of the #546 plan). +fn closed(body: &[WhereClause]) -> bool { + let bound: HashSet = body + .iter() + .filter_map(|c| match c { + WhereClause::Pattern(p) if !per_fact(p) => Some(optimizer::pattern_bound_vars(p)), + _ => None, + }) + .flatten() + .collect(); + body.iter() + .any(|c| matches!(c, WhereClause::Pattern(p) if !per_fact(p))) + && body.iter().all(|c| match c { + WhereClause::Expr { expr, .. } => { + optimizer::expr_vars(expr).iter().all(|v| bound.contains(v)) + } + WhereClause::Pattern(p) if per_fact(p) => p + .pseudo_source + .as_ref() + .and_then(EdnValue::as_variable) + .is_some_and(|v| bound.contains(v)), + _ => true, + }) } /// The join of the rows so far, whose variables are `slots`, with the diff --git a/src/query/engine/scan.rs b/src/query/engine/scan.rs index bf55ce8ba6..779a71eb67 100644 --- a/src/query/engine/scan.rs +++ b/src/query/engine/scan.rs @@ -236,6 +236,12 @@ impl Operator for Scan { } } + /// Start again; the constants resolved against the DICT are kept. + fn rewind(&mut self, _seed: &[Cell]) { + self.probe = None; + self.state = State::Start; + } + fn close(&mut self) { self.state = State::Done; self.keys_buf = Vec::new(); diff --git a/src/query/engine/seed.rs b/src/query/engine/seed.rs new file mode 100644 index 0000000000..c3530db28e --- /dev/null +++ b/src/query/engine/seed.rs @@ -0,0 +1,53 @@ +//! `Seed` (#546): the one row a correlated body starts from, the cells it +//! imports from the outer row. + +use super::batch::Batch; +use super::cell::Cell; +use super::{Counters, Ctx, Operator}; +use anyhow::Result; + +pub(crate) struct Seed { + row: Vec, + /// Whether the row has been returned since the last rewind. + done: bool, + counters: Counters, +} + +impl Seed { + /// A seed with no row until the first rewind. + pub(crate) fn new() -> Self { + Seed { + row: Vec::new(), + done: true, + counters: Counters::new("Seed"), + } + } +} + +impl Operator for Seed { + fn next_batch(&mut self, _: &mut Ctx<'_>) -> Result> { + if self.done { + return Ok(None); + } + self.done = true; + let mut batch = Batch::new(self.row.len()); + let mut row: Vec> = self.row.iter().cloned().map(Some).collect(); + batch.push(&mut row); + self.counters.out(&batch); + Ok(Some(batch)) + } + + fn rewind(&mut self, seed: &[Cell]) { + self.row.clear(); + self.row.extend_from_slice(seed); + self.done = false; + } + + fn close(&mut self) { + self.done = true; + } + + fn counters(&self, out: &mut Vec) { + out.push(self.counters); + } +} diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index dcef76f7d1..c007afd441 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -269,6 +269,10 @@ fn queries(tx: u64) -> Vec { for clauses in valid_at { let find = vars_of(clauses); for temporal in temporals(tx) { + // Per-fact metadata needs `:any-valid-time` (INT-026). + if clauses.contains(":db/tx-count") && !temporal.contains(":any-valid-time") { + continue; + } out.push(format!( "(query [:find {find} {temporal} :where {clauses}])" )); @@ -618,6 +622,8 @@ impl super::Operator for FailAfter { Ok(Some(batch)) } + fn rewind(&mut self, _: &[super::cell::Cell]) {} + fn close(&mut self) { self.closed = true; } @@ -848,3 +854,237 @@ fn engine_joins_read_many_batches() { 5 * 286 * 286 + 2 * 285 * 285 ); } + +/// `not` / `not-join` shapes (#546): hashed and correlated bodies, keys on +/// the entity, value and attribute positions, floats and keywords imported +/// into a body, expressions over imported variables, per-fact +/// pseudo-attributes and `:db/valid-at` in bodies, deferred and +/// variable-free negations. +fn negations() -> Vec<&'static str> { + vec![ + // Correlated: the body's entity is imported. + "[?e :person/name ?n] (not [?e :person/ok true])", + "[?e :person/friend ?f] (not [?f :person/ok true])", + "[?e :person/name ?n] (not-join [?e] [?e :person/friend ?f] [?f :person/ok true])", + "[?e :person/age ?a] (not-join [?e] [?e :person/score ?s] [(> ?s 1.0)])", + // Hashed: keyed on a value or an attribute. + "[?e :person/age ?a] (not-join [?a] [?f :person/age ?a] [?f :person/ok true])", + "[?e :person/score ?s] (not-join [?s] [?f :person/score ?s] [?f :person/ok false])", + "[?e :person/boss ?b] (not-join [?b] [?x :person/friend ?b])", + "[?e :person/alias ?b] (not-join [?b] [?x :person/boss ?b])", + "[?e :person/bio ?b] (not-join [?b] [?f :person/bio ?b] [?f :person/ok true])", + "[?e :person/attr ?x] (not-join [?x] [:p1 ?x 21])", + "[?e ?a 21] (not-join [?a] [?x :person/attr ?a])", + // A body that reads an imported variable it does not bind. + "[?e :person/age ?a] (not-join [?a] [?f :person/age ?b] [(< ?b ?a)])", + "[?e :person/age ?a] (not [(> ?a 21)])", + // A body binding no join variable; one reading no variable. + "[?e :person/name ?n] (not-join [?e] [?x :person/ok true])", + "[?e :person/name ?n] (not [:p1 :person/ok true])", + // Metadata of an outer source, and the valid time. + "[?e :person/name ?n] (not-join [?e] [?e :db/tx-count ?t] [(> ?t 3)])", + "[?e :person/name ?n] (not-join [?e] [?e :db/valid-at ?t] [(> ?t 0)])", + "[?e :person/name ?n] (not-join [?e] [?e :db/valid-at ?t])", + // Deferred: an expression binds the join variable. + "[?e :person/age ?a] [(+ ?a 1) ?b] (not-join [?b] [?f :person/age ?b])", + // Two negations. + "[?e :person/name ?n] (not [?e :person/ok true]) (not [?e :person/status :s1])", + ] +} + +fn negation_queries(tx: u64) -> Vec { + let mut out = Vec::new(); + for clauses in negations() { + let find = vars_of(clauses.split(" (not").next().unwrap_or(clauses)); + let find = find + .split(' ') + .filter(|v| !v.is_empty()) + .collect::>() + .join(" "); + for temporal in temporals(tx) { + // Per-fact metadata needs `:any-valid-time` (INT-026). + if clauses.contains(":db/tx-count") && !temporal.contains(":any-valid-time") { + continue; + } + out.push(format!( + "(query [:find {find} {temporal} :where {clauses}])" + )); + } + } + out +} + +/// Every negation shape with each body form forced and reordering on and +/// off; the oracle compares each run with the executor. +fn check_negations(db: &Minigraf) -> usize { + use crate::query::datalog::optimizer::{Subplans, set_reorder, set_subplans}; + let tx = db.current_tx_count(); + let mut total = 0; + for mode in [Subplans::Choose, Subplans::Hash, Subplans::Correlated] { + for on in [true, false] { + let _m = set_subplans(mode); + let _r = set_reorder(on); + total += negation_queries(tx) + .iter() + .map(|q| rows(db, q)) + .sum::(); + } + } + total +} + +#[test] +fn negation_matches_executor() { + let dir = tempfile::tempdir().unwrap(); + let mem = Minigraf::in_memory().unwrap(); + let file = Minigraf::open(dir.path().join("not.graph")).unwrap(); + for round in 0..3 { + write_round(&mem, round); + assert!(check_negations(&mem) > 0, "negations keep some rows"); + write_round(&file, round); + check_negations(&file); + file.checkpoint().unwrap(); + check_negations(&file); + } +} + +/// The body forms the planner chooses (#546 spec §4.4, decision 7 of the +/// plan): correlated when the first pattern's entity is imported or the +/// body reads an outer variable it does not bind, hashed otherwise; the +/// test switch forces either where the body allows it. +#[test] +fn planner_chooses_the_body_form() { + use super::plan::{Body, Step, plan}; + use crate::query::datalog::optimizer::{Subplans, set_subplans}; + use crate::query::datalog::parser::parse_datalog_command; + use crate::query::datalog::types::DatalogCommand; + let forms = |q: &str| -> Vec<&'static str> { + let Ok(DatalogCommand::Query(query)) = parse_datalog_command(q) else { + panic!("expected a query"); + }; + let plan = plan(&query).expect("an engine plan"); + plan.steps + .iter() + .filter_map(|s| match s { + Step::Anti(Body::Hashed { .. }) => Some("hashed"), + Step::Anti(Body::Correlated { .. }) => Some("correlated"), + _ => None, + }) + .collect() + }; + let probe = "(query [:find ?e :where [?e :a ?x] (not [?e :b 1])])"; + let keyed = "(query [:find ?e :where [?e :a ?x] (not-join [?x] [?f :b ?x])])"; + let open = "(query [:find ?e :where [?e :a ?x] (not-join [?x] [?f :b ?y] [(< ?y ?x)])])"; + let expr_only = "(query [:find ?e :where [?e :a ?x] (not [(> ?x 1)])])"; + let constant = "(query [:find ?e :where [?e :a ?x] (not [:p :b 1])])"; + assert_eq!(forms(probe), ["correlated"]); + assert_eq!(forms(keyed), ["hashed"]); + assert_eq!(forms(open), ["correlated"]); + assert_eq!(forms(expr_only), ["correlated"]); + assert_eq!(forms(constant), ["hashed"]); + { + let _h = set_subplans(Subplans::Hash); + assert_eq!(forms(probe), ["hashed"]); + assert_eq!(forms(open), ["correlated"], "not closed: never hashed"); + assert_eq!(forms(expr_only), ["correlated"], "nothing to scan"); + } + let _c = set_subplans(Subplans::Correlated); + assert_eq!(forms(keyed), ["correlated"]); + assert_eq!(forms(constant), ["correlated"]); +} + +/// Which negations the engine runs (#546 PR 1): every `not` / `not-join` +/// without a rule invocation; a query with `or` stays on the executor +/// until PR 2. +#[test] +fn negation_routing() { + let db = Minigraf::in_memory().unwrap(); + write_round(&db, 0); + db.execute("(rule [(okay ?e) [?e :person/ok true]])") + .unwrap(); + for q in [ + "(query [:find ?e :where [?e :person/name ?n] (not [?e :person/ok true])])", + "(query [:find ?e :where [?e :person/name ?n] (not [:p1 :person/ok true])])", + "(query [:find ?e :where [?e :person/age ?a] [(+ ?a 1) ?b] (not-join [?b] [?f :person/age ?b])])", + ] { + rows(&db, q); + } + for q in [ + "(query [:find ?e :where [?e :person/name ?n] (not (okay ?e))])", + "(query [:find ?e :where [?e :person/name ?n] (or [?e :person/ok true] [?e :person/age 21])])", + ] { + let before = runs(); + db.execute(q).unwrap(); + assert_eq!(runs(), before, "query stayed on the executor"); + } +} + +/// `not` filters and never deduplicates (spec §3.1): rows with the same +/// `:find` values both survive. A failing expression drops its body row, so +/// it cannot exclude the outer row (spec §3.3). +#[test] +fn negation_keeps_multiplicity() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :n 1] [:b :n 1] [:c :n 2] [:d :x 0.0]])") + .unwrap(); + assert_eq!( + rows( + &db, + "(query [:find ?v :where [?e :n ?v] (not-join [?v] [?f :n ?v] [(> ?v 1)])])" + ), + 2 + ); + assert_eq!( + rows( + &db, + "(query [:find ?e :where [?e :x ?v] (not-join [?v] [?f :x ?v] [(/ 1 0) ?z])])" + ), + 1 + ); +} + +/// An unknown predicate in a body fails on every body row, so the `not` +/// keeps every outer row (spec §3.3), on the engine as on the executor. +#[test] +fn negation_unknown_predicate_keeps_rows() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :n 1] [:b :n 2]])").unwrap(); + assert_eq!( + rows( + &db, + "(query [:find ?e :where [?e :n ?v] (not [?e :n ?v] [(no-such-pred? ?v)])])" + ), + 2 + ); +} + +/// A correlated body probes once per outer row from its seed; a hashed one +/// is read once, however many outer rows there are (#546 spec §4.2, §4.3). +#[test] +fn negation_bodies_run_per_row_or_once() { + let db = Minigraf::in_memory().unwrap(); + let facts: String = (0..50) + .map(|i| format!("[:e{i} :n {i}] [:e{i} :tag :t{}]", i % 5)) + .collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + let ops = |q: &str| { + let mut cursor = db.query(q).unwrap(); + cursor.next_batch(1).unwrap().expect("a row"); + cursor.counters() + }; + let c = ops("(query [:find ?e :where [?e :n ?v] (not [?e :tag :t0])])"); + let seed = c.iter().find(|c| c.op == "Seed").expect("a seed"); + let anti = c.iter().find(|c| c.op == "AntiJoin").expect("an AntiJoin"); + assert_eq!(seed.rows_out, 50, "one seed row per outer row"); + assert_eq!(anti.rows_in, 50); + assert_eq!(anti.rows_out, 40); + assert!(c.iter().any(|c| c.op == "IndexNestedLoopJoin")); + + let c = ops("(query [:find ?e :where [?e :n ?v] (not-join [?v] [?f :n ?v] [?f :tag :t0])])"); + assert!(!c.iter().any(|c| c.op == "Seed"), "hashed: no seed"); + let anti = c.iter().find(|c| c.op == "AntiJoin").expect("an AntiJoin"); + assert_eq!(anti.rows_out, 40); + // The outer scan, the body's scan and its probes: each key read once. + let read: u64 = c.iter().filter(|c| c.op == "Scan").map(|c| c.rows_in).sum(); + assert!(read <= 150, "the body is read once"); +} diff --git a/tests/negation_equality_test.rs b/tests/negation_equality_test.rs new file mode 100644 index 0000000000..a7e9cfff36 --- /dev/null +++ b/tests/negation_equality_test.rs @@ -0,0 +1,149 @@ +//! A value a `not` / `not-join` body takes from the outer row compares as a +//! join compares it (#546, design +//! `docs/superpowers/specs/2026-10-16-negation-disjunction-engine-design.md` +//! §3.1, §3.6 item 1): floats by IEEE `==`, a keyword equal to a ref to the +//! entity it names. Before, a path that substituted the outer value as a +//! literal matched floats within `f64::EPSILON`, so the answer depended on +//! whether the body held an expression. +#![cfg(not(target_arch = "wasm32"))] + +use minigraf::{Minigraf, OpenOptions, QueryResult, Value}; + +fn executed(db: &Minigraf, q: &str) -> Vec> { + match db.execute(&format!("(query {q})")).expect("query") { + QueryResult::QueryResults { results, .. } => results, + _ => panic!("expected QueryResults"), + } +} + +fn pulled(db: &Minigraf, q: &str) -> Vec> { + let mut cursor = db.query(&format!("(query {q})")).expect("query"); + let mut rows = Vec::new(); + while let Some(batch) = cursor.next_batch(3).expect("batch") { + rows.extend(batch.rows().iter().cloned()); + } + rows +} + +/// The entity a keyword names, as `edn_to_entity_id` derives it. +fn named(k: &str) -> uuid::Uuid { + uuid::Uuid::new_v5(&uuid::Uuid::NAMESPACE_OID, k.as_bytes()) +} + +/// The entities `q` returns, as the keywords that name them, through +/// `execute` and a cursor (which must agree), sorted. +fn entities(db: &Minigraf, q: &str, names: &[&str]) -> Vec { + let name = |v: &Value| -> String { + names + .iter() + .find(|k| matches!(v, Value::Ref(u) if *u == named(k))) + .map_or_else(|| "?".to_string(), |k| k.to_string()) + }; + let mut a: Vec = executed(db, q).iter().map(|r| name(&r[0])).collect(); + let mut b: Vec = pulled(db, q).iter().map(|r| name(&r[0])).collect(); + a.sort(); + b.sort(); + assert_eq!(a, b, "execute and cursor agree"); + a +} + +/// Two floats `1e-20` apart: within `f64::EPSILON`, but not equal. +const TINY: &str = "(transact [[:e1 :x 0.00000000000000000001] [:g :y 0.00000000000000000002]])"; + +/// Each `not` / `not-join` shape over [`TINY`]; every one keeps `:e1`. +const TINY_QUERIES: &[&str] = &[ + // §3.6 item 1: the exclusion-set path and the per-row path. + "[:find ?e :where [?e :x ?f] (not-join [?f] [?g :y ?f])]", + "[:find ?e :where [?e :x ?f] (not-join [?f] [?g :y ?f] [(> ?f 0.0)])]", + "[:find ?e :where [?e :x ?f] (not [:g :y ?f])]", + "[:find ?e :where [?e :x ?f] (not [:g :y ?f] [(> ?f 0.0)])]", + // A query that invokes a rule takes the rule path for its negation. + "[:find ?e :where [?e :x ?f] (any ?e) (not [:g :y ?f])]", + "[:find ?e :where [?e :x ?f] (any ?e) (not-join [?f] [?g :y ?f])]", + // A rule body's negation. + "[:find ?e :where (kept ?e)]", +]; + +fn tiny(db: &Minigraf) { + db.execute(TINY).unwrap(); + db.execute("(rule [(any ?e) [?e :x _]])").unwrap(); + db.execute("(rule [(kept ?e) [?e :x ?f] (not [:g :y ?f])])") + .unwrap(); +} + +#[test] +fn imported_float_compares_by_ieee_equality() { + let db = Minigraf::in_memory().unwrap(); + tiny(&db); + for q in TINY_QUERIES { + assert_eq!(entities(&db, q, &[":e1"]), vec![":e1"], "{q}"); + } +} + +#[test] +fn imported_float_compares_by_ieee_equality_after_checkpoint() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("neg.graph"); + { + let db = Minigraf::open(&path).unwrap(); + tiny(&db); + db.checkpoint().unwrap(); + } + let db = OpenOptions::new().path(&path).open().unwrap(); + db.execute("(rule [(any ?e) [?e :x _]])").unwrap(); + db.execute("(rule [(kept ?e) [?e :x ?f] (not [:g :y ?f])])") + .unwrap(); + for q in TINY_QUERIES { + assert_eq!(entities(&db, q, &[":e1"]), vec![":e1"], "{q}"); + } +} + +#[test] +fn imported_zero_equals_negative_zero() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :x 0.0] [:b :x 1.0] [:g :y -0.0]])") + .unwrap(); + db.execute("(rule [(any ?e) [?e :x _]])").unwrap(); + for q in [ + "[:find ?e :where [?e :x ?f] (not-join [?f] [?g :y ?f])]", + "[:find ?e :where [?e :x ?f] (not-join [?f] [?g :y ?f] [(>= ?f 0.0)])]", + "[:find ?e :where [?e :x ?f] (not [:g :y ?f] [(>= ?f 0.0)])]", + "[:find ?e :where [?e :x ?f] (any ?e) (not [:g :y ?f])]", + ] { + assert_eq!(entities(&db, q, &[":a", ":b"]), vec![":b"], "{q}"); + } +} + +#[test] +fn imported_keyword_equals_ref_to_its_entity() { + let db = Minigraf::in_memory().unwrap(); + // `:alice` and `:carol` hold a keyword naming an entity; `:bob` is banned. + db.execute("(transact [[:alice :friend :bob] [:carol :friend :dave] [:bob :banned true]])") + .unwrap(); + for q in [ + "[:find ?e :where [?e :friend ?f] (not [?f :banned true])]", + "[:find ?e :where [?e :friend ?f] (not [?f :banned true] [(< 0 1)])]", + "[:find ?e :where [?e :friend ?f] (not-join [?f] [?f :banned true])]", + "[:find ?e :where [?e :friend ?f] (not-join [?f] [?f :banned ?b] [(= ?b true)])]", + ] { + assert_eq!( + entities(&db, q, &[":alice", ":carol"]), + vec![":carol"], + "{q}" + ); + } +} + +#[test] +fn body_float_constant_keeps_epsilon_match() { + let db = Minigraf::in_memory().unwrap(); + db.execute("(transact [[:a :x 1.0] [:b :x 2.0] [:a :y 1.0]])") + .unwrap(); + // A literal in the body still matches within `f64::EPSILON`. + for q in [ + "[:find ?e :where [?e :x _] (not [?e :y 1.0000000000000001])]", + "[:find ?e :where [?e :x ?v] (not [?e :y 1.0000000000000001] [(> ?v 0.0)])]", + ] { + assert_eq!(entities(&db, q, &[":a", ":b"]), vec![":b"], "{q}"); + } +} diff --git a/tests/plan_independence_test.rs b/tests/plan_independence_test.rs index 1bbbcfb1a3..5e27042c01 100644 --- a/tests/plan_independence_test.rs +++ b/tests/plan_independence_test.rs @@ -3,7 +3,9 @@ //! //! Each query runs through `Minigraf::execute` and through a drained //! `Minigraf::query` cursor, with clause reordering on and off -//! (`minigraf::__reorder`), and all four answers must be the same bag. With +//! (`minigraf::__reorder`), and with the engine's `not` bodies chosen, +//! forced hashed and forced correlated (`minigraf::__subplans`, #546); all +//! twelve answers must be the same bag. With //! the `test-oracle` feature, every query the streaming engine runs is also //! run by the executor and must agree, so each run compares the two as well. //! Per-fact pseudo-attributes read the source the parser names (#594). @@ -48,31 +50,29 @@ fn pulled(db: &Minigraf, q: &str) -> Vec> { /// The answer to `q`, or how the plans disagree. fn check(db: &Minigraf, q: &str) -> Result>, String> { + use minigraf::Subplans; let on = { let _g = minigraf::__reorder(true); executed(db, q) }; - let runs = [ - ("cursor, reordering", { - let _g = minigraf::__reorder(true); - pulled(db, q) - }), - ("execute, source order", { - let _g = minigraf::__reorder(false); - executed(db, q) - }), - ("cursor, source order", { - let _g = minigraf::__reorder(false); - pulled(db, q) - }), - ]; - for (name, rows) in runs { - if rows != on { - return Err(format!( - "{name}: {} rows, reordering execute: {} rows, for {q}", - rows.len(), - on.len() - )); + for mode in [Subplans::Choose, Subplans::Hash, Subplans::Correlated] { + let _m = minigraf::__subplans(mode); + for reorder in [true, false] { + let _g = minigraf::__reorder(reorder); + for (how, rows) in [("execute", executed(db, q)), ("cursor", pulled(db, q))] { + if rows != on { + let order = if reorder { + "reordering" + } else { + "source order" + }; + return Err(format!( + "{how}, {order}, bodies {mode:?}: {} rows, reordering execute: {} rows, for {q}", + rows.len(), + on.len() + )); + } + } } } Ok(on) @@ -97,7 +97,8 @@ fn people(db: &Minigraf) { [:dave :name "Dave"] [:dave :age 25] [:p1 :score 41] [:p2 :score 31] [:p3 :score 41.0] [:alice :x 0.0] [:bob :y -0.0] [:carol :x 1.5] [:dave :y 1.5] - [:alice :bio "{long_a}"] [:bob :motto "{long_a}"] [:carol :motto "{long_b}"]])"#, + [:alice :bio "{long_a}"] [:bob :motto "{long_a}"] [:carol :motto "{long_b}"] + [:z1 :tiny 0.00000000000000000001] [:z2 :tiny2 0.00000000000000000002]])"#, bob().as_hyphenated() )) .unwrap(); @@ -157,6 +158,26 @@ const MATRIX: &[&str] = &[ r#"[:find ?n :where [?e :name ?n] (not-join [?e] [?e :friend ?f] [?f :age 40])]"#, r#"[:find ?n :where [?e :name ?n] (or [?e :age ?a] [?e :score ?a]) (not [(> ?a 35)])]"#, r#"[:find ?n :where [?e :name ?n] [?e :age ?a] (not-join [?a] [?f :age ?a] [?f :friend :carol])]"#, + // #546: imported floats by IEEE `==` (0.0 and -0.0 equal; 1e-20 and + // 2e-20 not), keywords and refs of one entity, long strings, bodies that + // read an imported variable they do not bind, no variable at all, or + // the valid time. + r#"[:find ?e :where [?e :x ?v] (not-join [?v] [?f :y ?v])]"#, + r#"[:find ?e :where [?e :x ?v] (not-join [?v] [?f :y ?v] [(>= ?v 0.0)])]"#, + r#"[:find ?e :where [?e :x ?v] (not [:bob :y ?v])]"#, + r#"[:find ?e :where [?e :x ?v] (not [:bob :y ?v] [(< ?v 1.0)])]"#, + r#"[:find ?e :where [?e :tiny ?v] (not-join [?v] [?f :tiny2 ?v])]"#, + r#"[:find ?e :where [?e :tiny ?v] (not-join [?v] [?f :tiny2 ?v] [(> ?v 0.0)])]"#, + r#"[:find ?a :where [?a :friend ?b] (not [?b :age 40])]"#, + r#"[:find ?a :where [?a :friend ?b] (not-join [?b] [?b :age ?x] [(> ?x 35)])]"#, + r#"[:find ?b :where [?b :name ?n] (not-join [?b] [?a :friend ?b])]"#, + r#"[:find ?b :where [?b :name ?n] (not-join [?b] [?a :friend ?b] [?a :age 30])]"#, + r#"[:find ?e :where [?e :bio ?s] (not-join [?s] [?f :motto ?s])]"#, + r#"[:find ?n :where [?e :name ?n] [?e :age ?a] (not-join [?a] [?f :age ?b] [(< ?b ?a)])]"#, + r#"[:find ?n :where [?e :name ?n] (not [:alice :age 30])]"#, + r#"[:find ?n :where [?e :name ?n] (not-join [?e] [?x :age 25])]"#, + r#"[:find ?n :valid-at "2030-01-01T00:00:00Z" :where [?e :name ?n] (not-join [?e] [?e :db/valid-at ?t] [(> ?t 0)])]"#, + r#"[:find ?n :valid-at "2030-01-01T00:00:00Z" :where [?e :name ?n] (not-join [?e] [?e :db/valid-at ?t])]"#, // Aggregates. r#"[:find ?a (count ?e) :where [?e :age ?a] [?e :name _]]"#, // Per-fact pseudo-attributes (#594): #594's example in both text orders, diff --git a/tests/property_test.rs b/tests/property_test.rs index ebde7effb6..c5a8f383a9 100644 --- a/tests/property_test.rs +++ b/tests/property_test.rs @@ -902,12 +902,14 @@ fn ctx() -> Ctx { } } -/// With `test-oracle`, every query also runs without clause reordering and -/// must give the same rows (#596). +/// With `test-oracle`, every query also runs without clause reordering +/// (#596) and with `not` bodies hashed where the engine would probe them +/// (#546), and must give the same rows. fn source_order() -> Option { #[cfg(feature = "test-oracle")] return Some(|db, q| { let _off = minigraf::__reorder(false); + let _hash = minigraf::__subplans(minigraf::Subplans::Hash); db.execute(q) }); #[cfg(not(feature = "test-oracle"))] diff --git a/tests/temporal_metadata_test.rs b/tests/temporal_metadata_test.rs index 2cc7747cb7..a73794a035 100644 --- a/tests/temporal_metadata_test.rs +++ b/tests/temporal_metadata_test.rs @@ -507,7 +507,7 @@ fn pseudo_attr_constant_filter_no_match() { } /// Gap 5: not-join body containing a pseudo-attr pattern. -/// Exercises evaluator.rs line 361 (substitute_pattern Pseudo arm in evaluate_not_join). +/// Exercises a per-fact pseudo-attribute in a seeded `not-join` body (`evaluate_not_join`). #[test] fn not_join_body_with_pseudo_attr() { let db = db(); @@ -519,7 +519,7 @@ fn not_join_body_with_pseudo_attr() { // Find entities whose valid-from is NOT 2020-01-01 (= 1577836800000). // The not-join body contains a pseudo-attr pattern [:db/valid-from 1577836800000], - // which triggers substitute_pattern's Pseudo arm. + // whose source is the outer `[?e :person/name _]`. let r = db .execute( r#"