Struct SemiJoinPushdownThroughInnerJoin 

pub struct SemiJoinPushdownThroughInnerJoin { /* private fields */ }

Push an existing semi-join down through an inner join, so the selective side filters one join input instead of the join’s output.

The query that motivated this

TPC-H q18’s o_orderkey IN (SELECT l_orderkey … HAVING sum(l_quantity) > 300) decorrelates to a semi-join, and DataFusion leaves it at the very top:

HashJoin [RightSemi] on (l_orderkey, o_orderkey)      300.92 s
  Filter: sum(l_quantity) > 300                        <- keeps ~570 of 150M orders
    Aggregate: groupBy=[l_orderkey]
  HashJoin [Inner] on (o_orderkey, l_orderkey)         764.03 s  <- all 600M rows
    HashJoin [Inner] on (c_custkey, o_custkey)          68.07 s

Measured at SF100 the joins are 82.9% of the query and the aggregate only 16.9%, so this is a join-ordering problem, not an aggregation one. The most selective predicate in the whole query — 570 surviving orders out of 150M — executes last, after the 764 s join has already materialised the full customer/orders/lineitem cross-section.

The rewrite

For an inner join whose output feeds a semi- or anti-join keyed on columns from only one side:

  SemiJoin(Inner(A, B), S)  on A.k     ==>  Inner(SemiJoin(A, S) on A.k, B)
  AntiJoin(Inner(A, B), S)  on A.k     ==>  Inner(AntiJoin(A, S) on A.k, B)

Anti joins and residual filters

Both were originally refused — anti joins as needing “their own reasoning”, and any join carrying a residual filter because it “may reference both sides”. Between them those two guards made the rule inert on TPC-H q21, whose EXISTS/NOT EXISTS produce exactly a semi and an anti join, each carrying l_suppkey <> l_suppkey. q21 was the slowest query in the SF100 sweep at 4309 s against Spark’s 391 s — the largest single loss of the 22 — with the most selective predicate in the query running above the whole four-way join.

The reasoning does carry over. For both kinds the existence test is a function of the filtered row and the probe alone, so a row of Inner(A, B) passes exactly when its A row passes. The residual is carried down and remapped at each level (see remap_residual) rather than refused, and re-attached only where every column it names resolves into the child being landed on or the probe.

Why it is safe

• The join below must be Inner. An outer join null-pads its non-preserved side, so a key that is null after the join was not null before it, and filtering earlier would keep different rows.
• Every semi-join key must resolve into one side. If the keys straddle A and B, the existence test genuinely depends on the joined row and cannot be evaluated before the join. The same test is applied to the residual’s columns.
• Row multiplicity is preserved. A semi-join emits each surviving row at most once and adds no columns, so Inner(SemiJoin(A,S), B) produces exactly the rows of Inner(A,B) whose A.k had a match — which is the definition of the original. Counts and sums downstream are unchanged.
• The output schema is identical. Semi-joins project only their filtered side, so A ⧺ B in both forms, in the same order.

The outer semi-join is replaced rather than duplicated, so there is no fixed-point concern: after one application the top node is an inner join.

Implementations

impl SemiJoinPushdownThroughInnerJoin

pub fn forced() -> Self

The rule with its env gate bypassed, for tests and explicit opt-in.

Trait Implementations

impl Debug for SemiJoinPushdownThroughInnerJoin

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for SemiJoinPushdownThroughInnerJoin

fn default() -> SemiJoinPushdownThroughInnerJoin

Returns the “default value” for a type.

impl OptimizerRule for SemiJoinPushdownThroughInnerJoin

fn name(&self) -> &str

A human readable name for this optimizer rule

fn apply_order(&self) -> Option<ApplyOrder>

How should the rule be applied by the optimizer? See comments on ApplyOrder for details.

fn rewrite( &self, plan: LogicalPlan, _config: &dyn OptimizerConfig, ) -> Result<Transformed<LogicalPlan>>

Try to rewrite plan to an optimized form, returning Transformed::yes if the plan was rewritten and Transformed::no if it was not.

fn supports_rewrite(&self) -> bool

👎Deprecated since 47.0.0:

This method is no longer used

Does this rule support rewriting owned plans (rather than by reference)?