Repository navigation
Recursive rule query 50–10,000× slower since #700: delta run hash-joins a whole attribute (v3) #721
Description
Found while measuring #551 PR 3 (#394 envelope, bench machine). v3 only: main has no streaming engine.
Regression
recursive_ancestors, (boss :p<leaf> ?b) over the envelope's :manager tree (5–7 rows through the magic-set rewrite), with boss the usual two-rule closure:
| 100K | 1M | 10M | |
|---|---|---|---|
#548 PR 3 (2ee149a2), docs/BENCHMARKS.md |
1.45 ms | 2.14 ms | 3.04 ms |
v3 today (1096e6a2 and after) |
101 ms | 1.8 s | 35 s |
Bisected with a probe that opens the 100K fixture read-only and times the query (p50 of 12, one process per commit, each commit built in its own target directory): 05352121 2.2 ms, 4413d711 (#700, the #694 fix) 101 ms. Every commit from 2ee149a2 to 05352121 is 1.9–3.0 ms.
Cause
After the magic-set rewrite the recursive rule's body is (__magic_boss_bf ?x) [?x :manager ?y] (boss ?y ?z). The run from the boss delta binds ?y ?z first. optimizer::connect (#700) then takes the next
8000
pattern that shares a variable with them, [?x :manager ?y], which shares only its value. That join is a HashJoin { build_inner: true } holding every :manager fact, rebuilt in every round: about 11 ms per round at 100K, whether or not the delta has rows. The magic relation (one row per round here) is probed after it. Before #700 the run joined the magic relation first and probed :manager by entity.
Instrumented plan of that run (round 2):
Join { inner: Scan [?x :manager ?y], kind: Hash { build_inner: true }, keys: [v = ?y] }
Join { inner: Scan [?x :__magic_boss_bf _] (derived, Old), kind: Probe(?x) }
#694's own case (recursion/fanout, (reach :n0 ?to) with body (magic ?from) [?from :next ?mid] (reach ?mid ?to)) is the mirror image: there the shared variable is the pattern's entity side of the next join, so connect makes it a probe. In the ancestors shape it is the value side, which the engine cannot probe (no AVET over pending facts, #545 plan decision 3), so "shares a variable" is not "joins cheaply".
Fix direction (to settle)
connect should prefer a next pattern whose shared variable lets the engine probe (entity bound) over one that only shares a value. When neither is available, a keyless join on a derived relation (a magic set, usually tiny) may still beat a hash join over a whole stored attribute. A Criterion case or envelope check for the ancestors shape, next to recursion/fanout, keeps both directions covered.
Activity
test: a value probe that falls back mid-batch joins every row once (#721
style: rustfmt (#721)
adityamukho commentedon Oct 23, 2026
Fixed on v3 by #722.
Merge pull request #722 from project-minigraf/fix/721-value-probes
Merge pull request #726 from project-minigraf/fix/721-probes-alloc