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.ArrayList;
27 import java.util.Collection;
28 import java.util.Iterator;
29 import java.util.LinkedList;
30 import java.util.List;
31 import java.util.Set;
32 import net.jcip.annotations.Immutable;
33 import org.modeshape.graph.property.ValueComparators;
34 import org.modeshape.graph.query.QueryContext;
35 import org.modeshape.graph.query.model.And;
36 import org.modeshape.graph.query.model.Between;
37 import org.modeshape.graph.query.model.BindVariableName;
38 import org.modeshape.graph.query.model.Comparison;
39 import org.modeshape.graph.query.model.Constraint;
40 import org.modeshape.graph.query.model.DynamicOperand;
41 import org.modeshape.graph.query.model.Literal;
42 import org.modeshape.graph.query.model.Operator;
43 import org.modeshape.graph.query.model.SelectorName;
44 import org.modeshape.graph.query.model.StaticOperand;
45 import org.modeshape.graph.query.model.Visitor;
46 import org.modeshape.graph.query.plan.PlanNode;
47 import org.modeshape.graph.query.plan.PlanNode.Property;
48 import org.modeshape.graph.query.plan.PlanNode.Type;
49 import com.google.common.collect.ArrayListMultimap;
50 import com.google.common.collect.Multimap;
51
52 /**
53 * An {@link OptimizerRule optimizer rule} that rewrites two {@link And AND-ed} {@link Constraint}s that constraint a dynamic
54 * operand to a range of values as a single {@link Between} constraint. This rule also collapses and removes any constraints that
55 * are unnecessary because other constraints are more restrictive or because they cancel out other constraints.
56 */
57 @Immutable
58 public class RewriteAsRangeCriteria implements OptimizerRule {
59
60 protected static final Constraint CONFLICTING_CONSTRAINT = new Constraint() {
61 private static final long serialVersionUID = 1L;
62
63 public void accept( Visitor visitor ) {
64 throw new UnsupportedOperationException();
65 }
66 };
67
68 public static final RewriteAsRangeCriteria INSTANCE = new RewriteAsRangeCriteria();
69
70 /**
71 * {@inheritDoc}
72 *
73 * @see org.modeshape.graph.query.optimize.OptimizerRule#execute(org.modeshape.graph.query.QueryContext,
74 * org.modeshape.graph.query.plan.PlanNode, java.util.LinkedList)
75 */
76 public PlanNode execute( QueryContext context,
77 PlanNode plan,
78 LinkedList<OptimizerRule> ruleStack ) {
79 // Find all the access nodes ...
80 boolean rewritten = false;
81 boolean foundNoResults = false;
82 for (PlanNode access : plan.findAllAtOrBelow(Type.ACCESS)) {
83 // Look for select nodes below an ACCESS node that have a single Comparison constraint,
84 // and accumulate them keyed by the dynamic operand ...
85 Multimap<DynamicOperand, PlanNode> selectNodeByOperand = ArrayListMultimap.create();
86 for (PlanNode select : access.findAllAtOrBelow(Type.SELECT)) {
87 Constraint constraint = select.getProperty(Property.SELECT_CRITERIA, Constraint.class);
88 // Look for Comparison constraints that use a range operator
89 if (constraint instanceof Comparison) {
90 Comparison comparison = (Comparison)constraint;
91 if (comparison.operator().isRangeOperator()) {
92 selectNodeByOperand.put(comparison.operand1(), select);
93 }
94 }
95 }
96
97 if (!selectNodeByOperand.isEmpty()) {
98
99 // Go through the constraints we've found ...
100 for (DynamicOperand operand : selectNodeByOperand.keySet()) {
101 Collection<PlanNode> nodes = selectNodeByOperand.get(operand);
102 if (nodes.size() <= 1) continue;
103
104 // Extract the constraints from the nodes ...
105 List<Comparison> rangeConstraints = new ArrayList<Comparison>(nodes.size());
106 List<PlanNode> selectNodes = new ArrayList<PlanNode>(nodes.size());
107 Set<SelectorName> selectors = null;
108 for (PlanNode select : nodes) {
109 selectNodes.add(select);
110 Comparison constraint = select.getProperty(Property.SELECT_CRITERIA, Comparison.class);
111 rangeConstraints.add(constraint);
112 // Record the selector names (should all be the same) ...
113 if (selectors == null) selectors = select.getSelectors();
114 else assert selectors.equals(select.getSelectors());
115 }
116
117 // Attempt to merge the constraints ...
118 Constraint merged = rewrite(context, rangeConstraints);
119 if (merged == CONFLICTING_CONSTRAINT) {
120 // The ANDed constraints cancel each other out, so this whole access node will return no results ...
121 access.setProperty(Property.ACCESS_NO_RESULTS, Boolean.TRUE);
122 foundNoResults = true;
123 break; // don't do anything else under this access node
124 }
125 if (merged != null) {
126 // Add a SELECT node for the new merged constraint ...
127 PlanNode newSelect = new PlanNode(Type.SELECT);
128 newSelect.getSelectors().addAll(selectors);
129 newSelect.setProperty(Property.SELECT_CRITERIA, merged);
130
131 // And insert the SELECT node into the tree (just below the ACCESS, we'll rerun pushdown selects) ...
132 assert access.getChildCount() == 1;
133 access.getFirstChild().insertAsParent(newSelect);
134 rewritten = true;
135 }
136
137 // Remove any of the SELECT nodes that were not needed (this can happen if the constraints are not needed) ...
138 Iterator<PlanNode> nodeIter = selectNodes.iterator();
139 Iterator<Comparison> constraintIter = rangeConstraints.iterator();
140 while (nodeIter.hasNext()) {
141 assert constraintIter.hasNext();
142 PlanNode node = nodeIter.next();
143 Comparison comparison = constraintIter.next();
144 if (comparison == null) {
145 // This comparison was rewritten, so remove the PlanNode ...
146 node.extractFromParent();
147 nodeIter.remove();
148 }
149 }
150 assert !constraintIter.hasNext();
151 }
152 }
153 }
154
155 if (rewritten) {
156 // We mucked with the SELECT nodes, adding SELECT node for each rewritten constraint.
157 // Rerun the rule that pushes SELECT nodes ...
158 ruleStack.addFirst(PushSelectCriteria.INSTANCE);
159 }
160 if (foundNoResults) {
161 ruleStack.addFirst(RemoveEmptyAccessNodes.INSTANCE);
162 }
163
164 return plan;
165 }
166
167 /**
168 * {@inheritDoc}
169 *
170 * @see java.lang.Object#toString()
171 */
172 @Override
173 public String toString() {
174 return getClass().getSimpleName();
175 }
176
177 /**
178 * Rewrite the supplied comparisons, returning the new constraint and nulling in the supplied list those comparisons that were
179 * rewritten (and leaving those that were not rewritten)
180 *
181 * @param context the query context
182 * @param comparisons the list of comparisons that sould be rewritten if possible; never null
183 * @return the rewritten constraint, or null if no comparisons were rewritten
184 */
185 @SuppressWarnings( "fallthrough" )
186 protected Constraint rewrite( QueryContext context,
187 List<Comparison> comparisons ) {
188 // Look for the lower bound (greater-than) and upper bound (less-than) ...
189 Comparison lessThan = null;
190 Comparison greaterThan = null;
191 List<Comparison> notNeeded = new LinkedList<Comparison>();
192 boolean inclusive = false;
193 for (Comparison comparison : comparisons) {
194 switch (comparison.operator()) {
195 case GREATER_THAN_OR_EQUAL_TO:
196 inclusive = true;
197 case GREATER_THAN:
198 if (greaterThan != null) {
199 // Find the smallest value ...
200 Comparison newGreaterThan = getComparison(context, greaterThan, comparison, true);
201 notNeeded.add(newGreaterThan == greaterThan ? comparison : greaterThan);
202 greaterThan = newGreaterThan;
203 } else {
204 greaterThan = comparison;
205 }
206 break;
207 case LESS_THAN_OR_EQUAL_TO:
208 inclusive = true;
209 case LESS_THAN:
210 if (lessThan != null) {
211 // Find the largest value ...
212 Comparison newLessThan = getComparison(context, lessThan, comparison, false);
213 notNeeded.add(newLessThan == lessThan ? comparison : lessThan);
214 greaterThan = newLessThan;
215 } else {
216 lessThan = comparison;
217 }
218 break;
219 default:
220 assert false;
221 return null;
222 }
223 }
224 if (lessThan == null || greaterThan == null) return null;
225
226 // Create the new Comparison ...
227 Constraint result = null;
228
229 // Compute the difference between the lessThan value and greaterThan value ...
230 int diff = compareStaticOperands(context, greaterThan, lessThan);
231 if (diff == 0) {
232 // The static operands are equivalent ...
233 if (inclusive) {
234 // At least one of the sides was inclusive, meaning the constraints were something
235 // like 'x >= 2 AND x < 2', so we can replace these with an equality constraint ...
236 result = new Comparison(lessThan.operand1(), Operator.EQUAL_TO, lessThan.operand2());
237 notNeeded.add(lessThan);
238 notNeeded.add(greaterThan);
239 } else {
240 // Neither is inclusive, so really the constraints are not needed anymore.
241 // And, because the constraints conflict, the whole access will return no nodes.
242 // So return the placeholder ...
243 return CONFLICTING_CONSTRAINT;
244 }
245 } else if (diff < 0) {
246 // The range is valid as is ...
247 boolean lowerInclusive = greaterThan.operator() == Operator.GREATER_THAN_OR_EQUAL_TO;
248 boolean upperInclusive = lessThan.operator() == Operator.LESS_THAN_OR_EQUAL_TO;
249 result = new Between(lessThan.operand1(), greaterThan.operand2(), lessThan.operand2(), lowerInclusive, upperInclusive);
250 notNeeded.add(lessThan);
251 notNeeded.add(greaterThan);
252 } else {
253 // The range is actually something like 'x < 2 AND x > 4', which can never happen ...
254 return CONFLICTING_CONSTRAINT;
255 }
256
257 // Now null out those comparison objects that are not needed ...
258 nullReference(comparisons, notNeeded);
259 return result;
260 }
261
262 /**
263 * Find all occurrences of the comparison object in the supplied list and null the list's reference to it.
264 *
265 * @param comparisons the collection in which null references are to be placed
266 * @param comparisonToNull the comparison that is to be found and nulled in the collection
267 */
268 protected void nullReference( List<Comparison> comparisons,
269 Comparison comparisonToNull ) {
270 if (comparisonToNull != null) {
271 for (int i = 0; i != comparisons.size(); ++i) {
272 if (comparisons.get(i) == comparisonToNull) comparisons.set(i, null);
273 }
274 }
275 }
276
277 /**
278 * Find all references in the supplied list that match those supplied and set them to null.
279 *
280 * @param comparisons the collection in which null references are to be placed
281 * @param comparisonsToNull the comparisons that are to be found and nulled in the collection
282 */
283 protected void nullReference( List<Comparison> comparisons,
284 Iterable<Comparison> comparisonsToNull ) {
285 for (Comparison comparisonToNull : comparisonsToNull) {
286 nullReference(comparisons, comparisonToNull);
287 }
288 }
289
290 /**
291 * Compare the values used in the two comparisons
292 *
293 * @param context the query context; may not be null
294 * @param comparison1 the first comparison object; may not be null
295 * @param comparison2 the second comparison object; may not be null
296 * @return 0 if the values are the same, less than 0 if the first comparison's value is less than the second's, or greater
297 * than 0 if the first comparison's value is greater than the second's
298 */
299 protected int compareStaticOperands( QueryContext context,
300 Comparison comparison1,
301 Comparison comparison2 ) {
302 Object value1 = getValue(context, comparison1.operand2());
303 Object value2 = getValue(context, comparison2.operand2());
304 return ValueComparators.OBJECT_COMPARATOR.compare(value1, value2);
305 }
306
307 /**
308 * Get the comparison with the smallest (or largest) value.
309 *
310 * @param context the query context; may not be null
311 * @param comparison1 the first comparison object; may not be null
312 * @param comparison2 the second comparison object; may not be null
313 * @param smallest true if the comparison with the smallest value should be returned, or false otherwise
314 * @return the comparison with the smallest (or largest) value
315 */
316 protected Comparison getComparison( QueryContext context,
317 Comparison comparison1,
318 Comparison comparison2,
319 boolean smallest ) {
320 int diff = compareStaticOperands(context, comparison1, comparison2);
321 if (diff == 0) {
322 // They are the same ...
323 return comparison1;
324 }
325 if (!smallest) diff = -1 * diff;
326 return diff < 1 ? comparison1 : comparison2;
327 }
328
329 /**
330 * Get the value associated with the static operand of the comparison. If the operand is a {@link BindVariableName variable
331 * name}, the variable value is returned.
332 *
333 * @param context the query context; may not be null
334 * @param operand the static operand; may not be null
335 * @return the value of the static operand
336 */
337 protected Object getValue( QueryContext context,
338 StaticOperand operand ) {
339 if (operand instanceof Literal) {
340 Literal literal = (Literal)operand;
341 return literal.value();
342 }
343 BindVariableName variable = (BindVariableName)operand;
344 return context.getVariables().get(variable.variableName());
345 }
346 }