Return-Path: Delivered-To: apmail-db-derby-commits-archive@www.apache.org Received: (qmail 25272 invoked from network); 16 Nov 2009 09:49:39 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3) by minotaur.apache.org with SMTP; 16 Nov 2009 09:49:39 -0000 Received: (qmail 53450 invoked by uid 500); 16 Nov 2009 09:49:39 -0000 Delivered-To: apmail-db-derby-commits-archive@db.apache.org Received: (qmail 53390 invoked by uid 500); 16 Nov 2009 09:49:39 -0000 Mailing-List: contact derby-commits-help@db.apache.org; run by ezmlm Precedence: bulk list-help: list-unsubscribe: List-Post: Reply-To: "Derby Development" List-Id: Delivered-To: mailing list derby-commits@db.apache.org Received: (qmail 53381 invoked by uid 99); 16 Nov 2009 09:49:39 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 16 Nov 2009 09:49:39 +0000 X-ASF-Spam-Status: No, hits=-2.6 required=5.0 tests=BAYES_00 X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 16 Nov 2009 09:49:36 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id 92F6F23888E5; Mon, 16 Nov 2009 09:49:16 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit 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 -0000 To: derby-commits@db.apache.org From: kahatlen@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20091116094916.92F6F23888E5@eris.apache.org> 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; + +/** + *

+ * 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}. + *

+ * + *

+ * The actual evaluation of the {@code ValueNode}s is performed by invoking + * {@link ValueNode#evaluateConstantExpressions()} on every {@code ValueNode} + * in the query tree. + *

+ * + *

+ * 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}. + *

+ */ +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();