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.LinkedList;
27  import java.util.List;
28  import java.util.Set;
29  import net.jcip.annotations.Immutable;
30  import org.modeshape.graph.query.QueryContext;
31  import org.modeshape.graph.query.model.ChildNodeJoinCondition;
32  import org.modeshape.graph.query.model.DescendantNodeJoinCondition;
33  import org.modeshape.graph.query.model.DynamicOperand;
34  import org.modeshape.graph.query.model.EquiJoinCondition;
35  import org.modeshape.graph.query.model.JoinCondition;
36  import org.modeshape.graph.query.model.Order;
37  import org.modeshape.graph.query.model.Ordering;
38  import org.modeshape.graph.query.model.PropertyValue;
39  import org.modeshape.graph.query.model.SameNodeJoinCondition;
40  import org.modeshape.graph.query.model.SelectorName;
41  import org.modeshape.graph.query.plan.JoinAlgorithm;
42  import org.modeshape.graph.query.plan.PlanNode;
43  import org.modeshape.graph.query.plan.PlanNode.Property;
44  import org.modeshape.graph.query.plan.PlanNode.Type;
45  
46  /**
47   * An {@link OptimizerRule optimizer rule} that choose the appropriate join algorithm and sets up any prerequisites, based upon
48   * the {@link JoinCondition}.
49   * <p>
50   * There are two static instances that can be used (or the equivalent can be instantiated or subclassed using the constructor):
51   * one that only uses {@link JoinAlgorithm#NESTED_LOOP nested-loop}, and another that will attempt to use
52   * {@link JoinAlgorithm#MERGE merge} where possible. Both instances ignore any existing {@link Property#JOIN_ALGORITHM} property
53   * value set on the JOIN node.
54   * </p>
55   * <p>
56   * For example, the {@link #USE_ONLY_NESTED_JOIN_ALGORITHM} instance will convert this simple tree:
57   * 
58   * <pre>
59   *          ...
60   *           |
61   *         JOIN
62   *        /     \
63   *      ...     ...
64   * </pre>
65   * 
66   * into this:
67   * 
68   * <pre>
69   *          ...
70   *           |
71   *         JOIN ({@link Property#JOIN_ALGORITHM JOIN_ALGORITHM}={@link JoinAlgorithm#NESTED_LOOP NESTED_LOOP})
72   *        /     \
73   *      ...     ...
74   * </pre>
75   * 
76   * On the other hand, the {@link #USE_BEST_JOIN_ALGORITHM} instance will do a couple of different things, depending upon the input
77   * plan.
78   * <ol>
79   * <li>If the condition is a {@link DescendantNodeJoinCondition}, then the join algorithm will always be
80   * {@link JoinAlgorithm#NESTED_LOOP}.</li>
81   * <li>Otherwise, the rule will use the {@link JoinAlgorithm#MERGE} algorithm and will change this structure:
82   * 
83   * <pre>
84   *          ...
85   *           |
86   *         JOIN
87   *        /     \
88   *      ...     ...
89   * </pre>
90   * 
91   * into this:
92   * 
93   * <pre>
94   *          ...
95   *           |
96   *         JOIN ({@link Property#JOIN_ALGORITHM JOIN_ALGORITHM}={@link JoinAlgorithm#MERGE MERGE})
97   *        /     \
98   *       /       \
99   * DUP_REMOVE  DUP_REMOVE
100  *     |           |
101  *    SORT       SORT
102  *     |           |
103  *    ...         ...
104  * </pre>
105  * 
106  * </li>
107  * </ol>
108  * </p>
109  */
110 @Immutable
111 public class ChooseJoinAlgorithm implements OptimizerRule {
112 
113     public static final ChooseJoinAlgorithm USE_ONLY_NESTED_JOIN_ALGORITHM = new ChooseJoinAlgorithm(true);
114     public static final ChooseJoinAlgorithm USE_BEST_JOIN_ALGORITHM = new ChooseJoinAlgorithm(false);
115 
116     private final boolean useOnlyNested;
117 
118     protected ChooseJoinAlgorithm( boolean useOnlyNested ) {
119         this.useOnlyNested = useOnlyNested;
120     }
121 
122     /**
123      * {@inheritDoc}
124      * 
125      * @see org.modeshape.graph.query.optimize.OptimizerRule#execute(org.modeshape.graph.query.QueryContext,
126      *      org.modeshape.graph.query.plan.PlanNode, java.util.LinkedList)
127      */
128     public PlanNode execute( QueryContext context,
129                              PlanNode plan,
130                              LinkedList<OptimizerRule> ruleStack ) {
131         // For each of the JOIN nodes ...
132         for (PlanNode joinNode : plan.findAllAtOrBelow(Type.JOIN)) {
133             JoinCondition condition = joinNode.getProperty(Property.JOIN_CONDITION, JoinCondition.class);
134             if (useOnlyNested) {
135                 joinNode.setProperty(Property.JOIN_ALGORITHM, JoinAlgorithm.NESTED_LOOP);
136                 break;
137             }
138 
139             if (condition instanceof DescendantNodeJoinCondition) {
140                 // It has to be a nest-loop join ...
141                 joinNode.setProperty(Property.JOIN_ALGORITHM, JoinAlgorithm.NESTED_LOOP);
142             } else {
143                 joinNode.setProperty(Property.JOIN_ALGORITHM, JoinAlgorithm.MERGE);
144                 assert joinNode.getChildCount() == 2;
145 
146                 // We can try to use the merge join, but we need to sort and remove remove duplicates ...
147                 // on the left and right children of the join ...
148                 Set<SelectorName> leftSelectors = joinNode.getFirstChild().getSelectors();
149                 Set<SelectorName> rightSelectors = joinNode.getLastChild().getSelectors();
150                 List<Object> leftSortBy = new LinkedList<Object>();
151                 List<Object> rightSortBy = new LinkedList<Object>();
152                 createOrderBysForJoinCondition(condition, leftSelectors, leftSortBy, rightSelectors, rightSortBy);
153 
154                 PlanNode leftSort = new PlanNode(Type.SORT, leftSelectors);
155                 leftSort.setProperty(Property.SORT_ORDER_BY, leftSortBy);
156                 joinNode.getFirstChild().insertAsParent(leftSort);
157                 if (joinNode.getFirstChild().findAllAtOrBelow(Type.DUP_REMOVE).isEmpty()) {
158                     // There is no duplicate removal below the left-hand side of the join, so insert it ...
159                     PlanNode leftDupRemoval = new PlanNode(Type.DUP_REMOVE, leftSelectors);
160                     joinNode.getFirstChild().insertAsParent(leftDupRemoval);
161                 }
162 
163                 // There is no sort below the right-hand side of the join, so insert it ...
164                 PlanNode rightSort = new PlanNode(Type.SORT, rightSelectors);
165                 rightSort.setProperty(Property.SORT_ORDER_BY, rightSortBy);
166                 joinNode.getLastChild().insertAsParent(rightSort);
167                 if (joinNode.getLastChild().findAllAtOrBelow(Type.DUP_REMOVE).isEmpty()) {
168                     // There is no duplicate removal below the right-hand side of the join, so insert it ...
169                     PlanNode rightDupRemoval = new PlanNode(Type.DUP_REMOVE, rightSelectors);
170                     joinNode.getLastChild().insertAsParent(rightDupRemoval);
171                 }
172             }
173         }
174         return plan;
175     }
176 
177     protected void createOrderBysForJoinCondition( JoinCondition condition,
178                                                    Set<SelectorName> leftSelectors,
179                                                    List<Object> leftSortBy,
180                                                    Set<SelectorName> rightSelectors,
181                                                    List<Object> rightSortBy ) {
182         if (condition instanceof SameNodeJoinCondition) {
183             SameNodeJoinCondition joinCondition = (SameNodeJoinCondition)condition;
184             SelectorName name1 = joinCondition.getSelector1Name();
185             SelectorName name2 = joinCondition.getSelector2Name();
186             if (leftSelectors.contains(name1)) {
187                 leftSortBy.add(name1);
188                 rightSortBy.add(name2);
189             } else {
190                 leftSortBy.add(name2);
191                 rightSortBy.add(name1);
192             }
193         } else if (condition instanceof ChildNodeJoinCondition) {
194             ChildNodeJoinCondition joinCondition = (ChildNodeJoinCondition)condition;
195             SelectorName childName = joinCondition.getChildSelectorName();
196             SelectorName parentName = joinCondition.getParentSelectorName();
197             if (leftSelectors.contains(childName)) {
198                 leftSortBy.add(childName);
199                 rightSortBy.add(parentName);
200             } else {
201                 leftSortBy.add(parentName);
202                 rightSortBy.add(childName);
203             }
204         } else if (condition instanceof EquiJoinCondition) {
205             EquiJoinCondition joinCondition = (EquiJoinCondition)condition;
206             SelectorName selector1 = joinCondition.getSelector1Name();
207             SelectorName selector2 = joinCondition.getSelector2Name();
208             String property1 = joinCondition.getProperty1Name();
209             String property2 = joinCondition.getProperty2Name();
210 
211             // Create the Ordering for the first selector/property pair ...
212             DynamicOperand operand1 = new PropertyValue(selector1, property1);
213             Ordering ordering1 = new Ordering(operand1, Order.ASCENDING);
214             // Create the Ordering for the second selector/property pair ...
215             DynamicOperand operand2 = new PropertyValue(selector2, property2);
216             Ordering ordering2 = new Ordering(operand2, Order.ASCENDING);
217 
218             if (leftSelectors.contains(selector1)) {
219                 leftSortBy.add(ordering1);
220                 rightSortBy.add(ordering2);
221             } else {
222                 leftSortBy.add(ordering2);
223                 rightSortBy.add(ordering1);
224             }
225         } else {
226             assert false;
227             throw new IllegalArgumentException();
228         }
229     }
230 
231     /**
232      * {@inheritDoc}
233      * 
234      * @see java.lang.Object#toString()
235      */
236     @Override
237     public String toString() {
238         return getClass().getSimpleName();
239     }
240 
241 }