feat(engine): not / not-join on the streaming engine, join equality in negation bodies (#546 PR 1) by adityamukho · Pull Request #624 · project-minigraf/minigraf

adityamukho · 2026-10-19T04:26:55Z

PR 1 of 2 for #546 (streaming engine part 4 of 9, #473): not and not-join. Spec: docs/superpowers/specs/2026-10-16-negation-disjunction-engine-design.md (#614). Plan: docs/superpowers/plans/2026-10-18-546-negation-disjunction.md (added here). PR 2 does or / or-join. #546 stays open until then. This does not close #473.

What changes

Executor: one comparison rule in negation bodies (spec §3.1, §3.6 item 1; breaking). Four places substituted the outer row's values into a not / not-join body as literals, so an imported float matched within f64::EPSILON: not_body_matches, the rule-query not path, evaluate_not_join, and the not loop in StratifiedEvaluator. They now match the body from a seed of the imported values (seeded_body_rows, match_patterns_seeded), which compares them as joins do: floats by IEEE ==, and a keyword equal to the ref of the entity it names. The exclusion-set paths already did this. Example:

(transact [[:e1 :x 1e-20] [:g :y 2e-20]])
[:find ?e :where [?e :x ?f] (not-join [?f] [?g :y ?f])]                ; :e1 (unchanged)
[:find ?e :where [?e :x ?f] (not-join [?f] [?g :y ?f] [(> ?f 0.0)])]   ; was nothing, now :e1

substitute_pattern / substitute_value had no callers left and are removed. The prepared-query substitution is separate code and is unchanged.

Engine: AntiJoin (spec §4).

Hashed body. A body is closed when its expressions and pseudo-attributes read only variables its own patterns bind. A closed body runs once, on the first pull. Its rows' cells of the imported variables become JoinKeys in a hash set.
Correlated body. Every other body runs once per outer row, starting from a new one-row Seed operator that holds the imported cells. So does a body whose first pattern's entity comes from the outer row: that costs one index probe per row and holds nothing. The new Operator::rewind(seed) restarts the body tree for each row, and the body stops at its first row.
Order and placement. Bodies are ordered by the new optimizer::plan_seeded, which counts imported variables as bound. Deferred nots run last, as on the executor. A not with no variables runs right after the first pattern.
Still on the executor. Queries whose negation calls a rule, and queries with or (until PR 2).

Test switch. optimizer::SUBPLANS (minigraf::__subplans, test-oracle only) forces bodies to run hashed or correlated.

Deviation from the spec

§4.4 runs a body correlated when its first pattern's entity is a constant or imported. Here only an imported entity makes it correlated. A body with a constant entity, such as (not [:p1 :ok true]), reads the same range for every outer row, so it is read once and hashed. Recorded in the plan (decision 7).

Measurements (#394 envelope, bench machine, base `v3` `b21708a` vs this PR, two rounds with base and PR on different NUMA nodes, swapped between rounds)

p50 of rounds 1 / 2, and peak RSS (round 1). not_probe = [:find ?e :where [?e :group 7] (not [?e :age 7])] (correlated); not_join_hash = [:find ?e :where [?e :group 7] [?e :age ?a] (not-join [?a] [?f :group 17] [?f :age ?a] [(< ?a 50)])] (hashed; on v3 the expression sends it to the executor's per-row path).

Shape	Scale	`v3`	this PR	RSS `v3` → PR
`not_probe`	100K	63.7 / 63.4 ms	2.91 / 2.86 ms	28 → 5 MiB
`not_probe`	1M	760 / 762 ms	26.8 / 26.9 ms	222 → 6 MiB
`not_probe`	10M	8.71 / 8.87 s	299 / 291 ms	1185 → 6 MiB
`not_join_hash`	100K	1.29 / 1.29 s	5.86 / 5.80 ms	43 → 6 MiB
`not_join_hash`	1M	capped (60 s)	52.9 / 53.0 ms	171 → 7 MiB
`not_join_hash`	10M	capped (60 s)	577 / 568 ms	1502 → 9 MiB

Every other workload is unchanged within noise at all three scales. Sub-100 µs shapes flip between about 20 and 50 µs on both builds (as in #602). join_3_scan at 10M: 13.2 / 13.5 s on v3, 13.6 / 13.4 s here. recursive_ancestors at 10M is capped on both.

Tests

1578 tests (1568 passing, 10 ignored), up from 1565.

tests/negation_equality_test.rs (5 tests): the changed answers on every executor path, through execute and a cursor, in memory and after a checkpoint.
Engine unit tests (6): every negation shape with each body form forced and reordering on and off, compared against the executor at six temporal settings, in memory and on file. They also check which form the planner picks, routing, multiplicity, failing expressions, and that a hashed body is read once.
tests/plan_independence_test.rs: every query now also runs with bodies forced hashed and forced correlated (12 runs per query). The matrix gains streaming engine 4/9: not, not-join, or and Distinct (#473) #546's negation shapes.
The property test's rerun also forces hashed bodies.
Optimizer unit tests (2): plan_seeded and the switch.

I checked that the oracle catches a broken AntiJoin: inverting either body form's test fails negation_matches_executor.

Docs site: project-minigraf/minigraf-docs#23

Codex review (read-only, whole diff against the spec): no findings; one speculative concern about plan_seeded placement of pseudo-attribute patterns, which the oracle and plan-independence matrix (pseudo-attributes in bodies, both body forms, reordering on/off) do not reproduce.

🤖 Generated with Claude Code

https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz

…path (#546) not / not-join bodies are matched from a seed of the outer row's imported values (match_patterns_seeded) instead of substituting them as literals, so a float matches by IEEE == and a keyword equals the ref it names on the per-row paths too, as the exclusion-set paths already did. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz

AntiJoin keeps the outer rows whose body has no row. A closed body runs once and its rows' keys of the imported variables form a hash set; any other body, and one whose first pattern's entity is imported, runs once per outer row from a Seed of the imported cells (Operator::rewind). Bodies are ordered by optimizer::plan_seeded, which counts imported variables as bound. A test-only switch (optimizer::SUBPLANS, minigraf::__subplans under test-oracle) forces either form; the plan-independence and property tests compare both. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz

codecov · 2026-10-19T04:43:05Z

Codecov Report

❌ Patch coverage is 96.76375% with 10 lines in your changes missing coverage. Please review.

Files with missing lines	Patch %	Lines
src/query/engine/anti.rs	93.24%	5 Missing ⚠️
src/query/datalog/optimizer.rs	88.46%	3 Missing ⚠️
src/query/engine/filter.rs	66.66%	1 Missing ⚠️
src/query/engine/plan.rs	99.29%	1 Missing ⚠️

📢 Thoughts on this report? Let us know!

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz

adityamukho and others added 4 commits October 19, 2026 09:26

bench(envelope): not_probe and not_join_hash workloads (#546)

645ba78

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz

docs: CHANGELOG, test counts and module notes for #546 PR 1

39c4804

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz

adityamukho and others added 2 commits October 19, 2026 10:14

test: skip the SUBPLANS thread check on wasm32 (WASI has no threads)

db48fba

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz

docs(changelog): #546 PR 1 envelope measurements

a2c5be6

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz

adityamukho merged commit c501f54 into v3 Oct 19, 2026
26 checks passed

adityamukho deleted the feat/546-not branch October 19, 2026 06:13

This was referenced Oct 19, 2026

streaming engine 4/9: not, not-join, or and Distinct (#473) #546

Closed

Benchmark regression: negation (v3) #669

Closed

Navigation Menu

Repository navigation

feat(engine): not / not-join on the streaming engine, join equality in negation bodies (#546 PR 1) - #624

feat(engine): not / not-join on the streaming engine, join equality in negation bodies (#546 PR 1)#624
adityamukho merged 6 commits into
v3from
feat/546-not

Uh oh!

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant

Conversation

Uh oh!

What changes

Deviation from the spec

Measurements (#394 envelope, bench machine, base v3 b21708a vs this PR, two rounds with base and PR on different NUMA nodes, swapped between rounds)

Tests

Uh oh!

Codecov Report

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant

Measurements (#394 envelope, bench machine, base `v3` `b21708a` vs this PR, two rounds with base and PR on different NUMA nodes, swapped between rounds)