Repository: tajo Updated Branches: refs/heads/master a1a9d624d -> bedce3aa0
http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinEdge.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinEdge.java b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinEdge.java index fb4fae1..3b67df0 100644 --- a/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinEdge.java +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinEdge.java @@ -18,58 +18,70 @@ package org.apache.tajo.plan.joinorder; -import com.google.common.collect.Sets; import org.apache.tajo.algebra.JoinType; +import org.apache.tajo.catalog.Schema; +import org.apache.tajo.catalog.SchemaUtil; import org.apache.tajo.plan.expr.EvalNode; -import org.apache.tajo.plan.logical.LogicalNode; +import org.apache.tajo.plan.logical.JoinSpec; import org.apache.tajo.util.StringUtils; -import java.util.Collections; import java.util.Set; public class JoinEdge { - private final JoinType joinType; - private final LogicalNode leftRelation; - private final LogicalNode rightRelation; - private final Set<EvalNode> joinQual = Sets.newHashSet(); - - public JoinEdge(JoinType joinType, LogicalNode leftRelation, LogicalNode rightRelation) { - this.joinType = joinType; - this.leftRelation = leftRelation; - this.rightRelation = rightRelation; - } + private final JoinSpec joinSpec; + private final JoinVertex leftVertex; + private final JoinVertex rightVertex; + private final Schema schema; - public JoinEdge(JoinType joinType, LogicalNode leftRelation, LogicalNode rightRelation, - EvalNode ... condition) { - this(joinType, leftRelation, rightRelation); - Collections.addAll(joinQual, condition); + public JoinEdge(JoinSpec joinSpec, JoinVertex leftVertex, JoinVertex rightVertex) { + this.joinSpec = joinSpec; + this.leftVertex = leftVertex; + this.rightVertex = rightVertex; + this.schema = SchemaUtil.merge(leftVertex.getSchema(), rightVertex.getSchema()); } public JoinType getJoinType() { - return joinType; + return joinSpec.getType(); } - public LogicalNode getLeftRelation() { - return leftRelation; + public boolean hasJoinQual() { + return joinSpec.hasPredicates(); } - public LogicalNode getRightRelation() { - return rightRelation; + public void addJoinQual(EvalNode joinQual) { + this.joinSpec.addPredicate(joinQual); } - public boolean hasJoinQual() { - return joinQual.size() > 0; + public void addJoinPredicates(Set<EvalNode> predicates) { + this.joinSpec.addPredicates(predicates); } - public void addJoinQual(EvalNode joinQual) { - this.joinQual.add(joinQual); + public Set<EvalNode> getJoinQual() { + return joinSpec.getPredicates(); + } + + public JoinSpec getJoinSpec() { + return this.joinSpec; } - public EvalNode [] getJoinQual() { - return joinQual.toArray(new EvalNode[joinQual.size()]); + public EvalNode getSingletonJoinQual() { + return joinSpec.getSingletonPredicate(); } public String toString() { - return leftRelation + " " + joinType + " " + rightRelation + " ON " + StringUtils.join(joinQual, ", "); + return leftVertex + " " + joinSpec.getType() + " " + rightVertex + " ON " + + StringUtils.join(joinSpec.getPredicates(), ", "); + } + + public JoinVertex getLeftVertex() { + return leftVertex; + } + + public JoinVertex getRightVertex() { + return rightVertex; + } + + public Schema getSchema() { + return schema; } } http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinGraph.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinGraph.java b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinGraph.java index 9ae5245..4727b2e 100644 --- a/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinGraph.java +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinGraph.java @@ -18,140 +18,36 @@ package org.apache.tajo.plan.joinorder; -import com.google.common.collect.Sets; -import org.apache.tajo.algebra.JoinType; -import org.apache.tajo.catalog.CatalogUtil; -import org.apache.tajo.catalog.Column; -import org.apache.tajo.util.StringUtils; -import org.apache.tajo.util.graph.SimpleUndirectedGraph; -import org.apache.tajo.plan.LogicalPlan; -import org.apache.tajo.plan.NamedExprsManager; -import org.apache.tajo.plan.util.PlannerUtil; import org.apache.tajo.plan.PlanningException; -import org.apache.tajo.plan.expr.AlgebraicUtil; -import org.apache.tajo.plan.expr.BinaryEval; -import org.apache.tajo.plan.expr.EvalNode; -import org.apache.tajo.plan.expr.EvalTreeUtil; -import org.apache.tajo.plan.logical.JoinNode; -import org.apache.tajo.plan.logical.RelationNode; - -import java.util.*; - -public class JoinGraph extends SimpleUndirectedGraph<String, JoinEdge> { - - private String [] guessRelationsFromJoinQual(LogicalPlan.QueryBlock block, BinaryEval joinCondition) - throws PlanningException { +import org.apache.tajo.plan.logical.JoinSpec; +import org.apache.tajo.plan.util.PlannerUtil; +import org.apache.tajo.util.graph.SimpleUndirectedGraph; - // Note that we can guarantee that each join qual used here is a singleton. - // This is because we use dissect a join qual into conjunctive normal forms. - // In other words, each join qual has a form 'col1 = col2'. - Column leftExpr = EvalTreeUtil.findAllColumnRefs(joinCondition.getLeftExpr()).get(0); - Column rightExpr = EvalTreeUtil.findAllColumnRefs(joinCondition.getRightExpr()).get(0); +import java.util.List; - // 0 - left table, 1 - right table - String [] relationNames = new String[2]; +/** + * A join graph must be the connected graph + */ +public class JoinGraph extends SimpleUndirectedGraph<JoinVertex, JoinEdge> { - NamedExprsManager namedExprsMgr = block.getNamedExprsManager(); - if (leftExpr.hasQualifier()) { - relationNames[0] = leftExpr.getQualifier(); - } else { - if (namedExprsMgr.isAliasedName(leftExpr.getSimpleName())) { - String columnName = namedExprsMgr.getOriginalName(leftExpr.getSimpleName()); - String qualifier = CatalogUtil.extractQualifier(columnName); - relationNames[0] = qualifier; - } else { - // search for a relation which evaluates a right term included in a join condition - for (RelationNode rel : block.getRelations()) { - if (rel.getOutSchema().contains(leftExpr)) { - String qualifier = rel.getCanonicalName(); - relationNames[0] = qualifier; - } - } + private boolean isSymmetricJoinOnly = true; - if (relationNames[0] == null) { // if not found - throw new PlanningException("Cannot expect a referenced relation: " + leftExpr); - } - } + public JoinEdge addJoin(JoinGraphContext context, JoinSpec joinSpec, JoinVertex left, JoinVertex right) throws PlanningException { + JoinEdge edge = context.getCachedOrNewJoinEdge(joinSpec, left, right); + isSymmetricJoinOnly &= PlannerUtil.isCommutativeJoinType(edge.getJoinType()); + this.addEdge(left, right, edge); + List<JoinEdge> incomeToLeft = getIncomingEdges(left); + if (incomeToLeft == null || incomeToLeft.isEmpty()) { + context.addRootVertexes(left); } - - if (rightExpr.hasQualifier()) { - relationNames[1] = rightExpr.getQualifier(); - } else { - if (namedExprsMgr.isAliasedName(rightExpr.getSimpleName())) { - String columnName = namedExprsMgr.getOriginalName(rightExpr.getSimpleName()); - String qualifier = CatalogUtil.extractQualifier(columnName); - relationNames[1] = qualifier; - } else { - // search for a relation which evaluates a right term included in a join condition - for (RelationNode rel : block.getRelations()) { - if (rel.getOutSchema().contains(rightExpr)) { - String qualifier = rel.getCanonicalName(); - relationNames[1] = qualifier; - } - } - - if (relationNames[1] == null) { // if not found - throw new PlanningException("Cannot expect a referenced relation: " + rightExpr); - } - } + if (context.getRootVertexes().size() > 1) { + // for the case of cycle + context.removeRootVertexes(right); } - - return relationNames; + return edge; } - public Collection<EvalNode> addJoin(LogicalPlan plan, LogicalPlan.QueryBlock block, - JoinNode joinNode) throws PlanningException { - if (joinNode.getJoinType() == JoinType.LEFT_OUTER || joinNode.getJoinType() == JoinType.RIGHT_OUTER) { - JoinEdge edge = new JoinEdge(joinNode.getJoinType(), - joinNode.getLeftChild(), joinNode.getRightChild(), joinNode.getJoinQual()); - - SortedSet<String> leftNodeRelationName = - new TreeSet<String>(PlannerUtil.getRelationLineageWithinQueryBlock(plan, joinNode.getLeftChild())); - SortedSet<String> rightNodeRelationName = - new TreeSet<String>(PlannerUtil.getRelationLineageWithinQueryBlock(plan, joinNode.getRightChild())); - - addEdge( - StringUtils.join(leftNodeRelationName, ", "), - StringUtils.join(rightNodeRelationName, ", "), - edge); - - Set<EvalNode> allInOneCnf = new HashSet<EvalNode>(); - allInOneCnf.add(joinNode.getJoinQual()); - - return allInOneCnf; - } else { - Set<EvalNode> cnf = Sets.newHashSet(AlgebraicUtil.toConjunctiveNormalFormArray(joinNode.getJoinQual())); - - for (EvalNode singleQual : cnf) { - if (EvalTreeUtil.isJoinQual(block, - joinNode.getLeftChild().getOutSchema(), - joinNode.getRightChild().getOutSchema(), - singleQual, true)) { - String[] relations = guessRelationsFromJoinQual(block, (BinaryEval) singleQual); - String leftExprRelName = relations[0]; - String rightExprRelName = relations[1]; - - Collection<String> leftLineage = PlannerUtil.getRelationLineageWithinQueryBlock(plan, joinNode.getLeftChild()); - - boolean isLeftExprForLeftTable = leftLineage.contains(leftExprRelName); - - JoinEdge edge = getEdge(leftExprRelName, rightExprRelName); - if (edge != null) { - edge.addJoinQual(singleQual); - } else { - if (isLeftExprForLeftTable) { - edge = new JoinEdge(joinNode.getJoinType(), - block.getRelation(leftExprRelName), block.getRelation(rightExprRelName), singleQual); - addEdge(leftExprRelName, rightExprRelName, edge); - } else { - edge = new JoinEdge(joinNode.getJoinType(), - block.getRelation(rightExprRelName), block.getRelation(leftExprRelName), singleQual); - addEdge(rightExprRelName, leftExprRelName, edge); - } - } - } - } - return cnf; - } + public boolean isSymmetricJoinOnly() { + return isSymmetricJoinOnly; } -} +} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinGraphContext.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinGraphContext.java b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinGraphContext.java new file mode 100644 index 0000000..97cd569 --- /dev/null +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinGraphContext.java @@ -0,0 +1,137 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you 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 org.apache.tajo.plan.joinorder; + +import org.apache.tajo.plan.expr.EvalNode; +import org.apache.tajo.plan.logical.JoinSpec; +import org.apache.tajo.util.Pair; +import org.apache.tajo.util.TUtil; + +import java.util.Collection; +import java.util.Map; +import java.util.Set; + +public class JoinGraphContext { + private Set<JoinVertex> rootVertexes = TUtil.newHashSet(); // most left vertex in the join plan + private JoinGraph joinGraph = new JoinGraph(); + + // New join edges are frequently created during join order optimization. + // This cache is to reduce the overhead of join edge creation. + private Map<Pair<JoinVertex,JoinVertex>, JoinEdge> edgeCache = TUtil.newHashMap(); + + // candidate predicates contain the predicates which are not pushed to any join nodes yet. + // evaluated predicates contain the predicates which are already pushed to some join nodes. + private Set<EvalNode> candidateJoinConditions = TUtil.newHashSet(); // predicates from the on clause + private Set<EvalNode> candidateJoinFilters = TUtil.newHashSet(); // predicates from the where clause + private Set<EvalNode> evaluatedJoinConditions = TUtil.newHashSet(); // predicates from the on clause + private Set<EvalNode> evaluatedJoinFilters = TUtil.newHashSet(); // predicates from the where clause + + public JoinGraph getJoinGraph() { + return joinGraph; + } + + public void addCandidateJoinConditions(Collection<EvalNode> candidates) { + for (EvalNode eachCandidate : candidates) { + if (!evaluatedJoinConditions.contains(eachCandidate)) { + candidateJoinConditions.add(eachCandidate); + } + } + } + + public void addCandidateJoinFilters(Collection<EvalNode> candidates) { + for (EvalNode eachCandidate : candidates) { + if (!evaluatedJoinFilters.contains(eachCandidate)) { + candidateJoinFilters.add(eachCandidate); + } + } + } + + public void removeCandidateJoinConditions(Collection<EvalNode> willBeRemoved) { + candidateJoinConditions.remove(willBeRemoved); + } + + public void removeCandidateJoinFilters(Collection<EvalNode> willBeRemoved) { + candidateJoinFilters.remove(willBeRemoved); + } + + public void markAsEvaluatedJoinConditions(Collection<EvalNode> willBeMarked) { + for (EvalNode eachEval : willBeMarked) { + if (candidateJoinConditions.contains(eachEval)) { + candidateJoinConditions.remove(eachEval); + evaluatedJoinConditions.add(eachEval); + } + } + } + + public void markAsEvaluatedJoinFilters(Collection<EvalNode> willBeMarked) { + for (EvalNode eachEval : willBeMarked) { + if (candidateJoinFilters.contains(eachEval)) { + candidateJoinFilters.remove(eachEval); + evaluatedJoinFilters.add(eachEval); + } + } + } + + public Set<EvalNode> getCandidateJoinConditions() { + return candidateJoinConditions; + } + + public Set<EvalNode> getCandidateJoinFilters() { + return candidateJoinFilters; + } + + public Set<EvalNode> getEvaluatedJoinConditions() { + return evaluatedJoinConditions; + } + + public Set<EvalNode> getEvaluatedJoinFilters() { + return evaluatedJoinFilters; + } + + public Set<JoinVertex> getRootVertexes() { + return rootVertexes; + } + + public void addRootVertexes(JoinVertex rootVertex) { + this.rootVertexes.add(rootVertex); + } + + public boolean removeRootVertexes(JoinVertex rootVertex) { + return this.rootVertexes.remove(rootVertex); + } + + public void replaceRootVertexes(JoinVertex oldRoot, JoinVertex newRoot) { + removeRootVertexes(oldRoot); + addRootVertexes(newRoot); + } + + public JoinEdge cacheEdge(JoinEdge edge) { + edgeCache.put(new Pair<JoinVertex, JoinVertex>(edge.getLeftVertex(), edge.getRightVertex()), edge); + return edge; + } + + public JoinEdge getCachedOrNewJoinEdge(JoinSpec joinSpec, JoinVertex left, JoinVertex right) { + Pair<JoinVertex,JoinVertex> cacheKey = new Pair<JoinVertex, JoinVertex>(left, right); + if (edgeCache.containsKey(cacheKey)) { + return edgeCache.get(cacheKey); + } else { + return cacheEdge(new JoinEdge(joinSpec, left, right)); + } + } +} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinOrderAlgorithm.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinOrderAlgorithm.java b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinOrderAlgorithm.java index 2dd0670..d9f4c69 100644 --- a/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinOrderAlgorithm.java +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinOrderAlgorithm.java @@ -33,16 +33,16 @@ import java.util.Set; public interface JoinOrderAlgorithm { /** + * Find the best join order. * * @param plan * @param block - * @param joinGraph A join graph represents join conditions and their connections among relations. - * Given a graph, each vertex represents a relation, and each edge contains a join condition. - * A join graph does not contain relations that do not have any corresponding join condition. - * @param relationsWithoutQual The names of relations that do not have any corresponding join condition. - * @return + * @param joinGraphContext A left-deep join tree represents join conditions and the join relationships among + * relations. A vertex can be a relation or a group of joined relations. + * An edge represents a join relation between two vertexes. + * @return found join order * @throws org.apache.tajo.plan.PlanningException */ - FoundJoinOrder findBestOrder(LogicalPlan plan, LogicalPlan.QueryBlock block, JoinGraph joinGraph, - Set<String> relationsWithoutQual) throws PlanningException; + FoundJoinOrder findBestOrder(LogicalPlan plan, LogicalPlan.QueryBlock block, JoinGraphContext joinGraphContext) + throws PlanningException; } http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinOrderingUtil.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinOrderingUtil.java b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinOrderingUtil.java new file mode 100644 index 0000000..3f6a1ca --- /dev/null +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinOrderingUtil.java @@ -0,0 +1,313 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you 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 org.apache.tajo.plan.joinorder; + +import org.apache.tajo.algebra.JoinType; +import org.apache.tajo.catalog.Column; +import org.apache.tajo.plan.expr.EvalNode; +import org.apache.tajo.plan.expr.EvalTreeUtil; +import org.apache.tajo.plan.expr.EvalType; +import org.apache.tajo.plan.util.PlannerUtil; +import org.apache.tajo.util.TUtil; + +import java.util.List; +import java.util.Set; + +public class JoinOrderingUtil { + + /** + * Find join conditions which can be evaluated at the given join edge. The result depends on the isOnPredicate flag + * which represents the given set of predicates is from the on clause of not. + * + * @param candidates set of predicates + * @param edge join edge + * @param isOnPredicates flag to represent the candidates from the on clause of not + * @return predicates which can be evaluated at the given join edge + */ + public static Set<EvalNode> findJoinConditionForJoinVertex(Set<EvalNode> candidates, JoinEdge edge, + boolean isOnPredicates) { + Set<EvalNode> conditionsForThisJoin = TUtil.newHashSet(); + for (EvalNode predicate : candidates) { + if (EvalTreeUtil.isJoinQual(predicate, false) + && checkIfEvaluatedAtEdge(predicate, edge, isOnPredicates)) { + conditionsForThisJoin.add(predicate); + } + } + return conditionsForThisJoin; + } + + /** + * Check whether the given predicate can be evaluated at the given join edge or not. The result depends on + * the isOnPredicate flag which represents the given predicate is from the on clause of not. + * + * @param evalNode predicate + * @param edge join edge + * @param isOnPredicate flag to represent the candidates from the on clause of not + * @return true if the predicate can be evaluated at the given join edge + */ + public static boolean checkIfEvaluatedAtEdge(EvalNode evalNode, JoinEdge edge, boolean isOnPredicate) { + Set<Column> columnRefs = EvalTreeUtil.findUniqueColumns(evalNode); + if (EvalTreeUtil.findDistinctAggFunction(evalNode).size() > 0) { + return false; + } + if (EvalTreeUtil.findEvalsByType(evalNode, EvalType.WINDOW_FUNCTION).size() > 0) { + return false; + } + if (columnRefs.size() > 0 && !edge.getSchema().containsAll(columnRefs)) { + return false; + } + // Currently, join filters cannot be evaluated at joins + if (PlannerUtil.isOuterJoinType(edge.getJoinType()) && !isOnPredicate) { + return false; + } + return true; + } + + /** + * Check the associativity between the given two join edges. + * For the associativity rules, please refer to the below isAssociativeJoinType() function. + * + * @param context join graph context + * @param leftEdge left join edge + * @param rightEdge right join edge + * @return true if two given join edges are associative. + */ + public static boolean isAssociativeJoin(JoinGraphContext context, JoinEdge leftEdge, JoinEdge rightEdge) { + if (isAssociativeJoinType(leftEdge.getJoinType(), rightEdge.getJoinType())) { + + // NOTE: There will be more predicates which are able to be evaluated at input join edges. + // In this case, the input edges are not considered as associative joins to evaluate those predicates at proper + // join edges, even though they have the associative relationship. + + // Create a temporal left-deep join node to find the potentially evaluatable quals. + JoinedRelationsVertex tempLeftChild = new JoinedRelationsVertex(leftEdge); + JoinEdge tempEdge = context.getCachedOrNewJoinEdge(rightEdge.getJoinSpec(), tempLeftChild, + rightEdge.getRightVertex()); + if ((rightEdge.getJoinType() != JoinType.INNER && rightEdge.getJoinType() != JoinType.CROSS) + || (leftEdge.getJoinType() != JoinType.INNER && leftEdge.getJoinType() != JoinType.CROSS)) { + if (!findJoinConditionForJoinVertex(context.getCandidateJoinConditions(), tempEdge, true).isEmpty()) { + return false; + } + if (!findJoinConditionForJoinVertex(context.getCandidateJoinFilters(), tempEdge, true).isEmpty()) { + return false; + } + } + return true; + } + return false; + } + + /** + * Check two join types are associative according to the following rule. + * + * <h3>Associativity rules</h3> + * + * ============================================================== + * Left-Hand Bracketed | Right-Hand Bracketed | Equivalence + * ============================================================== + * (A inner B) inner C | A inner (B inner C) | Equivalent + * (A left B) inner C | A left (B inner C) | Not equivalent + * (A right B) inner C | A right (B inner C) | Equivalent + * (A full B) inner C | A full (B inner C) | Not equivalent + * (A inner B) left C | A inner (B left C) | Equivalent + * (A left B) left C | A left (B left C) | Equivalent + * (A right B) left C | A right (B left C) | Equivalent + * (A full B) left C | A full (B left C) | Equivalent + * (A inner B) right C | A inner (B right C) | Not equivalent + * (A left B) right C | A left (B right C) | Not equivalent + * (A right B) right C | A right (B right C) | Equivalent + * (A full B) right C | A full (B right C) | Not equivalent + * (A inner B) full C | A inner (B full C) | Not equivalent + * (A left B) full C | A left (B full C) | Not equivalent + * (A right B) full C | A right (B full C) | Equivalent + * (A full B) full C | A full (B full C) | Equivalent + * ============================================================== + * + * @param leftType + * @param rightType + * @return true if two join types are associative. + */ + public static boolean isAssociativeJoinType(JoinType leftType, JoinType rightType) { + if (leftType == rightType) { + return true; + } + + if (leftType == JoinType.INNER && rightType == JoinType.CROSS || + leftType == JoinType.CROSS && rightType == JoinType.INNER) { + return true; + } + + if (leftType == JoinType.RIGHT_OUTER) { + return true; + } + + if (leftType == JoinType.LEFT_OUTER) { + // When the left type is the left outer join, input join types are associative + // if the right type is also the left outer join. + // This case is already checked above. + return false; + } + + if ((leftType == JoinType.INNER) || leftType == JoinType.CROSS) { + if (rightType == JoinType.LEFT_OUTER) { + return true; + } else { + return false; + } + } + + if (leftType == JoinType.FULL_OUTER) { + if (rightType == JoinType.LEFT_OUTER) { + return true; + } else { + return false; + } + } + + return false; + } + + /** + * Find all interchangeable vertexes from the given vertex. + * Join edges between relations are found at runtime. + * + * <H3>Vertex interchange rules</H3> + * - A vertex is interchangeable with the start vertex if it is reachable. + * - A vertex is reachable from the start vertex if it is able to replace another vertex which is connected to the start vertex. + * - A vertex is able to replace another vertex if they are connected without violating join commutativity or join associativity. + * + * @param context join graph context + * @param from start vertex + * @return + */ + public static Set<JoinVertex> getAllInterchangeableVertexes(JoinGraphContext context, JoinVertex from) { + Set<JoinVertex> founds = TUtil.newHashSet(); + getAllInterchangeableVertexes(founds, context, from); + return founds; + } + + public static void getAllInterchangeableVertexes(Set<JoinVertex> founds, JoinGraphContext context, JoinVertex vertex) { + founds.add(vertex); + Set<JoinVertex> foundAtThis = TUtil.newHashSet(); + List<JoinEdge> candidateEdges = context.getJoinGraph().getOutgoingEdges(vertex); + if (candidateEdges != null) { + for (JoinEdge candidateEdge : candidateEdges) { + // Evaluatable quals must be added to check the associativity of join edges. + candidateEdge = updateQualIfNecessary(context, candidateEdge); + if (!founds.contains(candidateEdge.getRightVertex())) { + List<JoinEdge> rightEdgesOfCandidate = context.getJoinGraph().getOutgoingEdges(candidateEdge.getRightVertex()); + boolean reacheable = false; + if (rightEdgesOfCandidate != null) { + reacheable = true; + for (JoinEdge rightEdgeOfCandidate : rightEdgesOfCandidate) { + // Evaluatable quals must be added to check the associativity of join edges. + rightEdgeOfCandidate = updateQualIfNecessary(context, rightEdgeOfCandidate); + if (!isAssociativeJoin(context, candidateEdge, rightEdgeOfCandidate)) { + reacheable = false; + break; + } + } + } + if (reacheable) { + foundAtThis.add(candidateEdge.getRightVertex()); + } + } + } + for (JoinVertex v : foundAtThis) { + getAllInterchangeableVertexes(founds, context, v); + } + } + } + + /** + * Check the given two join edges are equal or symmetric. + * + * @param edge1 + * @param edge2 + * @return True if two join edges are equal or symmetric. + */ + public static boolean isEqualsOrSymmetric(JoinEdge edge1, JoinEdge edge2) { + if (edge1.equals(edge2) || isSymmetric(edge1, edge2)) { + return true; + } + return false; + } + + /** + * Given two join edges e1 and e2, they are <b>symmetric</b> whey they satisfy the follwing conditions. + * + * <ul> + * <li>e1 and e2 have the same commutative join type.</li> + * <li>e1 and e2 have the same join condition.</li> + * <li>The left and right vertexes of e1 are the right and left vertexes of e2, respectively.</li> + * </ul> + * + * @param edge1 + * @param edge2 + * @return True if two join edges are symmetric. + */ + public static boolean isSymmetric(JoinEdge edge1, JoinEdge edge2) { + if (edge1.getLeftVertex().equals(edge2.getRightVertex()) && + edge1.getRightVertex().equals(edge2.getLeftVertex()) && + edge1.getJoinSpec().equals(edge2.getJoinSpec()) && + PlannerUtil.isCommutativeJoinType(edge1.getJoinType())) { + return true; + } + return false; + } + + /** + * If there are predicates which can be evaluated at the given join edge, push those predicates to the join edge. + * + * @param context + * @param edge + * @return + */ + public static JoinEdge updateQualIfNecessary(JoinGraphContext context, JoinEdge edge) { + Set<EvalNode> additionalPredicates = findJoinConditionForJoinVertex( + context.getCandidateJoinConditions(), edge, true); + additionalPredicates.addAll(findJoinConditionForJoinVertex( + context.getCandidateJoinFilters(), edge, false)); + edge.addJoinPredicates(additionalPredicates); + return edge; + } + + /** + * Find all edges that are associative with the given edge. + * + * @param context + * @param edge + * @return + */ + public static Set<JoinEdge> getAllAssociativeEdges(JoinGraphContext context, JoinEdge edge) { + Set<JoinEdge> associativeEdges = TUtil.newHashSet(); + JoinVertex start = edge.getRightVertex(); + List<JoinEdge> candidateEdges = context.getJoinGraph().getOutgoingEdges(start); + if (candidateEdges != null) { + for (JoinEdge candidateEdge : candidateEdges) { + candidateEdge = updateQualIfNecessary(context, candidateEdge); + if (!isEqualsOrSymmetric(edge, candidateEdge) && + isAssociativeJoin(context, edge, candidateEdge)) { + associativeEdges.add(candidateEdge); + } + } + } + return associativeEdges; + } +} http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinVertex.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinVertex.java b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinVertex.java new file mode 100644 index 0000000..328b474 --- /dev/null +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinVertex.java @@ -0,0 +1,32 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you 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 org.apache.tajo.plan.joinorder; + +import org.apache.tajo.catalog.Schema; +import org.apache.tajo.plan.LogicalPlan; +import org.apache.tajo.plan.logical.LogicalNode; + +import java.util.Set; + +public interface JoinVertex { + + Schema getSchema(); + Set<RelationVertex> getRelations(); + LogicalNode buildPlan(LogicalPlan plan, LogicalPlan.QueryBlock block); +} http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinedRelationsVertex.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinedRelationsVertex.java b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinedRelationsVertex.java new file mode 100644 index 0000000..6a72bb8 --- /dev/null +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/JoinedRelationsVertex.java @@ -0,0 +1,125 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you 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 org.apache.tajo.plan.joinorder; + +import org.apache.tajo.catalog.Schema; +import org.apache.tajo.catalog.SchemaUtil; +import org.apache.tajo.plan.LogicalPlan; +import org.apache.tajo.plan.logical.JoinNode; +import org.apache.tajo.plan.logical.LogicalNode; +import org.apache.tajo.plan.logical.RelationNode; +import org.apache.tajo.plan.util.PlannerUtil; +import org.apache.tajo.util.TUtil; + +import java.util.Set; + +/** + * The join order is fixed in this vertex. + */ +public class JoinedRelationsVertex implements JoinVertex { + + private final Set<RelationVertex> relations = TUtil.newHashSet(); + private final JoinEdge joinEdge; + + public JoinedRelationsVertex(JoinEdge joinEdge) { + this.joinEdge = joinEdge; + findRelationVertexes(this.joinEdge); + } + + private void findRelationVertexes(JoinEdge edge) { + if (edge.getLeftVertex() instanceof JoinedRelationsVertex) { + JoinedRelationsVertex leftChild = (JoinedRelationsVertex) edge.getLeftVertex(); + findRelationVertexes(leftChild.getJoinEdge()); + } else { + relations.add((RelationVertex) edge.getLeftVertex()); + } + if (edge.getRightVertex() instanceof JoinedRelationsVertex) { + JoinedRelationsVertex rightChild = (JoinedRelationsVertex) edge.getRightVertex(); + findRelationVertexes(rightChild.getJoinEdge()); + } else { + relations.add((RelationVertex) edge.getRightVertex()); + } + } + + public JoinEdge getJoinEdge() { + return joinEdge; + } + + @Override + public Schema getSchema() { + return joinEdge.getSchema(); + } + + @Override + public String toString() { + return joinEdge.toString(); + } + + @Override + public Set<RelationVertex> getRelations() { + return relations; + } + + @Override + public LogicalNode buildPlan(LogicalPlan plan, LogicalPlan.QueryBlock block) { + // TODO + LogicalNode leftChild = joinEdge.getLeftVertex().buildPlan(plan, block); + LogicalNode rightChild = joinEdge.getRightVertex().buildPlan(plan, block); + + JoinNode joinNode = plan.createNode(JoinNode.class); + + if (PlannerUtil.isCommutativeJoinType(joinEdge.getJoinType())) { + // if only one operator is relation + if ((leftChild instanceof RelationNode) && !(rightChild instanceof RelationNode)) { + // for left deep + joinNode.init(joinEdge.getJoinType(), rightChild, leftChild); + } else { + // if both operators are relation or if both are relations + // we don't need to concern the left-right position. + joinNode.init(joinEdge.getJoinType(), leftChild, rightChild); + } + } else { + joinNode.init(joinEdge.getJoinType(), leftChild, rightChild); + } + + Schema mergedSchema = SchemaUtil.merge(joinNode.getLeftChild().getOutSchema(), + joinNode.getRightChild().getOutSchema()); + joinNode.setInSchema(mergedSchema); + joinNode.setOutSchema(mergedSchema); + if (joinEdge.hasJoinQual()) { + joinNode.setJoinQual(joinEdge.getSingletonJoinQual()); + } + block.registerNode(joinNode); + return joinNode; + } + + @Override + public boolean equals(Object o) { + if (o instanceof JoinedRelationsVertex) { + return this.joinEdge.equals(((JoinedRelationsVertex) o).joinEdge); + } + return false; + } + + @Override + public int hashCode() { + return joinEdge.hashCode(); + } + +} http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/RelationVertex.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/RelationVertex.java b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/RelationVertex.java new file mode 100644 index 0000000..a7e3a4f --- /dev/null +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/joinorder/RelationVertex.java @@ -0,0 +1,76 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you 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 org.apache.tajo.plan.joinorder; + +import org.apache.tajo.catalog.Schema; +import org.apache.tajo.plan.LogicalPlan; +import org.apache.tajo.plan.logical.LogicalNode; +import org.apache.tajo.plan.logical.RelationNode; +import org.apache.tajo.util.TUtil; + +import java.util.Set; + +public class RelationVertex implements JoinVertex{ + + private final RelationNode relationNode; + private final LogicalNode topLogicalNode; + +public RelationVertex(RelationNode relationNode) { + this.relationNode = relationNode; + this.topLogicalNode = relationNode; + } + + @Override + public String toString() { + return relationNode.getCanonicalName(); + } + + @Override + public boolean equals(Object o) { + if (o instanceof RelationVertex) { + RelationVertex other = (RelationVertex) o; + return this.relationNode.equals(other.relationNode) && this.topLogicalNode.equals(other.topLogicalNode); + } + return false; + } + + @Override + public int hashCode() { + return relationNode.hashCode(); + } + + @Override + public Schema getSchema() { + return relationNode.getOutSchema(); + } + + @Override + public Set<RelationVertex> getRelations() { + return TUtil.newHashSet(this); + } + + @Override + public LogicalNode buildPlan(LogicalPlan plan, LogicalPlan.QueryBlock block) { + return topLogicalNode; + } + + public LogicalNode getRelationNode() { + return relationNode; + } +} http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/logical/JoinNode.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/logical/JoinNode.java b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/JoinNode.java index a0d8125..4f36026 100644 --- a/tajo-plan/src/main/java/org/apache/tajo/plan/logical/JoinNode.java +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/JoinNode.java @@ -25,7 +25,6 @@ import com.google.gson.annotations.Expose; import org.apache.tajo.algebra.JoinType; import org.apache.tajo.plan.PlanString; import org.apache.tajo.plan.Target; -import org.apache.tajo.plan.expr.BinaryEval; import org.apache.tajo.plan.expr.EvalNode; import org.apache.tajo.plan.util.PlannerUtil; import org.apache.tajo.util.TUtil; @@ -33,8 +32,7 @@ import org.apache.tajo.util.TUtil; import java.util.Arrays; public class JoinNode extends BinaryNode implements Projectable, Cloneable { - @Expose private JoinType joinType; - @Expose private EvalNode joinQual; + @Expose private JoinSpec joinSpec = new JoinSpec(); @Expose private Target[] targets; public JoinNode(int pid) { @@ -42,29 +40,33 @@ public class JoinNode extends BinaryNode implements Projectable, Cloneable { } public void init(JoinType joinType, LogicalNode left, LogicalNode right) { - this.joinType = joinType; + this.joinSpec.setType(joinType); setLeftChild(left); setRightChild(right); } public JoinType getJoinType() { - return this.joinType; + return this.joinSpec.getType(); + } + + public JoinSpec getJoinSpec() { + return joinSpec; } public void setJoinType(JoinType joinType) { - this.joinType = joinType; + this.joinSpec.setType(joinType); } public void setJoinQual(EvalNode joinQual) { - this.joinQual = joinQual; + this.joinSpec.setSingletonPredicate(joinQual); } public boolean hasJoinQual() { - return this.joinQual != null; + return this.joinSpec.hasPredicates(); } public EvalNode getJoinQual() { - return this.joinQual; + return this.joinSpec.getSingletonPredicate(); } @Override @@ -85,9 +87,9 @@ public class JoinNode extends BinaryNode implements Projectable, Cloneable { @Override public PlanString getPlanString() { - PlanString planStr = new PlanString(this).appendTitle("(").appendTitle(joinType.name()).appendTitle(")"); + PlanString planStr = new PlanString(this).appendTitle("(").appendTitle(joinSpec.getType().name()).appendTitle(")"); if (hasJoinQual()) { - planStr.addExplan("Join Cond: " + joinQual.toString()); + planStr.addExplan("Join Cond: " + joinSpec.getSingletonPredicate().toString()); } if (hasTargets()) { @@ -112,8 +114,7 @@ public class JoinNode extends BinaryNode implements Projectable, Cloneable { public int hashCode() { final int prime = 31; int result = 1; - result = prime * result + ((joinQual == null) ? 0 : joinQual.hashCode()); - result = prime * result + ((joinType == null) ? 0 : joinType.hashCode()); + result = prime * result + joinSpec.hashCode(); result = prime * result + Arrays.hashCode(targets); return result; } @@ -122,9 +123,8 @@ public class JoinNode extends BinaryNode implements Projectable, Cloneable { public boolean equals(Object obj) { if (obj instanceof JoinNode) { JoinNode other = (JoinNode) obj; - boolean eq = this.joinType.equals(other.joinType); + boolean eq = this.joinSpec.equals(other.joinSpec); eq &= TUtil.checkEquals(this.targets, other.targets); - eq &= TUtil.checkEquals(joinQual, other.joinQual); return eq && leftChild.equals(other.leftChild) && rightChild.equals(other.rightChild); } else { return false; @@ -134,8 +134,7 @@ public class JoinNode extends BinaryNode implements Projectable, Cloneable { @Override public Object clone() throws CloneNotSupportedException { JoinNode join = (JoinNode) super.clone(); - join.joinType = this.joinType; - join.joinQual = this.joinQual == null ? null : (BinaryEval) this.joinQual.clone(); + join.joinSpec = (JoinSpec) this.joinSpec.clone(); if (hasTargets()) { join.targets = new Target[targets.length]; for (int i = 0; i < targets.length; i++) { @@ -146,9 +145,9 @@ public class JoinNode extends BinaryNode implements Projectable, Cloneable { } public String toString() { - StringBuilder sb = new StringBuilder("Join (type").append(joinType); + StringBuilder sb = new StringBuilder("Join (type").append(joinSpec.getType()); if (hasJoinQual()) { - sb.append(",filter=").append(joinQual); + sb.append(",filter=").append(joinSpec.getSingletonPredicate()); } sb.append(")"); return sb.toString(); http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/logical/JoinSpec.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/logical/JoinSpec.java b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/JoinSpec.java new file mode 100644 index 0000000..7643e4b --- /dev/null +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/JoinSpec.java @@ -0,0 +1,132 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you 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 org.apache.tajo.plan.logical; + +import com.google.common.base.Objects; +import org.apache.tajo.algebra.JoinType; +import org.apache.tajo.plan.expr.AlgebraicUtil; +import org.apache.tajo.plan.expr.EvalNode; +import org.apache.tajo.util.TUtil; + +import java.util.Comparator; +import java.util.Set; +import java.util.TreeSet; + +public class JoinSpec implements Cloneable { + + private static class EvalNodeComparator implements Comparator<EvalNode> { + + @Override + public int compare(EvalNode e1, EvalNode e2) { + return e1.toJson().compareTo(e2.toJson()); + } + } + + private JoinType type = null; + private Set<EvalNode> predicates = new TreeSet<EvalNode>(new EvalNodeComparator()); + + public JoinSpec() { + + } + + public JoinSpec(JoinType type) { + this.type = type; + } + + public void addPredicate(EvalNode predicate) { + + if (!predicates.isEmpty()) { + if (type == JoinType.CROSS) { + type = JoinType.INNER; + } + } + this.predicates.add(predicate); + } + + public void addPredicates(Set<EvalNode> predicates) { + if (!predicates.isEmpty()) { + if (type == JoinType.CROSS) { + type = JoinType.INNER; + } + } + this.predicates.addAll(predicates); + } + + public boolean hasPredicates() { + return predicates.size() > 0; + } + + public void setPredicates(Set<EvalNode> predicates) { + this.predicates.clear(); + if (predicates == null || predicates.isEmpty()) { + if (type == JoinType.INNER) { + type = JoinType.CROSS; + } + } else { + this.predicates.addAll(predicates); + } + } + + public void setSingletonPredicate(EvalNode predicates) { + this.setPredicates(TUtil.newHashSet(AlgebraicUtil.toConjunctiveNormalFormArray(predicates))); + } + + public EvalNode getSingletonPredicate() { + if (predicates.size() > 1) { + return AlgebraicUtil.createSingletonExprFromCNF(predicates.toArray(new EvalNode[predicates.size()])); + } else if (predicates.size() == 1) { + return predicates.iterator().next(); + } else { + return null; + } + } + + public Set<EvalNode> getPredicates() { + return predicates; + } + + public JoinType getType() { + return type; + } + + public void setType(JoinType type) { + this.type = type; + } + + @Override + public boolean equals(Object o) { + if (o instanceof JoinSpec) { + JoinSpec other = (JoinSpec) o; + return this.type == other.type && this.predicates.equals(other.predicates); + } + return false; + } + + @Override + public int hashCode() { + return Objects.hashCode(type, predicates.hashCode()); + } + + @Override + public Object clone() throws CloneNotSupportedException { + JoinSpec clone = new JoinSpec(this.type); + clone.setPredicates(this.predicates); + return clone; + } +} http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/logical/ScanNode.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/logical/ScanNode.java b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/ScanNode.java index 0ba988f..8e369d6 100644 --- a/tajo-plan/src/main/java/org/apache/tajo/plan/logical/ScanNode.java +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/logical/ScanNode.java @@ -180,6 +180,7 @@ public class ScanNode extends RelationNode implements Projectable, SelectableNod eq = eq && TUtil.checkEquals(this.tableDesc, other.tableDesc); eq = eq && TUtil.checkEquals(this.qual, other.qual); eq = eq && TUtil.checkEquals(this.targets, other.targets); + eq = eq && TUtil.checkEquals(this.alias, other.alias); return eq; } http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/FilterPushDownRule.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/FilterPushDownRule.java b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/FilterPushDownRule.java index 587baa5..ee932fd 100644 --- a/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/FilterPushDownRule.java +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/rewrite/rules/FilterPushDownRule.java @@ -248,7 +248,7 @@ public class FilterPushDownRule extends BasicLogicalPlanVisitor<FilterPushDownCo nonPushableQuals.addAll(extractNonEquiThetaJoinQuals(onPredicates, block, joinNode)); // for outer joins - if (PlannerUtil.isOuterJoin(joinNode.getJoinType())) { + if (PlannerUtil.isOuterJoinType(joinNode.getJoinType())) { nonPushableQuals.addAll(extractNonPushableOuterJoinQuals(plan, onPredicates, wherePredicates, joinNode)); } return nonPushableQuals; http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/util/PlannerUtil.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/util/PlannerUtil.java b/tajo-plan/src/main/java/org/apache/tajo/plan/util/PlannerUtil.java index 19e6ad1..e314f99 100644 --- a/tajo-plan/src/main/java/org/apache/tajo/plan/util/PlannerUtil.java +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/util/PlannerUtil.java @@ -487,7 +487,7 @@ public class PlannerUtil { Preconditions.checkNotNull(type); ParentNodeFinder finder = new ParentNodeFinder(type); - node.postOrder(finder); + node.preOrder(finder); if (finder.getFoundNodes().size() == 0) { return null; @@ -770,11 +770,12 @@ public class PlannerUtil { } } - public static boolean isCommutativeJoin(JoinType joinType) { - return joinType == JoinType.INNER; + public static boolean isCommutativeJoinType(JoinType joinType) { + // Full outer join is also commutative. + return joinType == JoinType.INNER || joinType == JoinType.CROSS || joinType == JoinType.FULL_OUTER; } - public static boolean isOuterJoin(JoinType joinType) { + public static boolean isOuterJoinType(JoinType joinType) { return joinType == JoinType.LEFT_OUTER || joinType == JoinType.RIGHT_OUTER || joinType==JoinType.FULL_OUTER; } http://git-wip-us.apache.org/repos/asf/tajo/blob/bedce3aa/tajo-plan/src/main/java/org/apache/tajo/plan/visitor/BasicLogicalPlanVisitor.java ---------------------------------------------------------------------- diff --git a/tajo-plan/src/main/java/org/apache/tajo/plan/visitor/BasicLogicalPlanVisitor.java b/tajo-plan/src/main/java/org/apache/tajo/plan/visitor/BasicLogicalPlanVisitor.java index ecf9050..90ff1dc 100644 --- a/tajo-plan/src/main/java/org/apache/tajo/plan/visitor/BasicLogicalPlanVisitor.java +++ b/tajo-plan/src/main/java/org/apache/tajo/plan/visitor/BasicLogicalPlanVisitor.java @@ -54,6 +54,7 @@ public class BasicLogicalPlanVisitor<CONTEXT, RESULT> implements LogicalPlanVisi public RESULT visit(CONTEXT context, LogicalPlan plan, LogicalPlan.QueryBlock block, LogicalNode node, Stack<LogicalNode> stack) throws PlanningException { + preHook(plan, node, stack, context); RESULT current; switch (node.getType()) { case ROOT: @@ -141,6 +142,7 @@ public class BasicLogicalPlanVisitor<CONTEXT, RESULT> implements LogicalPlanVisi throw new PlanningException("Unknown logical node type: " + node.getType()); } + postHook(plan, node, stack, context); return current; }
