Repository navigation
fix(engine): rule delta runs join on a bound variable (#694) - #700
Merged
Merged
Conversation
A recursive rule's delta run moved the delta pattern to the front but kept the optimizer's whole-body order for the rest, so the next clause could share no variable with it. After the magic-set rewrite of (reach :n0 ?to), the run from the reach delta joined every delta row with every magic row, then probed :next once per pair: the nightly recursion/fanout/w10_d3 benchmark went from ~90 ms to 2.4-3.7 s on v3 at 97f27df. The rest of the body is now planned with optimizer::plan_after: the delta's variables seeded, and each next pattern sharing a variable with those bound before it when one does. The delta's range is listed first, so the pattern planned first takes it when an equal invocation comes before it. Answers are unchanged (oracle). Bench profile: fanout/w10_d3 4.94 s -> 22.6 ms, chain/depth_100 699 -> 41.5 ms, chain/depth_10 1.15 -> 0.68 ms. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz
Codecov Report❌ Patch coverage is
📢 Thoughts on this report? Let us know! |
This was referenced Oct 23, 2026
Closed
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Benchmark regression #694:
recursion/fanout/w10_d3onv3went from ~90 ms (v3 run 2026-10-20) to 3.7 s and 2.4 s (2026-10-21, 2026-10-22).Root cause
Bisected on the bench machine to 97f27df (#670, #548 PR 2: rule queries on the streaming engine); 84ac845 before it is 94 ms, 97f27df is 4.7 s.
A recursive rule's delta run (
rule_plan→clauses(…, first)) moved the delta pattern to the front but kept the optimizer's whole-body order for the rest. After the magic-set rewrite of(reach :n0 ?to)the rule body is(magic ?from) [?from :next ?mid] (reach ?mid ?to); the run from thereachdelta joinedmagicnext — sharing no variable with it — as a keylessHashJoin, then probed:nextonce per (delta × magic) pair: ~1.1M pending-range probes per round on a 1,110-edge tree.Fix
optimizer::plan_after(new):plan_seededwith the delta's variables seeded, plus aconnectpass — each next pattern shares a variable with those bound before it when one does (most selective of those as the bound variables stand; text order on ties; selectivity order when none shares one). Expressions,nots and pseudo-attribute patterns are placed by the existing code after it.reorder()off: unchanged (text order, delta not moved).engine::plan::clausesplans the rest of a rule body after its delta with it.Deltaeven when an equal invocation comes before it (ranges are claimed by the first equal pattern planned; answers never depended on this — Codex review finding).Answers are unchanged (every engine query runs against the executor under the oracle).
Measurements (bench machine, Criterion bench profile, base and fix in parallel on separate sockets)
Tests
engine::tests::rule_delta_runs_join_on_a_bound_variable: no delta run of the magic-set rewrite has a keyless join; fan-out answers. Fails onv3.optimizer::tests::plan_after_joins_each_pattern_on_a_bound_variable: connected order (magic body, a chain, no shared variable, reordering off).Codex review: two findings — duplicate equal invocations (no answer change; fixed the range order above) and the
reorder()-off test only covering the helper (engine path unchanged there; left as is).#694 closes by hand on merge (closing keywords do not fire on
v3).🤖 Generated with Claude Code
https://claude.ai/code/session_01PtCdzbJMSS1V8qEPaJ4jXz