Module com.darkcollective.relix.optimizer
Package com.darkcollective.relix.optimizer.internal

Class TransitiveEqualityPass

java.lang.Object
com.darkcollective.relix.optimizer.internal.TransitiveEqualityPass
public final class TransitiveEqualityPass extends Object
Transitive equality propagation (EQ-001) — the law that turns a one-sided filter into a filter on both sources. 

   A.x = B.x  ∧  A.x = 5    ⊨    B.x = 5

Today σ A.x = 5 (A ⨝ᴀ.ˣ⁼ᴮ.ˣ B) filters A and scans B whole, shipping every B row to the engine to be discarded by the join. Deriving B.x = 5 and placing it on B's side means — with capability-based pushdown (ADR-0011) — that both backends filter independently. That is the entire point of the rule: it is not fewer cycles, it is less data over the wire.

How the classes are built

At each ThetaJoinNode the pass gathers every top-level conjoined equality it can see from that vantage point — the join's own condition, the σ-chain above the join, and the σ-chain directly above each input (which is where JOIN-002 will have left a binding by the next sweep). Column-to-column equalities union their two operands; column-to-literal equalities bind a class. For every class with a binding, each other member gets that literal, as a σ placed directly on the side whose schema owns that column.

Column identity is textual, deliberately

A class member is the attribute reference as written, lowercased — so A.x and a bare x are different members. Stripping the qualifier first, as an equivalence over bare column names, would merge A.x and B.x into one member and make the motivating law vacuous: the two sides of an equi-join usually share a column name, which is exactly why the qualifier is the only thing distinguishing them. The cost is a missed derivation when the same column is written qualified in one conjunct and bare in another; the alternative is wrong answers.

Which side a derived predicate goes to is resolved by provenance, not by name (JoinSides): a qualified reference finds its input through the column provenance the executor itself resolves against. A member either side could own is skipped.

Soundness

  • Inner joins only. The pass matches ThetaJoinNode and nothing else. An outer join's condition does not hold of its padded rows, so an equality read out of ⟕/⟖/⟗ and pushed into the null-supplying side would delete rows the join is required to keep. (Once JOIN-004 demotes such a join to inner, it becomes eligible here — that is the intended interaction, and why the demotion runs first.)
  • Conjuncts only. Predicates.conjuncts(com.darkcollective.relix.ast.Predicate) descends ∧ and treats ∨/¬ as opaque leaves, so an equality that holds in only one branch of a disjunction is never read as a fact.
  • NULLs need no special case here. Equality is NULL-rejecting, so a row satisfying both A.x = B.x and A.x = 5 has neither column NULL; the derived B.x = 5 discards only rows the join would have discarded.

Termination

A derived predicate is redundant by construction, so the pass must not keep re-deriving it. Two things prevent that: the sweep collects existing bindings from the input σ-chains as well (so a derivation made last sweep is seen as a fact this sweep), and before emitting, the target input's whole subtree is checked for a predicate already constraining that column to that literal — which is what stops a re-emission after SEL-004 has carried the derived σ further down, out of the chain directly above the input.

Deliberately not implemented: the column-to-column half

The second law, A.x = B.x ∧ B.x = C.x ⊨ A.x = C.x, is sound and cheap to derive from the same classes. It is not emitted because nothing consumes it: the optimizer performs no join reordering at all — join shape is fixed by the query text — so an implied cross-join equality widens no search anything actually performs, and would only add a redundant predicate for the executor to evaluate. (The planner makes its cost decisions — join algorithm, build side — without touching the logical tree, so no rewrite in this space fires.) Worth revisiting if a cost-based join-order enumerator ever lands.

This class is package-private and stateless; call apply(RelNode, String, SchemaAnnotations, OptimizationContext) as a static method.