join.opt

# =============================================================================
# join.opt contains normalization rules for Join operators.
# =============================================================================


# EnsureJoinFiltersAnd replaces an And operator in a Join's On condition with
# the Filters operator. This allows other rules to rely upon the presence of
# the Filters when matching. See comment at top of bool.opt for more details.
# This rule is a special-case of the EnsureJoinFilters rule, for performance
# reasons (no need to construct a new conditions list) in a common case.
[EnsureJoinFiltersAnd, Normalize]
(Join
    $left:*
    $right:*
    (And $conditions:*)
)
=>
((OpName)
    $left
    $right
    (Filters $conditions)
)

# EnsureJoinFilters adds a Filters operator to a Join's On condition if it does
# not already exist. This allows other rules to rely upon the presence of the
# Filters when matching. See comment at top of bool.opt for more details.
[EnsureJoinFilters, Normalize]
(Join
    $left:*
    $right:*
    $filter:^(Filters | And | True | False)
)
=>
((OpName)
    $left
    $right
    (Filters [ $filter ])
)

# PushFilterIntoJoinLeft pushes Join filter conditions into the left side of the
# join. This is possible in the case of InnerJoin and RightJoin, as long as the
# condition has no dependencies on the right side of the join. Left and Full
# joins are not eligible, since filtering left rows will change the number of
# rows in the result for those types of joins:
#
#   -- A row with nulls on the right side is returned for a.x=1, a.y=2, b.x=1.
#   SELECT * FROM a LEFT JOIN b ON a.x=b.x AND a.y < 0
#
#   -- But if the filter is incorrectly pushed down, then no row is returned.
#   SELECT * FROM (SELECT * FROM a WHERE a.y < 0) a LEFT JOIN b ON a.x=b.x
#
# Citations: [1]
[PushFilterIntoJoinLeft, Normalize]
(InnerJoin | InnerJoinApply | RightJoin | RightJoinApply | SemiJoin | SemiJoinApply
    $left:*
    $right:*
    $on:(Filters $list:[ ... $condition:* & (IsBoundBy $condition $left) ... ])
)
=>
((OpName)
    (Select
        $left
        (Filters (ExtractBoundConditions $list $left))
    )
    $right
    (Filters (ExtractUnboundConditions $list $left))
)

# PushFilterIntoJoinRight is symmetric with PushFilterIntoJoinLeft. It pushes
# Join filter conditions into the right side of the join rather than into the
# left side. See that rule's comments for more details.
#
# This rule triggers a cycle with the TryDecorrelateSelect rule. That rule has
# the DetectCycle tag to break the cycle.
[PushFilterIntoJoinRight, Normalize]
(InnerJoin | InnerJoinApply | LeftJoin | LeftJoinApply |
 SemiJoin | SemiJoinApply | AntiJoin | AntiJoinApply
    $left:*
    $right:*
    $on:(Filters $list:[ ... $condition:* & (IsBoundBy $condition $right) ... ])
)
=>
((OpName)
    $left
    (Select
        $right
        (Filters (ExtractBoundConditions $list $right))
    )
    (Filters (ExtractUnboundConditions $list $right))
)

# DecorrelateJoin maps an apply join into the corresponding join without an
# apply if the right side of the join is not correlated with the left side.
# This allows the optimizer to consider additional physical join operators that
# are unable to handle correlated inputs.
#
# NOTE: Keep this before other decorrelation patterns, as if the correlated
#       join can be removed first, it avoids unnecessarily matching other
#       patterns that only exist to get to this pattern.
#
# Citations: [3]
[DecorrelateJoin, Normalize]
(JoinApply
    $left:*
    $right:* & ^(IsCorrelated $right $left)
    $on:*
)
=>
(RemoveApply (OpName) $left $right $on)

# TryDecorrelateSelect "pushes down" the join apply into the select operator,
# in order to eliminate any correlation between the select filter list and the
# left side of the join, and also to keep "digging" down to find and eliminate
# other unnecessary correlation. Eventually, the hope is to trigger the
# DecorrelateJoin pattern to turn the JoinApply operator into a non-apply Join
# operator.
#
# This rule triggers a cycle with the PushFilterIntoJoinRight rule. Because this
# rule has the DetectCycle tag, it is skipped once a cycle is detected. This
# gives the PushFilterIntoJoinRight rule one last chance to push Select into the
# right input, and therefore causes the normal form to be (Join (Select)) rather
# than (Select (Join)) when the choice is ambiguous.
#
# Note that citation [3] doesn't directly contain this identity, since it
# assumes that the Select will be hoisted above the Join rather than becoming
# part of its On condition. PushFilterIntoJoinRight allows the condition to be
# pushed down, so this rule can correctly pull it up.
#
# Citations: [3]
[TryDecorrelateSelect, Normalize, DetectCycle]
(InnerJoinApply | LeftJoinApply | SemiJoinApply | AntiJoinApply
    $left:*
    $right:(Select $input:* $filter:*) & (HasOuterCols $right)
    $on:*
)
=>
((OpName)
    $left
    $input
    (ConcatFilters $on $filter)
)