Module promote 

MultiWayJoin promotion pass. ChainJoin promotion for 2-atom chains. Recursive-SCC promotion for occurrence-level recursive bodies.

Walks an [ExecutionPlan] (post-lowering, post-optimizer) and rewrites recognized triangle / 4-cycle / K-clique subtrees in rule.body to [RirNode::MultiWayJoin], plus recognized 2-atom chains to [RirNode::ChainJoin]. Idempotent.

Eligibility

Exact-match against the canonical lowered-and-optimized triangle shape — the same tree shape recognized by the legacy triangle executor matcher:

Project {
    input: Join {
        left: Join {
            left: Scan(rel_xy),
            right: Scan(rel_yz),
            left_keys: [1],
            right_keys: [0],
            join_type: Inner,
        },
        right: Scan(rel_xz),
        left_keys: [0, 3],
        right_keys: [0, 1],
        join_type: Inner,
    },
    columns: [Column(0), Column(1), Column(3)],
}

4-cycle has the analogous canonical lowered shape. Any deviation in shape, predicate-pushdown-altered Join, or computed-projection variants is left untouched.

Recursive SCC handling

The promoter does not blanket-skip recursive SCCs. It gates per-rule on the number of body Scans whose RelId resolves to a predicate inside the rule’s head SCC:

Recursive Scans in body	Behavior
0 (stable rule)	Promote
1 (linear recursion)	Promote
≥ 2 (multi-recursion)	Promote

Per arXiv:2604.20073, semi-naïve evaluation reasons over body-clause OCCURRENCES, not predicate names. Multi-recursive bodies including same-predicate self-recursive occurrences (e.g. tri(X,Y,Z) :- p(X,Y), p(Y,Z), q(X,Z) with p recursive) are admitted. The recursive engine (Executor::execute_recursive_scc) consumes the resulting MultiWayJoin via execute_wcoj_or_fallback_node, dispatching WCOJ kernels on the seeding pass and on each iteration’s variant. The runtime occurrence-identity rewrite at crates/xlog-runtime/src/executor/rewrite.rs:303-311 + :477-504 ensures per-variant rewrites preserve the N-th occurrence independently in MultiWayJoin.inputs and MultiWayJoin.fallback.

Fallback identity invariant

The promoter captures the exact post-optimizer subtree as MultiWayJoin.fallback. Executing fallback produces the same row set as the pre-promotion tree — guaranteed by being the identical [RirNode].

Out of scope

• Cost model, selectivity reordering, variable-ordering choices.
• Stream-aligned multiplexing and adaptive histogram resolution for recursive cliques.
• 4-way / general-arity admission beyond triangle / 4-cycle / supported K-clique and generic Free Join paths.

Functions

promote_multiway

Walk an ExecutionPlan and rewrite eligible triangle / 4-cycle subtrees in each rule body to RirNode::MultiWayJoin. Idempotent.