db-derby-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kahat...@apache.org
Subject svn commit: r880693 - in /db/derby/code/trunk/java: engine/org/apache/derby/impl/sql/compile/ testing/org/apache/derbyTesting/functionTests/master/
Date Mon, 16 Nov 2009 09:49:04 GMT
Author: kahatlen
Date: Mon Nov 16 09:48:53 2009
New Revision: 880693

URL: http://svn.apache.org/viewvc?rev=880693&view=rev
Log:
DERBY-4416: Handle comparison of two constants as a boolean constant

Added a visitor that walks the query tree bottom-up and replaces
occurrences of constant expressions like 1<>1, 2<3 and 1=1 with
constants TRUE or FALSE values as appropriate.

Added:
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ConstantExpressionVisitor.java
  (with props)
Modified:
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/DMLStatementNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ValueNode.java
    db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/logop.out
    db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/outerjoin.out
    db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/specjPlans.out

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java?rev=880693&r1=880692&r2=880693&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/BinaryRelationalOperatorNode.java
Mon Nov 16 09:48:53 2009
@@ -981,6 +981,56 @@
 	public String getReceiverInterfaceName() {
 	    return ClassName.DataValueDescriptor;
 	}
+
+    /**
+     * See if the node always evaluates to true or false, and return a Boolean
+     * constant node if it does.
+     *
+     * @return a Boolean constant if the result of the operator is known, or
+     * the operator node otherwise
+     */
+    ValueNode evaluateConstantExpressions() throws StandardException {
+        if (leftOperand instanceof ConstantNode &&
+                rightOperand instanceof ConstantNode) {
+            ConstantNode leftOp = (ConstantNode) leftOperand;
+            ConstantNode rightOp = (ConstantNode) rightOperand;
+            DataValueDescriptor leftVal = leftOp.getValue();
+            DataValueDescriptor rightVal = rightOp.getValue();
+
+            if (!leftVal.isNull() && !rightVal.isNull()) {
+                int comp = leftVal.compare(rightVal);
+                switch (operatorType) {
+                    case EQUALS_RELOP:
+                        return newBool(comp == 0);
+                    case NOT_EQUALS_RELOP:
+                        return newBool(comp != 0);
+                    case GREATER_THAN_RELOP:
+                        return newBool(comp > 0);
+                    case GREATER_EQUALS_RELOP:
+                        return newBool(comp >= 0);
+                    case LESS_THAN_RELOP:
+                        return newBool(comp < 0);
+                    case LESS_EQUALS_RELOP:
+                        return newBool(comp <= 0);
+                }
+            }
+        }
+
+        return this;
+    }
+
+    /**
+     * Create a Boolean constant node with a specified value.
+     *
+     * @param b the value of the constant
+     * @return a node representing a Boolean constant
+     */
+    private ValueNode newBool(boolean b) throws StandardException {
+        return (ValueNode) getNodeFactory().getNode(
+                C_NodeTypes.BOOLEAN_CONSTANT_NODE,
+                Boolean.valueOf(b),
+                getContextManager());
+    }
 	
 	/**
 	 * Returns the negation of this operator; negation of Equals is NotEquals.

Added: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ConstantExpressionVisitor.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ConstantExpressionVisitor.java?rev=880693&view=auto
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ConstantExpressionVisitor.java
(added)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ConstantExpressionVisitor.java
Mon Nov 16 09:48:53 2009
@@ -0,0 +1,91 @@
+/*
+
+   Derby - Class org.apache.derby.impl.sql.compile.ConstantExpressionVisitor
+
+   Licensed to the Apache Software Foundation (ASF) under one or more
+   contributor license agreements.  See the NOTICE file distributed with
+   this work for additional information regarding copyright ownership.
+   The ASF licenses this file to you under the Apache License, Version 2.0
+   (the "License"); you may not use this file except in compliance with
+   the License.  You may obtain a copy of the License at
+
+      http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+
+ */
+
+package org.apache.derby.impl.sql.compile;
+
+import org.apache.derby.iapi.error.StandardException;
+import org.apache.derby.iapi.sql.compile.Visitable;
+import org.apache.derby.iapi.sql.compile.Visitor;
+
+/**
+ * <p>
+ * This visitor replaces a {@code ValueNode} with a node representing a
+ * constant value, if the {@code ValueNode} is known to always evaluate to the
+ * same value. It may for instance replace a sub-tree representing {@code 1=1}
+ * with a constant {@code TRUE}.
+ * </p>
+ *
+ * <p>
+ * The actual evaluation of the {@code ValueNode}s is performed by invoking
+ * {@link ValueNode#evaluateConstantExpressions()} on every {@code ValueNode}
+ * in the query tree.
+ * </p>
+ *
+ * <p>
+ * In contrast to most other visitors, this visitor walks the tree bottom-up.
+ * Top-down processing of the tree would only evaluate constant expressions
+ * at the leaf level, so for instance {@code (1=1)=(1=2)} would only be
+ * simplified to {@code TRUE=FALSE}. With bottom-up processing, the top-level
+ * = node will be processed after the leaves, and it sees the intermediate
+ * tree {@code TRUE=FALSE} which it is able to transform into the even simpler
+ * tree {@code FALSE}.
+ * </p>
+ */
+class ConstantExpressionVisitor implements Visitor {
+
+    /**
+     * Visit the node and call {@code evaluateConstantExpressions()} if it
+     * is a {@code ValueNode}.
+     *
+     * @see ValueNode#evaluateConstantExpressions()
+     */
+    public Visitable visit(Visitable node) throws StandardException {
+        if (node instanceof ValueNode) {
+            node = ((ValueNode) node).evaluateConstantExpressions();
+        }
+        return node;
+    }
+
+    /**
+     * {@inheritDoc}
+     * @return {@code false}, since the entire tree should be visited
+     */
+    public boolean stopTraversal() {
+        return false;
+    }
+
+    /**
+     * {@inheritDoc}
+     * @return {@code false}, since the entire tree should be visited
+     */
+    public boolean skipChildren(Visitable node) {
+        return false;
+    }
+
+    /**
+     * {@inheritDoc}
+     * @return {@code true}, since the tree should be walked bottom-up
+     */
+    public boolean visitChildrenFirst(Visitable node) {
+        return true;
+    }
+
+}

