Author: rhauch Date: 2009-11-17 13:47:00 -0500 (Tue, 17 Nov 2009) New Revision: 1324 Added: trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RemoveEmptyAccessNodes.java trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RewriteAsRangeCriteria.java trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/RewriteAsRangeCriteriaTest.java Modified: trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/model/Operator.java trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RuleBasedOptimizer.java trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/plan/PlanNode.java trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/process/QueryProcessor.java trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/PushSelectCriteriaTest.java trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/ReplaceViewsTest.java Log: DNA-552 The abstract query model now has a new Constraint subclass called Between that has a DynamicOperand, a StaticOperand lower boundary, a StaticOperand upper boundary, and a flag for each boundary that specifies whether the boundary is included or excluded in the range. This very capably handles all kinds of continuous ranges. The dna-searc project was enhanced to support this new Constraint type for numeric values (long, double, decimal, and date). The SQL language parser now handles the '<dynamicOperand> BETWEEN <staticOperandLowerBound> [EXCLUSIVE] AND <staticOperandUpperBound> [EXCLUSIVE]'. Additionally, a query optimizer rule was created to look for pairs of Comparison constraints that can be merged or rewritten: - two range constraints are replaced with a single Between constraint (e.g., 'table.column' >=4 and table.column <=10' replaced with 'table.column BETWEEN 4 AND 10', with the exclusive flags set properly) - two range constraints that specify a range of a single value are replaced with a single equality constraint (e.g., 'table.column >=4 AND table.column <= 4' replaced with 'table.column = 4') - unnecessary Comparison constraints are removed (e.g., given 'table.column < 4 AND table.column < 10' the latter constraint is removed) - conflicting constraints that will never be satisfied (e.g., 'table.column < 4 AND table.column > 10), marking the ACCESS node as having no results (this is handled in the query processor) The QueryProcessor was also changed to look for an ACCESS node with the (new) ACCESS_NO_RESULTS property, and to create a NoResultsComponent rather than a real access component. This will work in that an access query will never be made when we know the range constraints are invalid, but it does not look for other always-false constraints nor does it optimize the plan. (A RemoveEmptyAccessNodes optimizer plan was created, though it basically is a no-op at the moment.) Modified: trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/model/Operator.java =================================================================== --- trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/model/Operator.java 2009-11-17 18:46:21 UTC (rev 1323) +++ trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/model/Operator.java 2009-11-17 18:47:00 UTC (rev 1324) @@ -87,6 +87,27 @@ } /** + * Determine whether this operator is one that is used to define a range of values: {@link #LESS_THAN <}, + * {@link #GREATER_THAN >}, {@link #LESS_THAN_OR_EQUAL_TO <=}, or {@link #GREATER_THAN_OR_EQUAL_TO >=}. + * + * @return true if this operator is a range operator, or false otherwise + */ + public boolean isRangeOperator() { + switch (this) { + case GREATER_THAN: + case GREATER_THAN_OR_EQUAL_TO: + case LESS_THAN: + case LESS_THAN_OR_EQUAL_TO: + return true; + case EQUAL_TO: + case LIKE: + case NOT_EQUAL_TO: + default: + return false; + } + } + + /** * {@inheritDoc} * * @see java.lang.Enum#toString() Added: trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RemoveEmptyAccessNodes.java =================================================================== --- trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RemoveEmptyAccessNodes.java (rev 0) +++ trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RemoveEmptyAccessNodes.java 2009-11-17 18:47:00 UTC (rev 1324) @@ -0,0 +1,65 @@ +/* + * JBoss DNA (http://www.jboss.org/dna) + * See the COPYRIGHT.txt file distributed with this work for information + * regarding copyright ownership. Some portions may be licensed + * to Red Hat, Inc. under one or more contributor license agreements. + * See the AUTHORS.txt file in the distribution for a full listing of + * individual contributors. + * + * JBoss DNA is free software. Unless otherwise indicated, all code in JBoss DNA + * is licensed to you under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation; either version 2.1 of + * the License, or (at your option) any later version. + * + * JBoss DNA is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this software; if not, write to the Free + * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA + * 02110-1301 USA, or see the FSF site: http://www.fsf.org. + */ +package org.jboss.dna.graph.query.optimize; + +import java.util.LinkedList; +import net.jcip.annotations.Immutable; +import org.jboss.dna.graph.query.QueryContext; +import org.jboss.dna.graph.query.plan.PlanNode; +import org.jboss.dna.graph.query.plan.PlanNode.Property; +import org.jboss.dna.graph.query.plan.PlanNode.Type; + +/** + * An {@link OptimizerRule optimizer rule} that removes any ACCESS nodes that are known to never return any tuples because of + * conflicting constraints. + */ +@Immutable +public class RemoveEmptyAccessNodes implements OptimizerRule { + + public static final RemoveEmptyAccessNodes INSTANCE = new RemoveEmptyAccessNodes(); + + /** + * {@inheritDoc} + * + * @see org.jboss.dna.graph.query.optimize.OptimizerRule#execute(org.jboss.dna.graph.query.QueryContext, + * org.jboss.dna.graph.query.plan.PlanNode, java.util.LinkedList) + */ + public PlanNode execute( QueryContext context, + PlanNode plan, + LinkedList<OptimizerRule> ruleStack ) { + // Find all access nodes ... + for (PlanNode access : plan.findAllAtOrBelow(Type.ACCESS)) { + if (access.getProperty(Property.ACCESS_NO_RESULTS, Boolean.class)) { + // This node has conflicting constraints and will never return any results ... + + // TODO: implement this rule. + + // At least the QueryProcessor looks for this property and always creates a NoResultsComponent, + // saving some work. But implementing this rule will make queries more efficient. + } + } + + return plan; + } +} Property changes on: trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RemoveEmptyAccessNodes.java ___________________________________________________________________ Name: svn:keywords + Id Revision Name: svn:eol-style + LF Added: trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RewriteAsRangeCriteria.java =================================================================== --- trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RewriteAsRangeCriteria.java (rev 0) +++ trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RewriteAsRangeCriteria.java 2009-11-17 18:47:00 UTC (rev 1324) @@ -0,0 +1,335 @@ +/* + * JBoss DNA (http://www.jboss.org/dna) + * See the COPYRIGHT.txt file distributed with this work for information + * regarding copyright ownership. Some portions may be licensed + * to Red Hat, Inc. under one or more contributor license agreements. + * See the AUTHORS.txt file in the distribution for a full listing of + * individual contributors. + * + * JBoss DNA is free software. Unless otherwise indicated, all code in JBoss DNA + * is licensed to you under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation; either version 2.1 of + * the License, or (at your option) any later version. + * + * JBoss DNA is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this software; if not, write to the Free + * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA + * 02110-1301 USA, or see the FSF site: http://www.fsf.org. + */ +package org.jboss.dna.graph.query.optimize; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; +import java.util.Set; +import net.jcip.annotations.Immutable; +import org.jboss.dna.graph.property.ValueComparators; +import org.jboss.dna.graph.query.QueryContext; +import org.jboss.dna.graph.query.model.And; +import org.jboss.dna.graph.query.model.Between; +import org.jboss.dna.graph.query.model.BindVariableName; +import org.jboss.dna.graph.query.model.Comparison; +import org.jboss.dna.graph.query.model.Constraint; +import org.jboss.dna.graph.query.model.DynamicOperand; +import org.jboss.dna.graph.query.model.Literal; +import org.jboss.dna.graph.query.model.Operator; +import org.jboss.dna.graph.query.model.SelectorName; +import org.jboss.dna.graph.query.model.StaticOperand; +import org.jboss.dna.graph.query.model.Visitor; +import org.jboss.dna.graph.query.plan.PlanNode; +import org.jboss.dna.graph.query.plan.PlanNode.Property; +import org.jboss.dna.graph.query.plan.PlanNode.Type; +import com.google.common.collect.Multimap; +import com.google.common.collect.Multimaps; + +/** + * An {@link OptimizerRule optimizer rule} that rewrites two {@link And AND-ed} {@link Constraint}s that constraint a dynamic + * operand to a range of values as a single {@link Between} constraint. This rule also collapses and removes any constraints that + * are unnecessary because other constraints are more restrictive or because they cancel out other constraints. + */ +@Immutable +public class RewriteAsRangeCriteria implements OptimizerRule { + + protected static final Constraint CONFLICTING_CONSTRAINT = new Constraint() { + public void accept( Visitor visitor ) { + throw new UnsupportedOperationException(); + } + }; + + public static final RewriteAsRangeCriteria INSTANCE = new RewriteAsRangeCriteria(); + + /** + * {@inheritDoc} + * + * @see org.jboss.dna.graph.query.optimize.OptimizerRule#execute(org.jboss.dna.graph.query.QueryContext, + * org.jboss.dna.graph.query.plan.PlanNode, java.util.LinkedList) + */ + public PlanNode execute( QueryContext context, + PlanNode plan, + LinkedList<OptimizerRule> ruleStack ) { + // Find all the access nodes ... + boolean rewritten = false; + boolean foundNoResults = false; + for (PlanNode access : plan.findAllAtOrBelow(Type.ACCESS)) { + // Look for select nodes below an ACCESS node that have a single Comparison constraint, + // and accumulate them keyed by the dynamic operand ... + Multimap<DynamicOperand, PlanNode> selectNodeByOperand = Multimaps.newArrayListMultimap(); + for (PlanNode select : access.findAllAtOrBelow(Type.SELECT)) { + Constraint constraint = select.getProperty(Property.SELECT_CRITERIA, Constraint.class); + // Look for Comparison constraints that use a range operator + if (constraint instanceof Comparison) { + Comparison comparison = (Comparison)constraint; + if (comparison.getOperator().isRangeOperator()) { + selectNodeByOperand.put(comparison.getOperand1(), select); + } + } + } + + if (!selectNodeByOperand.isEmpty()) { + + // Go through the constraints we've found ... + for (DynamicOperand operand : selectNodeByOperand.keySet()) { + Collection<PlanNode> nodes = selectNodeByOperand.get(operand); + if (nodes.size() <= 1) continue; + + // Extract the constraints from the nodes ... + List<Comparison> rangeConstraints = new ArrayList<Comparison>(nodes.size()); + List<PlanNode> selectNodes = new ArrayList<PlanNode>(nodes.size()); + Set<SelectorName> selectors = null; + for (PlanNode select : nodes) { + selectNodes.add(select); + Comparison constraint = select.getProperty(Property.SELECT_CRITERIA, Comparison.class); + rangeConstraints.add(constraint); + // Record the selector names (should all be the same) ... + if (selectors == null) selectors = select.getSelectors(); + else assert selectors.equals(select.getSelectors()); + } + + // Attempt to merge the constraints ... + Constraint merged = rewrite(context, rangeConstraints); + if (merged == CONFLICTING_CONSTRAINT) { + // The ANDed constraints cancel each other out, so this whole access node will return no results ... + access.setProperty(Property.ACCESS_NO_RESULTS, Boolean.TRUE); + foundNoResults = true; + break; // don't do anything else under this access node + } + if (merged != null) { + // Add a SELECT node for the new merged constraint ... + PlanNode newSelect = new PlanNode(Type.SELECT); + newSelect.getSelectors().addAll(selectors); + newSelect.setProperty(Property.SELECT_CRITERIA, merged); + + // And insert the SELECT node into the tree (just below the ACCESS, we'll rerun pushdown selects) ... + assert access.getChildCount() == 1; + access.getFirstChild().insertAsParent(newSelect); + rewritten = true; + } + + // Remove any of the SELECT nodes that were not needed (this can happen if the constraints are not needed) ... + Iterator<PlanNode> nodeIter = selectNodes.iterator(); + Iterator<Comparison> constraintIter = rangeConstraints.iterator(); + while (nodeIter.hasNext()) { + assert constraintIter.hasNext(); + PlanNode node = nodeIter.next(); + Comparison comparison = constraintIter.next(); + if (comparison == null) { + // This comparison was rewritten, so remove the PlanNode ... + node.extractFromParent(); + nodeIter.remove(); + } + } + assert !constraintIter.hasNext(); + } + } + } + + if (rewritten) { + // We mucked with the SELECT nodes, adding SELECT node for each rewritten constraint. + // Rerun the rule that pushes SELECT nodes ... + ruleStack.addFirst(PushSelectCriteria.INSTANCE); + } + if (foundNoResults) { + ruleStack.addFirst(RemoveEmptyAccessNodes.INSTANCE); + } + + return plan; + } + + /** + * Rewrite the supplied comparisons, returning the new constraint and nulling in the supplied list those comparisons that were + * rewritten (and leaving those that were not rewritten) + * + * @param context the query context + * @param comparisons the list of comparisons that sould be rewritten if possible; never null + * @return the rewritten constraint, or null if no comparisons were rewritten + */ + @SuppressWarnings( "fallthrough" ) + protected Constraint rewrite( QueryContext context, + List<Comparison> comparisons ) { + // Look for the lower bound (greater-than) and upper bound (less-than) ... + Comparison lessThan = null; + Comparison greaterThan = null; + List<Comparison> notNeeded = new LinkedList<Comparison>(); + boolean inclusive = false; + for (Comparison comparison : comparisons) { + switch (comparison.getOperator()) { + case GREATER_THAN_OR_EQUAL_TO: + inclusive = true; + case GREATER_THAN: + if (greaterThan != null) { + // Find the smallest value ... + Comparison newGreaterThan = getComparison(context, greaterThan, comparison, true); + notNeeded.add(newGreaterThan == greaterThan ? comparison : greaterThan); + greaterThan = newGreaterThan; + } else { + greaterThan = comparison; + } + break; + case LESS_THAN_OR_EQUAL_TO: + inclusive = true; + case LESS_THAN: + if (lessThan != null) { + // Find the largest value ... + Comparison newLessThan = getComparison(context, lessThan, comparison, false); + notNeeded.add(newLessThan == lessThan ? comparison : lessThan); + greaterThan = newLessThan; + } else { + lessThan = comparison; + } + break; + default: + assert false; + return null; + } + } + if (lessThan == null || greaterThan == null) return null; + + // Create the new Comparison ... + Constraint result = null; + + // Compute the difference between the lessThan value and greaterThan value ... + int diff = compareStaticOperands(context, greaterThan, lessThan); + if (diff == 0) { + // The static operands are equivalent ... + if (inclusive) { + // At least one of the sides was inclusive, meaning the constraints were something + // like 'x >= 2 AND x < 2', so we can replace these with an equality constraint ... + result = new Comparison(lessThan.getOperand1(), Operator.EQUAL_TO, lessThan.getOperand2()); + notNeeded.add(lessThan); + notNeeded.add(greaterThan); + } else { + // Neither is inclusive, so really the constraints are not needed anymore. + // And, because the constraints conflict, the whole access will return no nodes. + // So return the placeholder ... + return CONFLICTING_CONSTRAINT; + } + } else if (diff < 0) { + // The range is valid as is ... + boolean lowerInclusive = greaterThan.getOperator() == Operator.GREATER_THAN_OR_EQUAL_TO; + boolean upperInclusive = lessThan.getOperator() == Operator.LESS_THAN_OR_EQUAL_TO; + result = new Between(lessThan.getOperand1(), greaterThan.getOperand2(), lessThan.getOperand2(), lowerInclusive, + upperInclusive); + notNeeded.add(lessThan); + notNeeded.add(greaterThan); + } else { + // The range is actually something like 'x < 2 AND x > 4', which can never happen ... + return CONFLICTING_CONSTRAINT; + } + + // Now null out those comparison objects that are not needed ... + nullReference(comparisons, notNeeded); + return result; + } + + /** + * Find all occurrences of the comparison object in the supplied list and null the list's reference to it. + * + * @param comparisons the collection in which null references are to be placed + * @param comparisonToNull the comparison that is to be found and nulled in the collection + */ + protected void nullReference( List<Comparison> comparisons, + Comparison comparisonToNull ) { + if (comparisonToNull != null) { + for (int i = 0; i != comparisons.size(); ++i) { + if (comparisons.get(i) == comparisonToNull) comparisons.set(i, null); + } + } + } + + /** + * Find all references in the supplied list that match those supplied and set them to null. + * + * @param comparisons the collection in which null references are to be placed + * @param comparisonsToNull the comparisons that are to be found and nulled in the collection + */ + protected void nullReference( List<Comparison> comparisons, + Iterable<Comparison> comparisonsToNull ) { + for (Comparison comparisonToNull : comparisonsToNull) { + nullReference(comparisons, comparisonToNull); + } + } + + /** + * Compare the values used in the two comparisons + * + * @param context the query context; may not be null + * @param comparison1 the first comparison object; may not be null + * @param comparison2 the second comparison object; may not be null + * @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 + * than 0 if the first comparison's value is greater than the second's + */ + protected int compareStaticOperands( QueryContext context, + Comparison comparison1, + Comparison comparison2 ) { + Object value1 = getValue(context, comparison1.getOperand2()); + Object value2 = getValue(context, comparison2.getOperand2()); + return ValueComparators.OBJECT_COMPARATOR.compare(value1, value2); + } + + /** + * Get the comparison with the smallest (or largest) value. + * + * @param context the query context; may not be null + * @param comparison1 the first comparison object; may not be null + * @param comparison2 the second comparison object; may not be null + * @param smallest true if the comparison with the smallest value should be returned, or false otherwise + * @return the comparison with the smallest (or largest) value + */ + protected Comparison getComparison( QueryContext context, + Comparison comparison1, + Comparison comparison2, + boolean smallest ) { + int diff = compareStaticOperands(context, comparison1, comparison2); + if (diff == 0) { + // They are the same ... + return comparison1; + } + if (!smallest) diff = -1 * diff; + return diff < 1 ? comparison1 : comparison2; + } + + /** + * Get the value associated with the static operand of the comparison. If the operand is a {@link BindVariableName variable + * name}, the variable value is returned. + * + * @param context the query context; may not be null + * @param operand the static operand; may not be null + * @return the value of the static operand + */ + protected Object getValue( QueryContext context, + StaticOperand operand ) { + if (operand instanceof Literal) { + Literal literal = (Literal)operand; + return literal.getValue(); + } + BindVariableName variable = (BindVariableName)operand; + return context.getVariables().get(variable.getVariableName()); + } +} Property changes on: trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RewriteAsRangeCriteria.java ___________________________________________________________________ Name: svn:keywords + Id Revision Name: svn:eol-style + LF Modified: trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RuleBasedOptimizer.java =================================================================== --- trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RuleBasedOptimizer.java 2009-11-17 18:46:21 UTC (rev 1323) +++ trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/optimize/RuleBasedOptimizer.java 2009-11-17 18:47:00 UTC (rev 1324) @@ -69,6 +69,7 @@ */ protected void populateRuleStack( LinkedList<OptimizerRule> ruleStack, PlanHints hints ) { + ruleStack.addFirst(RewriteAsRangeCriteria.INSTANCE); if (hints.hasJoin) { ruleStack.addFirst(ChooseJoinAlgorithm.USE_ONLY_NESTED_JOIN_ALGORITHM); ruleStack.addFirst(RewriteIdentityJoins.INSTANCE); Modified: trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/plan/PlanNode.java =================================================================== --- trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/plan/PlanNode.java 2009-11-17 18:46:21 UTC (rev 1323) +++ trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/plan/PlanNode.java 2009-11-17 18:47:00 UTC (rev 1324) @@ -39,7 +39,6 @@ import org.jboss.dna.common.util.ObjectUtil; import org.jboss.dna.graph.ExecutionContext; import org.jboss.dna.graph.query.model.Column; -import org.jboss.dna.graph.query.model.Command; import org.jboss.dna.graph.query.model.Constraint; import org.jboss.dna.graph.query.model.JoinCondition; import org.jboss.dna.graph.query.model.JoinType; @@ -189,9 +188,11 @@ /** For LIMIT nodes, the offset value. Value is an {@link Integer} object. */ LIMIT_OFFSET, - /** For ACCESS nodes, the {@link Command} that is to be executed by the source */ - // ACCESS_COMMAND, - BOGUS; // remove this + /** + * For ACESS nodes, this signifies that the node will never return results. Value is a {@link Boolean} object, though the + * mere presence of this property signifies that it is no longer needed. + */ + ACCESS_NO_RESULTS } private Type type; Modified: trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/process/QueryProcessor.java =================================================================== --- trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/process/QueryProcessor.java 2009-11-17 18:46:21 UTC (rev 1323) +++ trunk/dna-graph/src/main/java/org/jboss/dna/graph/query/process/QueryProcessor.java 2009-11-17 18:47:00 UTC (rev 1324) @@ -161,11 +161,16 @@ ProcessingComponent component = null; switch (node.getType()) { case ACCESS: - // Create the component to handle the ACCESS node ... - assert node.getChildCount() == 1; - component = createAccessComponent(originalQuery, context, node, columns, analyzer); - // // Don't do anything special with an access node at the moment ... - // component = createComponent(context, node.getFirstChild(), columns, analyzer); + // If the ACCESS node will not have results ... + if (node.getProperty(Property.ACCESS_NO_RESULTS, Boolean.class)) { + component = new NoResultsComponent(context, columns); + } else { + // Create the component to handle the ACCESS node ... + assert node.getChildCount() == 1; + component = createAccessComponent(originalQuery, context, node, columns, analyzer); + // // Don't do anything special with an access node at the moment ... + // component = createComponent(context, node.getFirstChild(), columns, analyzer); + } break; case DUP_REMOVE: // Create the component under the DUP_REMOVE ... Modified: trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/PushSelectCriteriaTest.java =================================================================== --- trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/PushSelectCriteriaTest.java 2009-11-17 18:46:21 UTC (rev 1323) +++ trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/PushSelectCriteriaTest.java 2009-11-17 18:47:00 UTC (rev 1324) @@ -206,7 +206,7 @@ // Execute the rule ... PlanNode result = rule.execute(context, project, new LinkedList<OptimizerRule>()); - System.out.println(result); + // System.out.println(result); assertThat(result, is(sameInstance(project))); assertChildren(project, select3); Modified: trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/ReplaceViewsTest.java =================================================================== --- trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/ReplaceViewsTest.java 2009-11-17 18:46:21 UTC (rev 1323) +++ trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/ReplaceViewsTest.java 2009-11-17 18:47:00 UTC (rev 1324) @@ -131,8 +131,8 @@ // Execute the rule ... PlanNode result = rule.execute(context, project, new LinkedList<OptimizerRule>()); - System.out.println(project); - System.out.println(result); + // System.out.println(project); + // System.out.println(result); assertThat(result.isSameAs(project), is(true)); assertChildren(project, select1); assertChildren(select1, select2); Added: trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/RewriteAsRangeCriteriaTest.java =================================================================== --- trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/RewriteAsRangeCriteriaTest.java (rev 0) +++ trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/RewriteAsRangeCriteriaTest.java 2009-11-17 18:47:00 UTC (rev 1324) @@ -0,0 +1,417 @@ +/* + * JBoss DNA (http://www.jboss.org/dna) + * See the COPYRIGHT.txt file distributed with this work for information + * regarding copyright ownership. Some portions may be licensed + * to Red Hat, Inc. under one or more contributor license agreements. + * See the AUTHORS.txt file in the distribution for a full listing of + * individual contributors. + * + * JBoss DNA is free software. Unless otherwise indicated, all code in JBoss DNA + * is licensed to you under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation; either version 2.1 of + * the License, or (at your option) any later version. + * + * JBoss DNA is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this software; if not, write to the Free + * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA + * 02110-1301 USA, or see the FSF site: http://www.fsf.org. + */ +package org.jboss.dna.graph.query.optimize; + +import static org.hamcrest.core.Is.is; +import static org.hamcrest.core.IsNull.nullValue; +import static org.hamcrest.core.IsSame.sameInstance; +import static org.junit.Assert.assertThat; +import static org.mockito.Mockito.mock; +import java.util.LinkedList; +import org.jboss.dna.graph.ExecutionContext; +import org.jboss.dna.graph.property.Name; +import org.jboss.dna.graph.query.AbstractQueryTest; +import org.jboss.dna.graph.query.QueryContext; +import org.jboss.dna.graph.query.model.Between; +import org.jboss.dna.graph.query.model.Comparison; +import org.jboss.dna.graph.query.model.Literal; +import org.jboss.dna.graph.query.model.Operator; +import org.jboss.dna.graph.query.model.PropertyValue; +import org.jboss.dna.graph.query.plan.PlanNode; +import org.jboss.dna.graph.query.plan.PlanNode.Property; +import org.jboss.dna.graph.query.plan.PlanNode.Type; +import org.jboss.dna.graph.query.validate.Schemata; +import org.junit.Before; +import org.junit.Test; + +/** + * + */ +public class RewriteAsRangeCriteriaTest extends AbstractQueryTest { + + private RewriteAsRangeCriteria rule; + private LinkedList<OptimizerRule> rules; + private QueryContext context; + private boolean print = true; + + @Before + public void beforeEach() { + rule = RewriteAsRangeCriteria.INSTANCE; + rules = new LinkedList<OptimizerRule>(); + rules.add(rule); + context = new QueryContext(new ExecutionContext(), mock(Schemata.class)); + } + + protected void print( PlanNode node ) { + if (print) System.out.println(node); + } + + /** + * Before: + * + * <pre> + * Access [t1] + * Project [t1] + * Select [t1] &lt;SELECT_CRITERIA=t1.c2 = 100&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &lt; 3&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &gt; 1&gt; + * Source [t1] &lt;SOURCE_NAME=t1&gt; + * </pre> + * + * And after: + * + * <pre> + * Access [t1] + * Project [t1] + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 BETWEEN 1 EXCLUSIVE AND 3 EXCLUSIVE&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c2 = 100&gt; + * Source [t1] &lt;SOURCE_NAME=t1&gt; + * </pre> + */ + @Test + public void shouldReplaceComparisonsSpecifyingExclusiveRangeWithBetweenConstraint() { + // Each of the PROJECT, SELECT, and SELECT nodes must have the names of the selectors that they apply to ... + PlanNode access = new PlanNode(Type.ACCESS, selector("t1")); + PlanNode project = new PlanNode(Type.PROJECT, access, selector("t1")); + PlanNode select1 = new PlanNode(Type.SELECT, project, selector("t1")); + PlanNode select2 = new PlanNode(Type.SELECT, select1, selector("t1")); + PlanNode select3 = new PlanNode(Type.SELECT, select2, selector("t1")); + PlanNode source = new PlanNode(Type.SOURCE, select3, selector("t1")); + source.setProperty(Property.SOURCE_NAME, selector("t1")); + select1.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c2")), + Operator.EQUAL_TO, new Literal(100L))); + select2.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c1")), + Operator.LESS_THAN, new Literal(3L))); + select3.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c1")), + Operator.GREATER_THAN, new Literal(1L))); + + // Execute the rule ... + print(access); + PlanNode result = executeRules(access); + print(result); + + // Compare results ... + assertThat(result, is(sameInstance(access))); + assertChildren(access, project); + PlanNode newSelect = project.getFirstChild(); + assertThat(newSelect.getType(), is(Type.SELECT)); + assertThat(newSelect.getSelectors(), is(access.getSelectors())); + assertThat(newSelect.getParent(), is(sameInstance(project))); + Between between = newSelect.getProperty(Property.SELECT_CRITERIA, Between.class); + assertThat(between.getOperand(), is(select2.getProperty(Property.SELECT_CRITERIA, Comparison.class).getOperand1())); + assertThat(between.getLowerBound(), is(select3.getProperty(Property.SELECT_CRITERIA, Comparison.class).getOperand2())); + assertThat(between.getUpperBound(), is(select2.getProperty(Property.SELECT_CRITERIA, Comparison.class).getOperand2())); + assertThat(between.isLowerBoundIncluded(), is(false)); + assertThat(between.isUpperBoundIncluded(), is(false)); + assertChildren(newSelect, select1); + assertChildren(select1, source); + } + + /** + * Before: + * + * <pre> + * Access [t1] + * Project [t1] + * Select [t1] &lt;SELECT_CRITERIA=t1.c2 = 100&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &lt;= 3&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &gt;= 1&gt; + * Source [t1] &lt;SOURCE_NAME=t1&gt; + * </pre> + * + * And after: + * + * <pre> + * Access [t1] + * Project [t1] + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 BETWEEN 1 AND 3&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c2 = 100&gt; + * Source [t1] &lt;SOURCE_NAME=t1&gt; + * </pre> + */ + @Test + public void shouldReplaceComparisonsSpecifyingInclusiveRangeWithBetweenConstraint() { + // Each of the PROJECT, SELECT, and SELECT nodes must have the names of the selectors that they apply to ... + PlanNode access = new PlanNode(Type.ACCESS, selector("t1")); + PlanNode project = new PlanNode(Type.PROJECT, access, selector("t1")); + PlanNode select1 = new PlanNode(Type.SELECT, project, selector("t1")); + PlanNode select2 = new PlanNode(Type.SELECT, select1, selector("t1")); + PlanNode select3 = new PlanNode(Type.SELECT, select2, selector("t1")); + PlanNode source = new PlanNode(Type.SOURCE, select3, selector("t1")); + source.setProperty(Property.SOURCE_NAME, selector("t1")); + select1.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c2")), + Operator.EQUAL_TO, new Literal(100L))); + select2.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c1")), + Operator.LESS_THAN_OR_EQUAL_TO, new Literal(3L))); + select3.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c1")), + Operator.GREATER_THAN_OR_EQUAL_TO, new Literal(1L))); + + // Execute the rule ... + print(access); + PlanNode result = executeRules(access); + print(result); + + // Compare results ... + assertThat(result, is(sameInstance(access))); + assertChildren(access, project); + PlanNode newSelect = project.getFirstChild(); + assertThat(newSelect.getType(), is(Type.SELECT)); + assertThat(newSelect.getSelectors(), is(access.getSelectors())); + assertThat(newSelect.getParent(), is(sameInstance(project))); + Between between = newSelect.getProperty(Property.SELECT_CRITERIA, Between.class); + assertThat(between.getOperand(), is(select2.getProperty(Property.SELECT_CRITERIA, Comparison.class).getOperand1())); + assertThat(between.getLowerBound(), is(select3.getProperty(Property.SELECT_CRITERIA, Comparison.class).getOperand2())); + assertThat(between.getUpperBound(), is(select2.getProperty(Property.SELECT_CRITERIA, Comparison.class).getOperand2())); + assertThat(between.isLowerBoundIncluded(), is(true)); + assertThat(between.isUpperBoundIncluded(), is(true)); + assertChildren(newSelect, select1); + assertChildren(select1, source); + } + + /** + * Before: + * + * <pre> + * Access [t1] + * Project [t1] + * Select [t1] &lt;SELECT_CRITERIA=t1.c2 = 100&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &gt; 3&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &lt; 1&gt; + * Source [t1] &lt;SOURCE_NAME=t1&gt; + * </pre> + * + * And after: + * + * <pre> + * Access [t1] &lt;ACCESS_NO_RESULTS=true&gt; + * Project [t1] + * Select [t1] &lt;SELECT_CRITERIA=t1.c2 = 100&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &gt; 3&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &lt; 1&gt; + * Source [t1] &lt;SOURCE_NAME=t1&gt; + * </pre> + */ + @Test + public void shouldReplaceComparisonsSpecifyingExclusiveRangeWithNotBetweenConstraint() { + // Each of the PROJECT, SELECT, and SELECT nodes must have the names of the selectors that they apply to ... + PlanNode access = new PlanNode(Type.ACCESS, selector("t1")); + PlanNode project = new PlanNode(Type.PROJECT, access, selector("t1")); + PlanNode select1 = new PlanNode(Type.SELECT, project, selector("t1")); + PlanNode select2 = new PlanNode(Type.SELECT, select1, selector("t1")); + PlanNode select3 = new PlanNode(Type.SELECT, select2, selector("t1")); + PlanNode source = new PlanNode(Type.SOURCE, select3, selector("t1")); + source.setProperty(Property.SOURCE_NAME, selector("t1")); + select1.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c2")), + Operator.EQUAL_TO, new Literal(100L))); + select2.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c1")), + Operator.GREATER_THAN, new Literal(3L))); + select3.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c1")), + Operator.LESS_THAN, new Literal(1L))); + + // Execute the rule ... + print(access); + PlanNode result = executeRules(access); + print(result); + + // Compare results ... + assertThat(result, is(sameInstance(access))); + assertChildren(access, project); + assertThat(access.getProperty(Property.ACCESS_NO_RESULTS, Boolean.class), is(true)); + } + + /** + * Before: + * + * <pre> + * Access [t1] + * Project [t1] + * Select [t1] &lt;SELECT_CRITERIA=t1.c2 = 100&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &gt;= 3&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &lt;= 1&gt; + * Source [t1] &lt;SOURCE_NAME=t1&gt; + * </pre> + * + * And after: + * + * <pre> + * Access [t1] &lt;ACCESS_NO_RESULTS=true&gt; + * Project [t1] + * Select [t1] &lt;SELECT_CRITERIA=t1.c2 = 100&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &gt;= 3&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &lt;= 1&gt; + * Source [t1] &lt;SOURCE_NAME=t1&gt; + * </pre> + */ + @Test + public void shouldReplaceComparisonsSpecifyingInclusiveRangeWithNotBetweenConstraint() { + // Each of the PROJECT, SELECT, and SELECT nodes must have the names of the selectors that they apply to ... + PlanNode access = new PlanNode(Type.ACCESS, selector("t1")); + PlanNode project = new PlanNode(Type.PROJECT, access, selector("t1")); + PlanNode select1 = new PlanNode(Type.SELECT, project, selector("t1")); + PlanNode select2 = new PlanNode(Type.SELECT, select1, selector("t1")); + PlanNode select3 = new PlanNode(Type.SELECT, select2, selector("t1")); + PlanNode source = new PlanNode(Type.SOURCE, select3, selector("t1")); + source.setProperty(Property.SOURCE_NAME, selector("t1")); + select1.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c2")), + Operator.EQUAL_TO, new Literal(100L))); + select2.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c1")), + Operator.GREATER_THAN_OR_EQUAL_TO, new Literal(3L))); + select3.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c1")), + Operator.LESS_THAN_OR_EQUAL_TO, new Literal(1L))); + + // Execute the rule ... + print(access); + PlanNode result = executeRules(access); + print(result); + + // Compare results ... + assertThat(result, is(sameInstance(access))); + assertChildren(access, project); + assertThat(access.getProperty(Property.ACCESS_NO_RESULTS, Boolean.class), is(true)); + } + + /** + * Before: + * + * <pre> + * Access [t1] + * Project [t1] + * Select [t1] &lt;SELECT_CRITERIA=t1.c2 = 100&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &lt;= 3&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &gt;= 3&gt; + * Source [t1] &lt;SOURCE_NAME=t1&gt; + * </pre> + * + * And after: + * + * <pre> + * Access [t1] + * Project [t1] + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 = 3&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c2 = 100&gt; + * Source [t1] &lt;SOURCE_NAME=t1&gt; + * </pre> + */ + @Test + public void shouldReplaceComparisonsSpecifyingInclusiveRangeWithOverlappingBoundaryEqualityComparison() { + // Each of the PROJECT, SELECT, and SELECT nodes must have the names of the selectors that they apply to ... + PlanNode access = new PlanNode(Type.ACCESS, selector("t1")); + PlanNode project = new PlanNode(Type.PROJECT, access, selector("t1")); + PlanNode select1 = new PlanNode(Type.SELECT, project, selector("t1")); + PlanNode select2 = new PlanNode(Type.SELECT, select1, selector("t1")); + PlanNode select3 = new PlanNode(Type.SELECT, select2, selector("t1")); + PlanNode source = new PlanNode(Type.SOURCE, select3, selector("t1")); + source.setProperty(Property.SOURCE_NAME, selector("t1")); + select1.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c2")), + Operator.EQUAL_TO, new Literal(100L))); + select2.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c1")), + Operator.LESS_THAN_OR_EQUAL_TO, new Literal(3L))); + select3.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c1")), + Operator.GREATER_THAN_OR_EQUAL_TO, new Literal(3L))); + + // Execute the rule ... + print(access); + PlanNode result = executeRules(access); + print(result); + + // Compare results ... + assertThat(result, is(sameInstance(access))); + assertThat(access.getProperty(Property.ACCESS_NO_RESULTS, Boolean.class), is(nullValue())); + assertChildren(access, project); + PlanNode newSelect = project.getFirstChild(); + assertThat(newSelect.getType(), is(Type.SELECT)); + assertThat(newSelect.getSelectors(), is(access.getSelectors())); + assertThat(newSelect.getParent(), is(sameInstance(project))); + Comparison equality = newSelect.getProperty(Property.SELECT_CRITERIA, Comparison.class); + assertThat(equality.getOperand1(), is(select2.getProperty(Property.SELECT_CRITERIA, Comparison.class).getOperand1())); + assertThat(equality.getOperator(), is(Operator.EQUAL_TO)); + assertThat(equality.getOperand2(), is(select2.getProperty(Property.SELECT_CRITERIA, Comparison.class).getOperand2())); + assertChildren(newSelect, select1); + assertChildren(select1, source); + } + + /** + * Before: + * + * <pre> + * Access [t1] + * Project [t1] + * Select [t1] &lt;SELECT_CRITERIA=t1.c2 = 100&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &lt; 3&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &gt; 3&gt; + * Source [t1] &lt;SOURCE_NAME=t1&gt; + * </pre> + * + * And after: + * + * <pre> + * Access [t1] &lt;ACCESS_NO_RESULTS=true&gt; + * Project [t1] + * Select [t1] &lt;SELECT_CRITERIA=t1.c2 = 100&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &lt; 3&gt; + * Select [t1] &lt;SELECT_CRITERIA=t1.c1 &gt; 3&gt; + * Source [t1] &lt;SOURCE_NAME=t1&gt; + * </pre> + */ + @Test + public void shouldMarkAsHavingNoResultsWhenComparisonsSpecifyRangeWithNonOverlappingBoundary() { + // Each of the PROJECT, SELECT, and SELECT nodes must have the names of the selectors that they apply to ... + PlanNode access = new PlanNode(Type.ACCESS, selector("t1")); + PlanNode project = new PlanNode(Type.PROJECT, access, selector("t1")); + PlanNode select1 = new PlanNode(Type.SELECT, project, selector("t1")); + PlanNode select2 = new PlanNode(Type.SELECT, select1, selector("t1")); + PlanNode select3 = new PlanNode(Type.SELECT, select2, selector("t1")); + PlanNode source = new PlanNode(Type.SOURCE, select3, selector("t1")); + source.setProperty(Property.SOURCE_NAME, selector("t1")); + select1.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c2")), + Operator.EQUAL_TO, new Literal(100L))); + select2.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c1")), + Operator.LESS_THAN, new Literal(3L))); + select3.setProperty(Property.SELECT_CRITERIA, new Comparison(new PropertyValue(selector("t1"), name("c1")), + Operator.GREATER_THAN, new Literal(3L))); + + // Execute the rule ... + print(access); + PlanNode result = executeRules(access); + print(result); + + // Compare results ... + assertThat(result, is(sameInstance(access))); + assertChildren(access, project); + assertThat(access.getProperty(Property.ACCESS_NO_RESULTS, Boolean.class), is(true)); + } + + protected PlanNode executeRules( PlanNode node ) { + while (!rules.isEmpty()) { + OptimizerRule rule = rules.poll(); + assert rule != null; + node = rule.execute(context, node, rules); + } + return node; + } + + protected Name name( String name ) { + return context.getExecutionContext().getValueFactories().getNameFactory().create(name); + } +} Property changes on: trunk/dna-graph/src/test/java/org/jboss/dna/graph/query/optimize/RewriteAsRangeCriteriaTest.java ___________________________________________________________________ Name: svn:keywords + Id Revision Name: svn:eol-style + LF