Add Subplan Sharing optimization pass

[justinjoy]

Summary

Add a Subplan Sharing optimization pass that identifies and eliminates redundant sub-computations across rules within the same stratum.

Motivation

When multiple rules scan the same relation with identical filters or join the same pair of relations on the same keys, the DD plan currently generates duplicate operator chains. Subplan sharing detects these common sub-plans and merges them so the underlying DD execution evaluates each unique sub-computation only once.

Design

• New pass file: wirelog/passes/subplan_sharing.c (following fusion.c, jpp.c, sip.c pattern)
• Operates on the stratified IR before DD plan generation
• Identifies structurally equivalent sub-trees (SCAN+FILTER, JOIN with same keys) across rules in a stratum
• Rewrites the IR to share a single sub-tree, with dependent rules referencing the shared node
• Integrated into the optimization pipeline in driver.c after SIP

Acceptance Criteria

• wl_subplan_sharing_apply() pass implemented and integrated
• Unit tests covering: identical scans merged, identical scan+filter merged, distinct scans preserved
• All existing tests pass (meson test, cargo test)
• Benchmark suite runs without regression
• C lint clean (clang-format-18)

Context

Phase 1 optimization — item 8 in the roadmap. Follows JPP and SIP.

[justinjoy]

Profiling Results: Subplan Sharing Impact on DOOP

Methodology

Identified 4 duplicate rule groups in DOOP (136 rules total):

Group	Pattern	Atoms	Shared heads
1	Virtual dispatch	8-way join	Reachable, CallGraphEdge (+VarPointsTo 9-way)
2	Static invocation	2-atom	Reachable, CallGraphEdge
3	Special invocation	6-way join	Reachable, CallGraphEdge, VarPointsTo
4	VMI derived	4-way join	SimpleName, Descriptor

Created a "shared" variant that factors all 4 groups into intermediate relations (_VDispatch, _StatDispatch, _SpecDispatch, _VMILookup), computing each shared body once and projecting to multiple heads.

Ran both versions on zxing dataset (3.5M input tuples, 34 CSV files), 3 repeats each.

Results

Metric	Baseline	Shared	Delta
Median time	46,095 ms	46,961 ms	+1.9% (slower)
Peak RSS	2,643 MB	2,232 MB	-15.6% (improved)
Output tuples	5,847,534	5,992,344	+144,810 (intermediate relation overhead)

Analysis

1. No execution time improvement. The intermediate relation materialization overhead offsets any savings from reduced duplicate join computation.
2. DD already shares efficiently. Variable references in Differential Dataflow are lightweight handles — the underlying timely Stream is shared. Duplicate Variable ops do NOT duplicate data.
3. Memory reduction is real (-15.6% RSS), likely because the shared version avoids duplicating operator chain state in the DD dataflow graph.
4. Only DOOP benefits. Systematic review of all 15 benchmarks found sharing opportunities exclusively in DOOP (4 groups out of 136 rules). Polonius, Andersen, CSPA, Galen, CRDT, DDISASM, and simpler benchmarks have zero sharing candidates.

RALPLAN Consensus (Planner + Architect + Critic)

• Critic: "Profile before optimizing" — confirmed by results. Recommended redefining scope to "Multi-Head Rule Detection" or closing as wontfix.
• Architect: DD-plan-level dedup would add WL_DD_SHARED_REF op type + Rust executor changes. Permanent complexity for <2% time improvement is unjustified.
• Planner: IR-level UNION child dedup is the lowest-risk approach but addresses intra-relation duplicates (not cross-relation sharing which is what DOOP needs).

Decision

Closing as wontfix: insufficient execution time benefit. The 15.6% memory reduction is notable but does not justify the implementation complexity (new DD op type, FFI changes, Rust executor modifications).

If a future workload demonstrates >20% execution time savings from sharing, this can be revisited.

[justinjoy]

Closing: profiling shows +1.9% slower execution (within noise) with subplan sharing on DOOP. DD already shares collections efficiently. See detailed analysis above.