Builds a balanced output predicate in bottom up approach, by applying binary operator op pair by pair on input predicates exprs recursively. Example: exprs = [a, b, c, d], op = And, returns (a And b) And (c And d) exprs = [a, b, c, d, e, f], op = And, returns ((a And b) And (c And d)) And (e And f)

Returns true if expr can be evaluated using only the output of plan. This method can be used to determine when it is acceptable to move expression evaluation within a query plan.

For example consider a join between two relations R(a, b) and S(c, d).

- canEvaluate(EqualTo(a,b), R) returns true - canEvaluate(EqualTo(a,c), R) returns false - canEvaluate(Literal(1), R) returns true as literals CAN be evaluated on any plan

Returns true iff expr could be evaluated as a condition within join.

Returns a filter that its reference is a subset of outputSet and it contains the maximum constraints from condition. This is used for predicate pushdown. When there is no such filter, None is returned.

Find the origin of where the input references of expression exp were scanned in the tree of plan, and if they originate from a single leaf node. Returns optional tuple with Expression, undoing any projections and aliasing that has been done along the way from plan to origin, and the origin LeafNode plan from which all the exp

Returns the inner query expressions that are guaranteed to have a single value for each outer row. Therefore, a scalar subquery is allowed to group-by on these expressions. We can derive these from correlated equality predicates, though we need to take care about propagating this through operators like OUTER JOIN or UNION.

Positive examples: - x = outer(a) AND y = outer(b) - x = 1 - x = outer(a) + 1 - cast(x as date) = current_date() + outer(b)

Negative examples: - x <= outer(a) - x + y = outer(a) - x = outer(a) OR y = outer(b) - y + outer(b) = 1 (this and similar expressions could be supported, but very carefully) - An equality under the right side of a LEFT OUTER JOIN, e.g. select *, (select count(*) from y left join (select * from z where z1 = x1) sub on y2 = z2 group by z1) from x; - An equality under UNION e.g. select *, (select count(*) from (select * from y where y1 = x1 union all select * from y) group by y1) from x;

Returns the correlated predicates from a logical plan. The OuterReference wrapper is removed before returning the predicate to the caller.

Returns all the expressions that have outer references from a logical plan. Currently only Filter operator can host outer references.

Given an expression, returns the expressions which have outer references. Aggregate expressions are treated in a special way. If the children of aggregate expression contains an outer reference, then the entire aggregate expression is marked as an outer reference. Example (SQL):

SELECT a FROM l GROUP by 1 HAVING EXISTS (SELECT 1 FROM r WHERE d < min(b))

In the above case, we want to mark the entire min(b) as an outer reference OuterReference(min(b)) instead of min(OuterReference(b)). TODO: Currently we don't allow deep correlation. Also, we don't allow mixing of outer references and local references under an aggregate expression. For example (SQL):

SELECT .. FROM p1
WHERE EXISTS (SELECT ...
              FROM p2
              WHERE EXISTS (SELECT ...
                            FROM sq
                            WHERE min(p1.a + p2.b) = sq.c))

SELECT .. FROM p1
WHERE EXISTS (SELECT ...
              FROM p2
              WHERE EXISTS (SELECT ...
                            FROM sq
                            WHERE min(p1.a) + max(p2.b) = sq.c))

SELECT .. FROM p1
WHERE EXISTS (SELECT ...
              FROM p2
              WHERE EXISTS (SELECT ...
                            FROM sq
                            WHERE min(p1.a + sq.c) > 1))

The code below needs to change when we support the above cases.

Returns whether an expression is likely to be selective

Merge an Alias(Alias(x)) into Alias(x) preserving metadata.

If the outer alias has explicit metadata, it is preserved. Else if the inner alias has explicit metadata, the result has explicit outer.metadata. Else both are deriving the metadata. the result is deriving metadata, with the union of noninheritable keys.

Merge any stack of aliases under the top-level alias, and then drops any aliases deeper in the expression tree. So Alias1(Alias2(Alias3(Foo(Alias4(x))))) becomes Alias5(Foo(x)) where Alias5 preserves the metadata of Alias{1,2,3} and the name and exprId of Alias1. Alias4 is simply removed.

Replace all attributes, that reference an alias, with the aliased expression

Replace all attributes, that reference an alias, with the aliased expression, but keep the name of the outermost attribute.