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 whether an expression is likely to be selective

Normalizes expressions in a plan, that either produces non-deterministic results or will be different between fixed-point and single-pass analyzer, due to the nature of bottom-up resolution. Before normalization, pre-process the plan by replacing all RuntimeReplaceable nodes with their replacements.

Normalizes plans: - Filter the filter conditions that appear in a plan. For instance, ((expr 1 && expr 2) && expr 3), (expr 1 && expr 2 && expr 3), (expr 3 && (expr 1 && expr 2) etc., will all now be equivalent. - Sample the seed will replaced by 0L. - Join conditions will be resorted by hashCode. - CTERelationDef ids will be rewritten using a monitonically increasing counter from 0. - CTERelationRef ids will be remapped based on the new CTERelationDef IDs. This is possible, because WithCTE returns cteDefs as first children, and the defs will be traversed before the refs.

Normalize RuntimeReplaceable nodes by replacing them with their replacement expressions. This is necessary because fixed-point analyzer may produce non-deterministic results when resolving original expressions. For example, in a query like:

SELECT assert_true(1)

Before resolution, we have UnresolvedFunction whose child is Literal(1). This child will first be converted to Cast(Literal(1), BooleanType) by type coercion. Because in this case Cast doesn't require timezone, the expression will be implicitly resolved. Because the child of initially unresolved function is resolved, the function can be converted to AssertTrue, which is of type InheritAnalysisRules. However, because the only child of InheritAnalysisRules is the replacement expression, the original expression will be lost and timezone will never be applied. This causes inconsistencies, because fixed-point semantic is to ALWAYS apply timezone, regardless of whether the Cast actually needs it.

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.