Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package com.facebook.presto.sql.planner.optimizations;
 
 
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
 import static com.facebook.presto.sql.ExpressionUtils.and;
 import static com.facebook.presto.sql.ExpressionUtils.combineConjuncts;
 import static com.facebook.presto.sql.ExpressionUtils.expressionOrNullSymbols;
 import static com.facebook.presto.sql.ExpressionUtils.extractConjuncts;
 import static com.facebook.presto.sql.ExpressionUtils.stripNonDeterministicConjuncts;
 import static com.facebook.presto.sql.analyzer.ExpressionAnalyzer.getExpressionTypes;
 import static com.facebook.presto.sql.planner.DeterminismEvaluator.isDeterministic;
 import static com.facebook.presto.sql.planner.EqualityInference.createEqualityInference;
 import static com.facebook.presto.sql.planner.plan.JoinNode.Type.CROSS;
 import static com.facebook.presto.sql.planner.plan.JoinNode.Type.FULL;
 import static com.facebook.presto.sql.planner.plan.JoinNode.Type.INNER;
 import static com.facebook.presto.sql.planner.plan.JoinNode.Type.LEFT;
 import static com.facebook.presto.sql.planner.plan.JoinNode.Type.RIGHT;
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.base.Preconditions.checkState;
 import static com.google.common.base.Predicates.equalTo;
 import static com.google.common.base.Predicates.in;
 import static com.google.common.base.Predicates.not;
 import static com.google.common.collect.Iterables.filter;
 import static com.google.common.collect.Iterables.transform;
 
 public class PredicatePushDown
         extends PlanOptimizer
 {
     private static final Logger log = Logger.get(PredicatePushDown.class);
 
     private final Metadata metadata;
    private final SqlParser sqlParser;
    public PredicatePushDown(Metadata metadataSqlParser sqlParser)
    {
        this. = checkNotNull(metadata"metadata is null");
        this. = checkNotNull(sqlParser"sqlParser is null");
    }
    @Override
    public PlanNode optimize(PlanNode planSession sessionMap<SymbolTypetypesSymbolAllocator symbolAllocatorPlanNodeIdAllocator idAllocator)
    {
        checkNotNull(plan"plan is null");
        checkNotNull(session"session is null");
        checkNotNull(types"types is null");
        checkNotNull(idAllocator"idAllocator is null");
        return PlanRewriter.rewriteWith(new Rewriter(symbolAllocatoridAllocatorsession), plan.);
    }
    private static class Rewriter
            extends PlanRewriter<Expression>
    {
        private final SymbolAllocator symbolAllocator;
        private final PlanNodeIdAllocator idAllocator;
        private final Metadata metadata;
        private final SqlParser sqlParser;
        private final Session session;
        private Rewriter(
                SymbolAllocator symbolAllocator,
                PlanNodeIdAllocator idAllocator,
                Metadata metadata,
                SqlParser sqlParser,
                Session session)
        {
            this. = checkNotNull(symbolAllocator"symbolAllocator is null");
            this. = checkNotNull(idAllocator"idAllocator is null");
            this. = checkNotNull(metadata"metadata is null");
            this. = checkNotNull(sqlParser"sqlParser is null");
            this. = checkNotNull(session"session is null");
        }
        @Override
        public PlanNode visitPlan(PlanNode nodeRewriteContext<Expressioncontext)
        {
            PlanNode rewrittenNode = context.defaultRewrite(node.);
            if (!context.get().equals(.)) {
                // Drop in a FilterNode b/c we cannot push our predicate down any further
                rewrittenNode = new FilterNode(.getNextId(), rewrittenNodecontext.get());
            }
            return rewrittenNode;
        }
        @Override
        public PlanNode visitExchange(ExchangeNode nodeRewriteContext<Expressioncontext)
        {
            boolean modified = false;
            ImmutableList.Builder<PlanNodebuilder = ImmutableList.builder();
            for (int i = 0; i < node.getSources().size(); i++) {
                Map<SymbolQualifiedNameReferenceoutputsToInputs = new HashMap<>();
                for (int index = 0; index < node.getInputs().get(i).size(); index++) {
                    outputsToInputs.put(
                            node.getOutputSymbols().get(index),
                            node.getInputs().get(i).get(index).toQualifiedNameReference());
                }
                Expression sourcePredicate = ExpressionTreeRewriter.rewriteWith(new ExpressionSymbolInliner(outputsToInputs), context.get());
                PlanNode source = node.getSources().get(i);
                PlanNode rewrittenSource = context.rewrite(sourcesourcePredicate);
                if (rewrittenSource != source) {
                    modified = true;
                }
                builder.add(rewrittenSource);
            }
            if (modified) {
                return new ExchangeNode(
                        node.getId(),
                        node.getType(),
                        node.getPartitionKeys(),
                        node.getHashSymbol(),
                        builder.build(),
                        node.getOutputSymbols(),
                        node.getInputs());
            }
            return node;
        }
        @Override
        public PlanNode visitProject(ProjectNode nodeRewriteContext<Expressioncontext)
        {
            Set<SymboldeterministicSymbols = node.getAssignments().entrySet().stream()
                    .filter(entry -> DeterminismEvaluator.isDeterministic(entry.getValue()))
                    .map(Map.Entry::getKey)
                    .collect(Collectors.toSet());
            java.util.function.Predicate<Expressiondeterministic = conjunct -> DependencyExtractor.extractAll(conjunct).stream()
                    .allMatch(deterministicSymbols::contains);
            Map<BooleanList<Expression>> conjuncts = extractConjuncts(context.get()).stream().collect(Collectors.partitioningBy(deterministic));
            // Push down conjuncts from the inherited predicate that don't depend on non-deterministic assignments
            PlanNode rewrittenNode = context.defaultRewrite(node,
                    ExpressionTreeRewriter.rewriteWith(new ExpressionSymbolInliner(node.getAssignments()), combineConjuncts(conjuncts.get(true))));
            // All non-deterministic conjuncts, if any, will be in the filter node.
            if (!conjuncts.get(false).isEmpty()) {
                rewrittenNode = new FilterNode(.getNextId(), rewrittenNodecombineConjuncts(conjuncts.get(false)));
            }
            return rewrittenNode;
        }
        @Override
        public PlanNode visitMarkDistinct(MarkDistinctNode nodeRewriteContext<Expressioncontext)
        {
            checkState(!DependencyExtractor.extractUnique(context.get()).contains(node.getMarkerSymbol()), "predicate depends on marker symbol");
            return context.defaultRewrite(nodecontext.get());
        }
        @Override
        public PlanNode visitSort(SortNode nodeRewriteContext<Expressioncontext)
        {
            return context.defaultRewrite(nodecontext.get());
        }
        @Override
        public PlanNode visitUnion(UnionNode nodeRewriteContext<Expressioncontext)
        {
            boolean modified = false;
            ImmutableList.Builder<PlanNodebuilder = ImmutableList.builder();
            for (int i = 0; i < node.getSources().size(); i++) {
                Expression sourcePredicate = ExpressionTreeRewriter.rewriteWith(new ExpressionSymbolInliner(node.sourceSymbolMap(i)), context.get());
                PlanNode source = node.getSources().get(i);
                PlanNode rewrittenSource = context.rewrite(sourcesourcePredicate);
                if (rewrittenSource != source) {
                    modified = true;
                }
                builder.add(rewrittenSource);
            }
            if (modified) {
                return new UnionNode(node.getId(), builder.build(), node.getSymbolMapping());
            }
            return node;
        }
        @Override
        public PlanNode visitFilter(FilterNode nodeRewriteContext<Expressioncontext)
        {
            return context.rewrite(node.getSource(), combineConjuncts(node.getPredicate(), context.get()));
        }
        @Override
        public PlanNode visitJoin(JoinNode nodeRewriteContext<Expressioncontext)
        {
            Expression inheritedPredicate = context.get();
            boolean isCrossJoin = (node.getType() == ..);
            // See if we can rewrite outer joins in terms of a plain inner join
            node = tryNormalizeToInnerJoin(nodeinheritedPredicate);
            Expression leftEffectivePredicate = EffectivePredicateExtractor.extract(node.getLeft(), .getTypes());
            Expression rightEffectivePredicate = EffectivePredicateExtractor.extract(node.getRight(), .getTypes());
            Expression joinPredicate = extractJoinPredicate(node);
            Expression leftPredicate;
            Expression rightPredicate;
            Expression postJoinPredicate;
            Expression newJoinPredicate;
            switch (node.getType()) {
                case :
                    InnerJoinPushDownResult innerJoinPushDownResult = processInnerJoin(inheritedPredicate,
                            leftEffectivePredicate,
                            rightEffectivePredicate,
                            joinPredicate,
                            node.getLeft().getOutputSymbols());
                    leftPredicate = innerJoinPushDownResult.getLeftPredicate();
                    rightPredicate = innerJoinPushDownResult.getRightPredicate();
                    postJoinPredicate = innerJoinPushDownResult.getPostJoinPredicate();
                    newJoinPredicate = innerJoinPushDownResult.getJoinPredicate();
                    break;
                case :
                    OuterJoinPushDownResult leftOuterJoinPushDownResult = processLimitedOuterJoin(inheritedPredicate,
                            leftEffectivePredicate,
                            rightEffectivePredicate,
                            joinPredicate,
                            node.getLeft().getOutputSymbols());
                    leftPredicate = leftOuterJoinPushDownResult.getOuterJoinPredicate();
                    rightPredicate = leftOuterJoinPushDownResult.getInnerJoinPredicate();
                    postJoinPredicate = leftOuterJoinPushDownResult.getPostJoinPredicate();
                    newJoinPredicate = joinPredicate// Use the same as the original
                    break;
                case :
                    OuterJoinPushDownResult rightOuterJoinPushDownResult = processLimitedOuterJoin(inheritedPredicate,
                            rightEffectivePredicate,
                            leftEffectivePredicate,
                            joinPredicate,
                            node.getRight().getOutputSymbols());
                    leftPredicate = rightOuterJoinPushDownResult.getInnerJoinPredicate();
                    rightPredicate = rightOuterJoinPushDownResult.getOuterJoinPredicate();
                    postJoinPredicate = rightOuterJoinPushDownResult.getPostJoinPredicate();
                    newJoinPredicate = joinPredicate// Use the same as the original
                    break;
                case :
                    leftPredicate = .;
                    rightPredicate = .;
                    postJoinPredicate = inheritedPredicate;
                    newJoinPredicate = joinPredicate;
                    break;
                default:
                    throw new UnsupportedOperationException("Unsupported join type: " + node.getType());
            }
            PlanNode leftSource = context.rewrite(node.getLeft(), leftPredicate);
            PlanNode rightSource = context.rewrite(node.getRight(), rightPredicate);
            PlanNode output = node;
            if (leftSource != node.getLeft() || rightSource != node.getRight() || !newJoinPredicate.equals(joinPredicate) || isCrossJoin) {
                List<JoinNode.EquiJoinClausecriteria = node.getCriteria();
                // Rewrite criteria and add projections if there is a new join predicate
                if (!newJoinPredicate.equals(joinPredicate) || isCrossJoin) {
                    // Create identity projections for all existing symbols
                    ImmutableMap.Builder<SymbolExpressionleftProjections = ImmutableMap.builder();
                    leftProjections.putAll(node.getLeft()
                            .getOutputSymbols().stream()
                            .collect(Collectors.toMap(key -> key, Symbol::toQualifiedNameReference)));
                    ImmutableMap.Builder<SymbolExpressionrightProjections = ImmutableMap.builder();
                    rightProjections.putAll(node.getRight()
                            .getOutputSymbols().stream()
                            .collect(Collectors.toMap(key -> key, Symbol::toQualifiedNameReference)));
                    // HACK! we don't support cross joins right now, so put in a simple fake join predicate instead if all of the join clauses got simplified out
                    // TODO: remove this code when cross join support is added
                    Iterable<ExpressionsimplifiedJoinConjuncts = transform(extractConjuncts(newJoinPredicate), this::simplifyExpression);
                    simplifiedJoinConjuncts = filter(simplifiedJoinConjunctsnot(Predicates.<Expression>equalTo(.)));
                    if (Iterables.isEmpty(simplifiedJoinConjuncts)) {
                        simplifiedJoinConjuncts = ImmutableList.<Expression>of(new ComparisonExpression(..new LongLiteral("0"), new LongLiteral("0")));
                    }
                    // Create new projections for the new join clauses
                    ImmutableList.Builder<JoinNode.EquiJoinClausebuilder = ImmutableList.builder();
                    for (Expression conjunct : simplifiedJoinConjuncts) {
                        checkState(joinEqualityExpression(node.getLeft().getOutputSymbols()).apply(conjunct), "Expected join predicate to be a valid join equality");
                        ComparisonExpression equality = (ComparisonExpressionconjunct;
                        boolean alignedComparison = Iterables.all(DependencyExtractor.extractUnique(equality.getLeft()), in(node.getLeft().getOutputSymbols()));
                        Expression leftExpression = (alignedComparison) ? equality.getLeft() : equality.getRight();
                        Expression rightExpression = (alignedComparison) ? equality.getRight() : equality.getLeft();
                        Symbol leftSymbol = .newSymbol(leftExpressionextractType(leftExpression));
                        leftProjections.put(leftSymbolleftExpression);
                        Symbol rightSymbol = .newSymbol(rightExpressionextractType(rightExpression));
                        rightProjections.put(rightSymbolrightExpression);
                        builder.add(new JoinNode.EquiJoinClause(leftSymbolrightSymbol));
                    }
                    leftSource = new ProjectNode(.getNextId(), leftSourceleftProjections.build());
                    rightSource = new ProjectNode(.getNextId(), rightSourcerightProjections.build());
                    criteria = builder.build();
                }
                output = new JoinNode(node.getId(), node.getType(), leftSourcerightSourcecriterianode.getLeftHashSymbol(), node.getRightHashSymbol());
            }
            if (!postJoinPredicate.equals(.)) {
                output = new FilterNode(.getNextId(), outputpostJoinPredicate);
            }
            return output;
        }
        private OuterJoinPushDownResult processLimitedOuterJoin(Expression inheritedPredicateExpression outerEffectivePredicateExpression innerEffectivePredicateExpression joinPredicateCollection<SymbolouterSymbols)
        {
            checkArgument(Iterables.all(DependencyExtractor.extractUnique(outerEffectivePredicate), in(outerSymbols)), "outerEffectivePredicate must only contain symbols from outerSymbols");
            checkArgument(Iterables.all(DependencyExtractor.extractUnique(innerEffectivePredicate), not(in(outerSymbols))), "innerEffectivePredicate must not contain symbols from outerSymbols");
            ImmutableList.Builder<ExpressionouterPushdownConjuncts = ImmutableList.builder();
            ImmutableList.Builder<ExpressioninnerPushdownConjuncts = ImmutableList.builder();
            ImmutableList.Builder<ExpressionpostJoinConjuncts = ImmutableList.builder();
            // Strip out non-deterministic conjuncts
            postJoinConjuncts.addAll(filter(extractConjuncts(inheritedPredicate), not(DeterminismEvaluator::isDeterministic)));
            inheritedPredicate = stripNonDeterministicConjuncts(inheritedPredicate);
            outerEffectivePredicate = stripNonDeterministicConjuncts(outerEffectivePredicate);
            innerEffectivePredicate = stripNonDeterministicConjuncts(innerEffectivePredicate);
            joinPredicate = stripNonDeterministicConjuncts(joinPredicate);
            // Generate equality inferences
            EqualityInference inheritedInference = createEqualityInference(inheritedPredicate);
            EqualityInference outerInference = createEqualityInference(inheritedPredicateouterEffectivePredicate);
            EqualityInference.EqualityPartition equalityPartition = inheritedInference.generateEqualitiesPartitionedBy(in(outerSymbols));
            Expression outerOnlyInheritedEqualities = combineConjuncts(equalityPartition.getScopeEqualities());
            EqualityInference potentialNullSymbolInference = createEqualityInference(outerOnlyInheritedEqualitiesouterEffectivePredicateinnerEffectivePredicatejoinPredicate);
            EqualityInference potentialNullSymbolInferenceWithoutInnerInferred = createEqualityInference(outerOnlyInheritedEqualitiesouterEffectivePredicatejoinPredicate);
            // Sort through conjuncts in inheritedPredicate that were not used for inference
            for (Expression conjunct : EqualityInference.nonInferrableConjuncts(inheritedPredicate)) {
                Expression outerRewritten = outerInference.rewriteExpression(conjunctin(outerSymbols));
                if (outerRewritten != null) {
                    outerPushdownConjuncts.add(outerRewritten);
                    // A conjunct can only be pushed down into an inner side if it can be rewritten in terms of the outer side
                    Expression innerRewritten = potentialNullSymbolInference.rewriteExpression(outerRewrittennot(in(outerSymbols)));
                    if (innerRewritten != null) {
                        innerPushdownConjuncts.add(innerRewritten);
                    }
                }
                else {
                    postJoinConjuncts.add(conjunct);
                }
            }
            // See if we can push down any outer or join predicates to the inner side
            for (Expression conjunct : EqualityInference.nonInferrableConjuncts(and(outerEffectivePredicatejoinPredicate))) {
                Expression rewritten = potentialNullSymbolInference.rewriteExpression(conjunctnot(in(outerSymbols)));
                if (rewritten != null) {
                    innerPushdownConjuncts.add(rewritten);
                }
            }
            // TODO: consider adding join predicate optimizations to outer joins
            // Add the equalities from the inferences back in
            outerPushdownConjuncts.addAll(equalityPartition.getScopeEqualities());
            postJoinConjuncts.addAll(equalityPartition.getScopeComplementEqualities());
            postJoinConjuncts.addAll(equalityPartition.getScopeStraddlingEqualities());
            innerPushdownConjuncts.addAll(potentialNullSymbolInferenceWithoutInnerInferred.generateEqualitiesPartitionedBy(not(in(outerSymbols))).getScopeEqualities());
            return new OuterJoinPushDownResult(combineConjuncts(outerPushdownConjuncts.build()),
                    combineConjuncts(innerPushdownConjuncts.build()),
                    combineConjuncts(postJoinConjuncts.build()));
        }
        private static class OuterJoinPushDownResult
        {
            private final Expression outerJoinPredicate;
            private final Expression innerJoinPredicate;
            private final Expression postJoinPredicate;
            private OuterJoinPushDownResult(Expression outerJoinPredicateExpression innerJoinPredicateExpression postJoinPredicate)
            {
                this. = outerJoinPredicate;
                this. = innerJoinPredicate;
                this. = postJoinPredicate;
            }
            private Expression getOuterJoinPredicate()
            {
                return ;
            }
            private Expression getInnerJoinPredicate()
            {
                return ;
            }
            private Expression getPostJoinPredicate()
            {
                return ;
            }
        }
        private InnerJoinPushDownResult processInnerJoin(Expression inheritedPredicateExpression leftEffectivePredicateExpression rightEffectivePredicateExpression joinPredicateCollection<SymbolleftSymbols)
        {
            checkArgument(Iterables.all(DependencyExtractor.extractUnique(leftEffectivePredicate), in(leftSymbols)), "leftEffectivePredicate must only contain symbols from leftSymbols");
            checkArgument(Iterables.all(DependencyExtractor.extractUnique(rightEffectivePredicate), not(in(leftSymbols))), "rightEffectivePredicate must not contain symbols from leftSymbols");
            ImmutableList.Builder<ExpressionleftPushDownConjuncts = ImmutableList.builder();
            ImmutableList.Builder<ExpressionrightPushDownConjuncts = ImmutableList.builder();
            ImmutableList.Builder<ExpressionjoinConjuncts = ImmutableList.builder();
            // Strip out non-deterministic conjuncts
            joinConjuncts.addAll(filter(extractConjuncts(inheritedPredicate), not(DeterminismEvaluator::isDeterministic)));
            inheritedPredicate = stripNonDeterministicConjuncts(inheritedPredicate);
            joinConjuncts.addAll(filter(extractConjuncts(joinPredicate), not(DeterminismEvaluator::isDeterministic)));
            joinPredicate = stripNonDeterministicConjuncts(joinPredicate);
            leftEffectivePredicate = stripNonDeterministicConjuncts(leftEffectivePredicate);
            rightEffectivePredicate = stripNonDeterministicConjuncts(rightEffectivePredicate);
            // Generate equality inferences
            EqualityInference allInference = createEqualityInference(inheritedPredicateleftEffectivePredicaterightEffectivePredicatejoinPredicate);
            EqualityInference allInferenceWithoutLeftInferred = createEqualityInference(inheritedPredicaterightEffectivePredicatejoinPredicate);
            EqualityInference allInferenceWithoutRightInferred = createEqualityInference(inheritedPredicateleftEffectivePredicatejoinPredicate);
            // Sort through conjuncts in inheritedPredicate that were not used for inference
            for (Expression conjunct : EqualityInference.nonInferrableConjuncts(inheritedPredicate)) {
                Expression leftRewrittenConjunct = allInference.rewriteExpression(conjunctin(leftSymbols));
                if (leftRewrittenConjunct != null) {
                    leftPushDownConjuncts.add(leftRewrittenConjunct);
                }
                Expression rightRewrittenConjunct = allInference.rewriteExpression(conjunctnot(in(leftSymbols)));
                if (rightRewrittenConjunct != null) {
                    rightPushDownConjuncts.add(rightRewrittenConjunct);
                }
                // Drop predicate after join only if unable to push down to either side
                if (leftRewrittenConjunct == null && rightRewrittenConjunct == null) {
                    joinConjuncts.add(conjunct);
                }
            }
            // See if we can push the right effective predicate to the left side
            for (Expression conjunct : EqualityInference.nonInferrableConjuncts(rightEffectivePredicate)) {
                Expression rewritten = allInference.rewriteExpression(conjunctin(leftSymbols));
                if (rewritten != null) {
                    leftPushDownConjuncts.add(rewritten);
                }
            }
            // See if we can push the left effective predicate to the right side
            for (Expression conjunct : EqualityInference.nonInferrableConjuncts(leftEffectivePredicate)) {
                Expression rewritten = allInference.rewriteExpression(conjunctnot(in(leftSymbols)));
                if (rewritten != null) {
                    rightPushDownConjuncts.add(rewritten);
                }
            }
            // See if we can push any parts of the join predicates to either side
            for (Expression conjunct : EqualityInference.nonInferrableConjuncts(joinPredicate)) {
                Expression leftRewritten = allInference.rewriteExpression(conjunctin(leftSymbols));
                if (leftRewritten != null) {
                    leftPushDownConjuncts.add(leftRewritten);
                }
                Expression rightRewritten = allInference.rewriteExpression(conjunctnot(in(leftSymbols)));
                if (rightRewritten != null) {
                    rightPushDownConjuncts.add(rightRewritten);
                }
                if (leftRewritten == null && rightRewritten == null) {
                    joinConjuncts.add(conjunct);
                }
            }
            // Add equalities from the inference back in
            leftPushDownConjuncts.addAll(allInferenceWithoutLeftInferred.generateEqualitiesPartitionedBy(in(leftSymbols)).getScopeEqualities());
            rightPushDownConjuncts.addAll(allInferenceWithoutRightInferred.generateEqualitiesPartitionedBy(not(in(leftSymbols))).getScopeEqualities());
            joinConjuncts.addAll(allInference.generateEqualitiesPartitionedBy(in(leftSymbols)).getScopeStraddlingEqualities()); // scope straddling equalities get dropped in as part of the join predicate
            // Since we only currently support equality in join conjuncts, factor out the non-equality conjuncts to a post-join filter
            List<ExpressionjoinConjunctsList = joinConjuncts.build();
            List<ExpressionpostJoinConjuncts = ImmutableList.copyOf(filter(joinConjunctsListnot(joinEqualityExpression(leftSymbols))));
            joinConjunctsList = ImmutableList.copyOf(filter(joinConjunctsListjoinEqualityExpression(leftSymbols)));
            return new InnerJoinPushDownResult(combineConjuncts(leftPushDownConjuncts.build()), combineConjuncts(rightPushDownConjuncts.build()), combineConjuncts(joinConjunctsList), combineConjuncts(postJoinConjuncts));
        }
        private static class InnerJoinPushDownResult
        {
            private final Expression leftPredicate;
            private final Expression rightPredicate;
            private final Expression joinPredicate;
            private final Expression postJoinPredicate;
            private InnerJoinPushDownResult(Expression leftPredicateExpression rightPredicateExpression joinPredicateExpression postJoinPredicate)
            {
                this. = leftPredicate;
                this. = rightPredicate;
                this. = joinPredicate;
                this. = postJoinPredicate;
            }
            private Expression getLeftPredicate()
            {
                return ;
            }
            private Expression getRightPredicate()
            {
                return ;
            }
            private Expression getJoinPredicate()
            {
                return ;
            }
            private Expression getPostJoinPredicate()
            {
                return ;
            }
        }
        private static Expression extractJoinPredicate(JoinNode joinNode)
        {
            ImmutableList.Builder<Expressionbuilder = ImmutableList.builder();
            for (JoinNode.EquiJoinClause equiJoinClause : joinNode.getCriteria()) {
                builder.add(equalsExpression(equiJoinClause.getLeft(), equiJoinClause.getRight()));
            }
            return combineConjuncts(builder.build());
        }
        private static Expression equalsExpression(Symbol symbol1Symbol symbol2)
        {
            return new ComparisonExpression(..,
                    new QualifiedNameReference(symbol1.toQualifiedName()),
                    new QualifiedNameReference(symbol2.toQualifiedName()));
        }
        private Type extractType(Expression expression)
        {
            return getExpressionTypes(.getTypes(), expression).get(expression);
        }
        private JoinNode tryNormalizeToInnerJoin(JoinNode nodeExpression inheritedPredicate)
        {
            Preconditions.checkArgument(EnumSet.of().contains(node.getType()), "Unsupported join type: %s"node.getType());
            if (node.getType() == ..) {
                return new JoinNode(node.getId(), ..node.getLeft(), node.getRight(), node.getCriteria(), node.getLeftHashSymbol(), node.getRightHashSymbol());
            }
            if (node.getType() == ..) {
                boolean canConvertToLeftJoin = canConvertOuterToInner(node.getLeft().getOutputSymbols(), inheritedPredicate);
                boolean canConvertToRightJoin = canConvertOuterToInner(node.getRight().getOutputSymbols(), inheritedPredicate);
                if (!canConvertToLeftJoin && !canConvertToRightJoin) {
                    return node;
                }
                if (canConvertToLeftJoin && canConvertToRightJoin) {
                    return new JoinNode(node.getId(), node.getLeft(), node.getRight(), node.getCriteria(), node.getLeftHashSymbol(), node.getRightHashSymbol());
                }
                else {
                    return new JoinNode(node.getId(), canConvertToLeftJoin ?  : ,
                            node.getLeft(), node.getRight(), node.getCriteria(), node.getLeftHashSymbol(), node.getRightHashSymbol());
                }
            }
            if (node.getType() == .. ||
                    node.getType() == .. && !canConvertOuterToInner(node.getRight().getOutputSymbols(), inheritedPredicate) ||
                    node.getType() == .. && !canConvertOuterToInner(node.getLeft().getOutputSymbols(), inheritedPredicate)) {
                return node;
            }
            return new JoinNode(node.getId(), ..node.getLeft(), node.getRight(), node.getCriteria(), node.getLeftHashSymbol(), node.getRightHashSymbol());
        }
        private boolean canConvertOuterToInner(List<SymbolinnerSymbolsForOuterJoinExpression inheritedPredicate)
        {
            Set<SymbolinnerSymbols = ImmutableSet.copyOf(innerSymbolsForOuterJoin);
            for (Expression conjunct : extractConjuncts(inheritedPredicate)) {
                if (DeterminismEvaluator.isDeterministic(conjunct)) {
                    // Ignore a conjunct for this test if we can not deterministically get responses from it
                    Object response = nullInputEvaluator(innerSymbolsconjunct);
                    if (response == null || response instanceof NullLiteral || ..equals(response)) {
                        // If there is a single conjunct that returns FALSE or NULL given all NULL inputs for the inner side symbols of an outer join
                        // then this conjunct removes all effects of the outer join, and effectively turns this into an equivalent of an inner join.
                        // So, let's just rewrite this join as an INNER join
                        return true;
                    }
                }
            }
            return false;
        }
        // Temporary implementation for joins because the SimplifyExpressions optimizers can not run properly on join clauses
        private Expression simplifyExpression(Expression expression)
        {
            IdentityHashMap<ExpressionTypeexpressionTypes = getExpressionTypes(.getTypes(), expression);
            ExpressionInterpreter optimizer = ExpressionInterpreter.expressionOptimizer(expressionexpressionTypes);
            return LiteralInterpreter.toExpression(optimizer.optimize(.), expressionTypes.get(expression));
        }

        
Evaluates an expression's response to binding the specified input symbols to NULL
        private Object nullInputEvaluator(final Collection<SymbolnullSymbolsExpression expression)
        {
            IdentityHashMap<ExpressionTypeexpressionTypes = getExpressionTypes(.getTypes(), expression);
            return ExpressionInterpreter.expressionOptimizer(expressionexpressionTypes)
                    .optimize(symbol -> nullSymbols.contains(symbol) ? null : new QualifiedNameReference(symbol.toQualifiedName()));
        }
        private static Predicate<ExpressionjoinEqualityExpression(final Collection<SymbolleftSymbols)
        {
            return expression -> {
                // At this point in time, our join predicates need to be deterministic
                if (isDeterministic(expression) && expression instanceof ComparisonExpression) {
                    ComparisonExpression comparison = (ComparisonExpressionexpression;
                    if (comparison.getType() == ..) {
                        Set<Symbolsymbols1 = DependencyExtractor.extractUnique(comparison.getLeft());
                        Set<Symbolsymbols2 = DependencyExtractor.extractUnique(comparison.getRight());
                        return (Iterables.all(symbols1in(leftSymbols)) && Iterables.all(symbols2not(in(leftSymbols)))) ||
                                (Iterables.all(symbols2in(leftSymbols)) && Iterables.all(symbols1not(in(leftSymbols))));
                    }
                }
                return false;
            };
        }
        @Override
        public PlanNode visitSemiJoin(SemiJoinNode nodeRewriteContext<Expressioncontext)
        {
            Expression inheritedPredicate = context.get();
            Expression sourceEffectivePredicate = EffectivePredicateExtractor.extract(node.getSource(), .getTypes());
            List<ExpressionsourceConjuncts = new ArrayList<>();
            List<ExpressionfilteringSourceConjuncts = new ArrayList<>();
            List<ExpressionpostJoinConjuncts = new ArrayList<>();
            // TODO: see if there are predicates that can be inferred from the semi join output
            // Push inherited and source predicates to filtering source via a contrived join predicate (but needs to avoid touching NULL values in the filtering source)
            Expression joinPredicate = equalsExpression(node.getSourceJoinSymbol(), node.getFilteringSourceJoinSymbol());
            EqualityInference joinInference = createEqualityInference(inheritedPredicatesourceEffectivePredicatejoinPredicate);
            for (Expression conjunct : Iterables.concat(EqualityInference.nonInferrableConjuncts(inheritedPredicate), EqualityInference.nonInferrableConjuncts(sourceEffectivePredicate))) {
                Expression rewrittenConjunct = joinInference.rewriteExpression(conjunctequalTo(node.getFilteringSourceJoinSymbol()));
                if (rewrittenConjunct != null && DeterminismEvaluator.isDeterministic(rewrittenConjunct)) {
                    // Alter conjunct to include an OR filteringSourceJoinSymbol IS NULL disjunct
                    Expression rewrittenConjunctOrNull = expressionOrNullSymbols(equalTo(node.getFilteringSourceJoinSymbol())).apply(rewrittenConjunct);
                    filteringSourceConjuncts.add(rewrittenConjunctOrNull);
                }
            }
            EqualityInference.EqualityPartition joinInferenceEqualityPartition = joinInference.generateEqualitiesPartitionedBy(equalTo(node.getFilteringSourceJoinSymbol()));
            filteringSourceConjuncts.addAll(ImmutableList.copyOf(transform(joinInferenceEqualityPartition.getScopeEqualities(),
                    expressionOrNullSymbols(equalTo(node.getFilteringSourceJoinSymbol())))));
            // Push inheritedPredicates down to the source if they don't involve the semi join output
            EqualityInference inheritedInference = createEqualityInference(inheritedPredicate);
            for (Expression conjunct : EqualityInference.nonInferrableConjuncts(inheritedPredicate)) {
                Expression rewrittenConjunct = inheritedInference.rewriteExpression(conjunctin(node.getSource().getOutputSymbols()));
                // Since each source row is reflected exactly once in the output, ok to push non-deterministic predicates down
                if (rewrittenConjunct != null) {
                    sourceConjuncts.add(rewrittenConjunct);
                }
                else {
                    postJoinConjuncts.add(conjunct);
                }
            }
            // Add the inherited equality predicates back in
            EqualityInference.EqualityPartition equalityPartition = inheritedInference.generateEqualitiesPartitionedBy(in(node.getSource().getOutputSymbols()));
            sourceConjuncts.addAll(equalityPartition.getScopeEqualities());
            postJoinConjuncts.addAll(equalityPartition.getScopeComplementEqualities());
            postJoinConjuncts.addAll(equalityPartition.getScopeStraddlingEqualities());
            PlanNode rewrittenSource = context.rewrite(node.getSource(), combineConjuncts(sourceConjuncts));
            PlanNode rewrittenFilteringSource = context.rewrite(node.getFilteringSource(), combineConjuncts(filteringSourceConjuncts));
            PlanNode output = node;
            if (rewrittenSource != node.getSource() || rewrittenFilteringSource != node.getFilteringSource()) {
                output = new SemiJoinNode(node.getId(), rewrittenSourcerewrittenFilteringSourcenode.getSourceJoinSymbol(), node.getFilteringSourceJoinSymbol(), node.getSemiJoinOutput(), node.getSourceHashSymbol(), node.getFilteringSourceHashSymbol());
            }
            if (!postJoinConjuncts.isEmpty()) {
                output = new FilterNode(.getNextId(), outputcombineConjuncts(postJoinConjuncts));
            }
            return output;
        }
        @Override
        public PlanNode visitAggregation(AggregationNode nodeRewriteContext<Expressioncontext)
        {
            Expression inheritedPredicate = context.get();
            EqualityInference equalityInference = createEqualityInference(inheritedPredicate);
            List<ExpressionpushdownConjuncts = new ArrayList<>();
            List<ExpressionpostAggregationConjuncts = new ArrayList<>();
            // Strip out non-deterministic conjuncts
            postAggregationConjuncts.addAll(ImmutableList.copyOf(filter(extractConjuncts(inheritedPredicate), not(DeterminismEvaluator::isDeterministic))));
            inheritedPredicate = stripNonDeterministicConjuncts(inheritedPredicate);
            // Sort non-equality predicates by those that can be pushed down and those that cannot
            for (Expression conjunct : EqualityInference.nonInferrableConjuncts(inheritedPredicate)) {
                Expression rewrittenConjunct = equalityInference.rewriteExpression(conjunctin(node.getGroupBy()));
                if (rewrittenConjunct != null) {
                    pushdownConjuncts.add(rewrittenConjunct);
                }
                else {
                    postAggregationConjuncts.add(conjunct);
                }
            }
            // Add the equality predicates back in
            EqualityInference.EqualityPartition equalityPartition = equalityInference.generateEqualitiesPartitionedBy(in(node.getGroupBy()));
            pushdownConjuncts.addAll(equalityPartition.getScopeEqualities());
            postAggregationConjuncts.addAll(equalityPartition.getScopeComplementEqualities());
            postAggregationConjuncts.addAll(equalityPartition.getScopeStraddlingEqualities());
            PlanNode rewrittenSource = context.rewrite(node.getSource(), combineConjuncts(pushdownConjuncts));
            PlanNode output = node;
            if (rewrittenSource != node.getSource()) {
                output = new AggregationNode(node.getId(),
                        rewrittenSource,
                        node.getGroupBy(),
                        node.getAggregations(),
                        node.getFunctions(),
                        node.getMasks(),
                        node.getStep(),
                        node.getSampleWeight(),
                        node.getConfidence(),
                        node.getHashSymbol());
            }
            if (!postAggregationConjuncts.isEmpty()) {
                output = new FilterNode(.getNextId(), outputcombineConjuncts(postAggregationConjuncts));
            }
            return output;
        }
        @Override
        public PlanNode visitUnnest(UnnestNode nodeRewriteContext<Expressioncontext)
        {
            Expression inheritedPredicate = context.get();
            EqualityInference equalityInference = createEqualityInference(inheritedPredicate);
            List<ExpressionpushdownConjuncts = new ArrayList<>();
            List<ExpressionpostUnnestConjuncts = new ArrayList<>();
            // Strip out non-deterministic conjuncts
            postUnnestConjuncts.addAll(ImmutableList.copyOf(filter(extractConjuncts(inheritedPredicate), not(DeterminismEvaluator::isDeterministic))));
            inheritedPredicate = stripNonDeterministicConjuncts(inheritedPredicate);
            // Sort non-equality predicates by those that can be pushed down and those that cannot
            for (Expression conjunct : EqualityInference.nonInferrableConjuncts(inheritedPredicate)) {
                Expression rewrittenConjunct = equalityInference.rewriteExpression(conjunctin(node.getReplicateSymbols()));
                if (rewrittenConjunct != null) {
                    pushdownConjuncts.add(rewrittenConjunct);
                }
                else {
                    postUnnestConjuncts.add(conjunct);
                }
            }
            // Add the equality predicates back in
            EqualityInference.EqualityPartition equalityPartition = equalityInference.generateEqualitiesPartitionedBy(in(node.getReplicateSymbols()));
            pushdownConjuncts.addAll(equalityPartition.getScopeEqualities());
            postUnnestConjuncts.addAll(equalityPartition.getScopeComplementEqualities());
            postUnnestConjuncts.addAll(equalityPartition.getScopeStraddlingEqualities());
            PlanNode rewrittenSource = context.rewrite(node.getSource(), combineConjuncts(pushdownConjuncts));
            PlanNode output = node;
            if (rewrittenSource != node.getSource()) {
                output = new UnnestNode(node.getId(), rewrittenSourcenode.getReplicateSymbols(), node.getUnnestSymbols(), node.