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;
 
 
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.UUID;
 
 import static com.facebook.presto.metadata.Util.toConnectorDomain;
 import static com.facebook.presto.spi.type.BigintType.BIGINT;
 import static com.facebook.presto.sql.ExpressionUtils.and;
 import static com.facebook.presto.sql.ExpressionUtils.combineConjuncts;
 import static com.facebook.presto.sql.ExpressionUtils.or;
 import static com.facebook.presto.sql.planner.plan.TableScanNode.GeneratedPartitions;
 
 @Test(singleThreaded = true)
 {
     private static final TableHandle DUAL_TABLE_HANDLE = new TableHandle("test"new TestingTableHandle());
 
     private static final Symbol A = new Symbol("a");
     private static final Symbol B = new Symbol("b");
     private static final Symbol C = new Symbol("c");
     private static final Symbol D = new Symbol("d");
     private static final Symbol E = new Symbol("e");
     private static final Symbol F = new Symbol("f");
     private static final Expression AE = symbolExpr();
     private static final Expression BE = symbolExpr();
     private static final Expression CE = symbolExpr();
     private static final Expression DE = symbolExpr();
     private static final Expression EE = symbolExpr();
     private static final Expression FE = symbolExpr();
 
     private static final Map<SymbolTypeTYPES = ImmutableMap.<SymbolType>builder()
             .put()
             .put()
             .put()
            .put()
            .put()
            .put()
            .build();
    private TableScanNode baseTableScan;
    public void setUp()
            throws Exception
    {
         = ImmutableMap.<SymbolColumnHandle>builder()
                .put(newColumnHandle("a"))
                .put(newColumnHandle("b"))
                .put(newColumnHandle("c"))
                .put(newColumnHandle("d"))
                .put(newColumnHandle("e"))
                .put(newColumnHandle("f"))
                .build();
        Map<SymbolColumnHandleassignments = Maps.filterKeys(, Predicates.in(ImmutableList.of()));
         = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(assignments.keySet()),
                assignments,
                null,
                Optional.empty()
        );
    }
    @Test
    public void testAggregation()
            throws Exception
    {
        PlanNode node = new AggregationNode(newId(),
                filter(,
                        and(
                                equals(),
                                equals(),
                                equals(),
                                lessThan(number(10)),
                                lessThan(),
                                greaterThan(number(2)),
                                equals())),
                ImmutableList.of(),
                ImmutableMap.of(fakeFunction("test"), fakeFunction("test")),
                ImmutableMap.of(fakeFunctionHandle("test"), fakeFunctionHandle("test")),
                ImmutableMap.<SymbolSymbol>of(),
                ..,
                Optional.empty(),
                1.0,
                Optional.empty());
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        // Rewrite in terms of group by symbols
        Assert.assertEquals(normalizeConjuncts(effectivePredicate),
                normalizeConjuncts(
                        lessThan(number(10)),
                        lessThan(),
                        greaterThan(number(2)),
                        equals()));
    }
    @Test
    public void testFilter()
            throws Exception
    {
        PlanNode node = filter(,
                and(
                        greaterThan(new FunctionCall(QualifiedName.of("rand"), ImmutableList.<Expression>of())),
                        lessThan(number(10))));
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        // Non-deterministic functions should be purged
        Assert.assertEquals(normalizeConjuncts(effectivePredicate),
                normalizeConjuncts(lessThan(number(10))));
    }
    @Test
    public void testProject()
            throws Exception
    {
        PlanNode node = new ProjectNode(newId(),
                filter(,
                        and(
                                equals(),
                                equals(),
                                lessThan(number(10)))),
                ImmutableMap.of());
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        // Rewrite in terms of project output symbols
        Assert.assertEquals(normalizeConjuncts(effectivePredicate),
                normalizeConjuncts(
                        lessThan(number(10)),
                        equals()));
    }
    @Test
    public void testTopN()
            throws Exception
    {
        PlanNode node = new TopNNode(newId(),
                filter(,
                        and(
                                equals(),
                                equals(),
                                lessThan(number(10)))),
                1, ImmutableList.of(), ImmutableMap.of(.), true);
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        // Pass through
        Assert.assertEquals(normalizeConjuncts(effectivePredicate),
                normalizeConjuncts(
                        equals(),
                        equals(),
                        lessThan(number(10))));
    }
    @Test
    public void testLimit()
            throws Exception
    {
        PlanNode node = new LimitNode(newId(),
                filter(,
                        and(
                                equals(),
                                equals(),
                                lessThan(number(10)))),
                1);
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        // Pass through
        Assert.assertEquals(normalizeConjuncts(effectivePredicate),
                normalizeConjuncts(
                        equals(),
                        equals(),
                        lessThan(number(10))));
    }
    @Test
    public void testSort()
            throws Exception
    {
        PlanNode node = new SortNode(newId(),
                filter(,
                        and(
                                equals(),
                                equals(),
                                lessThan(number(10)))),
                ImmutableList.of(), ImmutableMap.of(.));
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        // Pass through
        Assert.assertEquals(normalizeConjuncts(effectivePredicate),
                normalizeConjuncts(
                        equals(),
                        equals(),
                        lessThan(number(10))));
    }
    @Test
    public void testWindow()
            throws Exception
    {
        PlanNode node = new WindowNode(newId(),
                filter(,
                        and(
                                equals(),
                                equals(),
                                lessThan(number(10)))),
                ImmutableList.of(),
                ImmutableList.of(),
                ImmutableMap.of(.),
                new WindowNode.Frame(..,
                        .., Optional.empty(),
                        .., Optional.empty()),
                ImmutableMap.<SymbolFunctionCall>of(),
                ImmutableMap.<SymbolSignature>of(), Optional.empty());
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        // Pass through
        Assert.assertEquals(normalizeConjuncts(effectivePredicate),
                normalizeConjuncts(
                        equals(),
                        equals(),
                        lessThan(number(10))));
    }
    @Test
    public void testTableScan()
            throws Exception
    {
        // Effective predicate is True if there are no generated partitions
        Map<SymbolColumnHandleassignments = Maps.filterKeys(, Predicates.in(ImmutableList.of()));
        PlanNode node = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(assignments.keySet()),
                assignments,
                null,
                Optional.empty());
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        Assert.assertEquals(effectivePredicate.);
        // tupleDomainInput with no matching partitions
        node = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(assignments.keySet()),
                assignments,
                null,
                Optional.<GeneratedPartitions>of(new GeneratedPartitions(
                        TupleDomain.withColumnDomains(ImmutableMap.<ColumnHandleDomain>of(.get(), Domain.singleValue(1L))),
                        ImmutableList.<Partition>of())));
        effectivePredicate = EffectivePredicateExtractor.extract(node);
        Assert.assertEquals(effectivePredicate.);
        // tupleDomainInput with non-descriptive partitions
        node = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(assignments.keySet()),
                assignments,
                null,
                Optional.<GeneratedPartitions>of(new GeneratedPartitions(
                        TupleDomain.withColumnDomains(ImmutableMap.<ColumnHandleDomain>of(.get(), Domain.singleValue(1L))),
                        ImmutableList.of(new Partition("test"new TestingPartition())))));
        effectivePredicate = EffectivePredicateExtractor.extract(node);
        Assert.assertEquals(normalizeConjuncts(effectivePredicate), normalizeConjuncts(equals(number(1L), )));
        // tupleDomainInput with descriptive partitions
        node = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(assignments.keySet()),
                assignments,
                null,
                Optional.<GeneratedPartitions>of(new GeneratedPartitions(
                        TupleDomain.withColumnDomains(ImmutableMap.<ColumnHandleDomain>of(.get(), Domain.singleValue(1L))),
                        ImmutableList.<Partition>of(tupleDomainPartition("test",
                                TupleDomain.withColumnDomains(ImmutableMap.<ColumnHandleDomain>of(
                                        .get(), Domain.singleValue(1L),
                                        .get(), Domain.singleValue(2L))))))));
        effectivePredicate = EffectivePredicateExtractor.extract(node);
        Assert.assertEquals(normalizeConjuncts(effectivePredicate), normalizeConjuncts(equals(number(2L), ), equals(number(1L), )));
        // generic tupleDomainInput with no matching partitions
        node = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(assignments.keySet()),
                assignments,
                null,
                Optional.<GeneratedPartitions>of(new GeneratedPartitions(
                        TupleDomain.<ColumnHandle>all(),
                        ImmutableList.<Partition>of())));
        effectivePredicate = EffectivePredicateExtractor.extract(node);
        Assert.assertEquals(effectivePredicate.);
        // generic tupleDomainInput with non-descriptive partitions
        node = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(assignments.keySet()),
                assignments,
                null,
                Optional.<GeneratedPartitions>of(new GeneratedPartitions(
                        TupleDomain.<ColumnHandle>all(),
                        ImmutableList.of(new Partition("test"new TestingPartition())))));
        effectivePredicate = EffectivePredicateExtractor.extract(node);
        Assert.assertEquals(effectivePredicate.);
        // generic tupleDomainInput with descriptive partitions
        node = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(assignments.keySet()),
                assignments,
                null,
                Optional.<GeneratedPartitions>of(new GeneratedPartitions(
                        TupleDomain.<ColumnHandle>all(),
                        ImmutableList.of(tupleDomainPartition("test",
                                TupleDomain.withColumnDomains(ImmutableMap.<ColumnHandleDomain>of(
                                        .get(), Domain.singleValue(1L),
                                        .get(), Domain.singleValue(2L))))))));
        effectivePredicate = EffectivePredicateExtractor.extract(node);
        Assert.assertEquals(normalizeConjuncts(effectivePredicate), normalizeConjuncts(equals(number(2L), ), equals(number(1L), )));
        // Make sure only output symbols are produced
        node = new TableScanNode(
                newId(),
                ,
                ImmutableList.of(),
                assignments,
                null,
                Optional.<GeneratedPartitions>of(new GeneratedPartitions(
                        TupleDomain.withColumnDomains(ImmutableMap.<ColumnHandleDomain>of(
                                .get(), Domain.singleValue(1L),
                                .get(), Domain.singleValue(3L))),
                        ImmutableList.of(tupleDomainPartition("test",
                                TupleDomain.withColumnDomains(ImmutableMap.<ColumnHandleDomain>of(
                                        .get(), Domain.singleValue(1L),
                                        .get(), Domain.singleValue(2L))))))));
        effectivePredicate = EffectivePredicateExtractor.extract(node);
        Assert.assertEquals(normalizeConjuncts(effectivePredicate), normalizeConjuncts(equals(number(1L), )));
    }
    private static Partition tupleDomainPartition(String connectorIdfinal TupleDomain<ColumnHandletupleDomain)
    {
        return new Partition(connectorIdnew ConnectorPartition()
        {
            @Override
            public String getPartitionId()
            {
                throw new UnsupportedOperationException("not yet implemented");
            }
            @Override
            public TupleDomain<ConnectorColumnHandlegetTupleDomain()
            {
                return toConnectorDomain(tupleDomain);
            }
        });
    }
    @Test
    public void testUnion()
            throws Exception
    {
        PlanNode node = new UnionNode(newId(),
                ImmutableList.<PlanNode>of(
                        filter(greaterThan(number(10))),
                        filter(and(greaterThan(number(10)), lessThan(number(100)))),
                        filter(and(greaterThan(number(10)), lessThan(number(100))))
                ),
                ImmutableListMultimap.of()
        );
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        // Only the common conjuncts can be inferred through a Union
        Assert.assertEquals(normalizeConjuncts(effectivePredicate),
                normalizeConjuncts(greaterThan(number(10))));
    }
    @Test
    public void testInnerJoin()
            throws Exception
    {
        ImmutableList.Builder<JoinNode.EquiJoinClausecriteriaBuilder = ImmutableList.builder();
        criteriaBuilder.add(new JoinNode.EquiJoinClause());
        criteriaBuilder.add(new JoinNode.EquiJoinClause());
        List<JoinNode.EquiJoinClausecriteria = criteriaBuilder.build();
        Map<SymbolColumnHandleleftAssignments = Maps.filterKeys(, Predicates.in(ImmutableList.of()));
        TableScanNode leftScan = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(leftAssignments.keySet()),
                leftAssignments,
                null,
                Optional.empty()
        );
        Map<SymbolColumnHandlerightAssignments = Maps.filterKeys(, Predicates.in(ImmutableList.of()));
        TableScanNode rightScan = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(rightAssignments.keySet()),
                rightAssignments,
                null,
                Optional.empty()
        );
        PlanNode node = new JoinNode(newId(),
                ..,
                filter(leftScan,
                        and(
                                lessThan(),
                                lessThan(number(10)))),
                filter(rightScan,
                        and(
                                equals(),
                                lessThan(number(100)))),
                criteria,
                Optional.empty(),
                Optional.empty());
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        // All predicates should be carried through
        Assert.assertEquals(normalizeConjuncts(effectivePredicate),
                normalizeConjuncts(lessThan(),
                        lessThan(number(10)),
                        equals(),
                        lessThan(number(100)),
                        equals(),
                        equals()));
    }
    @Test
    public void testLeftJoin()
            throws Exception
    {
        ImmutableList.Builder<JoinNode.EquiJoinClausecriteriaBuilder = ImmutableList.builder();
        criteriaBuilder.add(new JoinNode.EquiJoinClause());
        criteriaBuilder.add(new JoinNode.EquiJoinClause());
        List<JoinNode.EquiJoinClausecriteria = criteriaBuilder.build();
        Map<SymbolColumnHandleleftAssignments = Maps.filterKeys(, Predicates.in(ImmutableList.of()));
        TableScanNode leftScan = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(leftAssignments.keySet()),
                leftAssignments,
                null,
                Optional.empty()
        );
        Map<SymbolColumnHandlerightAssignments = Maps.filterKeys(, Predicates.in(ImmutableList.of()));
        TableScanNode rightScan = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(rightAssignments.keySet()),
                rightAssignments,
                null,
                Optional.empty()
        );
        PlanNode node = new JoinNode(newId(),
                ..,
                filter(leftScan,
                        and(
                                lessThan(),
                                lessThan(number(10)))),
                filter(rightScan,
                        and(
                                equals(),
                                lessThan(number(100)))),
                criteria,
                Optional.empty(),
                Optional.empty());
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        // All right side symbols should be checked against NULL
        Assert.assertEquals(normalizeConjuncts(effectivePredicate),
                normalizeConjuncts(lessThan(),
                        lessThan(number(10)),
                        or(equals(), and(isNull(), isNull())),
                        or(lessThan(number(100)), isNull()),
                        or(equals(), isNull()),
                        or(equals(), isNull())));
    }
    @Test
    public void testRightJoin()
            throws Exception
    {
        ImmutableList.Builder<JoinNode.EquiJoinClausecriteriaBuilder = ImmutableList.builder();
        criteriaBuilder.add(new JoinNode.EquiJoinClause());
        criteriaBuilder.add(new JoinNode.EquiJoinClause());
        List<JoinNode.EquiJoinClausecriteria = criteriaBuilder.build();
        Map<SymbolColumnHandleleftAssignments = Maps.filterKeys(, Predicates.in(ImmutableList.of()));
        TableScanNode leftScan = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(leftAssignments.keySet()),
                leftAssignments,
                null,
                Optional.empty()
        );
        Map<SymbolColumnHandlerightAssignments = Maps.filterKeys(, Predicates.in(ImmutableList.of()));
        TableScanNode rightScan = new TableScanNode(
                newId(),
                ,
                ImmutableList.copyOf(rightAssignments.keySet()),
                rightAssignments,
                null,
                Optional.empty()
        );
        PlanNode node = new JoinNode(newId(),
                ..,
                filter(leftScan,
                        and(
                                lessThan(),
                                lessThan(number(10)))),
                filter(rightScan,
                        and(
                                equals(),
                                lessThan(number(100)))),
                criteria,
                Optional.empty(),
                Optional.empty());
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        // All left side symbols should be checked against NULL
        Assert.assertEquals(normalizeConjuncts(effectivePredicate),
                normalizeConjuncts(or(lessThan(), and(isNull(), isNull())),
                        or(lessThan(number(10)), isNull()),
                        equals(),
                        lessThan(number(100)),
                        or(equals(), isNull()),
                        or(equals(), isNull())));
    }
    @Test
    public void testSemiJoin()
            throws Exception
    {
        PlanNode node = new SemiJoinNode(newId(),
                filter(and(greaterThan(number(10)), lessThan(number(100)))),
                filter(greaterThan(number(5))),
                ,
                Optional.empty(),
                Optional.empty());
        Expression effectivePredicate = EffectivePredicateExtractor.extract(node);
        // Currently, only pull predicates through the source plan
        Assert.assertEquals(normalizeConjuncts(effectivePredicate),
                normalizeConjuncts(and(greaterThan(number(10)), lessThan(number(100)))));
    }
    private static ColumnHandle newColumnHandle(String name)
    {
        return new ColumnHandle("test"new TestingColumnHandle(name));
    }
    private static PlanNodeId newId()
    {
        return new PlanNodeId(UUID.randomUUID().toString());
    }
    private static FilterNode filter(PlanNode sourceExpression predicate)
    {
        return new FilterNode(newId(), sourcepredicate);
    }
    private static Expression symbolExpr(Symbol symbol)
    {
        return new QualifiedNameReference(symbol.toQualifiedName());
    }
    private static Expression number(long number)
    {
        return new LongLiteral(String.valueOf(number));
    }
    private static ComparisonExpression equals(Expression expression1Expression expression2)
    {
        return new ComparisonExpression(..expression1expression2);
    }
    private static ComparisonExpression lessThan(Expression expression1Expression expression2)
    {
        return new ComparisonExpression(..expression1expression2);
    }
    private static ComparisonExpression greaterThan(Expression expression1Expression expression2)
    {
        return new ComparisonExpression(..expression1expression2);
    }
    private static IsNullPredicate isNull(Expression expression)
    {
        return new IsNullPredicate(expression);
    }
    private static FunctionCall fakeFunction(String name)
    {
        return new FunctionCall(QualifiedName.of("test"), ImmutableList.<Expression>of());
    }
    private static Signature fakeFunctionHandle(String name)
    {
        return new Signature(name., ImmutableList.<String>of());
    }
    private Set<ExpressionnormalizeConjuncts(Expression... conjuncts)
    {
        return normalizeConjuncts(Arrays.asList(conjuncts));
    }
    private Set<ExpressionnormalizeConjuncts(Iterable<Expressionconjuncts)
    {
        return normalizeConjuncts(combineConjuncts(conjuncts));
    }
    private Set<ExpressionnormalizeConjuncts(Expression predicate)
    {
        // Normalize the predicate by identity so that the EqualityInference will produce stable rewrites in this test
        // and thereby produce comparable Sets of conjuncts from this method.
        predicate = .normalize(predicate);
        // Equality inference rewrites and equality generation will always be stable across multiple runs in the same JVM
        EqualityInference inference = EqualityInference.createEqualityInference(predicate);
        Set<ExpressionrewrittenSet = new HashSet<>();
        for (Expression expression : EqualityInference.nonInferrableConjuncts(predicate)) {
            Expression rewritten = inference.rewriteExpression(expression, Predicates.<Symbol>alwaysTrue());
            Preconditions.checkState(rewritten != null"Rewrite with full symbol scope should always be possible");
            rewrittenSet.add(rewritten);
        }
        rewrittenSet.addAll(inference.generateEqualitiesPartitionedBy(Predicates.<Symbol>alwaysTrue()).getScopeEqualities());
        return rewrittenSet;
    }

    
Normalizes Expression nodes (and all sub-expressions) by identity.

Identity equality of Expression nodes is necessary for EqualityInference to generate stable rewrites (as specified by Ordering.arbitrary())

    private static class ExpressionIdentityNormalizer
    {
        private final Map<ExpressionExpressionexpressionCache = new HashMap<>();
        private Expression normalize(Expression expression)
        {
            Expression identityNormalizedExpression = .get(expression);
            if (identityNormalizedExpression == null) {
                // Make sure all sub-expressions are normalized first
                for (Expression subExpression : Iterables.filter(SubExpressionExtractor.extract(expression), Predicates.not(Predicates.equalTo(expression)))) {
                    normalize(subExpression);
                }
                // Since we have not seen this expression before, rewrite it entirely in terms of the normalized sub-expressions
                identityNormalizedExpression = ExpressionTreeRewriter.rewriteWith(new ExpressionNodeInliner(), expression);
                .put(identityNormalizedExpressionidentityNormalizedExpression);
            }
            return identityNormalizedExpression;
        }
    }
New to GrepCode? Check out our FAQ X