Repository navigation
perf(query): magic sets rewriting for demand-driven recursive rule evaluation #289
Description
Problem
The semi-naive bottom-up evaluator in RecursiveEvaluator and StratifiedEvaluator computes the complete fixed-point closure of all recursive rules before any query-level filtering is applied. For a transitive-closure rule like ancestor over a 1,000-commit git history, this means deriving ~500,000 ancestor pairs even for a query like "is commit A an ancestor of tag T?" — which only needs O(N) derivations along the relevant path.
This is the root cause of the limit-exhaustion problem reported in #288. Making the limit configurable (#288) works around the symptom; magic sets rewriting eliminates the cause.
What magic sets rewriting does
Magic sets (Beeri & Ramakrishnan 1991) is a compile-time transformation that pushes the bound variables of the top-level query back into the recursive rules as "magic predicates." The result is that only derivations reachable from the actual query bindings are computed.
Example — without magic sets:
(rule [(ancestor ?a ?b)] [?a :commit/parent ?b])
(rule [(ancestor ?a ?c)] [?a :commit/parent ?b] (ancestor ?b ?c))
;; Query: (ancestor "abc123" ?tag)
;; Evaluator derives ALL ancestor pairs for ALL commits before filtering to ?a = "abc123"
Example — with magic sets:
;; Transformed rules (done at query time, transparent to user):
(rule [(magic-ancestor ?a)] [(seed-ancestor "abc123")])
(rule [(magic-ancestor ?b)] (magic-ancestor ?a) [?a :commit/parent ?b])
(rule [(ancestor ?a ?b)] (magic-ancestor ?a) [?a :commit/parent ?b])
(rule [(ancestor ?a ?c)] (magic-ancestor ?a) [?a :commit/parent ?b] (ancestor ?b ?c))
;; Evaluator now only derives ancestors reachable from "abc123" — O(N) not O(N²)
Performance impact
| Query type | Without magic sets | With magic sets |
|---|---|---|
| Point query (bound start) | O(N²) derivations | O(N) derivations |
| Full closure query | O(N²) derivations | O(N²) derivations (same) |
| Reverse query (bound end) | O(N²) derivations | O(N) derivations with sideways info passing |
For the 986-commit git history from #288, a point query reduces from ~500K derived facts to ~1K.
Implementation sketch
- Query adornment — classify each argument in a recursive predicate as bound (
b) or free (f) based on the query's?varbindings at the call site - Magic predicate generation — for each adornment, generate a
magic-<pred>/<adornment>predicate and seed facts from the query's bound values - Rule transformation — rewrite each rule to (a) propagate magic facts through recursive calls and (b) guard the rule head with the magic predicate
- Integration point —
executor.rsexecute_query_with_rules, before handing off toStratifiedEvaluator
Scope and complexity
- Non-trivial: query adornment + rule transformation must handle mutual recursion and negation correctly
- Well-studied: clean algorithms exist in the literature (Beeri & Ramakrishnan 1991; Bancilhon et al. 1986)
- Zero user-visible API changes — transformation is internal
- Should be implemented after v1.x stabilizes; Phase 9 or dedicated query optimization phase
References
src/query/datalog/evaluator.rs—RecursiveEvaluator,StratifiedEvaluatorsrc/query/datalog/executor.rs—execute_query_with_rulessrc/query/datalog/optimizer.rs— existing selectivity-based optimizer (integration point)- Closes the root cause of feat: make max_derived_facts_per_iteration configurable (currently hard-coded at 100,000) #288 (workaround: raise/configure the derived-facts limit)
- See also: post-1.0: build query profiler #185 (query profiler) — profiling data would help validate the improvement
Related
- feat: make max_derived_facts_per_iteration configurable (currently hard-coded at 100,000) #288 — immediate workaround (raise default + make configurable, already shipped)
Activity
Merge pull request #291 from project-minigraf/feat/magic-sets-289
adityamukho commentedon Jun 4, 2026
Implemented in #291 (merged). Magic sets rewriting is always-on for positive recursive rules with bound query args. 974 tests passing.
docs: update test count to 974, add magic_sets to TEST_COVERAGE (#289)