View Javadoc

1   /*
2    * ModeShape (http://www.modeshape.org)
3    * See the COPYRIGHT.txt file distributed with this work for information
4    * regarding copyright ownership.  Some portions may be licensed
5    * to Red Hat, Inc. under one or more contributor license agreements.
6    * See the AUTHORS.txt file in the distribution for a full listing of 
7    * individual contributors.
8    *
9    * ModeShape is free software. Unless otherwise indicated, all code in ModeShape
10   * is licensed to you under the terms of the GNU Lesser General Public License as
11   * published by the Free Software Foundation; either version 2.1 of
12   * the License, or (at your option) any later version.
13   * 
14   * ModeShape is distributed in the hope that it will be useful,
15   * but WITHOUT ANY WARRANTY; without even the implied warranty of
16   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17   * Lesser General Public License for more details.
18   *
19   * You should have received a copy of the GNU Lesser General Public
20   * License along with this software; if not, write to the Free
21   * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
22   * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
23   */
24  package org.modeshape.graph.query.optimize;
25  
26  import java.util.HashMap;
27  import java.util.LinkedList;
28  import java.util.List;
29  import java.util.Map;
30  import net.jcip.annotations.Immutable;
31  import org.modeshape.graph.GraphI18n;
32  import org.modeshape.graph.query.QueryContext;
33  import org.modeshape.graph.query.model.Column;
34  import org.modeshape.graph.query.model.EquiJoinCondition;
35  import org.modeshape.graph.query.model.JoinCondition;
36  import org.modeshape.graph.query.model.SameNodeJoinCondition;
37  import org.modeshape.graph.query.model.SelectorName;
38  import org.modeshape.graph.query.plan.PlanNode;
39  import org.modeshape.graph.query.plan.PlanUtil;
40  import org.modeshape.graph.query.plan.PlanNode.Property;
41  import org.modeshape.graph.query.plan.PlanNode.Type;
42  import org.modeshape.graph.query.validate.Schemata;
43  import org.modeshape.graph.query.validate.Schemata.Table;
44  
45  /**
46   * An {@link OptimizerRule optimizer rule} that rewrites JOIN nodes that have {@link EquiJoinCondition equi-join criteria} where
47   * the columns involved in the equi-join are all identity columns (that is, they form a {@link Schemata.Table#getKeys() key} for
48   * the table). This rewrite only happens when the left and right children of the JOIN node are both SOURCE nodes.
49   * <p>
50   * The basic idea is that in these identity equi-join cases, the following structure:
51   * 
52   * <pre>
53   *          ...
54   *           |
55   *         JOIN
56   *        /     \
57   *       /       \
58   *   SOURCE     SOURCE
59   * </pre>
60   * 
61   * is transformed into a simple SOURCE node:
62   * 
63   * <pre>
64   *        ...
65   *         |
66   *       SOURCE
67   * </pre>
68   * 
69   * Note that this rewriting removes a selector, and thus the nodes above the JOIN node that made use of the removed selector are
70   * also modified to reference the remaining selector.
71   * </p>
72   */
73  @Immutable
74  public class RewriteIdentityJoins implements OptimizerRule {
75  
76      public static final RewriteIdentityJoins INSTANCE = new RewriteIdentityJoins();
77  
78      /**
79       * {@inheritDoc}
80       * 
81       * @see org.modeshape.graph.query.optimize.OptimizerRule#execute(org.modeshape.graph.query.QueryContext,
82       *      org.modeshape.graph.query.plan.PlanNode, java.util.LinkedList)
83       */
84      public PlanNode execute( QueryContext context,
85                               PlanNode plan,
86                               LinkedList<OptimizerRule> ruleStack ) {
87          if (!context.getHints().hasJoin) return plan;
88  
89          // For each of the JOIN nodes ...
90          Map<SelectorName, SelectorName> rewrittenSelectors = null;
91          int rewrittenJoins = 0;
92          int numJoins = 0;
93          for (PlanNode joinNode : plan.findAllAtOrBelow(Type.JOIN)) {
94              ++numJoins;
95              JoinCondition condition = joinNode.getProperty(Property.JOIN_CONDITION, JoinCondition.class);
96              if (condition instanceof EquiJoinCondition) {
97                  PlanNode leftNode = joinNode.getFirstChild().findAtOrBelow(Type.SOURCE);
98                  PlanNode rightNode = joinNode.getLastChild().findAtOrBelow(Type.SOURCE);
99                  assert leftNode != null;
100                 assert rightNode != null;
101                 EquiJoinCondition equiJoin = (EquiJoinCondition)condition;
102                 // Find the names (or aliases) of the tables ...
103                 Schemata schemata = context.getSchemata();
104                 assert schemata != null;
105                 SelectorName leftTableName = leftNode.getProperty(Property.SOURCE_NAME, SelectorName.class);
106                 SelectorName rightTableName = rightNode.getProperty(Property.SOURCE_NAME, SelectorName.class);
107                 assert leftTableName != null;
108                 assert rightTableName != null;
109                 // Presumably the join condition is using at least one alias, but we only care about the actual name ...
110                 if (!leftTableName.equals(rightTableName)) {
111                     // The join is not joining the same table, so this doesn't meet the condition ...
112                     continue;
113                 }
114                 // Find the schemata columns referenced by the join condition ...
115                 Table table = schemata.getTable(leftTableName);
116                 if (table == null) {
117                     context.getProblems().addError(GraphI18n.tableDoesNotExist, leftTableName);
118                     continue;
119                 }
120                 String leftColumnName = equiJoin.getProperty1Name();
121                 String rightColumnName = equiJoin.getProperty2Name();
122                 Schemata.Column leftColumn = table.getColumn(leftColumnName);
123                 Schemata.Column rightColumn = table.getColumn(rightColumnName);
124                 if (leftColumn == null) {
125                     context.getProblems().addError(GraphI18n.columnDoesNotExistOnTable, leftColumnName, leftTableName);
126                     continue;
127                 }
128                 if (rightColumn == null) {
129                     context.getProblems().addError(GraphI18n.columnDoesNotExistOnTable, rightColumnName, leftTableName);
130                     continue;
131                 }
132                 // Are the join columns (on both sides) keys?
133                 if (table.hasKey(leftColumn) && (rightColumn == leftColumn || table.hasKey(rightColumn))) {
134                     // It meets all the criteria, so rewrite this join node ...
135                     if (rewrittenSelectors == null) rewrittenSelectors = new HashMap<SelectorName, SelectorName>();
136                     rewriteJoinNode(context, joinNode, rewrittenSelectors);
137                     ++rewrittenJoins;
138                 }
139             } else if (condition instanceof SameNodeJoinCondition) {
140                 SameNodeJoinCondition sameNodeCondition = (SameNodeJoinCondition)condition;
141                 if (sameNodeCondition.getSelector1Name().equals(sameNodeCondition.getSelector2Name())
142                     && sameNodeCondition.getSelector2Path() == null) {
143                     // It meets all the criteria, so rewrite this join node ...
144                     if (rewrittenSelectors == null) rewrittenSelectors = new HashMap<SelectorName, SelectorName>();
145                     rewriteJoinNode(context, joinNode, rewrittenSelectors);
146                     ++rewrittenJoins;
147                 }
148             }
149         }
150 
151         if (rewrittenSelectors != null && !rewrittenSelectors.isEmpty()) {
152             // We re-wrote at least one JOIN, but since this only applies to JOIN nodes that meet certain criteria,
153             // the rewriting may have changed JOIN nodes that did not meet this criteria into nodes that now meet
154             // this criteria, so we need to re-run this rule...
155             ruleStack.addFirst(this);
156 
157             // After this rule is done as is no longer needed, we need to try to push SELECTs and PROJECTs again ...
158             if (!(ruleStack.peek() instanceof PushSelectCriteria)) {
159                 // We haven't already added these, so add them now ...
160                 ruleStack.addFirst(PushProjects.INSTANCE);
161                 if (context.getHints().hasCriteria) {
162                     ruleStack.addFirst(PushSelectCriteria.INSTANCE);
163                 }
164             }
165 
166             // Now rewrite the various portions of the plan that make use of the now-removed selectors ...
167             PlanUtil.replaceReferencesToRemovedSource(context, plan, rewrittenSelectors);
168 
169             assert rewrittenJoins > 0;
170             if (rewrittenJoins == numJoins) {
171                 assert plan.findAllAtOrBelow(Type.JOIN).isEmpty();
172                 context.getHints().hasJoin = false;
173             }
174         }
175         return plan;
176     }
177 
178     protected void rewriteJoinNode( QueryContext context,
179                                     PlanNode joinNode,
180                                     Map<SelectorName, SelectorName> rewrittenSelectors ) {
181         // Remove the right source node from the join node ...
182         PlanNode rightChild = joinNode.getLastChild();
183         rightChild.removeFromParent();
184         PlanNode rightSource = rightChild.findAtOrBelow(Type.SOURCE);
185 
186         // Replace the join node with the left source node ...
187         PlanNode leftChild = joinNode.getFirstChild();
188         joinNode.extractFromParent();
189         PlanNode leftSource = leftChild.findAtOrBelow(Type.SOURCE);
190 
191         // Combine the right PROJECT node with that on the left ...
192         PlanNode rightProject = rightChild.findAtOrBelow(Type.PROJECT);
193         if (rightProject != null) {
194             PlanNode leftProject = leftChild.findAtOrBelow(Type.PROJECT);
195             if (leftProject != null) {
196                 List<Column> leftColumns = leftProject.getPropertyAsList(Property.PROJECT_COLUMNS, Column.class);
197                 for (Column rightColumn : rightProject.getPropertyAsList(Property.PROJECT_COLUMNS, Column.class)) {
198                     if (!leftColumns.contains(rightColumn)) leftColumns.add(rightColumn);
199                 }
200             } else {
201                 // Just create a project on the left side ...
202                 leftProject = new PlanNode(Type.PROJECT);
203                 leftProject.setProperty(Property.PROJECT_COLUMNS, rightProject.getProperty(Property.PROJECT_COLUMNS));
204                 leftChild.getFirstChild().insertAsParent(leftProject);
205             }
206         }
207 
208         // Accumulate any SELECT nodes from the right side and add to the left ...
209         PlanNode topRightSelect = rightChild.findAtOrBelow(Type.SELECT);
210         if (topRightSelect != null) {
211             PlanNode bottomRightSelect = topRightSelect;
212             while (true) {
213                 if (bottomRightSelect.getFirstChild().isNot(Type.SELECT)) break;
214                 bottomRightSelect = bottomRightSelect.getFirstChild();
215             }
216             topRightSelect.setParent(null);
217             bottomRightSelect.removeAllChildren();
218             // Place just above the left source ...
219             leftSource.getParent().addLastChild(topRightSelect);
220             leftSource.setParent(bottomRightSelect);
221         }
222 
223         // Now record that references to the right selector name should be removed ...
224         SelectorName rightTableName = rightSource.getProperty(Property.SOURCE_NAME, SelectorName.class);
225         SelectorName rightTableAlias = rightSource.getProperty(Property.SOURCE_ALIAS, SelectorName.class);
226         SelectorName leftTableAlias = leftSource.getProperty(Property.SOURCE_ALIAS, SelectorName.class);
227         if (leftTableAlias != null) {
228             if (rightTableName != null) rewrittenSelectors.put(rightTableName, leftTableAlias);
229             if (rightTableAlias != null) rewrittenSelectors.put(rightTableAlias, leftTableAlias);
230         } else {
231             SelectorName leftTableName = leftSource.getProperty(Property.SOURCE_NAME, SelectorName.class);
232             assert leftTableName != null;
233             if (rightTableName != null) rewrittenSelectors.put(rightTableName, leftTableName);
234             if (rightTableAlias != null) rewrittenSelectors.put(rightTableAlias, leftTableName);
235         }
236     }
237 
238     /**
239      * {@inheritDoc}
240      * 
241      * @see java.lang.Object#toString()
242      */
243     @Override
244     public String toString() {
245         return getClass().getSimpleName();
246     }
247 
248 }