Propchange: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ConstantExpressionVisitor.java
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/DMLStatementNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/DMLStatementNode.java?rev=880693&r1=880692&r2=880693&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/DMLStatementNode.java
(original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/DMLStatementNode.java
Mon Nov 16 09:48:53 2009
@@ -318,6 +318,16 @@
 		resultSet = resultSet.preprocess(getCompilerContext().getNumTables(),
 										 null,
 										 (FromList) null);
+
+		// Evaluate expressions with constant operands here to simplify the
+		// query tree and to reduce the runtime cost. Do it before optimize()
+		// since the simpler tree may have more accurate information for
+		// the optimizer. (Example: The selectivity for 1=1 is estimated to
+		// 0.1, whereas the actual selectivity is 1.0. In this step, 1=1 will
+		// be rewritten to TRUE, which is known by the optimizer to have
+		// selectivity 1.0.)
+		accept(new ConstantExpressionVisitor());
+
 		resultSet = resultSet.optimize(getDataDictionary(), null, 1.0d);
 
 		resultSet = resultSet.modifyAccessPaths();

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java?rev=880693&r1=880692&r2=880693&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/JoinNode.java Mon Nov
16 09:48:53 2009
@@ -1957,6 +1957,11 @@
 		{
 			usingClause = (ResultColumnList)usingClause.accept(v);
 		}
+
+		if (joinPredicates != null)
+		{
+			joinPredicates = (PredicateList) joinPredicates.accept(v);
+		}
 	}
 
 	// This method returns the table references in Join node, and this may be

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ValueNode.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ValueNode.java?rev=880693&r1=880692&r2=880693&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ValueNode.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/sql/compile/ValueNode.java Mon Nov
16 09:48:53 2009
@@ -461,6 +461,22 @@
 		return this;
 	}
 
