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.Collections;
27 import java.util.HashSet;
28 import java.util.LinkedList;
29 import java.util.Set;
30 import net.jcip.annotations.Immutable;
31 import org.modeshape.graph.query.QueryContext;
32 import org.modeshape.graph.query.model.Column;
33 import org.modeshape.graph.query.model.Constraint;
34 import org.modeshape.graph.query.model.EquiJoinCondition;
35 import org.modeshape.graph.query.model.JoinCondition;
36 import org.modeshape.graph.query.model.PropertyExistence;
37 import org.modeshape.graph.query.model.PropertyValue;
38 import org.modeshape.graph.query.model.ReferenceValue;
39 import org.modeshape.graph.query.model.SelectorName;
40 import org.modeshape.graph.query.model.Visitable;
41 import org.modeshape.graph.query.model.Visitors;
42 import org.modeshape.graph.query.model.Visitors.AbstractVisitor;
43 import org.modeshape.graph.query.plan.PlanNode;
44 import org.modeshape.graph.query.plan.PlanUtil;
45 import org.modeshape.graph.query.plan.PlanNode.Property;
46 import org.modeshape.graph.query.plan.PlanNode.Type;
47
48 /**
49 * An {@link OptimizerRule optimizer rule} that moves up higher in the plan any SELECT node that appears below a JOIN node and
50 * that applies to selectors that are on the other side of the join.
51 * <p>
52 * This step is often counterintuitive, since one of the best optimizations a query optimizer can do is to
53 * {@link PushSelectCriteria push down SELECT nodes} as far as they'll go. But consider the case of a SOURCE node that appears
54 * below a JOIN, where the SOURCE node is a view. The optimizer {@link ReplaceViews replaces the SOURCE node with the view
55 * definition}, and if the view definition includes a SELECT node, that SELECT node appears below the JOIN. Plus, that SELECT node
56 * is already pushed down as far as it can go (assuming the view isn't defined to use another view). However, the JOIN may use the
57 * same selector on the opposite side, and it may be possible that the same SELECT node may apply to the other side of the JOIN.
58 * In this case, we can push <i>up</i> the SELECT node higher than the JOIN, and then the push-down would cause the SELECT to be
59 * copied to both sides of the JOIN.
60 * </p>
61 * <p>
62 * Here is an example plan that involves a JOIN of two SOURCE nodes:
63 *
64 * <pre>
65 * ...
66 * |
67 * JOIN
68 * / \
69 * / SOURCE({@link Property#SOURCE_NAME SOURCE_NAME}="t1")
70 * /
71 * SOURCE({@link Property#SOURCE_NAME SOURCE_NAME}="v1")
72 * </pre>
73 *
74 * If the right-side SOURCE references the "t1" table, and the left-side SOURCE references a view "v1" defined as "
75 * <code>SELECT * FROM t1 WHERE t1.id < 3</code>", then the {@link ReplaceViews} rule would change this plan to be:
76 *
77 * <pre>
78 * ...
79 * |
80 * JOIN
81 * / \
82 * / SOURCE({@link Property#SOURCE_NAME SOURCE_NAME}="t1")
83 * /
84 * PROJECT
85 * |
86 * SELECT applies the "t1.id < 3" criteria
87 * |
88 * SOURCE({@link Property#SOURCE_NAME SOURCE_NAME}="t1")
89 * </pre>
90 *
91 * Again, the SELECT cannot be pushed down any further. But the whole query can be made more efficient - because the SELECT on the
92 * left-side of the JOIN will include only those tuples from 't1' that satisfy the SELECT, the JOIN will only include those tuples
93 * that also satisfy this criteria, even though more tuples are returned from the right-side SOURCE.
94 * </p>
95 * <p>
96 * In this case, the left-hand SELECT can actually be copied to the right-hand side of the JOIN, resulting in:
97 *
98 * <pre>
99 * ...
100 * |
101 * JOIN
102 * / \
103 * / SELECT applies the "t1.id < 3" criteria
104 * / |
105 * PROJECT SOURCE({@link Property#SOURCE_NAME SOURCE_NAME}="t1")
106 * |
107 * SELECT applies the "t1.id < 3" criteria
108 * |
109 * SOURCE({@link Property#SOURCE_NAME SOURCE_NAME}="t1")
110 * </pre>
111 *
112 * </p>
113 */
114 @Immutable
115 public class RaiseSelectCriteria implements OptimizerRule {
116
117 public static final RaiseSelectCriteria INSTANCE = new RaiseSelectCriteria();
118
119 /**
120 * {@inheritDoc}
121 *
122 * @see org.modeshape.graph.query.optimize.OptimizerRule#execute(org.modeshape.graph.query.QueryContext,
123 * org.modeshape.graph.query.plan.PlanNode, java.util.LinkedList)
124 */
125 public PlanNode execute( QueryContext context,
126 PlanNode plan,
127 LinkedList<OptimizerRule> ruleStack ) {
128 Set<PlanNode> copiedSelectNodes = new HashSet<PlanNode>();
129
130 for (PlanNode join : plan.findAllAtOrBelow(Type.JOIN)) {
131 // Get the join condition ...
132 JoinCondition joinCondition = join.getProperty(Property.JOIN_CONDITION, JoinCondition.class);
133 if (joinCondition instanceof EquiJoinCondition) {
134 EquiJoinCondition equiJoinCondition = (EquiJoinCondition)joinCondition;
135 SelectorName selector1 = equiJoinCondition.selector1Name();
136 SelectorName selector2 = equiJoinCondition.selector2Name();
137 String property1 = equiJoinCondition.property1Name();
138 String property2 = equiJoinCondition.property2Name();
139
140 // Walk up the tree looking for SELECT nodes that apply to one of the sides ...
141 PlanNode node = join.getParent();
142 while (node != null) {
143 if (!copiedSelectNodes.contains(node)) {
144 PlanNode copy = copySelectNode(context, node, selector1, property1, selector2, property2);
145 if (copy != null) {
146 node.insertAsParent(copy);
147 copiedSelectNodes.add(node);
148 copiedSelectNodes.add(copy);
149 } else {
150 copy = copySelectNode(context, node, selector2, property2, selector1, property1);
151 if (copy != null) {
152 node.insertAsParent(copy);
153 copiedSelectNodes.add(node);
154 copiedSelectNodes.add(copy);
155 }
156 }
157 }
158 node = node.getParent();
159 }
160 }
161 }
162 return plan;
163 }
164
165 protected PlanNode copySelectNode( QueryContext context,
166 PlanNode selectNode,
167 SelectorName selectorName,
168 String propertyName,
169 SelectorName copySelectorName,
170 String copyPropertyName ) {
171 if (selectNode.isNot(Type.SELECT)) return null;
172 if (selectNode.getSelectors().size() != 1 || !selectNode.getSelectors().contains(selectorName)) return null;
173
174 Constraint constraint = selectNode.getProperty(Property.SELECT_CRITERIA, Constraint.class);
175 Set<Column> columns = getColumnsReferencedBy(constraint);
176 if (columns.size() != 1) return null;
177 Column column = columns.iterator().next();
178 if (!column.selectorName().equals(selectorName)) return null;
179 if (!column.propertyName().equals(propertyName)) return null;
180
181 // We know that this constraint ONLY applies to the referenced selector and property,
182 // so we will duplicate this constraint ...
183
184 // Create the new node ...
185 PlanNode copy = new PlanNode(Type.SELECT, copySelectorName);
186
187 // Copy the constraint, but change the references to the copy selector and property ...
188 PlanUtil.ColumnMapping mappings = new PlanUtil.ColumnMapping(selectorName);
189 mappings.map(propertyName, new Column(copySelectorName, copyPropertyName, copyPropertyName));
190 Constraint newCriteria = PlanUtil.replaceReferences(context, constraint, mappings, copy);
191 copy.setProperty(Property.SELECT_CRITERIA, newCriteria);
192
193 return copy;
194 }
195
196 /**
197 * {@inheritDoc}
198 *
199 * @see java.lang.Object#toString()
200 */
201 @Override
202 public String toString() {
203 return getClass().getSimpleName();
204 }
205
206 /**
207 * Get the set of Column objects that represent those columns referenced by the visitable object.
208 *
209 * @param visitable the object to be visited
210 * @return the set of Column objects, with column names that always are the string-form of the {@link Column#propertyName()
211 * property name}; never null
212 */
213 public static Set<Column> getColumnsReferencedBy( Visitable visitable ) {
214 if (visitable == null) return Collections.emptySet();
215 final Set<Column> symbols = new HashSet<Column>();
216 // Walk the entire structure, so only supply a StrategyVisitor (that does no navigation) ...
217 Visitors.visitAll(visitable, new AbstractVisitor() {
218 protected void addColumnFor( SelectorName selectorName,
219 String property ) {
220 symbols.add(new Column(selectorName, property, property));
221 }
222
223 @Override
224 public void visit( Column column ) {
225 symbols.add(column);
226 }
227
228 @Override
229 public void visit( EquiJoinCondition joinCondition ) {
230 addColumnFor(joinCondition.selector1Name(), joinCondition.property1Name());
231 addColumnFor(joinCondition.selector2Name(), joinCondition.property2Name());
232 }
233
234 @Override
235 public void visit( PropertyExistence prop ) {
236 addColumnFor(prop.selectorName(), prop.propertyName());
237 }
238
239 @Override
240 public void visit( PropertyValue prop ) {
241 addColumnFor(prop.selectorName(), prop.propertyName());
242 }
243
244 @Override
245 public void visit( ReferenceValue ref ) {
246 String propertyName = ref.propertyName();
247 if (propertyName != null) {
248 addColumnFor(ref.selectorName(), propertyName);
249 }
250 }
251 });
252 return symbols;
253 }
254
255 }