+    /**
+     * If this node is known to always evaluate to the same value, return a
+     * node that represents that known value as a constant. Typically used to
+     * transform operators with constant operands into constants.
+     *
+     * @return a constant representing the value to which this node is
+     * guaranteed to evaluate, or {@code this} if the value is not known
+     * @throws StandardException if an error occurs during evaluation
+     * @see ConstantExpressionVisitor
+     */
+    ValueNode evaluateConstantExpressions() throws StandardException {
+        // We normally don't know what the node evaluates to up front, so
+        // don't do anything in the default implementation.
+        return this;
+    }
+
 	/**
 	 * Eliminate NotNodes in the current query block.  We traverse the tree, 
 	 * inverting ANDs and ORs and eliminating NOTs as we go.  We stop at 

Modified: db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/logop.out
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/logop.out?rev=880693&r1=880692&r2=880693&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/logop.out
(original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/logop.out
Mon Nov 16 09:48:53 2009
@@ -252,7 +252,8 @@
 1          
 ij> -- ... and false and ... should get resolved to false
 select x from s where 2147483647 + 10 = 2 and (1=2);
-ERROR 22003: The resulting value is outside the range for the data type INTEGER.
+X          
+-----------
 ij> select x from s where (1=2) and 2147483647 + 10 = 2;
 X          
 -----------

Modified: db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/outerjoin.out
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/outerjoin.out?rev=880693&r1=880692&r2=880693&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/outerjoin.out
(original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/outerjoin.out
Mon Nov 16 09:48:53 2009
@@ -1777,7 +1777,7 @@
 Begin Execution Timestamp : null
 End Execution Timestamp : null
 Statement Execution Plan Text: 
-Nested Loop Left Outer Join ResultSet:
+Hash Left Outer Join ResultSet:
 Number of opens = 1
 Rows seen from the left = 3
 Rows seen from the right = 2
@@ -1824,72 +1824,62 @@
 			qualifiers:
 				None
 	Right result set:
-		Project-Restrict ResultSet (5):
+		Hash Scan ResultSet for T2 at read committed isolation level using instantaneous share
row locking: 
 		Number of opens = 5
+		Hash table size = 4
+		Hash key is column number 0
 		Rows seen = 3
 		Rows filtered = 0
-		restriction = false
-		projection = false
 			constructor time (milliseconds) = 0
 			open time (milliseconds) = 0
 			next time (milliseconds) = 0
 			close time (milliseconds) = 0
-			restriction time (milliseconds) = 0
-			projection time (milliseconds) = 0
-		Source result set:
-			Hash Scan ResultSet for T2 at read committed isolation level using instantaneous share
row locking: 
-			Number of opens = 5
-			Hash table size = 4
-			Hash key is column number 0
-			Rows seen = 3
-			Rows filtered = 0
-				constructor time (milliseconds) = 0
-				open time (milliseconds) = 0
-				next time (milliseconds) = 0
-				close time (milliseconds) = 0
-				next time in milliseconds/row = 0
-			scan information: 
-				Bit set of columns fetched=All
-				Number of columns fetched=1
-				Number of pages visited=1
-				Number of rows qualified=5
-				Number of rows visited=5
-				Scan type=heap
-				start position:
-					null
-				stop position:
-					null
-				scan qualifiers:
-					None
-				next qualifiers:
-					Column[0][0] Id: 0
-					Operator: =
-					Ordered nulls: false
-					Unknown return value: false
-					Negate comparison result: false
+			next time in milliseconds/row = 0
+		scan information: 
+			Bit set of columns fetched=All
+			Number of columns fetched=1
+			Number of pages visited=1
+			Number of rows qualified=5
+			Number of rows visited=5
+			Scan type=heap
+			start position:
+				null
+			stop position:
+				null
+			scan qualifiers:
+				None
+			next qualifiers:
+				Column[0][0] Id: 0
+				Operator: =
+				Ordered nulls: false
+				Unknown return value: false
+				Negate comparison result: false
 Right result set:
-	Table Scan ResultSet for T3 at read committed isolation level using instantaneous share
row locking chosen by the optimizer
+	Hash Scan ResultSet for T3 at read committed isolation level using instantaneous share row
locking: 
 	Number of opens = 3
+	Hash table size = 4
+	Hash key is column number 0
 	Rows seen = 2
 	Rows filtered = 0
-	Fetch Size = 16
 		constructor time (milliseconds) = 0
 		open time (milliseconds) = 0
 		next time (milliseconds) = 0
 		close time (milliseconds) = 0
 		next time in milliseconds/row = 0
-	scan information:
+	scan information: 
 		Bit set of columns fetched=All
 		Number of columns fetched=1
 		Number of pages visited=1
-		Number of rows qualified=2
-		Number of rows visited=15
+		Number of rows qualified=5
+		Number of rows visited=5
 		Scan type=heap
 		start position:
 			null
 		stop position:
 			null
-		qualifiers:
+		scan qualifiers:
+			None
+		next qualifiers:
 			Column[0][0] Id: 0
 			Operator: =
 			Ordered nulls: false

Modified: db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/specjPlans.out
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/specjPlans.out?rev=880693&r1=880692&r2=880693&view=diff
==============================================================================
--- db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/specjPlans.out
(original)
+++ db/derby/code/trunk/java/testing/org/apache/derbyTesting/functionTests/master/specjPlans.out
Mon Nov 16 09:48:53 2009
@@ -908,41 +908,28 @@
 Begin Execution Timestamp : null
 End Execution Timestamp : null
 Statement Execution Plan Text: 
-Project-Restrict ResultSet (2):
+Table Scan ResultSet for M_LARGEORDER at read committed isolation level using instantaneous
share row locking chosen by the optimizer
 Number of opens = 1
 Rows seen = 0
 Rows filtered = 0
-restriction = false
-projection = false
+Fetch Size = 16
 	constructor time (milliseconds) = 0
 	open time (milliseconds) = 0
 	next time (milliseconds) = 0
 	close time (milliseconds) = 0
-	restriction time (milliseconds) = 0
-	projection time (milliseconds) = 0
-Source result set:
-	Table Scan ResultSet for M_LARGEORDER at read committed isolation level using instantaneous
share row locking chosen by the optimizer
-	Number of opens = 1
-	Rows seen = 0
-	Rows filtered = 0
-	Fetch Size = 16
-		constructor time (milliseconds) = 0
-		open time (milliseconds) = 0
-		next time (milliseconds) = 0
-		close time (milliseconds) = 0
-	scan information:
-		Bit set of columns fetched=All
-		Number of columns fetched=6
-		Number of pages visited=1
-		Number of rows qualified=0
-		Number of rows visited=0
-		Scan type=heap
-		start position:
-			null
-		stop position:
-			null
-		qualifiers:
-			None
+scan information:
+	Bit set of columns fetched=All
+	Number of columns fetched=6
+	Number of pages visited=1
+	Number of rows qualified=0
+	Number of rows visited=0
+	Scan type=heap
+	start position:
+		null
+	stop position:
+		null
+	qualifiers:
+		None
 ij> UPDATE M_INVENTORY  SET IN_QTY = 1, IN_LOCATION = 'sanfrancisco', IN_ACC_CODE = 1,
IN_ACT_DATE = '01/01/2003', IN_ORDERED = 1 WHERE IN_P_ID = 'abcdefghijklm';
 0 rows inserted/updated/deleted
 ij> values SYSCS_UTIL.SYSCS_GET_RUNTIMESTATISTICS();
@@ -2933,41 +2920,28 @@
 Begin Execution Timestamp : null
 End Execution Timestamp : null
 Statement Execution Plan Text: 
-Project-Restrict ResultSet (2):
+Table Scan ResultSet for S_SUPPLIER at read committed isolation level using instantaneous
share row locking chosen by the optimizer
 Number of opens = 1
 Rows seen = 0
 Rows filtered = 0
-restriction = false
-projection = false
+Fetch Size = 16
 	constructor time (milliseconds) = 0
 	open time (milliseconds) = 0
 	next time (milliseconds) = 0
 	close time (milliseconds) = 0
-	restriction time (milliseconds) = 0
-	projection time (milliseconds) = 0
-Source result set:
-	Table Scan ResultSet for S_SUPPLIER at read committed isolation level using instantaneous
share row locking chosen by the optimizer
-	Number of opens = 1
-	Rows seen = 0
-	Rows filtered = 0
-	Fetch Size = 16
-		constructor time (milliseconds) = 0
-		open time (milliseconds) = 0
-		next time (milliseconds) = 0
-		close time (milliseconds) = 0
-	scan information:
-		Bit set of columns fetched=All
-		Number of columns fetched=10
-		Number of pages visited=1
-		Number of rows qualified=0
-		Number of rows visited=0
-		Scan type=heap
-		start position:
-			null
-		stop position:
-			null
-		qualifiers:
-			None
+scan information:
+	Bit set of columns fetched=All
+	Number of columns fetched=10
+	Number of pages visited=1
+	Number of rows qualified=0
+	Number of rows visited=0
+	Scan type=heap
+	start position:
+		null
+	stop position:
+		null
+	qualifiers:
+		None
 ij> UPDATE U_SEQUENCES  SET S_NEXTNUM = 1	, S_BLOCKSIZE = 1000 WHERE S_ID = 'abcdefghijklmnopqrstuvwxyz';
 0 rows inserted/updated/deleted
 ij> values SYSCS_UTIL.SYSCS_GET_RUNTIMESTATISTICS();



Mime
View raw message